The traditional method for detecting collisions in a 2D computer game uses a axisaligned bounding box around each sprite, and checks to determine if the bounding boxes overlap periodically. Using this single bounding box method may result in a large amount of pixel intersection tests, since a sprite may be composed of areas where the pixels are empty and the intersecting bounding box test results in false positives.
Our algorithm analysis shows that the optimal two or three bounding boxes is the best partition we can get for a reasonable time complexity. The results further show significantly diminishing returns for calculating four bounding boxes and above, since it takes a comparably large amount of calculation to find the optimal four bounding boxes or more.
We present a multiple bounding boxes algorithm to show that multiple bounding boxes outperforms the traditional single bounding box method. In addition, we implement the simulation test for the 2-bounding-boxes and 3-bounding-boxes both in serial processing and CUDA parallel processing.
Our simulation result shows that out of the 1,000,000 tests we run, both the 2-bounding boxes and 3-bounding-boxes partition resulted in far fewer pixel-checks compared to the one bounding box method. Our experiment in serial processing and CUDA parallel processing also shows that GPU programming can be used to significantly reduce the time in calculation and to speed up the process of collision detection when we have a large enough number of pixels to process.
","abstract_html":"<p>The traditional method for detecting collisions in a 2D computer game uses a axisaligned bounding box around each sprite, and checks to determine if the bounding boxes overlap periodically. Using this single bounding box method may result in a large amount of pixel intersection tests, since a sprite may be composed of areas where the pixels are empty and the intersecting bounding box test results in false positives.</p> <p>Our algorithm analysis shows that the optimal two or three bounding boxes is the best partition we can get for a reasonable time complexity. The results further show significantly diminishing returns for calculating four bounding boxes and above, since it takes a comparably large amount of calculation to find the optimal four bounding boxes or more.</p> <p>We present a multiple bounding boxes algorithm to show that multiple bounding boxes outperforms the traditional single bounding box method. In addition, we implement the simulation test for the 2-bounding-boxes and 3-bounding-boxes both in serial processing and CUDA parallel processing.</p> <p>Our simulation result shows that out of the 1,000,000 tests we run, both the 2-bounding boxes and 3-bounding-boxes partition resulted in far fewer pixel-checks compared to the one bounding box method. Our experiment in serial processing and CUDA parallel processing also shows that GPU programming can be used to significantly reduce the time in calculation and to speed up the process of collision detection when we have a large enough number of pixels to process.</p>","abstract_has_math":false,"creators":["Qi, Min"],"institution":null,"degree_name":"M.S.","degree_level":"Masters Thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Mario Lopez, Ph.D.","Chris Gauthier-Dickey, Ph.D.","Scott Leutenegger","Nathan Sturtevant"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-01-01T08:00:00Z","date_published":"2013-01-01T08:00:00Z","updated_at":"2026-07-24T02:02:11Z","subjects":["Bounding boxes","Collision detection","CUDA","Computer Engineering","Computer Sciences","Databases and Information Systems"],"languages":["en"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/529","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mario Lopez, Ph.D.","Chris Gauthier-Dickey, Ph.D.","Scott Leutenegger","Nathan Sturtevant"]},{"key":"dc:creator","label":"Author","values":["Qi, Min"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2001-01-01T08:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Bounding boxes","Collision detection","CUDA","Computer Engineering","Computer Sciences","Databases and Information Systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/529"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The traditional method for detecting collisions in a 2D computer game uses a axisaligned bounding box around each sprite, and checks to determine if the bounding boxes overlap periodically. Using this single bounding box method may result in a large amount of pixel intersection tests, since a sprite may be composed of areas where the pixels are empty and the intersecting bounding box test results in false positives.
Our algorithm analysis shows that the optimal two or three bounding boxes is the best partition we can get for a reasonable time complexity. The results further show significantly diminishing returns for calculating four bounding boxes and above, since it takes a comparably large amount of calculation to find the optimal four bounding boxes or more.
We present a multiple bounding boxes algorithm to show that multiple bounding boxes outperforms the traditional single bounding box method. In addition, we implement the simulation test for the 2-bounding-boxes and 3-bounding-boxes both in serial processing and CUDA parallel processing.
Our simulation result shows that out of the 1,000,000 tests we run, both the 2-bounding boxes and 3-bounding-boxes partition resulted in far fewer pixel-checks compared to the one bounding box method. Our experiment in serial processing and CUDA parallel processing also shows that GPU programming can be used to significantly reduce the time in calculation and to speed up the process of collision detection when we have a large enough number of pixels to process.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Multiple Bounding Boxes Algorithm in Collision Detection and Its Performances in Sequential VS CUDA Parallel Processing"]}]}],"canonical_facts":{"dc:contributor":["Mario Lopez, Ph.D.","Chris Gauthier-Dickey, Ph.D.","Scott Leutenegger","Nathan Sturtevant"],"dc:creator":["Qi, Min"],"dc:date.available":["2001-01-01T08:00:00Z"],"dc:description.abstract":["The traditional method for detecting collisions in a 2D computer game uses a axisaligned bounding box around each sprite, and checks to determine if the bounding boxes overlap periodically. Using this single bounding box method may result in a large amount of pixel intersection tests, since a sprite may be composed of areas where the pixels are empty and the intersecting bounding box test results in false positives.
Our algorithm analysis shows that the optimal two or three bounding boxes is the best partition we can get for a reasonable time complexity. The results further show significantly diminishing returns for calculating four bounding boxes and above, since it takes a comparably large amount of calculation to find the optimal four bounding boxes or more.
We present a multiple bounding boxes algorithm to show that multiple bounding boxes outperforms the traditional single bounding box method. In addition, we implement the simulation test for the 2-bounding-boxes and 3-bounding-boxes both in serial processing and CUDA parallel processing.
Our simulation result shows that out of the 1,000,000 tests we run, both the 2-bounding boxes and 3-bounding-boxes partition resulted in far fewer pixel-checks compared to the one bounding box method. Our experiment in serial processing and CUDA parallel processing also shows that GPU programming can be used to significantly reduce the time in calculation and to speed up the process of collision detection when we have a large enough number of pixels to process.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/529"],"dc:language":["en"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["Bounding boxes","Collision detection","CUDA","Computer Engineering","Computer Sciences","Databases and Information Systems"],"dc:title":["Multiple Bounding Boxes Algorithm in Collision Detection and Its Performances in Sequential VS CUDA Parallel Processing"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-07-24T02:02:11Z"}