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