6533b859fe1ef96bd12b8258
RESEARCH PRODUCT
A Graph Based Algorithm For Intersection Of Subdivision Surfaces
Hamamache KheddouciSebti FoufouSandrine LanquetinMarc Neveusubject
Discrete mathematicsFoster graph[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM][INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Intersection number (graph theory)Intersection graphlaw.inventionCombinatorics[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]IntersectionlawHomeomorphism (graph theory)Subdivision surfaceCircle graphAlgorithmComputingMilieux_MISCELLANEOUS[ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]ComputingMethodologies_COMPUTERGRAPHICSMathematicsDistance-hereditary graphdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2003-01-01 |