Ghoscher's Blog

Introduction:

Hello & welcome to the second picking tutorial!
1- Ray picking.
2- RTS style selection box (two approaches).
3- Projection and why you need it.

In part I, I talked about picking single objects, In many cases such as RTS games that’s not enough…

You’ll need to select multiple units together using some sort of a rectangle or selection box that you make by clicking and dragging with your mouse.

Two approaches I know:
1- Unprojecting your selection box and check for collisions in 3D world space.
2- Projecting your 3D objects and perform simple 2D rectangle collision detection.

First approach, Unprojecting a rectangle ( A little tricky ) :

If you unproject a point the result should be a ray ( Part I discussed this issue in some detail) , If you unproject a rectangle the result depends on your projection matrix, We’ll assume it’s a perspective projection matrix, so the result of unprojecting a rectangle is a frustum (BoundingFrustum in XNA), in most cases this BoundingFrustum is not a scaled version of the view frustum, it’s some sort of irregular frustum, images are better than words:

Click on image to see full size

Now how do we get this frustum? what I really wanted to do is to unproject each corner of the selection rectangle twice and get 8 3D points which are exactly the 8 corners of the BoundingFrustum we want, but unfortunately BoundingFrustum doesn’t have a function like SetCorners(Vector3[] corners) 😦 …

I searched a lot about creating a custom BoundingFrustum and I came across this thread.
To be honest I don’t fully understand how it works but it does! I will update the post as soon as I get it right, if you do please kindly tell me and I’ll really appreciate it :D.

The bounding frustum is defined by two matrices, projection matrix which determines the shape of the frustum and the view matrix that determines the orientation of the frustum in the 3D world… For the view matrix we can just use the same view matrix of the camera we’re using to render the scene, the projection matrix is the tricky part, we take the projection matrix from the camera and modify some of its elements to give us the frustum we want…

Here’s the code from that thread wrapped in a function:

BoundingFrustum UnprojectRectangle(Rectangle source, Viewport viewport, Matrix projection, Matrix view)
{
    //http://forums.create.msdn.com/forums/p/6690/35401.aspx , by "The Friggm"
    // Many many thanks to him...

    // Point in screen space of the center of the region selected
    Vector2 regionCenterScreen = new Vector2(source.Center.X, source.Center.Y);

    // Generate the projection matrix for the screen region
    Matrix regionProjMatrix = projection;

    // Calculate the region dimensions in the projection matrix. M11 is inverse of width, M22 is inverse of height.
    regionProjMatrix.M11 /= ((float)source.Width / (float)viewport.Width);
    regionProjMatrix.M22 /= ((float)source.Height / (float)viewport.Height);

    // Calculate the region center in the projection matrix. M31 is horizonatal center.
    regionProjMatrix.M31 = (regionCenterScreen.X - (viewport.Width / 2f)) / ((float)source.Width / 2f);

    // M32 is vertical center. Notice that the screen has low Y on top, projection has low Y on bottom.
    regionProjMatrix.M32 = -(regionCenterScreen.Y - (viewport.Height / 2f)) / ((float)source.Height / 2f);

    return new BoundingFrustum(view * regionProjMatrix);
}

Again my apologies for not explaining :(.

Notes on the code above:
1- Please note that selectionRect is our selection rectangle and it’s relative to it’s viewport, this means that the upper left corner of the viewport is considered as the origin for the rectangle…
2- After we get the new projection matrix, we create a BoundingFrustum using the matrix camera.View*regionProjMatrix

Now that we have the correct bounding frustum we can check for collisions AND containment against this frustum, here’s a sample function for that (can be found inside my DrawableObject class):

public bool CheckFrustumIntersection(BoundingFrustum boundingFrustum)
{
    BoundingSphere boundingSphere;

    foreach (ModelMesh mesh in model.Meshes)
    {
        boundingSphere = mesh.BoundingSphere.Transform(modelTransforms[mesh.ParentBone.Index] * GetWorld());
        ContainmentType con =boundingFrustum.Contains(boundingSphere);
        if (con == ContainmentType.Contains || con == ContainmentType.Intersects ) return true;
    }
    return false;
}

Second approach, Projecting game objects ( A LOT easier ) :

A quick ( but not accurate ) definition of projecting is to remove a dimension, so projecting a 3D point with x,y and z components into a plane results in a 2D point with only x any components…

Remember when we used a ray to pick single objects? well… we could have done it in another way : project all your visible 3D objects to 2D circles and check if the mouse cursor is in side these circles.
What we’ll do here is projecting 3D objects to 2D points and do a simple check on each point to know whether it’s inside the selection rectangle or not…

To project a 3D position represented by a Vector3 we use the function

public Vector3 Project(Vector3 source, Matrix projection, Matrix view, Matrix world)

pretty much similar to the Viewport.Unproject
view, projection are the same matrices used to define the camera, set world matrix to Matrix.Identity , source is the position of your object in world space.
As you might have noticed, the Project function returns a Vector3 but you only need the x & y components of this vector.

So here’s a function that will do the work 🙂

List<DrawableObject> RectangleSelect(List<DrawableObject> objectsList, Viewport viewport, Matrix projection, Matrix view, Rectangle selectionRect)
{
    // Create a new list to return it
    List<DrawableObject> selectedObj = new List<DrawablrObject>();

    foreach (DrawableObject o in objectsList)
    {
        // Getting the 2D position of the object
        Vector3 screenPos = viewport.Project(o.Position, projection, view, Matrix.Identity);

        // screenPos is window relative, we change it to be viewport relative
        screenPos.X -= viewport.X;
        screenPos.Y -= viewport.Y;

        if (selectionRect.Contains((int)screenPos.X, (int)screenPos.Y))
        {
            // Add object to selected objects list
            selectedObj.Add(o);
        }
    }

    return selectedObj;
}

Notes on the code above:
1- DrawableObject is a simple class that wraps the basic functions needed to manipulate 3D objects.
2- We subtracted the offset from the viewport because the Viewport.Project method will return the position relative to the game window not the provided viewport, while our selection rectangle values (in this sample) are relative to the viewport, we wouldn’t run into this if our selection rectangle is window relative, this image shows the issue

Click on image to see full size

So which method should I use?
Well.. I’ve seen recommendations to go with the second approach ( the easy one 😉 )..
You might wonder why did I mention the first method in the first place? Actually when I first wanted to pick objects using a selection box the first thing that came to my mind is unprojecting a rectangle, but I couldn’t get it to work, then I came across the projecting method…Anyway it’s good to know them both :D.

Some notes for performance:
1- In both methods make sure you only check objects that are inside the camera frustum, you’re not actually gonna pick objects that you cannot see are you ???!?!? 😉
2- In the first method you could just create one BoundingFrustum instance and modify the function UnprojectRectangle to just return a matrix and then set the returned matrix to the property Matrix of that frustum instance… That’s better than creating a new BoundingFrustum each frame.

The ray picking sample is updated!

Now you can select single objects by clicking on them or select multiple objects by clicking and dragging, I also added a class BoundingFrustumRenderer, most of the code is taken from the VisualCamera class, I know that’s not how professionals would do it but I’m willing to set things right when I write my custom game library ;).
Here’s a screen shot that shows the BoundingFrustum resulted from unprojecting the selection rectangle:

Click on image to see full size

Another screen shot from inside the selection frustum:

Click on image to see full size

Here’s both source code & exe for the sample  ( VS2010 + XNA4) 😀

XNA Picking Sample Bin (39KB)

XNA Picking Sample Source (61KB)

Wow! That was too long.. I wonder who is patient enough to read such an article 🙂
The next article ( Part III ) should be short I guess, it will show another use of the method Viewport.Project.
See you there :).