Adaptive isotopic approximation of nonsingular curves and surfaces

摘要: Consider the problem of computing isotopic approximations nonsingular curves and surfaces that are implicitly represented by equations form f(X,Y) = 0 f(X,Y,Z ) 0. This fundamental has seen much progress along several fronts, but we will focus on domain subdivision algorithms. Two algorithms in this area from Snyder (1992) Plantinga & Vegter (2004). We introduce a family new combines advantages these two algorithms: like Snyder, use parameterizability criterion for subdivision, Vegter, exploit nonlocal isotopy. We first apply our approach to curves, resulting more efficient algorithm. then extend surfaces. The extension is no means routine, as correctness arguments case analysis subtle. Also, phenomenon arises which local rules constructing longer sufficient. further important practical directions: first, allow cells be non squares or cubes, with arbitrary bounded aspect ratios: 2D, boxes split into 2 4 children; 3D, 2, 8 children. Second, input region-of-interest (ROI) have geometry an quadtree octree, long singularities ROI intersects boundary transversally. Our algorithm numerical because primitives based interval arithmetic exact BigFloat numbers. It practical, easy implement exactly (compared algebraic approaches) does not suffer implementation gaps geometric approaches). report some very encouraging experimental results, showing can than (2D 3D) only).