{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T15:20:50Z","timestamp":1693927250000},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[1994,1]]},"abstract":"In this article we present new algorithms for rasterizing implicit curves, i.e., curves represented as level sets of functions of two variables. Considering the pixels as square regions of the plane, a \u201ccorrect\u201d algorithm should paint those pixels whose centers lie at less than half the desired line width from the curve. A straightforward implementation, scanning the display array evaluating the Euclidean distance from the center of each pixel to the curve, is impractical, and a standard quad-tree-like recursive subdivision scheme is used instead. Then we attack the problem of testing whether or not the Euclidean distance from a point to an implicit curve is less than a given threshold. For the most general case, when the implicit function is only required to have continuous first-order derivatives, we show how to reformulate the test as an unconstrained global root-finding problem in a circular domain. For implicit functions with continuous derivatives up to orderk<\/jats:italic>we introduce an approximate distance of orderk<\/jats:italic>. The approximate distance of orderk<\/jats:italic>from a point to an implicit curve is asymptotically equivalent to the Euclidean distance and provides a sufficient test for a polynomial of degreek<\/jats:italic>not to have roots inside a circle. This is the main contribution of the article. By replacing the Euclidean distance test with one of these approximate distance tests, we obtain a practical rendering algorithm, proven to be correct for algebraic curves. To speed up the computation we also introduce heuristics, which used in conjunction with low-order approximate distances almost always produce equivalent results. The behavior of the algorithms is analyzed, both near regular and singular points, and several possible extensions and applications are discussed.<\/jats:p>","DOI":"10.1145\/174462.174531","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:00Z","timestamp":1027769340000},"page":"3-42","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Distance approximations for rasterizing implicit curves"],"prefix":"10.1145","volume":"13","author":[{"given":"Gabriel","family":"Taubin","sequence":"first","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]}],"member":"320","published-online":{"date-parts":[[1994,1]]},"reference":[{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(87)90147-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(87)90235-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/1022003","article-title":"Simpliciai and continuation methods for approximating fixed points and solutions to systems of equations","volume":"22","author":"ALLGOWER E.","year":"1980","journal-title":"SIAM Rev."},{"key":"e_1_2_1_6_1","first-page":"2","article-title":"An algorithm for piecewise-linear approximation of an implicitly defined manifold","volume":"22","author":"ALLGOWEH E. L.","year":"1985","journal-title":"SIAM J. Num. Anal."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/964967.801152"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/29380.29862"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(88)90013-1"},{"key":"e_1_2_1_11_1","volume-title":"Ergebnisse der Mathematik un ihrer Grenzgebiete.","author":"BOC NAK"},{"key":"e_1_2_1_12_1","unstructured":"BORODIN A. AND MUNGO I. 1975. The Computational Complexity of Algebraic and Numeric Problems. American Elsevier New York. BORODIN A. AND MUNGO I. 1975. The Computational Complexity of Algebraic and Numeric Problems. American Elsevier New York."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"CANNY J.F. 1988. The Complexity of Robot Motion Planning. MIT Press Cambridge Mass. CANNY J.F. 1988. The Complexity of Robot Motion Planning. MIT Press Cambridge Mass.","DOI":"10.1109\/SFCS.1988.21947"},{"key":"e_1_2_1_14_1","first-page":"9","article-title":"Resolution of p(x, y) = O","volume":"23","author":"DE MOUNTAUDOUIN Y.","year":"1991","journal-title":"Comput. Aided Des."},{"key":"e_1_2_1_15_1","unstructured":"DENNIS J. E. AND SHNAItEI. R.B. 1983. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall Englewood Cliffs N.J. DENNIS J. E. AND SHNAItEI. R.B. 1983. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall Englewood Cliffs N.J."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/88560.88575"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"DOWLING; M. 1 . 1900. A fast parallel hornet algorithm. SIAM d. (?omput. 19 I (Feb.) 133 142 10.1137\/0219008 DOWLING; M. 1 . 1900. A fast parallel hornet algorithm. SIAM d. (?omput. 19 I (Feb.) 133 142 10.1137\/0219008","DOI":"10.1137\/0219008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2701.2705"},{"key":"e_1_2_1_19_1","unstructured":"GEIsow A. 1983. Surface interrogations. Ph.D. thesis Univ. of East Anglia School of Computing Studies U.K GEIsow A. 1983. Surface interrogations. Ph.D. thesis Univ. of East Anglia School of Computing Studies U.K"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/78964.78966"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"1052","DOI":"10.1109\/T-C.1973.223650","article-title":"An improved algorithm for the generation of nanparametrie curves","volume":"12","author":"JORDAN W.","year":"1973","journal-title":"IEEE Trans. Comput. C-22"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.62602"},{"key":"e_1_2_1_23_1","unstructured":"MANOCHA X D. 1992. Algebraic and numeric techniques in modeling and robotics. Ph.D. thesis Univ. of California at Berkeley Berkeley Cali~ MANOCHA X D. 1992. Algebraic and numeric techniques in modeling and robotics. Ph.D. thesis Univ. of California at Berkeley Berkeley Cali~"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"MANOCHA l). ANI) CANNY J.F. 1992. Multipolynomial resultant algorithms. Tech. Rep. Computer Science Div. Univ. of. Califi~rnia at Berkeley Berkeley Cali~ MANOCHA l). ANI) CANNY J.F. 1992. Multipolynomial resultant algorithms. Tech. Rep. Computer Science Div. Univ. of. Califi~rnia at Berkeley Berkeley Cali~","DOI":"10.1006\/jsco.1993.1009"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/328512.328521"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"OVERMARS m. H. 1988. Geometric data structures for computer graphics: an overview. In Theoretical Foundations of Computer Graphics and CAD. NAT() ASI Series vol. F40 Springer-Verlag 21- 49. OVERMARS m. H. 1988. Geometric data structures for computer graphics: an overview. In Theoretical Foundations of Computer Graphics and CAD. NAT() ASI Series vol. F40 Springer-Verlag 21- 49.","DOI":"10.1007\/978-3-642-83539-1_1"},{"key":"e_1_2_1_29_1","unstructured":"PEDERSEN P. 1991a. Counting real zeros. Ph.D. thesis New York Univ. New York. PEDERSEN P. 1991a. Counting real zeros. Ph.D. thesis New York Univ. New York."},{"key":"e_1_2_1_30_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 9th International ~;ymposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"PEDERSEN X, P"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/1049-9660(92)90016-V"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"PRATT V. 1987. Direct least squares fitting of algebraic surfaces. Cornput. Graph. 21 4 ( July) 145 152. 10.1145\/37402.37420 PRATT V. 1987. Direct least squares fitting of algebraic surfaces. Cornput. Graph. 21 4 ( July) 145 152. 10.1145\/37402.37420","DOI":"10.1145\/37402.37420"},{"key":"e_1_2_1_33_1","series-title":"NATO ASI Series","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"SAMET H."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0146-664X(82)90101-0","article-title":"Fitting conic sections to very scattered data: An iterative refinement of the bookstein algorithm","volume":"18","author":"SAMPSON P.D.","year":"1982","journal-title":"Comput. Vis. Graph. Image Pro{'."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/0734-189X(84)90140-3","article-title":"Implicit representation of parametric curves and surfaces","volume":"28","author":"SEDERBERG T. W.","year":"1984","journal-title":"Comput. Vis. Graph. Image Prec."},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"Implicitization, inversion, and intersection of planar rational cubic curves","volume":"31","author":"SEDERBERG T. W.","year":"1985","journal-title":"Comput. Vis. Graph. Image Pro{."},{"key":"e_1_2_1_37_1","unstructured":"SERRA 1. 1982. Image Analysis and Mathematical Morphology. Academic Press New York. SERRA 1. 1982. Image Analysis and Mathematical Morphology. Academic Press New York."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the IEEE Conference on Robotics and Automation. IEEE","author":"TAUBIN G.","year":"1988"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.103273"},{"key":"e_1_2_1_40_1","volume-title":"the ACM Symposium on Solid Modeling and Applications. ACM","author":"TAUBIN G.","year":"1993"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.276128"},{"key":"e_1_2_1_42_1","first-page":"103","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. IEEE","author":"TAUBIN G.","year":"1992"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"THORPE J.A. 1979. Elementary Topics in Differential Geometry. Springer-Verlag New York. THORPE J.A. 1979. Elementary Topics in Differential Geometry. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-6153-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"VAN AKFN J. AND NOVAK M. Curve-drawing algorithms for raster displays. ACM Trans. Graph. 4 2 147-169. 10.1145\/282918.282943 VAN AKFN J. AND NOVAK M. Curve-drawing algorithms for raster displays. ACM Trans. Graph. 4 2 147-169. 10.1145\/282918.282943","DOI":"10.1145\/282918.282943"},{"key":"e_1_2_1_45_1","volume-title":"R 1950. Algebraic Curves","author":"WALKER"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/174462.174531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,23]],"date-time":"2023-04-23T17:34:16Z","timestamp":1682271256000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/174462.174531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1145\/174462.174531"],"URL":"http:\/\/dx.doi.org\/10.1145\/174462.174531","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[1994,1]]},"assertion":[{"value":"1994-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}