## Trouble with mesh simplification

Sage
Posts: 1,199
Joined: 2004.10
Post: #1
My marching cubes code does an excellent job tessellating a voxel space, but it does produce an enormous number of triangles. I've been researching approaches to simplify the output in ( more or less ) real time, and have tried a couple of algorithms based on collapsing edges.

So, the one that works best is from here:
http://jsomers.com/vipm_demo/meshsimp.html

The algorithm does a pretty damn good job at simplifying my test mesh -- it goes from ~40k triangles to 4k without a significant distortion of appearance. Awesome, right?

Here's the problem. The output mesh is missing a few triangles. Here's a screenshot; the optimized mesh is on the right. You can see a few holes in it.

I figured at first that those triangles just had their windings reversed, but no, there's actually no triangle there at all. It's a hole!

So I'm trying to come up with a way to "plug" the holes. My idea is to compute triangle connectivity -- each triangle in a closed mesh should share an edge with three others. Each "hole" could be thought of as three vertices connecting three trianges which each have a missing neighbor. I could generate a triangle from that info.

But it's easier said than done. Does anybody here have any suggestions for algorithms ( or general approaches ) that might do this effectively? I'm open to suggestions; I want to think this through before I go further.

Of course, there might be some library out there that does a real bang-up job at mesh simplification. If any of you happen to know of such a thing, I'm open to suggestions. I'm by no means married to the code I'm using right now!
Member
Posts: 320
Joined: 2003.06
Post: #2
I haven't done anything like this. But firstly I would try to stop the algorithm from making holes in the first place. Otherwise, be careful as you can't be sure that for instance 2 or more missing triangles might show up next to each other.

Perhaps the missing triangles are sharing a single vertex for 2 corners? Perhaps it could be a precision error and (if you're not already) using doubles could reduce the occurrence enough?

Chopper, iSight Screensavers, DuckDuckDuck: http://majicjungle.com
Member
Posts: 45
Joined: 2006.07
Post: #3
I like qslim (http://graphics.cs.uiuc.edu/~garland/sof...qslim.html) for offline mesh simplification. I tend to feed it OBJ files on the command line.

You can compile it as a library, but I don't know how it performs in that setting. Also, licensing might be an issue. I *think* it's LGPL, but not sure.
Moderator
Posts: 869
Joined: 2003.01
Post: #4
Sounds like you just have a bug, either in your simplification algorithm, or your original mesh connectivity. It looks like you're not only missing triangles, but in some places the simplification just seems wrong, too.
Sage
Posts: 1,199
Joined: 2004.10
Post: #5
RIght now I'm investigating that my own connectivity code is screwed. Since MarchingCubes just gives you a triangle soup, I have code which attempts to "stitch" it together.

Recently, I rewrote that code using boost::unordered_map and while biking to work this morning it occurred to me that my old code ( using nested std::map mapping x->y->z->vertexIndex ) while slightly slower, did "snap" very close vertices together. The unordered_map code doesn't...

Hopefully this is my problem

EDIT: To clarify, what I mean is that boost::unordered_map is a hashtable. Two different objects which generate the same hash will not occupy the same place, thanks to buckets. I wasn't thinking of the bucketing of overlapping hashes. Which means that my hasher function, which snaps close vertices together, is irrelevant since the two very close vertices will still be distinct in storage.
Moderator
Posts: 869
Joined: 2003.01
Post: #6
That sounds like a horrible way to do stitching

Ideally, your algorithmic complexity should not exceed O(n log n) (for the sorting), but it seems to me like yours is much more complex.
Sage
Posts: 1,199
Joined: 2004.10
Post: #7
Well, when you screw it up it's a horrible way to stitch...

For what it's worth, the stitcher is pretty damn fast. I'm mapping the vertex position to the index in the vertex array, it's easy enough, and not complex at all. I've reverted to the old stitching code, albeit cleaned up a little. But the simplificator it still leaving holes in my mesh, so something's still wonky.
Sage
Posts: 1,199
Joined: 2004.10
Post: #8
So, a quick update. I randomly "wiggled" the vertices of my mesh after tesselation as an experiment -- the argument being that if the triangles aren't stitched correctly, and I do have duped vertices, I'd see cracks in the rendering.

And I don't see any cracks. This implies to me that my stitching is in fact working correctly. So the problem must lie elsewhere...

I downloaded qslim, and will look it over. My work isn't commercial, it's just for fun so I don't think the license would be an issue. Barring that, the cgal libraries have mesh simplification, which may be more robustly implemented.
Moderator
Posts: 869
Joined: 2003.01
Post: #9
Just because you don't see any cracks, doesn't mean connectivity is computed correctly. It just means that your triangles are pointing to the right vertices, but possibly computing which/how triangles share an edge is borked. Or, more likely, the simplification doesn't correctly recompute and update the newly created triangles/neighbours.
Sage
Posts: 1,199
Joined: 2004.10
Post: #10
I'm going to write a test to once and for all let me know if any dupes are making it past the stitching. I've almost completely rewritten my stitching code in the last day or so to be much more robust... but hey, it's possible it's still acting wonky.

An interesting note: I also implemented the Melax algorithm, and while it does produce some weirdness of other sorts, it doesn't have holes in the output mesh. It's possible that the algorithm I'm using just has problems.
Luminary
Posts: 5,125
Joined: 2002.04
Post: #11
I don't know why you're assuming it's an algorithmic bug rather than a code bug. I mean, it could be either, but if it were me, I'd be assuming my code was buggy...
Sage
Posts: 1,199
Joined: 2004.10
Post: #12
Well, a couple things.

1) I wrote some code to verify whether or not my stitcher is allowing dupes. It just checks forthe closest two vertices and checks whether they're closer than the min threshold for snapping. The good news is that I have no dupes! Whew.

2) Using this code: http://www.melax.com/polychop I don't get holes; but there is some vast pseudo degenerate triangle weirdness. Which is to say, the resultant geometry is valid, but wonky.

3) Using the demo code from Jeff Somers' site, I still get holes.

Now, regarding the implementation of the algorithms. I really don't have the wherewithal to implement these algorithms from scratch, particularly not while I'm still evaluating them. So I basically just wrote adapters to pipe my geometry to their interfaces; and adapters to pipe their output into my geometry format.

So I haven't screwed with their code; which is why I'm so baffled. If I'd reimplemented the edge collapse algorithm on my own ( I did, originally! And it wasn't pretty. ) I'd be suspicious of my implementation.

I suppose I can be suspicious of my adapter code, but frankly, that code's dead simple.
Sage
Posts: 1,199
Joined: 2004.10
Post: #13
I'm looking into CGAL for edge collapse now. CGAL is some hardcore C++; frankly, it's a little scary. But I think I grok it enough to use it.
Sage
Posts: 1,199
Joined: 2004.10
Post: #14
It's been a few days; I've been dealing with a family emergency. But yesterday I installed the CGAL library.

And let me say, looking over CGAL, I finally understand why so many people hate C++. Holy Moses! CGAL is appaling. Everything is templated to one inch of its life. Everything, literally everything is an abstracted typedef of inherited traits. It took me 15 minutes of reading the documentation just to figure out how to extract a vertex from some baffling iterator type. God, it took me 2 hours just to write a simple test which transmogrifies my geometry data to CGAL's polyhedron_3<oh,my,god,<nested<templated<horror>>> and to then convert that surface back to my geometry type.

And of course, I didn't quite do it right. But the documentation doesn't tell you how to generate a surface, much less how to extract data from it. I've had to pore through the iostream serializer code to figure out how to actually create a surface, but the templated datatype definitions are so opaque I can't figure out what the hell is actually going on.

I think I might write some cocoa for a while after this to clear my head. ObjC/Cocoa are really a thing of beauty.
Moderator
Posts: 869
Joined: 2003.01
Post: #15
Add to that the fact that there's no binary ABI compatibility between compilers, and you have a lot of fun using more than two pieces of software together, or, god help it, trying to actually use C++ code in Win32 DLLs