{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T06:03:31Z","timestamp":1750831411363,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israeli Ministry of Science","award":["Mar-73"],"award-info":[{"award-number":["Mar-73"]}]},{"name":"NRF Research","award":["2010-007872011-00034742011-0018017"],"award-info":[{"award-number":["2010-007872011-00034742011-0018017"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>We present a compact representation for the bounding volume hierarchy (BVH) of freeform NURBS surfaces using Coons patches. Following the Coons construction, each subpatch can be bounded very efficiently using the bilinear surface determined by the four corners. The BVH of freeform surfaces is represented as a hierarchy of Coons patch approximation until the difference is reduced to within a given error bound. Each leaf node contains a single Coons patch, where a detailed BVH for the patch can be represented very compactly using two lists (containing curve approximation errors) of length proportional only to the height of the BVH. We demonstrate the effectiveness of our compact BVH representation using several experimental results from real-time applications in collision detection and minimum distance computation for freeform models.<\/jats:p>","DOI":"10.1145\/2070781.2024203","type":"journal-article","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T13:58:46Z","timestamp":1322661526000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Coons BVH for freeform geometric models"],"prefix":"10.1145","volume":"30","author":[{"given":"Yong-Joon","family":"Kim","sequence":"first","affiliation":[{"name":"Seoul National University"}]},{"given":"Young-Taek","family":"Oh","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Seung-Hyun","family":"Yoon","sequence":"additional","affiliation":[{"name":"Dongguk University"}]},{"given":"Myung-Soo","family":"Kim","sequence":"additional","affiliation":[{"name":"Seoul National University"}]},{"given":"Gershon","family":"Elber","sequence":"additional","affiliation":[{"name":"Technion"}]}],"member":"320","published-online":{"date-parts":[[2011,12,12]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Hoffman","author":"Akenine-M\u00f6ller T.","year":"2008","unstructured":"Akenine-M\u00f6ller , T. , Hains , E. , Hoffman , N. : Real-Time Rendering, A. K. Peters, Natick, MA , 3 rd Ed., 2008 . Akenine-M\u00f6ller, T., Hains, E., Hoffman, N.: Real-Time Rendering, A. K. Peters, Natick, MA, 3rd Ed., 2008.","edition":"3"},{"key":"e_1_2_2_2_1","volume-title":"Peters","author":"Cohen E.","year":"2001","unstructured":"Cohen , E. , Riesenfeld , R. , and Elber , G .: Geometric Modeling with Splines: An Introduction, A. K . Peters , Natick, MA , 2001 . Cohen, E., Riesenfeld, R., and Elber, G.: Geometric Modeling with Splines: An Introduction, A. K. Peters, Natick, MA, 2001."},{"key":"e_1_2_2_3_1","volume-title":"MIT","author":"Coons S.","year":"1964","unstructured":"Coons , S. : Surfaces for Computer-Aided Design, Technical report , MIT , 1964 . Available as AD 663 504 from the National Technical Information Service, Springfield, VA, 22161. Coons, S.: Surfaces for Computer-Aided Design, Technical report, MIT, 1964. Available as AD 663 504 from the National Technical Information Service, Springfield, VA, 22161."},{"key":"e_1_2_2_4_1","volume-title":"Curves and Surfaces for CAGD","author":"Farin G.","year":"2002","unstructured":"Farin , G. : Curves and Surfaces for CAGD , 5 th Ed., MorganKaufmann , San Francisco, CA , 2002 . Farin, G.: Curves and Surfaces for CAGD, 5th Ed., MorganKaufmann, San Francisco, CA, 2002.","edition":"5"},{"key":"e_1_2_2_5_1","first-page":"2","article-title":"A fast procedure for computing the distance between complex objects in three-dimensional space","volume":"4","author":"Gilbert E.","year":"1988","unstructured":"Gilbert , E. , Johnson , D. , Keerthi , S. : A fast procedure for computing the distance between complex objects in three-dimensional space . IEEE Trans. Robot. Automat. 4 , 2 , 193--203, 1988 . Gilbert, E., Johnson, D., Keerthi, S.: A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Trans. Robot. Automat. 4, 2, 193--203, 1988.","journal-title":"IEEE Trans. Robot. Automat."},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1145\/237170.237244"},{"key":"e_1_2_2_7_1","first-page":"25","volume-title":"Proc. Eurographics\/SIGGRAPH Graphics Hardware Workshop","author":"Govindaraju N.","year":"2003","unstructured":"Govindaraju , N. , Redon , S. , Lin , M. , Manocha , D. : Cullide: interactive collision detection between complex models in large environments using graphics hardware . Proc. Eurographics\/SIGGRAPH Graphics Hardware Workshop , pp. 25 -- 32 , 2003 . Govindaraju, N., Redon, S., Lin, M., Manocha, D.: Cullide: interactive collision detection between complex models in large environments using graphics hardware. Proc. Eurographics\/SIGGRAPH Graphics Hardware Workshop, pp. 25--32, 2003."},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.1145\/1201775.882358"},{"unstructured":"IRIT 10.0 User's Manual Technion. http:\/\/www.cs.technion.ac.il\/~irit.  IRIT 10.0 User's Manual Technion. http:\/\/www.cs.technion.ac.il\/~irit.","key":"e_1_2_2_9_1"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1145\/1015706.1015735"},{"key":"e_1_2_2_11_1","volume-title":"E.: A framework for efficient minimum distance computations","author":"Johnson D.","year":"1998","unstructured":"Johnson , D. , Cohen , E.: A framework for efficient minimum distance computations . IEEE Int'l Conf. on Robotics and Automation , 3678--3684, 1998 . Johnson, D., Cohen, E.: A framework for efficient minimum distance computations. IEEE Int'l Conf. on Robotics and Automation, 3678--3684, 1998."},{"key":"e_1_2_2_12_1","first-page":"7","article-title":"HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. (Proc. of Pacific Graphics 2009)","volume":"28","author":"Kim D.","year":"1800","unstructured":"Kim , D. , Heo , J.-P. , Huh , J. , Kim , J. , Yoon , S.-E. : HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. (Proc. of Pacific Graphics 2009) , Computer Graphics Forum 28 , 7 , 1791-- 1800 , 2009. Kim, D., Heo, J.-P., Huh, J., Kim, J., Yoon, S.-E.: HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. (Proc. of Pacific Graphics 2009), Computer Graphics Forum 28, 7, 1791--1800, 2009.","journal-title":"Computer Graphics Forum"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.1111\/1467-8659.00278"},{"key":"e_1_2_2_15_1","first-page":"37","volume-title":"Proc. of IMA Conference on Mathematics of Surfaces","author":"Lin M. C.","year":"1998","unstructured":"Lin , M. C. , Gottschalk , S. : Collision detection between geometric models: A survey . Proc. of IMA Conference on Mathematics of Surfaces , pp. 37 -- 56 , 1998 . Lin, M. C., Gottschalk, S.: Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces, pp. 37--56, 1998."},{"key":"e_1_2_2_16_1","first-page":"787","volume-title":"Manocha","author":"Lin M. C.","year":"2004","unstructured":"Lin , M. C. , Manocha , D. : Collision and proximity queries. Handbook of Discrete and Computational Geometry, 2 nd Ed., J. E. Goodman and J. O'Rourke, Eds., Chapman & Hall\/CRC , pp. 787 -- 807 , 2004 . Lin, M. C., Manocha, D.: Collision and proximity queries. Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O'Rourke, Eds., Chapman & Hall\/CRC, pp. 787--807, 2004.","edition":"2"},{"key":"e_1_2_2_17_1","first-page":"145","volume-title":"Proc. ACM Symp. on Solid Modeling and Applications","author":"Redon S.","year":"2004","unstructured":"Redon , S. , Kim , Y. , Lin , M. , Manocha , D. : Fast continuous collision detection for articulated models . Proc. ACM Symp. on Solid Modeling and Applications , pp. 145 -- 156 , 2004 . Redon, S., Kim, Y., Lin, M., Manocha, D.: Fast continuous collision detection for articulated models. Proc. ACM Symp. on Solid Modeling and Applications, pp. 145--156, 2004."},{"key":"e_1_2_2_18_1","volume-title":"Morgan Kaufmann","author":"Samet H.","year":"2006","unstructured":"Samet , H. : Foundations of Multidimensional and Metric Data Structures , Morgan Kaufmann , San Francisco, CA , 2006 . Samet, H.: Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, San Francisco, CA, 2006."},{"doi-asserted-by":"publisher","key":"e_1_2_2_19_1","DOI":"10.1145\/1364901.1364908"},{"doi-asserted-by":"publisher","key":"e_1_2_2_20_1","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"doi-asserted-by":"publisher","key":"e_1_2_2_21_1","DOI":"10.1080\/10867651.1999.10487502"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1111\/j.1467-8659.2006.00970.x"},{"doi-asserted-by":"publisher","key":"e_1_2_2_23_1","DOI":"10.1109\/TVCG.2007.42"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2070781.2024203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2070781.2024203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:03Z","timestamp":1750241163000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2070781.2024203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2070781.2024203"],"URL":"https:\/\/doi.org\/10.1145\/2070781.2024203","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2011-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}