{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T04:34:16Z","timestamp":1772339656117,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T00:00:00Z","timestamp":1291161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003561","name":"Ministry of Culture, Sports and Tourism","doi-asserted-by":"publisher","award":["2008-F-033-02"],"award-info":[{"award-number":["2008-F-033-02"]}],"id":[{"id":"10.13039\/501100003561","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002994","name":"Ministry of Knowledge Economy","doi-asserted-by":"publisher","award":["2008-F-033-02"],"award-info":[{"award-number":["2008-F-033-02"]}],"id":[{"id":"10.13039\/501100002994","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2009-0086684"],"award-info":[{"award-number":["2009-0086684"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>We cull collisions between very large numbers of moving bodies using graphics processing units (GPUs). To perform massively parallel sweep-and-prune (SaP), we mitigate the great density of intervals along the axis of sweep by using principal component analysis to choose the best sweep direction, together with spatial subdivisions to further reduce the number of false positive overlaps. Our algorithm implemented entirely on GPUs using the CUDA framework can handle a million moving objects at interactive rates. As application of our algorithm, we demonstrate the real-time simulation of very large numbers of particles and rigid-body dynamics.<\/jats:p>","DOI":"10.1145\/1882261.1866180","type":"journal-article","created":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T20:18:10Z","timestamp":1291234690000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Real-time collision culling of a million bodies on graphics processing units"],"prefix":"10.1145","volume":"29","author":[{"given":"Fuchang","family":"Liu","sequence":"first","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takahiro","family":"Harada","sequence":"additional","affiliation":[{"name":"Advanced Micro Devices, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youngeun","family":"Lee","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Young J.","family":"Kim","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,12,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2008.0221"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Brown S. 2008. The scalable city project. http:\/\/scalablecity.net.  Brown S. 2008. The scalable city project. http:\/\/scalablecity.net.","DOI":"10.1145\/1280120.1280152"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199437"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.02.014"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70405"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90053-3"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Ericson C. 2005. Real-Time Collision Detection. Morgan Kaufmann.  Ericson C. 2005. Real-Time Collision Detection. Morgan Kaufmann.","DOI":"10.1201\/b14581"},{"key":"e_1_2_2_9_1","unstructured":"Grand S. L. 2008. GPU Gems 3. Addison-Wesley ch. Broad-Phrase Collision Detection with CUDA 697--721.  Grand S. L. 2008. GPU Gems 3. Addison-Wesley ch. Broad-Phrase Collision Detection with CUDA 697--721."},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Harada T. Koshizuka S. and Kawaguchi Y. 2007. Smoothed particle hydrodynamics on GPUs. In Computer Graphics International.  Harada T. Koshizuka S. and Kawaguchi Y. 2007. Smoothed particle hydrodynamics on GPUs. In Computer Graphics International.","DOI":"10.1145\/2614348.2614375"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Harada T. 2007. GPU Gems3. Addison-Wesley Pearson Education ch. Real-time Rigid Body Simulation on GPUs.  Harada T. 2007. GPU Gems3. Addison-Wesley Pearson Education ch. Real-time Rigid Body Simulation on GPUs.","DOI":"10.1145\/1280720.1280778"},{"key":"e_1_2_2_12_1","volume-title":"Principal Component Analysis","author":"Jolliffe I. T.","unstructured":"Jolliffe , I. T. 2002. Principal Component Analysis . Springer . Jolliffe, I. T. 2002. Principal Component Analysis. Springer."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Lauterbach C. Garland M. Sengupta S. Luebke D. and Manocha D. 2009. Fast BVH construction on GPUs. In Eurographics.  Lauterbach C. Garland M. Sengupta S. Luebke D. and Manocha D. 2009. Fast BVH construction on GPUs. In Eurographics.","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Lauterbach C. Mo Q. and Manocha D. 2010. gProximity: Hierarchical GPU-based operations for collision and distance queries. In Eurographics.  Lauterbach C. Mo Q. and Manocha D. 2010. gProximity: Hierarchical GPU-based operations for collision and distance queries. In Eurographics.","DOI":"10.1111\/j.1467-8659.2009.01611.x"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.  Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.","DOI":"10.1201\/9781420035315.ch35"},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Mazhar H. Heyn T. Tasora A. and Negrut D. 2009. Collision detection using spatial subdivision. In Multibody Dynamics.  Mazhar H. Heyn T. Tasora A. and Negrut D. 2009. Collision detection using spatial subdivision. In Multibody Dynamics.","DOI":"10.1115\/DETC2009-86366"},{"key":"e_1_2_2_19_1","unstructured":"NVIDIA. 2010. NVIDIA CUDA Best Practice Guide.  NVIDIA. 2010. NVIDIA CUDA Best Practice Guide."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/218013.218076"},{"key":"e_1_2_2_21_1","unstructured":"Press W. H. Teukolsky S. A. Vetterling W. T. and Flannery B. P. 1992. Numerical Recipes in C. Cambridge University Press.  Press W. H. Teukolsky S. A. Vetterling W. T. and Flannery B. P. 1992. Numerical Recipes in C. Cambridge University Press."},{"key":"e_1_2_2_22_1","unstructured":"Samet H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.   Samet H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360617"},{"key":"e_1_2_2_24_1","unstructured":"Sengupta S. Harris M. Zhang Y. and Owens J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware 97--106.   Sengupta S. Harris M. Zhang Y. and Owens J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware 97--106."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.12"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2010.01.001"},{"key":"e_1_2_2_27_1","unstructured":"Terdiman P. 2007. Sweep-and-prune. http:\/\/www.codercorner.com\/SAP.pdf.  Terdiman P. 2007. Sweep-and-prune. http:\/\/www.codercorner.com\/SAP.pdf."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/VR.2009.4811022"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/RT.2007.4342588"},{"key":"e_1_2_2_30_1","volume-title":"Workshop in Virtual Reality Interactions and Physical Simulation.","author":"Woulfe M.","unstructured":"Woulfe , M. , Dingliana , J. , and Manzke , M . 2007. Hardware accelerated broad phase collision detection for realtime simulations . In Workshop in Virtual Reality Interactions and Physical Simulation. Woulfe, M., Dingliana, J., and Manzke, M. 2007. Hardware accelerated broad phase collision detection for realtime simulations. In Workshop in Virtual Reality Interactions and Physical Simulation."},{"key":"e_1_2_2_31_1","unstructured":"Zerodin 2010. Zerodin games. http:\/\/www.zerodingames.com.  Zerodin 2010. Zerodin games. http:\/\/www.zerodingames.com."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409079"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1882261.1866180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1882261.1866180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:29Z","timestamp":1750244369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1882261.1866180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1145\/1882261.1866180"],"URL":"https:\/\/doi.org\/10.1145\/1882261.1866180","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]},"assertion":[{"value":"2010-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}