Rendu de polygones

Version imprimable

08/12/2009, 12h24
arcanis

Rendu de polygones

Bonjour,
Je cherche actuellement a realiser le rendu final d'une carte en fil de fer. Pour ce faire, j'utilise actuellement un algorithme qui marche mais qui est bourrin, et qui consiste a parcourir chaque pixel de la fenetre, et d'y tester chaque polygone de la carte. Et ca pique quand la hauteur, la largeur ou le nombre de polygones est important ...
J'ai aussi pense a une autre facon peut-etre plus rapide qui serait de proceder a la pot de peinture : tracer les lignes qui entourent un polygone dans mon image, puis colorier les pixels entoures via ces lignes de facon recursive. Mais j'hesite encore sur la facon de l'implementer.
Et enfin, j'ai entendu parler de la methode du Scanline. De ce que j'en ai compris, il s'agit de faire un rendu ligne par ligne plutot que pixel par pixel. Mais n'y a t'il pas des imprecisions (du style pixel pas colorie) dues aux limites du trace de ligne ?
Je ne pose pas vraiment de question ici, j'essaie plutot de voir comment je pourrais faire un rendering un minimum performant (mon algo actuel ne reussit pas a afficher mon beau chateau cree pour les tests :calim2: ).
La methode du pot de peinture me parait interessante, qu'en pensez-vous ? Je ne l'ai pas vue documentee, donc c'est peut-etre un peu inquietant, mais j'aimerais bien l'essayer ^^
08/12/2009, 13h22
Mac LAK
Ton tracé semble s'approcher d'un ray-tracing basique, non ? Si oui, en effet, c'est bourrin (et pas forcément efficace...).

Quelques liens :
[ame]http://fr.wikipedia.org/wiki/Algorithme_du_peintre[/ame]

Z-buffer
Détermination des surfaces cachées

Pour le tracé lui-même, on en revient en fait à un tracé d'une projection de triangle au final. Tu as donc le [ame="http://fr.wikipedia.org/wiki/Rendu_scanline"]scanline[/ame], très pratique et relativement peu complexe à implémenter : il suffit en fait de partir d'un sommet, de tracer (virtuellement) deux segments vers chacun des autres sommets (par Bresenham notamment) et d'effectuer les scanlines entre les points. Quand un des deux premiers segments est "terminé", tu poursuis sur le 3ème segment du triangle, et ton remplissage sera alors complet sans consommer beaucoup de temps CPU.
Le [ame="http://fr.wikipedia.org/wiki/Flood_fill"]flood fill[/ame] (optimisé ou non) sera rarement performant par contre, et encore moins si tu as des polygones complexes (= pas QUE des triangles, donc).

Ce que je te conseille, donc :
- Décomposition de ta scène en triangles, si ce n'est pas déjà fait.
- Tu peux si besoin / nécessaire pré-trier les facettes (algo du peintre ou Z-buffer).
- Tracé par Z-buffer, en utilisant un tracé scanline pour chaque facette.
Enfin, pour les problèmes de "jointure" entre les polygones : si cela pose un réel souci, tu peux ajouter de l'anti-aliasing : par exemple, modifier l'algo de tracé de triangle pour y mettre un algorithme de tracé de segment de Xiaolin Wu à la place de celui de Bresenham (ce qui revient un peu à du multisampling), ou rester bourrin et utiliser de l'oversampling (= doubler la taille de l'image, puis la réduire par interpolation).
08/12/2009, 14h37
arcanis

Merci ! =)
Le Z-Buffer me parait interessant, mais il necessite de pouvoir connaitre la position de chacun des pixels inclus dans les polygones. Or meme si l'on considere qu'il s'agit uniquement de triangles, je n'ai pas trouve d'equation parametrique permettant de realiser cette operation ... =/
Y a-t-il une methode permettant de calculer, meme approximativement, les valeurs des differents points ? Parce qu'il semblerait qu'il faille la meme chose pour tous les autres algorithmes (meme le Scanline necessite de connaitre la profondeur si l'on souhaite appliquer une couleur differente en fonction de la profondeur, pour ne pas se retrouver avec une unique couleur unie qui rend le rendu encore moins lisible que le fil de fer ^^) =/
08/12/2009, 17h35
Mac LAK

Citation:

Envoyé par arcanis

je n'ai pas trouve d'equation parametrique permettant de realiser cette operation ... =/

Parce qu'il ne faut PAS utiliser d'équations paramétriques... Regarde la méthode de Bresenham que je t'ai citée : c'est elle que tu vas utiliser (en 3D) pour tracer ton triangle, y compris sur les scanlines. Accessoirement, c'est aussi à ce niveau-là que tu pourras calculer un ombrage de type Gouraud.

Citation:

Envoyé par arcanis

Y a-t-il une methode permettant de calculer, meme approximativement, les valeurs des differents points ?

Que veux-tu dire par "valeur" ? Son Z, ou sa couleur ?

Citation:

Envoyé par arcanis

Parce qu'il semblerait qu'il faille la meme chose pour tous les autres algorithmes

D'où l'utilisation d'un algo itératif et nativement discret, comme Bresenham, pour effectuer ton tracé. Une équation paramétrique serait bien trop coûteuse en temps CPU, et en plus, produirait des artefacts lors du tracé.
08/12/2009, 19h42
arcanis

Citation:

Envoyé par Mac LAK

Parce qu'il ne faut PAS utiliser d'équations paramétriques... Regarde la méthode de Bresenham que je t'ai citée : c'est elle que tu vas utiliser (en 3D) pour tracer ton triangle, y compris sur les scanlines. Accessoirement, c'est aussi à ce niveau-là que tu pourras calculer un ombrage de type Gouraud.

J'ai du mal a me representer comment fonctionne le scanline dans les faits ... est-ce que tu connaitrais une animation gif un peu comme celle sur la page wikipedia du flood filling ?

Citation:

Envoyé par Mac LAK

Que veux-tu dire par "valeur" ? Son Z, ou sa couleur ?

Son Z, a partir duquel je pense pouvoir determiner une couleur (plus Z est important et plus la couleur est blanche, rien de bien complique je pense - j'espere x).
08/12/2009, 20h01
Mac LAK

Citation:

Envoyé par arcanis

J'ai du mal a me representer comment fonctionne le scanline dans les faits ... est-ce que tu connaitrais une animation gif un peu comme celle sur la page wikipedia du flood filling ?

Pas à ma connaissance, désolé. Je verrais si je trouve quelque chose, mais ne t'attends pas à un miracle.

Citation:

Envoyé par arcanis

Son Z, a partir duquel je pense pouvoir determiner une couleur (plus Z est important et plus la couleur est blanche, rien de bien complique je pense - j'espere x).

Non, la coordonnée Z et la couleur n'ont aucun rapport à priori. La couleur se calcule en fonction de la couleur propre (intrinsèque) du triangle, modifiée par un éventuel ombrage qui tient compte de l'orientation de la facette par rapport à la caméra et à la (aux) source(s) de lumière. Tu peux faire un ombrage flat (le plus simple, une couleur par facette), un gouraud (une couleur par scanline, interpolée), ou un phong (une couleur par pixel, doublement interpolée). Au delà, on arrive dans le raytracing, le texturage ou les fonctions devant être câblées.
08/12/2009, 23h40
arcanis

Youki. Bon, bah je vais essayer de voir comment faire ca.
Sinon, j'ai trouve un site avec pas mal de demos de rendering : http://www.netgraphics.sk/scan-line-algorithm
C'est en java, et assez bien fait.

Notre prochain projet utilisant la 3d sera un raycaster, mais avoir fait ca devrait m'aider pas mal, deja ^^
Je suis quand meme impressionne par le temps necessaire pour tracer une scene, si l'on compare avec des jeux type Far Cry qui sont en temps reel. Comment est-ce qu'ils font, les malades qui ont concus le moteur graphique (et physique, puisque les collisions sont gerees au poil de cul) ? Vraiment impressionant.
09/12/2009, 10h12
Mac LAK

Citation:

Envoyé par arcanis

Sinon, j'ai trouve un site avec pas mal de demos de rendering : http://www.netgraphics.sk/scan-line-algorithm
C'est en java, et assez bien fait.

Effectivement, ça mérite d'être mis en bookmark, ce truc.

Citation:

Envoyé par arcanis

Je suis quand meme impressionne par le temps necessaire pour tracer une scene, si l'on compare avec des jeux type Far Cry qui sont en temps reel. Comment est-ce qu'ils font, les malades qui ont concus le moteur graphique (et physique, puisque les collisions sont gerees au poil de cul) ? Vraiment impressionant.

Ben ils utilisent une accélération 3D pour le rendu, donc ça décharge quand même énormément le processeur principal... Du coup, il a beaucoup, beaucoup plus de temps pour gérer le reste (communication réseau, IHM, IA, etc.) tout en conservant un rendu graphique nickel.

De même, tu as des techniques de "fourbe" pour gérer les collisions, comme les bounding boxes (volumes englobants), qui évitent d'avoir à gérer chaque paire de facette pour les collisions.
Pour l'affichage, tu as les distances de visibilité, la réduction dynamique de polygones, et surtout le texturage qui permet d'économiser BEAUCOUP de polygones (notamment si l'on ajoute la gestion du bump mapping par exemple).

Côté calculs "purs", tu peux aussi mettre un coup d'accélérateur en utilisant pleinement le matériel, par exemple les registres SSE d'un CPU Intel pour les calculs de normales ou les transformations 3D... Certes, ça ne va pas rendre tes calculs instantanés, mais à force d'optimisations plus ou moins lourdes, on finit par gagner un bon paquet de charge CPU.

Faut pas te leurrer : quel que soit le moteur 3D "commercial" que tu puisses trouver dans un jeu, si tu effectuais un rendu logiciel à 100%, tu n'aurais pas les mêmes performances du tout, et tu le trouverais nettement moins impressionnant également ! :mouarf: