go to Tutorials Page | go to 3DKingdoms.com

Selection Tutorial (3d programming)

I plan to add images and diagrams to this tutorial sometime in the future. I may also try to clarify some parts of the text later. However the main tutorial part is done right now.
You might also want to read my Weekly Articles related to this topic: Line Box Intersection | Reflecting a Vector | 3D Vector Class | Line Mesh Intersection (sample program), Triangle Selection Program

Contents - Selection Tutorial

Introduction

In this tutorial any source code is given in C++, and uses a 3d vector class. In the source code it uses OpenGL for any rendering (or buffer reads), so it will help to be familiar with OpenGL, but of course the concepts and descriptions should be useful whatever you use for rendering. For more information about OpenGL go to www.opengl.org.

If you want to know more about programming a 3D Editor this tutorial should be useful to you, but even if you're more interested in just 3D programming in general, there might be times when you find you can apply some of the ideas covered here. 3D collision detection in particular is closely related to selection. I find knowing as much as possible about 3D math in general (time-permitting) is best. I'm assuming a reader will have knowledge of the basic 3D math, such as the Dot product and its uses. The algorithms explained here though can be fairly advanced, and I'm sure I could have gone into more depth in many places. I use all of these selection algorithms (and more) in the 3D Kingdoms Creator, but it's possible when editing code for this tutorial or in writing the descriptions I've made some mistakes.

Selection isn't speed critical, since a user won't click to select as many times a second as possible, so the code is called far less than the rendering and animation code. So for the most part I'm not worried about speed, as the algorithms described here all seem to give me an instant response so far. However response time will vary greatly on scene complexity, so if I ever start working with extremely complex scenes, there's room for optimization on the following.

Here's a selection exercise... let's say you want to test to see if a 3D point is in a cylinder. There are reasons why you might want to do this, for instance my algorithm for selecting vertices near bones to attach to them is based on this. (Although because of varying weights with distance and attachment influence shapes that aren't a plain cylinder, somewhat more complicated.)

I'll warn you this algorithm is just what I came up with myself without looking how anyone else does it, so it works fine for what I'm doing, but may not be the best way if you're serious about point-in-cylinder algorithms =)
Let's call the test point P (defined by an x,y, and z coordinate), and the cylinder C (defined by a line of 2 points CP1, CP2, and a radius, CR.)
To get the planes defined by the 2 caps of the cylinder is easy. You can define a plane with a point on the plane and the normal. For instance one plane has point CP1 and its normal CN1 = CP2-CP1. If the test point isn't between these two cap planes, it can't be within the cylinder. The dot product can be used to find which side of a plane a point is on. The total formula for this test would be: (P-CP1)Dot(CN1)>0

So now if the point is within the two cap planes, the question is if the point is if it is also within the radius. We could use the 3D distance between 2 points if only the test point was on one of the cap planes of the cylinder. Once again the dot product is useful, as it can also tell you the distance between a point and a plane. Then we can move the test point that distance along the normal to be on the cap plane without changing its distance from the center of the cylinder. The code for the entire algorithm follows:

   CN1 = CP2 - CP1;
   CN1.Normalize();
   CN2 = -CN1;
   fDistanceToPlane = Dot( P-CP1, CN1 );
   if (fDistanceToPlane < 0 )	return false;	
   if (Dot( P-CP2, CN2 ) < 0) return false; 
   TempP =  P - (CN1 * fDistanceToPlane);
   fDistanceFromCenter = Distance( TempP,  CP1);
   If (fDistanceFromCenter > fCR) return false;	
   return true; // All tests passed, point is in cylinder

Back-Buffer Selection

One common method of pixel-exact selection is called back-buffer selection. We forget about any 3d representation and just look at the pixel the user clicked on. The idea behind back buffer selection is to render the scene as usual, except render whatever you want to be able select with its own flat shade; then to find out what the user selects, simply take the color at the mouse location, and look up what object that color corresponds too. Because for many years any 3D card (or software implementation) have been able to use double-buffering, the selection buffer is never seen, it's rendered over with the normal 3D scene before swapping the buffers.

One thing to be aware of when using back-buffer selection is that 16-bit mode can't store 8-bits per color like 24-bit mode will. Usually two channels will have 5-bits, one 6-bits. You can make your back-buffer selector work with 16-bit mode by advancing the index by 8 instead of 1 (this means advancing by 8 per channel.) Nowadays it's quite rare for someone who runs graphics programs to not have 24-bit color depth, you'll have to decide for yourself whether you need to support 16-bit mode. (Voodoo3 graphics cards and below only support up to 16-bit color. Also you'll want to disable dithering with glDisable(GL_DITHER) before rendering into the back-buffer.)

Regardless of color depth it is important to remember that any state that could change the color needs to be disabled, such as GL_TEXTURE, GL_LIGHTING or GL_FOG.
And now some code. Parts of this code will look odd since it's set up to allow looping through a selected area, if you will only use a single pixel you won't need width&height and new&delete.

   glClearColor (0.0,0.0,0.0,0.0);
   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
   glEnable (GL_COLOR_MATERIAL);
   glDisable (GL_TEXTURE_2D);
   // World->DrawBackBufferSelectableObjects();
   //
   // Draws everything with backbuffer selection, keeping track of what object or sub-object each color matches up with
   // nIndex would start at 1, then be incremented after each selectable mesh or chunk of a mesh.
   // The code for drawing a selectable item with 24-bit color might look like this:
   //
   //	glColor3ub ( nIndex % 256, (nIndex>>8) % 256, (nIndex>>16) % 256);
   //	DrawSingleSelectable ( ) // Calling the same gl rendering code used for drawing the object on the screen
   //	nIndex++;
   //
   // note: (nStartX, nStartY) used later is the point the user has clicked

   nWidth = 1; 
   nHeight = 1;
   unsigned char *pRGB = new unsigned char [3 * (nWidth+1) * (nHeight + 1) + 3];
   
   glReadBuffer( GL_BACK );
   glReadPixels( nStartX, nStartY, nWidth, nHeight, GL_RGB, GL_UNSIGNED_BYTE, pRGB);

   int ColorNumber = (pRGB[ 0 ]) + (pRGB[ 1 ]<<8) + (pRGB[ 2 ]<<16);
   World->SelectBackBufferObject( ColorNumber );

   delete[] pRGB;

Suppose the user clicks the mouse somewhere on a 3D scene. Since the monitor is 2D, the user clicked on a 2D pixel, but if you imagine he was a selecting from the 3D scene, the user's selection is actually a 3D ray in your 3D scene's world space. (A ray directly into the screen that goes through that pixel and everything behind it or in front of it.) You can calculate this ray and use it to decide what was selected. For instance if the user is selecting from a group of tiny points, you can use this method to select the point closest to the place actually clicked. Calculating this ray isn't trivial, but it can be done in a few lines if you use the OpenGL gluUnProject function. (For the Z coordinate of the screen location passed in to gluUnProject, 0.0 corresponds to the near clip plane, and 1.0 the far clip plane.) Here's a snippet of code to give you the idea, it might not work exactly right in a different program. (x and y are the points of the mouse click. ClickRayP1 and ClickRayP2 are returned.)

   // This function will find 2 points in world space that are on the line into the screen defined by screen-space( ie. window-space ) point (x,y)
   double mvmatrix[16];
   double projmatrix[16];
   int viewport[4];
   double dX, dY, dZ, dClickY; // glUnProject uses doubles, but I'm using floats for these 3D vectors
	
   glGetIntegerv(GL_VIEWPORT, viewport);	
   glGetDoublev (GL_MODELVIEW_MATRIX, mvmatrix);
   glGetDoublev (GL_PROJECTION_MATRIX, projmatrix);
   dClickY = double (g_WindowHeight - y); // OpenGL renders with (0,0) on bottom, mouse reports with (0,0) on top
	
   gluUnProject ((double) x, dClickY, 0.0, mvmatrix, projmatrix, viewport, &dX, &dY, &dZ);
   ClickRayP1 = Vector3 ( (float) dX, (float) dY, (float) dZ );
   gluUnProject ((double) x, dClickY, 1.0, mvmatrix, projmatrix, viewport, &dX, &dY, &dZ);
   ClickRayP2 = Vector3 ( (float) dX, (float) dY, (float) dZ );

One reason you might want to use this method instead of back-buffer selection is so the user doesn't have to click the point exactly where it is drawn, you can just select the closest point that's within a certain distance from the ray. Another reason is you don't have to worry about rendering issues causing selection to work differently on a different computer (I haven't noticed this to be a problem, but it's a possibility with buffer selection.) Once you have the 2 world-space points on the ray, you can find the closest selectable point by testing to see which point's ray (formed by the vector between the selectable point and the origin point of the clickRay) is closest to the clickRay. The code is below:

   vClickSlope = vClickRayP2 - vClickRayP1;
   vClickSlope.Normalize();

   for (i = 0; i < numPoints; i++)
   {
      vSelSlope = pvPoints[i] - vClickRayP1;
      vSelSlope.Normalize( );

      float TestDist = Distance( vSelSlope, vClickSlope );
      if ( TestDist < MinDistance )
      {
         MinDistance = TestDist;
         nSelected = i;
      }
   }

Ray Intersection with Plane:

You may also want test if this ray intersects with a triangle, since any 3d geometry will probably be made of triangles. See the code for Line Intersects Triangle in the appendix. That algorithm is in some ways similiar to the one described in this section.

Sometimes you may want to calculate the point at which a ray intersects with a plane. An example of where I use this is to check whether the mouse pointer is over an axis of the gizmo. (The function to get the world-space ray the mouse position defines is under the point selection header.) If so turn I turn it yellow, thus letting user know that clicking will drag by this axis. I treat each axis line as a 3D box, and test the ray against the planes of the box. Calculating the proper box planes isn't entirely simple, but I just wanted to give an example of somewhere I use this. Here's the source code for finding the ray intersection point on the plane:

   // Returns in (fX, fY) the location on the plane (P1,P2,P3) of the intersection with the ray (R1, R2)
   // First compute the axes
   V1 = P2 - P1;
   V2 = P3 - P1;
   V3 = CrossProduct ( V1, V2);
   
   // Project ray points R1 and R2 onto the axes of the plane. (This is equivalent to a rotation.)
   vRotRay1 = CVector3 ( Dot (V1, R1-P1 ), Dot (V2, R1-P1 ), Dot (V3, R1-P1 ) );
   vRotRay2 = CVector3 ( Dot (V1, R2-P1 ), Dot (V2, R2-P1 ), Dot (V3, R2-P1 ) ); 
   // Return now if ray will never intersect plane (they're parallel)
   if (vRotRay1.z == vRotRay2.z) return FALSE;
   
   // Find 2D plane coordinates (fX, fY) that the ray interesects with
   float fPercent = vRotRay1.z / (vRotRay2.z-vRotRay1.z);
   vIntersect2d = vRotRay1 + (vRotRay1-vRotRay2) * fPercent;
   fX = vIntersect2d.x;
   fY = vIntersect2d.y;

   // Note that to find the 3D point on the world-space ray use this
   // vInstersect = R1 + (R1-R2) * fPercent;   

This test could also be used for something like testing if line-of-sight is obstructed by a plane, or any number of other things. I get 2D plane coordinates here because I'm dealing with rectangles; I can then easily test whether or not a point is on a rectangle from 2d coordinates.

Area (Marquee) Select:

Both back-buffer and point selection can be expanded to work for selecting everything within a certain area, instead of just whatever is below or nearest to the mouse cursor. I'll assume that the user selects a rectangle on the screen (defined by 2 points) as is most common for this type of selection, although other shapes of selection are possible too.

Back-Buffer: Using area selection with Back-Buffer selection is quite straight-forward. We have the 2 points that define the 2D rectangle, let's call them P1 (the upper-left) and P2 (lower-right.) All you have to have to do is loop through every pixel in the rectangle, and all the unique objects inside. You render the objects the same as with single-click back-buffer selection. nStartX, nStartY are the smallest valued coordinates of the corner of the selected rectangle, nEndX, nEndY are the largest valued corner.
Important note: OpenGL will usually default to padding reads of pixel rows to 4-byte alignment, so to avoid this with 3-byte RGB, you'll need this line glPixelStorei(GL_PACK_ALIGNMENT, 1);

   int nWidth = nEndX - nStartX;
   int nHeight= nEndY - nStartY;
   if (nWidth < 1) nWidth = 1;
   if (nHeight < 1) nHeight = 1;
   unsigned char *pRGB = new unsigned char [3 * (nWidth+1) * (nHeight + 1) + 3];
   
   glReadBuffer(GL_BACK);
   glReadPixels(nStartX, nStartY, nWidth, nHeight, GL_RGB, GL_UNSIGNED_BYTE, pRGB);

   int nLast = 0;
   int nEnd = nWidth * nHeight;
   for (i = 0; i < nEnd; i++)
   {
      int index = i*3;
      int ColorNumber = (pRGB[index]) + (pRGB[index+1]<<8) + (pRGB[index+2]<<16);
      if (ColorNumber > 0 && ColorNumber != nLast ) {
         World->SelectBackBufferObject ( ColorNumber );
         nLast = ColorNumber;
      }
   }

   delete[] pRGB;

Point in Frustum algorithm: Using area selection by using 3D planes is a bit more tricky, but should look very familiar to anyone who has done frustum culling, because once you have the planes, it's really the same thing. Frustum culling is used when you are rendering and don't want to render any points that wouldn't be visible (because they'd be off the edges of the rectangular viewing area.) For selection you can define a frustum based on the rectangle selected on the screen. You can calculate the 4 planes needed from the 2 screen-space points given (P1, P2). First we'll take the 2 points and calculate the 8 3D points of a frustum. Then we can use the crossproduct to calculate the normals of the four 3D planes that correspond to the four 2D screenspace lines of the selection rectangle. Once we have the normals, the always handy dot product can be used to test whether the points lie within the planes or not.
Note that you can use the point in frustum for a single click to make sure the closest point is within a certain screen distance of the point clicked on, as well as for area selecting all points within a selection rectangle. Another reason to sometimes use this type of area select instead of backbuffer is it will probably be faster (at least for a small number of points,) so this would be better if you want something like vertices in a selection rectangle to change color as the rectangle is being resized or as the viewport camera is rotated.

Example source code below. For the MouseLoc3D algorithm, see the first example source in Point Selection. The screen space selection rectangle is defined by the coordinates (X1,Y1)-(X2,Y2).

  int i, x;
  CVector3 P[8], Frustum[4];
  pWindows[ActiveView].MouseLoc3D( P[0], P[1], X1, Y1 );
  pWindows[ActiveView].MouseLoc3D( P[2], P[3], X1, Y2 );
  pWindows[ActiveView].MouseLoc3D( P[4], P[5], X2, Y2 );
  pWindows[ActiveView].MouseLoc3D( P[6], P[7], X2, Y1 );
  Frustum[0] = CrossProduct( P[0]-P[1], P[2]-P[3] );
  Frustum[1] = CrossProduct( P[2]-P[3], P[4]-P[5] );
  Frustum[2] = CrossProduct( P[4]-P[5], P[6]-P[7] );
  Frustum[3] = CrossProduct( P[6]-P[7], P[0]-P[1] );

  for (i = 0; i < 4; i++) Frustum[i].Normalize(); // this is unecessary

  // Check which points are within the Frustum formed by the selected square.
  for (i = 0; i < numPoints; i++)
  {
    for (x = 0; x < 4; x++)
    {
      float fDot = Dot( pPoints[i]-P[x*2], Frustum[x] );
      if ( fDot > 0) break;
    }
    if (x == 4) World->SelectPointObject( i );			
  }

I use all of the selection algorithms described here and more in the 3D Kingdoms Creator. I use point select to select vertices, or the joints on a skeleton or point-type objects like lights or cameras. I do this so the user doesn't have to click exactly on a point, it just selects the point closest to where you click. (If there are no points within a certain defined range of the cursor, it selects nothing.) Things like meshes use back buffer selection, meaning you select exactly what you click on (by-pixel.) When the user clicks on a view window or selects an area of it, I first try back-buffer selection, and if that is unsuccessful I then try point selection. In the back-buffer phase, I still render objects I use point selection for, so that for instance, if a light is in front of a mesh, the user can click on it exactly and it will be selected. I also keep track of which points were selected, so if the user clicks again in the same spot, and there are other points within the defined max range, it will cycle through them.

Appendix (3D Vector Class): This tutorial uses a 3D Vector Class. I think what the functions of the class do are probably clear from the context & names, and this will make the code easier to read. It uses C++ operator overloading to allow +,- or * between vectors, floats, and matrices. Of note is that V3.Normalize(), normalizes V3 instead of returning a 3d vector. I would recommend 3d vector and matrix classes so you can write code like you'd write a mathematical formula, usually reducing the number of lines of code in the process. There are probably places online to download code for a 3D vector class, but since they're quick and simple to write, I wrote my own. I find this leaves me familiar with exactly how it works and where to add new functions for only a tiny bit of extra coding time. See my article 3D Vectors for an example of a vector class.

Appendix (Line Intersects with triangle test):

Note: This is not the fastest possible way to do this, but rather written to be general purpose and (maybe?) simpler. But before we worry about the speed of this code, I should note that in a line to mesh collision test, we should first have a very quick initial test against a bounding box, and only if it passes check the line against all the triangles of the mesh. Having your mesh subdivided into chunks each with their own bounding box can add a second level of quick tests.

//
// Check for an intersection (HitPos) between a line(LP1,LP2) and a triangle face (TP1, TP2, TP3)
//
bool CheckLineTri( CVector3 TP1, CVector3 TP2, CVector3 TP3, CVector3 LP1, CVector3 LP2, CVector3 &HitPos)
  {
   CVector3 Normal, IntersectPos;

   // Find Triangle Normal
   Normal = CrossProduct( TP2 - TP1, TP3 - TP1 );
   Normal.Normalize(); // not really needed

   // Find distance from LP1 and LP2 to the plane defined by the triangle
   float Dist1 = (LP1-TP1).Dot( Normal );
   float Dist2 = (LP2-TP1).Dot( Normal );
   if ( (Dist1 * Dist2) >= 0.0f) return false;  // line doesn't cross the triangle.
   if ( Dist1 == Dist2) return false;// line and plane are parallel

   // Find point on the line that intersects with the plane
   IntersectPos = LP1 + (LP2-LP1) * ( -Dist1/(Dist2-Dist1) );

   // Find if the interesection point lies inside the triangle by testing it against all edges
   CVector3 vTest;
   vTest = CrossProduct( Normal, TP2-TP1 );
   if ( Dot( vTest, IntersectPos-TP1) < 0.0f ) return false;
   vTest = CrossProduct( Normal, TP3-TP2 );
   if ( Dot( vTest, IntersectPos-TP2) < 0.0f ) return false;
   vTest = CrossProduct( Normal, TP1-TP3 );
   if ( Dot( vTest, IntersectPos-TP1) < 0.0f ) return false;

   HitPos = IntersectPos;
   return true;
   }