Usine à gaz-on

Quel est le problème ?
Une couverture adaptative d'un height_field
Couverture des plaques, export POV-Ray
Téléchargement <----------------------- Si vous êtes vraiment très pressé, c'est là!
Documentation
Copie d'écran
Historique

Quel est le problème ?

La réalisation d'étendues herbeuses sous Pov-Ray se heurte à une difficulté majeure : l'occupation mémoire. Il est en effet courant de devoir utiliser des millions de brins d'herbe pour couvrir une étendue pas forcément gigantesque. Jusqu'ici, deux solutions permettaient de limiter la casse :

L'utilisation d'une texture imitant l'herbe. Le meilleur travail en ce sens est probablement celui de Rune Johannson. En dépit de son petit côté "Van Gogh", il permet d'obtenir des résultats convenables pour des étendues éventuellement vallonées, uniformes, à partir du moment où l'on n'y regarde pas de trop près et où le relief présente peu de sommets ou de bosses visibles.
L'utilisation d'un paquet, ou plaque, d'herbe, que l'on recopie pour couvrir un plan. C'est le principe d'un jeu de macros écrit par Gilles Tran, qui exploite le fait qu'une copie d'un objet mesh prend très peu de place. Ce système donne de bons résultats, même de près, sur une surface plane, au prix d'un temps de parsing assez long.

Une couverture adaptative d'un height_field

On se propose ici d'étendre le principe des macros de Gilles Tran pour permettre la couverture d'objets height_field. La méthode originelle n'est pas directement utilisable, puisque la couverture d'une surface bosselée avec des plaques planes ne permet pas de suivre les dénivellations. Le height_field est découpé en petits carrés, que l'on cherche à approcher par un sous-ensemble réduit de plaques non planes, quitte à les déplacer en hauteur ou à les tourner pour les adapter aux particularités de chaque petit carré. Cette méthode peut s'apparenter aux compressions à "dictionnaire" telles que l'algorithme célèbre de Lempel-Ziv-Welch dont le brevet qui a empoisonné la communauté informatique durant des années est tombé dans le domaine public depuis quelques jours ;-)

Le programme prend donc en entrée une image en nuances de gris, au format PNG, qui sera recalé sur une "profondeur" utile de 8 bits par couleur, ce qui suffit largement pour cette application. Il accepte aussi les images en 16 bits codées sur le rouge et le vert.

En pratique, les dimensions de l'image sont limitées à environ 1024x1024. Il est possible d'ouvrir des images plus grandes en augmentant la taille de la mémoire alouée à la VM Java, par exemple en utilisant java -Xmx256m -jar hfc.jar ce qui fait passer la mémoire à 256 Mo. Toutefois, ne pas perdre de vue que l'objectif est de placer des brins d'herbe, pas de faire un rendu très précis du terrain. Si hfc semble ne rien faire au chargement d'une image, c'est paobablement parce qu'elle est trop grande. Commencez donc par essayer avec une version plus petite, et ne revenez à une taille déraisonnable que si le besoin s'en fait vraiment sentir.

Deux paramètres sont donc nécessaires pour construire le dictionnaire : la taille des "plaques", et la tolérance autorisant l'assimilation d'une plaque à une autre. En règle générale, on peut dire que:

Plus les plaques sont grandes, moins la compression est utile, car il est probable que la totalité du height_field sera reconstituée à partir de plaques différentes. De même, si la tolérance est très stricte, on ne gagnera pas grand chose, sauf peut-être sur des parties très planes.
Des plaques trop petites peuvent conduire à un dictionnaire très réduit, donc à une forte compression, au prix de motifs répétitifs très voyants
Une tolérance trop faible peut conduire à faire disparaître de l'herbe sous la terre ou à avoir des touffes volant au-dessus du sol: il y a un compromis à trouver entre réduction du dictionnaire et réalisme du résultat

En pratique, il semble que des plaques de 8x8 pixels donnent des bons résultats, associés à une tolérance de l'ordre du quart de la hauteur moyenne des brins d'herbe.

Le résultat de cette première étape reste interne au programme, et est constitué d'une part d'un dictionnaire contenant les "plaques" nécessaires à la reconstitution du height_field, et d'autre part d'une table de correspondance associant chaque case du height_field à une plaque du dictionnaire et à la transformation (translation verticale, rotation) permettant de passer de l'un à l'autre.

Le programme indique le nombre de carrés de la grille, le nombre de plaques du dictionnaire, ainsi que le nombre de plaques du dictionnaires utilisées une seule fois dans la reconstitution : si ce nombre est trop élevé, il peut être intéressant d'augmenter la tolérance de la compression.

Couverture des plaques, export Pov-Ray

La seconde phase consiste à couvrir chaque plaque du dictionnaire de brins d'herbe, et à recopier cette plaque là où c'est nécessaire.

Plusieurs algorithmes sont disponibles, et d'autres peuvent être ajoutés moyennant un peu de programmation en java. Un module permet une exportation très basique sous forme de paires de triangles croisés à la base, à raison d'une paire par brin d'herbe. Un second module est inspiré de la macro MakeBlade de Gilles Tran. Ces deux modules produisent des fichiers Pov-Ray et utilisent la représentation mesh2, économisant de la place et réduisant considérablement le temps de parsing. A titre d'exemple, une falaise couverte de trois millions de brins "basiques" se lit en 7 secondes.

Une indication de la taille du fichier exporté est fournie avant l'exportation.

Téléchargement

Pour des raisons de portabilité et de rapidité de développement, le programme est écrit en Java. Le temps de calcul est en général très raisonnable, de l'ordre de quelques secondes à quelques minutes au maximum. Il est nécessaire de disposer d'une machine virtuelle Java complète (version 1.4), et de l'extension Java3D (n'importe laquelle devrait aller). Si vous utilisez encore windows, il est fortement recommandé de télécharger une JVM qui fonctionne, et de ne pas se contenter de celle éventuellement fournie d'origine.

Le programme est librement distribuable dans les conditions prévues par la GNU General Public License, version 2 ou ultérieure à votre choix.

C'est là: hfc.jar. Chargez l'archive (~75 k), et double-cliquez dessus, ou tapez java -jar hfc.jar pour lancer le programme.

Les sources du programme sont également disponibles pour ceux que ça intéresse: hfc_src.zip

Copie d'écran

Scrinechotte [16k]

Historique (très approximatif)

0.1.0: Première version publiée
0.1.1: Possibilité d'utiliser des formats non carrés, traduction en français, réglage de la hauteur des brins
0.1.2: Correction de bugs, barre d'état
0.1.3: Modes de compression complexe/simplifié, prise en compte de la pente
0.1.4: Refonte du calcul de pente.
0.1.5: Achèvement du module de brins d'herbe courbes
0.1.6: Vérification de la présence de Java3D, gestion des HFs 16 bits en rouge+vert, système de touffes (merci Marc!).
0.1.7: Gestion des masques de probabilités.
0.1.8: Correction de bugs mineurs.
0.1.9: Correction de bugs mineurs, version néerlandaise (merci Thomas!).