View Full Version : (OT) Polygon optimizing routine.

06-10-2003, 02:10 PM
I was wondering if anyone has seen an algorithm or written an alogorithm that will do the following. (I fear I may have to write it myself). I want to be able to take a triangle mesh (all one texture). Feed that mesh to an algorithm that will optimize the polys (without changing the shape at all) and wont mess up the texture coords. Example, say i have a wall mesh, the wall mesh is 10 units long, 10 units high and maybe has some holes in it (not nessesary, but it adds a mark of difficutly). And all the same texture.

Say i have 2 triangles for every square unit, making 200 triangles all togeather. (well maybe less for the holes). That is TOO many polys for that one wall, (but do to the type of model im working with that is what i get to start with). I would like an algorithm to feed these 200 some polys to and have it spit out say 2 polys (cause the wall could just have 2 giangt polys), but maybe more because of the holes. And I would like the algorithm not to mess up the texture coords as well, basicaly if it sees a gap in the texture coords between points, it either dosnt optimize that point, or it skips it. Get it??? Im not explaining it well, but i hope you understand. Has anyone ever seen or heard of something that will do this? I understand it wouldnt be that hard to do that to just a wall, but i would like to feed it much more difficult meshs than that obviosly. Thank you very much in advance.

06-10-2003, 02:27 PM
Seems like this falls into the realm of LOD. I'd take alook at Hoppe's "progressive meshes":


06-10-2003, 04:50 PM
I've done something similar. It took quite a while to get it to be robust. The basic algorithm for what I did was to take the original geometry, merge all of its polygons as much as possible into complex polygons, and then use a heuristic to efficiently triangulate those complex polygons.

Rather than directly storing texture coordinates I stored the parametric functions to get texture coordinates from a vertex position; likewise, I did this for vertex colors. This simplifies splits and mergability tests; for example, if you have two quads next to each other that don't texture seam but one is mirrored, storing the equations will give correct results while merely checking texture coordinates could screw up.

Almost all of the trickiness is in handling epsilon issues and in removing / simplifying the "tendrils" or "tethers" that connect holes inside a complex polygon to its perimeter. I also wanted to eliminate all t-junctions.

06-11-2003, 01:13 AM
I did something like this before. It is a lot of work, but it isnīt really hard.

My approach was very simple: Check all triangles against all others and find all triangles that have two vertices in commen. If i found two triangles, which have two vertices in common, i just merged them (watch out for the vertex-winding afterwards!). However if they had a different texture or different texcoords at the vertices, i didnīt merge them.
After i did this process with all triangles, i repeated it with the new mesh to minimize the trianglecount even more. Just make it recursive until no triangles get merged anymore.
One other thing to watch out is, that two merged polys could be concave.
If you want only triangles (i work with polys in that program), you can triangulate it afterwards.

This approach is very simple, because it only merges triangles, that have two vertices in common. However this yields to surprisingly good results in most situations. I did this with all objects, which got split in a CSG operation and it worked very well.