A graph based algorithm for intersection of subdivision surfaces

S. Lanquetin; S. Foufou; H. Kheddouci; M. Neveu

doi:10.1007/3-540-44842-x_40

A graph based algorithm for intersection of subdivision surfaces

S. Lanquetin, S. Foufou, H. Kheddouci, M. Neveu

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

Computing surface intersections is a fundamental problem in geometric modeling. Any boolean operation can be seen as an intersection calculation followed by a selection of the parts necessary for building the surface of the resulting object. A robust and efficient algorithm to compute intersection on subdivision surfaces (surfaces generated by the Loop scheme) is proposed here. This algorithm relies on the concept of a bipartite graph which allows the reduction of the number of faces intersection tests. Intersection computations are accelerated by the use of the bipartite graph and the neighborhood of intersecting faces at a given level of subdivision to deduce intersecting faces at the following levels of subdivision.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Vipin Kumar, Marina L. Gavrilova, Chih Jeng Kenneth Tan, Pierre L’Ecuyer, Chih Jeng Kenneth Tan
Publisher	Springer Verlag
Pages	387-396
Number of pages	10
ISBN (Print)	3540401563
DOIs	https://doi.org/10.1007/3-540-44842-x_40
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2669
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44842-x_40

Cite this

Lanquetin, S., Foufou, S., Kheddouci, H., & Neveu, M. (2003). A graph based algorithm for intersection of subdivision surfaces. In V. Kumar, M. L. Gavrilova, C. J. Kenneth Tan, P. L’Ecuyer, & C. J. Kenneth Tan (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 387-396). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2669). Springer Verlag. https://doi.org/10.1007/3-540-44842-x_40

A graph based algorithm for intersection of subdivision surfaces. / Lanquetin, S.; Foufou, S.; Kheddouci, H. et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Vipin Kumar; Marina L. Gavrilova; Chih Jeng Kenneth Tan; Pierre L’Ecuyer; Chih Jeng Kenneth Tan. Springer Verlag, 2003. p. 387-396 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2669).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Lanquetin, S, Foufou, S, Kheddouci, H & Neveu, M 2003, A graph based algorithm for intersection of subdivision surfaces. in V Kumar, ML Gavrilova, CJ Kenneth Tan, P L’Ecuyer & CJ Kenneth Tan (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2669, Springer Verlag, pp. 387-396. https://doi.org/10.1007/3-540-44842-x_40

Lanquetin S, Foufou S, Kheddouci H, Neveu M. A graph based algorithm for intersection of subdivision surfaces. In Kumar V, Gavrilova ML, Kenneth Tan CJ, L’Ecuyer P, Kenneth Tan CJ, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 387-396. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44842-x_40

Lanquetin, S. ; Foufou, S. ; Kheddouci, H. et al. / A graph based algorithm for intersection of subdivision surfaces. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Vipin Kumar ; Marina L. Gavrilova ; Chih Jeng Kenneth Tan ; Pierre L’Ecuyer ; Chih Jeng Kenneth Tan. Springer Verlag, 2003. pp. 387-396 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{bfa90c86011143c58bf0f35979fcb4ba,

title = "A graph based algorithm for intersection of subdivision surfaces",

abstract = "Computing surface intersections is a fundamental problem in geometric modeling. Any boolean operation can be seen as an intersection calculation followed by a selection of the parts necessary for building the surface of the resulting object. A robust and efficient algorithm to compute intersection on subdivision surfaces (surfaces generated by the Loop scheme) is proposed here. This algorithm relies on the concept of a bipartite graph which allows the reduction of the number of faces intersection tests. Intersection computations are accelerated by the use of the bipartite graph and the neighborhood of intersecting faces at a given level of subdivision to deduce intersecting faces at the following levels of subdivision.",

author = "S. Lanquetin and S. Foufou and H. Kheddouci and M. Neveu",

year = "2003",

doi = "10.1007/3-540-44842-x_40",

language = "English (US)",

isbn = "3540401563",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "387--396",

editor = "Vipin Kumar and Gavrilova, {Marina L.} and {Kenneth Tan}, {Chih Jeng} and Pierre L{\textquoteright}Ecuyer and {Kenneth Tan}, {Chih Jeng}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - A graph based algorithm for intersection of subdivision surfaces

AU - Lanquetin, S.

AU - Foufou, S.

AU - Kheddouci, H.

AU - Neveu, M.

PY - 2003

Y1 - 2003

N2 - Computing surface intersections is a fundamental problem in geometric modeling. Any boolean operation can be seen as an intersection calculation followed by a selection of the parts necessary for building the surface of the resulting object. A robust and efficient algorithm to compute intersection on subdivision surfaces (surfaces generated by the Loop scheme) is proposed here. This algorithm relies on the concept of a bipartite graph which allows the reduction of the number of faces intersection tests. Intersection computations are accelerated by the use of the bipartite graph and the neighborhood of intersecting faces at a given level of subdivision to deduce intersecting faces at the following levels of subdivision.

AB - Computing surface intersections is a fundamental problem in geometric modeling. Any boolean operation can be seen as an intersection calculation followed by a selection of the parts necessary for building the surface of the resulting object. A robust and efficient algorithm to compute intersection on subdivision surfaces (surfaces generated by the Loop scheme) is proposed here. This algorithm relies on the concept of a bipartite graph which allows the reduction of the number of faces intersection tests. Intersection computations are accelerated by the use of the bipartite graph and the neighborhood of intersecting faces at a given level of subdivision to deduce intersecting faces at the following levels of subdivision.

UR - http://www.scopus.com/inward/record.url?scp=35248864455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248864455&partnerID=8YFLogxK

U2 - 10.1007/3-540-44842-x_40

DO - 10.1007/3-540-44842-x_40

M3 - Chapter

AN - SCOPUS:35248864455

SN - 3540401563

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 387

EP - 396

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Kumar, Vipin

A2 - Gavrilova, Marina L.

A2 - Kenneth Tan, Chih Jeng

A2 - L’Ecuyer, Pierre

A2 - Kenneth Tan, Chih Jeng

PB - Springer Verlag

ER -

A graph based algorithm for intersection of subdivision surfaces

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this