VB:Tutorials:3Dmouse

From GPWiki
Jump to: navigation, search

How to use the mouse to select objects in 3D space

By Joshua Smyth

www.TinyFrogSoftware.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 maths 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

VB3DClick fustrum.gif

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

VB3DClick topdown.gif

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)

VB3DClick grid.gifVB3DClick between.gifVB3DClick grid2.gif

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 ' It was this: NX = X / ((Screen_Width / 2 ) - 1) / Aspect_Ratio NY = 1 - (y / (Screen_height / 2)) ' It was this: 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

VB3DClick tan.gifVB3DClick tan2.gifVB3DClick tan3.gif

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 ' It was this: NX = X / ((Screen_Width / 2 ) - 1) / Aspect_Ratio NY = 1 - (y / (Screen_height / 2)) ' It was this: 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

VB3DClick normal.gif

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.

VB3DClick dot.gif

So how can this aid us?

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

VB3DClick vectors.gif

Second we need to create vectors perpandicular to our new vectors

VB3DClick perpandicular.gif

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

VB3DClick angle.gifVB3DClick angle2.gifVB3DClick angle3.gif

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.

VB3DClick project.gif

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 is the code for it all '######################################################################### '# # '# Function Name  : Point In Triangle # '# Desc  : Function tests if a given point is within # '# a triangle as defined by verticies V1, V2 and V3 # '# P is the point to be tested # '# # '######################################################################### Public Function PointInTriangle(v1 As D3DVECTOR, v2 As D3DVECTOR, v3 As D3DVECTOR, P As D3DVECTOR)

   'Project all vectors onto the xy plane
   'making this a 2d problem instead of a 3d problem
   
   'If the point is within the triangle in 3d space, it is also within the triangle in 2d
   'space. So it is ok to do this method.
   
   'V1, V2 and V3 do not need to be in clockwise order
   
   Dim vertex1 As D3DVECTOR2   'Our 2D verticies
   Dim vertex2 As D3DVECTOR2
   Dim vertex3 As D3DVECTOR2
   
   Dim edge1 As D3DVECTOR2     'Our 2D vectors
   Dim edge2 As D3DVECTOR2
   Dim edge3 As D3DVECTOR2
   
   Dim NormEdge1 As D3DVECTOR2 'Vectors perpendicular to to the edge vectors
   Dim NormEdge2 As D3DVECTOR2
   Dim NormEdge3 As D3DVECTOR2
   
   Dim testvec1 As D3DVECTOR2  'A vector drawn between a triangle vertex and the test point
   Dim testvec2 As D3DVECTOR2
   Dim testvec3 As D3DVECTOR2
   
   Dim dot1 As Single          'Dot products can tell us the angle between two vectors
   Dim dot2 As Single          'they can also tell us what side of a plane a point is on.
   Dim dot3 As Single
   
   Dim PointVertex As D3DVECTOR2   'A 2d version of our testpoint
   
   Dim TriangleNormal As D3DVECTOR         'Which direction is our 3d triangle pointing?
   Dim ABSTriangleNormal As D3DVECTOR      'Absolute values of the above
   
   'Get TriangleNormal
   GenerateTriangleNormal v1, v2, v3, TriangleNormal
   'What is the greatest absolute value
   ABSTriangleNormal.X = Abs(TriangleNormal.X)
   ABSTriangleNormal.Y = Abs(TriangleNormal.Y)
   ABSTriangleNormal.Z = Abs(TriangleNormal.Z)
   
   'Discard the greatest absolute value and project onto the other
   'remaining planes.
   
   If ABSTriangleNormal.X > ABSTriangleNormal.Y And ABSTriangleNormal.X > ABSTriangleNormal.Z Then
       
       Project3dvectorYZplane PointVertex, P
       Project3dvectorYZplane vertex1, v1
       Project3dvectorYZplane vertex2, v2
       Project3dvectorYZplane vertex3, v3
   
   Else
       If (ABSTriangleNormal.Y > ABSTriangleNormal.X) and (ABSTriangleNormal.Y > ABSTriangleNormal.z) Then
           Project3dvectorXZplane PointVertex, P
           Project3dvectorXZplane vertex1, v1
           Project3dvectorXZplane vertex2, v2
           Project3dvectorXYplane vertex3, v3
       Else
           Project3dvectorXYplane PointVertex, P
           Project3dvectorXYplane vertex1, v1
           Project3dvectorXYplane vertex2, v2
           Project3dvectorXYplane vertex3, v3
       End If
   End If
   
   'Create the vectors from the verticies
   D3DXVec2Subtract edge1, vertex2, vertex1
   D3DXVec2Subtract edge2, vertex3, vertex2
   D3DXVec2Subtract edge3, vertex1, vertex3
   
   'Create vectors perpendicular to the edge vectors
   OrthangonaliseVec2 NormEdge1, edge1
   OrthangonaliseVec2 NormEdge2, edge2
   OrthangonaliseVec2 NormEdge3, edge3
   'Create vector between the vertex point and the testpoint
   D3DXVec2Subtract testvec1, vertex1, PointVertex
   D3DXVec2Subtract testvec2, vertex2, PointVertex
   D3DXVec2Subtract testvec3, vertex3, PointVertex
   
   
   'Calculate dot products
   dot1 = D3DXVec2Dot(testvec1, NormEdge1)
   dot2 = D3DXVec2Dot(testvec2, NormEdge2)
   dot3 = D3DXVec2Dot(testvec3, NormEdge3)
   
   If dot1 > 0 And dot2 > 0 And dot3 > 0 Then
       PointInTriangle = True
   End If
   If dot1 < 0 And dot2 < 0 And dot3 < 0 Then
       PointInTriangle = True
   End If
   

End Function

Public Sub OrthangonaliseVec2(ByRef vout As D3DVECTOR2, vin As D3DVECTOR2)

   vout.X = vin.Y * -1
   vout.Y = vin.X

End Sub

Public Sub Project3dvectorXYplane(ByRef vout As D3DVECTOR2, vin As D3DVECTOR)

   vout.X = vin.X
   vout.Y = vin.Y

End Sub

Public Sub Project3dvectorYZplane(ByRef vout As D3DVECTOR2, vin As D3DVECTOR)

   vout.X = vin.Z
   vout.Y = vin.Y

End Sub

Public Sub Project3dvectorXZplane(ByRef vout As D3DVECTOR2, vin As D3DVECTOR)

   vout.X = vin.X
   vout.Y = vin.Z

End Sub

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