{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T17:54:55Z","timestamp":1720806895999},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Comput. Graph. Interact. Tech."],"published-print":{"date-parts":[[2020,8,26]]},"abstract":"We present a simple degree reduction technique for piecewise cubic polynomial splines, converting them into piecewise quadratic splines that maintain the parameterization and C1 continuity. Our method forms identical tangent directions at the interpolated data points of the piecewise cubic spline by replacing each cubic piece with a pair of quadratic pieces. The resulting representation can lead to substantial performance improvements for rendering geometrically complex spline models like hair and fiber-level cloth. Such models are typically represented using cubic splines that are C1-continuous, a property that is preserved with our degree reduction. Therefore, our method can also be considered a new quadratic curve construction approach for high-performance rendering. We prove that it is possible to construct a pair of quadratic curves with C1 continuity that passes through any desired point on the input cubic curve. Moreover, we prove that when the pair of quadratic pieces corresponding to a cubic piece have equal parametric lengths, they join exactly at the parametric center of the cubic piece, and the deviation in positions due to degree reduction is minimized.<\/jats:p>","DOI":"10.1145\/3406178","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T17:45:26Z","timestamp":1616521526000},"page":"1-17","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Quadratic Approximation of Cubic Curves"],"prefix":"10.1145","volume":"3","author":[{"given":"Nghia","family":"Truong","sequence":"first","affiliation":[{"name":"University of Utah"}]},{"given":"Cem","family":"Yuksel","sequence":"additional","affiliation":[{"name":"University of Utah"}]},{"given":"Larry","family":"Seiler","sequence":"additional","affiliation":[{"name":"Facebook Reality Labs"}]}],"member":"320","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Jens Alfke. 1994. Converting B\u00e9zier Curves to Quadratic Splines. http:\/\/steve.hollasch.net\/cgindex\/curves\/cbez-quadspline.html Jens Alfke. 1994. Converting B\u00e9zier Curves to Quadratic Splines. http:\/\/steve.hollasch.net\/cgindex\/curves\/cbez-quadspline.html"},{"key":"e_1_2_2_2_1","volume-title":"Jeppe Revall Frisvad, and Niels J\u00f8rgen Christensen","author":"Andersen Tobias Gr\u00f8beck","year":"2016","unstructured":"Tobias Gr\u00f8beck Andersen , Viggo Falster , Jeppe Revall Frisvad, and Niels J\u00f8rgen Christensen . 2016 . Hybrid Fur Rendering: Combining Volumetric Fur with Explicit Hair Strands. Vis. Comput . 32, 6--8 (June 2016), 739--749. Tobias Gr\u00f8beck Andersen, Viggo Falster, Jeppe Revall Frisvad, and Niels J\u00f8rgen Christensen. 2016. Hybrid Fur Rendering: Combining Volumetric Fur with Explicit Hair Strands. Vis. Comput. 32, 6--8 (June 2016), 739--749."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366181"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/378456.378511"},{"key":"e_1_2_2_5_1","volume-title":"Barsky","author":"Bartels Richard H.","year":"1987","unstructured":"Richard H. Bartels , John C. Beatty , and Brian A . Barsky . 1987 . An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. Morgan Kaufmann Publishers Inc ., San Francisco, CA, USA. Richard H. Bartels, John C. Beatty, and Brian A. Barsky. 1987. An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA."},{"key":"e_1_2_2_6_1","unstructured":"P. B\u00e9zier. 1977. Essai de d\u00e9finition num\u00e9rique des courbes et des surfaces exp\u00e9rimentales: contribution \u00e0 l'\u00e9tude des propri\u00e9t\u00e9s des courbes et des surfaces param\u00e9triques polynomiales \u00e0 coefficients vectoriels. Number v. 1. Universite Pierre et Marie Curie (Paris VI). P. B\u00e9zier. 1977. Essai de d\u00e9finition num\u00e9rique des courbes et des surfaces exp\u00e9rimentales: contribution \u00e0 l'\u00e9tude des propri\u00e9t\u00e9s des courbes et des surfaces param\u00e9triques polynomiales \u00e0 coefficients vectoriels. Number v. 1. Universite Pierre et Marie Curie (Paris VI)."},{"key":"e_1_2_2_7_1","volume-title":"On the method of rapid approximation of a cubic B\u00e9zier curve by quadratic B\u00e9zier curves. Silesian Journal of Pure and Applied Mathematics","author":"Bily Barbara","year":"2014","unstructured":"Barbara Bily . 2014. On the method of rapid approximation of a cubic B\u00e9zier curve by quadratic B\u00e9zier curves. Silesian Journal of Pure and Applied Mathematics ( 2014 ). Barbara Bily. 2014. On the method of rapid approximation of a cubic B\u00e9zier curve by quadratic B\u00e9zier curves. Silesian Journal of Pure and Applied Mathematics (2014)."},{"key":"e_1_2_2_8_1","volume-title":"A Class of Local Interpolating Splines","author":"Catmull Edwin","unstructured":"Edwin Catmull and Raphael Rom . 1974a. A Class of Local Interpolating Splines . In Computer Aided Geometric Design, Robert E. Barnhill and Richard F. Riesenfeld (Eds.). Academic Press , 317 - 326. Edwin Catmull and Raphael Rom. 1974a. A Class of Local Interpolating Splines. In Computer Aided Geometric Design, Robert E. Barnhill and Richard F. Riesenfeld (Eds.). Academic Press, 317 - 326."},{"key":"e_1_2_2_9_1","volume-title":"Catmull and Raphael Rom","author":"Edwin","year":"1974","unstructured":"Edwin E. Catmull and Raphael Rom . 1974 b. A class of local interpolating splines. Computer Aided Geometric Design ( 1974), 317--326. Edwin E. Catmull and Raphael Rom. 1974b. A class of local interpolating splines. Computer Aided Geometric Design (1974), 317--326."},{"key":"e_1_2_2_10_1","unstructured":"Adrian Colomitchi. 2006. Approximating cubic B\u00e9zier curves by quadratic ones. http:\/\/www.caffeineowl.com\/graphics\/2d\/vectorial\/cubic2quad01.html Adrian Colomitchi. 2006. Approximating cubic B\u00e9zier curves by quadratic ones. http:\/\/www.caffeineowl.com\/graphics\/2d\/vectorial\/cubic2quad01.html"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/11.2.159"},{"key":"e_1_2_2_12_1","volume-title":"Curves and Surfaces for Computer Aided Geometric Design","author":"Farin Gerald","unstructured":"Gerald Farin . 1997. Curves and Surfaces for Computer Aided Geometric Design ( 4 th Ed.): A Practical Guide. Academic Press Professional , Inc., USA. Gerald Farin. 1997. Curves and Surfaces for Computer Aided Geometric Design (4th Ed.): A Practical Guide. Academic Press Professional, Inc., USA.","edition":"4"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1176499.1648473"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Thomas A. Foley Nielson and Gregory M. 1989. Knot Selection for Parametric Spline Interpolation -- Mathematical Methods in Computer Aided Geometric Design. Academic Press Professional Inc. San Diego CA USA. 261--272 pages. Thomas A. Foley Nielson and Gregory M. 1989. Knot Selection for Parametric Spline Interpolation -- Mathematical Methods in Computer Aided Geometric Design. Academic Press Professional Inc. San Diego CA USA. 261--272 pages.","DOI":"10.1016\/B978-0-12-460515-2.50023-8"},{"key":"e_1_2_2_15_1","unstructured":"Timoth\u00e9e Groleau. 2002. Approximating Cubic B\u00e9zier Curves in Flash MX. http:\/\/www.timotheegroleau.com\/Flash\/articles\/cubic_bezier_in_flash.htm Timoth\u00e9e Groleau. 2002. Approximating Cubic B\u00e9zier Curves in Flash MX. http:\/\/www.timotheegroleau.com\/Flash\/articles\/cubic_bezier_in_flash.htm"},{"key":"e_1_2_2_16_1","volume-title":"Johnson","author":"Han Mengjiao","year":"2019","unstructured":"Mengjiao Han , Ingo Wald , Will Usher , Qi Wu , Feng Wang , Valerio Pascucci , Charles D. Hansen , and Chris R . Johnson . 2019 . Ray Tracing Generalized Tube Primitives: Method and Applications. Computer Graphics Forum ( 2019). Mengjiao Han, Ingo Wald, Will Usher, Qi Wu, Feng Wang, Valerio Pascucci, Charles D. Hansen, and Chris R. Johnson. 2019. Ray Tracing Generalized Tube Primitives: Method and Applications. Computer Graphics Forum (2019)."},{"key":"e_1_2_2_17_1","volume-title":"Eurographics","author":"Higashi Masatake","year":"1988","unstructured":"Masatake Higashi , Kohji Kaneko , and Mamoru Hosaka . 1988. Generation of High-Quality Curve and Surface with Smoothly Varying Curvature . In Eurographics 1988 . Eurographics Association . Masatake Higashi, Kohji Kaneko, and Mamoru Hosaka. 1988. Generation of High-Quality Curve and Surface with Smoothly Varying Curvature. In Eurographics 1988. Eurographics Association."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778842"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(89)90003-1"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(92)90050-Y"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(98)00025-9"},{"key":"e_1_2_2_22_1","volume-title":"Ray Tracing for Curves Primitive. WSCG","author":"Nakamaru Koji","year":"2002","unstructured":"Koji Nakamaru and Yoshio Ohno . 2002. Ray Tracing for Curves Primitive. WSCG ( 2002 ), 311--316. Koji Nakamaru and Yoshio Ohno. 2002. Ray Tracing for Curves Primitive. WSCG (2002), 311--316."},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"G. Nielson and T. Foley. 1989. A Survey of Applications of an Affine Invariant Metric -- Mathematical methods in computer aided geometric design. (1989) 445--468. G. Nielson and T. Foley. 1989. A Survey of Applications of an Affine Invariant Metric -- Mathematical methods in computer aided geometric design. (1989) 445--468.","DOI":"10.1016\/B978-0-12-460515-2.50036-6"},{"key":"e_1_2_2_24_1","volume-title":"Physically Based Rendering: From Theory to Implementation","author":"Pharr Matt","unstructured":"Matt Pharr , Wenzel Jakob , and Greg Humphreys . 2016. Physically Based Rendering: From Theory to Implementation ( 3 rd ed.). Morgan Kaufmann Publishers Inc ., San Francisco, CA, USA. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation (3rd ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.","edition":"3"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.270"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105762.3105783"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3233307"},{"key":"e_1_2_2_28_1","volume-title":"Approximation Of A Cubic B\u00e9zier Curve By Circular Arcs And Vice Versa. Information Technology and Control 35, 4","author":"Ri\u0161kus Aleksas","year":"2006","unstructured":"Aleksas Ri\u0161kus . 2006. Approximation Of A Cubic B\u00e9zier Curve By Circular Arcs And Vice Versa. Information Technology and Control 35, 4 ( 2006 ). Aleksas Ri\u0161kus. 2006. Approximation Of A Cubic B\u00e9zier Curve By Circular Arcs And Vice Versa. Information Technology and Control 35, 4 (2006)."},{"key":"e_1_2_2_29_1","volume-title":"An Improved Algorithm for the Approximation of a Cubic B\u00e9zier Curve and its Application for Approximating Quadratic B\u00e9zier Curve. Information Technology and Control 42, 4","author":"Ri\u0161kus Aleksas","year":"2013","unstructured":"Aleksas Ri\u0161kus and Giedrius Liutkus . 2013. An Improved Algorithm for the Approximation of a Cubic B\u00e9zier Curve and its Application for Approximating Quadratic B\u00e9zier Curve. Information Technology and Control 42, 4 ( 2013 ). Aleksas Ri\u0161kus and Giedrius Liutkus. 2013. An Improved Algorithm for the Approximation of a Cubic B\u00e9zier Curve and its Application for Approximating Quadratic B\u00e9zier Curve. Information Technology and Control 42, 4 (2013)."},{"key":"e_1_2_2_30_1","unstructured":"Mat Sutcliffe. 2007. Approximating cubic B\u00e9zier curves. https:\/\/academia.fandom.com\/wiki\/Approximating_cubic_Bezier_curves Mat Sutcliffe. 2007. Approximating cubic B\u00e9zier curves. https:\/\/academia.fandom.com\/wiki\/Approximating_cubic_Bezier_curves"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601199"},{"key":"e_1_2_2_32_1","volume-title":"Eurographics\/ ACM SIGGRAPH Symposium on High Performance Graphics, Ingo Wald and Jonathan Ragan-Kelley (Eds.)","author":"Woop Sven","unstructured":"Sven Woop , Carsten Benthin , Ingo Wald , Gregory S. Johnson , and Eric Tabellion . 2014. Exploiting Local Orientation Similarity for Efficient Ray Traversal of Hair and Fur . In Eurographics\/ ACM SIGGRAPH Symposium on High Performance Graphics, Ingo Wald and Jonathan Ragan-Kelley (Eds.) . The Eurographics Association . Sven Woop, Carsten Benthin, Ingo Wald, Gregory S. Johnson, and Eric Tabellion. 2014. Exploiting Local Orientation Similarity for Efficient Ray Traversal of Hair and Fur. In Eurographics\/ ACM SIGGRAPH Symposium on High Performance Graphics, Ingo Wald and Jonathan Ragan-Kelley (Eds.). The Eurographics Association."},{"key":"e_1_2_2_33_1","first-page":"12","article-title":"Real-time Cloth Rendering with Fiber-level Detail","volume":"99","author":"Wu Kui","year":"2017","unstructured":"Kui Wu and Cem Yuksel . 2017 a. Real-time Cloth Rendering with Fiber-level Detail . IEEE Transactions on Visualization and Computer Graphics PP , 99 (2017), 12 . Kui Wu and Cem Yuksel. 2017a. Real-time Cloth Rendering with Fiber-level Detail. IEEE Transactions on Visualization and Computer Graphics PP, 99 (2017), 12.","journal-title":"IEEE Transactions on Visualization and Computer Graphics PP"},{"key":"e_1_2_2_34_1","volume-title":"Real-time Fiber-level Cloth Rendering. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D 2017)","author":"Wu Kui","year":"2017","unstructured":"Kui Wu and Cem Yuksel . 2017 b. Real-time Fiber-level Cloth Rendering. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D 2017) (San Francisco, CA). ACM, New York, NY, USA, 8. Kui Wu and Cem Yuksel. 2017b. Real-time Fiber-level Cloth Rendering. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D 2017) (San Francisco, CA). ACM, New York, NY, USA, 8."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073692"},{"key":"e_1_2_2_36_1","volume-title":"Stitch Meshes for Modeling Knitted Clothing with Yarn-level Detail. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012)","author":"Yuksel Cem","year":"2012","unstructured":"Cem Yuksel , Jonathan M. Kaldor , Doug L. James , and Steve Marschner . 2012 . Stitch Meshes for Modeling Knitted Clothing with Yarn-level Detail. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012) 31, 3, Article 37 (2012), 12 pages. Cem Yuksel, Jonathan M. Kaldor, Doug L. James, and Steve Marschner. 2012. Stitch Meshes for Modeling Knitted Clothing with Yarn-level Detail. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012) 31, 3, Article 37 (2012), 12 pages."},{"key":"e_1_2_2_37_1","volume-title":"Article 166","author":"Yuksel Cem","year":"2009","unstructured":"Cem Yuksel , Scott Schaefer , and John Keyser . 2009a. Hair Meshes . ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2009) 28, 5 , Article 166 ( 2009 ), 7 pages. Cem Yuksel, Scott Schaefer, and John Keyser. 2009a. Hair Meshes. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2009) 28, 5, Article 166 (2009), 7 pages."},{"key":"e_1_2_2_38_1","volume-title":"On the Parameterization of Catmull-Rom Curves. In 2009 SIAM\/ACM Joint Conference on Geometric and Physical Modeling","author":"Yuksel Cem","year":"2009","unstructured":"Cem Yuksel , Scott Schaefer , and John Keyser . 2009 b. On the Parameterization of Catmull-Rom Curves. In 2009 SIAM\/ACM Joint Conference on Geometric and Physical Modeling ( San Francisco, California). ACM, New York, NY, USA, 47--53. Cem Yuksel, Scott Schaefer, and John Keyser. 2009b. On the Parameterization of Catmull-Rom Curves. In 2009 SIAM\/ACM Joint Conference on Geometric and Physical Modeling (San Francisco, California). ACM, New York, NY, USA, 47--53."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.08.008"}],"container-title":["Proceedings of the ACM on Computer Graphics and Interactive Techniques"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T11:13:37Z","timestamp":1675422817000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,26]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,8,26]]}},"alternative-id":["10.1145\/3406178"],"URL":"http:\/\/dx.doi.org\/10.1145\/3406178","relation":{},"ISSN":["2577-6193"],"issn-type":[{"value":"2577-6193","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,26]]},"assertion":[{"value":"2020-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}