<!DOCTYPE html><htmllang="en-US"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=Edge"><title>(Task 3) BVH - </title><linkrel="shortcut icon"href="/favicon.ico"type="image/x-icon"><linkrel="stylesheet"href="/assets/css/just-the-docs-default.css"><script type="text/javascript"src="/assets/js/vendor/lunr.min.js"></script><script type="text/javascript"src="/assets/js/just-the-docs.js"></script><metaname="viewport"content="width=device-width, initial-scale=1"><!-- Begin Jekyll SEO tag v2.7.1 --><title>(Task 3) BVH</title><metaname="generator"content="Jekyll v4.2.0"/><metaproperty="og:title"content="(Task 3) BVH"/><metaproperty="og:locale"content="en_US"/><metaname="twitter:card"content="summary"/><metaproperty="twitter:title"content="(Task 3) BVH"/><script type="application/ld+json">{"headline":"(Task 3) BVH","@type":"WebPage","url":"/pathtracer/bounding_volume_hierarchy","@context":"https://schema.org"}</script><!-- End Jekyll SEO tag --></head><body><svgxmlns="http://www.w3.org/2000/svg"style="display: none;"><symbolid="svg-link"viewBox="0 0 24 24"><title>Link</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-link"><pathd="M10 13a5 5 0 0 0 7.54.54l3-3a5 5 0 0 0-7.07-7.07l-1.72 1.71"></path><pathd="M14 11a5 5 0 0 0-7.54-.54l-3 3a5 5 0 0 0 7.07 7.07l1.71-1.71"></path></svg></symbol><symbolid="svg-search"viewBox="0 0 24 24"><title>Search</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-search"><circlecx="11"cy="11"r="8"></circle><linex1="21"y1="21"x2="16.65"y2="16.65"></line></svg></symbol><symbolid="svg-menu"viewBox="0 0 24 24"><title>Menu</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-menu"><linex1="3"y1="12"x2="21"y2="12"></line><linex1="3"y1="6"x2="21"y2="6"></line><linex1="3"y1="18"x2="21"y2="18"></line></svg></symbol><symbolid="svg-arrow-right"viewBox="0 0 24 24"><title>Expand</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-chevron-right"><polylinepoints="9 18 15 12 9 6"></polyline></svg></symbol><symbolid="svg-doc"viewBox="0 0 24 24"><title>Document</title><svgxmlns="http://www.w3.org/2000/svg"width="24"height="24"viewBox="0 0 24 24"fill="none"stroke="currentColor"stroke-width="2"stroke-linecap="round"stroke-linejoin="round"class="feather feather-file"><pathd="M13 2H6a2 2 0 0 0-2 2v16a2 2 0 0 0 2 2h12a2 2 0 0 0 2-2V9z"></path><polylinepoints="13 2 13 9 20 9"></polyline></svg></symbol></svg><divclass="side-bar"><divclass="site-header"><ahref="/"class="site-title lh-tight"></a><ahref="#"id="menu-button"class="site-button"><svgviewBox="0 0 24 24"class="icon"><usexlink:href="#svg-menu"></use></svg></a></div><navrole="navigation"aria-label="Main"id="site-nav"class="site-nav"><ulclass="nav-list"><liclass="nav-list-item"><ahref="/"class="nav-list-link">Home</a></li><liclass="nav-list-item"><ahref="/git/"class="nav-list-link">GitHub Setup</a></li><liclass="nav-list-item"><ahref="/build/"class="nav-list-link">Building Scotty3D</a></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/guide/"class="nav-list-link">User Guide</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/guide/animate_mode/"class="nav-list-link">Animate</a></li><liclass="nav-list-item "><ahref="/guide/layout_mode/"class="nav-list-link">Layout</a></li><liclass="nav-list-item "><ahref="/guide/model_mode/"class="nav-list-link">Model</a></li><liclass="nav-list-item "><ahref="/guide/render_mode/"class="nav-list-link">Render</a></li><liclass="nav-list-item "><ahref="/guide/rigging_mode/"class="nav-list-link">Rig</a></li><liclass="nav-list-item "><ahref="/guide/simulate_mode/"class="nav-list-link">Simulate</a></li></ul></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/"class="nav-list-link">A2: MeshEdit</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/meshedit/halfedge"class="nav-list-link">Halfedge Mesh</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/local/"class="nav-list-link">Local Operations</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/meshedit/local/edge_flip"class="nav-list-link">Edge Flip Tutorial</a></li><liclass="nav-list-item "><ahref="/meshedit/local/bevel/"class="nav-list-link">Bevelling</a></li></ul></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/meshedit/global/"class="nav-list-link">Global Operations</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/meshedit/global/catmull/"class="nav-list-link">Catmull-Clark Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/remesh/"class="nav-list-link">Isotropic Remeshing</a></li><liclass="nav-list-item "><ahref="/meshedit/global/linear/"class="nav-list-link">Linear Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/loop/"class="nav-list-link">Loop Subdivision</a></li><liclass="nav-list-item "><ahref="/meshedit/global/simplify/"class="nav-list-link">Simplification</a></li><liclass="nav-list-item "><ahref="/meshedit/global/triangulate/"class="nav-list-link">Triangulation</a></li></ul></li></ul></li><liclass="nav-list-item active"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/"class="nav-list-link">A3: Pathtracer</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/pathtracer/camera_rays"class="nav-list-link">(Task 1) Camera Rays</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/intersecting_objects"class="nav-list-link">(Task 2) Intersections</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/ray_triangle_intersection"class="nav-list-link">Ray Triangle Intersection</a></li><liclass="nav-list-item "><ahref="/pathtracer/ray_sphere_intersection"class="nav-list-link">Ray Sphere Intersection</a></li></ul></li><liclass="nav-list-item active"><ahref="/pathtracer/bounding_volume_hierarchy"class="nav-list-link active">(Task 3) BVH</a></li><liclass="nav-list-item "><ahref="/pathtracer/shadow_rays"class="nav-list-link">(Task 4) Shadow Rays</a></li><liclass="nav-list-item "><ahref="/pathtracer/path_tracing"class="nav-list-link">(Task 5) Path Tracing</a></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/materials"class="nav-list-link">(Task 6) Materials</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/dielectrics_and_transmission"class="nav-list-link">Dielectrics and Transmission</a></li></ul></li><liclass="nav-list-item "><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/pathtracer/environment_lighting"class="nav-list-link">(Task 7) Environment Lighting</a><ulclass="nav-list"><liclass="nav-list-item "><ahref="/pathtracer/importance_sampling"class="nav-list-link">Environment Light Importance Sampling</a></li></ul></li><liclass="nav-list-item "><ahref="/pathtracer/visualization_of_normals"class="nav-list-link">Visualization of normals</a></li></ul></li><liclass="nav-list-item"><ahref="#"class="nav-list-expander"><svgviewBox="0 0 24 24"><usexlink:href="#svg-arrow-right"></use></svg></a><ahref="/animation/"class="nav-list-link">A4: Animation</a><ulclass="nav-list "><liclass="nav-list-item "><ahref="/animation/splines"class="nav-list-link">Splines</a></li><liclass="nav-list-item "><ahref="/animation/skeleton_kinematics"class="nav-list-link">Skeleton Kinematics</a></li><liclass="nav-list-item "><ahref="/animation/skinning"class="nav-list-link">Skinning</a></li><liclass="nav-list-item "><ahref="/animation/particles"class="nav-list-link">Particles</a></li></ul></li></ul></nav><footerclass="site-footer"> This site uses <ahref="https://github.com/pmarsceill/just-the-docs">Just the Docs</a>, a documentation theme for Jekyll. </footer></div><divclass="main"id="top"><divid="main-header"class="main-header"><divclass="search"><divclass="search-input-wrap"><inputtype="text"id="search-input"class="search-input"tabindex="0"placeholder="Search "aria-label="Search "autocomplete="off"><labelfor="search-input"class="search-label"><svgviewBox="0 0 24 24"class="search-icon"><usexlink:href="#svg-search"></use></svg></label></div><divid="search-results"class="search-results"></div></div></div><divid="main-content-wrap"class="main-content-wrap"><navaria-label="Breadcrumb"class="breadcrumb-nav"><olclass="breadcrumb-nav-list"><liclass="breadcrumb-nav-list-item"><ahref="/pathtracer/">A3: Pathtracer</a></li><liclass="breadcrumb-nav-list-item"><span>(Task 3) BVH</span></li></ol></nav><divid="main-content"class="main-content"role="main"><h1id="task-3-bounding-volume-hierarchy"><ahref="#task-3-bounding-volume-hierarchy"class="anchor-heading"aria-labelledby="task-3-bounding-volume-hierarchy"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> (Task 3) Bounding Volume Hierarchy </h1><p>In this task you will implement a bounding volume hierarchy that accelerates ray-scene intersection. Most of this work will be in <codeclass="language-plaintext highlighter-rouge">student/bvh.inl</code>. Note that this file has an unusual extension (<codeclass="language-plaintext highlighter-rouge">.inl</code> = inline) because it is an implementation file for a template class. This means <codeclass="language-plaintext highlighter-rouge">bvh.h</code> must <codeclass="language-plaintext highlighter-rouge">#include</code> it, so all code that sees <codeclass="language-plaintext highlighter-rouge">bvh.h</code> will also see <codeclass="language-plaintext highlighter-rouge">bvh.inl</code>.</p><p>First, take a look at the definition for our <codeclass="language-plaintext highlighter-rouge">BVH</code> in <codeclass="language-plaintext highlighter-rouge">rays/bvh.h</code>. We represent our BVH using a vector of <codeclass="language-plaintext highlighter-rouge">Node</code>s, <codeclass="language-plaintext highlighter-rouge">nodes</code>, as an implicit tree data structure in the same fashion as heaps that you probably have seen in some other courses. A <codeclass="language-plaintext highlighter-rouge">Node</code> has the following fields:</p><ul><li><codeclass="language-plaintext highlighter-rouge">BBox bbox</code>: the bounding box of the node (bounds all primitives in the subtree rooted by this node)</li><li><codeclass="language-plaintext highlighter-rouge">size_t start</code>: start index of primitives in the <codeclass="language-plaintext highlighter-rouge">BVH</code>’s primitive array</li><li><codeclass="language-plaintext highlighter-rouge">size_t size</code>: range of index in the primitive list (number of primitives in the subtree rooted by the node)</li><li><codeclass="language-plaintext highlighter-rouge">size_t l</code>: the index of the left child node</li><li><codeclass="language-plaintext highlighter-rouge">size_t r</code>: the index of the right child node</li></ul><p>The BVH class also maintains a vector of all primitives in the BVH. The fields start and size in the BVH <codeclass="language-plaintext highlighter-rouge">Node</code> refer the range of contained primitives in this array. The primitives in this array are not initially in any particular order, and you will need to <em>rearrange the order</em> as you build the BVH so that your BVH can accurately represent the spacial hierarchy.</p><p>The starter code constructs a valid BVH, but it is a trivial BVH with a single node containing all scene primitives. Once you are done with this task, you can check the box for BVH in the left bar under “Visualize” when you start render to visualize your BVH and see each levels.</p><p>Finally, note that the BVH visualizer will start drawing from <codeclass="language-plaintext highlighter-rouge">BVH::root_idx</code>, so be sure to set this to the proper index (probably 0 or <codeclass="language-plaintext highlighter-rouge">nodes.size() - 1</code>, depending on your implementation) when you build the BVH.</p><h2id="step-0-bounding-box-calculation"><ahref="#step-0-bounding-box-calculation"class="anchor-heading"aria-labelledby="step-0-bounding-box-calculation"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Step 0: Bounding Box Calculation </h2><p>Implement <codeclass="language-plaintext highlighter-rouge">BBox::hit</code> in <codeclass="language-plaintext highlighter-rouge">student/bbox.cpp</code>. Also if you haven’t already, implement <codeclass="language-plaintext highlighter-rouge">Triangle::bbox</code> in <codeclass="language-plaintext highlighter-rouge">student/tri_mesh.cpp</code> (<codeclass="language-plaintext highlighter-rouge">Triangle::bbox</code> should be fairly straightforward). We recommend checking out this <ahref="https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection">Scratchapixel article</a>.</p><h2id="step-1-bvh-construction"><ahref="#step-1-bvh-construction"class="anchor-heading"aria-labelledby="step-1-bvh-construction"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Step 1: BVH Construction </h2><p>Your job is to construct a <codeclass="language-plaintext highlighter-rouge">BVH</code> using the <ahref="http://15462.courses.cs.cmu.edu/fall2017/lecture/acceleratingqueries/slide_025">Surface Area Heuristic</a> discussed in class. Tree construction would occur when the BVH object is constructed. Below is the pseudocode by which your BVH construction procedure should generally follow (copied from lecture slides).</p><center><imgsrc="BVH_construction_pseudocode.png"/></center><h2id="step-2-ray-bvh-intersection"><ahref="#step-2-ray-bvh-intersection"class="anchor-heading"aria-labelledby="step-2-ray-bvh-intersection"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Step 2: Ray-BVH Intersection </h2><p>Implement the ray-BVH intersection routine <codeclass="language-plaintext highlighter-rouge">Trace BVH<Primitive>::hit(const Ray& ray)</code>. You may wish to consider the node visit order optimizations we discussed in class. Once complete, your renderer should be able to render all of the test scenes in a reasonable amount of time. <ahref="visualization_of_normals.md">Visualization of normals</a> may help with debugging.</p><center><imgsrc="ray_bvh_pseudocode.png"/></center><h2id="visualization"><ahref="#visualization"class="anchor-heading"aria-labelledby="visualization"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Visualization </h2><p>In Render mode, simply check the box for “BVH”, and you would be able to see the BVH you generated in task 3 when you <strong>start rendering</strong>. You can click on the horizontal bar to see each level of your BVH.</p><center><imgsrc="new_results/bvh_button.png"style="height:120px"/></center><h2id="sample-bvhs"><ahref="#sample-bvhs"class="anchor-heading"aria-labelledby="sample-bvhs"><svgviewBox="0 0 16 16"aria-hidden="true"><usexlink:href="#svg-link"></use></svg></a> Sample BVHs </h2><p>The BVH constructed for Spot the Cow on the 10th level.</p><center><imgsrc="new_results/bvh.png"style="height:320px"/></center><p>The BVH constructed for a scene composed of several cubes and spheres on the 0th and 1st levels.</p><center><imgsrc="new_results/l0.png"style="height:220px"/><imgsrc="new_results/l2.png"style="height:220px"/></center><p>The BVH constructed for the Stanford Bunny on the 10th level.</p><center><imgsrc="new_results/bvh_bunny_10.png"style="height:320px"/></center></div></div><divclass="search-overlay"></div></div></body></html>
