Approximating Implicit Curves On Triangulations With Affine Arithmetic

We present an adaptive method for computing a robust polygonal approximation of an implicit curve in the plane that uses affine arithmetic to identify regions where the curve lies inside a thin strip. Unlike other interval methods, even those based on affine arithmetic, our method works on triangulations, not only on rectangular quad trees. © 2012 IEEE.94101De Figueiredo, L.H., Stolfi, J., Affine arithmetic: Concepts and applications (2004) Numerical Algorithms, 37 (1-4 SPEC. ISS.), pp. 147-158. , DOI 10.1023/B:NUMA.0000049462.70970.b6Dobkin, D.P., Levy, S.V.F., Thurston, W.P., Wilks, A.R., Contour tracing by piecewise linear approximations (1990) ACM Transactions on Graphics, 9 (4), pp. 389-423Persiano, R.C.M., Ao, J., Comba, L.D., Barbalho, V., An adaptive triangulation refinement scheme and construction (1993) Proceedings of SIBGRAPI'93, pp. 259-266Suffern, K.G., Fackerell, E.D., Interval methods in computer graphics (1991) Computers & Graphics, 15 (3), pp. 331-340Mitchell, D.P., Three applications of interval analysis in computer graphics (1991) Frontiers in Rendering Course Notes. SIGGRAPH'91, pp. 1401-1413Lopes, H., Oliveira, J.B., De Figueiredo, L.H., Robust adaptive polygonal approximation of implicit curves (2002) Computers & Graphics, 26 (6), pp. 841-852Comba, J.L.D., Stolfi, J., Affine arithmetic and its applications to computer graphics (1993) Proceedings of SIBGRAPI'93, pp. 9-18Martin, R., Shou, H., Voiculescu, I., Bowyer, A., Wang, G., Comparison of interval methods for plotting algebraic curves (2002) Computer Aided Geometric Design, 19 (7), pp. 553-587. , DOI 10.1016/S0167-8396(02)00146-2, PII S0167839602001462De Cusatis Jr., A., De Figueiredo, L.H., Gattass, M., Interval methods for ray casting implicit surfaces with affine arithmetic (1999) Proceedings of SIBGRAPI'99, pp. 65-71. , IEEE PressDe Figueiredo, L.H., Stolfi, J., Velho, L., Approximating parametric curves with strip trees using affine arithmetic (2003) Computer Graphics Forum, 22 (2), pp. 171-179Bühler, K., Fast and reliable plotting of implicit curves (2002) Uncertainty Geometric Computations, pp. 15-28. , Kluwer AcademicBühler, K., Implicit linear interval estimations (2002) Proceedings of SCCG '02, pp. 123-132. , ACMMoore, R.E., (1966) Interval Analysis, , Prentice-HallStolfi, J., De Figueiredo, L.H., (1997) Self-Validated Numerical Methods and Applications, , 21st Brazilian Mathematics Colloquium, IMPATaubin, G., Rasterizing algebraic curves and surfaces (1994) IEEE Computer Graphics and Applications, 14, pp. 14-23Velho, L., Zorin, D., 4-8 Subdivision (2001) Computer Aided Geometric Design, 18 (5), pp. 397-427. , DOI 10.1016/S0167-8396(01)00039-5, PII S0167839601000395Kobbelt, L., Radic 3-subdivision (2000) Proceedings of SIGGRAPH '00, pp. 103-112. , AC