Génération procédurale de terrain: Part. III, Cube mapping

Nous allons aujourd’hui parler de cube mapping. Le procédé est absolument indispensable pour ce que l’on se propose de faire. Dans le dernier article nous avions étudié comment projeter un cube sur une sphère, hors, à ce moment, le cube était vierge. Nous voulons maintenant appliquer sur ce cube une heightmap. Cette heightmap se présentera sous la forme d’une texture particulière à la façon d’un patron de cube.

patroncube1.png

Notons par ailleurs qu’en ce qui concerne le cube mapping il existe plusieurs école. Une des technique utilisées et expliquées ici utilise notamment la carte graphique. Même si la carte graphique est très rapide, dans le cas du Stamp Noise cela oblige le programme à faire de très très nombreux allez-retours entre la mémoire vive de l’ordinateur et celle de la GPU. Par ailleurs l’algorithme est dépendant du GPU. La technique que nous allons voir a la prétention d’être raisonnablement optimisée et fonctionne sans GPU tout en offrant un temps d’exécution confortable qui permet au programme de s’exécuter en temps réel.

Enfin, avant de commencer, nous allons présenter les problématiques du cube mapping pour bien cerner la difficulté de l’entreprise. Notons également que l'article ne traitera que les "grosses" parties de la preuve de concept. Un article exhaustif en explications sur chaque détails du programme serait bien trop long. Nous survolerons ici la preuve de concept afin d’en avoir un aperçu raisonnable.

En premier lieu, on doit pouvoir subdiviser un nombre arbitraire de fois chacune des faces. Ces subdivisions sont locales. La raison est que nous voulons un niveau de détail dynamique ; à mesure que la caméra est proche de la surface de la planète on doit gagner en niveau de détail. Mais cela ne sert à rien de subdiviser l’ensemble de la cubemap, il ne faut subdiviser que les portions qui sont affichées à l’écran (sinon la mémoire va très vite être saturée). Le choix des portions est laissé à la discrétion d’un autre algorithme qui n’est pas encore implémenté et dont on ne parlera pas ici. Ci-dessous un exemple de subdivision.

cubemap2.png

Nous avons donc un ensemble de subdivisions, calculées à la volée, et dont on veut, en second lieu, que chacune des frontières correspondet à la frontière adjacente, autrement dit, on doit faire correspondre chacune des faces et des subdivisions qui composent ces faces entre elles de sorte à avoir un espace continu ; qui ne donne pas l’impression que les « pièces » auraient était mises ensemble n’importe comment. Typiquement on veut éviter ça

wrongCubemap.png

Sur cette dernière image on voit qu’une des subdivisions ne correspond pas à ses voisines, et qu’une face entière ne correspond également pas aux autres.

Bon. À partir de là on distingue quatre cas de figure que notre algorithme devra reconnaître et traiter. Pour visualiser ça on va prendre une cubemap dont chacune des faces est subdivisée une fois (ça fait quatre secteurs par face), cela nous permettra de mettre en évidence nos différentes situations. Rappelons que nous appliquons un tampon sur une matrice. Pour faire une surface continue il faut détecter quand ce tampon dépasse de la matrice courante pour faire en sorte que la partie du tampon qui dépasse soit « imprimée » de l’autre côté, sur la matrice adjacente correspondante. C’est là que tout se complique comme on va le voir :

patroncube3.png

Chaque petite « gommette » représente un tampon imprimé à un endroit de la cubemap. La couleur de la gommette renseigne le cas de figure auquel on s’expose.

En vert, c’est le cas trivial où le tampon est imprimé à l’intérieur du secteur courant. Il n’y a pas de traitement particulier à faire.

En bleu, c’est le cas un peu plus compliqué où le tampon dépasse soit sur l’axe x soit sur l’axe y, mais pas les deux à la fois.

En rouge, c’est le cas encore un peu plus compliqué où le tampon dépasse sur l’axe x ET y.

Enfin, en jaune, c’est le cas difficile mais plus rare où le tampon dépasse en x ET y ET sur un coin d’une face. C’est important de faire la distinction. Le dépassement sur le coin des faces implique un traitement particulier que nous verrons plus bas.

La première chose que l’on remarque c’est que dans les situations marquées en bleu , jaune et rouge il va falloir transformer les coordonnées du pixel courant quand celui-ci est en dehors de son secteur d’origine. Pour bien comprendre le phénomène on se donne encore un schéma qui illustre la problématique:

patroncube4.png

En effet si on se donne pour face de référence celle qui est marqué +z alors le système de coordonnées des autres faces, relativement à +z, change. Par exemple, lorsque l’on se déplace verticalement, vers le bas sur +x, on arrive à la face adjacente inférieur +y. Le déplacement ne se fait alors plus verticalement de haut en bas, mais horizontalement de droite à gauche.

Pour la petite histoire, la première version de la preuve de concept que l’on étudie aujourd’hui est monolithique. C’est à dire que tout le code tiens dans un seul fichier contenant deux ou trois grosses fonctions. Cette version là ne gérait que les cas relativement simples décrits par les gommettes vertes et bleues, et ne gérait pas la subdivision de surface. Le code devenait très compliqué et contrairement aux autres preuves de concept il ne pouvait décemment pas tenir dans un seul fichier source. Finalement, la preuve de concept actuelle est assez proche du produit final qui devra être intégré au code d’UNIVERSE. Pour jeter un œil à la première version du PoC, rendez vous [ici |https://github.com/DenisSalem/UNIVERSE/blob/master/PoC/cubeMapping/main.cpp.megamoth|en|megamoth]

Rappelons que pour le moment nous utilisions le C++ mais sans vraiment en tirer partie. Hors ici l’utilisation de la programmation orienté objet est tout à fait pertinente. L’idée centrale est que chaque face, appelé royaume, soit une classe gérant son espace. Chaque royaume est lié aux autres par références. Et pour pouvoir se déplacer dans un espace en dehors du royaume on définit des méthodes virtuelles implémentées pour chacune de ces classes. C’est le moment d’expliquer tout ça plus en détail via un diagramme UML qui va illustrer exactement ce que fait notre preuve de concept de cube mapping. Il est fortement suggéré d’être à l’aise avec les rudiments d’UML et de la programmation orientée objet pour comprendre ce qui va suivre.

cubemappingUML.png

Comme nous le disions, on se donne une classe abstraite Realm dont on implémente six fois (une fois pour chaque faces) les fonctions de correspondances de coordonnées. Les systèmes de coordonnées implémentés sont relatifs à la face courante et décrivent comment se déplacer sur les faces adjacentes. Ces fonctions sont notées en gras et en italique.

Dans la classe abstraite Realm, les quatre premières méthodes abstraites décrivent des déplacement sur l’axe vertical ou horizontal, mais pas les deux axes à la fois. Les huit fonctions restantes ne gèrent que les dépassement simultanés sur l’axe horizontal et vertical. Ces dernières fonctions sont utilisés quand le dépassement se fait sur le coin d’un secteur. Sans pour autant dépasser sur le coin d’une face. Cette situation est illustrée par les gommettes rouges sur la figure plus haut.

Les quatres premières fonctions

  • GetCoordsToNeighbourTop
  • GetCoordsToNeighbourBottom
  • GetCoordsToNeighbourLeft
  • GetCoordsToNeighbourRight

correspondent au cas d’usage illustré par les gommettes bleues.

La classe abstraite Realm comporte finalement quatre grosses méthodes qui correspondent à chacune des couleurs de gommettes vues plus haut :

  • StampWithinChunk
  • StampBeyondBorder
  • StampBeyondCorner
  • StampBeyondCornerBeyondRealm

Dans la fonction principale de bas niveau Noise (la fonction est privée et est appelée par son homonyme public) on analyse le décalage aléatoire du tampon pour décider quelle fonction de tamponnage utiliser.

  if ( this->IsChunkACorner(chunkCoordX,chunkCoordY,chunkScale-1) && stampCrossCornerBeyondRealm) {
    this->StampBeyondCornerBeyondRealm(sectorScale, halfScale, offsetX, offsetY, stampCrossCornerBeyondRealm);
  }
  else {
    chunkLimit = chunkScale - 1;
    for (int y=0; y<sectorScale; y++) {
      stampX = 0;
      for (int x=0; x<sectorScale; x++) {
        stampIndex = stampX + sectorScale * stampY;
	if ( stamp[ stampIndex ] != 0) {
          if (x+offsetX >= 0 && x+offsetX < this->scale && y+offsetY >= 0 && y+offsetY < this->scale) {
            this->StampWithinChunk(x+offsetX, y+offsetY, stampIndex);
          }
          else {
            StampBeyondCorner(x+offsetX, y+offsetY, chunkCoordX, chunkCoordY, chunkLimit, stampIndex);
            StampBeyondBorder(x+offsetX, y+offsetY, chunkCoordX, chunkCoordY, stampIndex);
          }
        }
        stampX += this->step;
      }
      stampY += this->step * this->step;
    }
  }

En effet, le premier test consiste à vérifier le cas particulier (et rare) du tampon qui dépasse sur un coin d’une face. Si c’est le cas on appelle StampBeyondCornerBeyondRealm. Sinon c’est que l’on se trouve dans une situation relativement simple à gérer : Soit le tampon est contenu exactement à l’intérieur du secteur courant, soit il en dépasse. S’il dépasse on appelle successivement StampBeyondCorner et StampBeyondBorder. À l’intérieur de celle-ci s’effectuent les tests qui doivent décider si oui ou non le tampon est appliqué. À ce niveau de code, le tampon est écrit nécessairement par l’une ou l’autre fonction.

Dans la fonction StampBeyondBorder on fait la distinction entre le dépassement sur un bord à l’intérieur d’une face ou vers l’extérieur d’une face. Par exemple :

inline void Realm::StampBeyondBorder(int x, int y, int chunkCoordX, int chunkCoordY, int stampIndex) {
  if(this->horizontalNeighbourChunk != 0 && x < 0 && y >= 0 && y < this->scale) {
    if (chunkCoordX == 0) {
      this->chunkIndex = this->GetCoordsToNeighbourLeft(x, y, this->scale) ;
    }
    else {
      this->chunkIndex = y * this->scale + this->scale + x;
    }
    horizontalNeighbourChunk[chunkIndex] += this->sign * this->stamp[ stampIndex ] / this->step;
    this->UpdateMinMax(chunkIndex, this->horizontalNeighbourChunk);
  }

De façon identique, dans StampBeyondCorner on regarde si le tampon dépasse sur le bord d’une face, sur le coin d’un secteur ou si le dépassement se fait sur le coin d’un secteur à l’intérieur de la face courante

  if (this->diagonalNeighbourChunk != 0) {
    if(x < 0 &&  y < 0) {
      if (chunkCoordX == 0) {
        this->chunkIndex = this->GetCoordsToNeighbourLeftTopLeft(x, y, this->scale) ;
      }
      else if (chunkCoordY == 0) {
        this->chunkIndex = this->GetCoordsToNeighbourTopTopLeft(x, y, this->scale) ;
      }
      else {
        this->chunkIndex = this->scale + x + this->scale * (this->scale + y);
      }
    }

J’aimerais rappeler que l’on ne parle volontairement pas des fonctions intermédiaires nécessaires au bon déroulement du programme. Je pense par exemple aux fonctions qui préparent les pointeurs désignant les espaces mémoire à remplir. Pour une compréhension plus complète de la preuve de concept vous êtes invité à vous plonger dans le code source, disponible sur Github.

Ceci étant dit, on arrive à la partie importante de la preuve de concept. Jusqu’à présent nous pouvions travailler sans trop faire de mathématiques, les opérations effectués étaient relativement simple et ne nécessitaient pas de trigonométrie. Nous allons parler de la façon dont on peut imprimer le tampon sur trois faces adjacentes, à l’endroit où les coins de celles là se confondent.

Le problème est le suivant ; jusqu’à présent, nous savions faire ça

cubemap5.png

C’est à dire imprimer le tampon sur des surfaces contiguës que l’on peut ramener sur le même plan sans distorsion. Ça se complique dans cette situation :

cubemap6.png

Dans cette situation le secteur de la face A et le secteur de la face C ne sont pas contiguës. Il n’y a rien qui lie les bords de ceux là, c’est le vide. Hors le tampon (la partie en rouge) chevauche cet espace vide. On ne peut pas simplement supprimer cette partie rouge sinon il y aurait un évident problème de correspondance au moment de la jointure (quand on transforme le patron en cube). Il faut donc ruser. Je propose d’utiliser un espace de transition que l’on peut représenter ainsi :

transitionSpace.png

Comme on le voit, par distorsion, on a joint les trois faces A,B et C. Notre espace de transition c’est ça : Entre chaque face, en prenant comme point de référence là où les coins de confondent, on a 120°. Avec trois faces, on a donc bien trois fois 120° soit 360° ; un tour complet. Du coup la suite des hostilités va consister à déterminer, en fonction du décalage aléatoire la distance entre le centre du tampon à l’endroit ou il devrait être imprimé normalement, sans l’espace de transition, et le coin sur lequel le tampon dépasse. On récupère également l’angle que fait le centre du tampon avec le coin qui nous intéresse.

cubemap7.png

L’angle que fait le centre du tampon peut systématiquement varier entre 0 et 90°. L’objectif est de reporter et mettre à l’échelle cet angle dans l’espace de transition à l’aide d’un produit en croix. Cet à dire que l’on va positionner le tampon sur la face correspondante, déformée, de l’espace de transition, dans laquelle sa position angulaire variera non plus entre 0 et 90° mais entre 0 et 120°. La distance du centre du tampon avec le point où les faces se confondent reste la même. Dans la pratique on a quelque chose comme ça :

    // Préparation des coordonnées de référence.
    transitionSpace = new float [transitionSpaceScale * transitionSpaceScale]();
    StampCenterCoordX = halfScale - ABS(offsetX % sectorScale);
    StampCenterCoordY = halfScale - ABS(offsetY % sectorScale);
    distanceFromStampCenterToCorner = sqrtl(pow(StampCenterCoordX,2) + pow(StampCenterCoordY,2))*this->step;
    angleStampCenterCorner = this->SetAngle(stampCrossCornerBeyondRealm, StampCenterCoordY, StampCenterCoordX);

    // Préparation des coordonnées de transition
    if ( stampCrossCornerBeyondRealm == CORNER_TOP_LEFT) {
      newAngle = - PI2_12 + (( angleStampCenterCorner) * PI2_3) / PI_2 ;
    }
    else if(stampCrossCornerBeyondRealm == CORNER_TOP_RIGHT) {
      newAngle = -PI2_12 + (( angleStampCenterCorner + PI_2) * PI2_3) / PI_2 ;
    }
    else if ( stampCrossCornerBeyondRealm == CORNER_BOTTOM_LEFT || stampCrossCornerBeyondRealm == CORNER_BOTTOM_RIGHT) {
      newAngle = - PI2_12 + (( angleStampCenterCorner) * PI2_3) / PI_2 ;
    }

    newStampOffsetX = (int) halfTransitionSpaceScale - (this->scale >> 1) + cos(newAngle) * distanceFromStampCenterToCorner ;
    newStampOffsetY = (int) halfTransitionSpaceScale - (this->scale >> 1) - sin(newAngle) * distanceFromStampCenterToCorner ;

On remarque tout de même que la détermination du nouvel angle, sur l’espace de transition est un peu plus compliqué. En effet, puisqu’on travaille sur le cercle trigonométrique, pour une position donnée , l’angle correspondant n’est pas nécessaire compris entre 0 et 90°. Il faut donc compenser. Par exemple dans le cas où le dépassement se fait sur le coin supérieur droit, cela veut dire que l’angle correspondant sur le cercle trigonométrique sera compris entre – 180° et -90°. On ajoute donc 90° (PI/2) pour être dans une plage d’angle qui fait sens.

Mais ce n’est pas tout. Une fois le produit en croix terminé ;

(( angleStampCenterCorner + PI_2) * PI2_3) / PI_2

On a bien une variation angulaire comprise entre 0 et 120°. Il faut maintenant rajouter un nouveau décalage. En effet, l’angle de départ varie selon la face et le coin sur lequel on dépasse. Dans le cas du dépassement sur le coin supérieur droit on à une variation finale négative entre 0 et -120°. On se donne comme angle de départ pour la face B -30° soit -2Pi/12

transitionSpace2.png

d’où

newAngle = -PI2_12 + (( angleStampCenterCorner + PI_2) * PI2_3) / PI_2 ;

Et voilà, avec ça on est capables d’imprimer le tampon sur l’espace de transition qui, à coup sûr, dépassera sur les autres faces adjacentes.

Du coup, on arrive à l'étape finale de notre cas particulier. Il s'agit maintenant de rapatrier les données de l'espace de transition vers la cubemap. Pour ça nous allons travailler successivement sur trois face. À chaque fois, pour un pixel donné on déterminera la position angulaire et la distance de ce pixel avec le coin ciblé. Ce sera ensuite la même mécanique ; mise à l’échelle de l’angle et détermination des coordonnées sur l’espace de transition. Finalement on prélève le pixel de l’espace de transition à l’aide de ces nouvelles coordonnées pour l’appliquer à la surface de destination, sur la cubemap.

Quelque soit la face de destination il y a une optimisation non négligeable que l’on peut s’offrir. En effet, on a pas besoin de parcourir toute la face de destination courante mais seulement une partie comme illustré ci-dessous :

circleLimit.png

En effet le tampon, à taille maximale, ne dépassera jamais de la zone circulaire décrite par le cercle gris et de rayon égal à la taille du secteur courant. Du coup, dans le code, nous aurons ceci dans le cas d’un dépassement sur le coin supérieur droit :

      for(int x = 0; x < sectorScale; x++) {
        for(int y = 0; y < sectorScale; y++) {
          currentPixelDistance = sqrtl( pow( sectorScale-x,2) + pow(-y-1,2) );
          // Pour économiser un peu de temps CPU on évite des calculs inutiles en s'assurant
          // que le pixel courant est dans une zone d'impression qui fait sens.
          // On réitérera ce test plus bas.
          if(currentPixelDistance < sectorScale) {
		...
          }
	 …
        }
      }

Dans la version actuelle du code une autre optimisation possible mais que je n’ai pas encore implémentée est de créer une matrice contenant toutes les valeurs utiles des racines carrées, ce qui nous octroiera un gain de temps énorme. En effet, la fonction sqrtl est très gourmande en temps CPU...

À présent, si l’on est dans une zone d’impression valide, on peut calculer l’angle que fait le pixel courant avec le coin qui nous intéresse, ici toujours le coin supérieur droit.

Notons que pour éviter les artefacts, on ajoute 1 ou -1 à la coordonnée courante, dans certains cas, pour éviter d’avoir une valeur nulle, ce qui produirait des angles doublons à l’origine de petits artéfacts visuels.

            currentPixelAngle = atan2((double) -y-1, (double) -sectorScale+x);

Après quoi, on met à l’échelle l’angle pour l’espace de transitionSpace

            newAngle = - PI2_12 + (( currentPixelAngle + PI_2) * PI2_3) / PI_2 ;

Duquel on va déduire les nouvelles coordonnées sur cet espace de transition

            newX = (int) (cos(newAngle) * scaledCurrentPixelDistance + halfTransitionSpaceScale);
            newY = (int) (-sin(newAngle) * scaledCurrentPixelDistance + halfTransitionSpaceScale);

Enfin, il n’y a plus qu’a prélever la valeur du pixel sur la zone de transition

               chunkIndex = this->scale - sectorScale + x + this->scale * y;
            this->localChunk[ chunkIndex ] += this->sign * transitionSpace[newX + newY * transitionSpaceScale] / this->step;
            this->UpdateMinMax(chunkIndex, this->localChunk);

Finalement pour la face courante du coin supérieur droit on a

      for(int x = 0; x < sectorScale; x++) {
        for(int y = 0; y < sectorScale; y++) {
          // ROYAUME COURANT
          currentPixelDistance = sqrtl( pow( sectorScale-x,2) + pow(-y-1,2) );
          // Pour économiser un peu de temps CPU on évite des calculs inutiles en s'assurant
          // que le pixel courant est dans une zone d'impression qui fait sens.
          // On réitérera ce test plus bas.
          if(currentPixelDistance < sectorScale) {
            scaledCurrentPixelDistance = currentPixelDistance * this->step;
            // À surveiller: les coordonnées passées à atan2 ne doivent jamais être nulles,
            // sinon cela produit des artefacts. D'où le -y-0.0001.
            currentPixelAngle = atan2((double) -y-1, (double) -sectorScale+x);
            newAngle = - PI2_12 + (( currentPixelAngle + PI_2) * PI2_3) / PI_2 ;
            newX = (int) (cos(newAngle) * scaledCurrentPixelDistance + halfTransitionSpaceScale);
            newY = (int) (-sin(newAngle) * scaledCurrentPixelDistance + halfTransitionSpaceScale);
            chunkIndex = this->scale - sectorScale + x + this->scale * y;
            this->localChunk[ chunkIndex ] += this->sign * transitionSpace[newX + newY * transitionSpaceScale] / this->step;
            this->UpdateMinMax(chunkIndex, this->localChunk);
          }
	…
        }
      }

En mode debug, pour un seul niveau de récursion on obtient visuellement ça

transitionSpaceFinal.png

Comme on le voit, le tampon imprimé en haut à droite est bien raccord! Pour terminer, on obtient bien une superbe cubemap, prête à l'emploi!

cubeMapFinal.png

En exécutant le code en condition normale, c'est à dire sans écrire dans un fichier, le code s’exécute relativement rapidement

anonyme@anonymoushost /home/http/dev/UNIVERSE/PoC/cubeMapping $ time ./cubeMapper 

real	0m0.428s
user	0m0.391s
sys	0m0.036s

Notons que la preuve de concept génère en fait six fois quatre secteurs de 256 pixel² (chaque faces est subdivisée en quatre). Ce qui fait environs 17ms par secteur. C'est un temps de génération tout à fait raisonnable mais qui devrait pouvoir être amélioré dans de futures versions, en effet dans la preuve de concept du Stamp Noise le temps d’exécution pour une surface de 256 pixel² était moitié moins long,

Pour découvrir la preuve de concept intégralement rendez-vous ici

À bientôt pour un prochain article !