Jump to content
  • Advertisement
Sign in to follow this  
smek2

collision between two ellipsoids

This topic is 4850 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I have written a basic 2D engine, based on Direct3D. I have a texture manager who's managing and loading any sized picture and creates a D3D texture with the next power of 2 automatically. My render system uses batching and index buffers, my sprites are textured quads who i scale, rotate and color and all that stuff. But when it comes to serious math, i downright suck. My excuse is that i'm out of school for quiet some time and that this is my very first game. Anyways, my problem is collision detection. In the beginning (of my game) there was none. Then there was simple "Overlap" check between two rectangles. Then i realized that for sprites whose graphic is round (a ball for example), the simple rectangle overlap check wont work with precision. So i decided to use bounding spheres for my sprites. I managed to check whether two spheres (radii from the sprites width) collide or not. But then i realized that some sprites have a considerable differecne between height and width. So i thought about ellipsoids. And before i even tried to understand all that math i found here and via google, i recalled that i scale and rotate my sprites too. I considered crying a bit, but started this topic instead. *sniff* Can anybody give me some hints about how to check for ellipsoid collision detection, consider rotation degree and scale factor? Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
A sphere is merely a special case of ellipsoid, where all three projections (xyz) happen to be exactly same. You can mathematically model an ellipsoid by using an unit sphere as the base, and scaling it by a 3-vector before doing calculations with it.

You could also transform the sphere using full matrices instead of simple 3-vectors - this way, you can easily model scaling, shearing, rotation and movement of your ellipsoids.

With the transformation handled, the collision detection can be done between unit spheres.

Share this post


Link to post
Share on other sites
It would be ellipses rather than ellipsoids in 2d. (I mention it just so you can search for the correct terms.)

Without getting into the whole ellipse/ellipsoid intersection thing, let me just suggest the possibility of using oriented bounding boxes instead - they're quite a bit easier to work with.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nik02
With the transformation handled, the collision detection can be done between unit spheres.


No you can't - trouble is that when you apply the transformation to turn one ellipsoid into a sphere, it turns the other ellipsoid into just another ellipsoid.

Three options:

1. Work out the transformation needed to turn ellipsoid 1 into a unit sphere. Apply this transformation to the second ellipsoid to generate a new ellipsoid. Calculate the distance (not trivial) between the sphere centre and the ellipsoid surface. If it's less than 1 there's an intersection.

2. Don't use spheres - use capsules (sphere swept along a segment). Then capsule-capsule intersection checks turn into simple segment-segment distance calculations.

3. Allow each object to be represented by more than one sphere - then collision between two objects just involves sphere-sphere distance checks (which turn into point-point distance calculations).

I suggest the second.

But hang on... at the start of your post you talk about 2D stuff, but then you ask about spheres and ellipsoids (3D objects). Are you sure you don't mean circles and ellipses (2D)? Anyway, my answer is much the same - just convert sphere->circle, ellipsoid->ellipse and capsule->swept circle.

Share this post


Link to post
Share on other sites
Thanks for the replies.
Yes, i mean ellipses and circles.
But from what i understood, the math behind that is very simillar, if not the same, right?
Even though i'm in danger to sound like a baby now, but what i want to do is to take it easy for my first game and produce a decent 2D side-scrolling shooter.
I choose Direct3D because in doing so, i learn the basics 3D (like vertex buffers, special effects, textures etc.), which should it make more easy to get "fully 3D" later. What i basically want is to calculate an ellipse for each sprite (based on its width and height, maybe with an offset) and then check if that ellipse is colliding with another one. All this consider there's a scale and rotation factor for each sprite (i do not use matrices, when drawing a quad i apply the sprites x and y position to the vertices (multiply with scale factor) and calculate the rotation using the sprites rotation degree. Right now i'm reading a paper about tangent planes of ellipsoids and unit sphere collision. Pretty heavy stuff, it requires a good knowledge of linear algebra. I wonder, do you really need to be a math wiz to make a simple game like a shooter? There must be an easier way, right?
I already thought about simple rectangle checking again, but theres still the issue with rotation.
PS: I mentioned a working sphere collision test. My mistake. It's really a "circle" collision test and it works very simple by calculationg the distance bewteen two given objects and then checking the radius of each object. No such thing as vectors to specify the exact point on the circle, were the collision took place. Did i mention that i suck in math?

Share this post


Link to post
Share on other sites
Quote:
I already thought about simple rectangle checking again, but theres still the issue with rotation.
To clarify, my suggestion was to use oriented bounding boxes. This takes orientation into account, and generally provides for a better fit than axis-aligned bounding boxes.
Quote:
Yes, i mean ellipses and circles.
But from what i understood, the math behind that is very simillar, if not the same, right?
The math is similar in the sense that a circle is a special case of an ellipse, but again, ellipses are much harder to work with than circles (for most purposes).
Quote:
but what i want to do is to take it easy for my first game and produce a decent 2D side-scrolling shooter.
You should of course do whatever interests you and seems like the best solution for your needs. But if your goal is really to 'take it easy' and successfully make a first game, my advice would be to avoid ellipses for now. Circles and OBBs are much easier, and I would think they'd be perfectly adequate for a 2d shooter.

Just my $.02.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!