| 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. |