Lancer Ray pour sélectionner un bloc dans le jeu Voxel

22

Je développe un jeu avec un terrain de type Minecraft composé de blocs. Étant donné que le rendu de base et le chargement de blocs sont maintenant effectués, je souhaite implémenter la sélection de blocs.

Par conséquent, je dois découvrir à quel bloc la caméra à la première personne est confrontée. J'ai déjà entendu parler de ne pas projeter toute la scène, mais j'ai décidé de ne pas le faire car cela semble hacky et n'est pas précis. Peut-être que je pourrais en quelque sorte lancer un rayon dans la direction de la vue, mais je ne sais pas comment vérifier la collision avec un bloc dans mes données de voxel. Bien sûr, ces calculs doivent être effectués sur le CPU car j'ai besoin des résultats pour effectuer des opérations de logique de jeu.

Alors, comment pourrais-je savoir quel bloc se trouve devant la caméra? Si c'est préférable, comment pourrais-je lancer un rayon et vérifier les collisions?

danijar
la source
Je ne l'ai jamais fait moi-même. Mais ne pourriez-vous pas simplement avoir un "rayon" (segment linéaire dans ce cas) du plan de la caméra, un vecteur normal, avec une certaine longueur (vous voulez seulement qu'il soit dans un rayon) et voir s'il intersecte avec l'un des blocs. Je suppose que l'espacement partiel et l'écrêtage sont également mis en œuvre. Donc, savoir avec quels blocs tester ne devrait pas être un gros problème ... je pense?
Sidar

Réponses:

21

Lorsque j'ai eu ce problème en travaillant sur mes cubes , j'ai trouvé l'article "Un algorithme de traversée rapide de voxel pour le traçage de rayons" de John Amanatides et Andrew Woo, 1987 qui décrit un algorithme qui peut être appliqué à cette tâche; il est précis et ne nécessite qu'une seule itération de boucle par voxel intersecté.

J'ai écrit une implémentation des parties pertinentes de l'algorithme de l'article en JavaScript. Mon implémentation ajoute deux fonctionnalités: elle permet de spécifier une limite sur la distance du raycast (utile pour éviter les problèmes de performances ainsi que pour définir une `` portée '' limitée), et calcule également la face de chaque voxel dans laquelle le rayon est entré.

Le originvecteur d' entrée doit être mis à l'échelle de telle sorte que la longueur latérale d'un voxel soit 1. La longueur du directionvecteur n'est pas significative mais peut affecter la précision numérique de l'algorithme.

L'algorithme fonctionne en utilisant une représentation paramétrée du rayon, origin + t * direction. Pour chaque axe de coordonnées, nous gardons une trace de la tvaleur que nous aurions si nous avons fait un pas suffisant pour franchir une limite de voxel le long de cet axe (ie changer la partie entière de la coordonnée) dans les variables tMaxX, tMaxYet tMaxZ. Ensuite, nous faisons un pas (en utilisant les variables stepet tDelta) le long de l'axe qui a le moins tMax- c'est-à-dire de la limite de voxel la plus proche.

/**
 * Call the callback with (x,y,z,value,face) of all blocks along the line
 * segment from point 'origin' in vector direction 'direction' of length
 * 'radius'. 'radius' may be infinite.
 * 
 * 'face' is the normal vector of the face of that block that was entered.
 * It should not be used after the callback returns.
 * 
 * If the callback returns a true value, the traversal will be stopped.
 */
function raycast(origin, direction, radius, callback) {
  // From "A Fast Voxel Traversal Algorithm for Ray Tracing"
  // by John Amanatides and Andrew Woo, 1987
  // <http://www.cse.yorku.ca/~amana/research/grid.pdf>
  // <http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.3443>
  // Extensions to the described algorithm:
  //   • Imposed a distance limit.
  //   • The face passed through to reach the current cube is provided to
  //     the callback.

  // The foundation of this algorithm is a parameterized representation of
  // the provided ray,
  //                    origin + t * direction,
  // except that t is not actually stored; rather, at any given point in the
  // traversal, we keep track of the *greater* t values which we would have
  // if we took a step sufficient to cross a cube boundary along that axis
  // (i.e. change the integer part of the coordinate) in the variables
  // tMaxX, tMaxY, and tMaxZ.

  // Cube containing origin point.
  var x = Math.floor(origin[0]);
  var y = Math.floor(origin[1]);
  var z = Math.floor(origin[2]);
  // Break out direction vector.
  var dx = direction[0];
  var dy = direction[1];
  var dz = direction[2];
  // Direction to increment x,y,z when stepping.
  var stepX = signum(dx);
  var stepY = signum(dy);
  var stepZ = signum(dz);
  // See description above. The initial values depend on the fractional
  // part of the origin.
  var tMaxX = intbound(origin[0], dx);
  var tMaxY = intbound(origin[1], dy);
  var tMaxZ = intbound(origin[2], dz);
  // The change in t when taking a step (always positive).
  var tDeltaX = stepX/dx;
  var tDeltaY = stepY/dy;
  var tDeltaZ = stepZ/dz;
  // Buffer for reporting faces to the callback.
  var face = vec3.create();

  // Avoids an infinite loop.
  if (dx === 0 && dy === 0 && dz === 0)
    throw new RangeError("Raycast in zero direction!");

  // Rescale from units of 1 cube-edge to units of 'direction' so we can
  // compare with 't'.
  radius /= Math.sqrt(dx*dx+dy*dy+dz*dz);

  while (/* ray has not gone past bounds of world */
         (stepX > 0 ? x < wx : x >= 0) &&
         (stepY > 0 ? y < wy : y >= 0) &&
         (stepZ > 0 ? z < wz : z >= 0)) {

    // Invoke the callback, unless we are not *yet* within the bounds of the
    // world.
    if (!(x < 0 || y < 0 || z < 0 || x >= wx || y >= wy || z >= wz))
      if (callback(x, y, z, blocks[x*wy*wz + y*wz + z], face))
        break;

    // tMaxX stores the t-value at which we cross a cube boundary along the
    // X axis, and similarly for Y and Z. Therefore, choosing the least tMax
    // chooses the closest cube boundary. Only the first case of the four
    // has been commented in detail.
    if (tMaxX < tMaxY) {
      if (tMaxX < tMaxZ) {
        if (tMaxX > radius) break;
        // Update which cube we are now in.
        x += stepX;
        // Adjust tMaxX to the next X-oriented boundary crossing.
        tMaxX += tDeltaX;
        // Record the normal vector of the cube face we entered.
        face[0] = -stepX;
        face[1] = 0;
        face[2] = 0;
      } else {
        if (tMaxZ > radius) break;
        z += stepZ;
        tMaxZ += tDeltaZ;
        face[0] = 0;
        face[1] = 0;
        face[2] = -stepZ;
      }
    } else {
      if (tMaxY < tMaxZ) {
        if (tMaxY > radius) break;
        y += stepY;
        tMaxY += tDeltaY;
        face[0] = 0;
        face[1] = -stepY;
        face[2] = 0;
      } else {
        // Identical to the second case, repeated for simplicity in
        // the conditionals.
        if (tMaxZ > radius) break;
        z += stepZ;
        tMaxZ += tDeltaZ;
        face[0] = 0;
        face[1] = 0;
        face[2] = -stepZ;
      }
    }
  }
}

function intbound(s, ds) {
  // Find the smallest positive t such that s+t*ds is an integer.
  if (ds < 0) {
    return intbound(-s, -ds);
  } else {
    s = mod(s, 1);
    // problem is now s+t*ds = 1
    return (1-s)/ds;
  }
}

function signum(x) {
  return x > 0 ? 1 : x < 0 ? -1 : 0;
}

function mod(value, modulus) {
  return (value % modulus + modulus) % modulus;
}

Lien permanent vers cette version de la source sur GitHub .

Kevin Reid
la source
1
Cet algorithme fonctionne-t-il également pour un espace numérique négatif? J'ai implémenté l'algorithme juste et généralement je suis impressionné. Cela fonctionne très bien pour des coordonnées positives. Mais pour une raison quelconque, j'obtiens des résultats étranges si des coordonnées négatives sont impliquées parfois.
danijar
2
@danijar Je ne pouvais pas obtenir le intbounds / mod choses à travailler avec l' espace négatif, donc j'utiliser ceci: function intbounds(s,ds) { return (ds > 0? Math.ceil(s)-s: s-Math.floor(s)) / Math.abs(ds); }. Comme Infinityc'est plus grand que tous les nombres, je ne pense pas que vous ayez besoin de vous prémunir contre le fait que ds soit 0.
Will
1
@BotskoNet Il semble que vous ayez un problème avec la non-projection pour trouver votre rayon. J'ai eu des problèmes comme ça au début. Suggestion: tracez une ligne de l'origine à l'origine + direction, dans l'espace mondial. Si cette ligne n'est pas sous le curseur, ou si elle n'apparaît pas comme un point (puisque les X et Y projetés doivent être égaux), alors vous avez un problème de non-projection ( ne faisant pas partie du code de cette réponse). Si c'est de manière fiable un point sous le curseur, le problème est dans le raycast. Si vous avez toujours un problème, veuillez poser une question distincte au lieu d'étendre ce fil.
Kevin Reid
1
Le cas du bord est où une coordonnée de l'origine du rayon est une valeur entière et la partie correspondante de la direction du rayon est négative. La valeur tMax initiale pour cet axe doit être nulle, car l'origine se trouve déjà au bord inférieur de sa cellule, mais elle 1/dsentraîne plutôt l'incrémentation de l'un des autres axes. Le correctif consiste à écrire intfloorpour vérifier si les deux dssont négatifs et s'il ss'agit d'une valeur entière (mod renvoie 0), et renvoie 0,0 dans ce cas.
codewarrior
2
Voici mon port vers Unity: gist.github.com/dogfuntom/cc881c8fc86ad43d55d8 . Cependant, avec quelques changements supplémentaires: intégré les contributions de Will et codewarrior et rendu possible de lancer dans un monde illimité.
Maxim Kamalov
1

Regardez peut-être l' algorithme de ligne de Bresenham , en particulier si vous travaillez avec des blocs d'unité (comme la plupart des jeux minecraftish le font).

Fondamentalement, cela prend deux points et trace une ligne ininterrompue entre eux. Si vous lancez un vecteur du joueur à sa distance de cueillette maximale, vous pouvez l'utiliser, et les joueurs se positionnent comme des points.

J'ai une implémentation 3D en python ici: bresenham3d.py .

salmonmoose
la source
6
Un algorithme de type Bresenham manquera cependant certains blocs. Il ne prend pas en compte chaque bloc traversé par le rayon; il en sautera certains dans lesquels le rayon ne se rapproche pas suffisamment du centre du bloc. Vous pouvez le voir clairement sur le diagramme de Wikipédia . Le bloc 3ème en bas et 3ème à droite du coin supérieur gauche en est un exemple: la ligne le traverse (à peine) mais l'algorithme de Bresenham ne le frappe pas.
Nathan Reed
0

Pour trouver le premier bloc devant la caméra, créez une boucle for qui boucle de 0 à une distance maximale. Ensuite, multipliez le vecteur avant de la caméra par le compteur et vérifiez si le bloc à cette position est solide. Si c'est le cas, enregistrez la position du bloc pour une utilisation ultérieure et arrêtez la boucle.

Si vous voulez également pouvoir placer des blocs, le choix du visage n'est pas plus difficile. Il suffit de revenir en boucle à partir du bloc et de trouver le premier bloc vide.

sans titre
la source
Cela ne fonctionnerait pas, avec un vecteur avant incliné, il serait très possible d'avoir un point avant une partie d'un bloc, et le point suivant après, manquer le bloc. La seule solution à cela serait de réduire la taille de l'incrément, mais il faudrait que ce soit si petit qu'il rende les autres algorithmes beaucoup plus efficaces.
Phil
Cela fonctionne assez bien avec mon moteur; J'utilise un intervalle de 0,1.
sans titre
Comme l'a souligné @Phil, l'algorithme manquerait des blocs où seule une petite arête est visible. De plus, boucler en arrière pour placer des blocs ne fonctionnerait pas. Il faudrait également boucler en avant et décrémenter le résultat de un.
danijar
0

J'ai fait un post sur Reddit avec mon implémentation , qui utilise l'algorithme de ligne de Bresenham. Voici un exemple d'utilisation que vous en feriez:

// A plotter with 0, 0, 0 as the origin and blocks that are 1x1x1.
PlotCell3f plotter = new PlotCell3f(0, 0, 0, 1, 1, 1);
// From the center of the camera and its direction...
plotter.plot( camera.position, camera.direction, 100);
// Find the first non-air block
while ( plotter.next() ) {
   Vec3i v = plotter.get();
   Block b = map.getBlock(v);
   if (b != null && !b.isAir()) {
      plotter.end();
      // set selected block to v
   }
}

Voici l'implémentation elle-même:

public interface Plot<T> 
{
    public boolean next();
    public void reset();
    public void end();
    public T get();
}

public class PlotCell3f implements Plot<Vec3i>
{

    private final Vec3f size = new Vec3f();
    private final Vec3f off = new Vec3f();
    private final Vec3f pos = new Vec3f();
    private final Vec3f dir = new Vec3f();

    private final Vec3i index = new Vec3i();

    private final Vec3f delta = new Vec3f();
    private final Vec3i sign = new Vec3i();
    private final Vec3f max = new Vec3f();

    private int limit;
    private int plotted;

    public PlotCell3f(float offx, float offy, float offz, float width, float height, float depth)
    {
        off.set( offx, offy, offz );
        size.set( width, height, depth );
    }

    public void plot(Vec3f position, Vec3f direction, int cells) 
    {
        limit = cells;

        pos.set( position );
        dir.norm( direction );

        delta.set( size );
        delta.div( dir );

        sign.x = (dir.x > 0) ? 1 : (dir.x < 0 ? -1 : 0);
        sign.y = (dir.y > 0) ? 1 : (dir.y < 0 ? -1 : 0);
        sign.z = (dir.z > 0) ? 1 : (dir.z < 0 ? -1 : 0);

        reset();
    }

    @Override
    public boolean next() 
    {
        if (plotted++ > 0) 
        {
            float mx = sign.x * max.x;
            float my = sign.y * max.y;
            float mz = sign.z * max.z;

            if (mx < my && mx < mz) 
            {
                max.x += delta.x;
                index.x += sign.x;
            }
            else if (mz < my && mz < mx) 
            {
                max.z += delta.z;
                index.z += sign.z;
            }
            else 
            {
                max.y += delta.y;
                index.y += sign.y;
            }
        }
        return (plotted <= limit);
    }

    @Override
    public void reset() 
    {
        plotted = 0;

        index.x = (int)Math.floor((pos.x - off.x) / size.x);
        index.y = (int)Math.floor((pos.y - off.y) / size.y);
        index.z = (int)Math.floor((pos.z - off.z) / size.z);

        float ax = index.x * size.x + off.x;
        float ay = index.y * size.y + off.y;
        float az = index.z * size.z + off.z;

        max.x = (sign.x > 0) ? ax + size.x - pos.x : pos.x - ax;
        max.y = (sign.y > 0) ? ay + size.y - pos.y : pos.y - ay;
        max.z = (sign.z > 0) ? az + size.z - pos.z : pos.z - az;
        max.div( dir );
    }

    @Override
    public void end()
    {
        plotted = limit + 1;
    }

    @Override
    public Vec3i get() 
    {
        return index;
    }

    public Vec3f actual() {
        return new Vec3f(index.x * size.x + off.x,
                index.y * size.y + off.y,
                index.z * size.z + off.z);
    }

    public Vec3f size() {
        return size;
    }

    public void size(float w, float h, float d) {
        size.set(w, h, d);
    }

    public Vec3f offset() {
        return off;
    }

    public void offset(float x, float y, float z) {
        off.set(x, y, z);
    }

    public Vec3f position() {
        return pos;
    }

    public Vec3f direction() {
        return dir;
    }

    public Vec3i sign() {
        return sign;
    }

    public Vec3f delta() {
        return delta;
    }

    public Vec3f max() {
        return max;
    }

    public int limit() {
        return limit;
    }

    public int plotted() {
        return plotted;
    }



}
ClickerMonkey
la source
1
Comme quelqu'un l'a remarqué dans les commentaires, votre code n'est pas documenté. Bien que le code puisse être utile, il ne répond pas tout à fait à la question.
Anko