Face-Click-Erkennung (wie in Minecraft)

Ich arbeite an einer Box-basierten Spiel-Engine wie Minecraft und habe mich gefragt, wie ich das "angeklickte Gesicht" beim Platzieren von Blöcken erkennen kann.

Ich habe diese Engine in C ++ (DirectX / D3D), C # (XNA) und Flash (away3d & papervision3d) erstellt.

Der Engine-Code ist bei jedem ziemlich gleich, aber da einer C # und der andere C ++ ist, suche ich nur nach dem Pseudocode, der Theorie oder dem Rat, wie man platzierte Blöcke auf dem angeklickten Gesicht "schnappt".

Wie soll ich seine Ausrichtung erhalten und dann einen Block auf diesem Gesicht in dieser Position mit der entsprechenden Ausrichtung platzieren?

AKTUALISIEREN

Im Moment habe ich mich für eine einfache, aber effektive Methode entschieden:

Zuerst habe ich mich an den grundlegenden 3D-2D-Projektionsalgorithmus erinnert.

Wenn ich jetzt einen Klickpunkt auf dem Bildschirm habe, kann ich einfach eine Linie von der Kamera (Auge) durch den Bildschirm bis zu einer bestimmten Entfernung verfolgen.

Mit dieser Linie "im Auge" und einer modifizierten (3D) Version von Bresenhams (2D) Linienalgorithmus konnte ich nun sehen, ob meine imaginäre Linie auf einen Block in meinem 3D-Gitter "zeigt".

Danke für all deine Vorschläge.

UPDATE 2

Ich hoffe es erklärt meine Lösung. (Rot ist der ursprüngliche Algorithmus, Grün ist meine modifizierte Version)

auch: mit "gerundet" meine ich, dass der ursprüngliche Algorithmus nur den xy-Faktor-Wert rundet, um das nächste Pixel zu erhalten. Ich hoffe ihr wisst wovon ich rede.

Wenn Ihr Strahl durch ein Gitter verfolgt wird, können Sie einfach die Zellen durchlaufen, durch die der Strahl der Reihe nach gehen würde. Ich fand das extrem schnell im Vergleich zum Umgang mit einer Reihe von AABBs in einer großen Welt.

Für jede Zelle können Sie sehen, ob sie als fest angesehen wird. Wenn dies der Fall ist, haben Sie angesichts der vorherigen Zellkoordinaten auch das Gesicht. Sie können auch eine maximale Entfernung festlegen und die Ein- und Ausstiegspunkte für jede Zelle berechnen.

Sie können dies mit einigen komplexeren Kollisionstests für Nicht-Würfel-Zellen kombinieren (z. B. wissen Sie, dass der Strahl mit einem Zaun durch diese Zelle geht, sodass Sie detaillierte Tests durchführen können, um festzustellen, ob Sie den Zaun getroffen oder eine Lücke passiert haben.

Hier gibt es einen Blog-Beitrag, der einige Details und eine Implementierung in 2D enthält. Ich habe es geschafft, meine eigene 3D-Version ohne wirkliche Probleme zu erstellen.

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

BEARBEITEN:

Beachten Sie, dass es wichtig sein kann zu überlegen, wo der Strahl innerhalb einer Zelle beginnt, z. B. das Bild unten mit einem Strahl, der am roten Punkt beginnt und in Richtung des grünen Punkts geht. Die Start- und Endzellen sind gleich, aber ich habe die Position in der Zelle geändert, wodurch dann einige der Zellen zwischen den ausgewählten Zellen geändert wurden. Die blauen Punkte sind die Schnittpunkte. Ich habe diese mit "Start + Zeit * Überschrift" berechnet und die Iteration beendet, sobald ich Zeit = 1 überschritten habe (in diesem Fall ist die Richtung kein Einheitsvektor. Wenn es sich um einen Einheitsvektor handelt, dann natürlich um die Zeit = Entfernung, damit Sie auf diese Weise bis zu einer gewissen Entfernung iterieren können).

Die Idee ist, einen Strahl zu werfen und zu sehen, auf welches Gesicht er trifft. Dies ist so ziemlich ein Ray-to-AABB-Kreuzungstest, bei dem Sie den anfänglichen Kontaktpunkt finden.

Eine gute Ressource (die ich mir beim Schreiben anschaue) ist das Buch Real-Time Collision Detection von Christer Ericson. Die Idee ist, 3 Platten zu verwenden und den Strahl gegen sie zu testen. Eine Platte wäre ein Bereich zwischen zwei Ebenen (gegenüberliegende Seiten des AABB). Wenn der Strahl alle drei Platten schneidet, schneidet er den AABB und ein Kontaktpunkt und eine Zeit t können zurückgegeben werden.

Unter Verwendung dieses Kontaktpunkts kann leicht bestimmt werden, welches Gesicht den meisten Gesichtern dieser Punkt zugewandt ist, insbesondere wenn der AABB implizit gespeichert ist. Wenn der AABB implizit definiert ist, kann das Gesicht direkt berechnet werden, da Sie wissen, dass der Kontaktpunkt auf diesem Gesicht liegt.

Wenn Ihre Box eine Ausrichtung hat, kann das Problem in Strahl gegen AABB umgewandelt werden, indem der Strahl in die Basis der ausgerichteten Box umgewandelt wird.

Diese Berechnung kann durch die Verwendung einer breiten Phasenbaumstruktur unter Verwendung von Begrenzungsrahmen erheblich beschleunigt werden. AABB-Bäume oder dynamische AABB-Bäume eignen sich hervorragend für diese Art von Ray Cast-Abfragen.

Da Sie mit der Maus klicken, wird dies auch als "Kommissionieren" bezeichnet.

Ich hoffe das hilft! Ich habe Raycasting noch nicht selbst implementiert, daher kann ich den Pseudocode für die Implementierung nicht selbst schreiben, habe Sie aber zumindest auf eine großartige Ressource verwiesen.

Diese Frage ähnelt der Frage, wie ich einen Auswahlblock in TechCraft verwaltet habe:

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;
}

Dies gibt uns die WVP-Matrix zum Rendern des Netzes im ausgewählten Block. Wir müssen jedoch noch bestimmen, welcher Block neben diesem Auswahlblock platziert werden soll.

Dies geschieht unter Verwendung eines Vektors3 an dieser Position:

private float setPlayerSelectedBlock(bool waterSelectable)
    {

// 0,5f = min zu prüfender Abstand // 8f = maximal zu prüfender Abstand. Außerdem wird es keinen Auswahlblock geben

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

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

// Sollte nicht versuchen, Wasser oder andere Flüssigkeiten auszuwählen oder neben diese zu stellen

            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;
    }

// Jetzt können wir den Strahl richtig zum benachbarten Block bringen:

    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;
            }
        }
    }

Es gibt einen einfachen, präzisen Algorithmus zum Besuchen der Würfel, die ein Strahl in einer gitterbasierten Welt wie Minecraft durchläuft. In dieser Antwort finden Sie den vollständigen Quellcode.