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;
}
/////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////// |
Methods of Collision Detection