Date: Tue, 7 Feb 95 14:02:38 CST
From: rusin (Dave Rusin)
To: derrico@pixel.kodak.com, baier@forwiss.uni-passau.de
Subject: Re: collision detection
Newsgroups: sci.math
>baier@forwiss.uni-passau.de writes:
>>Given a set of truncated cones with elliptic base and top I would like to
>>detect collisions between different solids.
>>Now imagine dozens of such cones randomly distributed in space and
>>your task is it to detect impossible states i.e those where some cones
>>intersect.
derrico@pixel.kodak.com writes:
>Not too hard. Assume that each cone is defined by its four
>vertices.
There lies the rub: what are the four vertices of a cone? You must be
thinking of its cross-section.
The rest of the article is still fine, that is, you can easily limit
the candidates for intersection to a few (unless, as noted, the cones
are pencil-like). You'll just have to work harder to figure out when
they intersect.
I guess the question hinges on the representation of the cones. I suppose
for each cone you need to store the length of its central axis, the
major and minor axes on the bottom, and the ratio of lengths in the
top and bottom ellipses. Then, if the cone is to be set randomly in space,
you need to keep track of the position of its center of mass (or any
other predesignated point), the direction of its central axis away from
the center of mass, and the rotation of cone about this axis (relative to
some standard inclination like having the major axis of the bottom ellipse
lying the the plane of the central axis and the z-axis (boy, it's harder
just to say what needs to be fixed than to visualize it) ). So it looks
to me like the specification of such a shape in space requires 10 parameters
(for comparison, those cross-sections in the plane require knowing 6).
If you track each cone this way, then at least one way you can solve
the intersection problem goes like this: given one such cone and another
which you wish to investigate for intersection,
(1) translate both so the C-o-M of the first is at the origin
(2) rotate the picture so the central axis of the 1st is the +z-axis
(3) rotate around the z-axis so the axes of the bottom ellipse
lie on the x- and y- axes
In these coordinates, a point lies on the first cone iff 0<=z<=z0 and
(x/a)^2+(y/b)^2<= (1-mz)^2 [the numbers z0, a, b, and m describe the
first cone]. I guess in your shoes I'd go over the whole 2nd cone
looking to minimize (x/a)^2+(y/b)^2-(1-mz)^2 subject to the constraints
0<=z<=z0. This minimum is <=0 if and only if the cones intersect.
Fortunately, the idea of "minimize ... subject to the constraints..."
is precisely what Lagrange multipliers solve. Or of course you
could go over the whole 2nd cone and check to see whether the
above inequality is satisfied for any (x, y, a) in it.
(Oh, and in order to "go over the whole second cone", you'll need to
parameterize it in some way. It consists of the points (x,y,z)
where each of x, y, and z is a simple function of three parameters
lying in a box in R^3. For example, the prototypical cone list above
may be found by first parameterizing the edge of the bottom ellipse:
(a cos(theta), b sin(theta), 0) with 0< theta<2pi); then parameterizing
the interior of that ellipse:
(a r cos(theta), b r sin(theta), 0) with 0< theta<2pi and 0 < r < 1;
then parameterizing the whole cone:
(a (1-mt) r cos(theta), b (1-mt) r sin(theta), t ) with 0