+ Répondre à la discussion
Affichage des résultats 1 à 15 sur 15
  1. #1
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut clipping, comment obtenir un rendu fidèle?

    Bonsoir, voila maintenant quelques jours que je cherche un moyen d'obtenir un rendu fidèle pour le clipping de lignes.

    Je m'explique mieux : lorsque je clippe une ligne par un rectangle (avec Cohen-sutherland en l'occurence), j'obtiens (généralisons) 2 nouveaux points.

    Avec ces deux points, j'appelle mon algo incrémental de Bresenham mais je n'obtiens pas un rendu exact de ligne découpée!

    Je pense que le problème est bien connu des gens qui connaissent les méthodes de clipping, et pourtant je n'ai rien trouvé sur le net! (si, j'ai trouvé un article écrit par un russe sur plusieurs sites américains mais l'accès est payant : premier résultat sur google pour "Bresenham’s Line Generation Algorithm with Built-in Clipping").

    Y a-t-il un moyen réalisable d'arranger ça? Comment dois-je initialiser mon algo de bresenham? Est-ce que cela a une influence seulement sur le début du tracé? L'ensemble du tracé?

    D'avance merci, je dois résoudre ce problème :-)

  2. #2
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    A cause du clipping (et de la discrétisation) la pente de la nouvelle droite n'est pas forcément la meme que l'ancienne. Pour compenser cela, il suffit de calculer la pente avec les coordonnées originales (avant clipping).

    Suivant ton algo de bresenham il peut y avoir également des problèmes liés à la valeur initiale de l'erreur ("decision value"). Il vaut mieux utiliser la technique du midpoint.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut Merci, mais une petite précision

    Bonjour, entendu, je vais une première fois essayer
    de changer la pente pour celle d'origine.

    Par contre, je n'ai pas compris le second point.

    J'utilise l'algorithme incrémental de Bresenham qui n'utilise que des entiers.

    S'agit-il du midpoint dont tu parles? Ou est-ce que le midpoint agit toujours sur des reels?

    Sinon est-ce impossible d'obtenir le rendu fidele avec l'algo incrémental sur les entiers?

  4. #4
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par franklin626 Voir le message
    Par contre, je n'ai pas compris le second point.
    Lors du clipping, les nouvelles coordonnées "idéales" des point de départ/arrivée ne sont pas forcément entières.

    Si la ligne (x0,y0)-(x1,y1) est clippée par le bord gauche du rectangle (xmin,ymin,xmax,ymax) => le point de départ de la droite "clippée" est de la forme (xmin, yclip).

    La valeur de yclip "ideale" est un rationnel et pas un entier => la valeur initiale de l'erreur n'est pas zéro, comme dans le cas classique de l'algo de bresenham.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut

    D'accord, merci, là je vois le problème.
    Maintenant, comment résoudre :-)

    Dans mon cas d'algorithme sur les entiers, je ne vois pas bien comment initialiser mon erreur à autre chose que 0.

    Je n'arrive pas à distinguer les cas lors de mon appel à mon algo de Bresenham.

    Pouvez-vous me donner encore des pistes?

    Merci!

  6. #6
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par franklin626 Voir le message
    D'accord, merci, là je vois le problème.
    Maintenant, comment résoudre :-)

    Dans mon cas d'algorithme sur les entiers, je ne vois pas bien comment initialiser mon erreur à autre chose que 0.

    Je n'arrive pas à distinguer les cas lors de mon appel à mon algo de Bresenham.

    Pouvez-vous me donner encore des pistes?

    Merci!
    Je ne me suis jamais amusé a faire les calculs, mais en repartant de la formulation de base de l'algo de Bresenham ca doit etre possible.

    Au fait, pourquoi tu fais tout cela ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut

    Je fais une petite interface minimale de dessin, du genre paint.

    La différence est qu'on utilise une "toolglass". En cliquant au travers, on peut modifier/créer diverses formes. On utilise deux souris pour faire ça.

    C'est assez nouveau dans le principe les toolglass mais ça permet de gagner du temps.
    La fréquence des actions de l'utilisateur est optimisée

  8. #8
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut

    je cherche toujours une aide pour mon initialisation de l'erreur dans Bresenham :-)

    ça n'a pas l'air trivial

  9. #9
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    La formulation de départ est :
    Code :
    1
    2
    slope = (y1-y0)/(x1-x0) 
    y = slope * (x-x0) + y0 +0.5
    On s'interesse à la position de "y" pour x = xmin (le clipping gauche):
    Code :
    y = slope * (xmin-x0) + y0 + 0.5
    Le but est de connaitre la partie fractionnaire de ce "y".


    Sinon, en première approximation, on peut se contenter de trouver l'erreur qui nous permet de passer par les pixels clippés (xmin,ymin) et (xmax,ymax) tout en utilisant la pente originale de la droite (y1-y0)/(x1-x0) :

    Code :
    1
    2
    3
    ymin = Partie Entiere{ (y1-y0)/(x1-x0) * (xmin-x0) + y0 + 0.5 + error }
    ymax = Partie Entiere{ (y1-y0)/(x1-x0) * (xmax-x0) + y0 + 0.5 + error }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  10. #10
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut

    Ok, merci beaucoup, je vais déjà faire une première réflexion sur le second point que tu m'as expliqué.

    Tu parlais tout d'abord d'obtenir la partie fractionnaire de y, mais mon erreur en entrée de bresenham est necesairement entiere. (En effet, il y a une convention dans mon code qui requiert une erreur entiere pour le choix d'un pixel si le midpoint dit qu'on peut en choisir deux indifferemment.)

    A chaque deplacement axial dans mon bresenham, je réactualise l'erreur +/- Dx/Dy.

    Avant mon post sur ce forum, Dx/Dy etaient les differences apres clipping. Maintenant, j'utilise les différences d'origine.

  11. #11
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par franklin626 Voir le message
    Tu parlais tout d'abord d'obtenir la partie fractionnaire de y, mais mon erreur en entrée de bresenham est necesairement entiere. (En effet, il y a une convention dans mon code qui requiert une erreur entiere pour le choix d'un pixel si le midpoint dit qu'on peut en choisir deux indifferemment.)
    Oui, c'est une optimisation de l'algo.

    slope = dy/dx
    y = slope * (x-x0) + y0 + 0.5

    Durant le tracé incrémental, ce qui nous intéresse c'est de savoir si la partie fractionnaire est supérieur/inférieur a 1 afin de choisir le pixel "y" ou "y+1". Par récurrence, on calcule la partie fractionnaire du pixel "n" a partir de la partie fractionnaire du pixel "n-1":

    Frac(0) = 0.5
    Frac(n) = Frac(n-1) + slope

    Si c'est inférieur a 1 on choisit le pixel "y", si c'est supérieur a 1 on choisit le pixel "y+1" ( et donc on retranche 1 de Frac(n) ).

    Pour passer en calcul entier, on fait un changement d'axe (on retranche 1) et un changement d'echelle (on multiplie par 2*dx):

    Frac(0) = (0.5-1)*2*dx = -dx
    Frac(n) = Frac(n-1) + slope*2*dx = Frac(n-1) + 2*dy

    Si c'est inférieur a 0 on choisit le pixel "y", si c'est supérieur a 0 on choisit le pixel "y+1" ( et donc on retranche 2*dx de Frac(n) ).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut

    Merci!

    je comprends ce que tu as écrit, mais je n'arrive toujours pas à rassembler les morceaux.
    Désolé si la réponse est effectivement dans tes posts...

    Apres clipping, je garde bien la pente originale -> OK
    Les points de depart et d'arrivée ne sont pas forcement corrects -> a regler
    L'erreur "entiere" dans mon algo n'est pas forcement bien initialisée -> a regler


    Deja mon soucis, c'est que j'arrive pas a differencier les cas types.


    PS : aurais-tu une source intéressante sur laquelle je pourrais m'appuyer?

  13. #13
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Computer graphics Par James D. Foley, Andries Van Dam, Steven K. Feiner, John F. Hughes
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  14. #14
    Nouveau Membre du Club
    Inscrit en
    décembre 2007
    Messages
    120
    Détails du profil
    Informations forums :
    Inscription : décembre 2007
    Messages : 120
    Points : 31
    Points
    31

    Par défaut Un grand merci

    Un grand merci pour ton intervention de qualité. Il me semble avoir vu cet ouvrage cité ça et là, je vais me le procurer.


    Merci dev'.com, continuez comme ça!

  15. #15
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 42
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par franklin626 Voir le message
    Il me semble avoir vu cet ouvrage cité ça et là, je vais me le procurer.
    Le lien que j'ai donné t'amène sur google books, sur la page qui t'intéresse.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •