On Thu, Nov 13, 2008 at 11:49 AM, Benjamin Kirk <benjamin.kirk@nasa.gov> wrote:
>>> There is actually a commented-out section of code in MeshCommunication that
>>> used to do this using bounding spheres, but I think for my meshes with
>>> boundary-layers that would just have an annoying amount of false positives.
>> What about boundary layers that aren't aligned with a coordinate axis?
>> Won't that have nearly the same problem?
> Yeah, nearly the same problem...
>> 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'd say 'clearly I should get the nemesis part
> finished' and then implement what you describe.  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.
> 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.

I'm not sure about Qhull.  I don't think it's had any releases since 2003.  This in itself isn't bad, but from http://www.qhull.org/html/qh-in.htm#library, I see:

Warning: Qhull was not designed for calling from other programs. There is neither API nor Qhull classes. It can be done, but it takes work and head scratching. You will need to understand the data structures and read the code. Most users will find it easier to call Qhull as an external command.