Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / Game Design & Programming / collision detection theory Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
LabRat404

December 08, 2004, 09:42 AM

I read on this site about a collsion detection method where you determine if a vertice crosses a plane, and (if it does cross) if you create a temporary plane for each edge of the face that the plane belongs to, and calculate the vertex of the intersection and test it using classifyPoint(), if the point is within the region, classify_point will return PLANE_BACK, or something to that effect.

well, I thought it made sense to just check if the vertex you are checking for is behind all the faces that already exist for the 3d poly, instead of checking each infdividual face.

this works in theory, as far as I can tell, but it doesnt quite work in code. I'm not sure if all my planes' normals are facing outward, if I just have an error in my code, or if my theory is incorrect...

(and by the way, how do I do a source box for my code on this forum?)

code example:


// move from *position to *destination
void moveIfNoCollision(Vertex3 *position, Vertex3 *destination)
{
extern WORLD world;

uint g, t, count;
bool legal;

for (g=0; g < world.cntBrushes; g++) /* for each 3d shape */
{
count = 0;

for (t=0; t < world.brush[g].cntFaces; t++) /* for each face of the shape */
if (classifyPoint(&world.poly[g].face[t], destination) == PLANE_BACK) /* if the point is behind this face's plane */
count++;
else
break; /* obviously, the destination is not inside this poly */

if (count == t) /* the point is behind every face's plane in the shape, which means that its inside! */
return;
}

/** the function would have returned by now if there was a collision **/
*position = *destination;

return;
}

 
nGoon

December 08, 2004, 11:56 AM

Umm maybe I misunderstood your approach but it seems to be flawed.
For example take a landscape, if you place a vertex in the highest place under the landscape (under a mountain for example) the vertex most definitely is on the "correct" side of polygons which are lower than the vertex itself...
Another example; Lets say you have a torus object, you cannot find a place in the whole world where you could put the vertex so that it would be in the "back" side of all faces.

- nG

 
LabRat404

December 08, 2004, 12:10 PM

well my method almost works, but it gets caught in open space 50% of the time.


what my method attempts to do is this:

if a start point and a destination point are on different sides of any Face's plane, then determine whether or not the destination point lies within the 3D polygon that the face belongs to. if it doesn't, make the move. but that is to say that all normals of each plane are pointed outward from the 3D polygon.


I guess I'm basically skipping trying to figure out whether or not a point is on the Face, because that would require use of an Epsilon to modify an intersection point, while using classifyPoint does not. it seems more efficient.

everyone uses the word 'polygon' to describe a two dimensional shape. I'm not sure what to call the actual 3D thing other than a 3D polygon, or a brush, or what.

 
LabRat404

December 08, 2004, 12:33 PM

alright. this method seems to work now except for that it doesnt work on any brushes within brushes...I cant walk thru walls, but if I had a box in a room, I can walk thru the box all I want but not be able to leave the room unless there is a door...

I think there is one more step I need to make in order for this to work perfectly. its surounded by backets below:

if a start point and a destination point are on different sides of any Face's plane, then determine whether or not the intersection point [ plus an vector of length 'epsilon' which points in the direction of the movement ] lies within the 3D polygon that the face belongs to. if it doesn't, make the move. but that is to say that all normals of each plane are pointed outward from the 3D polygon.

I need to add a vector of length 'epsilon' to the point of intersection just to make sure that the point is going to be completely inside the bounds of the 3D polygon. after that, and working out the bug mentioned at the top of this post, it should work. but is this too much computation? I'm not sure if this method is fast enough...

 
timm

December 08, 2004, 01:43 PM

polyhedron?

 
This thread contains 5 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.