After looking at the methods of finding collision between an ellipsoid and a plane, I found that most algorithms were actually wrong! By wrong, I mean that the methods implement do not check for ellipsoid-plane collision at all! I know that accuracy is often sacrificed for speed, but in this case, the speed of calculation the same if not faster when being calculated in a 100% accurate manner. The problem I noticed with each and every ellipsoid-plane collision detection example that I''ve seen (that includes all of the ones in the articles and resources here including that master''s thesis, which IMHO... well... stunk *sorry*), is that they check collision by determining if the distance between the plane and the center of the ellipsoid is less than that of the radius following the normal to the plane. At first glance, most people think nothing of it, but this is not accurate at all! In fact, when using this method, you aren''t really applying the actual shape of the ellipsoid for bounding collision detection. The reason that this isn''t accurate is because the point that lies between the plane and the center of the ellipsoid is ( in almost every circumstance, unless it is a spere or if it lies along a semi-axis ) not the closest point on the ellipsoid to the plane! In fact, the more the ellipsoid is "stretched" the more inaccurate this is, and actually, it can be off by an unbelievably large amount depending on the case. In actuality, I realized that both the closest and the furthest point on the ellipsoid are those which have tangiential planes that lay parallel to the plane of which you are checking collision. The way I implement collision detection for ellipsoids(actually I use a spheroid for reasons I will go into later) is I just check to see if the "d" of the plane of intersection lies between the "d''s" of the furthest and closest parallel planes (with a, b and c, all the same of course). If this is true, then the plane is currently colliding. After searching, I could find no formulas for ellipsoid-plane intersection following my concept, so I derived a formula which does the computations in exactly 1 line based around planar derivatives on 3D Surfaces solving for when the tangiential plane is parallel to the plane of intersection. The formula is fully modular taking parameters for translations, and differing semi-axis ellipsoid values. The domain includes all values that would possibly make up an ellipsoid and plane and is fully accurate in every circumstance. I''ll write up the entire derivation (which is a lot longer than I expected when first approaching the problem, I might add) and submit it along with an example of it''s use in an article as soon as I get a chance. Until then, I''d like to hear your opinions, or if you know of anyone who has already done this. I haven''t seen any documentation about it, so I think it''s unique. Also, does anyone know of how I would be able to brand my name on the formula? If I''m the first person to derive it (which I suspect I am not, though I haven''t found evidence oterwise), where should I send it? I mailed the full derivation to myself yesterday as recommended by my calculus teacher, but is there a way I could register it at the USCO or something? Thanks in advance! -------------------- Matthew Calabrese Realtime 3D Orchestra: Programmer, Composer, and 3D Artist/Animator "I can see the music..."

You cannot really ''brand'' your name on a formula... the only way that happens is after publication of the result in a peer reviewed journal and thorough acceptance of the work as original. Even then, it''s unlikely that it will ever be known as The Calabrese Algorithm or something similar, but probably just the Spheroid-Plane Collision Algorithm .

As to whether it''s been done before... well, yes, the mathematics is not original. You get the same mathematics when you derive the solution for ellipsoid sections of an ellipsoid. It is possible though that the application to collision detection is original (although I highly doubt it). I highly recommend a detailed literature search before attempting to publish the results as original. You could certainly write an article for GameDev.net expounding on your idea. That will certainly bring the experts out of their boxes and they''ll quickly tell you whether it''s been done before or not!

Cheers,

Timkin

Anyone know of any good freeware/shareware applications for the purpose of displaying algebraic functions and operations? I rewrote out my entire derivation on paper and it takes up a few pages. It''d look pretty nasty with the lines just typed because of the fractions, "plus or minus," and all of the powers/roots. If I send in an article, what would be the best way of formatting the math?

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

Latex.

If you don''t have access to a machine running this package, then just use Microsoft Word''s equation editor. Ugly and klunky, but it gets the job done.

Timkin

Thanks!

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

What's the difference between an ellipsoid & a spheroid?

I'm willing to bet that most derivations assume axis-aligned ellipsoids - so the more general case you handle is outside their domain. Also, you might want to extend your detection to include movement; and here-in lies the problem. You've opened-up a huge-can of mathematical whup-ass by allowing the ellipsoid to rotate while moving. This means you need to interpolate the position and orientation of the ellipsoid between rendering-frames, to back-calculate the point-in-time of a collision. e.g. a sphere moving through time swipes out a capsule, so to do correct cd of a moving sphere, you can just do static capsule cd, and if there's a collision you find the intersection-point, then can directly compute the time of intersection. The shape of an arbitrarily oriented ellipsoid, with both linear and angular velocities, swipes a non-trivial volume through space-time; this greatly complicates the problem.

Do you have "3D Game Engine Design" (Eberly)? He touches on this in 6.7 "Processing of rotating and moving objects".


[edited by - Magmai Kai Holmlor on April 1, 2002 10:19:44 PM]