{"id":613,"date":"2024-09-14T21:30:18","date_gmt":"2024-09-14T19:30:18","guid":{"rendered":"https:\/\/heikkili.kapsi.fi\/blog\/?p=613"},"modified":"2024-09-14T21:30:18","modified_gmt":"2024-09-14T19:30:18","slug":"cse168-notes-4-acceleration-bvh-bsp-trees","status":"publish","type":"post","link":"http:\/\/heikkili.kapsi.fi\/blog\/?p=613","title":{"rendered":"CSE168 Notes 4, Acceleration, BVH, BSP Trees"},"content":{"rendered":"\n<p><strong>Acceleration Structures and Grids<\/strong><\/p>\n\n\n\n<p>Interested of ways that have fewer number of rays per intersection<\/p>\n\n\n\n<p><strong>Acceleration structures:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>uniform spatial subdivision (grids)<\/li>\n\n\n\n<li>Bounding Volume Hierarchies (BVH)<\/li>\n\n\n\n<li>Binary Space Partitioning (BSP Trees)\n<ul class=\"wp-block-list\">\n<li>Axis-aligned often for ray tracing: kd-trees<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>conceptually simple, implementation bit tricky<\/li>\n<\/ul>\n\n\n\n<p><strong>Acceleration and Regular Grids<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>simplest acceleration for example 5x5x5 grid<\/li>\n\n\n\n<li>for each grid cell, store overlapping triangles<\/li>\n\n\n\n<li>March ray along grid, test each triangle in grid cell<\/li>\n\n\n\n<li>More sophisticated: kd-tree, oct-tree, bsp-tree<\/li>\n\n\n\n<li>Or use (hierarchical) bounding boxes<\/li>\n<\/ul>\n\n\n\n<p><strong>Bounding Volume Hierarchies<\/strong><\/p>\n\n\n\n<p><strong>Bounding Box Test<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>ray-intersection simple coordinate check<\/li>\n\n\n\n<li>hierarchical bounding boxes<\/li>\n<\/ul>\n\n\n\n<p><strong>Hierarchical Bounding Box Test<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>if ray hits root box\n<ul class=\"wp-block-list\">\n<li>intersect left subtree<\/li>\n\n\n\n<li>intersect right subtree<\/li>\n\n\n\n<li>merge intersections (find closest one)<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>standard hierarchical traversal<\/li>\n\n\n\n<li>at leaf nodes, must intersect objects<\/li>\n<\/ul>\n\n\n\n<p><strong>Binary Space Partitioning (BSP) Trees<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>divide space rather than objects<\/li>\n\n\n\n<li>in BVH each object is in one of two sibling nodes<\/li>\n\n\n\n<li>in spatial subdivision, each space point in one node<\/li>\n\n\n\n<li>but object may lie in multiple spatial nodes<\/li>\n<\/ul>\n\n\n\n<p><strong>BSP trees<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>axis aligned splits sometimes called kd-trees<\/li>\n\n\n\n<li>split space (binary space partition) along planes<\/li>\n\n\n\n<li>fast queries and back to front traversal<\/li>\n\n\n\n<li>construction is conceptually simple\n<ul class=\"wp-block-list\">\n<li>select a plane as root of a sub tree<\/li>\n\n\n\n<li>split into two children along this root<\/li>\n\n\n\n<li>random polygon for splitting plane<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>continue splitting until leaf nodes<\/li>\n\n\n\n<li>visibility traversal in order\n<ul class=\"wp-block-list\">\n<li>child one<\/li>\n\n\n\n<li>root<\/li>\n\n\n\n<li>child two<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>child one chose based on viewpoint<\/li>\n\n\n\n<li>BSP tree built once, used for all viewpoints<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Acceleration Structures and Grids Interested of ways that have fewer number of rays per intersection Acceleration structures: Acceleration and Regular Grids Bounding Volume Hierarchies Bounding Box Test Hierarchical Bounding Box Test Binary Space Partitioning (BSP) Trees BSP trees<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[6,43,7],"tags":[10,42,11],"class_list":["post-613","post","type-post","status-publish","format-standard","hentry","category-computer-graphics","category-cse168","category-raytracing","tag-computer-graphics","tag-cse168","tag-ray-tracing"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p7k3DT-9T","_links":{"self":[{"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=\/wp\/v2\/posts\/613"}],"collection":[{"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=613"}],"version-history":[{"count":1,"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=\/wp\/v2\/posts\/613\/revisions"}],"predecessor-version":[{"id":614,"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=\/wp\/v2\/posts\/613\/revisions\/614"}],"wp:attachment":[{"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=613"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/heikkili.kapsi.fi\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}