IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Rendu de polygones


Sujet :

Mathématiques

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    53
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2006
    Messages : 53
    Points : 44
    Points
    44
    Par défaut 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 ).
    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 ^^

  2. #2
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    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).
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    53
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2006
    Messages : 53
    Points : 44
    Points
    44
    Par défaut
    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 ^^) =/

  4. #4
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par arcanis Voir le message
    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 Voir le message
    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 Voir le message
    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é.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    53
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2006
    Messages : 53
    Points : 44
    Points
    44
    Par défaut
    Citation Envoyé par Mac LAK Voir le message
    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 Voir le message
    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).

  6. #6
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par arcanis Voir le message
    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 Voir le message
    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.
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

  7. #7
    Membre du Club
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    53
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2006
    Messages : 53
    Points : 44
    Points
    44
    Par défaut
    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.

  8. #8
    Inactif  
    Avatar de Mac LAK
    Profil pro
    Inscrit en
    Octobre 2004
    Messages
    3 893
    Détails du profil
    Informations personnelles :
    Âge : 49
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Octobre 2004
    Messages : 3 893
    Points : 4 846
    Points
    4 846
    Par défaut
    Citation Envoyé par arcanis Voir le message
    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 Voir le message
    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 !
    Mac LAK.
    ___________________________________________________
    Ne prenez pas la vie trop au sérieux, de toutes façons, vous n'en sortirez pas vivant.

    Sources et composants Delphi sur mon site, L'antre du Lak.
    Pas de question technique par MP : posez-la dans un nouveau sujet, sur le forum adéquat.

    Rejoignez-nous sur : Serveur de fichiers [NAS] Le Tableau de bord projets Le groupe de travail ICMO

Discussions similaires

  1. rendu polygonal d'une image 3D
    Par arij25 dans le forum Images
    Réponses: 14
    Dernier message: 06/01/2011, 23h22
  2. Triangulation de Polygones
    Par seb_lisha dans le forum DirectX
    Réponses: 1
    Dernier message: 01/07/2003, 13h40
  3. [Algo] Point à l'intérieur d'un polygone ?
    Par kebby dans le forum C++Builder
    Réponses: 5
    Dernier message: 23/05/2003, 14h22
  4. Un objet rendu apparaît derrière un autre objet
    Par jamal24 dans le forum OpenGL
    Réponses: 2
    Dernier message: 01/05/2003, 21h47
  5. une ligne et un polygone convexe
    Par rekam dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 20/12/2002, 11h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo