I have things in my game where units are shaped irregularly -- however, they will always have a width and a length.
This got me to thinking as to how to represent the unit's bounding box for collision detection.
My first assumption was to have a rectangle, but then for things like helicopters, you can swat them in the tail rotor even though you actually completely missed.
I opted instead of an ellipse.
If I recall, the formula for an ellipse is
(x-squared over a) plus (y-squared over b) equals (distance from point A to point B)
where x,y are the coordinates of points on the ellipse, a is the length, b is the width, point A is one of the centre points and point B is the other.
My question is this... how do you find the centre points?
ID:154177
 Apr 24 2002, 5:48 am
|
|
I believe you're thinking of the foci, but I don't think the equation there is right. The usual ellipse equation is this: Yep, that's what I was referring to (the focii, that is). I did remember that I had seriously messed up what I meant to say and said it as (distance from point A to point B). What I should have said was (distance to x,y such that the distance from point A plus the distance from point B equals this amount). But that's just unwieldy. =P Of course that's when the major axis is horizontal, Yep. The origin is at (0,0), and it is always represented horizontally. If the ellipse had a width of 2 and a length of 4, then the endpoints of the narrowest and widest points would be (0,1), (0,-1), (2,0), (-2,0). but the equation can apply to either. a is the distance from the farthest point to the center, and b is from the closest point to the center. c is the distance from a focus to the center; the foci are lined up on the major (longest) axis, in the direction of a. c is calculated such that c2=a2-b2. Ah, that was the perfect explanation I needed. If we just set a to always go with x, we'd get these equations: Well, mainly I want it to satisfy an equality -- if, along the line between object 1 and object 2, the point at the end of object 1's ellipse's radius (if you can call it that) passes through object 2's ellipse's radius, then the two items have collided. Basically it takes circular bounding boxes and changes them to ellipses. Should I just stick to circular ones and save myself a headache? I wouldn't need to work out any rotation stuff either. =P | |
It would be a headache, even without the rotations.
[Edit] I just realized that what I said below will tell you if the ellipses intersect in certain situations but there will be many exceptions where it will be inconclusive. You can read it if you want to but something else would need to be added to make it complete enough to use for collision detection [/Edit] One approach would be to center one of the ellipses at the origin then displace the other like this: (x - xo)^2/(a1)^2 + (y-yo)^2/(b1)^2 = 1 xo = initial x displacement yo = initial y displacement (x/a2)^2 + (y/b2)^2 = 1 Then calculate the line that passes through both centers: y = mx + b b = 0 because it passes through origin (center of one ellipse) m = yo/xo Then find the intersection of that line with each ellipse by the substitution method. You'd probably have to throw in some matrices or the quadratic equation to have the computer solve it and choose which points are the correct ones by checking how close they are to the other ellipse. (Each ellipse should give you two intersections). Then add the distances between the points of intersection on each ellipse and if that total is greater than or equal to the distance between the centers of the ellipses then they are intersecting at at least one point. That is English's Proof of Intersecting Ellipses. (Copyright 2002) Actually, I'm sure it has been done before but I thought of it on my own :p (If there is a hole in the strategy then please point it out ;) ) This would be one CPU hog... | |
I believe you're thinking of the foci, but I don't think the equation there is right. The usual ellipse equation is this:
(x/a)2+(y/b)2=1
Of course that's when the major axis is horizontal, but the equation can apply to either. a is the distance from the farthest point to the center, and b is from the closest point to the center. c is the distance from a focus to the center; the foci are lined up on the major (longest) axis, in the direction of a. c is calculated such that c2=a2-b2.
If we just set a to always go with x, we'd get these equations:
a=(width-1)/2 (assuming odd numbers here)
b=(height-1)/2
c=sqrt(abs(a*a-b*b))
c isn't too useful for detecting collisions, though. It's mainly used for another definition of the ellipse: That the ellipse is the set of points such that the sum of the distances from that point to each of the foci is equal to a fixed mount. That is,
sqrt((x-cx1)2+(y-cy1)2) + sqrt((x-cx2)2+(y-cy2)2) = 2a
sqrt((cx1-cx2)2+(cy1-cy2)2) = 2c
b = sqrt(a2-c2)
When two ellipses touch, there will be at least one point that satisfies both ellipse equations. That's a mess I won't even get into right now.
Lummox JR