The following fundamental problem is of theoretical interest and has applications in graphics, computer aided design, and the analysis of polynomial surfaces: Suppose we are given (1) a function F : Rn→R , (2) an interval formulation of F and ∇ F, (3) an axis aligned closed hypercube B0 ⊂ Rn , and (4) a distance epsilon > 0. Assuming 0 is a regular value of F, and some additional conditions on F, find a piecewise linear approximation V of {F = 0} in the sense that it lies within epsilon of and is isotopic to B 0 ∩ {F = 0}.;It is often the topological condition which is difficult to ensure. We present a theorem which introduces a new test for topological accuracy. Making use of this, we develop a family of algorithms very similar in form to the Vegter-Plantinga algorithm. They are correct for all n and we implement a variation which is practical when n ≤ 4. This is the first known numeric (as opposed to algebraic) algorithm which ensures the topological guarantee with n > 3. When n ≤ 3 this algorithm produces a mesh with densities similar to those produced by the Vegter-Plantinga algorithm. For n = 2 we describe an advancing boxes algorithm which is based on subdivision followed by an advancing front style progression. It has several unique characteristics, including an ability to ensure good approximations of surface normals and no requirement for precise sign determination of F.
展开▼
