Object selection lasso

From GPWiki

In many (RTS) games involving units you will find this nice feature that allows you to select object by drawing a "lasso" or "box" around them. I will post some code here to do just that, and explain the technique a bit. Note that most of the code is C++, but many of the functions can be used in Visual Basic DirectX too.

In my application I got all kinds of selection methods:

• Using rays
• Using the stencil buffer

These work fine, for selecting one unit. The last method is pixel perfect. But when selecting an entire box you will need an enormous amount of rays, or pixels to check. So, we are going to build a selection frustum and check what is inside!

What you need:

• Objects which have a bounding box, which is transformed to object space
• A box. I assume you can make a box yourself.
• Project, View matrices available.

Object space is just the transformation which you are using to render the object, normally. Simply keep a copy of it when rendering.

The box is very simple: Two pairs of mouse (x,y) coordinates. When the mousedown is pressed, store the current position, and during mouse moves simply update the second pair of coordinates. When the mouse button goes up, you call the box selection function.

The code is of course, optimized for my game, but I think things are pretty simple to understand.

void CMouse::DoLassoSelection()
    	{
  		//Select objects using the drawn lasso
  		//First we have to transform the box to worldspace coordinates
  		//This way ,we can simply do intersect tests of the unit bounding boxes
  
  		D3DXVECTOR3 vTopLeftNear, vBottomRightNear;
  		D3DXVECTOR3 vTopLeftFar, vBottomRightFar;
  		D3DXVECTOR3 v1, v2, v3, v4;
  		D3DVIEWPORT8 vp;
  		
  		D3DXMATRIX matView		= objCamera.GetViewMatrix();
  		D3DXMATRIX matProject   = objCamera.GetProjectionMatrix();
  		D3DXMATRIX matWorld     = matIdentity;
  
 		mp_d3d_device->GetViewport( &vp ); // Viewport structure
  
  		//First determine how the player did the lasso move, top-left->bottom-right? or else?
  		
  		//Swap values as needed. v1 should ALWAYS be topleft
  		if (m_vRectanglePosition[1].x < m_vRectanglePosition[0].x) swap<float>(m_vRectanglePosition[0].x,
  m_vRectanglePosition[1].x);
  		if (m_vRectanglePosition[1].y < m_vRectanglePosition[0].y) swap<float>(m_vRectanglePosition[0].y,
  m_vRectanglePosition[1].y);
  
  		//Get top-left / bottom-right from NEAR plane:
  		v1.x = m_vRectanglePosition[0].x;
  		v1.y = m_vRectanglePosition[0].y;
  		v1.z = 0.0f;
  		
  		v2.x = m_vRectanglePosition[1].x;
  		v2.y = m_vRectanglePosition[1].y;
  		v2.z = 0.0f;
  
  		//Get top-left / bottom-right from FAR plane:
  		v3.x = m_vRectanglePosition[0].x;
  		v3.y = m_vRectanglePosition[0].y;
  		v3.z = 1.0f;
  		v4.x = m_vRectanglePosition[1].x;
  		v4.y = m_vRectanglePosition[1].y;
  		v4.z = 1.0f;
  
  		// Inverse projection (screen to 3D) 
  		D3DXVec3Unproject( &vTopLeftNear,	  &v1, &vp, &matProject, &matView, &matWorld ); 
  		D3DXVec3Unproject( &vBottomRightNear, &v2, &vp, &matProject, &matView, &matWorld ); 
  
  		D3DXVec3Unproject( &vTopLeftFar,	  &v3, &vp, &matProject, &matView, &matWorld ); 
  		D3DXVec3Unproject( &vBottomRightFar,  &v4, &vp, &matProject, &matView, &matWorld ); 
  		
  		//Top left
  		BoxLineList[0].x = vTopLeftNear.x;
  		BoxLineList[0].y = vTopLeftNear.y;
  		BoxLineList[0].z = vTopLeftNear.z;
  		BoxLineList[0].colour = D3DCOLOR_ARGB(255,255,0,0);
  		BoxLineList[1].x = vTopLeftFar.x;
  		BoxLineList[1].y = vTopLeftFar.y;
  		BoxLineList[1].z = vTopLeftFar.z;
  		BoxLineList[1].colour = D3DCOLOR_ARGB(255,255,0,0) ;
  
  		//Bottom right
  		BoxLineList[2].x = vBottomRightNear.x;
  		BoxLineList[2].y = vBottomRightNear.y;
  		BoxLineList[2].z = vBottomRightNear.z;
  		BoxLineList[2].colour = D3DCOLOR_ARGB(255,0,255,0);
  		BoxLineList[3].x = vBottomRightFar.x;
  		BoxLineList[3].y = vBottomRightFar.y;
  		BoxLineList[3].z = vBottomRightFar.z;
  		BoxLineList[3].colour = D3DCOLOR_ARGB(255,0,255,0);
  
  		//Bottom left
  		BoxLineList[6].x = vTopLeftNear.x;
  		BoxLineList[6].y = vBottomRightNear.y;
  		BoxLineList[6].z = vTopLeftNear.z;
  		BoxLineList[6].colour = D3DCOLOR_ARGB(255,0,0,255);
  		BoxLineList[7].x = vTopLeftFar.x;
  		BoxLineList[7].y = vBottomRightFar.y;
  		BoxLineList[7].z = vTopLeftFar.z;
  		BoxLineList[7].colour = D3DCOLOR_ARGB(255,0,0,255);
  		
  		//Top right
  		BoxLineList[4].x = vBottomRightNear.x;
  		BoxLineList[4].y = vTopLeftNear.y;
  		BoxLineList[4].z = vBottomRightNear.z;
  		BoxLineList[4].colour = D3DCOLOR_ARGB(255,0,255,255);
  		BoxLineList[5].x = vBottomRightFar.x;
  		BoxLineList[5].y = vTopLeftFar.y;
  		BoxLineList[5].z = vBottomRightFar.z;
  		BoxLineList[5].colour = D3DCOLOR_ARGB(255,0,255,255);
  
  		//Create our clipping planes:
  		D3DXPLANE	ClippingPlanes[6];
  
  		D3DXVECTOR3 vLeftBottomFar  (vTopLeftFar.x, vBottomRightFar.y,vTopLeftFar.z);
  		D3DXVECTOR3 vLeftBottomNear (vTopLeftNear.x,	 vBottomRightNear.y,vTopLeftNear.z);
  		D3DXVECTOR3 vRightTopNear	(vBottomRightNear.x, vTopLeftNear.y,vBottomRightNear.z);
  		D3DXVECTOR3 vRightTopFar	(vBottomRightFar.x,  vTopLeftFar.y,vBottomRightFar.z);
  		
  		//Left plane:
  		D3DXPlaneFromPoints(&ClippingPlanes[0], &vLeftBottomFar,  &vTopLeftFar,     &vTopLeftNear);
  		
  		//Right plane:
  		D3DXPlaneFromPoints(&ClippingPlanes[1], &vRightTopNear,   &vRightTopFar,    &vBottomRightNear);
  		
  		//Top plane:
  		D3DXPlaneFromPoints(&ClippingPlanes[3], &vTopLeftNear,	  &vRightTopFar,    &vRightTopNear);
  
  		//Bottom plane:
  		D3DXPlaneFromPoints(&ClippingPlanes[2], &vBottomRightFar, &vLeftBottomFar,  &vBottomRightNear);
  
  		//Near clip plane:
  		D3DXPlaneFromPoints(&ClippingPlanes[4], &vTopLeftNear,	  &vRightTopNear,   &vBottomRightNear);
  
  		//Far clip plane:
  		D3DXPlaneFromPoints(&ClippingPlanes[5], &vRightTopFar,	  &vTopLeftFar,     &vBottomRightFar);
  		
  		bRenderbox = true;
  
  		//D3DXP
  		bool retVal;
  		CEBoundingBox* box;
  		
  		//Loop through all objects:
  		for (unsigned int i = 0; i < m_EObjects.size(); i++)
  		{
  			retVal = true;
  			box = m_EObjects[i]->BoundingBox;
  			
  			//Loop through all plans:
  			for (int p = 0; p < 6; p++)
  			{
  
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[0]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[1]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[2]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[3]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[4]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[5]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[6]) > 0.0f) continue;
  				if (D3DXPlaneDotCoord(&ClippingPlanes[p], &box->mod_point[7]) > 0.0f) continue;
  
  				//if ((ClippingPlanes[p].a * box->mod_point[0].x + ClippingPlanes[p].b 
  * box->mod_point[0].y + ClippingPlanes[p].c * box->mod_point[0].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[1].x + ClippingPlanes[p].b
  * box->mod_point[1].y + ClippingPlanes[p].c * box->mod_point[1].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[2].x + ClippingPlanes[p].b 
  * box->mod_point[2].y + ClippingPlanes[p].c * box->mod_point[2].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[3].x + ClippingPlanes[p].b
  * box->mod_point[3].y + ClippingPlanes[p].c * box->mod_point[3].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[4].x + ClippingPlanes[p].b 
  * box->mod_point[4].y + ClippingPlanes[p].c * box->mod_point[4].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[5].x + ClippingPlanes[p].b 
  * box->mod_point[5].y + ClippingPlanes[p].c * box->mod_point[5].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[6].x + ClippingPlanes[p].b 
  * box->mod_point[6].y + ClippingPlanes[p].c * box->mod_point[6].z + ClippingPlanes[p].d) > 0) continue;
  				//if ((ClippingPlanes[p].a * box->mod_point[7].x + ClippingPlanes[p].b 
  * box->mod_point[7].y + ClippingPlanes[p].c * box->mod_point[7].z + ClippingPlanes[p].d) > 0) continue;
  				//If we are still here, something was outside the frustum...
  				retVal = false;
  			}
  		
  			m_EObjects[i]->bSelected = retVal;
  		
  		}
  
  	}

Okay, that's quite some code! Some of it is also for debugging purposes.

//Swap values as needed. v1 should ALWAYS be topleft
  		if (m_vRectanglePosition[1].x < m_vRectanglePosition[0].x) swap<float>(m_vRectanglePosition[0].x,
  m_vRectanglePosition[1].x);
  		if (m_vRectanglePosition[1].y < m_vRectanglePosition[0].y) swap<float>(m_vRectanglePosition[0].y,
  m_vRectanglePosition[1].y);
  
  		//Get top-left / bottom-right from NEAR plane:
  		v1.x = m_vRectanglePosition[0].x;
  		v1.y = m_vRectanglePosition[0].y;
  		v1.z = 0.0f;
  		
  		v2.x = m_vRectanglePosition[1].x;
  		v2.y = m_vRectanglePosition[1].y;
  		v2.z = 0.0f;
  
  		//Get top-left / bottom-right from FAR plane:
  		v3.x = m_vRectanglePosition[0].x;
  		v3.y = m_vRectanglePosition[0].y;
  		v3.z = 1.0f;
  		v4.x = m_vRectanglePosition[1].x;
  		v4.y = m_vRectanglePosition[1].y;
  		v4.z = 1.0f;

This code will simply put the mouse coordinates in four D3DXVECTOR3's. We need 4 because we have a top-left and bottom-right coordinates. We want these two positions for the NEAR clipping plane of the camera, and the FAR clipping plane. Specifying z will do this for us. z = 1.0f; is the far clipping plane.

Now we have to transform these coordinates to 3D. Right now they are still in 2D (screen space). We will do this with the DirectX Unproject functions:

// Inverse projection (screen to 3D) 
  		D3DXVec3Unproject( &vTopLeftNear,	  &v1, &vp, &matProject, &matView, &matWorld ); 
  		D3DXVec3Unproject( &vBottomRightNear, &v2, &vp, &matProject, &matView, &matWorld ); 
  
  		D3DXVec3Unproject( &vTopLeftFar,	  &v3, &vp, &matProject, &matView, &matWorld ); 
  		D3DXVec3Unproject( &vBottomRightFar,  &v4, &vp, &matProject, &matView, &matWorld );

These simply take the viewport, the projection+view matrix, and a world matrix. Look at the variable names. Now we have 4 sets of coordinates, defining our "selection frustum". Anything that is partially inside this frustum gets selected, eventually. This frustum is very similar to the standard viewing frustum.

The code that follows the above code is just for rendering purposes. I'd like to see how the frustum looks like. It's simply creating a line list. If you want to use this too, create a line vertexarray of 8, and use the following code to render it:

void CMouse::RenderBoxFrustum()
    {
     	if (bRenderbox == true) {
    		mp_d3d_device->SetVertexShader(D3DFVF_LINEVERTEX);
    		mp_d3d_device->SetTransform(D3DTS_WORLD, &matIdentity);
    		mp_d3d_device->DrawPrimitiveUP(D3DPT_LINELIST,4,&BoxLineList[0],sizeof(BoxLineList[0]));
    	}
    }

If you don't want to render the frustum, simply remove all that code that generates the line list. But I recommend you to render it first, just to make sure your code works.

After this linelist code, we start making D3DXPlanes. This is a crucial part. We are going to make planes from all the 6 sides of our frustum. Then we can check if something is inside it or not, using a Dot product. It looks quite like normal frustum culling for geometry, doesn't it?

D3DXPlaneFromPoints creates a D3DXPlane from 3 vectors. I think the code is pretty self explainable. Just make sure you pass the right coordinates :-). The code above should be fine. Googleing on "D3DXPlaneFromPoints" will return many results for creating a box from all kinds of points, if you really need it.

We got 6 clipping planes now. Left, right, top, bottom, near and far. Any object which bounding box intersects between one of these points should be selected. If needed you could modify the code that all points of a bounding box should be inside the frustum, to select a unit.

We loop through all 6 planes and check if the Dot product is bigger than 0. This means it's inside it. We have to do this for all 8 points of the bounding box. Note that I’m using object space here! Hence the mod_ prefix. The object space includes all the rotations of the object, and is quite trivial.

As you can see, I have two ways of doing this check: Using the DirectX function, or the commented code. Both perform the same function, it's just for showing what actually happens.

If one of the checks pass, then at least one point of the object is inside the frustum, thus the object should be selected. If no points match, it will return false and does not select the object.

I've just got this function to work, eventually I guess it might be better if you make the code work as a function, instead of doing the selection direction in the function.