Capsule/Axis-aligned bounding box intersection
Omair-Inam Abdul-Matin
I'm looking for an algorithm that can compute the intersection between a
capsule and an axis aligned bounding box (AABB). On the
magic-software.com website there is an algorithm for computing the
intersection between a sphere and an AABB so even if someone knows where
I could find an algorithm for cylinder/AABB intersection that would be
sufficient as well.
Any ideas?
Omair
Dave Eberly
news:cb7str$hvd$1...@rumours.uwaterloo.ca...
It is not clear from your post what type of intersection
you are looking for. My distinctions are:
1. both objects stationary
a. test if they are intersecting
b. find the set of intersection
2. one object moving, one object stationary for some time
interval 0 <= t <= tmax.
a. test if they are initially intersecting (case 1.a.)
b. find the set of intersection initially, if any (case 1.b.)
c. test if they intersect at some time in [0,tmax]
d. find the first time of contact T, if any
e. find the contact set at time T
3. two objects moving - reduce to case 2 by subtracting
velocity of one object from the other.
For 1.a., you can compute the distance from the capsule
segment to the box and compare to the capsule radius.
(Code at my site on the Distance page.)
Case 1.b. is complicated. The set of intersection can be
very complex.
Case 1.d.,e. If your reference to sphere-AABB intersection is
really my code for moving sphere versus oriented bounding
box, notice that the code for that is quite complicated.
Extending that to moving capsules is a challenge.
Alternatively, you can set up the problem as a root finder
for F(t) = D(t) - r where D(t) is the distance between the
capsule segment and the box and r is the capsule radius.
Knowing F(0) > 0, you can attempt to compute the first
root of F(t) = 0 for t in [0,tmax]. Perhaps a hybrid
bisection-Newton's method will do. At first time of
contact, the distance code at my site produces the closest
points on the objects. When distance is zero, these will
be the same point, your first point of contact.
Case 1.c. The capsule segment sweeps a certain region
over [0,tmax]. Assuming you have constant linear
velocity, it can be a line segment (velocity is in the
direction of the segment) or a parallelepiped. In the
former case, you compute the distance from the line
segment to the box and compare to the radius. In the
latter case, you compute the distance from the parallelepiped
to the box and compare to the radius.
--
Dave Eberly
http://www.magic-software.com
Omair-Inam Abdul-Matin
My case was 1 a.
Omair
Omair-Inam Abdul-Matin
Does the restriction that the box is axis-aligned lead to a distance
algorithm that might be simpler than the one for calculating the
distance between a line segment and an oriented. I'm just wondering
whether there exists a more efficient AABB-lineseg distance computing
algorithm than the WmlDistLin3Box3.h
Omair
Dave Eberly
> Does the restriction that the box is axis-aligned lead to a distance
> algorithm that might be simpler than the one for calculating the
> distance between a line segment and an oriented. I'm just wondering
> whether there exists a more efficient AABB-lineseg distance computing
> algorithm than the WmlDistLin3Box3.h
If you want to use an AABB, you can simplify
the code a little bit, but I doubt if you will see a
significant speed up. The first blocks of code in
the SqrDistance functions transform the line segment
into the coordinate space of the OBB. An OBB *is*
an AABB in its own coordinate space, so the remaining
code blocks are computing the distance between a line
segment and an AABB.