# More and More Collision Detection(3D)

Started by Feb 15 2000 03:02 PM

,
5 replies to this topic

###
#1
Members - Reputation: **275**

Posted 15 February 2000 - 03:02 PM

One of the most common posts, harder to explain!
I have seen multiple styles of collision detection. I don't have a clue on how people do it. I understand you have to find the plane and check if you collide with it, but I don't understand those weird vector functions.
What is a dot product?
Help me out here, I'm not even near pre-calc.
Oh ya, I already know about spheres and bounding boxes and they are a horrible approach to quake-style collision detection.
Edited by - nes8bit on 2/15/00 9:06:12 PM

###
#2
Moderators - Reputation: **11365**

Posted 16 February 2000 - 03:02 AM

Ok, how much math do you know? Algebra I? Geometry? It would be easier to given an answer if we knew what the target audience is.

However, here''s the short answer for a dot product: take the two vectors, multiply pair-wise their elements and add the products together. So (x1, y1, x1).(x2, y2, z2) = x1 * x2 + y1 * y2 + z1 * z2 .

However, here''s the short answer for a dot product: take the two vectors, multiply pair-wise their elements and add the products together. So (x1, y1, x1).(x2, y2, z2) = x1 * x2 + y1 * y2 + z1 * z2 .

###
#4
Members - Reputation: **166**

Posted 16 February 2000 - 09:52 AM

Well DOT products are fairly easily understood when you put them in the context of matrix's. A matrix is similar to an array but a matrix only accepts number input. So lets say we have two matrix's A and B.

A1=4 A2=3 A3=5 A4=2 AND B1=3 B2=4 B3=8 B5=3

The matrix's look like this

A= [4 3]

[5 2]

B= [3 4]

[8 3]

Now this is where DOT Product comes in. In order to multiply the matrix's togeather and get the correct answer you take and Multiply the matrix's corrosponding entries and then add them togeather. For instance the Dot product of the above 2 matrix's would be:

(A1*B1)+(A2*B2)+(A3*C3)+(A4*B4)

Which equils

(4*3)+(3*4)+(5*8)+(2*3)

Now as far as vectors go...

There are 2 types of numbers. Scalar and Vector. Scalar values are numbers which do not have a direction associated with them. An example of a Scalar quantity would be the ammount of money you have in your wallet. A vector quantity has a direction associated with it. So a good example of a Vector Quantity would be a character in your game moving 5 steps forward.

Both of these are pretty much paired togeather when it comes to 3d collision detection. You use vector quantities held in a matrix to detect where the bounding box is around your player, what direction your going in, and if the box has collided with another bounding box. I'd suggest getting a book on Linear Algebra if you'd like to find out more about the subject. You don't even need to buy one, most libraries are filled with them. Good Luck and I hope I helped.

Edited by - evaclear on 2/16/00 3:55:13 PM

A1=4 A2=3 A3=5 A4=2 AND B1=3 B2=4 B3=8 B5=3

The matrix's look like this

A= [4 3]

[5 2]

B= [3 4]

[8 3]

Now this is where DOT Product comes in. In order to multiply the matrix's togeather and get the correct answer you take and Multiply the matrix's corrosponding entries and then add them togeather. For instance the Dot product of the above 2 matrix's would be:

(A1*B1)+(A2*B2)+(A3*C3)+(A4*B4)

Which equils

(4*3)+(3*4)+(5*8)+(2*3)

Now as far as vectors go...

There are 2 types of numbers. Scalar and Vector. Scalar values are numbers which do not have a direction associated with them. An example of a Scalar quantity would be the ammount of money you have in your wallet. A vector quantity has a direction associated with it. So a good example of a Vector Quantity would be a character in your game moving 5 steps forward.

Both of these are pretty much paired togeather when it comes to 3d collision detection. You use vector quantities held in a matrix to detect where the bounding box is around your player, what direction your going in, and if the box has collided with another bounding box. I'd suggest getting a book on Linear Algebra if you'd like to find out more about the subject. You don't even need to buy one, most libraries are filled with them. Good Luck and I hope I helped.

Edited by - evaclear on 2/16/00 3:55:13 PM

###
#5
Members - Reputation: **122**

Posted 16 February 2000 - 10:27 AM

The dot product between the two vectors u and v is the number you get when multiplying the length of u with the length of the component of v that is parallell with u.

The formula for the dot product looks like this:

u·v = /u/ /v/ cos [u, v]

where /u/ is the length of the vector and [u, v] is the smallest angle between the vectors.

Note that with a cartesian system, where all axis are of unit length and orthogonal, the formula is a lot simpler:

u·v = xu*xv + yu*yv + zu*zv

With the help of these two formulas it''s easy to compute the angle between two vectors, which is used in many situations, e.g. computing distance, hidden surface removal and lighting calculations.

Read this article on 3D vectors. (Written by me )

The formula for the dot product looks like this:

u·v = /u/ /v/ cos [u, v]

where /u/ is the length of the vector and [u, v] is the smallest angle between the vectors.

Note that with a cartesian system, where all axis are of unit length and orthogonal, the formula is a lot simpler:

u·v = xu*xv + yu*yv + zu*zv

With the help of these two formulas it''s easy to compute the angle between two vectors, which is used in many situations, e.g. computing distance, hidden surface removal and lighting calculations.

Read this article on 3D vectors. (Written by me )

###
#6
Members - Reputation: **275**

Posted 16 February 2000 - 01:21 PM

Ok more text needed...

I was not wondering exactly how a dot product is calculated (it is in DX) or what only the dot product does. I needed help on an accurate style of collision detection. The only thing I thought of was use 3-2D triangles to check collisions.(too hard to explain) I have source for collisions, but it is confusing. I ported it from somewhere and it does not work. Sorry for the coding style since gamedev removes formatting without HTML.

Option Explicit

#Const Test_Cull = False

Private Const EPSILON As Single = 0.000001

Function Intersect_Triangle(Orig As D3DVECTOR, Dir_ As D3DVECTOR, _

Vert0 As D3DVECTOR, Vert1 As D3DVECTOR, Vert2 As D3DVECTOR, _

Optional t As Single, Optional u As Single, Optional v As Single) As Boolean

Dim Edge1 As D3DVECTOR, Edge2 As D3DVECTOR, tvec As D3DVECTOR, pvec As D3DVECTOR, qvec As D3DVECTOR

Dim det As Single, inv_det As Single

''/* find vectors for two edges sharing vert0 */

dx.VectorSubtract Edge1, Vert1, Vert0

dx.VectorSubtract Edge2, Vert2, Vert0

''/* begin calculating determinant - also used to calculate U parameter */

dx.VectorCrossProduct pvec, Dir_, Edge2

''/* if determinant is near zero, ray lies in plane of triangle */

det = dx.VectorDotProduct(Edge1, pvec)

#If Test_Cull Then '' /* define TEST_CULL if culling is desired */

If det < EPSILON Then Exit Function

''/* calculate distance from vert0 to ray origin */

dx.VectorSubtract tvec, Orig, Vert0

''/* calculate U parameter and test bounds */

u = dx.VectorDotProduct(tvec, pvec)

If u < 0 Or u > det Then Exit Function

''/* prepare to test V parameter */

dx.VectorCrossProduct qvec, tvec, Edge1

''/* calculate V parameter and test bounds */

v = dx.VectorDotProduct(Dir_, qvec)

If v < 0 Or u + v > det Then Exit Function

''/* calculate t, scale parameters, ray intersects triangle */

t = dx.VectorDotProduct(Edge2, qvec)

inv_det = 1 / det

t = t * inv_det

u = u * inv_det

v = v * inv_det

#Else ''/* the non-culling branch */

If det > -EPSILON And det < EPSILON Then Exit Function

inv_det = 1 / det

''/* calculate distance from vert0 to ray origin */

dx.VectorSubtract tvec, Orig, Vert0

''/* calculate U parameter and test bounds */

''*u = DOT(tvec, pvec) * inv_det;

u = dx.VectorDotProduct(tvec, pvec) * inv_det

If u < 0 Or u > 1 Then Exit Function

''/* prepare to test V parameter */

dx.VectorCrossProduct qvec, tvec, Edge1

''/* calculate V parameter and test bounds */

v = dx.VectorDotProduct(Dir_, qvec) * inv_det

If v < 0 Or u + v > 1 Then Exit Function

''/* calculate t, ray intersects triangle */

t = dx.VectorDotProduct(Edge2, qvec) * inv_det

#End If

Intersect_Triangle = True

End Function

I was not wondering exactly how a dot product is calculated (it is in DX) or what only the dot product does. I needed help on an accurate style of collision detection. The only thing I thought of was use 3-2D triangles to check collisions.(too hard to explain) I have source for collisions, but it is confusing. I ported it from somewhere and it does not work. Sorry for the coding style since gamedev removes formatting without HTML.

Option Explicit

#Const Test_Cull = False

Private Const EPSILON As Single = 0.000001

Function Intersect_Triangle(Orig As D3DVECTOR, Dir_ As D3DVECTOR, _

Vert0 As D3DVECTOR, Vert1 As D3DVECTOR, Vert2 As D3DVECTOR, _

Optional t As Single, Optional u As Single, Optional v As Single) As Boolean

Dim Edge1 As D3DVECTOR, Edge2 As D3DVECTOR, tvec As D3DVECTOR, pvec As D3DVECTOR, qvec As D3DVECTOR

Dim det As Single, inv_det As Single

''/* find vectors for two edges sharing vert0 */

dx.VectorSubtract Edge1, Vert1, Vert0

dx.VectorSubtract Edge2, Vert2, Vert0

''/* begin calculating determinant - also used to calculate U parameter */

dx.VectorCrossProduct pvec, Dir_, Edge2

''/* if determinant is near zero, ray lies in plane of triangle */

det = dx.VectorDotProduct(Edge1, pvec)

#If Test_Cull Then '' /* define TEST_CULL if culling is desired */

If det < EPSILON Then Exit Function

''/* calculate distance from vert0 to ray origin */

dx.VectorSubtract tvec, Orig, Vert0

''/* calculate U parameter and test bounds */

u = dx.VectorDotProduct(tvec, pvec)

If u < 0 Or u > det Then Exit Function

''/* prepare to test V parameter */

dx.VectorCrossProduct qvec, tvec, Edge1

''/* calculate V parameter and test bounds */

v = dx.VectorDotProduct(Dir_, qvec)

If v < 0 Or u + v > det Then Exit Function

''/* calculate t, scale parameters, ray intersects triangle */

t = dx.VectorDotProduct(Edge2, qvec)

inv_det = 1 / det

t = t * inv_det

u = u * inv_det

v = v * inv_det

#Else ''/* the non-culling branch */

If det > -EPSILON And det < EPSILON Then Exit Function

inv_det = 1 / det

''/* calculate distance from vert0 to ray origin */

dx.VectorSubtract tvec, Orig, Vert0

''/* calculate U parameter and test bounds */

''*u = DOT(tvec, pvec) * inv_det;

u = dx.VectorDotProduct(tvec, pvec) * inv_det

If u < 0 Or u > 1 Then Exit Function

''/* prepare to test V parameter */

dx.VectorCrossProduct qvec, tvec, Edge1

''/* calculate V parameter and test bounds */

v = dx.VectorDotProduct(Dir_, qvec) * inv_det

If v < 0 Or u + v > 1 Then Exit Function

''/* calculate t, ray intersects triangle */

t = dx.VectorDotProduct(Edge2, qvec) * inv_det

#End If

Intersect_Triangle = True

End Function