Génération procédurale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique image illustrant le jeu vidéo
Cet article est une ébauche concernant l’informatique et le jeu vidéo.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En informatique, la génération procédurale ( ou le modèle procédural) est la création de contenu numérique (niveau de jeu, modèle 3D, dessins 2D, animation, son, musique, histoire, dialogues) à une grande échelle (en grande quantité), de manière automatisé répondant à un ensemble de règles définis par des algorithmes[1],[2]. Le modèle procédural s’appuie sur les informations d'un algorithme pour construire[3]

La méthode de génération procédural trouve application dans le domaine principalement du jeu vidéo ainsi que du cinéma. Dans le domaine du jeu vidéo, il y a la notion de création à portée artistique ainsi que de conception de contenu à grande échelle, c'est pourquoi la notion de génération procédurale s'associe avec un contrôle à posteriori par l'artiste qui modifie l’environnement (simulation, modélisation) (aléatoire contrôlé)[4].

La génération procédural est une catégorie des techniques de modélisation (les deux autres étant : la Simulation informatique et la Modélisation par esquisses ou par édition) permettant la création de monde virtuel cohérent[5].

Génération par esquisses[modifier | modifier le code]

La génération par esquisses consiste à modéliser en contrôlant la forme du relief[6],[7]. Cela définit les éléments important (vallées, crêtes), le système construit alors le sol (génère le relief) à parti de l'empreinte (ligne pour vallées ou crêtes) de la montagne associé a ses lignes de vallées ou de crêtes, un contrôle à posteriori peut se faire par l'utilisateur[5]

Les applications de génération procédurale[modifier | modifier le code]

Génération de paysages[modifier | modifier le code]

Article détaillé : Générateur de paysage.

La génération du paysage dans la génération procédurale tiens une place importante dû fait de son importance visuelle à toutes les échelles, de l'arrière-plan jusqu'au premier plan[1]. La génération de cartes de hauteur (heightmap) sont basées sur le bruit de Perlin ou le midpoint displacement (Fournier)[8].

Approche géologique[modifier | modifier le code]

L’érosion est l’élément centrale dans la générale de paysage d'un point de vue géologique, dans sa dimension hydraulique (vallées) ou thermique (effondrement de zones)[9],[1]. Pour l'application, de ses méthodes d'érosion il existe différentes approche : l'approche fractale[10],[11] ou diffusion d'une contrainte donnée par l'utilisateur[12]. Ces approches peuvent être appliquées avec différents niveau de précision de celles peu précise (par colonnes d'eau [13]), a des plus précises[14]. Les fractales sont associés a des algorithmes comme celui de diamond-square (pouvait prendre en compte les rivières et crètes)[15] ou de square scheme[16] qui sont les plus connus. La technique de Milgram est d'utiliser le Bruit de Perlin avec une érosion hydraulique et thermique.

Pour crée de nouvelle forme a partir d'autre méthode, notamment dû a la limitation de la height map il existe le modèle de colonne permettant de gérer plusieurs strates de roche[17], qui permet la création de de tunnels et de grottes[18].

Information sur les méthodes de génération (voir ref)[19],[20].

Génération de terrains complexes[modifier | modifier le code]

La création de détails répond au besoins d'avoir une scène avec le maximum de précision mais d'éviter de représenter toutes cette variété par un travail manuelle, l'enjeux est donc de l'automatiser[21] L'enjeux de la création de paysages complexes est d'y apporté un réalisme plus important, avec la prise en compte des interactions entre les éléments, d'adaptation à leur environnement[5]. Les formes complexes comprennent les surplombs, des arches, des grottes, des couches de matières, l'empilement de pierre, les routes urbaines et de campagnes, et les espaces urbains etc...[5]. Pour une haute précision dans l'affichage de ses éléments dans une scènes par exemple pour les routes, la méthode utilisée consiste à faire des fonctions de coût pondérées par les caractéristique du terrain traversées (fonction de la pente, du niveau, de la matière traversé (génération de ponts, bitume, ponts, tunnels, barrière est coûteux)).

Végétation, Écosystème[modifier | modifier le code]

La végétation et l'écosystème est défini par l'ensemble des arbres et plantes interagissant avec l'environnement. Les plantes représente un défi à représenter du fait de leur complexité d’éléments (racines, troncs, branches, fleurs fruits, feuilles)[5]. Il existe différentes techniques pour leur création avec des embranchement (ramification) à chaque niveau, ou bien avec l'utilisation d'automates cellulaires pour définir les branches d'un arbre[5],[22],[23],[24],[25]. Le réalisme des structures de plantes sont notamment possible grâce a des diagrammes de structures de plantes et de fleurs[26], combiner à une hiérarchie de plans[27]. Des plantes grimpantes peuvent être crée en fonction de l’environnement lui-même, et non plus de manière indépendante, en gérant la distribution des racines en fonction de l'eau dans le sol[5]. Pour la distribution de ces éléments il existe plusieurs moyens : avec la simulation d'une croissance des plantes avec compétition entre elle, avec une carte de densité ou avec la méthode de pavage (éfficace pour de grande échelle, en distribuant par groupe et par duplication) avec la répétition d'une instance[5]. Une autre technique consistant à utiliser plusieurs photographies avec de la simulation de particules peut générer des arbres avec un volume de voxels[21].

Il existe des méthodes pour animer le comportement des plantes qui se scinde en deux objectifs, chercher la lumière et conquérir le plus d'espace. Un des moyens de simuler l'écosystème est de représenter les éléments avec un point et une taille du point, lorsque les points se touche c'est la plus grande qui reste l'autre disparaît lorsqu'elle atteindre son espérance de vie et de la combiner avec une règle de groupe, qui fait que la même famille de plantes s'installe par groupe (en mourant d'autres apparaissent à côté d'elle), donc propagation de l'espèce mais cette méthode n'est pas bien représentatif car exclusif (aucune pousse n'est admise prêt d'une grand arbre)[5]. Le contrôle de ce processus peut ce faire avec des cartes de densité qui est fonction de la distribution de l'eau, et la capacité d'absorption par plante[5].

Paysages Urbains[modifier | modifier le code]

Un paysage urbains est constitué d'un réseaux de rues, de routes avec des blocs de bâtiments, de quartiers[5],[21].

Génération de formes complexes[modifier | modifier le code]

La génération de terrains complexes multimatériaux (par exemple : une arche de roche près de la mer avec du sable au sol et de l'herbe en haut de la falaise)[5] est possible mais utilise beaucoup de mémoire, et n'est pas possible sur une très grande échelle. Il y a l'édition de couche de roches, de fissures, de grottes, d'érosion locale, du phénomène de stabilisation, de lacs, et plans d'eaux naturel[28]. La génération de route pour s'adapter aux caractéristiques du terrain peut répondre à des contraintes de coût du trajet, le terrain doit avoir une valeur pondérée par ses caractéristiques (pente du terrain, densité de végétation, profondeur de l'eau, courbure de route, hauteur du sol, profondeur dans le sol). La route se crée avec différentes méthodes pour trouver le « plus court chemin », et peut être utilisé pour la génération de tunnels et ponts[5].

Génération de texture[modifier | modifier le code]

Le Procedural Shading est une technique de génération de texture.

Article détaillé : Texture procédurale.

Animation procédurale[modifier | modifier le code]

Article détaillé : Animation procédurale.

Modélisation procédurale[modifier | modifier le code]

Article détaillé : Modélisation procédurale.

Programmation procédurale[modifier | modifier le code]

Article détaillé : Programmation procédurale.

Applications[modifier | modifier le code]

Jeux vidéo[modifier | modifier le code]

L'utilisation dans le jeu vidéo en massif, notamment dans le jeu vidéo indépendant permettant de répondre a des attentes spécifique aux joueur, notamment la rejouabilité[4]. Cette idée est souvent liée aux applications de synthèse d'image et au level design dans les jeux vidéo. Dans le jeu vidéo la génération procédurale correspond à l'application d'un aléatoire contrôlé (ou d'un faux aléatoire)[1] régit par des règles définies dans le but de générer quelque chose d'unique mais en conservant une cohérence. L'objectif étant de pouvoir crée une très grande quantité de contenu tout en assurant une cohérence de l’environnement, en lui donnant un aspect unique[4]. L'enjeu étant d'un point de vue du game design de proposer un nombre infini de niveaux unique tout en contrôle l'équilibrage de la difficulté pour le joueur. La génération d'objets par fragments permet de multiplier la variété des scènes et de leur réalisme[21].

Contrainte spécifique lié au jeux vidéo[modifier | modifier le code]

La génération procédurale dans le cadre du jeu vidéo impose des contraintes à l'utilisation de cette méthode, en effet, le rendu des calculs de la génération procédurale doit permettre d'avoir d'avoir un affichage en temps réelle à l’écran (output), dans le cas contraire cela cassera l'immersion du joueur dans le jeu vidéo (lag, bug, glitch, bug graphique).

Développement de la technologie dans le jeu vidéo[modifier | modifier le code]

[29]

Films[modifier | modifier le code]

la génération procédurale est souvent utilisé dans le cinéma pour créer rapidement des espaces visuellement intéressants et précis. Ceci est vrai pour une grande variété d'applications. L'application la plus répandue c'est celle de l' « usine imparfaite » où les artistes peuvent rapidement générer un grand nombre d'objets similaires. Ce processus ce fait pour un souci de réalisme, dans la vraie vie, deux objets ne sont jamais exactement semblables. Par exemple, un artiste peut modéliser un produit pour une tablette de magasin d'épicerie, puis il peut générer — à l'aide de cette méthode — un grand nombre d'objets similaires pour remplir l'étagère.

MASSIVE est une animation haut de gamme par ordinateur et un logiciel d'intelligence artificielle utilisée pour générer une foultitude d'effets visuels pour le cinéma et la télévision. Il a été développé pour générer automatiquement les soldats — dans une bataille qui en comptaient des centaines de milliers — dans Le Seigneur des Anneaux[réf. nécessaire].

Le Coherent noise) peut être extrêmement important dans flux de travail procédural pour film. Le Simplex noise est souvent plus rapide avec moins d'artefacts, mais une fonction plus ancienne bruit de Perlin peut aussi être utilisé. Coherent noise, dans ce cas, se réfère à une fonction qui génère de pseudo-aléatoire en n dimensions.

Développement de la technologie au cinéma[modifier | modifier le code]

Exemple de génération procédurale[modifier | modifier le code]

L'un des premiers jeu utilisant cette technologie est le jeu Élite (sorti en 1984), permettant aux joueurs d'explorer 8 galxies contenant 256 systèmes solaires, soit 2500 mondes, le tout tenant sur une disquettes de 20 Ko de mémoire[30]. Ce jeu utilise des formules mathématiques précises comme la suite de Fibonacci (créée par le mathématiciens Leonardo Fibonacci en 1202)[31],[32]. Dans le jeu Minecraft, lea génération procédurale est un des éléments au coeur du processus de developpement de Notch pour son jeu, en ajoutant au fur et a mesure une meilleur cohérence a l'univers, et une plus grand diversité (création de biomes, de temps différents, de rivières, de villages,de donjons etc.)[33].

Application de la génération procédurale[modifier | modifier le code]

Dans le jeu vidéo[modifier | modifier le code]

Ressources de base[modifier | modifier le code]

Base Mathématique[modifier | modifier le code]

  • La génération procédurale utilise un large nombre d'outils mathématiques dans le processus de création de contenu de la génération procédural notamment le Diagramme de Voronoï (qui y détermine a une étape la zone d'influence d'un point), il peut être utilisé pour y mettre des valeur de vitesse (représentant la pression) pour y simuler les montagnes[2],[37].
  • La suite de Fibonacci (créée par le mathématiciens Leonardo Fibonacci en 1202) est utilisé pour la création de nombre aléatoire (faussement aléatoire).
  • Les fractales avec le mouvement Brownien fractionnaire peut permettre de crée des cartes de hauteur (heightmap)[2] pour les rivières et montagnes par exemple (érosion).

Base Technique[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a, b, c et d http://indius.org/dossiers/generation-procedurale-jeu-video/
  2. a, b et c http://www.di.ens.fr/~bouillar/Stages/Rapports/rapport_Michel.pdf École Normale Supérieure, Département d'Informatique, Rapport de Stage L3 - Génération procédurale de paysages à partir de cartes vectorielles - Intégration d'une mini-simulation géologique par Élie MICHEL le 29 Août 2014
  3. https://tel.archives-ouvertes.fr/tel-01196438/document
  4. a, b et c http://indius.org/dossiers/generation-procedurale-jeu-video/
  5. a, b, c, d, e, f, g, h, i, j, k, l, m et n http://liris.cnrs.fr/~apeytavi/these/Thesis.pdf https://tel.archives-ouvertes.fr/tel-00841373/document Thèse Université de Lyon - Génération procédurale de monde par Adrien PEYTAVIE de 2010
  6. J. M. Cohen, J. F. Hughes, and R. C. Zeleznik. Harold : a world made of drawings. In Proceedings of the 1st international symposium on Nonphotorealistic animation and rendering, pages 83 90, 2000.
  7. N. Watanabe and T. Igarashi. A sketching interface for terrain modeling. In ACM SIGGRAPH Posters, page 73, 2004.
  8. Fournier, A., Fussell, D., & Carpenter, L. (1982). Computer rendering of stochastic models. Communications of the ACM, 25(6), 371-384
  9. Musgrave, F. K., Kolb, C. E., & Mace, R. S. (1989, July). The synthesis and rendering of eroded fractal terrains. In ACM SIGGRAPH Computer Graphics (Vol. 23, No. 3, pp. 41-50). ACM.
  10. B. B. Mandelbrot. The Fractal Geometry of Nature. W. H. Freeman & Co Ltd, 1982.
  11. Pytel, A., & Mann, S. (2013). Self-organized approach to modeling hydraulic erosion features. Computers & Graphics, 37(4), 280-292
  12. Hnaidi, H., Guérin, E., Akkouche, S., Peytavie, A., & Galin, E. (2010, September). Feature basedterrain generation using diffusion equation. In Computer Graphics Forum (Vol. 29, No. 7, pp. 2179-2186). Blackwell Publishing Ltd.
  13. Beneš, B., & Forsbach, R. (2002). Visual simulation of hydraulic erosion
  14. Krištof, P., Beneš, B., Křivánek, J., & Št'ava, O. (2009, April). Hydraulic erosion using smoothed particle hydrodynamics. In Computer Graphics Forum (Vol. 28, No. 2, pp. 219-228). Blackwell Publishing Ltd.
  15. G. S. P. Miller. The definition and rendering of terrain maps. In Proceedings of ACM SIGGRAPH, pages 39–48, 1986
  16. A. Fournier, D. Fussell, and L. Carpenter. Computer rendering of stochastic models. Communication of the ACM, 25(6) :371–384, 1982.
  17. Beneš, B., & Forsbach, R. (2001). Layered data representation for visual simulation of terrain erosion. In Computer Graphics, Spring Conference on, 2001. (pp. 80-86). IEEE.
  18. Št'ava, O., Beneš, B., Brisbin, M., & Křivánek, J. (2008, July). Interactive terrain modeling using hydraulic erosion. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (pp. 201-210). Eurographics Association.
  19. Natali, M., Lidal, E. M., Viola, I., & Patel, D. (2013). Modeling terrains and subsurface geology. Proceedings of EuroGraphics 2013 State of the Art Reports (STARs), 155-173.
  20. Smelik, R. M., De Kraker, K. J., Tutenel, T., Bidarra, R., & Groenewegen, S. A. (2009, June). A survey of procedural methods for terrain modelling. In Proceedings of the CASA Workshop on 3D Advanced Media In Gaming And Simulation (3AMIGAS) (pp. 25-34).
  21. a, b, c et d https://tel.archives-ouvertes.fr/tel-00843000/document Nicolas Marechal. Génération de contenu graphique - Université Claude Bernard - Lyon I, 2010.
  22. Stefan Bornhofen and Claude Lattaud. Competition and evolution in virtual plant communities : a new modeling approach. Natural Computing : an international journal, 8(2) :349 385, 2009.
  23. Bedrich Bene² and Erik Uriel Millán. Virtual climbing plants competing for space. In Proceedings of the Computer Animation, page 33, 2002.
  24. N. Greene. Voxel space automata : modeling with stochastic growth processes in voxel space. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques, pages 175 184, 1989.
  25. Wojtek Palubicki. Fuzzy Plant Modeling with OpenGL- Novel Approaches in Simulating Phototropism and Environmental Conditions. 2007.
  26. T. Ijiri, S. Owada, M. Okabe, and T. Igarashi. Floral diagrams and inflorescences : interactive flower modeling using botanical structural constraints. ACM Transaction on Graphics, 24(3) :720–726, 2005.
  27. T. Ijiri, S. Owada, and T. Igarashi. Seamless integration of initial sketching and subsequent detail editing in flower modeling. Computer Graphics Forum, 25(3) :617–624, 2006.
  28. http://www.gamasutra.com/blogs/MatthewKlingensmith/20130811/198049/
  29. http://www.gamasutra.com/view/feature/174311/
  30. http://www.numerama.com/sciences/133517-la-generation-procedurale-ou-comment-le-jeu-video-devient-infini.html
  31. https://www.youtube.com/watch?v=t4V4e-8TGnc
  32. http://www.numerama.com/sciences/133517-la-generation-procedurale-ou-comment-le-jeu-video-devient-infini.html
  33. http://notch.tumblr.com/post/3746989361/terrain-generation-part-1
  34. (en) « VANISH », sur VANISH Horror Game
  35. (en) « Team Junkfish Monstrum », sur teamjunkfish.com
  36. (en) « Monstrum », sur giantbomb.com
  37. http://www.gamasutra.com/blogs/MatthewKlingensmith/20130811/198049/
  38. Manuel Gamito and F. Kento Musgrave. Procedural landscapes with overhangs. In 10th Portuguese Computer Graphics Meeting, pages 33-42, 2001.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Domaine d'application procédurale
Technique prodédurale

Liens externes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]