Projet image 2014 : Génération procédurale de forteresses

De Ensiwiki
Aller à : navigation, rechercher
Project schedule.png
Titre du projet Projet image 2014 : Génération procédurale de forteresses
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Marie-Paule Cani, Arnaud Emilien



L'équipe

BENTROUDI Galaad (MMIS)

BLERON Alexandre (MMIS)

MEYRON Jocelyn (MMIS)

TRAN QUANG Son (MMIS)

Contexte

De nos jours, les infographistes et concepteurs de mondes virtuels souhaitent toujours créer plus de contenu avec toujours plus de détails. Cela s'avère laborieux, répétitif et coûteux. Pour résoudre ces problèmes, des techniques de génération procédurales ont émergées. Leurs principes est de générer du contenu à l'aide d'algorithmes par exemple en répétant des motifs ou en transformant des volumes en d'autres formes. Beaucoup de travaux ont été réalisés dans ce domaine mais encore peu de travaux se sont intéressés à la gestion de contraintes extérieures liées par exemple à la morphologie du terrain (élévation, présence de cours d'eau...).

Problématique

Notre objectif est de générer de manière procédurale une forteresse en tenant compte de contraintes liées au terrain, et à l'aide de grammaires proche des L-systèmes [1].

Notre forteresse présente plusieurs éléments clefs:

- la muraille, avec ses créneaux, ses tours et sa porte

- les bâtiments à l'intérieur: donjon, maisons, etc

- un réseau de chemins

Vue d'ensemble de la forteresse

Grammaire

L'utilisateur est invité à écrire dans un fichier texte un ensemble de règles de génération. Voici un exemple:

   // Extrusion
   35 : WallsTopSideUp -> extrude(1) CrenelTop;
   // Splitting
   352 : CrenelTop -> splitEqually(Z, 3) CrenelTopSplit; 
   // Contraintes even/odd
   3533 : CrenelTopSplit -> Crenels : { even };
   3534 : CrenelTopSplit -> epsilon : { odd };
   // Splitting avancé 
   3535 : Crenels -> splitRepeat(X, (2.0,1.0), -1, Begin) Crenels0;
   3536 : Crenels0 ->  show : { even };
   3537 : Crenels0 -> epsilon : { odd };

On peut observer la syntaxe suivante:

   indice : Prédecesseur -> operation( paramètres ) Successeur* : {contrainte} : poids ;

Les contraintes permettent à l'utilisateur d'avoir plus de controle sur le résultat, notamment s'il veut sélectionner par exemple certaines parties à afficher et pas d'autres.

Les poids représentent des probabilités que l'on associe aux règles, en vue de créer des résultats non deterministes, pouvant changer à chaque régénération de la forteresse.

L'exemple précédent est le morceau d'une grammaire qui permet d'obtenir des créneaux sur les remparts:

Créneaux

Muraille

Pour construire la muraille en s'adaptant au terrain, nous sommes parvenus à une methode donnant des resultats convaincants:

1. Application d'un filtre passe-bas (Gaussien, bi-dimensionnel) sur la heightmap, afin de supprimer les petite variations de pentes.

2. Subdivisions des murs, en cherchant les point de variations brusques.

3. Rectification des longueurs des sections de murs, afin d'éviter les sections trop courtes.

4. Elévations des points de subdivision pour adoucir les pentes trop raides.

5. Enfoncement des murs dans le sol pour éviter les éventuels espaces vides sous la muraille.

Placement des Maisons

Pour placer les maisons, on procède en trois étapes :

- Génération de graines de maisons

- Placement des chemins (voir partie suivante)

- Placement et orientation des fondations des maisons

En ce qui concerne la génération des graines de maisons, on génère des points aléatoires dans la muraille. On rejette les points vérifiant les contraintes suivantes :

- points situés sur une pente trop raide

- afin d'avoir des groupements de maisons, on ajoute un coût de proximité qui attire les maisons entre elles mais pas trop pour éviter qu'elles se collisionnent

Pour le placement et l'orientation des fondations, on s'inquiète des collisions avec les autres maisons et la muraille ainsi que de la position par rapport au chemin le plus proche.

Maisons et chemins à l'intérieur de la forteresse

Construction des Chemins

Pour la construction des chemins, on utilise un algorithme de recherche de plus court chemin (A*) couplé à une matrice de fréquentation pour inciter les chemins à être réutilisés. Nous symbolisons la pente par un coût de déplacement plus élevé et restreignons le périmètre de recherche à l'enceinte de la muraille.

Le résultat se présente sous la forme d'un réseau de chemins, certains étant plus larges de par leur fréquentation plus importante.

Chemins

Bibliographie

[1] - Procedural Modeling of Buildings : Peter Wonka, Simon Haegler, Andreas Ulmer, Luc Van Gool, K. U. Leuven

[2] - Procedural Generation of Villages on Arbitrary Terrains : Arnaud Emilien, Adrien Bernhardt, Adrien Peytavie, Marie-Paule Cani, Eric Galin