Visual Basic 6 (VB6)

By Joshua Smyth
www.Peachysoft.com
Download Source Code

This problem usually has people scratching their heads for a semi-decent amount of time - and it's no wonder why. There is a fair bit of math to get your head around. So a fair amount of google searching, reading through books, pouring over the gamedev messageboards and two university level math classes later. I think I can finally write that tutoral.

I going to assume that you can set up a 3d application. I use directX but any API should do. This tutorial should also be language independant. Even though the code given is written in Visual Basic. I've tried to include the concepts were possible. Porting the example program to C++ or to OpenGL should be fairly easy. But anyway - On with the tutorial.

Section One : The viewing Frustum

The viewing frustum is the volume of everything contained within your 3D scene. Ie inside of this odd shaped box is everything that is rendered on your computer screen. The viewing frustum has 6 sides. Named (quite unoriginally) the top, bottom, left, right, near and far planes. The eye is the position of the camera. Knowing the frustum planes is very handy and can be used for many tasks including culling polygons to render our scene faster as well as various other optimization techniques. However, for this application the only frustum planes we will be associating ourselves with are the near + far planes.

Top Down View of the Frustum

 
Part One : Normalizing the Mouse Coordinates
There are a few things that we need to know before we can proceed. We need to know

1. The width of our screen
2. The height of our screen
3. The aspect ratio
4. The field of view
5. The near clipping plane distance
6. The far clipping plane distance

Most of this stuff you would have already needed to decide on before directX was invoked. Now the height and width of our screen is pretty self explainitory and for this tutorial I shall assume 800x600 as being our screen size. The field of view is the viewing angle of the scene, usually pi/2 or 90 degrees. The near and far clipping plane distances are required when you create your perspective matrix. I usually use 0.1 and 500 respectfully. The aspect ratio has to do with the perspective ratio of the display. Usually width divided by height - but whatever values you use make sure you use the same values you defined when you created your perspective matrix.

The first thing We need to do is normalize our mouse coordinants. This means that we change our mouse click from values between (0,0) and (800,600) to values that are between (-1,1) and (1,-1)

Private Sub viewport_MouseDown(Button As Integer, Shift As Integer, _
   X As Single, Y As Single)
   
   Dim NX as single 'Normalized X coordinate
   Dim NY as single 'Normalized Y coordinate
   
   NX = X / ((Screen_Width / 2 ) - 1) / Aspect_Ratio
   NY = (1 - Y) / (Screen_height / 2)
End Sub

Part Two : Finding Points on the Near + Far Clipping Planes
We need to find two 3D points: One point residing on the near clipping plane and another point sitting on the far clipping plane. We need these two points because later on we are going to use them to create a ray between them which shoots through our world to select objects. In order for us to do this we need to use the Tan function to find ratios realitive to the view. Let me explain.

The Tan function and top down view of the frustum

 

Tan is the ratio between the opposite side of a triangle and the adjacent side of a triangle. If we take the viewing frustum and look at it either top down or from the side we get a triangle. This triangle can be split nicely down the middle into two equal right angle triangles. The ratio of our normalized screen coordinates can easily be found by multiplying them by tan(fov/2). For example: If our normalized X screen coordinate is 1. then the ratio will be Tan(fov/2) if our x coordinate is 0.5 as shown in the image above then the ratio between the opposite and the adjacent sides is going to be smaller. Thus the ratio is tan(fov/2) * 0.5.

So what we need to do is Multiply the normalized coordinates by tan(fov / 2) Once we have done this we can multiply our ratios by any value of Z (adjacent side) to get points on the near and far clipping planes - This is because of the formula Tan(theta) * Adjacent side = opposite side - Which should be familar to anyone who has done High School Trigonometry. We just replace Tan(theta) with our own ratios we worked out earlier and Z with our distances between the eye and the near or far planes and viola we've just found two points in 3D space.

Private Sub viewport_MouseDown(Button As Integer, Shift As Integer, _
   X As Single, Y As Single)
   
   Dim NX as single 'Normalized X coordinate
   Dim NY as single 'Normalized Y coordinate
   
   Dim RatioX as single	'The ratio between the oposite and adjacent sides
   Dim RatioY as single	'in our triangle.
   
   Dim P1 as D3DVector	'A 3D point on our near frustum plane
   Dim P2 as D3DVector	'A 3D point on our far frustum plane
   
   NX = X / ((Screen_Width / 2 ) - 1) / Aspect_Ratio
   NY = (1 - Y) / (Screen_height / 2) 
   
   RatioX = tan(fov / 2) * NX
   RatioY = tan(fov / 2) * NY
   
   P1.X = ratioX * Near
   P1.Y = ratioY * Near
   P1.Z = Near
   
   P2.X = ratioX * Far
   P2.Y = ratioY * Far
   P2.Z = Far
End Sub

Part Three : Transforming our points inside the viewing frustum into world points

The two points we have now obtained are realitive to the viewing frustum. We still need to do some calculations if we want to transform these realitive points into 3D world points. To do this we will need to find the inverse of the view matrix. (This is because the view matrix is located somewhere inside the 3D world and looking in some direction. It isn't just flat straight on and at the (0,0,0) position as we have assumed up until now.) This is actually really easy to do. Instead of going into Matrix theory here I'm just going to give you a simple formula to transform the points.

Transforming into world points

A` * P = TransformedP

Where

A` = The inverse view matrix

P = A point within our viewing frustum

'Inverse the view matrix
Dim matInverse As D3DMATRIX
D3DDevice.GetTransform D3DTS_VIEW, matView
    
D3DXMatrixInverse matInverse, 0, matView
    
VectorMatrixMultiply P1, P1, matInverse
VectorMatrixMultiply P2, P2, matInverse
public Sub VectorMatrixMultiply(ByRef vDest As D3DVECTOR, _
   ByRef vSrc As D3DVECTOR, ByRef mat As D3DMATRIX)
   
   dim W as single
   W = 1 / (vSrc.X * mat.m14 + vSrc.Y * mat.m24 + vSrc.Z * mat.m34 + mat.m44)
   
   vDest.X = (vSrc.X * mat.m11 + vSrc.Y * mat.m21 + vSrc.Z * mat.m31 + mat.m41) * W
   vDest.Y = (vSrc.X * mat.m12 + vSrc.Y * mat.m22 + vSrc.Z * mat.m32 + mat.m42) * W
   vDest.Z = (vSrc.X * mat.m13 + vSrc.Y * mat.m23 + vSrc.Z * mat.m33 + mat.m43) * W
end sub

All the above code is doing is taking the viewmatrix and creating an inverse matrix. Once this is done the inverse matrix is multiplied by our 3DPoints to turn them into 3D world points. DirectX doesn't supply a VectorMatrix multiply function so the above function will do our multiplication for us. If you know how to multiply a matrix by a vector then the above will be obvious. If you don't theres really no worry just use the code above.

Part Four : Creating a Ray

Now we have got our two points we need to turn them into a ray. The point on the near plane will become the starting point for our ray and the point on the far plane will become the end point. But we need to alter it a bit to fit the mathmatical definition of a ray. The equation for a ray is p(t) = StartPoint + t * Vdirection. Where Vdirection is a vector and t is how long the ray is. For the moment we are going to assume that the ray is infinate and so we can ignore t for now - but we are going to need it later on so keep it in the back of your minds.

How to find vDirection

VDir = P2 - P1

Where:

P2 is the point on our far plane

P1 is the point on our near plane

Yay! we now have a ray with a starting point and a direction in 3D space! Clap your hands and give yourself a pat on the back.

Section Two : Implementing ray to plane collision detection

Part One : Generating a Surface Normal

For this part we need to know the formula for our Ray. IE The startpoint as well as the direction vector. Part 1 was dedicated to finding this. We also need to know the equation for the plane we are testing against. This requires us to generate the normal of the object we are testing against. Which uses the cross-product - so I might as well spend a little bit of time talking about the crossproduct and normals and what a plane is and how it works.

The Cross-Product

The Cross-Product can be used to work out the surface normal of a polygon. The normal is quite simply the direction in which a polygon faces. This is extremely useful to know for several applications including lighting calculations. Essentially what the Cross-Product does, is take two vectors as inputs and comes up with a vector that is perpendicular to the two input vectors. Maybe a graphic will help

Example of a surface normal

 

Definition for the Cross-Product

P x Q = [P.y*Q.z - P.z*Q.y, P.z*Q.x - P.x*Q.z, P.x*Q.y - P.y*Q.x]

Now as you may have noticed the cross product takes two vectors and produces a normal vector as a result. But a polygon is made up of (at a minimum) 3 points. This doesn't pose much of a problem, 'cause if we take any 3 points that rest inside of a polygon we can easily create 2 vectors between the points.

Make 2 vectors from 3 points

P = point2 - point1

Q = point3 - point1

If we then calculate the cross-product of our two vectors we will get the resulting normal vector. Note: We might wish to normalize the cross-product, it's not really necessary but we have a built in directX function that does it for us so we might as well do it. (Normalizing a vector scales it down proportionally so that the length of the vector = 1)

Normalizing the cross-product

D3DXVec3Normalize(Vout,Vin)

Here is a function to generate the normal of a triangle

Public Sub GenerateTriangleNormal(p0 As D3DVECTOR, p1 As D3DVECTOR _
   , p2 As D3DVECTOR, vout As D3DVECTOR)
   
   'Variables required
   Dim v01 As D3DVECTOR        'Vector from points 0 to 1
   Dim v02 As D3DVECTOR        'Vector from points 0 to 2
   Dim vNorm As D3DVECTOR      'The final vector
   
   'Create the vectors from points 0 to 1 and 0 to 2
   D3DXVec3Subtract v01, p1, p0
   D3DXVec3Subtract v02, p2, p0
   
   'Get the cross product
   D3DXVec3Cross vNorm, v01, v02
   
   ' Normalize this vector
   D3DXVec3Normalize vNorm, vNorm
   
   ' Return the value
   vout.X = vNorm.X
   vout.Y = vNorm.Y
   vout.Z = vNorm.Z
End Sub 

Part Two: Generating a plane

Now that we have generated a normal for our polygon. We can extend this idea to create a plane. Now a plane is a 4D object that goes on infinately. We need to create this plane so we can test if our ray hits it. Note: Because the ray and the plane are both infinate then they will always hit somewhere in world space, unless they are parallel.

Formula for a plane

[Nx, Ny, Nz,-N.P0]

As said before a plane is a four dimentional vector. The first 3 components corespond to the three components of the normal we generated earlier. -N.P0 is the negitive dot-product between the normal and any point on the plane.

The Dot Product

N.P0 = (Px * Qx) + (Py * Qy) + (Pz * Qz)

I won't spend too much time on the dot product here, I'll come back to it in more detail in section 3. Instead I will just give you the formula for it. (Remember the last component of the plane is -N.P0 so we will have to multiply the dot product by -1) If you've done all that - you now have a plane.

Here it is in code

'############################################
'# Create a 4 Dimentional Plane Vector
'############################################ 
Public Function Create4DPlaneVectorFromPoints(v1 As D3DVECTOR, _
   v2 As D3DVECTOR, v3 As D3DVECTOR) As D3DVECTOR4
   Dim Edge1 As D3DVECTOR
   Dim edge2 As D3DVECTOR
   
   Dim pNormal As D3DVECTOR
   
   D3DXVec3Subtract Edge1, v2, v1
   D3DXVec3Subtract edge2, v3, v1
   
   D3DXVec3Cross pNormal, Edge1, edge2  'This is the normal vector
   D3DXVec3Normalize pNormal, pNormal    'This is the scaled normal vector
   
   'Generate the 4D Plane Vector
   Create4DPlaneVectorFromPoints.W = -D3DXVec3Dot(pNormal, v1)
   Create4DPlaneVectorFromPoints.X = pNormal.X
   Create4DPlaneVectorFromPoints.Y = pNormal.Y
   Create4DPlaneVectorFromPoints.Z = pNormal.Z
End Function

Part Three : Ray - Plane intersection

Alrighty this is where the fun begins. We're finally going to shoot our ray at something. Remember the equation for a line above and it had this funny little t in it? P(t) = Pstart + t*Vdir ? And remember I told you earlier that because the plane and the ray are infinate they will always intersect at some point? Well t is going to help us find the point of intersection between the ray and the plane.

Formula for working out t

t = -1 * (L.Pstart) / (L.Vdir)

Where:

L.Pstart is the dot-product between the the plane and the starting point

L.Vdir is the dot-product between the the plane and the direction vector

There is a proof for this formula but I'm not gonna include it, if you want to do additional research be my guest. Now there is only one case when the ray and plane will not intersect and that is when they are parallel. They are parallel when the dot-product of L.Vdir = 0. We would also have a divide by zero error here, so watch out for that senario when it comes to coding the problem.

So if L.Vdir is not equal to 0 we have found the value for t that we where looking for. Subsituting back into the original equation for a line P(t) = Q + tV we can find the point of intersection.

VIntersectOut.X = Q.X + (T * V.X)

VIntersectOut.Y = Q.Y + (T * V.Y)

VIntersectOut.Z = Q.Z + (T * V.Z)

'#######################################################
'#                                                                                                          
'# Function Name    :   Ray Intersect Plane                                                                 
'# Desc             :   Checks to see if a ray has intersected a plane                                      
'#                                                                                                           
'#                      Plane  = The plane to test against                                                  
'#                      PStart = The starting point of the ray                                              
'#                      VDir   = A vector representing the direction of the ray                             
'#                      VIntersectOut = A variable that returns the coordinates of the intersection         
'#                                                                                                          
'# Returns          :   TRUE if a collision occurs                                                          
'#                      FALSE if there is no collision                                                      
'#                                                                                                          
'#######################################################
Public Function RayIntersectPlane(Plane As D3DVECTOR4, PStart As D3DVECTOR, _
   vDir As D3DVECTOR, ByRef VIntersectOut As D3DVECTOR) As Boolean
   
   Dim Q As D3DVECTOR4     'Start Point
   Dim V As D3DVECTOR4     'Vector Direction
   
   Dim planeQdot As Single 'Dot products
   Dim planeVdot As Single
    
   Dim T As Single         'Part of the equation for a ray P(t) = Q + tV
      
   Q.X = PStart.X          'Q is a point and therefore it's W value is 1
   Q.Y = PStart.Y
   Q.Z = PStart.Z
   Q.W = 1
   
   V.X = vDir.X            'V is a vector and therefore it's W value is zero
   V.Y = vDir.Y
   V.Z = vDir.Z
   V.W = 0
   planeVdot = D3DXVec4Dot(Plane, V)
   planeQdot = D3DXVec4Dot(Plane, Q)
   'If the dotproduct of plane and V = 0 then there is no intersection
   If planeVdot <> 0 Then
      T = (planeQdot / planeVdot) * -1
      'This is where the line intersects the plane
      VIntersectOut.X = Q.X + (T * V.X)
      VIntersectOut.Y = Q.Y + (T * V.Y)
      VIntersectOut.Z = Q.Z + (T * V.Z)
      RayIntersectPlane = True
   Else
      'No Collision
      RayIntersectPlane = False
   End If
End Function

There you have it. We now have the point of intersection on our plane!

Section Three : Seeing if our intersection point is within a Polygon

Alright, we are finally getting there. The last part of this is to see if our intersection point is contained within our given polygon. I'm going to use a triangle here because it's the simplest polygon there is. If you wished to test against a more complex polygon, such as a square or a hexagon or whatever, you can still use method given here. You'll just need to extend it a little.

The Dot Product (For real this time)

Ok, I mentioned the dot product before. This time round I'll spend a little more time explaining what it is and how it's useful. The dot product's main use is to determine the angle between two vectors. There some particularly interesting facts about the dot product that are listed below.

• Cos (Theta) = Dot Product
• If the Dot Product = 0 : The vectors are at 90 degrees to each other
• If the Dot Product > 0 : The second vector is on the near side of a plane perpandicular to the first vector
• If the Dot Product < 0 : The second vector is on the far side of a plane perpandicular to the first vector

 

This little bit of information is probably best represented graphicly to give you a better idea.

So how can this aid us?

First we have to use our three verticies that define our triangle to obtain three vectors.

 Second we need to create vectors perpandicular to our new vectors

Then we need to create another set of vectors from our verticies to our intersection point from section 2 above.  

 

Once this is done we apply dot product tests. For each vertex we need to test the dot product between it's perpandicular vector and the vector between the vertex and the intersection point.

If all the dot products are > 0 then the point lies within the triangle. Note: In the previous version of this article I mentioned that verticies V1, V2 and V3 have to be presented to the function in clockwise order, I have re-written the function so that the verticies can actually be given to the function in any order and it will still work out a hit, this is done by performing an addictional check on the dot products - If all the dot-products are < 0 then there is a hit.

There is also one last thing we need to do before we run off and start coding this algorithim. The method above requires us to create vectors perpandicular to other vectors. In 3D this is near impossible - It may actually be possible, but I haven't seen a way to do it. So what we are going to do to make it more managable is to project our 3D triangle onto either the XY, YZ or XZ planes changing our problem from a 3D problem to a 2D problem.

Now we need to know which two planes we are going to project onto. How to do this is realativly easy. First we need to generate the surface normal. (We did this in section 2 Part 1) Then we discard the coordinate which is greatest in absolute value. This will project our triangles verticies from three dimentions into two dimentions. We are now free to calculate Two Dimentional vectors and obtaining their perpinducular vectors by swaping the position of the two values and multiplying the first entry by -1.

Here You Can Download The Source Code For It All

I hope you liked this tutorial; Its the first one I have written and would like to hear from you if you found it useful in anyway. I've created an example program which I'd encourage you to download and play with. If any of the contents in this tutorial were a bit vague I appologise. Email me for clarifications. If you've got some suggestions on how to improve this tutorial then I'd be glad to hear from you.

Joshua Smyth
www.peachysoft.com
Download Source Code

This tutorail is released under the GNU Free Documentation License 1.2. The original can be found here.