Licence d'Informatique

340 - Informatique Graphique


Devoir 1 - à rendre le 29 mars 1995

 

RASTéRISATION DE PARABOLE

Le devoir consiste à implémenter un algorithme de rastérisation de parabole.

L'équation de la parabole est

y - y0 = a (x - x0)2

avec a > 0 et a = p/q, p et q entiers.

La parabole est définie par deux points : son sommet (x0, y0) et un autre point appartenant à la parabole. On utilisera l'algorithme du point médian. Il n'est pas nécessaire d'utiliser les différences du second ordre.

DOCUMENTS A RENDRE

1- Un document (1 à 2 pages) qui décrit les calculs menant à l'algorithme ;

2- Un programme écrit avec la librairie Raster qui permet de tester l'algorithme.

Le document est à déposer au secrétariat de la Licence.

Le source du programme est à envoyer par courrier électronique à votre enseignant (bellik@limsi.fr pour le groupe 1, mbl@lri.fr pour le groupe 2). N'oubliez pas d'indiquer votre nom dans un commentaire au début du programme.

La date limite pour rendre le document et le programme est le 29 Mars 1995.


SOLUTION - DEVOIR 1 - RASTéRISATION DE PARABOLE

On considère la parabole y = ax2. Pour tracer la parabole de l'énoncé, il suffit de faire une translation de (x0, y0). Soit F(x, y) = y - ax2. F(x, y) > 0 au-dessus de la parabole et < 0 en-dessous. La parabole est symétrique autour de l'axe Oy : F(x, y) = F(-x, y). Il suffit donc de la tracer pour x >= 0.

Comme a > 0 (parabole dirigée vers le haut), pour x >= 0 on a une section où la tangente à la parabole est en dessous de la diagonale principale, donc les mouvements sont E ou NE, et une section où la tangente est au-dessus de la diagonale, donc les mouvements sont N ou NE.

Considérons la première section. Etant donné un point (xi, yi) de la parabole, le mouvement suivant est en fonction de di+1 = F(xi+1, yi+1/2).

Si à l'étape précédente, on avait fait un mouvement E, on a di = F(xi, yi+1/2), donc

di+1 = F(xi+1, yi+1/2) = yi+1/2 - a(xi+1)2 = yi+1/2 - axi2 -2axi - a = di -2axi - a.

Si à l'étape précédente, on avait fait un mouvement NE, on a di = F(xi, yi-1/2), donc

di+1 = F(xi+1, yi+1/2) = yi+1/2 - a(xi+1)2 = yi-1/2 +1 - axi2 -2axi - a = di +1 -2axi - a.

Le point x0 = (0, 0) appartient à la parabole. On a donc d1 = F(1, 1/2) = 1/2 - a.

Pour la seconde section, les mouvements possibles sont N et NE. Etant donné un point (xi, yi) de la parabole, le mouvement suivant est calculé en fonction de di+1 = F(xi+1/2, yi+1).

Si à l'étape précédente, on avait fait un mouvement N, on a di = F(xi+1/2, yi), donc

di+1 = F(xi+1/2, yi+1) = yi+1 - a(xi+1/2)2 = di +1.

Si à l'étape précédente, on avait fait un mouvement NE, on a di = F(xi-1/2, yi), donc

di+1 = F(xi+1/2, yi+1) = yi+1 - a(xi+1/2)2 = yi+1 - a(xi-1/2 + 1)2

= yi +1 - a(xi-1/2)2 -2a(xi -1/2) - a = di +1 -2a(xi -1/2) - a = di +1 -2axi -2a.

Il reste à calculer le point où l'on change de section. Le vecteur nave; l'lle. On a donc d1BLOCKQUOTE>

On confslachles action o&u=#0s aut

Pour la lémenter un et dcr pt NE,lgorithme.

PUL LI>s un première section. E LI>rave; l'&eainitialtion de : d := q- a.LI>aeacuve;re n comvement E, o : d := da.<2pxa.

LI>aeacuve;re n comvement E, No : d := da+ qa.<2pxa.

LI>si da; 0 (pn a dt un mouvement E, on sic&e No LI>change de section o&u=#0s autLI>s un prex pograve;re mection. E LI>aeacuve;re n comvement E, N : d := da+ q LI>aeacuve;re n comvement E, No : d := da+ qa.<2pxa.<2p LI>si da;l0 (pn a dt un mouvement E, Nn sic&e No LI>chaaacucirc;te doccer cute; en =#0s autx NE.ynt rt la parPouNo&ag: cute;tape donné un point (xi, yi) de !0, 0) appla parabole, le otipeuulculer le t q ent: >

y - B>i) dax2) dP>2 = yi) da/ UP>2) dP>2 = y<; 0 (p i) d, nt= UP>2) dP>2 = >

Il No&a2g: utipeuuldre le dgorithme ;

PouVoici programme est:>

PPRET> PRETP>


T>Michel Beaudouin-Lacti>