A graph based algorithm for intersection of subdivision surfaces

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

Research output: Chapter in Book/Report/Conference proceedingChapter

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 languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsVipin Kumar, Marina L. Gavrilova, Chih Jeng Kenneth Tan, Pierre L’Ecuyer, Chih Jeng Kenneth Tan
PublisherSpringer Verlag
Pages387-396
Number of pages10
ISBN (Print)3540401563
DOIs
StatePublished - 2003

Publication series

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A graph based algorithm for intersection of subdivision surfaces'. Together they form a unique fingerprint.

Cite this