Licence d'Informatique
Examen (3h) - 17 juin 1996
Documents autorisés : notes personnelles de cours et de TD uniquement.
Lisez l'ensemble de l'énoncé. Soyez clair, précis, concis. Justifiez vos réponses. Relisez-vous.
Pour l'écriture des programmes, vous pouvez utiliser Pascal au lieu de C si vous le désirez.
La courbe de von Koch est une courbe fractale qui est définie de la façon suivante : on part d'un segment de longueur unité (étape 0), que l'on remplace par 4 segments selon la figure 1 ci-dessous (étape 1). Chaque segment a pour longueur le tiers de la longueur du segment initial, les angles sont de 60º. A l'étape n+1, on remplace chaque segment de la figure obtenue à l'étape n par le même principe. La figure ci-dessous montre les 4 premières étapes.
1. Soit S0 le segment d'extrémités (0, 0), (1, 0), corres-pondant à l'étape 0. Ecrire les 4 matrices de transformations en coordonnées homogènes qui permettent de transformer ce segment en chacun des 4 segments de l'étape 1. On rappelle que cos 60º = 1/2 et sin 60º = [[radical]]3 / 2.
2. En déduire les matrices de transformations permettant de passer d'un segment quelconque d'extrémités (xn0, yn0), (xn1, yn1) aux quatre segments qui le remplacent à l'étape suivante. Le résultat peut être laissé sous forme de produit matriciel.
3. Ecrire une programme qui permet de dessiner la courbe de von Koch à l'étape n. On pourra se donner des fonctions de multiplication de matrices entre elles et par des vecteurs. La procédure de dessin d'un segment est
DrawLine (int x0, int y0, int x1, int y1)
4. Modifier le programme de la question 3 pour dessiner la courbe à la résolution maximale permise par le système d'affichage. On pourra utiliser la propriété selon laquelle la courbe est toujours incluse dans le triangle équilatéral dont un côté est le segment initial S0.
Le langage de programmation LOGO permet de réaliser des dessins en programmant les mouvements d'une tortue qui peut laisser une trace sur l'écran lors de ses déplacements. On se propose d'utiliser le même principe pour créer une librairie de fonctions graphiques.
Une tortue est caractérisée par une position (x, y) et une direction repérée par une angle en degrés par rapport à l'horizontale. La position (0, 0) correspond au centre de l'écran, l'angle 0 à une tortue orientée vers la droite de l'écran. On représente une tortue par la structure suivante :
typedef struct {
x, y, dir : float;
} Tortue;
1. On dispose de la procédure DrawPixel (int x, int y) qui allume le pixel de coordonnées écran (x, y). Définir et implémenter un algorithme incrémental qui permet de tracer un segment défini par deux extrémité (x0, y0) et (x1, y1) de coordonnées réelles. L'algorithme ne doit pas utiliser de multiplication dans sa boucle principale. Comparer son efficacité avec l'algorithme classique du point médian, dans l'hypothèse où les opérations arithmétiques sur les réels sont aussi efficaces que celles sur les entiers.
2. Ecrire le corps des fonctions suivantes :
void Gauche (Tortue* t, float a); void Droite (Tortue* t, float a); void Saute (Tortue* t, float d); void Avance (Tortue* t, float d);
Gauche (resp. Droite) tourne la tortue d'un angle a dans le sens trigonométrique direct (resp. trigonométrique inverse). Saute déplace la tortue de d dans sa direction courante. Avance est comme Saute mais dessine un segment de la position initiale à la position finale.
3. La procédure suivante trace la courbe de von Koch (voir exercice 1) à l'étape 1 :
Avance (t, 1/3); Gauche (t, 60); Avance (t, 1/3); Droite (t, 120); Avance (t, 1/3); Gauche (t, 60); Avance (t, 1/3);
Ecrire une procédure qui trace la courbe à l'étape n, et une procédure qui trace la courbe à la résolution maximale. Comparer avec les programmes des questions 3 et 4 de l'exercice 1.
On veut réaliser un programme de dessin permettant la création et l'édition de courbes de Bézier. Chaque courbe est formée d'un ou plusieurs segments de Bézier. Chaque segment est défini par les 4 points de contrôle habituels. La procédure Bezier(P1,P2,P3,P4) trace un segment de Bézier.
Pour que les courbes soient lisses, on impose que les deux demi-tangentes aux points de jonctions entre les segments soient opposées. Une courbe de Bézier est donc définie par un ensemble de couples (Ci, Ti) où chaque Ci définit un point et chaque Ti les tangentes en ce point des deux segments adjacents (voir figure ci-contre ; T'2 est le symétrique de T2 par rapport à C2).
La création interactive d'une courbe de Bézier se fait en définissant successivement chaque point et la tangente en ce point, de la façon suivante : le point Ci est défini par la position de la souris lors de l'appui sur le bouton ; ensuite l'utilisateur déplace la souris avec le bouton enfoncé ; le point Ti est défini par la position de la souris lorsque il relâche le bouton.
1. Décrire la machine à états qui implémente la création d'une courbe de Bézier. Le feed-back visuel doit inclure le tracé de la courbe et des tangentes au fur et à mesure de leur définition.
2. Pour éditer une courbe de Bézier, celle-ci doit être sélectionnée. Les points de contrôles et les tangentes apparaissent alors comme dans la figure ci-dessus. Définir la machine à états décrivant les 3 possibilités suivantes d'édition :
1. Donner la définition des 3 principales types de lumière utilisés dans les modèles d'illumination : lumière ambiante, réflection diffuse, réflection spéculaire.
2. Expliquer les effets de chaque type de lumière sur l'affichage d'une sphère et d'un cube.