arbitrary bounding box intersection
Stefan Gottschalk
3d rectangles, anyway) arbitrarily positioned and oriented in
3-space, and I want to know if they touch or intersect. I don't
need to know WHERE they touch, but only WHETHER they touch.
Does anyone know an efficient way to do this?
Currently I test whether any of the edges of box A intersects any
of the faces of box B and vice versa, for a total of 144 edge-face
intersection tests. Yuck. I want to do better.
-stefan
Justin Johnson
gott...@cs.unc.edu "Stefan Gottschalk" writes:
Umm. I've not actually done this yet, but I've thought a bit about it so here
goes.
First, get the minimum x,y,z and maximum x,y,z's for the two rectangles.
You can then do a very quick general rejection test.
If the rectangles come through this, then check each vertex of rect B to be
on the inside of rect A's planes. If a vertex is on the outside for any plane,
then move directly to the next vertex. If the vertex is on the inside of all
rect A's planes then there is a collision.
I *think* this might be faster for you.
Regards,
--------------------------------------------------------------------------------
Justin Johnson
E-Mail: jus...@jjavp.demon.co.uk
BOOM! BABY ... Not bad for a Humanoid.
================================================================================
Mikki Larcombe
Given two convex polyhedra these are separable (i.e. have no point in
common) if there is some axis such that the points from each polygon project
onto this axis in two separable sets. This is equivalent to the notion of a
plane of separation but has the advantage of giving a direct measure for
comparison purposes: given the two convex polyhedra A and B and letting
these project onto some axis as p(A),p(B) then separability exists if
max p(a)<min p(B) or max p(B)<min p(A).
This leaves us to choose the appropriate directions. There is a finite set of
such directions for polyhedra: the facet normals from both polyhedra and the
directions formed from the vector cross-products of an edge direction taken from
each polyhedra. For the rectangular boxes this gives 15 directions, but
the tests are rejective... it is sufficient to find separability in one of these
directions, intersection requires overlap of the projected sets in all of these
directions.
In making these tests it is useful to have the formula for the extent of a
rectangular box in any direction to hand (extent is the range of the projected
points. Given a mid-point m, orthonormal
basis vectors b0,b1,b2, and semi-axis s0,s1,s2 the extent in a direction d
relative to a test point q is:
d.(m-q)+/-(s0|d.b0|+s1|d.b1|+s2|d.b2|)
where |d.b0| means the absolute value of the dot product.
--
Mikki Larcombe
--
Mikki Larcombe