IG1 1995 - devoir 1

Licence d'Informatique

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

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 = ax². Pour tracer la parabole de l'énoncé, il suffit de faire une translation de (x0, y0). Soit F(x, y) = y - ax². 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 (x_i, y_i) de la parabole, le mouvement suivant est en fonction de d_i+1 = F(x_i+1, y_i+1/2).

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

d_i+1 = F(x_i+1, y_i+1/2) = y_i+1/2 - a(x_i+1)² = y_i+1/2 - ax_i² -2ax_i - a = d_i -2ax_i - a.

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

d_i+1 = F(x_i+1, y_i+1/2) = y_i+1/2 - a(x_i+1)² = y_i-1/2 +1 - ax_i² -2ax_i - a = d_i +1 -2ax_i - a.

Le point x₀ = (0, 0) appartient à la parabole. On a donc d₁ = F(1, 1/2) = 1/2 - a.

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

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

d_i+1 = F(x_i+1/2, y_i+1) = y_i+1 - a(x_i+1/2)² = d_i +1.

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

d_i+1 = F(x_i+1/2, y_i+1) = y_i+1 - a(x_i+1/2)² = y_i+1 - a(x_i-1/2 + 1)²

= y_i +1 - a(x_i-1/2)² -2a(x_i -1/2) - a = d_i +1 -2a(x_i -1/2) - a = d_i +1 -2ax_i -2a.

Il reste à calculer le point où l'on change de section. Le vecteur normal à la parabole est

d/dx F(x, y) i + d/dy F(x, y) j = -2ax i + j.

On franchit la section lorsque 2ax > 1.

Pour implémenter efficacement l'algorithme, on utilise F' = qF. Il en résulte :

dans la première section
à l'initialisation : d := q/2 - p. Malheureusement cette valeur n'est pas entière. Si q est impair, q = 2q' +1 et d = q' - p + 1/2. le 1/2 ne change pas le signe de d, car q'-p est entier et les variations de d sont entières. On peut donc utiliser d = q' - a, soit d := q div 2 - p
après un mouvement E : d := d - 2px - p
après un mouvement NE : d := d + q - 2px - p
si d > 0, on fait un mouvement E, sinon NE
on change de section lorsque 2px > q. On peut calculer 2px - q incrémentalement :
initialisation : s := -q
itération : s := s + 2p (dans la première section, x augmente de 1 à chaque pas)
dans la deuxième section
après un mouvement N : d := d + q
après un mouvement NE : d := d + q - 2px - 2p
si d < 0, on fait un mouvement N, sinon NE
on arête le tracé lorsque x ou y sort de la fenêtre.

Note : étant donné un point P (x_p, y_p) != (0, 0) de la parabole, on peut calculer p et q :

y_p - ax_p² = 0 => a = y_p / x_p² => p = y_p, q = x_p²

Note2 : On peut rendre l'algorithme plus efficace en utilisant les différences du second ordre...

Voici le programme :

/*
 * Scan converting a parabola
 * p1 is the apex, p2 a point on the parabola
 */
 
boolean
ParabolaPoints (point a, int x, int y)
{
	int x1 = a.x + x;
	int x2 = a.x - x;
	y = a.y + y;
	WritePixel (x1, y);
	WritePixel (x2, y);
	if (y < 0 || y > _Raster.width)
		return FALSE;
	return TRUE;
}
 
void
RasterParabola (point p1, point p2)
{
	int p = p2.y - p1.y;
	int q = (p2.x - p1.x) * (p2.x - p1.x);
	int d = q / 2 - p;
	int s = -q;
	int sincr = 2*p;
	int x = 0;
	int y = 0;
	
	if (p < 0 || q < 0)
		return;
	
	WritePixel (p1.x, p1.y);
	
	/* first section */
	while (s < 0) {
		if (d > 0) { /* move E */
			x++;
			d += -2*p*x - p;
		} else { /* move NE */
			x++, y++;
			d += q - 2*p*x - p;
		}
		if (! ParabolaPoints (p1, x, y))
			return;
		s += sincr;
	}
	
	/* second section */
	for (;;) {
		if (d < 0) { /* move N */
			y++;
			d += q;
		} else { /* move NE */
			x++, y++;
			d += q - 2*p*x - 2*p;
		}
		if (! ParabolaPoints (p1, x, y))
		return;
	}
}

Michel Beaudouin-Lafon