Hi guys, at the moment I'm coding a 3d racing game. For collisions between the ship and the ground (represented as triangles not other polygons) I fire a ray from the bottom of the ship and see which polygon it intersects, calculate the rotation and rotate the ship over 6 frames to provide a smooth rotation. Now the problem arises when moving over two triangles with a large angle between them, as the ship can move through a polygon if going at fast speeds. I've been looking into swept collisions but they're only useful for volumes (like spheres and aabbs) so was wondering if anybody has any ideas on how to "swept" the ray triangle test? I was thinking of doing further tests at increments between the ships 2 positions, by creating a line between the 2 points and firing the ray down at say quarters along the line, but this would only reduce the problem not eliminate it completely. I could fire another ray from the front of the ship, but that would double the collision detection so I'm looking for a way which doesn't do that. Anybody got any ideas?

This sounds like a WipeOut clone?

So I guess you cast a ray down to the ground, primarilly to adjust the hover height of your racer. Not to do collisions (since these guys never touch the ground thus don't actually collide with it).

So really, what you're doing now is a separate issue from the passing thru polygon issue (Walls collision).


for wall collisions (as well as floor polys) you'll want to draw a line segment from the past and future locations of the racer and see if it intersects anything... Once that part gets resolved, *then* do the check of the ray down to the floor and adjust hover height.



So Yes, you really should be doing additional collision checks; and I really wouldnt worry about increasing(doubleing?) cost, because... this stuff is cheap.
You did remember to use space partitioning to speed up collision checks, right?

Yep, I thought I'd program a WipeOut/F-Zero clone as my first project :) At the moment I'm hovering the ship over the ground but at a fixed height, so I don't adjust height or anything (but I'll put this in soon). I guess you're right, I should use additional tests, its the only way. I'm using an octree system, so I'll optimise it a bit more for more calculations. Cheers :)

You mean use a sphere for testing against polygons?

Just one quick question: I've made an octree system so what I intend to do is, for both the future and present locations of the ship, traverse the octree to find which polygons to test the line between both points against. However, it's occured to me that the line may cut through a third box before the future position ends up in its box. So without testing the line against each node (i.e. wihtout having to perform a line-aabb test each frame per ship) what you would suggest?

Quote:Original post by Rajveer
However, it's occured to me that the line may cut through a third box before the future position ends up in its box. So without testing the line against each node (i.e. wihtout having to perform a line-aabb test each frame per ship) what you would suggest?

This is one reason why I don't like tree based partitioning schemes; correlating node connectivity to spatial connectivity is not very direct.

I suppose what you could do is, find the smallest branch of the tree that contains both the past and destination locations. then check all nodes within that as potential 'passed through'.
Since typically we use a 16ms physics update, the distance travelled will be small and most position changes remain within a single node
(with the pass thru 3rd box situation being incredibly rare).


Or toss the whole octree.
This is a racetrack right?? so its essentially linear. Just make your track into segments that go in order. Much easier to figure out which ones you passed through.

Solving the problem with ray-triangle tests on terrain amounts to using spatial locality (and avoiding having an image-based table look-up). Keep track of the current triangle you are over. On the next query, check the current triangle. Chances are you are still over it, so you have an O(1) intersection test. If not over the current triangle, do a breadth-first search or a BSP-based search to find the nearby triangle that you are over. If you have an index array to define the triangles, it is easy to construct an adjacency array to support the search.