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