Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

enter image description here

enter image description here

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:

enter image description here

enter image description here

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:

enter image description here

share|improve this question
1  
Try drawing a line from your camera position to the targetPoint after your for loop exits. Both the float version and the cast to int version. –  Byte56 Jan 11 '12 at 23:52
1  
It looks like you're stepping along the view vector and checking to see what block the point is in. This might work, but it's crude and could miss blocks when you aim at their edges. For your actual problem, what's the origin of the blocks when they are rendered? Flooring should be the appropriate action if the center of the blocks are actually at 0.5,0.5,0.5 in block-space. Rounding (add 0.5 then floor) if appropriate if the center of the block is at 0,0,0 in block-space. –  Blecki Jan 12 '12 at 3:31
    
If it's always off-center in the same direction it seems likely that you've got the origin of the blocks wrong. Perhaps they are actually at -0.5,0.5,0.5 instead of 0.5,0.5,0.5? Maybe your look-vector is a little off? –  Blecki Jan 12 '12 at 3:47
    
No, the off-centre(ness) changes in the way you are facing. –  Darestium Jan 12 '12 at 3:49
    
That is consistent with my theory, assuming the off-centerness is consistent in world space. –  Blecki Jan 12 '12 at 3:51

4 Answers 4

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.

share|improve this answer
    
This seems overly complicated for such a simpile task xD. Or maybe it just doesn't appeal to my idea of logic. I'll try it if I can't get my current method to work. Thanks :) –  Darestium Jan 12 '12 at 6:34

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.

share|improve this answer

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.

share|improve this answer
up vote 0 down vote accepted

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;
    }
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.