Weird block selector selection (to floor or not to floor)?

Question

Well, I am creating a Minecraft like engine in XNA, and since I first implemented the block selector (the cube that allows you to select blocks in 3D space) it has always been very inaccurate. Here is what I mean:

And here is the code that does the selecting (note that I have tryed to ceil then floor the vectors but none correct the abnormal positioning of it):

private Block GetSelectedBlock()
{
    Block block = new Block();
    block.BlockType = BlockType.none;

    for (float x = Variables.SELECTION_MIN; x < Variables.SELECTION_MAX; x += 0.1f)
    {
        Vector3 targetPoint = camera.Position + (camera.LookVector * x);
        //targetPoint = Util.FloorVector3(targetPoint);
        //targetPoint = Util.CeilVector3(targetPoint);

        blockSelector.UpdatePosition(new Vector3((int)targetPoint.X, (int)targetPoint.Y, (int)targetPoint.Z));
        block = world.GetBlock((int)targetPoint.X, (int)targetPoint.Y, (int)targetPoint.Z);

        if (block.BlockType != BlockType.none)
        {
            blockSelector.Visible = true;
            break;
        }

        blockSelector.Visible = false;
    }

    return block;
}

Also the two following screen shots show where the block selection cube is placed when I do call the blockSelector.UpdatePosition() function but do not cast the values to integers:

Any ideas what I am doing incorrectly?

Also regarding Blecki's answer here is what I implemented based on his idea:

       private Block GetSelectedBlock()
    {
        Block block = new Block();
        block.BlockType = BlockType.none;

        for (float x = Variables.SELECTION_MIN; x < Variables.SELECTION_MAX; x += 0.1f)
        {
            Vector3 targetPoint = camera.Position + (camera.LookVector * x) + new Vector3(0.5f, 0.5f, 0.5f);
            targetPoint = Util.FloorVector3(targetPoint);

            blockSelector.UpdatePosition(new Vector3((int)targetPoint.X, (int)targetPoint.Y, (int)targetPoint.Z));
            block = world.GetBlock((int)targetPoint.X, (int)targetPoint.Y, (int)targetPoint.Z);

            if (block.BlockType != BlockType.none)
            {
                blockSelector.Visible = true;
                break;
            }

            blockSelector.Visible = false;
        }

        return block;
    }

It seems to allow you to place blocks alot more accurately but it is still off centre:

Answer 1

There's a better and simpler way to find the closest block under the 'mouse'. XNA provides a ray and an AABB type, and the function Ray.Intersects. Intersects returns the distance to the intersection or null, if there was none. You can test the blocks that may be under the 'mouse/reticle' and pick whichever block is closest. Obviously, checking every block would be terribly in-efficient. You can use a simple tree of bounding boxes to narrow the search down to individual blocks.

Here is some code I ripped out a project of mine that does exactly this. In this example, imagine that 'prism' represents a rectangular prism of blocks, and Prism.Split splits the prism on it's longest axis, unless it's smaller than a threshold, in which case it returns false.

    public static void rayTraversal(
        Prism prism,
        Ray ray,
        Action<Coordinate> func)
    {
        Prism? A, B;
        if (!prism.Split(out A, out B))
            _raySubRegion(A.Value, ray, func);
        else
        {
            var ADistance = ray.Intersects(GetPrismAABB(A.Value));
            if (ADistance.HasValue)
                rayTraversal(A.Value, ray, func);
            var BDistance = ray.Intersects(GetPrismAABB(B.Value));
            if (BDistance.HasValue)
                rayTraversal(B.Value, ray, func);
        }
    }

    private static void _raySubRegion(Prism prism, Ray ray, Action<Coordinate> func)
    {
        for (short _x = prism.X; _x < prism.X + prism.Width; ++_x)
            for (short _y = prism.Y; _y < prism.Y + prism.Height; ++_y)
                for (short _z = prism.Z; _z < prism.Z + prism.Depth; ++_z)
                {
                    var Box = GetTileAABB(new Coordinate(_x, _y, _z));
                    if (ray.Intersects(Box).HasValue)
                        func(new Coordinate(_x, _y, _z));
                }
    }

This will call the action passed in for every block coordinate that intersects the ray. You should be able to figure out how to make it choose the block closest to the camera.

Another solution is to use a raycasting algorithm, but I'll let someone else write that one up.

Answer 2

Your current method is never going to work 100% of the time, because you're stepping in increments that could occasionally miss the edges of blocks.

You should probably be using a form of raycasting. Because you're creating a Minecraft clone that means all of your blocks are axis-aligned boxes, which makes it extremely easy to determine which blocks are lie along a line in front of the camera.

Viewport viewPort = game.GraphicsDevice.Viewport;

// ===================================================
// If you want to use the mouse, use this code
MouseState state = Mouse.GetState();
Vector2 screenPos = new Vector2(state.X, state.Y);
// ===================================================

// ===================================================
// If you want to use a reticule centered at the middle of the screen, use this code
Vector2 screenPos = new Vector2(viewPort.X + Math.Floor(viewPort.Width * 0.5f),
                                viewPort.Y + Math.Floor(viewPort.Height * 0.5f))
// ===================================================

// Create two positions in screenspace using the cursor position. 0 is as
// close as possible to the camera, 1 is as far away as possible.
Vector3 nearSource = new Vector3(screenPos, 0f);
Vector3 farSource = new Vector3(screenPos, 1f);    

Vector3 start = viewPort.Unproject(nearSource, projectionMatrix, viewMatrix, Matrix.Identity);
Vector3 end = viewPort.Unproject(farSource, projectionMatrix, viewMatrix, Matrix.Identity);

This gives you a line segment with which to check boxes against, and it should work with any XNA-based game. And if you planned things well then your boxes are exactly 1x1x1, which makes it very easy to know which block areas the line goes through. You would write an algorithm to check each of those areas, in order from nearest to the camera, to furthest, and as soon as a block is found then you're done.

One optimization you should make would be to shorten the line segment to only be as long as you want players to be able to click on blocks.

Vector3 shortenedEndPoint = start + ((end - start).Normalize() * 20.0f)

The above code would take the endpoints we calculated earlier and give you a new endpoint that is only 20 units away from the camera. By shortening it the amount of block areas you may have to check becomes much smaller.

Now, for an algorithm to find the blocks that the line segment collides with:

Block FindNearestBlock(Vector3 start, Vector3 shortenedEndPoint)
{                
    int lowestX = Math.Floor(start.X);
    int highestX = Math.Ceiling(shortenedEndPoint.X);

    int lowestY = Math.Floor(start.Y);
    int highestY = Math.Ceiling(shortenedEndPoint.Y);

    int lowestZ = Math.Floor(start.Z);
    int highestZ = Math.Ceiling(shortenedEndPoint.Z);            

    // Loop through all units we pass along the shortened line segment
    for ( int x = lowestX; x < highestX; ++x )
    {
        for ( int y = lowestY; y < highestY; ++y )
        {
            for ( int z = lowestZ; z < highestZ; ++z )
            {
                // Here you check if a block inhabits the area defined by
                // this point in space. This point represents the axis-aligned
                // block's minimum corner¹
                Vector3 minimumBoxCorner = new Vector(x, y, z);

                Block minCornerBlock = GetBlockAtMinimumCorner( minimumBoxCorner );
                if ( null != minCornerBlock
                {
                    return minCornerBlock;
                }
            }
        }
    }

    // If we made it here then there were no blocks in range that are in front
    // of the reticule.
    return null;
}

¹ Minimum corner: Refers to the corner of the box with the lowest X, Y, and Z values.

Please note, I created this algorithm off the top of my head, it may not even compile exactly as written, but hopefully you'll get the gist. An algorithm like this checks one block at a time, rather than moving in segments that could step over the edges of blocks.

EDIT: Just realized how similar my algorithm ended up being to Blecki's answer. Maybe that gives some merit to each answer as being a good possible solution, seeing as how we both came to similar conclusions.

Answer 3

The operation you want is ray-voxel intersection. You want to step through all the grid cells that the ray intersects, in order of their distance, and stop when you find a non-empty one. A lovely algorithm for this can be found in this easily digestible paper. It is similar to Bresenham's algorithm.

This algorithm gives you an intersecting cell every time through the loop, so the running time is linear with the distance to the target voxel. Some of the other algorithms presented here run in cubic time, which seems very wasteful.

Answer 4

I did the following to get accurate block placement:

    public Block GetBlock(Vector3 position)
    {
        int x = (int)Math.Floor(position.X);
        int y = (int)Math.Floor(position.Y);
        int z = (int)Math.Ceiling(position.Z);

        Block block = GetBlock(x, y, z);

        return block;
    }