Sign in to follow this  
solinent

Cylinder-triangle collision detection

Recommended Posts

I'm looking for a fast method to determine where and when a car's wheel is intersecting with a scene (the road). I am hoping to find a method that's pretty fast. I have experience with kd-trees in raytracers, but I can't figure out or find any reference that relates using spatial partition schemes with oriented cylinders. Realistically, I'm trying to simulate a car, and I need to figure out the normal force that the wheels are exerting on the body. When a wheel collides with, lets say a curb, then realistically the car should luch upwards. This should be calculated via torques applied to the car's body. However, to find the upwards force and torque applied, I need to know the normal of the point of intersection of the wheel. Also, if someone could point me to physics describing such a collision? I understand the normal force changes, but there should also be a force in the opposite direction, assuming the curb is perfectly rigid and in place. So the car should experience a force equal to its weight in the direction of the normal at the point of intersection, right? But what if this force isn't enough to generate a torque? Obviously the wheel cannot pass through the curb, so what happens? Or is it always enough? I have to take into account momentum, right? So, in short I need: - Fast method of finding the intersection and normal of a cylinder and a scene (consisting of triangles) (this should be under 1ms for all tyres, hopefully). - Understanding the reaction physics, currently I only have a gr 11 understanding + an understanding of some things regarding torques found in the internet. I don't mind researching this kinds of stuff.

Share this post


Link to post
Share on other sites
First of all, in the realm of physics, X-versus-triangle intersection tests are not particularly useful. Far more useful are intersection tests between two solids, which can give you useful information about restitution vectors and points of deepest intersection and suchlike. One generally models one's world in solids, at least as far as physics is concerned.

You have to ask yourself whether you are interested in making a physics simulation or making a racing game. The former requires a great deal of physics and mathematics knowledge. The latter is best served with an off-the-shelf physics engine such as Newton or PhysX or Tokamak or Bullet.

Share this post


Link to post
Share on other sites
My aim is actually to become a physics simulation, and not a car game :).

Being a fun game is a side note, but I'd love to have accurate physics.

I understand that triangle-cylinder collisions will be expensive, but even in arcade games, you see the wheel being accurately portrayed. How do they detect the wheel's collision with the ground?

I could trace 8 rays per wheel, which would definitely take less than 1 ms on a recent cpu, but this would certainly miss the point.

Of course, before I even check for collisions, I'll do a fast test with an axis-aligned BBox, and then only do more expensive tests for triangles that have a point within the bounding box. I still need to know the normal of the point of intersection in order to generate any forces. Maybe I should look into PhysX to see how one is expected to do this?

(As a side note: A main reason for me doing this is just for the heck of it. So if a great deal of knowledge is required, then my goal is to learn it. It would hardly be a learning experience if I used an engine.)

Share this post


Link to post
Share on other sites
The mathematical algorithm for (bounded)cylinder-triangle intersection has a lot of cases based on the position/orientation of the triangle relative to the cylinder. The cost of such a query is excessive, so you do not want to do this.

Consider generating a rectangular grid for the domain of the terrain triangles. As a preprocessing step, for each grid cell determine those triangles whose projection overlap the cell. The goal is to have a small number of triangles per grid cell. It is fast to determine which grid cell the bottom-most point of a tire is over. Then cast a ray and test for intersection with the small number of triangles covering that cell.

Share this post


Link to post
Share on other sites
Theres a problem with only tracing one ray, and that is the fact that the wheel can intersect at multiple points at the same time, (a pothole is a good example of this).

I need to know the exact time of intersection in order to calculate the force.

However, tracing one single ray in my engine is trivial when used with a kd-tree, so I can trace a 400x400 grid of rays (so 160 000x2 rays with phong shading and shadow testing) in less than 32 ms, so tracing maybe 16 rays per wheel with a static scene shouldn't be a problem. Should I do it this way? I am designing this game to be effect-heavy, so it is likely a newer CPU would be involved (I'm not realy making this game for anyone but myself).

[Edited by - solinent on November 9, 2008 1:27:15 PM]

Share this post


Link to post
Share on other sites
how about just using spheres. You can ignore collisions that are outside a given area of the sphere (near-ish the contact patch).

EDIT: ha, you want just the physics of it.

In that case, your best bet would be the GJK algorythm.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this