tag:blogger.com,1999:blog-5246987755651065286.post66863413913127424..comments2023-03-24T22:50:18.274-07:00Comments on cbloom rants: 08-14-11 - A note on convex hull simplificationcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-5246987755651065286.post-91475789094020993222011-08-22T20:45:56.614-07:002011-08-22T20:45:56.614-07:00If the input to CSG is planes, then you can do it ...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.<br /><br />The 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.<br /><br />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)?<br /><br />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.<br /><br />A non-planar polygon would be a trickier starting point.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-42601031181808986402011-08-18T16:21:11.545-07:002011-08-18T16:21:11.545-07:00Can you do simple CSG with BSP's without infin...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?<br /><br />Anyhoo.. I do imagine that you certainly could do approximate convex hull in ints, which currently I don't do nicely.<br /><br />Also obviously you would really like to find the approximate hull directly, rather than finding the exact hull then simplifying.<br /><br />etc. I mean really, this is not meant to be a good solution to this problem.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-45475101596863020822011-08-16T11:19:57.453-07:002011-08-16T11:19:57.453-07:00yay for textfields that don't remember previou...yay for textfields that don't remember previous values when you come 'back' to them. sigh.<br /><br />resummarizing. "blah blah BSP isn't convex hull, ok yes, but PVS isn't BSP. And PVS only needs conservative stuff"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-42418764886852000552011-08-16T11:14:12.207-07:002011-08-16T11:14:12.207-07:00Yeah, that's probably true. I guess the questi...Yeah, that's probably true. I guess the question is whether you can simplify directly somehow.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-11519021589635624872011-08-15T16:11:02.357-07:002011-08-15T16:11:02.357-07:00Convex hull in ints is pretty easy; cblib/galaxy h...Convex hull in ints is pretty easy; cblib/galaxy has done convex hull in ints forever. The only operation you need is :<br /><br />"given 4 points, what's the volume"<br /><br />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.<br /><br />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.<br /><br />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.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-22931858356470204482011-08-15T14:02:28.199-07:002011-08-15T14:02:28.199-07:00Argh, I left out the main thing I wanted to say, w...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.<br /><br />I 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.<br /><br />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=275Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-42457805638022507192011-08-15T14:00:12.462-07:002011-08-15T14:00:12.462-07:00I have in-development CSG code that starts from pl...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).<br /><br />IIRC, 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.)<br /><br />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.Anonymousnoreply@blogger.com