Discussion :

[franklin626]

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 :-)

[pseudocode]

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.

[franklin626]

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?

[pseudocode]

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.

[franklin626]

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!

[pseudocode]

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 ?

[franklin626]

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

[franklin626]

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

ça n'a pas l'air trivial

[pseudocode]

La formulation de départ est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 }

[franklin626]

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.

[pseudocode]

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) ).

[franklin626]

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?

[pseudocode]

Computer graphics Par James D. Foley, Andries Van Dam, Steven K. Feiner, John F. Hughes

[franklin626]

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!

[pseudocode]

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.