tag:blogger.com,1999:blog-5246987755651065286.post3661212699841227581..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 10-18-10 - Frustum and RadiusInDirectioncbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5246987755651065286.post-7790208642563846502010-10-19T11:09:58.549-07:002010-10-19T11:09:58.549-07:00For example I've often seen this with Dave Ebe...For example I've often seen this with Dave Eberly's geometry intersection stuff.<br /><br />He tends to find intersections by just plugging in the equations for the primitives and finding where they are equal.<br /><br />This often leads to very ugly and inefficient code.<br /><br />If instead you form equations based on the symmetries and geometric tests, you wind up with code that is usually (*) not only much cleaner and easier to read but also faster.<br /><br />(* = obviously this is not always true, it's just a rule of thumb, there's no gaurantee that the elegant way of writing something is actually the most efficient)cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-75724852575028173332010-10-19T10:49:56.123-07:002010-10-19T10:49:56.123-07:00" I don't really buy the claim that this ..." I don't really buy the claim that this arises "naturally" (i.e. "automatically") from using some kind of type-based dispatch mechanism. "<br /><br />No no, I don't mean "natural" as in the templates or the C++ junk, I mean "natural" as in the mathematical choice of variables and way of expressing the mathematics.<br /><br />This is a very common theme in physics but I guess it isn't that well known in CS.<br /><br />In physics there's this sort of superstition (which turns out to be true very often so I guess its more of a rule of thumb) that if you simply phrase your problem in the correct coordinates and with the right symmetries, then the simplest, most beautiful way to solve it pops right out.<br /><br />A lot of problems in physics are a tedious nightmare to solve if you just go about them in a brute force way from cartesian coordinates, but they can become super simple if you find the "natural" way of writing them.<br /><br />eg. if you're trying to solve a field equation, if you first transform the field into a basis where the basis functions have the same symmetry as the problem, the math becomes very easy.<br /><br />The thing I observed is that the right way to make an interface for Generic Programming is to think about what the "natural" mathematical way is to talk to these different objects. And it just so turns out that the natural way is often efficient computationally.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-11159188605172715122010-10-19T04:14:09.534-07:002010-10-19T04:14:09.534-07:00Maybe there's some more subtle point at work, ...Maybe there's some more subtle point at work, but I interpreted that part of the post as simply being about how the compiler flattens all the templates out at compile time. So you can just write the natural routine, in a natural sort of way, and you'll end up with as many instantiations as you need, each one compiled as if you'd written it out by hand. So, at best, you end up with something pretty good at the end, and you've written M+N parts rather than M*N.<br /><br />And at worst, you end up with something more like boost... That takes a bit of effort, though! -- for most code, any templates required are usually straightforward.<br /><br />(You could do something similar with macros if you were doing this in C, I guess, but they don't interact as well with debuggers, and keeping on top of everything (\s everywhere, and the occasionally-surprising argument expansion rules) can get a bit much.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-33022969601383634712010-10-19T00:24:32.907-07:002010-10-19T00:24:32.907-07:00I don't really buy the claim that this arises ...I don't really buy the claim that this arises "naturally" (i.e. "automatically") from using some kind of type-based dispatch mechanism.<br /><br />It certainly <i>works well</i> if you happen to use a design with GetRadiusInDirection. But I'm highly doubtful you (or at least the average developer) would ever have defined GetRadiusInDirection as part of the API unless you already knew it was an important thing to have for fast implementation of separating planes or plane-sidedness testing.<br /><br />Again, I'm not denying it maps cleanly, and that that is cool. Just the seeming implication that OO saves you having to figure out what the fast method is in the first. Maybe I'm misinterpreting what you wrote, though.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-57859621809373744982010-10-18T12:03:45.865-07:002010-10-18T12:03:45.865-07:00Good point. Of course this type of PlaneSide test...Good point. Of course this type of PlaneSide test is just a separating axis test (the only axis for a plane is its normal).<br /><br />BTW I didn't see either of your mention the old Quake-style AABB-Plane test. In some cases it can be faster.<br /><br />You store your AABB as min and max in an array : m_ends[2]<br /><br />For the Planes you precompute whether to check min or max for each component (from the sign of plane normal), stored as ix,iy,iz (0 or 1).<br /><br />Then the test is :<br /><br />d = plane.w + plane.x * m_ends[ plane.ix ].x + plane.y * m_ends[ plane.iy ].y + plane.z * m_ends[ plane.iz ].z<br /><br />I believe this is equivalent as your Method 5 of precomputing the sign flip mask.<br /><br />The details of whether its faster or slower will depend on your platform, whether a dependent load hurts or whether mixing int & float math hurts.<br /><br />Similar technique of precomputing an index for a test is used in voxel raytracing, etc.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-6936222865518882022010-10-18T11:49:06.801-07:002010-10-18T11:49:06.801-07:00Addendum to the addendum: You want GetRadiusInDire...Addendum to the addendum: You want GetRadiusInDirection anyway (together with a "GetCenterInDirection", which reduces to GetCenter for most symmetric objects) since that's the primitives you need to determine the support of a convex object along an arbitrary axis - an essential ingredient to both Separating Axis Tests for overlap detection and the GJK algorithm for more accurate collision detection.<br /><br />There's still some details you need to handle yourself (e.g. figure out which axes to test for separation), but other than that, you get very nice and uniform code out of this.ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.com