A while ago I wrote mainly about OBB algorithms but a little note about convex hull simplification
It's a little unclear, so I clarified :
My algorithm is very simple and by no means optimal.
I construct a standard (exact) convex hull, then make a mesh from it. I then run a normal mesh simplifier (see for example Garland Heckbert Quadric Error Metrics) to simplify the CH as if it was a mesh. This can ruin inclusion. I then fix it by taking all the face planes of the simplified mesh and pushing them out past any vert in the original mesh.
Stan's (Melax - Convex Hull Simplification With Containment By Successive Plane Removal) way is similar but better. He uses a BSP engine to create the hull. First he finds a normal convex hull. Then he considers only the planes that make up that hull. The working hull is the volume that is on the "front" side of all planes. He then considers removing planes one by one. When you remove a plane, the cost to remove it is the volume that is added to the hull, which is the volume of the space that is on the back side of that plane but is on the front side of all other planes. You create a heap to do this so that the total cost to simplify is only N log N. This requires good BSP code which I don't have, which is why I used the mesh-simplifier approach.
An alternative in the literature is the "progressive hull" technique. This is basically using PM methods but directly considering the mesh as a hull during simplification instead of fixing it after the fact as I do. Probably a better way is to use a real epsilon-hull finder from the beginning rather than finding the exact hull and then simplifying.
My code is in Galaxy4 / gApp_HullTest which is available here ; You should be able to run "Galaxy4.exe hull" ; Hit the "m" key to see various visualations ; give it a mesh argument if you have one (takes .x, .m , .smf etc.)
BTW to summarize : I don't really recommend my method. It happens to be easy to implement if you have a mesh simplifier lying around. Stan's method is also certainly not optimal but is easy to implement if you have good BSP code lying around (and is better than mine (I suspect)).
The technique I actually prefer is to just use k-dops. k-dops are the convex hull made from the touching planes in a fixed set of k directions. Maybe find the optimal OBB and use that as the axis frame for the k directions. Increase k until you are within the desired error tolerance (or k exceeds the number of faces in the exact hull).
ASIDE : I have some BSP code but I hate it; I hate all floating point geometry code. I love integer geometry code. The problem with integers in BSP's is that clipping creates rational points. Maybe I'll write some BSP routines based on rational Vec3's. The only big problem is that the precision requirement goes up with each clip. So you either need arbitrary precision rationals or you have to truncate the precision at some maximum, and then handle the errors created by that (like the truncated point could move onto the back side of a plane that you said you were in front of). (this is better than the errors in floating points, because at least the truncated point is at a definite well defined location, floating points move around depending on how you look at them, those wiggly bastards) (I'm tempted to say that they're like quantum mechanics in that they change when you measure them, except that they really aren't at all, and that's the type of pseudo-scientific-mumbo-jumbo that pseudo-intellectual fucktards love and I so despise, so no, I won't say it).
I have in-development CSG code that starts from planes and infers points from them. You never need to do anything other than find the intersection of three planes (and see whether another plane falls on either side of it).
ReplyDeleteIIRC, the main datatype is rationals with 128-bit numerators and denominators. The input planes have 23-bit integer normals and ~50 bit integer distance-from-integers. (The idea being that it allows you nearly float-precise plane orientations, and double-sized worlds.)
So (a) I bet if you work through the math you can do it without generic multiprecision code, and (b) if you want I can send you the current version and you can use my code, but you probably wouldn't want it.
Argh, I left out the main thing I wanted to say, which is that, because of the design, the precision required never grows, no matter how complex the objects. It's always just an operation on four *input* planes.
ReplyDeleteI assume for convex hull, something similar can be done where planes are defined on three input vertices, and then you're comparing a fourth input vertex.
In fact, I was inspired to do this by somebody's exact-integer convex hull patch for bullet; reading the code I realized it didn't seem that scary. http://code.google.com/p/bullet/issues/detail?id=275
Convex hull in ints is pretty easy; cblib/galaxy has done convex hull in ints forever. The only operation you need is :
ReplyDelete"given 4 points, what's the volume"
I use 64 bit temporaries which means I get 19 bits for coordinates, which is plenty for instanced models but probably not enough if you treated your whole world as one model.
I was thinking of BSP ops like "generate the point from clipping these planes" , now generate new planes from points made from clipping; each time you do that the precision requirements grow. But I guess as long a you only use planes made from input verts that never arises.
It's not fully general BSP code though. Say for example you want to generate the portals out of the leafs (requires points generated by clipping). Then you want to do something like PVS which involves generating new planes that go through the portals - you're increasing precision. Probably if you're clever you can reformulate all queries in terms of only original planes, but it's less straightforward it seems to me.
Yeah, that's probably true. I guess the question is whether you can simplify directly somehow.
ReplyDeleteyay for textfields that don't remember previous values when you come 'back' to them. sigh.
ReplyDeleteresummarizing. "blah blah BSP isn't convex hull, ok yes, but PVS isn't BSP. And PVS only needs conservative stuff"
Can you do simple CSG with BSP's without infinite precision? eg. given two models, find the union or intersection. Certainly the naive implementation involves cutting against a plane, then cutting the results of that, etc. and each time you cut you increase the precision requirements. But maybe there's a better way?
ReplyDeleteAnyhoo.. I do imagine that you certainly could do approximate convex hull in ints, which currently I don't do nicely.
Also obviously you would really like to find the approximate hull directly, rather than finding the exact hull then simplifying.
etc. I mean really, this is not meant to be a good solution to this problem.
If the input to CSG is planes, then you can do it without infinite precision. Every vertex you generate from operations is always the intersection of 3 input planes. So the needed precision is finite.
ReplyDeleteThe only operation you need is "point on side of plane test", where point is defined as the intersection of 3 planes. So the whole thing works out to a big 4x4 determinant or something, I forget exactly. I tweaked the input precision a bunch to try to find the sweet spot for 128-bit precision.
For BSP it's different unless the inputs are defined based on planes (e.g. if you took the output of the CSG and did BSP on it, they would be). But I'm not sure there's a good way of defining exact input to BSP--as soon as you want to have 4- or more-sided polygons, how do you define the vertices to guarantee that they're exactly planar (so that exact arithmetic can be well behaved)?
Of course you have the dual problem with planes; if you're supposed to have more than 3 planes meeting at a single vertex, they might not in exact arithmetic. For CSG this isn't a problem because a collection of half-spaces always defines a convex polyhedron (assuming it's closed at all), so even if it's not quite the polyhedron you meant it's still something.
A non-planar polygon would be a trickier starting point.