Face-Click Detection ( like in Minecraft )

Question

I am working on a box-based game engine like minecraft and I was wondering how to detect the "clicked face" when placing blocks.

I have created this engine in C++ ( DirectX / D3D ), C# ( XNA ) and Flash ( away3d & papervision3d ).

The engine code is pretty much the same on each, however as one is C# and the other C++ I'm just looking for the pseudo code, theory or advice on how to "snap" placed blocks on the face that has been clicked on.

How should I get its orientation and then place a block on that face in that position with the corresponding orientation.

UPDATE

For now, I've decided to go with a simple but effective method:

First I've remembered the basic 3D to 2D Projection Algorythm.

If I now have a click-point on the screen, I can simply trace a line from the camera ( eye ) through the screen, up to a specific distance.

With this line "in mind" and a modified ( 3D ) version of Bresenham's ( 2D ) line algorithm, I was now able to see, if my imagined line is "pointing" onto a Block in my 3D grid.

thx for all of your suggestions.

UPDATE 2

I hope it explains my solution. ( red is the original algorythm, green is my modified version )

also: with "rounded" i mean that the original algorythm is just rounding the x-y-factor-value to get the nearest pixel. hope u guys know what i'm talking about.

Answer 1

If your ray tracing through a grid, you can simply iterate over the cells that the ray would pass through, in order. I found this to be extremely fast compared to dealing with a bunch of AABB's in a large world.

For each cell you can see if it is considered solid, if it is, given the previous cell coordinates you have the face as well. You can also have a maximum distance and calculate the entry and exit points for each cell.

You can combine this with some more complex collision testing for non-cube cells (e.g. you know the ray goes through this cell with a fence, so you can then do detailed testing to see if you hit the fence or passed through a gap.

There is a blog post here that gives some details and an implementation in 2D. I managed to create my own 3D version without any real problems.

http://playtechs.blogspot.co.uk/2007/03/raytracing-on-grid.html

EDIT:

Note that it can be important to consider where the ray starts from within a cell, e.g. consider the image below with a ray starting at the red point and heading towards the green one. The start and end cells are are the same, but I changed the position in the cell which then changed some of the cells in between picked. The blue dots are the intersection points, I calculated those with "start + time * heading", and stopped iterating once I passed time = 1 (in this case direction is not a unit vector. Of course if it was a unit vector then time = distance so you could iterate up to some distance that way).

Answer 2

The idea is to cast a ray and see what face it hits. This is pretty much a ray to AABB intersection test, in which you find the initial point of contact.

A good resource (which I'm looking at as I write this) is in the book Real-Time Collision Detection by Christer Ericson. The idea is to use 3 slabs and test the ray against them. A slab would be a region between two planes (being opposite sides of the AABB). If the ray intersects all three slabs, it intersects the AABB and a point of contact and time t can be returned.

Using this point of contact determining which face most faces this point can be done easily, especially if the AABB is stored implicity. If the AABB is implictly defined, then the face can be outright computed, as you know the point of contact lies upon that face.

If your box has an orientation, the problem can be transformed into ray vs AABB by transforming the ray into the basis of the oriented box.

This calculation can be greatly sped up with the use of some sort of broad phase tree structure using bounding boxes. AABB trees or dynamic AABB trees are great for these sort of ray cast queries.

Since you're clicking with your mouse this is also commonly referred to as "picking".

I hope this helps! I haven't implemented raycasting myself yet, so I can't write out the psuedo-code for the implementation myself, but at least referred you to a great resource.

Answer 3

This question seems similar to how I managed a selection block in TechCraft:

public void RenderSelectionBlock()
{
    //Get exact centre vector
    Vector3 position = player.currentSelection.Value.position.asVector3() + new Vector3(0.5f, 0.5f, 0.5f);

    Matrix matrix_a, matrix_b;
    Matrix identity = Matrix.Identity;                       // setup the matrix prior to translation and scaling  
    Matrix.CreateTranslation(ref position, out matrix_a);    // translate the position a half block in each direction
    Matrix.CreateScale((float)0.51f, out matrix_b);          // scales the selection box slightly larger than the targetted block

    identity = Matrix.Multiply(matrix_b, matrix_a);          // the final position of the block

    // set up the World, View and Projection
    _selectionBlockEffect.World = identity;
    _selectionBlockEffect.View = camera.View;
    _selectionBlockEffect.Projection = camera.Projection;
}

This gives us the WVP matrix for rendering the mesh at the chosen block. But, we still need to determine which block to place adjacent to that selection block.

This is done by using a vector3 to that position:

private float setPlayerSelectedBlock(bool waterSelectable)
    {

// 0.5f = min distance to check // 8f = max distance to check. Further, there wont be a selection block

        for (float x = 0.5f; x < 8f; x += 0.1f)
        {
            Vector3 targetPoint = camera.Position + (lookVector * x);

            Block block = player.world.BlockAt(targetPoint);

// Shouldnt be attempting to select or place adjacent to water or other fluids

            if (block.Type != BlockType.None && (waterSelectable || block.Type != BlockType.Water))
            {
                player.currentSelection = new PositionedBlock(new Vector3i(targetPoint), block);
                return x;
            }
            else
            {
                player.currentSelection = null;
                player.currentSelectedAdjacent = null;
            }
        }
        return 0;
    }

// Now we can get the ray to the adjacent block properly:

    private void setPlayerAdjacentSelectedBlock(float xStart)
    {
        for (float x = xStart; x > 0.7f; x -= 0.1f)
        {
            Vector3 targetPoint = camera.Position + (lookVector * x);
            Block block = player.world.BlockAt(targetPoint);

            if (player.world.BlockAt(targetPoint).Type == BlockType.None)
            {
                player.currentSelectedAdjacent = new PositionedBlock(new Vector3i(targetPoint), block);
                break;
            }
        }
    }

Answer 4

There is a straightforward precise algorithm for visiting the cubes that a ray passes through in a grid-based world like Minecraft; see this answer for full source code.