Algorithme de Bresenham

Exercice 1. Un segment de droite peut être défini par deux points, à partir desquels on peut déterminer son équation : \(y = ax + b\).

Ecrire le programme "naïf" de tracé de segments de droite dans l'espace écran, reliant deux points quelconques \(P_1(x_1,y_1)\) et \(P_2(x_2,y_2)\), définis dans l'espace objet, en utilisant cette équation et en calculant les valeurs de y pour x dans \([x_1, x_2]\) (avec un majorant du pas).

Les points, et donc les segments, étant définis dans l'espace objet, on utilisera avec profit la projection de l'espace objet dans l'espace écran implantée au TP 1.

Comment déceler les segments totalement ou partiellement hors de la window ? Cette problématique appartient à la famille des algorithmes de clipping. Dans le cadre de ce TP, on ne choisira que des segments dont les deux sommets appartiennent à la window.

Exercice 2. Cette méthode n'est pas assez rapide pour les systèmes graphiques interactifs (manipulation dynamique des objets de la visu). Il faut donc adopter une solution plus efficace : l'algorithme de Bresenham pour la droite.

Ecrire le programme de tracé de segments de Bresenham pour un segment de droite défini dans le premier octant et dont l'un des sommets est confondu avec l'origine.

Exercice 3. Adapter ce programme pour le tracé d'un segment de droite quelconque en conservant son caractère optimal.

Exercice 4. Comparer géométriquement (en changeant de couleur) et en temps (voir pour cela le module time) les tracés de 1000 segments engendrés aléatoirement et construits par les deux programmes de tracés. Prendre garde à bien utiliser la même séquence de nombres pseudo-aléatoires dans les deux cas (voir pour cela la fonction seed()).