Does anybody know how to do collision detection using rotated 2d or 3d rectangles? It is bugging the **** out of me!! Please, if you how, drop me a line! (zlaj@hotmail.com) Also, if you know how to do poly/poly or line/poly collision detection, also help me out, please!!

Hi,

since you did not tell us something about the environment you
want to use the collision detection for, it''s pretty hard to
give you a tip with optimal performance behaviour.

What you could do for example, is to calculate bounding boxes around your rectangles to get a first impression of possible
collisions. The next thing you do is to use is mathematical line intersections for the potential candidates.


If the playfield you are using is not too big you could also use a buffer to draw your boxes into, but instead of colour information you write handles to your objects into this map.
Whenever you will write such a handle you can then look if there is already a valid handle of another object already in this cell.

In most cases the best thing to use is a DIVIDE AND CONQUER approach which minimizes the amount of data to compare from step to step.



cu

Peter




cu

Peter

The enviroment I''m working in is an overhead 3d game, sorta like Grand Theft Auto. All vehicles have a box for collision bounding, but when I turn the vehicle I don''t want to be stuck with the absolute outmost bounds, for obvious reasons. So, I have rotated rectangles.

Yes, your post helped a bit, but I need the maths/methods on HOW to test whether the points/edges of one rectangle are inside the other, when both are rotated to some obscure angle.

Any more suggestions? Or followups?

Have you considered using a few bounding circles instead to APPROXIMATE the shape of the bounding rectangle you were planning on using? Afterall, 1 'big' circle with 4 'small' circles at the corners can come pretty close to approximating a square.

With some creative placement you should be able approximate a rectangle pretty closely.

Just a thought.

C=64



Edited by - C=64 on July 27, 2000 3:03:53 AM

Hi,

for the math stuff i would say you should read the
"Foley, Van Damme" book about graphics programming.
I will look for the exact title and post it as soon
as i can.
This book is at last a very good source for understanding
3D and 3D programming.

cu

Peter

C=64, that does help a bit, and will be used for collision with gun turrets, but do you want to make 12+ circles to approximate the shape of an 18-wheeler trailer? By your method, the square root function which is used to calculate distance would be well taxed, and I could probably lose a good 6, 8 fps just to collision detection. A very good idea, but impractical for the way I''m using it.

Phemmer, that would surely help a lot. If I can afford it. Right now I''ve got a back-pocket allowance for programming stuff... But I will check it out.

Remember, in almost all cases, it''s just as simple to use the squared distance as it is the square root of the distance for bounding sphere calculations.

In your case, instead of storing the radius, consider storing the radius SQUARED. Then, when you do distance tests for intersections, there should be no need to actually generate the square root; All your comparisons will be vs squared components, so a squared distance is completely kosher.

But, as I said before, it''s just a thought...

C=64

True... It might require more memory to store (Squared means MUCH Larger numbers, Mainly because of the size of the objects I have in mind, measured in meters). But still, using spheres to approximate the shape of a large building? It doesn''t work that well.

And I still do need help on other forms of collision detection... But keep this in mind, please. Rotated rectangles by preference, polygon/polygon collision if possible, line/polygon collision if possible.

Wyrframe: A float is a float no matter how large the number it holds is. I wouldn''t be too wary of memory. Computers now a days have so much that you could go buck wild allocating megabytes here and megabytes there with plenty left over (except on my computer ). Also, you can represent meters as 1 = 1 meter, or .1 = 1 meter, or even .00001 = 1 meter.

-e

Perhaps a float is a float, and yes I know what a floating-point number is.

However, I am doing this in Visual Basic 6. I can use a Long Integer (4 bytes) or a Double Floating-point (8 bytes). And it''s not RAM memory I''m worried about, it''s disk space and processing speed. A LONG variable can usually be processed about 7 times as fast as a DOUBLE.

Still, that was worth mentioning, thanks. It will help, letting everybody else know what language I''m working in...