3D Theory - Collision Detection

By: Richard - redeyes2003
file Methods of Collision Detection  
2004-07-13 14:42

I am interested somewhat in collision detection, or finding a suitable way of implementing it in a simulation. Does any know of any methods? What is it? What are good links on the topic?
I would like to know about any methods, such as bounding boxes, you name it, and the accompaning code.

This is one example of a method that I used before.

Create a few Ray Segments in the main object. Detect when the raysegments of the object penetrate polygons in the background object. Thus I use a ray segment test algorithm. This is not ideal. The background object is divided spacially; this is pre-calculated. Only the sub-division that encapsulates the main object is used in the ray-segment test. This method is pretty much old. And I would like other ideas.


This is the code for the ray-segment test. (I upgraded it recently. Previously it used precals of the polygons. I tested it in 2-d but not in 3-d as yet. If is does not work, I will revert to the precals method. Note it is not finisehed)


/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////

/*
R is the hit point, A,B,C are the vertices of the triangle, N is the normal to the triangle
e is a factor in which the triangle's boundaries are extended, its default was 0.005f. e can be ommitted if you do not
mind gaps between polygons occurs amlost never.
*/

bool IsPointInTriangle_IsPointInTriangle2dMethod( const float * R, const float * A, const float * B, const float * C, const float * N, float e /*= 0.005f*/ )
{
//Method is untested, but does not use division


//use the two smallest dimension of the normal
int dim1 = 0;
int dim2 = 1;

if((N[0]*N[0]) > (N[2]*N[2]))//I was lazy to implement if(fabs(N[0]) > fabs(N[2]) using the 'and' operator and 'sign mask' in fabs
dim1 = 2;
if((N[1]*N[1]) > (N[2]*N[2]))
dim2 = 2;


//uv for AC line in 2d
float A_C0 = (A[dim1] - C[dim1]);
float A_C1 = (C[dim2] - A[dim2]);


float ue = 1.0f+e;
//Error is calculated into it
float AR0 = (ue)*A[dim2]-R[dim2]-(e)*B[dim2];
float AR1 = (ue)*A[dim1]-R[dim1]-(e)*B[dim1];

float BR0 = (ue)*B[dim2]-R[dim2]-(e)*C[dim2];
float BR1 = (ue)*B[dim1]-R[dim1]-(e)*C[dim1];

//max line to AC
float F_BR_AC = (BR0)*(A_C0) + (BR1)*(A_C1);

//min line to AC with the relative distance from A point used
float F_AR_AC = (AR0)*(A_C0) + (AR1)*(A_C1);

//just getting the sign
if(F_BR_AC > 0.0)
{

//sideAC in
if(F_AR_AC < 0.0)
{

float B_A0 = (B[dim1] - A[dim1]);
float B_A1 = (A[dim2] - B[dim2]);

float F_BR_BA = (BR0)*(B_A0) + (BR1)*(B_A1);

//sideBA in
if(F_BR_BA < 0.0)//&&(F_CR_BA > 0.0) I think I have this here for a greater rejection test but it is not needed at this point
{
float C_B0 = (C[dim1] - B[dim1]);
float C_B1 = (B[dim2] - C[dim2]);

float CR0 = (ue)*C[dim2]-R[dim2]-(e)*A[dim2];
float CR1 = (ue)*C[dim1]-R[dim1]-(e)*A[dim1];

float F_CR_CB = (CR0)*(C_B0) + (CR1)*(C_B1);

//sideCB in
if(F_CR_CB < 0.0)
{
return true;
}
else
return false;
}
else
return false;
}
else
return false;

}
else//if(NEG)
{

//sideAC in
if(F_AR_AC > 0.0)
{

float B_A0 = (B[dim1] - A[dim1]);
float B_A1 = (A[dim2] - B[dim2]);

float F_BR_BA = (BR0)*(B_A0) + (BR1)*(B_A1);

//sideBA in
if(F_BR_BA > 0.0)
{
float C_B0 = (C[dim1] - B[dim1]);
float C_B1 = (B[dim2] - C[dim2]);

float CR0 = (ue)*C[dim2]-R[dim2]-(e)*A[dim2];
float CR1 = (ue)*C[dim1]-R[dim1]-(e)*A[dim1];

float F_CR_CB = (CR0)*(C_B0) + (CR1)*(C_B1);

//sideCB in
if(F_CR_CB > 0.0)
{
return true;
}
else
return false;
}
else
return false;
}
else
return false;

}

return false;

}


bool IsPointInTriangle_IsPointInTriangle3dMethod( const float * R, const float * A, const float * B, const float * C, const float * N, float e /*= 0.005f*/ )
{
//Method is untested, but does not use division



float A_C0 = (A[1] - C[1]) + (C[2] - A[2]);
float A_C1 = (A[2] - C[2]) + (C[0] - A[0]);
float A_C2 = (A[0] - C[0]) + (C[1] - A[1]);



float ue = 1.0f+e;
//Error is calculated into it
float AR0 = (ue)*A[0]-R[0]-(e)*B[0];
float AR1 = (ue)*A[1]-R[1]-(e)*B[1];
float AR2 = (ue)*A[2]-R[2]-(e)*B[2];

float BR0 = (ue)*B[0]-R[0]-(e)*C[0];
float BR1 = (ue)*B[1]-R[1]-(e)*C[1];
float BR2 = (ue)*B[2]-R[2]-(e)*C[2];


//max line to AC
float F_BR_AC = (BR0)*(A_C0) + (BR1)*(A_C1) + (BR2)*(A_C2);


//min line to AC with the relative distance from A point used
float F_AR_AC = (AR0)*(A_C0) + (AR1)*(A_C1) + (AR2)*(A_C2);


//if(POS)
if(F_BR_AC > 0.0)//BA>0 or BR>0
{

//sideAC in
if(F_AR_AC < 0.0)
{

float B_A0 = (B[1] - A[1]) + (A[2] - B[2]);
float B_A1 = (B[2] - A[2]) + (A[0] - B[0]);
float B_A2 = (B[0] - A[0]) + (A[1] - B[1]);

float F_BR_BA = (BR0)*(B_A0) + (BR1)*(B_A1) + (BR2)*(B_A2);

//sideBA in
if(F_BR_BA < 0.0)//&&(F_CR_BA > 0.0)
{
float C_B0 = (C[1] - B[1]) + (B[2] - C[2]);
float C_B1 = (C[2] - B[2]) + (B[0] - C[0]);
float C_B2 = (C[0] - B[0]) + (B[1] - C[1]);

float CR0 = (ue)*C[0]-R[0]-(e)*A[0];
float CR1 = (ue)*C[1]-R[1]-(e)*A[1];
float CR2 = (ue)*C[2]-R[2]-(e)*A[2];

float F_CR_CB = (CR0)*(C_B0) + (CR1)*(C_B1) + (CR2)*(C_B2);

//sideCB in
if(F_CR_CB < 0.0)
{
return true;
}
else
return false;
}
else
return false;
}
else
return false;

}
else//if(NEG)
{

//sideAC in
if(F_AR_AC > 0.0)
{

float B_A0 = (B[1] - A[1]) + (A[2] - B[2]);
float B_A1 = (B[2] - A[2]) + (A[0] - B[0]);
float B_A2 = (B[0] - A[0]) + (A[1] - B[1]);

float F_BR_BA = (BR0)*(B_A0) + (BR1)*(B_A1) + (BR2)*(B_A2);

//sideBA in
if(F_BR_BA > 0.0)
{
float C_B0 = (C[1] - B[1]) + (B[2] - C[2]);
float C_B1 = (C[2] - B[2]) + (B[0] - C[0]);
float C_B2 = (C[0] - B[0]) + (B[1] - C[1]);

float CR0 = (ue)*C[0]-R[0]-(e)*A[0];
float CR1 = (ue)*C[1]-R[1]-(e)*A[1];
float CR2 = (ue)*C[2]-R[2]-(e)*A[2];

float F_CR_CB = (CR0)*(C_B0) + (CR1)*(C_B1) + (CR2)*(C_B2);

//sideCB in
if(F_CR_CB > 0.0)
{
return true;
}
else
return false;
}
else
return false;
}
else
return false;

}

return false;

}


/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////

By: Martin Baker - martinbaker
file RE: Methods of Collision Detection  
2004-07-15 08:10

It seems to me that the method used would depend on the type of program.

If the physics simulation is being used to generate an animation, then each frame might be generated from the last frame, so collision could be detected by bounding box or bounding sphere or geometry intersection. Perhaps using bounding box/sphere to get a list of possible collision candidates, then do more CPU intensive geometry intersection test on these only.

If we are doing a simulation without dividing up into time segments, then I guess it would be more efficient to project a ray in the direction of motion and find where it intersects with stationary objects, or rays from other moving objects?

One issue that I am interested in is: If we are representing objects in a scene graph with multiple level transforms, how can we do collision detection without flattening the scenegraph into global coordinates at each frame?

Martin

By: Richard - redeyes2003
file RE: Methods of Collision Detection  
2004-07-16 02:58

Thanks for the good ideas Martin.

Any collision detection algorithm, I believe logically, must have two basic things. One is calculating the positions of the object and background, and the other is comparing them. I guess when two objects positions are not in the same reference frame, it would be suitable to calculate their global positions. Still there could be more efficient ways, I hope somebody have a suggestion.

I think bounding boxes are great to reduce cpu work and increase efficiency. Its more than 10 times faster than doing ray intercept with objects with only 4 polygons, because you have to transform the polygons with the cpu. So I definitely will find a means of using it.

 

metadata block
see also:

 

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Collision Detection in Interactive 3D Environments by Gino van den Bergen.

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to this site, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.

 

cover Dark Basic Professional Edition - It is better to get this professional edition

cover This is a version of basic designed for building games, for example to rotate a cube you might do the following:
make object cube 1,100
for x=1 to 360
rotate object 1,x,x,0
next x

cover Game Programming with Darkbasic - book for above software

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.