On Thu, 13 Nov 2008, Benjamin Kirk wrote: >> Clearly you ought to be working on a BoundingConvexHull class. The >> standard algorithm for polygons is on page 898 of >> Cormen/Leiserson/Rivest; I'm sure you won't have any problem extending >> it to polyhedra and writing an intersection test. > > Not sure about that,
I may have been a *bit* sarcastic there. I don't think polyhedral hulls are easy even in the well-defined problem, much less when we'd want to communicate a decimated superset hull instead. > I'd say 'clearly I should get the nemesis part finished' and then > implement what you describe. No rush; we should see how the bounding boxes alone scale. > Right now we can get a bounding box for two processors easily > enough, and (I am sure you are gonna love this...) overload '&&' to > return true if they intersect. If you must use operator overloading, at least use '&' instead? Bitwise AND resembles an intersection operation more than logical AND does. > Going forward, Qhull (http://www.qhull.org/) looks like it will fit the bill > for building the convex hull, and then we just need to write an intersection > test... We could go so far as to derive the BoundingBox and > BoundingConvexHull from the same base class, so that you can use either to > perform the test. Wow. Is it too late to pretend that my joking BoundingConvexHull suggestion was serious? Maybe it should have been. The trouble is that we'd need to use a decimated superset of the hull. The goal is to reduce communication, and the hull of a smoothly curved convex surface requires nearly as many points to describe as the surface itself. A tilted "slab" of hexes can have a hull described by 8 vertices. Curve it a bit and now the hull has 80,000 vertices... but there's still a small "superset slab" that can be described with 8. Hard problem finding it, though. > In any case, since communicating a bounding box should be cheaper than a > hull, I'd expect we still might want to use it first to limit the number of > hulls we receive and test for intersection. Definitely. > (looking toward the full ranger problem...) Hmm... for the full ranger problem, I don't like the idea of having to do all-to-all communication even of bounding boxes, except when there's been a real topology change (such as loading a new mesh, or Derek's contact problems). For adaptivity we ought to be able to leave 90% of neighbor links intact, just doing local updates around each refinement/coarsening. --- Roy ------------------------------------------------------------------------- This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100&url=/ _______________________________________________ Libmesh-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/libmesh-devel
