# 3D Theory - Collision Detection

 By: Richard - redeyes2003 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 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 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.

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.

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.

 Dark Basic Professional Edition - It is better to get this professional edition 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 Game Programming with Darkbasic - book for above software

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