Construction et visualisation d'une enveloppe convexe 3D

Sujet proposé par Philippe Chassignet

Philippe.Chassignet@polytechnique.fr

Introduction

Étant donné un ensemble de points de l'espace affine 3D, leur enveloppe convexe est la frontière du plus petit domaine convexe contenant ces points. C'est un polyèdre dont les sommets sont des points de l'ensemble initial.

L'enveloppe convexe d'un objet est couramment utilisée, en synthèse d'images, en CAO, en robotique, comme approximation pour des tests rapides d'intersection. Il y a également des applications en statistique. Par exemple, le ``pelage'' consiste à supprimer les points de l'enveloppe convexe, ce qui permet d'obtenir des estimateurs plus robustes.

Dans ce projet, il s'agit de construire cette enveloppe convexe et de la visualiser. Il existe de nombreuses méthodes de construction d'une enveloppe convexe [1]. Celle utilisée pour ce projet consiste à rechercher de manière incrémentale les faces triangulaires qui constituent l'enveloppe. C'est l'algorithme dit de ``l'emballage'' qui est une généralisation de l'algorithme de Jarvis en dimension 2. La visualisation est une application particulière des techniques les plus simples de synthèse d'image [2,3,4,5].

Il s'agit essentiellement d'un problème de géométrie affine. La difficulté principale réside dans la définition d'une structure de données appropriée pour gérer toutes les relations nécessaires entre sommets, arêtes et faces.

Ce sujet ne demande pas de connaissance particulière en programmation graphique et interface. La librairie MacLib [6] suffit pour produire le résultat demandé.

Détail du sujet

Algorithme de construction

Principe général

La recherche d'une première face fait l'objet d'une méthode particulière qui est décrite plus loin. Lorsque cette face est connue, on dispose alors de 3 arêtes qui servent à initialiser un ensemble de ``bords''. Cet ensemble va contenir toutes les arêtes qui, provisoirement, ne sont encore liées qu'à une seule face. Les grandes lignes de l'algorithme sont alors:

- calcul de la 1ère face,

- initialisation de l'ensemble des ``bords'',

- tant qu'il reste (au moins) une arête de bord:

- calculer la deuxième face qui s'appuie sur cette arête,

- mettre à jour l'ensemble des bords.

Calcul d'une face supplémentaire

Étant donnée a, une arête de bord, on connaît ``la'' face f₁ à laquelle elle appartient. Il s'agit de trouver la seconde face triangulaire f₂ qui s'appuie sur cette arête.

Soient pour cela:

- $\bf n$, le vecteur unitaire orthogonal à la face f₁ et orienté vers l'intérieur du convexe,

- $\bf k$, le vecteur unitaire orthogonal à $\bf n$ et à l'arête a et orienté vers l'intérieur de la face f₁,

- p, un point de l'arête a.

Pour tout point q de l'ensemble initial et n'appartenant pas à l'arête a, on considère le critère:

$$\frac{{\overline{p q}.{\bf k}}} {\sqrt{({\overline{p q}.{\bf n}})^2+({\overline{p q}.{\bf k}})^2}}$$

C'est le cosinus de l'angle d'ouverture entre la face f₁ et le plan qui s'appuie sur l'arête a et passe par q. La nouvelle face f₂ recherchée sera celle déterminée par les deux points extrémités de a et par le point q qui minimise ce critère.

Remarque: Si plusieurs points minimisent ce critère, on devra écarter ceux qui se trouvent à l'intérieur des triangles construits avec d'autres points. Cela se fait en O(n) en maximisant un critère bien choisi.

Calcul de la première face

On prend comme premier point p₁, celui dont la coordonnée z est minimale. Ce point est trivialement dans l'enveloppe convexe.

On prend comme second point p₂, celui qui minimise l'angle entre la droite p₁p₂ et le plan d'équation (z=cste) passant par p₁. L'arête $\overline{p_1p_2}$ est trivialement dans l'enveloppe convexe.

Pour le troisième point, on utilise une adaptation de l'algorithme général, pour l'arête $\overline{p_1p_2}$ et une ``normale'' $\bf n$ bien choisie. On fera attention au fait qu'on ne peut pas orienter $\bf k$.

À chaque fois, si plusieurs points minimisent le critère considéré, il faut raffiner de manière appropriée.

Généralisation à des faces non-triangulaires

L'algorithme donné ci-dessus construit des faces triangulaires. Si plus de 3 points de l'enveloppe sont coplanaires on doit produire des faces polygonales. En effet, le polyèdre à faces triangulaires n'est pas minimal en nombre de faces. D'autre part, il n'est pas unique dans la mesure où plusieurs triangulations sont possibles.

Pour obtenir le polyèdre convexe minimal en nombre de faces, il faut fusionner toutes les paires de faces qui sont coplanaires et qui partagent une arête. Cette opération pourrait être réalisée au fur et à mesure pendant la construction. Cela revient à rendre l'algorithme plus général: Étant donnés tous les points qui minimisent le critère du cosinus, la face recherchée est le polygone convexe défini par ces points.

Pour ce projet, il est conseillé d'en faire une opération indépendante qui prend en entrée l'ensemble de faces triangulaires déjà construites.

Algorithme de visualisation

Projection prespective

Pour tout point 3D (x, y, z), on construit son image 2D (x_p, y_p), définie par la transformation projective:

$$\left( \begin{array} {c} d.x_p \\ d.y_p \\ d \end{array} \... ...left( \begin{array} {c} x \\ y \\ z \\ 1 \end{array} \right)$$

Cette transformation sera exprimée comme la composition de plusieurs transformations plus simples, de ``mise en scène'' (matrices $4\times 4$ de rotations et translations), d'une part, et de ``prise de vue'' (matrice $4 \times 3$ de projection), d'autre part. Il est essentiel de pouvoir faire tourner l'objet pour pouvoir observer toutes ses faces. Les réglages de translation et de focale serviront à un bon cadrage.

Il n'est pas demandé d'interface sophistiquée pour le contrôle de ces opérations. En particulier, on se contentera de translations et rotations élémentaires selon les axes canoniques.

Élimination des parties cachées

On utilisera l'algorithme du peintre qui consiste à dessiner entièrement chaque face, de la plus éloignée à la plus proche. L'élimination des parties cachées se fait alors par simple recouvrement. Il suffit pour cela de trier les faces, en remarquant que dans le cas de faces convexes, il n'y a pas d'ambiguïté sur la relation d'ordre.

Rendu

On simulera une réflexion diffuse (loi de Lambert) qui modélise une surface parfaitement matte. Pour cela, on considère une source lumineuse à l'infini déterminée par son intensité uniforme en tout point de l'espace L et par sa direction ${\bf d}$.L'intensité réfléchie par une face est considérée comme uniforme dans toutes les directions et vaut $L.\cos({\bf d},{\bf n})$, où $\bf n$ est le vecteur normal à la face.

Remarque

Tout travail supplémentaire qui consisterait à exploiter les caractéristiques particulières d'une machine pour notament ``accélérer'' le grqphique ou ``améliorer'' le rendu ne sera pris en compte que de manière marginale dans la note.

Travail demandé

Le travail sera noté principalement sur le choix des structures de données et sur la mise en uvre des algorithmes décrits ci-dessus.

Ce sujet se partage naturellement en deux parties:

- construction de l'enveloppe,

- visualisation.

Pour équilibrer la charge de travail, la fusion des faces triangulaires en faces polygonales sera rattachée à la seconde partie.

Dans un premier temps, les deux parties peuvent être traitées de manière indépendante dans la mesure où l'on convient d'un format de fichier commun (voir annexe).

Le résultat final devra intégrer les deux parties dans un seul programme avec une structure de données commune. En particulier, il doit être possible de visualiser des étapes de la construction de l'enveloppe.

Annexe, le format OFF

La première ligne comporte les trois lettres OFF qui caractérise le format. La ligne suivante indique successivement les nombres de sommets (n_s), de faces (n_f) et d'arêtes (n_a). Viennent ensuite n_s lignes qui donnent les coordonnées des sommets, implicitement numérotés de à n_s-1. Viennent finalement les n_f lignes qui décrivent les faces. La description d'une face comporte le nombre de sommets qui la composent suivi des numéros de ces sommets. Les lignes qui commencent par # sont des commentaires. Par exemple, pour deux pyramides accolées cela donne:

OFF
6 8 12
#
 0.000  0.000  1.000
 1.000  0.000  0.000
 0.000  1.000  0.000
-1.000  0.000  0.000
 0.000 -1.000  0.000
 0.000  0.000 -1.000
#
3 1 0 2
3 2 0 3
3 3 0 4
3 4 0 1
3 1 2 5
3 2 3 5
3 3 4 5
3 4 1 5

Ce format est reconnu par l'outil geomview disponible sur les stations Unix. Si les données sont dans le fichier pyramides.off, elles peuvent être visualisées par la commande geomview pyramides.off.

References

1

F. P. Preparata, M. I. Shamos, Computational Geometry, an introduction, Springer-Verlag, 1985.

2

J. D. Foley, A. van Dam, Fundamentals of Interactive Computer Graphics, Addison-Wesley, 1982.

3

J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, Computer Graphics, principles and practice, 2nd ed., Addison-Wesley, 1990.

4

W. M. Newman, R. F. Sproull, Principles of Interactive Computer Graphics, 2nd ed., McGraw-Hill, 1979.

5

B. Peroche, J. Argence, D. Ghazanfarpour, D. Michellucci, La synthèse d'images, Hermès, 1988.

6

La librairie MacLib,
http://lix.polytechnique.fr/Labo/Philippe.Chassignet/MACLIB/maclib_intro.html