Re: [Algorithms] N-body processing

[Dave E. <eb...@ma...>]

From: "Pierre Terdiman" <p.t...@wa...>

> Dave,
> Welcome. Stefan actually tried that approach, but later. Well, whatever.
> Could you explain what would be the benefit of lozenges ? Especially a
> lozenge-tree ?!

A lozenge looks like an OBB that is 'rounded' at the
edges and corners.  You effectively have the same
degrees of freedom to provide a good fit of an
object by an OBB or lozenge.  So now the problem
is to decide whether an OBB-OBB or lozenge-lozenge
test is cheaper.  For static OBBs, you have up to
15 separating axes to test.  You can compute an
average time for the test based on empirical
probabilities about which axes tend to yield the
separation (for randomly generated OBBs, the
face axes covered about 95% of the cases when
boxes did not intersect).  For static lozenges, you
need to determine the time it takes to compute
the distance between two rectangles in 3D.  I
believe this distance test wins.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com