<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Roman Wiche on Medium]]></title>
        <description><![CDATA[Stories by Roman Wiche on Medium]]></description>
        <link>https://medium.com/@bromanz?source=rss-a36dbb4b9c08------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*Io0RNLcBD19A86xoYGYOqQ.jpeg</url>
            <title>Stories by Roman Wiche on Medium</title>
            <link>https://medium.com/@bromanz?source=rss-a36dbb4b9c08------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 14:45:22 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@bromanz/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Axis-Aligned Bounding Tetrahedra and Octahedra for Ray Tracing Bounding Volume Hierarchies]]></title>
            <link>https://medium.com/@bromanz/axis-aligned-bounding-tetrahedra-and-octahedra-for-ray-tracing-bounding-volume-hierarchies-683751d84bca?source=rss-a36dbb4b9c08------2</link>
            <guid isPermaLink="false">https://medium.com/p/683751d84bca</guid>
            <category><![CDATA[axis-aligned]]></category>
            <category><![CDATA[tetrahedron-octahedron]]></category>
            <category><![CDATA[ray-tracing]]></category>
            <category><![CDATA[bounding-volume-hierarchy]]></category>
            <category><![CDATA[bvh]]></category>
            <dc:creator><![CDATA[Roman Wiche]]></dc:creator>
            <pubDate>Sun, 21 Jul 2019 17:41:35 GMT</pubDate>
            <atom:updated>2019-07-21T17:51:40.011Z</atom:updated>
            <content:encoded><![CDATA[<p>Noteworthy Alternatives to Axis-Aligned Bounding Boxes?</p><h3>Motivation</h3><p><a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf">Today, the Bounding Volume Hierarchy (BVH) and it’s variations are the most common acceleration structures for ray tracing</a>. During the last decades, the BVH often proved superior to the likes of uniform grids, kd-trees, BSP-trees, etc. Consequently, it is employed in the world’s most sophisticated ray tracers, like NVIDIA OptiX and Intel Embree.</p><p>In all cases that I’m aware of, the BVH is built upon Axis-Aligned Bounding Boxes (AABBs) as bounding volumes. The reasoning behind this is the simplicity to build the hierarchy, fast intersection testing with rays, and an often sufficiently tight enough bounding volume around objects. Besides AABBs, there are many other bounding volumes, like bounding spheres, Oriented-Bounding-Boxes (OBBs), and more. <a href="http://cis.poly.edu/tr/tr-cis-2001-06.pdf">Usually, these volumes offer a trade-off between tight volumes and fast computation</a>. <a href="https://dl.acm.org/citation.cfm?id=357335">Weghorst et al.</a> define this simple relationship as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/131/1*naR4T5fQoyMBzTdxbJHy3Q.gif" /></figure><p>where <em>T</em> is the total cost, <em>b</em> the number of times that the bounding volume is tested for intersection, <em>B</em> the cost of testing the bounding volume, <em>i</em> the number of times that the enclosed item is tested for intersection, and <em>I</em> the cost of testing the enclosed item for an intersection.</p><p>At the beginning of BVH research for ray tracing, <a href="https://ieeexplore.ieee.org/abstract/document/694275">few works were mentioning BVHs built upon volumes like OBBs</a>. However, today, the AABB is the de-facto standard for BVHs in the context of ray tracing, and I’m not aware of any recent works questioning that. But is it the best fit for BVHs?</p><p>In this article, let us together wonder ‘what-if’ and have a look at two other, possibly competitive, bounding volumes: the Axis-Aligned-Bounding-Tetrahedron (AABT) and Axis-Aligned-Bounding-Octahedron (AABO).</p><h3>AABT and AABO</h3><p>This article is heavily inspired by the work from <a href="https://twitter.com/bmcnett">Bryan McNett</a>. <a href="https://github.com/bryanmcnett/aabo">He wrote an excellent and inspiring article about AABT and AABO recently</a>, presenting their possible use in real-time collision detection systems. So I thought hey, why not try this for ray tracing too? In the following, I’ll give a quick summary of what I think is important for this article, but I highly recommend checking out <a href="https://github.com/bryanmcnett/aabo">the source for it and where these original ideas are coming from</a>.</p><p>Let us illustrate and work through the topics in 2D for better understanding. Later on, we’ll see that it’s trivial to extend this into 3D (I always wanted to say that!)</p><p>When we take a look at an AABB in 2D (an ‘axis-aligned bounding rectangle’), we see that it consists of four planes, axis-aligned to some coordinate system:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f0rM957kwfLepjlBV4N8sg.png" /><figcaption>Utah teapot enclosed by an ‘axis-aligned bounding rectangle’ in 2D which requires four planes</figcaption></figure><p>The question is: Is there any way to enclose our object with less than four planes? If we could, this could mean a saving in space and maybe computation, too. And indeed, we can use three planes as an ‘axis-aligned bounding triangle’ to enclose our object:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*a3636FJriTIgHUL1r29RJw.png" /><figcaption>Utah teapot enclosed by an ‘axis-aligned bounding triangle’ in 2D which requires only three planes. Note the additional definition of the -(x+y) axis.</figcaption></figure><p>We could use arbitrary oriented axes, but using the coordinate systems main axes <em>x</em>, <em>y</em>, and a simple combination of <em>-(x+y)</em> allows for easy conversion between coordinate systems.</p><p>So it’s great we saved in 25% of space, however, at the same time, we most likely ended up with a more loose bounding volume (except for maybe an axis-aligned triangle object). To achieve a tighter bounding volume, we can extend the bounding volume with another triangle oriented in the opposite direction, essentially ending up with an ‘axis-aligned bounding hexagon’:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*udh6oq_3Vr__16O0dILz9w.png" /><figcaption>Utah teapot enclosed by an ‘axis-aligned bounding hexagon’, two overlapping axis-aligned bounding triangles, in 2D. The violet area visualizes the hexagon’s intersection area between both triangles. Note how the -min(x+y) and -max(x+y) allow decreasing the area of an ‘axis-aligned bounding rectangle’.</figcaption></figure><p>With this bounding volume, we can see that we’ll always be as tight as with an axis-aligned bounding rectangle in the worst-case, but may additionally have the chance to shrink the bounding volume further down with the two triangle hypotenuses.</p><p>But what was the point of decreasing the number of enclosing planes, just to increase them again, and ending up with six planes instead of rectangle’s four? Here is the deal: Assume we assemble the hexagon test from the two triangle tests. Then, if the ray does <strong><em>not </em></strong>intersect the first triangle, we can ignore the second triangle alltogether, and don’t even need to load it from memory. Just if the ray hits the first triangle, we need to test the second one, and even though this is arguably more expensive overall, we have a (most likely) tighter bounding volume. Wow.</p><p>Let us end this section by recognizing that the previous remarks extend into all higher dimensions. This means we need at least <em>n+1</em> hyperplanes in the <em>nth</em> dimension (in 2D three hyperplanes, in 3D four hyperplanes) to enclose objects. Thus, our ‘axis-aligned bounding triangle’ and ‘axis-aligned bounding hexagon’ transform into a tetrahedron/AABT and octahedron/AABO in 3D, respectively.</p><h3>New Ray-AABT Intersection Algorithm</h3><p>We saw that we can save some space with AABT in contrast to AABB. Our hope now is to find a sufficiently fast Ray-AABT intersection algorithm to make up for the more loose bounding volume. This way, we might end up with a faster overall hierarchy.</p><p>Unfortunately for us, a quick google search shows us that there is not much on the table here. The best general ray-tetrahedra test I could find is the one from <a href="http://realtimecollisiondetection.net/blog/?p=13">Christer Ericson</a>. However, since the axis-aligned restriction may give us new possibilities, let’s see if we can come up with something ourselves.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*eDQrtTxzvijjpw7QZu9uUQ.jpeg" /><figcaption>ALL RIGHT, BRAIN. IT’S ALL UP TO YOU. YOU HAVE TO COME UP WITH AN ALGORITHM. #THINKING RAPIDLY# EAT THE PUDDING, EAT THE PUDDING, EAT THE PUDDING. [<a href="https://frinkiac.com/img/S05E22/1096795.jpg">https://frinkiac.com/img/S05E22/1096795.jpg]</a></figcaption></figure><p>Since we’re dealing with a BVH traversal, we’re not only interested in a boolean hit result. Instead, we’d like to receive a hit range of our ray where the ray is intersecting an AABT (that is, the parametric distance <em>tmin</em> and <em>tmax</em>). This gives us more flexibility during the traversal (e.g., for culling nodes).</p><p>We already know how to compute the parametric distance of a ray to an axis-aligned plane. This is exactly what we do during a Ray-AABB intersection. Therefore, let’s start the algorithm off by computing the parametric distance of the ray to the four axis-aligned planes of the tetrahedron. This is very convenient because it fits in one <em>float4</em> vector and we can compute it with just one vectorized subtraction and multiplication. The prerequisite here is that we have prepared a <em>float4</em> ray origin and direction so that the <em>w</em>-component represents the <em>-(x+y+z)</em> axis. We can easily compute this sum of vector components by taking the dot product with a one-vector. So far, we got:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/40fc6a1d33582291016b78368152c350/href">https://medium.com/media/40fc6a1d33582291016b78368152c350/href</a></iframe><p>Now we already know that we have to extract <em>tmin</em> and <em>tmax</em> from two components in the vector <em>t4</em>, but we don’t know which ones yet. From what I got so far when drawing different cases of rays intersecting tetrahedra, it appears to me that it’s not as easy to select them as within the AABB test. Whereas in the AABB test you can choose between the min and max of one axis (where you can be certain that one is certainly the min and one is certainly the max), we can’t easily tell this for the tetrahedron from what I can see.</p><p>To get a better grasp which parametric distance might be a <em>tmin</em> and a <em>tmax </em>candidate, let’s take the location of the ray origin into consideration. One interesting thing to note is that with the AABT, all plane normals either point inside or outside of the tetrahedron. Say we have a tetrahedron where each axis-aligned plane normal points towards the inside. Then, if our ray is originating on the side of a plane normal, this plane is a <em>tmax</em> candidate. Otherwise, it is a<em> tmin</em> candidate, because the ray has to intersect the backside of the plane at some point if it is to enter the tetrahedron. If all plane normals point outside of the tetrahedron, the opposite holds:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ibXCsvuRrGr4bjKit-zyVw.png" /><figcaption>Various cases of rays intersecting AABTs. Violet circles indicate parametric distance to the planes. Top-left: Rays originating outside of the AABT. Plane normals pointing toward the origin are max-candidates / pointing away from the origin are min-candidates. Top-right: Ray is originating inside the AABT. All planes are possible max-candidates, but we ignore negative values, and intersections in the origin (if a ray lies exactly on a plane) if the ray points into the tetrahedron. Note that tmin is 0. Bottom-left: AABT planes all point outside instead of inside. Our previous rules for min/max-candidates are inverted. Bottom-right: If any tmin candidate is negative, there is no way the ray can intersect the AABT.</figcaption></figure><p>The only exception which needs more special handling is a ray originating exactly on a plane, which also requires to check the direction.</p><p>We use this knowledge to create an <em>int4</em> mask which will store if the corresponding vector component is a <em>tmin/tmax</em> candidate. By multiplying this mask with all our candidates, we receive one vector containing the candidates for <em>tmin/tmax</em>. Finally, just like in the AABB test, we must select the min/max components of the vectors.</p><p>The only thing left to check is if any of the <em>tmin </em>candidates are negative. Then, we don’t hit the tetrahedron. Translating all these things into code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6f4ee0006f3c43fa38d7e52cc815b036/href">https://medium.com/media/6f4ee0006f3c43fa38d7e52cc815b036/href</a></iframe><p>The selection of <em>tmin</em> and <em>tmax</em> plus the mask handling is more involved than I’d like, but hey, this is the best I can come up with right now. Certainly, there is something better out there. Although the whole algorithm looks more tangled than the AABB test due to all the conditional moves, we shouldn’t forget that it has the advantage of just using one vector register input representing the tetrahedron’s planes compared to AABB’s two.</p><h3>New Ray-AABO Intersection Algorithm</h3><p>Regarding the Ray-AABO test, I generally see two ways going forward:</p><ol><li>Assemble the Ray-AABO test from two Ray-AABT tests as explained in the previous sections. Since we already have a working Ray-AABT test, this is straight-forward, and I won’t describe this path any further (just mind the correct update of <em>tmin</em> and <em>tmax </em>and cull if required).</li><li>Come up with a new ‘atomic’ Ray-AABO test which tests the AABO ‘at-once’. Let’s see how we could do that.</li></ol><p>The state-of-the-art Ray-AABB algorithm which is also used by NVIDIA OptiX and Intel Embree is described by <a href="http://jcgt.org/published/0007/03/04/">Majercik et al</a>. I’ve also written <a href="https://medium.com/@bromanz/another-view-on-the-classic-ray-aabb-intersection-algorithm-for-bvh-traversal-41125138b525">a blog post about it</a>. For convenience, here is the listing again:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c0f1ff016a31521cfd45ebea79c135c5/href">https://medium.com/media/c0f1ff016a31521cfd45ebea79c135c5/href</a></iframe><p>If we take a closer look at it, we can see pretty quickly that it is very easy to extend this to a Ray-AABO test. Like in the Ray-AABT test, we achieve this by using the fourth <em>w</em>-component of the ray and plane vectors to compute the parametric distance for the two additional planes on the <em>-(x+y+z)</em> axis. Then, we end up with:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/28ac9b2b67478a454111a4dea359761d/href">https://medium.com/media/28ac9b2b67478a454111a4dea359761d/href</a></iframe><p>Besides one additional <em>min/max </em>operation in selecting the min/max component of <em>tmin/tmax</em> in line 7, it is pretty much the same algorithm just using <em>vec4</em> instead of <em>vec3</em>. So we got two additional restricting planes, without any substantial cost. The prerequisite here is that we transformed the ray origin’s and direction’s <em>w</em>-component correctly once before, like in the Ray-AABT test.</p><h3>Preliminary Results</h3><p>Let’s find out how all these things we’ve been going through translate into a ray tracing system.</p><p>First, we have to update our way of building the BVH, and for the beginning, we will do this very naively. When building the bounding volumes, we not only have to compute the min and max but also <em>-min(x+y+z)</em> and <em>-max(x+y+z)</em> for our additional axis, so that we can use it in our node planes later on. This will take a bit of extra time when building the hierarchy, but if we’re dealing with static BVHs it shouldn’t bother us too much. There are a lot more possibilities for improvement (more on this at the end), but for now, let’s leave it like that to not overcomplicate things.</p><p>Second, it is important that we save a <em>float4</em> origin and direction within a ray instead of <em>float3</em> (if that is not already the case). Then, after the last transform operation on the ray (e.g., after it’s transformed into local space of an object), we have to compute the <em>w</em>-component of the origin and direction one time as two dot products, that is -dot(orig, 1) and -dot(dir, 1), respectively.</p><p>Now that we’re done with this arrangement, we can trace our rays through BVHs built from AABBs, AABTs, and AABOs. We will create some renderings with each BVH variant and profile them against various test meshes from <a href="http://casual-effects.com/data/?source=post_page---------------------------">Morgan McGuire’s Computer Graphics Archive</a>. Here are the numbers and some heatmap rendering eye-candy:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xsEhy-Fy37pZrb3H-XIgtg.png" /><figcaption>Performance numbers of the previously discussed four BVH variants. For these measurements, three viewpoints were averaged for each mesh. I used Full-HD resolution and shot only primary rays with 16 samples per pixel for Teapot and Bunny, and four samples per pixel for Bedroom and Sibenik (my GPU couldn’t take so much more). Tests were conducted on NVIDIA GeForce GTX 970M with one thread per ray and thread group size 16x8x1.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BrdEcasDZaiLJHh4hZBy6A.png" /><figcaption>Heatmap images rendered for the three bounding volume types. Top-Left: AABB. Top-Right: AABT. Bottom: AABO. Note how the AABO uses its diagonals to shrink the intersection area compared to AABB. Also, this shows perfectly that building AABTs naively into the previous AABB scheme definitely needs more refinement.</figcaption></figure><h4>What to make out of all this?</h4><p>Good question. What I can say is this:</p><ol><li>Yes, in my specific ray tracing system and setup, AABOs and AABBs match pretty much. Which one wins in which situation seems to depend on the scene and viewpoint. AABOs can shrink the volume further down, but I didn’t manage to pack pointers to next nodes / leaf node information into AABO nodes compared to AABBs, so there was some additional reading cost.</li><li>The ‘atomic’ AABO test is to prefer against the assembled version from two AABT tests (though this might change with a better AABT intersection).</li><li>When using a naive approach to replace AABBs with AABTs, they definitely perform worse (which is not specifically surprising, but still worth mentioning).</li><li>How these results translate into different layouts of BVHs, variations, hardware, and other systems, I don’t have a clue to be honest. After all, I called this section preliminary results for a reason, and this is not an all encompassing scientific paper, but a blog post. Still, I think it is fair to say that AABOs are definitely noteworthy alternatives to AABBs.</li></ol><p>To get a better grasp of what AABTs might be capable of when using a more intelligent BVH construction, there should be a focus on:</p><ul><li>Taking the fourth axis into cutting consideration</li><li>Being able to switch between (possibly) four diagonal axes to get differently oriented tetrahedrons on each hierarchy level</li><li>An alternative or extension to the Surface Area Heuristic, since we will deal with bounding volumes which do not enclose each other completely anymore, but rather child volumes which ‘carve’ volumes out of the parent volume. My dear colleague <a href="https://twitter.com/daerst?lang=de">David Kuri</a> and I already talked about this general idea some time ago and called it the ‘Bounding Volume Carving Hierarchy’. The following illustrations show the potential behind this concept:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*z_sDGswibb17LasosawMuA.png" /><figcaption>Using a more versatile and intelligent BVH construction for AABT. Note the additional (-x+y) axis to allow for another diagonal split. While the root node bounding volume is most likely more loose than an AABB, we see tighter child volumes compared to AABB on the first level already. Also, note how the child volumes are not completely enclosed by the parent, but just ‘carve’ a volume out of the parent.</figcaption></figure><p>Now call me crazy (rightfully so), but I think that with these additions, the AABT is the most interesting route to investigate further. This will be super exciting and may very well be a part 2 article.</p><p>Besides a second part, there is also a lot to look forward to from Bryan McNett. In addition to his work on AABT and AABO, he wrote another interesting article on <a href="https://github.com/bryanmcnett/hexprism">HexPrism</a>.</p><p>We’re living in exciting times.</p><p>Cheers, Broman</p><h3>References</h3><p><em>(in order of appearance)</em></p><ul><li><a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf?source=post_page---------------------------">Tomas Akenine-Möller, Eric Haines, Naty Hoffman, Angelo Pesce, Michal Iwanicki, Sébastien Hillaire: Real-Time Rendering 4th Edition, 2018, Real-Time Ray Tracing Chapter</a></li><li><a href="http://cis.poly.edu/tr/tr-cis-2001-06.pdf">Allen Y. Chang: A Survey of Geometric Data Structures for Ray Tracing, Technical Report, 2001</a></li><li><a href="https://dl.acm.org/citation.cfm?id=357335">Hank Weghorst, Gary Hooper, Donald P. Greenberg: Improved Computational Methods for Ray Tracing, ACM Transcations on Graphics, 1984</a></li><li><a href="https://ieeexplore.ieee.org/abstract/document/694275">A. Iones, S. Zhukov, A. Krupkin: On optimality of OBBs for visibility tests for frustum culling, ray shooting and collision detection, Proceedings Computer Graphics International, 1998</a></li><li><a href="https://github.com/bryanmcnett/aabo">Bryan McNett: Axis-Aligned Bounding Octahedra and The 7-Sided AABB, 2019</a></li><li><a href="http://realtimecollisiondetection.net/blog/?p=13">Christer Ericson: Plücker coordinates considered harmful!, Real-Time Collision Detection Blog, 2007</a></li><li><a href="http://jcgt.org/published/0007/03/04/?source=post_page---------------------------">Alexander Majercik, Cyril Crassin, Peter Shirley, and Morgan McGuire: A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering, <em>Journal of Computer Graphics Techniques (JCGT)</em>, 2018</a></li><li><a href="https://medium.com/@bromanz/another-view-on-the-classic-ray-aabb-intersection-algorithm-for-bvh-traversal-41125138b525">Broman: Another View on the Classic Ray-AABB Intersection Algorithm for BVH Traversal, 2018</a></li><li><a href="http://casual-effects.com/data/?source=post_page---------------------------">Morgan McGuire: Computer Graphics Archive, 2017</a></li><li><a href="https://github.com/bryanmcnett/hexprism">Bryan McNett: Hexagonal Prism Bounding Volume, 2019</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=683751d84bca" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Another View on the Classic Ray-AABB Intersection Algorithm for BVH traversal]]></title>
            <link>https://medium.com/@bromanz/another-view-on-the-classic-ray-aabb-intersection-algorithm-for-bvh-traversal-41125138b525?source=rss-a36dbb4b9c08------2</link>
            <guid isPermaLink="false">https://medium.com/p/41125138b525</guid>
            <category><![CDATA[box]]></category>
            <category><![CDATA[aabb]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[intersections]]></category>
            <category><![CDATA[ray-tracing]]></category>
            <dc:creator><![CDATA[Roman Wiche]]></dc:creator>
            <pubDate>Fri, 28 Sep 2018 23:13:38 GMT</pubDate>
            <atom:updated>2018-09-29T08:15:51.580Z</atom:updated>
            <content:encoded><![CDATA[<h3>Another View on the Classic Ray-AABB Intersection Algorithm for BVH Traversal</h3><p>…</p><h4>Motivation</h4><p><a href="http://jcgt.org/published/0007/03/04/">Rendering, physics, and AI applications benefit from fast ray-box intersection tests</a>. For me, ray-axis-aligned-bounding-box (AABB) intersection tests are of particular interest, because Bounding Volume Hierarchies (BVHs) are commonly built with AABBs. <a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf">BVHs, in turn, are the most common acceleration structures for ray tracing</a>. To traverse BVHs efficiently, a fast algorithm to judge whether a ray is piercing an AABB is essential. This way, the algorithm determines whether primitives or child nodes need to be tested or discarded because the ray does or does not hit the parent AABB.</p><h4>Most common algorithm</h4><p>There are a few algorithms which solve the ray-AABB intersection problem. <a href="http://jcgt.org/published/0007/03/04/">Majercik et al.</a> give an excellent overview of existing ray-box tests. Which algorithm to choose amongst these, is usually dependent on a few factors:</p><ul><li>Hardware (CPU/GPU, Which architecture?)</li><li>Context (Where is this algorithm called? How many times? What outcoming values do we expect? (e.g. a boolean, parametric min and max values, hit normal?)</li><li>Performance, Precomputation</li><li>Ease of understanding and implementation</li></ul><p>To my knowledge, the simplest but also most competitive ones are variants of slabs tests originating from <a href="http://papers.cumincad.org/data/works/att/67d2.content.pdf">Kay and Kajiya</a>. <a href="http://psgraphics.blogspot.com/2016/02/new-simple-ray-box-test-from-andrew.html">Andrew Kensler proposed a simple and fast variant featured on Peter Shirley’s Blog</a>, which is also referenced as one of the most novel ones in the <a href="http://www.realtimerendering.com/intersections.html">real-time rendering intersection table</a>. A very similar variant is also given by <a href="https://www.pbrt.org/">Pharr et al.</a></p><p>There are many sources explaining the concept behind the slabs algorithm [<a href="http://papers.cumincad.org/data/works/att/67d2.content.pdf">Kay and Kajiya</a>| <a href="https://www.pbrt.org/">Pharr et al.</a> | <a href="https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection">Scratchapixel</a> | <a href="http://roman-wiche.com/misc/wiche-accel-cone-tracing-thesis-2017.pdf">Broman</a>]. So I’ll skip the explanation at this point.</p><h4>My story — and an idea</h4><p><a href="https://github.com/bromanz/Portfolio/blob/master/AccelConeTracing/AccelConeTracing.md">A s part of my master thesis in fall 2016, I worked on a ray- and cone tracing framework in Unity3D</a>. I implemented the creation of offline acceleration structures on the CPU and traversal on the GPU. Our goal was a modular framework to enable the exchange of different modules in the ray/cone tracing pipeline (e.g. variants of triangle intersectors or acceleration structures).</p><p>In this context, I also integrated Andrew Kensler’s ray-AABB intersection algorithm variant from the previous section. But, when I learned about SIMD/SSE and related concepts, I was always wondering if this algorithm could be further optimized. At the same time, I also had not heard from anyone doing this yet, while I was certain it would be possible — somehow.</p><p>I was eager to take a closer look at this but, unfortunately, this was not the goal of my thesis. So at that time, the idea dropped from the table and just wandered in the back of my unconscious mind.</p><p>Fast forward to fall 2018. With the recent emerges in RTX and DirectX Ray tracing, I am very happy that the “holy grail” of computer graphics will finally come to consumers. It is very impressive what NVIDIA pulled off here. Also, adding legends in the field like Ingo Wald and Matt Pharr to their existing team of world-class experts, I am sure much more exciting news will come from them in the near future.</p><p>With all these ray tracing developments coming at me, I also looked back on my time researching in this area. And then, I remembered this idea of improving Kensler’s variant of the slabs algorithm. So I just had to sit down and get closure on this topic: Is it possible to extend it with vector intrinsics, and if so, why hadn’t I’ve heard from anyone about this possibility yet?</p><h4>Applying my ideas to the classic Ray-AABB algorithm</h4><p>I will try to frame my approach following these guidelines:</p><ol><li>Use intrinsic GPU functions where possible: They are likely to be optimized and provide a faster solution than a manual implementation (I hope!).</li><li>Prepare for the worst-case: Assume that our algorithm does not get an early out.</li><li>Take advantage of vectorization where possible.</li></ol><p>We’ll implement the algorithm on the GPU in HLSL. This way, we can utilize it in Compute Shaders and Unity3D.</p><p>Let’s start.</p><p>We begin with <a href="http://psgraphics.blogspot.com/2016/02/new-simple-ray-box-test-from-andrew.html">Andrew Kensler’s variant</a>, just converted into HLSL:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e25229265fcd921cf0ae1b56327678e4/href">https://medium.com/media/e25229265fcd921cf0ae1b56327678e4/href</a></iframe><p>Let’s grab the low-hanging fruits first.</p><p>In line 3, the reciprocal of the ray direction is computed. In HLSL, we can replace the manual computation with the intrinsic function call rcp(<a href="https://docs.microsoft.com/en-us/windows/desktop/direct3dhlsl/dx-graphics-hlsl-intrinsic-functions">please see here for a full list of intrinsic functions in HLSL</a>). Also, in line 12–13 we use ternary operators to assign tmin the max value of (t0, tmin) and tmax with the min value of (t1, tmax). Consequently, we can replace them with min/max function calls.</p><p>Cool.</p><p>Now what was always bothering me is the for-loop in this algorithm. In the worst-case, meaning that a ray really intersects with an AABB, the algorithm needs to go through the loop three times (one time for each axis) and does not get any early out. Consequently, all branch operations and computations are executed three times. This may not sound like too much, but when considering that this is computed for multiple AABBs on multiple levels on multiple BVHs for millions of rays per frame: phew.</p><p>When examining the algorithm closely, we see that even in the best-case, the loop is executed one time. The question arises: if we compute the reciprocal for the ray direction on one axis anyway in the best-case, why don’t we just compute all three axes at once through vectorization so that we’re also well-prepared for the worst-case? The same applies for the next two lines of code, in which we can compute the parametric distances t0 and t1 to aabb.min and aabb.max for all three axes at once because there is no sequential computational dependency between these values. In addition, we can also do the invD &lt; 0.0f check in line 6 in a vectorized format.</p><p>Let’s see where we’re getting with this:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/81002accd5a4d903abcd86003fb6ef32/href">https://medium.com/media/81002accd5a4d903abcd86003fb6ef32/href</a></iframe><p>I love that we’re moving things out of the loop here. But there is still too much left we also need to get rid of.</p><p>It’s good already that we just check for a boolean value in the if-clause instead of checking the invD condition three times. But we can go further. We test the sign of the direction (or inverse direction — makes no difference here) in line 9 because we’re interested if t0 or t1 is bigger and then swap these values accordingly (so that t1 &gt; t0). Well: We could also use the min/max functions again to ensure this! And when applying them to our float3 vectors, we avoid branching and compute the min/max for all axes in one line of code, respectively. We can then also delete the invD check completely.</p><p>After that, the for loop only consists of the selection of the min/max component of two vectors and tmin / tmax — and a possible early out. Since we want to optimize for the worst-case, we assume that the early out in line 19 does actually more harm than actually helping us. Remember: in the worst-case, we pay three times for it!</p><p>So we’re just left with the min/max component selection, which we can easily unroll and — boom: the complete loop is gone. Let’s hope it was worth the effort.</p><p>Finally, we return the value of tmin &lt; tmax.</p><p>Then, the algorithm transforms into:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/23ca9993cb2cb72cc63bce55dde1d6e8/href">https://medium.com/media/23ca9993cb2cb72cc63bce55dde1d6e8/href</a></iframe><h4>Results</h4><p>Let’s find out if all the changes were worth going through. In the following, I’ll compare the performance of Andrew Kensler’s variant with the final transformation of the previous section. For this purpose, I employed both in a Unity3D ray tracing framework with BVH traversal. In this test, we’ll just focus on the traversal. So we’ll only shoot primary rays from the camera, traverse them through the BVH, and sum the number of traversal steps / number of intersections with triangles (without computing them). This will provide us with a nice heatmap visualization and we can profile rendering times for one frame. We will conduct these tests with some traditional test meshes from <a href="http://casual-effects.com/data/">Morgan McGuires Computer Graphics Archive</a> (Thanks for providing them!)</p><p>Let’s have a look at the resulting data:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/876/1*3pDI5-Ssq2TvPBFi0U40GQ.png" /><figcaption>Performance comparison: The Kensler algorithm from which we started vs. the final transformed algorithm</figcaption></figure><p>In these tests, the new variant provides a speedup of ~1.33 on average. Awesome! For example, this is the difference between 30 fps to 40 fps, or 50 fps to 66 fps.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FG2eXFKaFagJIdTplFOaRA.jpeg" /><figcaption>Heatmap example renderings of four scenes</figcaption></figure><h4>What now?</h4><p>After seeing the results, I was thrilled to share these with other people to discuss them. But before sending them out, I wanted to be sure one more time that I did not miss anything. Especially because I was not actively doing research since my thesis.</p><p>So I checked again, and to my surprise, found a freshly published JCGT paper from just two days ago: <a href="http://jcgt.org/published/0007/03/04/">A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering by<strong> </strong>Majercik, Crassin, Shirley, and McGuire (NVIDIA)</a>. They present a novel intersection algorithm for arbitrarily oriented boxes and showcase it by rendering a huge amount of dynamic voxels via voxel ray tracing.</p><p>But more interestingly for me, they also wrote about an “efficient slab test”, which is apparently used in implementations of NVIDIA OptiX and Intel Embree.</p><p>In their listing, they put it as:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c0f1ff016a31521cfd45ebea79c135c5/href">https://medium.com/media/c0f1ff016a31521cfd45ebea79c135c5/href</a></iframe><p>I was stunned that this was basically the same as the result of the process I was just going through. In their findings, they show that this is the currently most efficient algorithm known for a simple ray-AABB intersection test. They add that “to their knowledge, this important efficient slabs method used by industry ray tracers is not widely known.”</p><p>I have to say: I am very happy that I come to the same conclusion as the authors, and my journey without this knowledge was very exciting. In my tests, the efficient slabs test outperformed as well. Also, I agree that this variant is currently not very well known.</p><p>So I guess my goal is now to make this form of implementation more well-known across developers. I hope this article helps in doing so!</p><p>Cheers<br>Broman</p><h4>References (in order of appearance)</h4><ul><li><a href="http://jcgt.org/published/0007/03/04/">Alexander Majercik, Cyril Crassin, Peter Shirley, and Morgan McGuire: A Ray-Box Intersection Algorithm and Efficient Dynamic Voxel Rendering, <em>Journal of Computer Graphics Techniques (JCGT)</em>, vol. 7, no. 3, 66–81, 2018</a></li><li><a href="http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf">Tomas Akenine-Möller, Eric Haines, Naty Hoffman, Angelo Pesce, Michal Iwanicki, Sébastien Hillaire: Real-Time Rendering 4th Edition, 2018, Real-Time Ray Tracing Chapter</a></li><li>Kay, T. L., Kajiya, J. T. Ray tracing complex scenes. In Proceedings of the<br>13th Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, SIGGRAPH ’86, 269–278. 69, 75, 76</li><li><a href="http://psgraphics.blogspot.com/2016/02/new-simple-ray-box-test-from-andrew.html">Peter Shirley: New simple ray-box test from Andrew Kensler, 2016</a></li><li><a href="http://www.realtimerendering.com/intersections.html">Real-Time Rendering Intersection Table</a></li><li><a href="http://www.pbrt.org/">M. Pharr, J. Wenzel, and G. Humphreys. Physically Based Rendering, Third Edition: From Theory To Implementation. Morgan Kaufmann Publishers Inc., 3rd edition, 2016</a></li><li><a href="https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection">Scratchapixel: Ray — Box Intersection</a></li><li><a href="http://roman-wiche.com/misc/wiche-accel-cone-tracing-thesis-2017.pdf">Broman: Acceleration Structures for Cone Tracing, 2017</a></li><li><a href="https://docs.microsoft.com/en-us/windows/desktop/direct3dhlsl/dx-graphics-hlsl-intrinsic-functions">Full list of intrinsic functions in HLSL</a></li><li><a href="http://casual-effects.com/data/">Morgan McGuires Computer Graphics Archive</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=41125138b525" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How to create awesome accelerators: The Surface Area Heuristic]]></title>
            <link>https://medium.com/@bromanz/how-to-create-awesome-accelerators-the-surface-area-heuristic-e14b5dec6160?source=rss-a36dbb4b9c08------2</link>
            <guid isPermaLink="false">https://medium.com/p/e14b5dec6160</guid>
            <category><![CDATA[ray-tracing]]></category>
            <category><![CDATA[sah]]></category>
            <category><![CDATA[acceleration-structures]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[surface-area-heuristic]]></category>
            <dc:creator><![CDATA[Roman Wiche]]></dc:creator>
            <pubDate>Tue, 10 Apr 2018 21:51:43 GMT</pubDate>
            <atom:updated>2020-10-01T18:44:29.936Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*c8qmUYHMd6h4KaCiQx-SnA.jpeg" /><figcaption>Acceleration structure heat map visualization of the <a href="https://casual-effects.com/data">Stanford Dragon</a></figcaption></figure><h4>Motivation</h4><p>We use acceleration data structures for various computer science topics. For example, we use a <a href="https://en.wikipedia.org/wiki/K-d_tree">kd-tree</a> to perform nearest neighbor searches or multidimensional key queries. Accelerators for <a href="https://en.wikipedia.org/wiki/Ray_tracing_(graphics)">ray tracing</a> applications enable the fast selection of potential ray-triangle intersections. But why is this necessary? What about a brute-force solution?</p><p>Let’s consider the following example: We’d like to render a high polygon mesh with one million triangles. Plus, we’d like to render it in Full-HD (1920x1080 pixels). Without accelerators, we’d have to compute one million intersections for each ray. So if we’d shoot only one ray per pixel, we’d end up with <strong>two trillion</strong> intersection tests. And this doesn’t even include rays for reflections.</p><p>Phew. Let’s just say, it’s a lot of computation!</p><p>By introducing acceleration structures, we cut the search space into smaller parts. This is like a search in a <a href="https://en.wikipedia.org/wiki/Binary_search_tree">binary search tree</a>.</p><p>Describing it in a more formal way: Let <em>n</em> be the number of possible intersections. <em>n</em> reaches trillions when considering complex scenes, meshes, and high quality settings. Well built <a href="http://ieeexplore.ieee.org/document/4057175/">accelerators can then improve the performance of a naive <em>O(n)</em> ray tracing algorithm to<em> O(log n)</em></a>. This can enable interactive ray tracing. Why? Because <a href="https://dl.acm.org/citation.cfm?id=358882">intersection tests account for around 95% of the performance burdens in complex scenes</a>.</p><p>We can conclude: Creating intelligent data structures will skyrocket our algorithm performance.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lrZgHEyH02GVyh36dDSKHQ.jpeg" /><figcaption><a href="http://l2program.co.uk/931/geometric-instancing">Image rendered with Path Tracing by Joss Whittle</a>. Wouldn’t it be amazing rendering this imagery in real-time? Accelerators support us accomplishing this ambitious vision.</figcaption></figure><h4>A Bit of History</h4><p>There are two common ways to approach accelerator creation. We call the first way object subdivision. It works by grouping objects together like it is performed by a <a href="https://en.wikipedia.org/wiki/Bounding_volume_hierarchy">Bounding Volume Hierarchy</a> (BVH). We call the second way space subdivision. As the name suggests, it divides space into sub spaces and assigns contained objects to these spaces. One concrete example for such a partitioning theme is a kd-tree.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*S6Fi47eD47IQFWLyds3HgQ.png" /><figcaption>BVH visualization of a <a href="https://casual-effects.com/data">Stanford Bunny</a>. Cyan boxes are left children, magenta boxes are right children. Images show how a BVH adjusts step by step to the mesh with several depth layers. From left to right: 1, 5, 9, 13.</figcaption></figure><p>The algorithms in the spirit of Divide &amp; Conquer are relatively straight-forward. But there is currently no practical way determining the best split position of a node on each level. So we don’t know which objects we have to group together or where we have to cut space into two subsequent nodes for the best performance.</p><p>The first computer graphic pioneers had to select the objects within an accelerator in a manual fashion. First automatic creations forced nodes to split in the middle. <a href="https://link.springer.com/article/10.1007/BF01911006">Other methods stopped subdivision when reaching a predefined tree or hierarchy depth</a>. Since these approaches don’t adapt to the scene structure, they fail for a plethora of scenes. Other uncertainties include the building speed and the selection of the split axis.</p><p>These are reasons why the research community assumes that <a href="http://research.nvidia.com/publication/quality-metrics-bounding-volume-hierarchies">creating an optimal accelerator is an NP-hard problem</a>. So we have to fallback to heuristics or cost models. With them, we can build sophisticated structures with reasonable performance. Surface Area Heuristic (SAH) to the rescue!</p><h4>SAH Concept</h4><p>Before we get to the formal descriptions, let’s try to grasp what the SAH trys to do in an intuitive way. The SAH rewards small nodes with many triangles, while avoiding large nodes with few triangles. Consider the following image. Think about what choice of split position (magenta line) would be the best:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JOaOx9bEDjJ4mg7HtJnaoQ.png" /></figure><p>If you guessed the third one, you are correct.</p><p>The first image shows the result of dividing a node in the middle. This may seem to be okay and not too bad. But there is quite a big chance that a ray might pierce the right child node. Indeed, it is actually a 50:50 situation. If we assume uniformly distributed and directed rays, every second ray will need to perform intersection tests with nearly every triangle. Not very promising.</p><p>The second image shows an even worse situation. Dividing the node at the median resulted in both regions requiring a test for more than half of all present triangles.</p><p>The last image shows an optimized solution. The SAH chooses the area for most of the triangles as tight as possible. Also, it raises the probability of only having to test a single triangle as much as possible by growing the surface area of the “cheap” left node. Cool!</p><h4>SAH Formula</h4><p>In the following section, we’ll have a look at the formal description of the SAH. Bear with me!</p><p><a href="https://link.springer.com/article/10.1007/BF01911006">MacDonald and Booth</a> proposed the SAH. It predicts the cost of a defined split position on a per-node basis. The model states that:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/900/1*AwfpiH2ElMX1gT722b59ug.png" /></figure><ul><li><em>C(A, B)</em> is the cost for splitting a node into volumes <em>A</em> and <em>B</em></li><li><em>t_traversal is </em>the time to traverse an interior node</li><li><em>p_A</em> and <em>p_B</em> are the probabilities that the ray passes through the volumes <em>A</em> and <em>B</em></li><li><em>N_A</em> and <em>N_B</em> are the number of triangles in volumes <em>A</em> and <em>B</em></li><li><em>a_i</em> and <em>b_i</em> are the <em>i</em>th triangle in volumes <em>A</em> and <em>B</em></li><li><em>t_intersect</em> is the cost for one ray-triangle intersection.</li></ul><p>We can compute p_A and p_B as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/175/1*d-xLAs8kC71DjQ1dKlCGlw.png" /></figure><ul><li><em>S_C</em> and <em>S_P</em> are the surface areas of volumes <em>C</em> and <em>P</em> (We can simply compute the surface area of a node by summing all faces of a node)</li><li><em>p(C|P)</em> is the conditional probability that a random ray passing through <em>P</em> will also pass through <em>C</em>, given that <em>C</em> is a convex volume in another convex volume <em>P</em>.</li></ul><p>These definitions are taken from the book <a href="http://www.pbrt.org/">Physically-based Rendering</a>.</p><p>Phew. Let that sink in for a minute.</p><p>With this formula, the SAH rewards many triangles in tight boxes which are not likely to get pierced by a ray.</p><p>We can compute the SAH for various split positions. Then, we select the one with the lowest cost. We can receive possible split positions by taking triangle bounds into consideration. Another method is called <a href="https://dl.acm.org/citation.cfm?id=1524953">binning</a>. It defines a certain amount of linearly distributed positions over an axis.</p><p>Further extensions to the SAH include a possible bonus for empty nodes. Also, there are improvements to the SAH assumptions, for example that rays are uniformly distributed in the scene.</p><p><strong>Back to the Drawing Board</strong></p><p>Now that we know about the formal details, let’s consider our previous example again. We will show why the third option is indeed the best choice according to the SAH. This way, we’ll get a better grasp of the SAH.</p><p>Let’s assume the costs <em>t_traversal </em>= 1 and <em>t_intersect </em>= 2. Then, we end up with:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lMCqKQ56x9d04KI29eOATg.png" /></figure><p>According to the SAH, the algorithm would then choose the third split position because it has the lowest cost. Sweet!</p><p>The next figure shows a heat map visualization. It shades a mesh depending on the number of traversed nodes and ray-triangle intersection tests.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*kze7OCdfdlc5uFmjgZR5RA.jpeg" /><figcaption><a href="https://casual-effects.com/data">Sibenik cathedral</a> heat map visualizations. Left: BVH built by always splitting the nodes in the middle. Right: BVH built with the SAH. We observe that the SAH lowers the number of traversed nodes and intersection tests significantly.</figcaption></figure><h4>Conclusion</h4><p>Well built acceleration structures are crucial for interactive ray tracing applications. The community assumes that building an optimal accelerator is an NP-hard problem. Thus, heuristics or cost models are vital to build high quality accelerators in reasonable time. The most prominent model in this field is the SAH. It tries to minimize the area of many adjacent triangles and maximize the area of smaller triangle groups. This reduces probabilities of ray-triangle intersection tests.</p><p>For a long time, I did not understand how to create accelerators in an adaptive way. I was very happy when I found out and hope that I supported you to grasp this idea too. If you’re eager to find out more about ray tracing and acceleration structures, be sure to check out <a href="http://pbrt.org/">Physically Based Rendering by Pharr et al.</a> It’s an awesome piece of work covering a plethora of ray tracing topics, including acceleration structures. At the end of this article you’ll also find a list of references I used in this article.</p><p>I’m a great friend of free and accessible knowledge for everyone. If my work helped you out and you feel like giving something back, you can consider supporting me by sharing this article. I deeply appreciate your support, truly. Thanks!</p><p>All the best, Broman</p><h4>References (in order of appearance)</h4><ul><li><a href="https://casual-effects.com/data">Morgan McGuire, Computer Graphics Archive, July 2017</a></li><li><a href="http://ieeexplore.ieee.org/document/4057175/">J. Goldsmith and J. Salmon. Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl., 7(5):14–20, 1987</a></li><li><a href="https://dl.acm.org/citation.cfm?id=358882">T. Whitted. An improved illumination model for shaded display. Commun. ACM, 23(6):343–349, 1980</a></li><li>M. R. Kaplan. The uses of spatial coherence in ray tracing. In SIGGRAPH ’85 Course notes no 11., 1985</li><li><a href="http://research.nvidia.com/publication/quality-metrics-bounding-volume-hierarchies">T. Aila, T. Karras, and S. Laine. On quality metrics of bounding volume hierarchies. In Proceedings of the 5th High-Performance Graphics Conference, HPG ’13, pages 101–107. ACM, 2013</a></li><li><a href="https://link.springer.com/article/10.1007/BF01911006">D. J. MacDonald and K. S. Booth. Heuristics for ray tracing using space subdivision. Vis. Comput., 6(3):153–166, 1990</a></li><li><a href="http://www.pbrt.org/">M. Pharr, J. Wenzel, and G. Humphreys. Physically Based Rendering, Third Edition: From Theory To Implementation. Morgan Kaufmann Publishers Inc., 3rd edition, 2016</a></li><li><a href="https://dl.acm.org/citation.cfm?id=1524953">I. Wald. On fast construction of sah-based bounding volume hierarchies. In Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, RT ’07, pages 33–40. IEEE Computer Society, 2007</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e14b5dec6160" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Utilizing SIMD/SSE in Unity3D (.NET 2.0)]]></title>
            <link>https://medium.com/@bromanz/simd-sse-unity3d-net-2-0-70f6c911713f?source=rss-a36dbb4b9c08------2</link>
            <guid isPermaLink="false">https://medium.com/p/70f6c911713f</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[simd]]></category>
            <category><![CDATA[csharp]]></category>
            <category><![CDATA[unity3d]]></category>
            <category><![CDATA[sse]]></category>
            <dc:creator><![CDATA[Roman Wiche]]></dc:creator>
            <pubDate>Wed, 18 Oct 2017 21:21:05 GMT</pubDate>
            <atom:updated>2019-05-07T20:09:09.786Z</atom:updated>
            <cc:license>http://creativecommons.org/licenses/by/4.0/</cc:license>
            <content:encoded><![CDATA[<p><strong>Motivation<br></strong>First of all, what does SIMD actually mean? I certainly haven’t heard of it until some years into my computer science studies. It is an acronym for <a href="https://en.wikipedia.org/wiki/SIMD">Single instruction, multiple data (SIMD)</a> and is related to the architecture of CPU’s and GPU’s. Another acronym often appearing alongside SIMD is <a href="https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions">Streaming SIMD Extensions (SSE)</a>. You can read theoretical details about it in various publications and all over the internet, but I’ll try to frame it in a simplified, practical fashion: Basically for you as a coder, SIMD allows to perform four operations (reading/writing/calculating) for the price of one instruction. The cost reduction is enabled by vectorization and data-parallelism. What a deal! And you don’t even have to handle threads and race conditions to gain this parallelism. You’d better take advantage of it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uiYS-VhMxoUm9EKMNTMwgQ.jpeg" /></figure><p><strong>The problem<br></strong>So from a conceptual standpoint, how can we translate that into code? Let’s assume we have an array of positions (three floats in a vector) and we would like to compute the average of all positions. To do so, we’d simply need to loop over the array, sum up all positions, and divide the result by the number of elements in the array. Speaking C# in Unity3D, the “normal” way we would implement it could look something like this:</p><pre>public Vector3 Average(Vector3[] positions)<br>{<br>   Vector3 summed = Vector3.zero;<br> <br>   for(int i=0;i&lt;positions.Length;i++)<br>   {<br>      summed += positions[i];<br>   }</pre><pre>   return summed / positions.Length;<br>}</pre><p>Unfortunately, SIMD is not directly supported in Unity. First, I thought you can utilize the Vector4 struct instead of Vector3 provided by UnityEngine, but that doesn’t work either. Thus, you have to come up with your own solution. From my point of view, you have the following options:</p><p>1. It is common to utilize the benefits of SIMD in C++ and related math libraries. Therefore, you could code part of the algorithm in C++. You’d then have to transfer the data from Unity to a DLL, compute the result “externally” in your C++ code and transfer the data back. This can be a viable option if there is a lot of computation required, but brings the problem of transferring the data back and forth. In addition, I think this <em>can </em>be more error prone due to the transfer of data and can slow down the development process, as the proper function and communication between two distinct components needs to be verified.</p><p>2. You can integrate plugins into Unity and implement SIMD operations directly in C#. Since this variant is simpler and should work well for smaller samples, I’ll elaborate on this option.</p><p><strong>Solution in C# with .NET 2.0<br></strong>Although Unity does not (yet?) support SIMD operations innately, you can take advantage of the Mono.simd.dll hidden in the Unity installation folder. Depending on the version you prefer, just copy the .dll from PathToUnity\Editor\Data\Mono\lib\mono\2.0over into your project. It provides 16-byte data structures like a vector with four floats or integers. Benefiting from using Mono.simd; we can change the previous code as follows:</p><pre>public Vector3 AverageSIMD(Vector3[] positions)<br>{<br>   Vector4f summed = new Vector4f(0, 0, 0, 0);<br>   <br>   for (int i = 0; i &lt; positions.Length; i++)<br>   {<br>      summed += new Vector4f(positions[i].x,<br>                             positions[i].y,<br>                             positions[i].z, 1.0f);<br>   }<br>   <br>   summed /= new Vector4f(positions.Length, <br>                          positions.Length, <br>                          positions.Length, 1.0f);</pre><pre>   return new Vector3(summed.X, summed.Y, summed.Z);<br> }</pre><p>In each step of the loop, the cost of summing up three float values was reduced to a single instruction. For one step in the loop, this may seem just a bit. However, depending on the number of positions we have to sum up, the performance gain will be significant. The provided version can be optimized further if the positions array is provided with Vector4f directly at the method call, so that the loop does not have to convert each Vector3 into a Vector4f. Comparing each variant with random generated positions gave the following results:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/989/1*mypOOn5wIBCChK4wrtCAww.jpeg" /></figure><p>While the SIMD with Vector3 conversion takes about 66% of the original duration, the SIMD without conversion actually just takes about 22% of the original duration. Neat, isn’t it?</p><p><strong>Conclusion<br></strong>SIMD offers powerful ways to crank up the performance and can be implemented within Unity. This article showed how to apply it to a simple problem, but I hope you are eager to apply it to other problems as well. How could this knowledge be applied to compute various powers of a number, a dot product, or a polynomial? (Maybe I’ll demonstrate this in another article). Think about how to package float values intelligently into the provided vector structs and work with them. Profile it, and see if the change was worth it. <br>For the future, it would be cool to find out how the performance compares to the C++ alternative mentioned earlier in this article. Furthermore, newer versions of Unity (2017+) already provide experimental support for .NET 4.6, which offers <a href="https://msdn.microsoft.com/en-ca/library/mt452176(v=vs.111).aspx">System.Numerics</a>. A quick test exposed that these vector structs seem to be superior to the Mono.Simd equivalent. Also, the UnityEngine.Vector3 seems to compute faster with .NET 4.6, but I’d need to investigate this further. When Unity will provide stable support for .NET 4.6, the new structs will definitely be very viable options for SIMD improvements.</p><p>[UPDATE 03/2018] Now that the C# Entity-Component-System, Job System, and Burst compiler will be available soon, you should consider using it: <a href="https://www.youtube.com/watch?v=tGmnZdY5Y-E">Unite Austin 2017 — Writing High Performance C# Scripts</a></p><p>I’m a great friend of free and accessible knowledge for everyone. If my work helped you out and you feel like giving something back, you can consider supporting me by sharing this article. I deeply appreciate your support, truly. Thanks!</p><p>All the best, Broman</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=70f6c911713f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>