This is a quick post which will discuss picking. Picking is the process of figuring out what object was clicked on in a 3D scene. There are a number of ways of doing this, each with their own pros and cons.

Color Keys

The first method of picking is using color keys. Basically, every 3D object in the scene is assigned a unique color. When rendering the scene, a pass is done where each object just outputs this color. This creates a render of the scene with a bunch of flat shapes in the shape of the objects themselves. Then, the pixel from the point where the mouse (or whatever else, ie a targting reticle) is positioned in 2D space. The color that the pixel contains will match up with an object in the scene, which tells us which object was clicked on.

The benefit here is that the picking will be “pixel perfect”, meaning that it can tell exactly what object was clicked on on with pixel accuracy. This is much more accurate than other methods, and is also somewhat cheap if the object is already being drawn anyway. Plus, if any techniques that modify the geometry in the shader are being employed, like bump mapping, we will be able to include that in the picking as well.

However, there are some downsides. First, if an object becomes smaller than one pixel, we won’t be able to distinguish it from other objects near it, because we can only get to a pixel accuracy. Secondly, if we are trying to figure out what objects are contained in an area (like when a box select is dragged across the screen) we have to sample more points, which can be very expensive on some computers. Finally, we can only get the top level of objects, because we can only put one color in each pixel. This means that if an object is behind another one, we won’t know it because we only saved the color of the object in front of it. This makes multiple-selections difficult, because we will get the front level of objects but not the objects behind them.

I wrote a sample demonstrated this technique and it is available on Ziggyware.com:

http://www.ziggyware.com/readarticle.php?article_id=203

Polygon Picking

The second method of picking is polygon picking. The idea here is to create a ray that starts from the mouse’s position in 3D space, and extends infinitely far away (in theory- we can’t actually do this in practice, because we can’t work with infinite numbers. We can get close enough that it doesn’t matter though). We then take the ray and check it against the polygons in the objects in the scene. If one of them intersects with the ray, we know that the object is under the mouse cursor, so we add it to a list and move on to the next one. Once we have checked all the objects, we look at the list and choose the closest object.

Figuring out where the cursor is in 3D space is easy using the Viewport.Unproject() method. It takes a Vector3 for the mouse coordinates in screen space. X and Y are the X and Y position of the mouse in 2D space, and Z is the distance from the “screen”. So, to get our two points, we would create a Vector3 that represents the cursor right on the screen, and another that represents the cursor infinitely far away fromt the screen. These should be (X Pos, Y Pos, 0) and (X Pos, Y Pos, 1) respectively. However, since we can’t actually use infinite numbers, the latter’s Z coord should really be something like .99f.

Polygon picking is more accute than color keys because it is not limted by the number of pixels in the image. At the same time, as long as no geometry modifying rendering techniques are being used, it is pretty much pixel perfect. It also allows for multiple objects to be layered and still be found.

The downside is that polygon picking is very expensive. Checking a ray against every polygon in every object gets really sluggish really quickly.

There is another Ziggyware sample that demonstrates how to actually pick against the polygons here:

http://www.ziggyware.com/readarticle.php?article_id=103

Bounding Volumes

By far the most efficient method of picking, Bounding Volumes approximate the shape of the geometry instead of checking against the geometry itself. The shapes used most often are boxes and spheres. Checking if a ray intersects a box or sphere is much, much faster than checking against thousands of polygons. Usually a number of bounding volumes are used in a model, to make the picking more accurate while still keeping the picking efficient.

The only downside here is that this method is not pixel perfect. However, if you think about it, you don’t usually need picking to be pixel perfect anyway. Checking against a box, sphere, or capsule is usually all you really need.

XNA provides a number of bounding volumes that already contain methods to figure out if they are intersection with eachother. These types are BoundingBox, BoundingSphere, BoundingFrustum, Plane, and Ray. The Intersects() method on all of these objects will tell you if they contain or overlap with another object you choose to test against.

The final section of this post contains the code to implement bounding volume picking both generically and specifically for our engine.

A Combined Approach

If you really need to be pixel perfect in a certain situation, consider taking a combined approach. Having a combined approach will allow you to be pixel perfect some of the time, and approxiamte the rest of the time. For example, if you are making a game with a bunch of enemies, the player is probably not going to notice that they can still hit the enemy if they shoot a few pixels away from the side of the head. Then later on if, for example, you need to be very accurate because the player is zoomed all the way in with a sniper scope, then you could switch to a color key system.

This would be much more feasible, because you are only sampling the pixel where the dot in the scope is, and you only need to do it when the player pulls the trigger. You don’t need to worry about the limitations here, because the objects you are looking for will probably be larger than one pixel and you don’t need to worry about what is behind them. (Unless you want to be able to shoot through certain materials, in which case you would probably want to be checking against polygons instead). You also probably wouldn’t need to worry about the overhead of drawing the color key pass because you would only need to draw the objects in view of the scope, which shouldn’t be too many since the field of view is generally much smaller and the rest of the objects probably have some kind of scope texture over them anyway.

Optimizations

Even with the bounding volume approximations, if enough objects are in the scene the game will slow down significantly because of all the checks it’s doing. Luckily, we can cut down on the number of objects we are checking. We probably won’t need to check against most of the objects in the scene if we apply a few optimization techniques. The most common and likely to help are QuadTrees, OctTrees, Binary Space Partitioning (BSP), Occlusion Culling, and View Frustum culling.

Implementing Bounding Volume Approximation

Actually implementing bounding bolume approximation is very simple. First we find the two points that make up our picking line: the mouse’s screen position in 3D space to the “infinitely” far away point that corresponds with it. Then we make a ray using the first point and the direction to the next one. We then use this to check against the BoundingBoxes for each model. The BoundingBoxes can be calculated by combining the spheres provided by each ModelMesh in the model, or by going throug every vertex in the model in the content processor and checking if they are lower than the minimum point or higher than the maximum. If they are, the minimum or maximum points are moved to the position of the vertex. Those two points then become the corners of the BoundingBox. This is best done in the content processor, to avoid having to do it more than once.

The following shows how to do this with a list of bounding boxes:

public BoundingBox Pick (int X, int Y, out float Dist, List<BoundingBox> Check, Matrix View, Matrix Projection)
{
    Vector3 nearSource = new Vector3((float)X, (float)Y, 0);
    Vector3 farSource = new Vector3((float)X, (float)Y, .99f);

    Vector3 nearPoint = Engine.GraphicsDevice.Viewport.Unproject(nearSource, Projection, View, Matrix.CreateTranslation(0, 0, 0));
    Vector3 farPoint = Engine.GraphicsDevice.Viewport.Unproject(farSource, Projection, View, Matrix.CreateTranslation(0, 0, 0));

    Vector3 direction = farPoint - nearPoint;
    direction.Normalize();

    Ray ray = new Ray(nearPoint, direction);

    BoundingBox closest = null;
    float? closestDist = float.MaxValue;

    foreach (BoundingBox box in check)
    {
         float? dist;
         ray.Intersects(ref box, out dist);

         if (dist != null)
            if (dist.Value < closestDist)
            {
                    closestDist = dist;
                    closest = box;
            }
     }

    Dist = (closestDist != null ? closestDist.Value : 0);
    return closest;
}

This next block of code shows how this can be implemented in the engine:

public Component Pick (int X, int Y, out float Dist)
{
    Vector3 nearSource = new Vector3((float)X, (float)Y, 0);
    Vector3 farSource = new Vector3((float)X, (float)Y, .99f);

    Vector3 nearPoint = Engine.GraphicsDevice.Viewport.Unproject(nearSource, Camera.Projection, Camera.View, Matrix.CreateTranslation(0, 0, 0));
    Vector3 farPoint = Engine.GraphicsDevice.Viewport.Unproject(farSource, Camera.Projection, Camera.View, Matrix.CreateTranslation(0, 0, 0));

    Vector3 direction = farPoint - nearPoint;
    direction.Normalize();

    Ray ray = new Ray(nearPoint, direction);

    Component closest = null;
    float? closestDist = float.MaxValue;

    foreach (GameScreen screen in Engine.GameScreens)
        foreach (Component component in screen.Components)
            if (component is I3DComponent)
            {
                BoundingBox bbox = ((I3DComponent)component).BoundingBox;

                float? dist;
                ray.Intersects(ref bbox, out dist);

                if (dist != null && component != Camera && component != Grid)
                    if (dist.Value < closestDist)
                    {
                        closestDist = dist;
                        closest = component;
                    }
            }

    Dist = (closestDist != null ? closestDist.Value : 0);
    return closest;
}

One note: The BoundingBoxes returned by the components should be offset to the components position. This can be done by returning a BoundingBox whose corners are the original’s corners plus the position of the component.

« »