Computing Subdivision Surface Intersection

Sandrine Lanquetin, Sebti Foufou, Hamamache Kheddouci, Marc Neveu
University of Bourgogne
Department of Computer Science
21078 Dijon Cedex



Keywords: Subdivision surfaces, Loop scheme, intersection curves, bipartite graph


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 parts necessary for building the surface of the resulting object. This paper deals with the computing of intersection curves on subdivision surfaces (surfaces generated by the Loop scheme). We present three variants of our algorithm. The first variant calculates this intersection after a classification of the object faces into intersecting and non intersecting pairs of faces. The second variant is based on the 1-neighborhood of the intersecting faces. The third variant uses the concept of bipartite graph.