{"id":{"repo_id":"calpoly","oai_identifier":"oai:digitalcommons.calpoly.edu:theses-1891"},"canonical_url":"https://search.ndltd.org/etd/calpoly/oai:digitalcommons.calpoly.edu:theses-1891","repository":{"repo_id":"calpoly","name":"Cal Poly","base_url":"https://digitalcommons.calpoly.edu/do/oai/"},"display":{"title":"Accelerating Ray Casting Using Culling Techniques to Optimize K-D Trees","abstract":"Ray tracing is a graphical technique that provides realistic simulation of light sources and complex lighting effects within three-dimensional scenes, but it is a time-consuming process that requires a tremendous amount of compute power. In order to reduce the number of calculations required to render an image, many different algorithms and techniques have been developed. One such development is the use of tree-like data structures to partition space for quick traversal when finding intersection points between rays and primitives. Even with this technique, ray-primitive intersection for large datasets is still the bottleneck for ray tracing. This thesis proposes the use of a specific spatial data structure, the K-D tree, for faster ray casting of primary rays and enables a ray-triangle culling technique that compliments view frustum and backface culling. The proposed method traverses the entire tree structure to mark nodes to be inactive if it is outside of the view frustum and skipped if the triangle is a backface. In addition, a ray frustum is calculated to test the spatial coherency of the primary ray. The combination of these optimizations reduces the average number of intersection tests per ray from 98% to 99%, depending on the data size.","abstract_html":"Ray tracing is a graphical technique that provides realistic simulation of light sources and complex lighting effects within three-dimensional scenes, but it is a time-consuming process that requires a tremendous amount of compute power. In order to reduce the number of calculations required to render an image, many different algorithms and techniques have been developed. One such development is the use of tree-like data structures to partition space for quick traversal when finding intersection points between rays and primitives. Even with this technique, ray-primitive intersection for large datasets is still the bottleneck for ray tracing. This thesis proposes the use of a specific spatial data structure, the K-D tree, for faster ray casting of primary rays and enables a ray-triangle culling technique that compliments view frustum and backface culling. The proposed method traverses the entire tree structure to mark nodes to be inactive if it is outside of the view frustum and skipped if the triangle is a backface. In addition, a ray frustum is calculated to test the spatial coherency of the primary ray. The combination of these optimizations reduces the average number of intersection tests per ray from 98% to 99%, depending on the data size.","abstract_has_math":false,"creators":["Nguyen, Anh Viet"],"institution":null,"degree_name":"MS in Electrical Engineering","degree_level":null,"degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["John Oliver"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:11:02Z","subjects":["ray tracing","k-d trees","view frustum","backface","ray-triangle","culling","Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["10.15368/theses.2012.163"],"render_values":[{"text":"10.15368/theses.2012.163","href":"https://doi.org/10.15368/theses.2012.163","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.calpoly.edu/theses/847","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.calpoly.edu/theses/847","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.calpoly.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.calpoly.edu%3Atheses-1891","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["John Oliver"]},{"key":"dc:creator","label":"Author","values":["Nguyen, Anh Viet"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2012-08-31T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2012-08-01T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Electrical Engineering"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["ray tracing","k-d trees","view frustum","backface","ray-triangle","culling","Engineering"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.calpoly.edu/theses/847","10.15368/theses.2012.163"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Ray tracing is a graphical technique that provides realistic simulation of light sources and complex lighting effects within three-dimensional scenes, but it is a time-consuming process that requires a tremendous amount of compute power. In order to reduce the number of calculations required to render an image, many different algorithms and techniques have been developed. One such development is the use of tree-like data structures to partition space for quick traversal when finding intersection points between rays and primitives. Even with this technique, ray-primitive intersection for large datasets is still the bottleneck for ray tracing. This thesis proposes the use of a specific spatial data structure, the K-D tree, for faster ray casting of primary rays and enables a ray-triangle culling technique that compliments view frustum and backface culling. The proposed method traverses the entire tree structure to mark nodes to be inactive if it is outside of the view frustum and skipped if the triangle is a backface. In addition, a ray frustum is calculated to test the spatial coherency of the primary ray. The combination of these optimizations reduces the average number of intersection tests per ray from 98% to 99%, depending on the data size."]},{"key":"dc:title","label":"Title","values":["Accelerating Ray Casting Using Culling Techniques to Optimize K-D Trees"]}]}],"canonical_facts":{"dc:contributor":["John Oliver"],"dc:creator":["Nguyen, Anh Viet"],"dc:date.available":["2012-08-31T07:00:00Z"],"dc:date.created":["2012-08-01T07:00:00Z"],"dc:description.abstract":["Ray tracing is a graphical technique that provides realistic simulation of light sources and complex lighting effects within three-dimensional scenes, but it is a time-consuming process that requires a tremendous amount of compute power. In order to reduce the number of calculations required to render an image, many different algorithms and techniques have been developed. One such development is the use of tree-like data structures to partition space for quick traversal when finding intersection points between rays and primitives. Even with this technique, ray-primitive intersection for large datasets is still the bottleneck for ray tracing. This thesis proposes the use of a specific spatial data structure, the K-D tree, for faster ray casting of primary rays and enables a ray-triangle culling technique that compliments view frustum and backface culling. The proposed method traverses the entire tree structure to mark nodes to be inactive if it is outside of the view frustum and skipped if the triangle is a backface. In addition, a ray frustum is calculated to test the spatial coherency of the primary ray. The combination of these optimizations reduces the average number of intersection tests per ray from 98% to 99%, depending on the data size."],"dc:identifier":["https://digitalcommons.calpoly.edu/theses/847","10.15368/theses.2012.163"],"dc:subject":["ray tracing","k-d trees","view frustum","backface","ray-triangle","culling","Engineering"],"dc:title":["Accelerating Ray Casting Using Culling Techniques to Optimize K-D Trees"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_name":["MS in Electrical Engineering"]},"updated_at":"2026-11-19T07:11:02Z"}