Extending the A-patch single sheet conditions to enable the tessellation of algebraics

ABSTRACT

A-patches are a form of representation of an algebraic curve or surface over a simplex. The A-patch conditions can be used as the basis for an adaptive subdivision style marching tetrahedra algorithm whose advantage is that it guarantees that we do not miss features of the algebraic: singularities are localized, and in regions around nearby multiple sheets, the subdivision process continues until the sheets are separated.

Unfortunately, the A-patch single sheet conditions are too strict: for some algebraics, the subdivision process converges slowly or fails to converge. In this paper, I give an additional single sheet condition for curves that allows for convergence of this process. I also give additional conditions for surfaces that trades off some of the single sheet guarantees for improved convergence.

REFERENCES

• 1: L. Alberti, G. Comte, and B. Mourrain. Meshing implicit algebraic surfaces: the smooth case. In L. Schumaker, M. Maehlen, and K. Morken, editors, Mathematical Methods for Curves and Surfaces: Tromso '04. Nashboro, 2005.
• 2: C. L. Bajaj, J. Chen, and G. Xu. Modeling with cubic A-patches. ACM Transactions on Graphics, Volume 14, Issue 2, pages 103--133, 1995.
• 3: H. Lopes, J. B. Oliveira, and L. H. de Figueiredo. Robust adaptive polygonal approximation of implicit curves. Computers and Graphics, 26, 2002.
• 4: W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. Computer Graphics, Volume 21, Number 4, July 1987, pages 163--169, 1987.
• 5: C. Luk. Tessellating algebraic curves and surfaces using A-Patches. Master's thesis, University of Waterloo, 2008.
• 6: C. Luk and S. Mann. Tessellating algebraic curves and surfaces using a-patches. In GRAPP 2009 Proceedings, pages 83--89, 2009.
• 7: S. Mann. A Blossoming Approach to Splines. Morgan-Claypool, 2006.
• 8: S. Mann. Using A-patches to tessellate algebraic curves and surfaces. Technical Report CS-2009-21, University of Waterloo, 2009.
• 9: T. Newman and H. Yi. A survey of the marching cubes algorithm. Computer and Graphics, 30(5):854--879, October 2006.
• 10: B. Payne and A. Toga. Surface mapping brain function on 3D models. Computer Graphics and Applications, 10(5):33--41, September 1990.
• 11: P. Shirley and A. Tuchman. A polygonal approximation to direct scalar volume rendering. In Computer Graphics, pages 63--70, 1990.
• 12: G. Taubin. Distance approximations for rasterizing implicit curves. ACM Transactions on Graphics, 13(1):3--42, January 1994.
• 13: J. Wilhelms and A. van Gelder. Octrees for faster isosurface generation. ACM Transcations on Graphics, 11(3):201--227, 1992.

INDEX TERMS

Keywords:
A-patches, adaptive tessellation, algebraic surfaces