ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Revue Internationale de CFAO et d'informatique graphique

0298-0924
remplacée par la Revue Internationale d'Ingénierie Numérique
 

 ARTICLE VOL 18/2 - 2003  - pp.247-264
TITRE
Trois algorithmes d'intersection des surfaces de subdivision

RÉSUMÉ
Dans cet article, nous nous intéressons particulièrement au calcul des courbes d'intersection entre deux surfaces de subdivision. Pour des raisons pratiques, nous ne considérons que les surfaces de subdivision générées par le principe de Loop. Nous présentons et nous comparons trois algorithmes de calcul. Comme une surface de subdivision est représentée par un maillage, le calcul des courbes polygonales d'intersection se fait naturellement en calculant les intersections entre chaque face d'une des surfaces et toutes les faces de l'autre. Au niveau initial, cette méthode est incontournable mais la complexité augmente très rapidement ce qui engendre des calculs très lourds. Pour les réduire, il est intéressant d'utiliser les propriétés des surfaces de subdivision. Le second algorithme se base sur le 1-voisinage des faces en intersection. Le troisième algorithme utilise la notion de graphe biparti. La principale différence entre ces deux algorithmes repose sur les ensembles de faces considérés. Le premier considère un seul ensemble de faces par objet constitué des faces en intersection et de leurs voisines alors que le second fait intervenir plusieurs sous ensembles de cet ensemble par l'intermédiaire d'un graphe biparti.


ABSTRACT
In this paper, we focus on the computation of intersection curves between two subdivision surfaces. For practical reasons, we only consider the subdivision surfaces generated by the Loop scheme. We present and compare three algorithms. As a subdivision surface is represented by a mesh, the calculation of the polygonal intersection curves is naturally obtained by computing the intersections between each face of one surface and all the faces of the other. At the initial level, this method is unavoidable but complexity increases very quickly and generates very heavy calculations. To reduce them, it is interesting to use the subdivision surface properties. The second algorithm is based on the 1-neighborhood of the intersection faces. The third algorithm uses the concept of bipartite graph. The main difference between these two algorithms rests on the considered sets of faces. The first considers a unique set of faces per object constituted on intersecting faces and neighbouring faces whereas the second uses several subsets of this set by using a bipartite graph.


AUTEUR(S)
Sandrine LANQUETIN, Sebti FOUFOU, Hamamache KHEDDOUCI, Marc NEVEU

MOTS-CLÉS
opérations booléennes, courbes d'intersection, surface de subdivision, principe de Loop.

KEYWORDS
boolean operations, intersection curves, subdivision surfaces, Loop schemes.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 34.95 €
• Non abonné : 34.95 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (2,18 Mo)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
made by WAW Lavoisier