# Optimising a voxel-polygon mesh

2 replies to this topic

### #1 Zesterer

Zesterer

Professor of Articul

• GMC Member
• 1019 posts
• Version:GM8

Posted 29 July 2012 - 07:18 AM

Hey there,

I am currently developing a voxel engine that makes use of a 3D arrays to convert voxel data into a 3D polygon mesh based on blocks (not marching cubes). However, it is obvious that the mesh is not optimised - there are flat areas that are inefficiently composed of up to 40 polygons, when they only require 3 or 4.

My first thought was to split up the voxel data into 2D planes, but I still need an algorithm that can find the most efficient way of covering a 2D plane (with holes) in to polygons. I have wracked my brain, but I cannot find a solution.

Any ideas or pointers as to where I should go?

P.S: This is NOT another bad Minecraft clone, it only resembles Minecraft in the sense that it has 3D cubes.

Zesterer
• 0

### #2 Gamer3D

Gamer3D

Human* me = this;

• GMC Member
• 1590 posts
• Version:GM8.1

Posted 29 July 2012 - 08:29 AM

You could try using edge-contraction methods. Find pairs of triangles that share an edge, and find the pair which, if you get rid of them by pulling the vertexes together, would be closest to the original mesh.

Obviously, edges like the ones you describe will make no difference to the mesh, so they will be eliminated first (or your algorithm is implemented wrong). If you want it to make no visual difference, stop when it can't find perfect edges to contract.

Note that you'll need to pay special attention to the UV mapping. If UV map of the edge and its surrounding triangles has a gap, then contracting the edge will change the mapping.

Of course, you don't want to run through the entire mesh multiple times, so only re-evaluate the edges of triangles that had one of the moved vertexes.
• 2

### #3 Zesterer

Zesterer

Professor of Articul

• GMC Member
• 1019 posts
• Version:GM8

Posted 29 July 2012 - 09:46 AM

Thank you Gamer3D, that is very helpful. I would have never found that algorithm without you. +1 to you, and thanks again!

Zesterer
• 0

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users