2 replies to this topic

[Zesterer]

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

[Gamer3D]

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.

[Zesterer]

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

Zesterer