1

CHAPITRE IV

OBJETS ÉLÉMENTAIRESDANS

L’ESPACE À TROIS DIMENSIONS

2

TRIANGLEIl est défini par ses 3 sommets p1, p2, p3.

L'équation du plan qui coïncide avec ce triangle est:

[(p2 - p1) x (p3 - p1)] * (P - p1) = 0.

où P est un point quelconque du plan.

L'aire du triangle est égale à ||(p2 - p1) x (p3 - p1)|| / 2.

S(u, v) = u p1 + (1 – u) {p2 v + (1 – v) p3}, u, v [0, 1].

OBJETS ÉLÉMENTAIRESConsidérons les principales classes de surfaces ou volumes simples utilisées enmodélisation géométrique et en infographie.

p1

p2

p3

p2 v + (1 – v) p3

S(u, v)

Espace normalisé

3

CERCLEIl est défini par son centre C, son rayon R et le vecteur normal N au plan du cercle.

Hypothèse : le cercle est centré à l'origine.

L'équation du plan du cercle est: N . P = 0 où P est un point quelconque du plan.

On recherche donc l'intersection de ce plan avec la sphère de centre 0 et de rayon rdont l'équation est:

x2 + y2 + z2 = r2 .

On obtient donc:      (N = (n1, n2, n3) , P = (x, y, z))

  (n12 + n2

2 ) y2  +  (n12 + n3

2 )z2  + 2 n2 n3 y z = n12 r2    où n1 0

Hypothèse : le cercle est différent de l'origine.

Effectuer une translation de C des points satisfaisant l'équation précédente.

4

POLYGONESUn polygone est une figure fermée formée d'une suite de points appelés"sommets " reliés par des segments appelés "arêtes".

Les sommets sont distincts et les arêtes ne se croisent pas.

L'ensemble des sommets font partie d'un même plan.

Un polygone est défini à partir de ses sommets P0, P1, P2, ..., PN-1.

5

POLYGONES CONVEXESUn polygone où chaque paire de points à l'intérieur du polygone implique que lesegment de droite les reliant se trouve aussi complètement à l'intérieur du polygone.

oui non

POLYGONES MONOTONESUn polygone possédant 2 sommets extrêmes dans une direction donnée,reliés par 2 chaînes monotones dans cette direction.

La direction x est choisie.

6

POLYGONES EN SPIRALEUn polygone dont le contour contient uniquement une sous-chaîne concave.

POLYGONES EN ÉTOILEUn polygone possédant un sommet visible de tous les autres sommets.

7

POLYÈDRESUne figure fermée bornée où chaque face est un polygone.

typedef Liste Polyedre; (* liste de polygones 3D *)

Le type liste représente une liste doublement chaînée.

POLYGONES- Comment vérifier que nous sommes en présence d’un polygone ?- Déterminer si un polygone est convexe, monotone, en spirale ou en étoile ?- Vérifier si un point appartient ou non à un polygone ?- Calculer l’intersection entre 2 polygones, entre une droite et un polygone,

entre un plan et un polygone, etc.

8

SURFACES DE RÉVOLUTIONAppliquer une rotation à une courbe autour d'un axe quelconque dans l'espace 3D :

soient la courbe génératrice C(u), u [0,1],l'axe de rotation d,la transformation TZ faisant coïncider l'axe de rotation à l'axe des z,la transformation inverse T-1

Z,la transformation T de rotation d'un angle autour de l'axe des z,

on obtient :

S(u, ) = T-1Z T TZ C(u), u [0, 1], [0, 2].

La courbe génératrice C(u) est quelconque; nous pouvons utiliser une splinecubique, une courbe de Bézier ou une courbe B-Spline par exemple.

C(u) | | d

C(u) est un segment de droite

Ex.

9

SURFACES DE RÉVOLUTIONEx.

axe de rotation

segment de droite

X

Y

C(u) | | d

C(u) est un segment de droite

C(u) et d sont coplanaires.

10

SURFACES DE BALAYAGEDéplacement d'une droite, d'un polygone ou d'une courbe quelconque le long d'unecourbe dans l'espace à 3 dimensions.

Surfaces cylindriques

Déplacement d'une droite de direction w constante (génératrice) s’appuyant surune courbe fixe C(u) (directrice)

C(u) + w, u [0,1], .

C(u)

w N(u, ) = d C(u) x w d u

11

SURFACES DE BALAYAGEDéplacement d'une droite, d'un polygone ou d'une courbe quelconque le long d'unecourbe dans l'espace à 3 dimensions.

Surfaces coniques

Déplacement d'une droite (génératrice) s’appuyant sur une courbe fixe C(u)(directrice) tout en passant par un point fixe P.

S(u, ) = P + (C(u) - P), u [0,1], .

P

C(u)

N(u, ) = d C(u) x (C(u) - P) d u

12

SURFACES DE BALAYAGEDéplacement d'une droite, d'un polygone ou d'une courbe quelconque le long d'unecourbe dans l'espace à 3 dimensions.

Surfaces conoïdes

Déplacement d'une droite (génératrice) s’appuyant sur une courbe fixe C(u),

u [0,1], et une droite fixe D: : a + d, tout en restant | | à un plan dontla normale est N. C(u) + {a + d - C(u)}, u [0,1], .

où = [C(u) * N - a * N] / (d * N).D

C(u) Le plan est | | à a + d - C(u)

(a + d - C(u)) N

N * (a + d - C(u)) = 0

= [C(u) * N - a * N] / (d * N).

13

SURFACES BILINÉAIRES

Une surface bilinéaire est construite à partir de 4 sommets P, Q, R et W.

Chaque point sur la surface est obtenu par interpolation linéaire entre 2 points surdes frontières opposées:

S(u, v) = (1-u) (1-v) P +(1-u)v Q + u(1-v) R + u v W, u, v [0,1].

Si les 4 sommets sont dans un même plan, la surface en question est un quadrilatère.

N(u, v) = S(u, v) x S(u, v) u v

où

S(u, v) = v (W – Q) + (1 – v) (R – P),u

S(u, v) = u (W – R) + (1 – u) (Q – P).v

14

SURFACES BILINÉAIRESS(u, v) = (1-u) (1-v) P +(1-u)v Q + u(1-v) R + u v W, u, v [0,1].

On peut subdiviser S en 4 sous-surfaces bilinéaires avec les sommets suivants :

I : P, S(0, ½), S(½, 0) et S(½, ½).II : S(0, ½), Q, S(½, ½) et S(½, 1).III : S(½, 0), S(½, ½), R et S(1, ½).IV : S(½, ½), S(½, 1), S(1, ½) et W.

Cette subdivision est exacte. Considérons par exemple la sous-surface I notée A(u, v):

A(u, v) = (1-u) (1-v) P +(1-u)v S(0, ½) + u(1-v) S(½, 0) + u v S(½, ½),= (1-u) (1-v) P + (1-u)v {½ P + ½Q} + u(1-v) {½ P + ½ R}

+ u v {¼ P + ¼ Q + ¼ R + ¼ W}

= {(1-u) (1-v) + ½ (1-u)v + ½ (1-v)u + ¼ u v } P + {½ (1-u)v + ¼ u v} Q + {½ u(1-v) + ¼ u v} R + {¼ u v} W

= {1 - ½ v - ½ u + ¼ u v } P + {½ v - ¼ u v} Q + {½ u - ¼ u v} R + {¼ u v} W

= S(½ u , ½ v)

15

SURFACES GUIDÉESElle est obtenue par interpolation linéaire de 2 courbes P(v) et Q(v):

S(u, v) = (1-u) P(v) + u Q(v), u, v [0,1].

Nous pouvons remarquer que S(0,v) = P(v) et S(1,v) = Q(v).

De plus, nous avons: S(0,0) = P(0), S(1,1) = Q(1), S(0,1) = P(1) et S(1,0) = Q(0),les extrémités des 2 courbes.

16

SURFACES DE COONS LINÉAIRESEn considérant les 4 courbes frontières C1(u), C2(u), C3(v) et C4(v), on peutimaginer simplement la somme de 2 surfaces guidées:

S(u, v) = (1-v) C1(u) + v C2(u) + (1-u) C3(v) + u C4(v) u, v [0,1].

où C1(0) C3(0), C3(1) C2(0), C2(1) C4(1) et C1(1) C4(0).

C1(u)

C2(u)

C4(v)

C3(v)

Après examen, on voit que :

S(0, 0) = 2 C1(0),S(0, 1) = 2 C2(0),S(1, 0) = 2 C4(0),S(1, 1) = 2 C4(1),S(0, v) = (1-v) C1(0) + v C2(0) + C3(v) S(1, v) = (1-v) C1(1) + v C2(1) + C4(v)S(u, 0) = C1(u) + (1-u) C3(0) + u C4(0)S(u, 1) = C2(u) + (1-u) C3(1) + u C4(1).

Ceci est dû à la duplication des 4 sommets.

17

SURFACES DE COONS LINÉAIRESPour corriger cet état de fait, nous considérons plutôt:

S(u,v) = (1-v) C1(u) + v C2(u) + (1-u) C3(v) + u C4(v)- C1(0) (1-u)(1-v) – C2(0)(1-u)v-C4(0) u(1-v) – C4(1) u v, u, v [0,1]

où S(0, 0) = C1(0),S(0, 1) = C2(0),S(1, 0) = C4(0),S(1, 1) = C4(1),S(0, v) = C3(v),S(1, v) = C4(v),S(u, 0) = C1(u), S(u, 1) = C2(u).

18

SURFACES DE COONS LINÉAIRES

19

Maillage polygonal

Jusqu’à maintenant, nous avons considéré des surfaces qui peuvent être décritesanalytiquement.

Dans bien des applications, une description analytique est absente.Pensons à la représentation d’une automobile ou d’un paquebot.

La surface d’un objet peut alors être représentée approximativementpar un ensemble de polygones.

Même si nous possédons des surfaces décrites analytiquement comme par ex.,des surfaces paramétriques, il est facile de construire un maillage triangulaireapproximant chaque surface à partir des points suivants de la surface :

{S(u, v) | u = 0, , 2, …, 1; v = 0, , 2, …, 1}

et cela facilite l’application des algorithmes d’affichage.

20

Maillage polygonal

Calcul de la normale en chacun des sommets des facettes d’un maillage triangulaire.

la normale en chacun des sommets d’une facette triangulaire est la même etcorrespond à la normale au plan du triangle.

la normale en un sommet d’une facette triangulaire est la moyenne desnormales des plans des triangles ayant ce sommet en commun.

la normale en un sommet d’une facette triangulaire est la normale à la surfaceen ce point.

TROIS FAÇONS DIFFÉRENTES :

21

Exercice # 1

Fonction booléenne qui retourne TRUE si un point P appartient à un polygone.FALSE autrement.

On peut supposer que le polygone est dans le plan X°Y.

Construisons une demi-droite issue de P qui intercepte le polygonesans intercepter ces sommets.

Calculer m  # d’intersections entre cette demi-droite et les arêtes du polygone.

Si m est impaire alors retourne TRUEsinon retourne FALSE.

m = 4.

P

22

Exercice # 2

Fonction booléenne qui retourne TRUE si un polygone est convexe.FALSE autrement.

Soient P0, P1, P2, …, Pn-1 les sommets d’un polygone,

testez le signe de la coordonnée en z du vecteur :(Pi - Pi-1) x (Pi+1 - Pi), i = 1, 2, …, n avec Pn P0 et Pn+1 P1.

Si le signe est le même pour tout i = 1, 2, …, nalors retourner TRUEsinon retourner FALSE.

Note : Le polygone est dans le plan X°Y; la coordonnée en z des sommets est nulle.

23

Exercice # 3

Considérons un plan dont le vecteur normal est N etla distance de l’origine au plan est d, etun triangle 3D non dégénéré dont les sommets sont resp. Q, R et S.

L’intersection de ces 2 objets donne lieu à plusieurs situations. Dans chacune d’elles,indiquez comment nous pouvons identifier les surfaces résultantes et comment nouspouvons déterminer quelle situation s’applique.

L’équation du plan est : N* P + d = 0.

1er cas : Surface résultante Triangle QRS

Condition : N * Q + d = 0, N * R + d = 0, N * S + d = 0.

2ième cas : Surface résultante aucune

Condition : N * Q + d < 0, N * R + d < 0, N * S + d < 0ou encore

N * Q + d > 0, N * R + d > 0, N * S + d > 0.

24

Exercice # 3 (suite)3ième cas : Surface résultante 1 point

Si la surface résultante est un point alors il s’agit d’un des 3 sommets du triangle disons Q.

Conditions : N * Q + d = 0,(N * R + d < 0, N * S + d < 0)

ou(N * R + d > 0, N* S + d > 0).

Des conditions semblables peuvent être fournies lorsque le point résultant est R ou S. 4ième cas : Surface résultante 1 segment de droite

(i) La surface résultante est une arête du triangle, disons QR.

Condition : N * Q + d = 0, N * R + d = 0, N * S + d 0.

Des conditions semblables peuvent être fournies lorsque la surface résultante estRS ou QS.

QR

25

Exercice # 3 (suite)(ii) La surface résultante est un segment de droite dont l’une des extrémités est un sommet du triangle, disons Q.

Condition : N * Q + d = 0,(N * R + d <0, N * S + d > 0) ou (N * R + d >0, N* S + d < 0).

Pour trouver l’autre extrémité du segment résultant, il s’agit de calculer [0, 1]tel que R + (S - R) fait partie du plan N * P + d = 0.

Une démarche semblable peut être effectuée lorsque le sommet du triangleappartenant au plan est R ou S.

Q

R

S

26

Exercice # 3 (fin)(iii) la surface résultante est un segment de droite : aucun des sommets du triangle ne fait partie du plan et il existe au moins un sommet du triangle de chaque côté du plan (supposons que R et S sont de part et d’autre du plan).

Condition : N * Q + d 0, N * R + d 0, N * S + d 0l’un des 3 termes est négatif et l’un des trois termes est positif.

Pour calculer l’intersection entre chaque arête du triangle (dont les extrémités sontde part et d’autre du plan) et le plan, on peut procéder comme en (ii).

Q

R

S