5.8.2.2 Subdivision methods

Subdivision methods in their most basic form, involve recursive decomposition of the problem into simpler similar problems until a level of simplicity is reached, which allows simple direct solution, (e.g. plane/plane intersection [177,295]). This is followed by a connection phase of the individual solutions to form the complete solution. Dokken [77] transforms surface/surface intersection problems to finding zeroes of functions of four variables using recursive subdivision techniques [221]. Initially conceived in the context of intersections of polynomial parametric surfaces [220], they can be extended to the computation of RPP/IA and IA/IA surface intersections [302]. A simple subdivision algorithm employs uniform subdivision which leads to a uniform quadtree data structure shown in Fig. 5.23. Subdivision techniques do not require starting points as marching methods, an important advantage. General non-uniform subdivision allows selective refinement of the solution providing the basis for an adaptive intersection technique. A disadvantage of subdivision techniques used in the evaluation of the entire intersection set is that, in actual implementations with finite subdivision steps, correct connectivity of solution branches in the vicinity of singular or near-singular points is difficult to guarantee, small loops may be missed (in methods with polyhedral surface approximations) or extraneous loops may be present in the approximation of the solution. Furthermore, if subdivision methods are used for high precision evaluation of the entire intersection set, they lead to data proliferation and are consequently slow, and, therefore, unattractive. There are many applications in CAD/CAM, that require high accuracy, for which pure subdivision methods are impractical. However, adaptive subdivision methods coupled with efficient local techniques to get high accuracy, offer the best known practical approach for the computation of characteristic points. These points can then be used in initiating efficient marching methods for tracing intersection curves.

Figure 5.23: Subdivision method