Menu principal	bas de page

III/ Elimination des faces cachées :

Jusqu’à présent, nous avons obtenu une représentation des objets de type " Fil de fer " : tous les segments de l’espace 3D projeté sont visibles, mêmes ceux devant normalement être invisibles du fait de l’opacité de certains objets (les murs d’une maison sont opaques et ne laissent pas voir le côté opposé de cette dernière), ainsi que ceux cachés par d’autres objets.
On cherchera donc à éliminer, dans un premier temps, les faces appartenant à un objet, cachées par lui-même (polygone convexe uniquement). Puis, on verra comment gérer l’élimination des faces d’un objet cachées par d’autres objets (polygone concave).

1) Cas des polygones convexes :

a) Principe :

La procédure à suivre est très simple. Il s’agit tout d’abord de déterminer, pour chaque face, un vecteur normal. On le calculera grâce au produit vectoriel de 2 vecteurs portés par les arrêtes de la face. Ce qui nous intéresse n’est, non pas la norme, mais la direction et le sens.
Puis, ceci fini, il faut déterminer le vecteur vision, légèrement modifié : il part de l’oeil et se dirige vers un point de la face considérée (et non pas vers le centre du repère de l’objet).
Enfin, on calcule le produit scalaire des 2 vecteurs obtenus. Son signe nous indique si la face est visible ou pas.

b) Rappels mathématiques concernant le produit vectoriel :

On considère 2 vecteurs (Xa, Ya, Za) et (Xb, Yb, Zb). Le produit vectoriel de par est un vecteur , de normal au plan défini par et , de sorte que (,,) soit une base directe.

Ses coordonnées sont		Xv = Ya * Zb - Za * Yb
		Yv = Za * Xb - Xa * Zb
		Zv = Xa * Yb - Ya * Xb

Sa norme (sans importance ici) vaut : |||| * |||| * sin(,)

Note : il faudra déterminer, dés le début du programme, un sens (trigonométrique ou horlogique) dans la déclaration des sommets composant une face. En effet, le vecteur normal est complètement dépendant du sens des vecteurs choisis pour le calculer : il n’est pas commutatif.

Sens trigonométrique		Sens horlogique

Note : Dans notre programme, la déclaration des sommets des faces s’effectue dans le sens horlogique.

c) Rappels mathématiques sur le produit scalaire :

On considère une nouvelle fois 2 vecteurs (Xa, Ya, Za) et <(Xb, Yb, Zb). Le produit scalaire de et est un nombre réèl égal à |||| * |||| * cos (,). Dans un repère orthonormal, il peut encore s’écrire = Xa * Xb + Ya * Yb + Za * Zb.
Puisque les normes sont positives, le signe du produit scalaire est déterminé par le signe de cos(,).

	Si -/2 < (,) < 0 ou 0 < (,) < /2 alors > 0
	Si /2 < (,) < ou < (,) < -/2 alors <0

Comme Cos(-) = Cos() R, on ramène tous ces cas aux suivants :
- Si 0 < |(,)| < /2 alors >0
- Si /2 < |(,)| < alors <0

d) Calcul du vecteur vision :

Le vecteur vision est tout simplement un vecteur joignant l’oeil à n’importe quel sommet de la face.
Note : Par mesure de simplicité, nous avons choisi dans notre programme de prendre le 1^er sommet déclaré.


Vecteur vision

Attention : Il ne faut pas confondre le vecteur vision avec l’axe Z du repère de l’oeil. En effet, même si leur origine est la même, l’axe Z pointe vers le centre du repère de l’objet qui n’est pas forcément partie de la face.

e) Test de visibilité :

Le test est réalisé en déterminant le signe du produit scalaire de et . On va détailler la suite des opérations enconsidérant que la déclaration des sommets s’est faite dans le sens horlogique. Deux cas sont possibles :
- Le produit scalaire est positif. La face est visible.
- Le produit scalaire est négatif. La face est invisible.

0 < |(,)| < /2		/2 < |(,)| <

Remarque : Si le produit scalaire est nul, les vecteurs et sont orthogonaux. On voit donc la face de profil : elle est réduite à une ligne.

2) Cas des polygones concaves :

a) Différence Concave/convexe :

La première question à se poser est : pourquoi se limiter aux polygones convexes ? Présenter un contre-exemple est le moyen le plus simple pour l’expliquer.
Dessinons 2 objets convexes : une maison simple, et une cheminée.

Maison avec faces cachées		Cheminée avec les faces cachées

L’association Maison/Cheminée forme un objet concave (on peut trouver 2 points dans l’objet qui forment un segment qui en sort). Si on garde l’algorithme précédent d’élimination des faces cachés, on obtient la figure n°1, peu satisfaisante, alors que l’on aurait préféré la figure n°2.

Fig. 1		Fig. 2
Association des objets convexes avec élimination des parties cachées en un objet concave		Vus réaliste de la maison et de sa cheminée (objet concave)
Résultat peu satisfaisant		C'est le résultat que l'on recherche

On cherche donc un algorithme plus performant, gérant la présence d’objets concaves.

b) Principe :

Cette fois-ci, on ne base pas sur un calcul mathématique mais sur une simple constation logique pour déterminer quelles faces sont cachées : les plus proches de l’oeil recouvrent les autres. On va donc procéder, dans l’ordre :
- Au calcul de la distance, selon l’axe Z, séparant l’oeil et chaque face.
- Au tri dans l’ordre décroissant des faces selon la distance précédemment calculée.
- A l’affichage des faces dans l’ordre du tableau, en les remplissant avec une texture, recouvrant les textures des faces antérieures.

Pour le calcul de la distance à l’oeil, il suffit de faire la moyenne des coordonnées selon l’axe Z des sommets de la faces.
En ce qui concerne le tri des faces, un grand nombre de procédures différentes sont disponibles. Cependant, il ne faut pas oublier que la vitesse de calcul compte, vu que l’on tient à faire tourner la figure dans l’espace ; c’est pourquoi dans notre programme, nous utilisons un algorithme de tri de type QuickSort. Le voici en Pascal :

Type tableau_simple = array[1..nb_max_faces] of integer; {tableau de nb_max_faces cases}
procedure quick_sort(var tableau_trie : tableau_simple; deb, fin : integer);
var i, j, temp : integer;
milieu : real;
begin
i:=deb;
j:=fin;
milieu:=tab_faces[(deb+fin) div 2].profondeur;
while i<=j do
begin
while tab_faces[tableau_trie[i]].profondeur > milieu do inc(i);
while tab_faces[tableau_trie[j]].profondeur < milieu do dec(j);
if i<=j then
begin
temp:=tableau_trie[i];
tableau_trie[i]:=tableau_trie[j];
tableau_trie[j]:=temp;
inc(i);
dec(j);
end;
end;
if i<fin then quick_sort(tableau_trie,i,fin);
if deb<j then quick_sort(tableau_trie,deb,j);
end;

Enfin, le remplissage des faces est assuré par une procédure inclue dans la bibliothèque graphique que nous utilisons. Etant écrite en assembleur (bien plus rapide à l’exécution que le Pascal), nous ne la détaillerons pas.

Remarque: on calcul pour chaque face sa distance à l'œil en faisant la moyenne des distances sommets-œil. Cela présente un petit inconvénient : il faut que les objets soit à peu près tous de la même taille. Si il y a trop de disparités, certaines faces risquent dans certains cas de se retrouver en premier plan alors qu'elles devraient être en partie cachées par un autre objet.
Voici donc une limite à cet algorithme.

---

Page précédente

Page suivante