Box Collision Detection ?!! | |

game_maker | Hi Today I tried to test Collisions for 3D Boundary Objects (and); First I tried to test for Sphere Collision Type and it seems to be working 100% [8)] Then I moved to another Type witch is (Box), here is the problem!! Rotation issue makes me nerves?!! I know that it can't be lots of calculation because I have been through this once, and that problem was about finding if the point inside a triangle, the solution was about 30 Lines (I used equation of Line ) ?!!! I think that we can solve this problem by vector calculation!! And my question is HOW?!! |

Eric Coleman | I think the easiest method would be to transform box "A" into the coordinate system of box "B," then you wouldn't have to worry about rotation. Then it becomes a regular box-box collision detection. |

game_maker | what do you mean by that ?!! do you mean changing the rotation ?! it will change the state hmmm I think I need a code this is the part for Computing Max & Min [code] Public Function AC_GetBoundingBox() As NoorT_Box Dim I As Long, VMax(2) As Single, VMin(2) As Single With AC_Prop(AC_Current) VMax(0) = .Object(0).X VMax(1) = .Object(0).Y VMax(2) = .Object(0).Z VMin(0) = .Object(0).X VMin(1) = .Object(0).Y VMin(2) = .Object(0).Z For I = 0 To .NumTris * 3 + 3 If VMax(0) < .Object(I).X Then VMax(0) = .Object(I).X If VMax(1) < .Object(I).Y Then VMax(1) = .Object(I).Y If VMax(2) < .Object(I).Z Then VMax(2) = .Object(I).Z If VMin(0) > .Object(I).X Then VMin(0) = .Object(I).X If VMin(1) > .Object(I).Y Then VMin(1) = .Object(I).Y If VMin(2) > .Object(I).Z Then VMin(2) = .Object(I).Z Next I End With With AC_Matrix(AC_Current) AC_GetBoundingBox.Max = Help.Set_V3B(VMax(0) + .m41, VMax(1) + .m42, VMax(2) + .m43) AC_GetBoundingBox.Min = Help.Set_V3B(VMin(0) + .m41, VMin(1) + .m42, VMin(2) + .m43) End With End Function [/code] |

Eric Coleman | I haven't had my coffee yet this morning when I posted that, so sorry for the confusion. Doing a box-box collision test isn't easy. You might want to consider spheres or cylinders. |

game_maker | bro it's must be done [:)] 3D Game usually based on Box-Box Collision Not Sphere - Sphere ... so I really need to slove this a problem OK to make our life easy we agnore Y-axis I Know this method : our box2 contains 2 triangles - without Y-axis find if any of the four point is laying inside of any of the 2 triangles for finding I know 2 methods : 1- if the sum of the three trinagles is equal to the full triangle 2- by equation of line ( y = mx + b) but all of these methods is A loooooooong solution ?!! so we need to solve it by another method [:)] |

SuperC | I havent coded what im about to recommend but i believe it should work and be easy. You can give a quad on the xz axis to two characters. Each quad would have 4-6 verts. If you want to see if they overlap then use the point in triangle formula to see if one of the 4 verts are in the opponents quad(2 polys) _____ |\ | | \ | | \| ------ quad Make sure when doing the test you perform vector transformation on the quads points to translate them to where the models are. 'This moves 1 polygon to where a model is o QuadVert(0)=new vector3(0,0,0) | \ Quadvert(1)=new vector3(10,0,0) | \ Quadvert(2)=new vector3(10,0,10) | \ o----o shift this poly from origin (0,0,0) to the models position NewPositionOfQuadVerts(0)=Vector3.transformcoordinate(QuadVert(0),models matrix). NewPositionOfQuadVerts(1)=Vector3.transformcoordinate(QuadVert(1),models matrix). NewPositionOfQuadVerts(2)=Vector3.transformcoordinate(QuadVert(2),models matrix). You dont want to do quadvert(0)=vector3.transformcoordinate (quadvert(0),matrix) because your shifting the verts from origin to the current model position. |

game_maker | SuperC : Why would I translate them, and what do mean by quad (Is it a non uniform rectangle in 3D Space?! OK it first we ignore Y-axis then it becomes a 2D problem... Then we need to find if any of the four points is laying in any of the 2 triangle The problem is How to perform a (FAST) test on every (point in triangle) I know 2 methods (as I said before witch is totally slow) So the question is how to perform a (Fast) test?! [:)] |

SuperC | when i say a quad its just another way to say a rectangle made up of 2 polygons with 4 or 6 vertices. 4 if its stripped, 6 if its a triangle list. o---o | / | | / | o---o 2---3 | / | | / | 1---4 lets say you set your values for the verts as 1=(-10,0,-10) 2=(-10,0,10) 3=(10,0,10 4=(10,0,-10) Now the center point of this box/quad would be (0,0,0) which is origin. You want origin to be your center point btw. You would have to translate this box so that (0,0,0) had the position of (player.x,0,player.z) so that the box was around your player so it could do collision detection properly. Whats good about this is that the boxes rotation of verts will match the players rotation around the Y axis because it uses the same matrix as the player. The point in triangle formula doesnt care how the polygons are are rotated around the Y axis. Just make sure they all have the same Y values. Since your only using x and z the triangles will be coplaner if the y of each vert is the same. If the y of each vert varried they could overlap on the xz plane but the point in triangle function could fail. To see if 2 boxes overlap with any rotation, just use 4 verts so that you only call the point in triangle function 8 times.(4 points have to be compared to one polygon/triangle. Since there are 2 polygons its 8 calls. Here is a link for Point in triangle http://www.blackpawn.com/texts/pointinpoly/default.html A way to speed this up is to use bounding spheres around the box verts and if the bounded spheres collide goto point in triangle/poly testing. Bounding sphere would be faster and save some cycles. Youll have to learn this someday if you want to do per poly collision detection between 2 meshes. They break up the meshes polygons and put spheres around the skeleton to reduce the point in polygon testing. The sphere allows it to focus on a certain area or set of polygons to test. |

game_maker | This is fairly working 1000% and easy and also very fast [:)] I have read all the word and letters in your post and the site and I have enjoyed a lot [:)], This is the code [code] '/// Part 1 - Computing Bounding Box Public Function AC_GetBoundingBox() As NoorT_Box Dim I As Long, VMax(2) As Single, VMin(2) As Single With AC_Prop(AC_Current) VMax(0) = .Object(0).X VMax(1) = .Object(0).Y VMax(2) = .Object(0).Z VMin(0) = .Object(0).X VMin(1) = .Object(0).Y VMin(2) = .Object(0).Z For I = 0 To .NumTris * 3 + 3 If VMax(0) < .Object(I).X Then VMax(0) = .Object(I).X If VMax(1) < .Object(I).Y Then VMax(1) = .Object(I).Y If VMax(2) < .Object(I).Z Then VMax(2) = .Object(I).Z If VMin(0) > .Object(I).X Then VMin(0) = .Object(I).X If VMin(1) > .Object(I).Y Then VMin(1) = .Object(I).Y If VMin(2) > .Object(I).Z Then VMin(2) = .Object(I).Z Next I End With With AC_Matrix(AC_Current) AC_GetBoundingBox.Max = Help.Set_V3B(VMax(0) + .m41, VMax(1) + .m42, VMax(2) + .m43) AC_GetBoundingBox.Min = Help.Set_V3B(VMin(0) + .m41, VMin(1) + .m42, VMin(2) + .m43) End With End Function '/// Part 2 - Math Libs : Public Function Vector_PointInTriangle(P As NoorT_Vector3D, A As NoorT_Vector3D, B As NoorT_Vector3D, C As NoorT_Vector3D) As Boolean If Vector_SameSide(P, A, B, C) And Vector_SameSide(P, B, A, C) And Vector_SameSide(P, C, A, B) Then Vector_PointInTriangle = True End Function Public Function Vector_SameSide(P1 As NoorT_Vector3D, P2 As NoorT_Vector3D, A As NoorT_Vector3D, B As NoorT_Vector3D) As Boolean Dim V1 As NoorT_Vector3D, V2 As NoorT_Vector3D V1 = Vector_CrossProduct(Vector_Make(A, B), Vector_Make(A, P1)) V2 = Vector_CrossProduct(Vector_Make(A, B), Vector_Make(A, P2)) If Vector_DotProduct(V1, V2) >= 0 Then Vector_SameSide = True End Function Public Function Vector_CrossProduct(V1 As NoorT_Vector3D, V2 As NoorT_Vector3D) As NoorT_Vector3D Vector_CrossProduct.X = V1.Y * V2.Z - V1.Z * V2.Y Vector_CrossProduct.Y = -(V1.X * V2.Z - V1.Z * V2.X) Vector_CrossProduct.Z = V1.X * V2.Y - V1.Y * V2.X End Function Public Function Vector_DotProduct(V1 As NoorT_Vector3D, V2 As NoorT_Vector3D) As Single Vector_DotProduct = V1.X * V2.X + V1.Y * V2.Y + V1.Z * V2.Z End Function Public Function Vector_Make(P1 As NoorT_Vector3D, P2 As NoorT_Vector3D) As NoorT_Vector3D Vector_Make.X = P2.X - P1.X Vector_Make.Y = P2.Y - P1.Y Vector_Make.Z = P2.Z - P1.Z End Function '/// Part 3 - Finding Box Collision : Public Function CollisionBox_Find(Box1 As NoorT_Box, Box2 As NoorT_Box, Speed As NoorT_Vector3D) As Boolean Dim P(3) As NoorT_Vector3D, T(3) As NoorT_Vector3D With Box1 P(0) = Set_V3B(.Max.X - Speed.X, 0, .Max.Z - Speed.Z) P(1) = Set_V3B(.Max.X - Speed.X, 0, .Min.Z - Speed.Z) P(2) = Set_V3B(.Min.X - Speed.X, 0, .Max.Z - Speed.Z) P(3) = Set_V3B(.Min.X - Speed.X, 0, .Min.Z - Speed.Z) End With With Box2 T(0) = Set_V3B(.Max.X, 0, .Max.Z) T(1) = Set_V3B(.Max.X, 0, .Min.Z) T(2) = Set_V3B(.Min.X, 0, .Max.Z) T(3) = Set_V3B(.Min.X, 0, .Min.Z) End With If Vector_PointInTriangle(P(0), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(1), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(2), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(3), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(0), T(1), T(2), T(3)) Or _ Vector_PointInTriangle(P(1), T(1), T(2), T(3)) Or _ Vector_PointInTriangle(P(2), T(1), T(2), T(3)) Or _ Vector_PointInTriangle(P(3), T(1), T(2), T(3)) Then CollisionBox_Find = True End Function [/code] Optimizations Part: I didn't until now optimized any thing but I will do the following: # First Find if there is Sphere Coll then Find if its Box (as you suggest) # Cross Product In XZ is A vector in Y or -Y so no need for X And Z part Ie Instead of [code] Public Function Vector_CrossProduct(V1 As NoorT_Vector3D, V2 As NoorT_Vector3D) As NoorT_Vector3D Vector_CrossProduct.X = V1.Y * V2.Z - V1.Z * V2.Y Vector_CrossProduct.Y = -(V1.X * V2.Z - V1.Z * V2.X) Vector_CrossProduct.Z = V1.X * V2.Y - V1.Y * V2.X End Function [/code] [code] Public Function Vector_CrossProduct(V1 As NoorT_Vector3D, V2 As NoorT_Vector3D) As NoorT_Vector3D Vector_CrossProduct.Y = -(V1.X * V2.Z - V1.Z * V2.X) End Function [/code] Also the minus sign Has No Effect in the last result because we want to know is it along or not in direction ... ie we can erase it Any way I was stick in the problem how to determine wither it should be above or down the line ,, so what I did is I took a particular solution and go for it (ie arraigning vertex order) to have my old particular solution .... And I found the point is above or down by method of line equation: y = mx + b At first I find m and b : m = (y2-y1) / (x2-x1) b = y - mx Then substitute the x-component of the point in this equation and compare the resultant y with the one in the point, by this I defined wither it's above or down, but still I need to determine if it should be above or down.... Method 2: is to separate the triangle to 3 triangle (from the point) and if the sum of the three small areas = the area of the original triangle then its inside (don't you think so); Method 3: today it came up to my mind! OK if you have a point P outside the triangles ABC Then There must be an angle > 180 between one of these vectors We can find the angle by: VectorA . VectorB = |A| * |B| Cos(Theta) ie Theta = arccos( (VectorA . VectorB) . (|A| * |B|) ) and we can get arccos in visual Basic By : [code] Public Function ACos(xCos As Double) As Double ACos = Atn(Sqr(1 / xCos ^ 2 - 1)) / (Atn(1) * 4 / 180) End Function Public Function ASin(xSin As Double) As Double ASin = Atn(Sqr(1 / (1 - xSin ^ 2) - 1)) / (Atn(1) * 4 / 180) End Function [/code] but the result won't be greater than 90 degree while it should be so I must to find if VecA.X = minus and VecB.X = ?? to determine the real angle ... Anyway you can see the pain I have been through these 3 days [:D] Thanks SuperC [;)] |

SuperC | No problem. I dont understand the last part with vecA.x = minus and vecB.x and you wanting an angle Other notes... You can also use the cross product to find an axis of rotation when you want to rotate one vector onto another. The sign of x or y or z of the vector returned from crossproduct will tell you which way to rotate. You may have to flip the signs i dont recall at the moment. You may know this but, the dx math functions use special instructions and they are faster than coding your own in vb. Its good you know the code though. Its also faster to do rotations on 1 axis using sin cos on the box verts since they wont pitch or roll just yaw. |

VBBR | Instead of using [code]If Vector_PointInTriangle(P(0), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(1), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(2), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(3), T(0), T(1), T(2)) Or _ Vector_PointInTriangle(P(0), T(1), T(2), T(3)) Or _ Vector_PointInTriangle(P(1), T(1), T(2), T(3)) Or _ Vector_PointInTriangle(P(2), T(1), T(2), T(3)) Or _ Vector_PointInTriangle(P(3), T(1), T(2), T(3)) Then CollisionBox_Find = True[/code] try using this, is much faster: [code]If Vector_PointInTriangle(P(0), T(0), T(1), T(2)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(1), T(0), T(1), T(2)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(2), T(0), T(1), T(2)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(3), T(0), T(1), T(2)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(0), T(1), T(2), T(3)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(1), T(1), T(2), T(3)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(2), T(1), T(2), T(3)) Then CollisionBox_Find = True Goto Later End If If Vector_PointInTriangle(P(3), T(1), T(2), T(3)) Then CollisionBox_Find = True Goto Later End If Later: 'now you continue your code here... [/code] just because, if one fails, it won't check the laters. But using ORs it would. I hope it's right now. [:D] |

Sr. Guapo | VBBR, would it not be easier to use an elseif statement instead of seperate if statements. That would also eliminate the need for the goto... How does VB use if/elseif, I get all the different languages confused. Does it immediately skip the other cases when a true case is found? |

VBBR | Honestly I don't know... but probably it skips. Not sure though. |

game_maker | Good day every one [:)] yeh , I have changed the code 180 degree and optimized every thing and now I am going for advanced collision [8)] ... VBBR & Sr. Guapo : I think it skips too .. you can find that simply by [code] Dim A as Byte ,B as Byte B = 2 if B > 0 then A = 1 elseif b > 1 A = 2 end if Msgbox iif(A = 2,"Do Not Skip","Skip") [/code] this PC does not have vb installed ,,,sorry [8)] SuperC : about the third unusefull method : I ment that the real angle mayby : theta 180 - theta 180 + theta 360 - theta the arccos & arcsin functions only return angle with range [0,90] so we need to find the real angle by finding the sings between .x & .y |

VBBR | Just ran the code you wrote. It skips. |