Re: [eigen] Bounding Volume Hierarchies

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

Hi,

wow, the patch seems to be very complete.

Actually, I think a BVH is a bit too far to Eigen's objectives, and at
a first glance I don't think it should be included in Eigen.
Otherwise, by extension, we'll soon add a physics engine, a raytracer,
etc. I think we have to find a limit.

On the other hand, I have the project to write a spatial data
structure library based on Eigen, and so your contribution would
perfectly fit :) Since it is not started and yet and I don't have much
time for that, I'm currently ok to commit your patch in Eigen's tree
because:
1 - the module is in unsupported so no big deal, we can still see
later whether it is worth creating a separate project or not,
2 - the contribution looks good, and so it's worth it making it
available to most people right away,
3 - I know one KDE application which needs a BVH: Step.

Regarding the changes in AxisAlignedBox, I'm not very fan of using
operator & and | for the intersection and union, and I would suggest
explicit names.

....
<have to go, no time to finish the email, I'll come back with more
comments later>
....

gael.

On Thu, Mar 5, 2009 at 1:01 AM, Ilya Baran <baran37@xxxxxxxxx> wrote:
> Hi,
>
> Since Eigen has a Geometry module, I think it would be useful to have
> a bounding volume hierarchy (BVH) module, since they are so useful in
> accelerating tons of different kinds of geometric computations.  I'm
> attaching a patch (to unsupported) that provides what I think is a
> pretty generic approach (criticism is, of course, welcomed)--it
> decouples traversal algorithms from both the query and the hierarchy.
> It also provides a simple BVH implementation based on AlignedBox.  The
> documentation in the patch describes the features in detail, but as
> this is my first experience with CMake and doxygen, I may have gotten
> some paths/settings wrong.  In particular, I can't seem to get the
> module documentation to display properly (at one point it did, but now
> on even on a fresh checkout without my patch it doesn't).  I'm also
> not sure how well I followed Eigen's coding conventions.
>
> To get this working, the patch also fixes a memory alignment bug in
> AlignedBox (no pun intended :) and adds union and intersection
> operators to it as well as a couple of other things.  However, the
> current AlignedBox design is slightly flawed: the intersection of two
> disjoint boxes may be empty, but unioning it with another box can
> change the box--checking for emptiness has to be done somewhere.  I
> think the best way is to check at construction/modification time
> whether the box is empty and call setNull, if so.  That has drawbacks,
> though, such as making the non-const min() and max() either impossible
> or requiring wrapper trickery.
>
> Thanks,
>
>   -Ilya
>