[Algorithms] Capsule-OBB separating axes

[Andy Sloane]

Hello,

For various reasons, I would like a quick capsule-oriented box test.
Intuitively, this is equivalent to a line segment-oriented box separating
axis test, except the line segment is 'inflated' by the radius when it is
projected onto any axis.

The obvious choices are the axes of the box itself, the axis of the line
segment, and the cross product of the latter with the former three, so
seven in all. Is that it? Is that too many?

More generally, one thing I'm having trouble with is that I'm not really
sure how to select an axis to represent a near-collision between the vertex
of the line segment and a vertex of the box.

The segment-box test on magic-software
(http://www.magic-software.com/Source/Intersection/WmlIntrLin3Box3.cpp)
utterly confounds me after the first three axes are tested. The cross
product of the difference between centers and the axis of the line segment
is taken, but I don't understand what's going on with the three tests after
that; I can't wrap my head around the geometry.

-Andy

[Per Vognsen]

Hey Andy,

I haven't studied Dave's code but here's an idea, which may or may not
be identical to what he is doing.

Let the capsule be defined by a line segment AB and a radius R.

The problem reduces to testing the line segment AB against the
convolution of the oriented box with a sphere of radius R. This
convolution can be represented as the union of these geometric
primitives:

The original oriented box.
Capsules for each edge of the original box, with radius R.
Oriented boxes for each face, with height R.

Make a few diagrams to see why this works. Anyway, given this
decomposition, testing the line segment against the convolution is the
same as testing the line segment against each of the components. Each of
these individual tests can be done using the separating axis method. You
should be able to work out the resulting separating axes, expressed
directly in terms of the data defining the original oriented box. This
way you don't actually construct the components explicitly and you
should end up with a "pure" separating axis method.

Hope this helps,
Per

-----Original Message-----
Behalf Of Andy Sloane
Sent: Thursday, April 15, 2004 1:21 PM
Subject: [Algorithms] Capsule-OBB separating axes
Hello,
For various reasons, I would like a quick capsule-oriented box test.
Intuitively, this is equivalent to a line segment-oriented
box separating axis test, except the line segment is
'inflated' by the radius when it is projected onto any axis.
The obvious choices are the axes of the box itself, the axis
of the line segment, and the cross product of the latter with
the former three, so seven in all. Is that it? Is that too many?
More generally, one thing I'm having trouble with is that I'm
not really sure how to select an axis to represent a
near-collision between the vertex of the line segment and a
vertex of the box.
The segment-box test on magic-software
(http://www.magic-software.com/Source/Intersection/WmlIntrLin3
Box3.cpp)
utterly confounds me after the first three axes are tested.
The cross product of the difference between centers and the
axis of the line segment is taken, but I don't understand
what's going on with the three tests after that; I can't wrap
my head around the geometry.
-Andy
-------------------------------------------------------
This SF.Net email is sponsored by: IBM Linux Tutorials Free
Linux tutorial presented by Daniel Robbins, President and CEO
of GenToo technologies. Learn everything from fundamentals to
system
administration.http://ads.osdn.com/?ad_id=1470&alloc_id=3638&op=click
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188

[Andy Sloane]

Thanks for the reply.

Post by Per Vognsen
The problem reduces to testing the line segment AB against the
convolution of the oriented box with a sphere of radius R. This
convolution can be represented as the union of these geometric
The original oriented box.
Capsules for each edge of the original box, with radius R.
Oriented boxes for each face, with height R.

Well, sure, but, stepping back a bit, what are the necessary separating
axes for the line segment and the original box?

My intuition is that these are the same as what are needed for the capsule
and the box, because the capsule is simply an extrusion of the line
segment. Or equivalently, as you suggest, an extrusion of the box could be
tested against the line segment. ("extrusion" not technically being the
right term here, but you know what I mean)

-Andy

[Andy Sloane]

Of course, now that I've correctly defined the actual problem I want to
solve, I can just look on the internet and find this:
http://www.gamasutra.com/features/19991018/Gomez_6.htm

Doh! So the three box axes, and the cross product of the line segment and
the three box axes, as I thought, and I don't need the line segment
direction itself.

-Andy

[Per Vognsen]

-----Original Message-----
Behalf Of Andy Sloane
Sent: Thursday, April 15, 2004 2:35 PM
Subject: Re: [Algorithms] Capsule-OBB separating axes
Thanks for the reply.

Post by Per Vognsen
The problem reduces to testing the line segment AB against the
convolution of the oriented box with a sphere of radius R. This
convolution can be represented as the union of these geometric
The original oriented box.
Capsules for each edge of the original box, with radius R.
Oriented boxes for each face, with height R.

Well, sure, but, stepping back a bit, what are the necessary
separating axes for the line segment and the original box?

You listed them already in your original post. They are the face normals
as well as cross products of the line vector with each of the edge
vectors.

My intuition is that these are the same as what are needed
for the capsule and the box, because the capsule is simply an
extrusion of the line segment. Or equivalently, as you
suggest, an extrusion of the box could be tested against the
line segment. ("extrusion" not technically being the right
term here, but you know what I mean)

Not quite. Unfortunately this doesn't even work for testing a sphere
(the degenerate case of a capsule) against a box. Consider the
two-dimensional case, for the sake of simplicity.

|
1 | 2
|
_____ _ _ _ _
| |
| |
|_____| 3


This is (supposed to look like) a rectangle and the three labelled
regions defined by its top and right side. Imagine a circle centered
somewhere in region 2 such that it reaches into both regions 1 and 3 yet
doesn't intersect the box. The separating axis test (using the two axes
from regions 1 and 3, respectively) will fail in this case. We also need
to check the separating axis joining the upper-right vertex to the
center of the sphere. This is necessary if and only if the center falls
in region 2 and we can quickly decide whether this is the case by
transforming to a basis in which the box is axis-aligned. The
three-dimensional case is only slightly more complicated. There you will
also need to use a special kind of separating axis when the closest
feature of the sphere center is an edge. In this case the separating
axis is the perpendicular dropped from the sphere center down onto the
edge. Again, you can decide when this kind of axis is to be considered
by working in the axis-aligned frame of the box and comparing the point
to the defining box intervals.

So I guess the short answer would be: No, this box-capsule problem is
not at all equivalent to testing a line segment against an oriented box.

Exercise: Generalize the above enumeration of separating axes for the
box-sphere case to the more general box-capsule case. :)

Per

[Andy Sloane]

Post by Per Vognsen
Not quite. Unfortunately this doesn't even work for testing a sphere
(the degenerate case of a capsule) against a box. Consider the
two-dimensional case, for the sake of simplicity.

Duh! Thank you, I was being naive.

Post by Per Vognsen
Exercise: Generalize the above enumeration of separating axes for the
box-sphere case to the more general box-capsule case. :)

Hmm.. So the separating axes for the degenerate case (sphere) would be:
3 - three box axes
8 - (each vertex of box) - (sphere center)
12 - perpendicular to each edge toward sphere center

except you'd only really need to consider the nearest vertex or the
nearest edge, depending on the location of the sphere. Hmm.

Ugh! Ok, so in general we have:
3 - the three box axes
3 - (three box axes) x (line segment axis)
16 - (each vertex of the line segment) - (each vertex of box)
24 - perpendicular to each edge toward each vertex of the line segment

That's awful! "Pure" separating axis is probably not what I want here, eh?

So, what about this:

We use a quick box-sphere intersection test, by transforming the endpoints
of the linesegment defining the capsule into box space and using, for
instance, "A Simple Method for Box-Sphere Intersection Testing" by Jim Avro
(Graphics Gems).

Then, once we've determined that the spheres defining the ends of the
capsule are not intersecting, the only remaining feature is the 'extrusion'
of the line segment, and then we only need to check the 6 line segment
axes... or am I missing something yet again?

-Andy

[Per Vognsen]

-----Original Message-----
Behalf Of Andy Sloane
Sent: Thursday, April 15, 2004 4:48 PM
Subject: Re: [Algorithms] Capsule-OBB separating axes

Post by Per Vognsen
Not quite. Unfortunately this doesn't even work for testing

a sphere

Post by Per Vognsen
(the degenerate case of a capsule) against a box. Consider the
two-dimensional case, for the sake of simplicity.

Duh! Thank you, I was being naive.

I think most people make this mistake initially (myself included). Don't
sweat it!

Post by Per Vognsen
Exercise: Generalize the above enumeration of separating

axes for the

Post by Per Vognsen
box-sphere case to the more general box-capsule case. :)

Hmm.. So the separating axes for the degenerate case (sphere)
3 - three box axes
8 - (each vertex of box) - (sphere center)
12 - perpendicular to each edge toward sphere center

Right. A somewhat orthogonal observation: When writing
production-quality code for this separating axis method, it makes sense
to first check the vertex axes, then the edge axes and finally the face
edges for early-out purposes. If you visualize the regions corresponding
to the different kinds of features, that should make a lot of sense: The
closest-feature region corresponding to a vertex is cone-like and keeps
growing in all three directions as you move away. The region for an edge
is wedge-shaped and only grows in two dimensions while the slab-like
region for a face only grows in one dimension. Thus, when at a
reasonable distance to the box (compared to its size), you are more
likely to fall in a vertex region than, say, a face region.

except you'd only really need to consider the nearest vertex
or the nearest edge, depending on the location of the sphere. Hmm.
3 - the three box axes
3 - (three box axes) x (line segment axis)
16 - (each vertex of the line segment) - (each vertex of box)
24 - perpendicular to each edge toward each vertex of the
line segment
That's awful! "Pure" separating axis is probably not what I
want here, eh?
We use a quick box-sphere intersection test, by transforming
the endpoints of the linesegment defining the capsule into
box space and using, for instance, "A Simple Method for
Box-Sphere Intersection Testing" by Jim Avro (Graphics Gems).

For what it's worth, I like to think of Arvo's algorithm as an optimized
separating axis method. The difference between it and a more generic
method is that he only checks separating axes corresponding to vertices
and faces when necessary (i.e. when the sphere center falls into the
appropriate regions) and he also uses this "region classification" to
add up face distances in order to get edge and vertex distances. Pretty
clever, reusing the distances like that!

Then, once we've determined that the spheres defining the
ends of the capsule are not intersecting, the only remaining
feature is the 'extrusion'
of the line segment, and then we only need to check the 6
line segment axes... or am I missing something yet again?

No, sounds good to me but of course I've been known to make mistakes.
Anyway, I hope it at least comforts you to know that Arvo's algorithm is
really the separating axis method in disguise :)

Per

[Gino van den Bergen]

A "pure" separating axis approach is not applicable here, since you can
not restrict the potential separating axes to the face orientations and
cross products of edge directions, as with polytopes.

You solve this problem by computing the (squared) distance of the line
segment and the box. (If the distance is greater than the capsules
radius, the objects do not intersect.) The witness points of the
distance, i.e. the closest points, construct a separating axis (or
conincide in case of an intersection).

You can use GJK for computing the distance between a line segment and a
box (my favorite hammer). However, in this case an explicit
"construction" of the Minkowski sum of the line segment and the box
might be faster (although I'd doubt it). Simply, construct all the
supporting planes (a x + b y + c z + d = 0, normal n = (a, b, c)^T
pointing outward) of faces of the Minkowski sum. These are

(a) Faces of the box offset by Max(dot(n, p), dot(n, q)) where p and q
are endpoints of the line segment. 6 in total.

(b) Cross products of the direction (p - q) and the box's principle axes
offset by the vertices. Also 6 in total.

See a pattern? These correspond with the potential separating axes in
the separating axes method. Each axis results in two parallel planes.

Next, find the closest point to the origin of the rhombic dodecahedron
formed by these 12 planes. Planes for which the origin lies on the
negative side (plane offset d is negative) are immediately discarded.

So, now are left with at most 6 planes. Select the furthest plane (the
plane for which d is the largest, if we normalized all normals). Compute
the closest point on this plane and check whether it lies inside all
other halfspaces. If it does, then this is your closest point. If not,
then compute the line of intersection of the furthest plane and the
violating plane, and compute the closest point on this line. Perform the
same check for the remaining (at most 4) faces, and compute the point of
intersection of the line and the violating plane if one exists.

There you have it. The closest point is your separating axis, and its
distance to the origin is the distance between the line segment and the
box.
As said, I would not put my money on this routine being faster than GJK
for the general case, but at least it can be parallelized a little
easier.


Gino van den Bergen
www.dtecta.com



-----Original Message-----
From: Andy Sloane [mailto:***@guildsoftware.com]
Sent: Thursday, April 15, 2004 22:48
To: gdalgorithms-***@lists.sourceforge.net
Subject: Re: [Algorithms] Capsule-OBB separating axes

Post by Per Vognsen
Not quite. Unfortunately this doesn't even work for testing a sphere
(the degenerate case of a capsule) against a box. Consider the
two-dimensional case, for the sake of simplicity.

Duh! Thank you, I was being naive.

Post by Per Vognsen
Exercise: Generalize the above enumeration of separating axes for the
box-sphere case to the more general box-capsule case. :)

Hmm.. So the separating axes for the degenerate case (sphere) would be:
3 - three box axes
8 - (each vertex of box) - (sphere center)
12 - perpendicular to each edge toward sphere center

except you'd only really need to consider the nearest vertex or the
nearest edge, depending on the location of the sphere. Hmm.

Ugh! Ok, so in general we have:
3 - the three box axes
3 - (three box axes) x (line segment axis)
16 - (each vertex of the line segment) - (each vertex of box)
24 - perpendicular to each edge toward each vertex of the line segment

That's awful! "Pure" separating axis is probably not what I want here,
eh?

So, what about this:

We use a quick box-sphere intersection test, by transforming the
endpoints
of the linesegment defining the capsule into box space and using, for
instance, "A Simple Method for Box-Sphere Intersection Testing" by Jim
Avro
(Graphics Gems).

Then, once we've determined that the spheres defining the ends of the
capsule are not intersecting, the only remaining feature is the
'extrusion'
of the line segment, and then we only need to check the 6 line segment
axes... or am I missing something yet again?

-Andy



-------------------------------------------------------
This SF.Net email is sponsored by: IBM Linux Tutorials
Free Linux tutorial presented by Daniel Robbins, President and CEO of
GenToo technologies. Learn everything from fundamentals to system
administration.http://ads.osdn.com/?ad_id=1470&alloc_id=3638&op=click
_______________________________________________
GDAlgorithms-list mailing list
GDAlgorithms-***@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=6188

[Alen Ladavac]

Actually, it is not that hard to do a proper separating axis test. The axes
are:

1) 3 cross products of box axes with capsule main axis direction (to test
edges to capsule cylinder),
2) 8 directions of lines perpendicular to capsule main axis, passing through
each of the box vertices (to test vertices to capsule cylinder, actually
catches the faces agains capsule cylinder as a side effect),
3) 2 "Arvo's axes", one for each capsule sphere (this catches capsule caps
against anything on the cube).

What I like to call "Arvo's axis" is what you get from the Arvo's algorithm
if you track actual direction vector instead of distance. Note that you
cannot just do Arvo's algo for both spheres because you cannot get any
useful result from that for the entire capsule (at least I didn't find any),
so you need to find the axis resulting from it and then do a usual
separating axis test.

Whether this classifies as a "pure" separating axis approach or not, I don't
know. But I'm sure it does the work, and with a reasonable number of axes.
;)

HTH,
Alen

[Andy Sloane]

Post by Alen Ladavac
1) 3 cross products of box axes with capsule main axis direction (to test
edges to capsule cylinder),
2) 8 directions of lines perpendicular to capsule main axis, passing through
each of the box vertices (to test vertices to capsule cylinder, actually
catches the faces agains capsule cylinder as a side effect),
3) 2 "Arvo's axes", one for each capsule sphere (this catches capsule caps
against anything on the cube).

I finally got around to implementing this, and it works like a charm!
Thank you very much!

-Andy

[Alen Ladavac]

No probs. FYI, several other of similar SA-based tests are integrated into
ODE by Nguyen Binh at the moment. You might want to check the ODE mailing
list (www.q12.org).

Alen

----- Original Message -----
From: "Andy Sloane" <***@guildsoftware.com>
To: <gdalgorithms-***@lists.sourceforge.net>
Sent: Friday, April 23, 2004 03:15
Subject: Re: [Algorithms] Capsule-OBB separating axes

Post by Andy Sloane

Post by Alen Ladavac
1) 3 cross products of box axes with capsule main axis direction (to test
edges to capsule cylinder),
2) 8 directions of lines perpendicular to capsule main axis, passing through
each of the box vertices (to test vertices to capsule cylinder, actually
catches the faces agains capsule cylinder as a side effect),
3) 2 "Arvo's axes", one for each capsule sphere (this catches capsule caps
against anything on the cube).

I finally got around to implementing this, and it works like a charm!
Thank you very much!
-Andy
-------------------------------------------------------
This SF.net email is sponsored by: The Robotic Monkeys at ThinkGeek
For a limited time only, get FREE Ground shipping on all orders of $35
or more. Hurry up and shop folks, this offer expires April 30th!
http://www.thinkgeek.com/freeshipping/?cpg=12297
_______________________________________________
GDAlgorithms-list mailing list
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
http://sourceforge.net/mailarchive/forum.php?forum_id=6188