doxygen/html/kdtree_8cpp-source.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>pbrt: kdtree.cpp Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.6 -->
<div class="navigation" id="top">
  <div class="tabs">
    <ul>
      <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li class="current"><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
<h1>kdtree.cpp</h1><a href="kdtree_8cpp.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 
<a name="l00002"></a>00002 <span class="comment">/*</span>
<a name="l00003"></a>00003 <span class="comment">    pbrt source code Copyright(c) 1998-2007 Matt Pharr and Greg Humphreys.</span>
<a name="l00004"></a>00004 <span class="comment"></span>
<a name="l00005"></a>00005 <span class="comment">    This file is part of pbrt.</span>
<a name="l00006"></a>00006 <span class="comment"></span>
<a name="l00007"></a>00007 <span class="comment">    pbrt is free software; you can redistribute it and/or modify</span>
<a name="l00008"></a>00008 <span class="comment">    it under the terms of the GNU General Public License as published by</span>
<a name="l00009"></a>00009 <span class="comment">    the Free Software Foundation; either version 2 of the License, or</span>
<a name="l00010"></a>00010 <span class="comment">    (at your option) any later version.  Note that the text contents of</span>
<a name="l00011"></a>00011 <span class="comment">    the book "Physically Based Rendering" are *not* licensed under the</span>
<a name="l00012"></a>00012 <span class="comment">    GNU GPL.</span>
<a name="l00013"></a>00013 <span class="comment"></span>
<a name="l00014"></a>00014 <span class="comment">    pbrt is distributed in the hope that it will be useful,</span>
<a name="l00015"></a>00015 <span class="comment">    but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00016"></a>00016 <span class="comment">    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the</span>
<a name="l00017"></a>00017 <span class="comment">    GNU General Public License for more details.</span>
<a name="l00018"></a>00018 <span class="comment"></span>
<a name="l00019"></a>00019 <span class="comment">    You should have received a copy of the GNU General Public License</span>
<a name="l00020"></a>00020 <span class="comment">    along with this program.  If not, see &lt;http://www.gnu.org/licenses/&gt;.</span>
<a name="l00021"></a>00021 <span class="comment"></span>
<a name="l00022"></a>00022 <span class="comment"> */</span>
<a name="l00023"></a>00023 
<a name="l00024"></a>00024 <span class="comment">// kdtree.cpp*</span>
<a name="l00025"></a>00025 <span class="preprocessor">#include "<a class="code" href="pbrt_8h.html">pbrt.h</a>"</span>
<a name="l00026"></a>00026 <span class="preprocessor">#include "<a class="code" href="primitive_8h.html">primitive.h</a>"</span>
<a name="l00027"></a>00027 <span class="comment">// KdAccelNode Declarations</span>
<a name="l00028"></a>00028 <span class="keyword">struct </span><a class="code" href="structMailboxPrim.html">MailboxPrim</a> {
<a name="l00029"></a><a class="code" href="structMailboxPrim.html#55176dcb2ffa6eb28784971189643781">00029</a>         <a class="code" href="structMailboxPrim.html#55176dcb2ffa6eb28784971189643781">MailboxPrim</a>(<span class="keyword">const</span> <a class="code" href="classReference.html">Reference&lt;Primitive&gt;</a> &amp;p) {
<a name="l00030"></a>00030                 <a class="code" href="structMailboxPrim.html#6f38bbe89d239a2b92311f292ee3063a">primitive</a> = p;
<a name="l00031"></a>00031                 <a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> = -1;
<a name="l00032"></a>00032         }
<a name="l00033"></a>00033         <a class="code" href="classReference.html">Reference&lt;Primitive&gt;</a> <a class="code" href="structMailboxPrim.html#6f38bbe89d239a2b92311f292ee3063a">primitive</a>;
<a name="l00034"></a>00034         <span class="keywordtype">int</span> <a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a>;
<a name="l00035"></a>00035 };
<a name="l00036"></a><a class="code" href="structKdAccelNode.html">00036</a> <span class="keyword">struct </span><a class="code" href="structKdAccelNode.html">KdAccelNode</a> {
<a name="l00037"></a>00037         <span class="comment">// KdAccelNode Methods</span>
<a name="l00038"></a><a class="code" href="structKdAccelNode.html#6fc2201c22f04f078707674e8a410c05">00038</a>         <span class="keywordtype">void</span> <a class="code" href="structKdAccelNode.html#6fc2201c22f04f078707674e8a410c05">initLeaf</a>(<span class="keywordtype">int</span> *primNums, <span class="keywordtype">int</span> np,
<a name="l00039"></a>00039                         <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *mailboxPrims, <a class="code" href="classMemoryArena.html">MemoryArena</a> &amp;arena) {
<a name="l00040"></a>00040                 <span class="comment">// Update kd leaf node allocation statistics</span>
<a name="l00041"></a>00041                 <span class="keyword">static</span> <a class="code" href="classStatsCounter.html">StatsCounter</a> numLeafMade(<span class="stringliteral">"Kd-Tree Accelerator"</span>,
<a name="l00042"></a>00042                                                 <span class="stringliteral">"Leaf kd-tree nodes made"</span>);
<a name="l00043"></a>00043                 <span class="comment">//static StatsCounter maxDepth("Kd-Tree Accelerator",</span>
<a name="l00044"></a>00044                 <span class="comment">//                             "Maximum kd-tree depth");</span>
<a name="l00045"></a>00045                 <span class="keyword">static</span> <a class="code" href="classStatsCounter.html">StatsCounter</a> maxLeafPrims(<span class="stringliteral">"Kd-Tree Accelerator"</span>,
<a name="l00046"></a>00046                         <span class="stringliteral">"Maximum number of primitives in leaf node"</span>);
<a name="l00047"></a>00047                 ++numLeafMade;
<a name="l00048"></a>00048                 <span class="comment">//maxDepth.Max(depth);</span>
<a name="l00049"></a>00049                 maxLeafPrims.<a class="code" href="classStatsCounter.html#8e0916b5f43cf8e8e89d5b2c3c20b87a">Max</a>(np);
<a name="l00050"></a>00050                 <span class="keyword">static</span> <a class="code" href="classStatsRatio.html">StatsRatio</a> leafPrims(<span class="stringliteral">"Kd-Tree Accelerator"</span>,
<a name="l00051"></a>00051                         <span class="stringliteral">"Avg. number of primitives in leaf nodes"</span>);
<a name="l00052"></a>00052                 leafPrims.<a class="code" href="classStatsRatio.html#c0530f7ffbb92fa6f736767f0217ed51">Add</a>(np, 1);
<a name="l00053"></a>00053                 <a class="code" href="structKdAccelNode.html#609ce5843e395b81c9edd5c57b73b87c">nPrims</a> = np &lt;&lt; 2;
<a name="l00054"></a>00054                 <a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">flags</a> |= 3;
<a name="l00055"></a>00055                 <span class="comment">// Store _MailboxPrim *_s for leaf node</span>
<a name="l00056"></a>00056                 <span class="keywordflow">if</span> (np == 0)
<a name="l00057"></a>00057                         <a class="code" href="structKdAccelNode.html#9321fe66117c7a99121db94cb77995ba">onePrimitive</a> = NULL;
<a name="l00058"></a>00058                 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (np == 1)
<a name="l00059"></a>00059                         <a class="code" href="structKdAccelNode.html#9321fe66117c7a99121db94cb77995ba">onePrimitive</a> = &amp;mailboxPrims[primNums[0]];
<a name="l00060"></a>00060                 <span class="keywordflow">else</span> {
<a name="l00061"></a>00061                         <a class="code" href="structKdAccelNode.html#e63025f82b0ddee781b570123bfc52c8">primitives</a> = (<a class="code" href="structMailboxPrim.html">MailboxPrim</a> **)arena.<a class="code" href="classMemoryArena.html#d36b79fe2137490940c57d090cf58674">Alloc</a>(np *
<a name="l00062"></a>00062                                 <span class="keyword">sizeof</span>(<a class="code" href="structMailboxPrim.html">MailboxPrim</a> *));
<a name="l00063"></a>00063                         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; np; ++i)
<a name="l00064"></a>00064                                 <a class="code" href="structKdAccelNode.html#e63025f82b0ddee781b570123bfc52c8">primitives</a>[i] = &amp;mailboxPrims[primNums[i]];
<a name="l00065"></a>00065                 }
<a name="l00066"></a>00066         }
<a name="l00067"></a><a class="code" href="structKdAccelNode.html#41d3268a638d7635f2301cd26742668b">00067</a>         <span class="keywordtype">void</span> <a class="code" href="structKdAccelNode.html#41d3268a638d7635f2301cd26742668b">initInterior</a>(<span class="keywordtype">int</span> axis, <span class="keywordtype">float</span> s) {
<a name="l00068"></a>00068                 <span class="keyword">static</span> <a class="code" href="classStatsCounter.html">StatsCounter</a> nodesMade(<span class="stringliteral">"Kd-Tree Accelerator"</span>, <span class="stringliteral">"Interior kd-tree nodes made"</span>); <span class="comment">// NOBOOK</span>
<a name="l00069"></a>00069                 ++nodesMade; <span class="comment">// NOBOOK</span>
<a name="l00070"></a>00070                 <a class="code" href="structKdAccelNode.html#d01f9afa92372d028e21281138eec26f">split</a> = s;
<a name="l00071"></a>00071                 <a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">flags</a> &amp;= ~3;
<a name="l00072"></a>00072                 <a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">flags</a> |= axis;
<a name="l00073"></a>00073         }
<a name="l00074"></a><a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">00074</a>         <span class="keywordtype">float</span> <a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="structKdAccelNode.html#d01f9afa92372d028e21281138eec26f">split</a>; }
<a name="l00075"></a><a class="code" href="structKdAccelNode.html#130aad6aa2dc153a1e2ffacd45e44494">00075</a>         <span class="keywordtype">int</span> <a class="code" href="structKdAccelNode.html#130aad6aa2dc153a1e2ffacd45e44494">nPrimitives</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="structKdAccelNode.html#609ce5843e395b81c9edd5c57b73b87c">nPrims</a> &gt;&gt; 2; }
<a name="l00076"></a><a class="code" href="structKdAccelNode.html#3bf5999b06774527309b3220644dd5d9">00076</a>         <span class="keywordtype">int</span> <a class="code" href="structKdAccelNode.html#3bf5999b06774527309b3220644dd5d9">SplitAxis</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">flags</a> &amp; 3; }
<a name="l00077"></a><a class="code" href="structKdAccelNode.html#2dd55e7aebd0c6cc67403e33b92d103e">00077</a>         <span class="keywordtype">bool</span> <a class="code" href="structKdAccelNode.html#2dd55e7aebd0c6cc67403e33b92d103e">IsLeaf</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> (<a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">flags</a> &amp; 3) == 3; }
<a name="l00078"></a>00078         <span class="keyword">union </span>{
<a name="l00079"></a><a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">00079</a>                 <a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> <a class="code" href="structKdAccelNode.html#64309531baa7364a96612d3c699ccd91">flags</a>;   <span class="comment">// Both</span>
<a name="l00080"></a><a class="code" href="structKdAccelNode.html#d01f9afa92372d028e21281138eec26f">00080</a>                 <span class="keywordtype">float</span> <a class="code" href="structKdAccelNode.html#d01f9afa92372d028e21281138eec26f">split</a>;   <span class="comment">// Interior</span>
<a name="l00081"></a><a class="code" href="structKdAccelNode.html#609ce5843e395b81c9edd5c57b73b87c">00081</a>                 <a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> <a class="code" href="structKdAccelNode.html#609ce5843e395b81c9edd5c57b73b87c">nPrims</a>;  <span class="comment">// Leaf</span>
<a name="l00082"></a>00082         };
<a name="l00083"></a>00083         <span class="keyword">union </span>{
<a name="l00084"></a><a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">00084</a>                 <a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> <a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">aboveChild</a>;           <span class="comment">// Interior</span>
<a name="l00085"></a><a class="code" href="structKdAccelNode.html#9321fe66117c7a99121db94cb77995ba">00085</a>                 <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *<a class="code" href="structKdAccelNode.html#9321fe66117c7a99121db94cb77995ba">onePrimitive</a>;  <span class="comment">// Leaf</span>
<a name="l00086"></a><a class="code" href="structKdAccelNode.html#e63025f82b0ddee781b570123bfc52c8">00086</a>                 <a class="code" href="structMailboxPrim.html">MailboxPrim</a> **<a class="code" href="structKdAccelNode.html#e63025f82b0ddee781b570123bfc52c8">primitives</a>;   <span class="comment">// Leaf</span>
<a name="l00087"></a>00087         };
<a name="l00088"></a>00088 };
<a name="l00089"></a><a class="code" href="structBoundEdge.html">00089</a> <span class="keyword">struct </span><a class="code" href="structBoundEdge.html">BoundEdge</a> {
<a name="l00090"></a>00090         <span class="comment">// BoundEdge Public Methods</span>
<a name="l00091"></a><a class="code" href="structBoundEdge.html#64e06f6561f6ab6072d16ae7eb605a37">00091</a>         <a class="code" href="structBoundEdge.html#64e06f6561f6ab6072d16ae7eb605a37">BoundEdge</a>() { }
<a name="l00092"></a><a class="code" href="structBoundEdge.html#dbbd76d8496c78a403bb9c6f8c2ea3ae">00092</a>         <a class="code" href="structBoundEdge.html#64e06f6561f6ab6072d16ae7eb605a37">BoundEdge</a>(<span class="keywordtype">float</span> tt, <span class="keywordtype">int</span> pn, <span class="keywordtype">bool</span> starting) {
<a name="l00093"></a>00093                 <a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a> = tt;
<a name="l00094"></a>00094                 <a class="code" href="structBoundEdge.html#fc3ae70ceb7900b2ebecef81eb2644a9">primNum</a> = pn;
<a name="l00095"></a>00095                 <a class="code" href="structBoundEdge.html#cf8b4bbd4d06a4f389f870276acd3215">type</a> = starting ? <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80fad2c2d42b8b6d0315dd46136b45305de">START</a> : <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80f376ce9156fc010604ed569d04ac9e688">END</a>;
<a name="l00096"></a>00096         }
<a name="l00097"></a><a class="code" href="structBoundEdge.html#90fe9cbf55124a70659287a62a4e139d">00097</a>         <span class="keywordtype">bool</span> <a class="code" href="structBoundEdge.html#90fe9cbf55124a70659287a62a4e139d">operator&lt;</a>(<span class="keyword">const</span> <a class="code" href="structBoundEdge.html">BoundEdge</a> &amp;e)<span class="keyword"> const </span>{
<a name="l00098"></a>00098                 <span class="keywordflow">if</span> (<a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a> == e.<a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a>)
<a name="l00099"></a>00099                         <span class="keywordflow">return</span> (<span class="keywordtype">int</span>)<a class="code" href="structBoundEdge.html#cf8b4bbd4d06a4f389f870276acd3215">type</a> &lt; (int)e.<a class="code" href="structBoundEdge.html#cf8b4bbd4d06a4f389f870276acd3215">type</a>;
<a name="l00100"></a>00100                 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a> &lt; e.<a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a>;
<a name="l00101"></a>00101         }
<a name="l00102"></a><a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">00102</a>         <span class="keywordtype">float</span> <a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a>;
<a name="l00103"></a><a class="code" href="structBoundEdge.html#fc3ae70ceb7900b2ebecef81eb2644a9">00103</a>         <span class="keywordtype">int</span> <a class="code" href="structBoundEdge.html#fc3ae70ceb7900b2ebecef81eb2644a9">primNum</a>;
<a name="l00104"></a><a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80fad2c2d42b8b6d0315dd46136b45305de">00104</a>         <span class="keyword">enum</span> { <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80fad2c2d42b8b6d0315dd46136b45305de">START</a>, <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80f376ce9156fc010604ed569d04ac9e688">END</a> } <a class="code" href="structBoundEdge.html#cf8b4bbd4d06a4f389f870276acd3215">type</a>;
<a name="l00105"></a>00105 };
<a name="l00106"></a>00106 <span class="comment">// KdTreeAccel Declarations</span>
<a name="l00107"></a>00107 <span class="keyword">struct </span><a class="code" href="structKdAccelNode.html">KdAccelNode</a>;
<a name="l00108"></a><a class="code" href="classKdTreeAccel.html">00108</a> <span class="keyword">class  </span><a class="code" href="classKdTreeAccel.html">KdTreeAccel</a> : <span class="keyword">public</span> <a class="code" href="classAggregate.html">Aggregate</a> {
<a name="l00109"></a>00109 <span class="keyword">public</span>:
<a name="l00110"></a>00110         <span class="comment">// KdTreeAccel Public Methods</span>
<a name="l00111"></a>00111         <a class="code" href="classKdTreeAccel.html#62f9a15970262e8b316e35fcab2956e4">KdTreeAccel</a>(<span class="keyword">const</span> vector&lt;<a class="code" href="classReference.html">Reference&lt;Primitive&gt;</a> &gt; &amp;p,
<a name="l00112"></a>00112                 <span class="keywordtype">int</span> icost, <span class="keywordtype">int</span> scost,
<a name="l00113"></a>00113                 <span class="keywordtype">float</span> ebonus, <span class="keywordtype">int</span> maxp, <span class="keywordtype">int</span> maxDepth);
<a name="l00114"></a><a class="code" href="classKdTreeAccel.html#a8dedf8866949620dcf1d31aca26935b">00114</a>         <a class="code" href="classBBox.html">BBox</a> <a class="code" href="classKdTreeAccel.html#a8dedf8866949620dcf1d31aca26935b">WorldBound</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>; }
<a name="l00115"></a><a class="code" href="classKdTreeAccel.html#4508e3d3e599429304e2ed0da848390a">00115</a>         <span class="keywordtype">bool</span> <a class="code" href="classKdTreeAccel.html#4508e3d3e599429304e2ed0da848390a">CanIntersect</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <span class="keyword">true</span>; }
<a name="l00116"></a>00116         <a class="code" href="classKdTreeAccel.html#5bc6b8ac95f4f03363f24a19bb88f04e">~KdTreeAccel</a>();
<a name="l00117"></a>00117         <span class="keywordtype">void</span> <a class="code" href="classKdTreeAccel.html#081525774974a4d860f28488cd5285c7">buildTree</a>(<span class="keywordtype">int</span> nodeNum, <span class="keyword">const</span> <a class="code" href="classBBox.html">BBox</a> &amp;<a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>,
<a name="l00118"></a>00118             <span class="keyword">const</span> vector&lt;BBox&gt; &amp;primBounds,
<a name="l00119"></a>00119                 <span class="keywordtype">int</span> *primNums, <span class="keywordtype">int</span> nprims, <span class="keywordtype">int</span> depth,
<a name="l00120"></a>00120                 <a class="code" href="structBoundEdge.html">BoundEdge</a> *edges[3],
<a name="l00121"></a>00121                 <span class="keywordtype">int</span> *prims0, <span class="keywordtype">int</span> *prims1, <span class="keywordtype">int</span> badRefines = 0);
<a name="l00122"></a>00122         <span class="keywordtype">bool</span> <a class="code" href="classKdTreeAccel.html#3e6620d44766ad36a06c2515c73c3f94">Intersect</a>(<span class="keyword">const</span> <a class="code" href="classRay.html">Ray</a> &amp;ray, <a class="code" href="structIntersection.html">Intersection</a> *isect) <span class="keyword">const</span>;
<a name="l00123"></a>00123         <span class="keywordtype">bool</span> <a class="code" href="classKdTreeAccel.html#7c038872df7027e0f0d7be0d1108bb66">IntersectP</a>(<span class="keyword">const</span> <a class="code" href="classRay.html">Ray</a> &amp;ray) <span class="keyword">const</span>;
<a name="l00124"></a>00124 <span class="keyword">private</span>:
<a name="l00125"></a>00125         <span class="comment">// KdTreeAccel Private Data</span>
<a name="l00126"></a><a class="code" href="classKdTreeAccel.html#96d40a7cb14257932f589642862a72c5">00126</a>         <span class="keywordtype">int</span> <a class="code" href="classKdTreeAccel.html#5812c41fd50653c6331044d1989af185">isectCost</a>, <a class="code" href="classKdTreeAccel.html#96d40a7cb14257932f589642862a72c5">traversalCost</a>, <a class="code" href="classKdTreeAccel.html#7402fb2d0d5763961bc8c82acbe91f3a">maxPrims</a>;
<a name="l00127"></a><a class="code" href="classKdTreeAccel.html#7c30ec030e0340a801858bb6eb698d29">00127</a>         <span class="keywordtype">float</span> <a class="code" href="classKdTreeAccel.html#7c30ec030e0340a801858bb6eb698d29">emptyBonus</a>;
<a name="l00128"></a><a class="code" href="classKdTreeAccel.html#9be5bd79d199360cc542a3210b3c930d">00128</a>         <a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> <a class="code" href="classKdTreeAccel.html#9be5bd79d199360cc542a3210b3c930d">nMailboxes</a>;
<a name="l00129"></a><a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">00129</a>         <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *<a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a>;
<a name="l00130"></a><a class="code" href="classKdTreeAccel.html#f75252a3070a8413f49147c8340c65a8">00130</a>         <span class="keyword">mutable</span> <span class="keywordtype">int</span> <a class="code" href="classKdTreeAccel.html#f75252a3070a8413f49147c8340c65a8">curMailboxId</a>;
<a name="l00131"></a><a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">00131</a>         <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>;
<a name="l00132"></a><a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">00132</a>         <span class="keywordtype">int</span> <a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a>, <a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">nextFreeNode</a>;
<a name="l00133"></a><a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">00133</a>         <a class="code" href="classBBox.html">BBox</a> <a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>;
<a name="l00134"></a><a class="code" href="classKdTreeAccel.html#517b3a08d6596893b29f72e22e221016">00134</a>         <a class="code" href="classMemoryArena.html">MemoryArena</a> <a class="code" href="classKdTreeAccel.html#517b3a08d6596893b29f72e22e221016">arena</a>;
<a name="l00135"></a>00135 };
<a name="l00136"></a><a class="code" href="structKdToDo.html">00136</a> <span class="keyword">struct </span><a class="code" href="structKdToDo.html">KdToDo</a> {
<a name="l00137"></a><a class="code" href="structKdToDo.html#b481373c1ed09adca53e1c5004d2e83f">00137</a>         <span class="keyword">const</span> <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *<a class="code" href="structKdToDo.html#b481373c1ed09adca53e1c5004d2e83f">node</a>;
<a name="l00138"></a><a class="code" href="structKdToDo.html#697d1bb71b5168c10372863f422df3fa">00138</a>         <span class="keywordtype">float</span> <a class="code" href="structKdToDo.html#697d1bb71b5168c10372863f422df3fa">tmin</a>, <a class="code" href="structKdToDo.html#8634eadf7b2289a771626a3aecc8fe12">tmax</a>;
<a name="l00139"></a>00139 };
<a name="l00140"></a>00140 <span class="comment">// KdTreeAccel Method Definitions</span>
<a name="l00141"></a>00141 <a class="code" href="classKdTreeAccel.html#62f9a15970262e8b316e35fcab2956e4">KdTreeAccel::</a>
<a name="l00142"></a><a class="code" href="classKdTreeAccel.html#62f9a15970262e8b316e35fcab2956e4">00142</a> <a class="code" href="classKdTreeAccel.html#62f9a15970262e8b316e35fcab2956e4">    KdTreeAccel</a>(<span class="keyword">const</span> vector&lt;<a class="code" href="classReference.html">Reference&lt;Primitive&gt;</a> &gt; &amp;p,
<a name="l00143"></a>00143                 <span class="keywordtype">int</span> icost, <span class="keywordtype">int</span> tcost,
<a name="l00144"></a>00144                 <span class="keywordtype">float</span> ebonus, <span class="keywordtype">int</span> maxp, <span class="keywordtype">int</span> maxDepth)
<a name="l00145"></a>00145         : isectCost(icost), traversalCost(tcost),
<a name="l00146"></a>00146         maxPrims(maxp), emptyBonus(ebonus) {
<a name="l00147"></a>00147         vector&lt;Reference&lt;Primitive &gt; &gt; prims;
<a name="l00148"></a>00148         <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; p.size(); ++i)
<a name="l00149"></a>00149                 p[i]-&gt;<a class="code" href="classPrimitive.html#19ae8ce0faad41fcd789ce48cd6c3260">FullyRefine</a>(prims);
<a name="l00150"></a>00150         <span class="comment">// Initialize mailboxes for _KdTreeAccel_</span>
<a name="l00151"></a>00151         <a class="code" href="classKdTreeAccel.html#f75252a3070a8413f49147c8340c65a8">curMailboxId</a> = 0;
<a name="l00152"></a>00152         <a class="code" href="classKdTreeAccel.html#9be5bd79d199360cc542a3210b3c930d">nMailboxes</a> = prims.size();
<a name="l00153"></a>00153         <a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a> = (<a class="code" href="structMailboxPrim.html">MailboxPrim</a> *)<a class="code" href="pbrt_8h.html#6999b138e9c0d348eee4455b4ba3d624">AllocAligned</a>(<a class="code" href="classKdTreeAccel.html#9be5bd79d199360cc542a3210b3c930d">nMailboxes</a> *
<a name="l00154"></a>00154                 <span class="keyword">sizeof</span>(<a class="code" href="structMailboxPrim.html">MailboxPrim</a>));
<a name="l00155"></a>00155         <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; <a class="code" href="classKdTreeAccel.html#9be5bd79d199360cc542a3210b3c930d">nMailboxes</a>; ++i)
<a name="l00156"></a>00156                 <span class="keyword">new</span> (&amp;<a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a>[i]) <a class="code" href="structMailboxPrim.html">MailboxPrim</a>(prims[i]);
<a name="l00157"></a>00157         <span class="comment">// Build kd-tree for accelerator</span>
<a name="l00158"></a>00158         <a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">nextFreeNode</a> = <a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a> = 0;
<a name="l00159"></a>00159         <span class="keywordflow">if</span> (maxDepth &lt;= 0)
<a name="l00160"></a>00160                 maxDepth =
<a name="l00161"></a>00161                     <a class="code" href="pbrt_8h.html#9fc5ba3cf5304cfa5cf04fe22fa7a0f1">Round2Int</a>(8 + 1.3f * <a class="code" href="pbrt_8h.html#8bc246329312fc639a86e37fa937b483">Log2Int</a>(<span class="keywordtype">float</span>(prims.size())));
<a name="l00162"></a>00162         <span class="comment">// Compute bounds for kd-tree construction</span>
<a name="l00163"></a>00163         vector&lt;BBox&gt; primBounds;
<a name="l00164"></a>00164         primBounds.reserve(prims.size());
<a name="l00165"></a>00165         <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; prims.size(); ++i) {
<a name="l00166"></a>00166                 <a class="code" href="classBBox.html">BBox</a> b = prims[i]-&gt;WorldBound();
<a name="l00167"></a>00167                 <a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a> = <a class="code" href="geometry_8cpp.html#b6b355a05ae9130aceaa5ed34f3eb75b">Union</a>(<a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>, b);
<a name="l00168"></a>00168                 primBounds.push_back(b);
<a name="l00169"></a>00169         }
<a name="l00170"></a>00170         <span class="comment">// Allocate working memory for kd-tree construction</span>
<a name="l00171"></a>00171         <a class="code" href="structBoundEdge.html">BoundEdge</a> *edges[3];
<a name="l00172"></a>00172         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; 3; ++i)
<a name="l00173"></a>00173                 edges[i] = <span class="keyword">new</span> <a class="code" href="structBoundEdge.html">BoundEdge</a>[2*prims.size()];
<a name="l00174"></a>00174         <span class="keywordtype">int</span> *prims0 = <span class="keyword">new</span> <span class="keywordtype">int</span>[prims.size()];
<a name="l00175"></a>00175         <span class="keywordtype">int</span> *prims1 = <span class="keyword">new</span> <span class="keywordtype">int</span>[(maxDepth+1) * prims.size()];
<a name="l00176"></a>00176         <span class="comment">// Initialize _primNums_ for kd-tree construction</span>
<a name="l00177"></a>00177         <span class="keywordtype">int</span> *primNums = <span class="keyword">new</span> <span class="keywordtype">int</span>[prims.size()];
<a name="l00178"></a>00178         <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; prims.size(); ++i)
<a name="l00179"></a>00179                 primNums[i] = i;
<a name="l00180"></a>00180         <span class="comment">// Start recursive construction of kd-tree</span>
<a name="l00181"></a>00181         <a class="code" href="classKdTreeAccel.html#081525774974a4d860f28488cd5285c7">buildTree</a>(0, <a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>, primBounds, primNums,
<a name="l00182"></a>00182                   prims.size(), maxDepth, edges,
<a name="l00183"></a>00183                           prims0, prims1);
<a name="l00184"></a>00184         <span class="comment">// Free working memory for kd-tree construction</span>
<a name="l00185"></a>00185         <span class="keyword">delete</span>[] primNums;
<a name="l00186"></a>00186         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; 3; ++i)
<a name="l00187"></a>00187                 <span class="keyword">delete</span>[] edges[i];
<a name="l00188"></a>00188         <span class="keyword">delete</span>[] prims0;
<a name="l00189"></a>00189         <span class="keyword">delete</span>[] prims1;
<a name="l00190"></a>00190 }
<a name="l00191"></a><a class="code" href="classKdTreeAccel.html#5bc6b8ac95f4f03363f24a19bb88f04e">00191</a> <a class="code" href="classKdTreeAccel.html#5bc6b8ac95f4f03363f24a19bb88f04e">KdTreeAccel::~KdTreeAccel</a>() {
<a name="l00192"></a>00192         <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; <a class="code" href="classKdTreeAccel.html#9be5bd79d199360cc542a3210b3c930d">nMailboxes</a>; ++i)
<a name="l00193"></a>00193                 <a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a>[i].~<a class="code" href="structMailboxPrim.html">MailboxPrim</a>();
<a name="l00194"></a>00194         <a class="code" href="pbrt_8h.html#338d7748e3c01292726a6e82059d90ff">FreeAligned</a>(<a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a>);
<a name="l00195"></a>00195         <a class="code" href="pbrt_8h.html#338d7748e3c01292726a6e82059d90ff">FreeAligned</a>(<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>);
<a name="l00196"></a>00196 }
<a name="l00197"></a><a class="code" href="classKdTreeAccel.html#081525774974a4d860f28488cd5285c7">00197</a> <span class="keywordtype">void</span> <a class="code" href="classKdTreeAccel.html#081525774974a4d860f28488cd5285c7">KdTreeAccel::buildTree</a>(<span class="keywordtype">int</span> nodeNum,
<a name="l00198"></a>00198         <span class="keyword">const</span> <a class="code" href="classBBox.html">BBox</a> &amp;nodeBounds,
<a name="l00199"></a>00199                 <span class="keyword">const</span> vector&lt;BBox&gt; &amp;allPrimBounds, <span class="keywordtype">int</span> *primNums,
<a name="l00200"></a>00200                 <span class="keywordtype">int</span> nPrims, <span class="keywordtype">int</span> depth, <a class="code" href="structBoundEdge.html">BoundEdge</a> *edges[3],
<a name="l00201"></a>00201                 <span class="keywordtype">int</span> *prims0, <span class="keywordtype">int</span> *prims1, <span class="keywordtype">int</span> badRefines) {
<a name="l00202"></a>00202         <a class="code" href="pbrt_8h.html#ab1e54dcc40192f9704e8b252635450f">Assert</a>(nodeNum == <a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">nextFreeNode</a>); <span class="comment">// NOBOOK</span>
<a name="l00203"></a>00203         <span class="comment">// Get next free node from _nodes_ array</span>
<a name="l00204"></a>00204         <span class="keywordflow">if</span> (<a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">nextFreeNode</a> == <a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a>) {
<a name="l00205"></a>00205                 <span class="keywordtype">int</span> nAlloc = max(2 * <a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a>, 512);
<a name="l00206"></a>00206                 <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *n = (<a class="code" href="structKdAccelNode.html">KdAccelNode</a> *)<a class="code" href="pbrt_8h.html#6999b138e9c0d348eee4455b4ba3d624">AllocAligned</a>(nAlloc *
<a name="l00207"></a>00207                         <span class="keyword">sizeof</span>(<a class="code" href="structKdAccelNode.html">KdAccelNode</a>));
<a name="l00208"></a>00208                 <span class="keywordflow">if</span> (<a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a> &gt; 0) {
<a name="l00209"></a>00209                         <a class="code" href="pbrtparse_8y.html#2ac249754cc680184bc1b7825aacb876">memcpy</a>(n, <a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>,
<a name="l00210"></a>00210                                <a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a> * <span class="keyword">sizeof</span>(<a class="code" href="structKdAccelNode.html">KdAccelNode</a>));
<a name="l00211"></a>00211                         <a class="code" href="pbrt_8h.html#338d7748e3c01292726a6e82059d90ff">FreeAligned</a>(<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>);
<a name="l00212"></a>00212                 }
<a name="l00213"></a>00213                 <a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a> = n;
<a name="l00214"></a>00214                 <a class="code" href="classKdTreeAccel.html#b74a4e1db5a9ca478144cb08a692fd7b">nAllocedNodes</a> = nAlloc;
<a name="l00215"></a>00215         }
<a name="l00216"></a>00216         ++<a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">nextFreeNode</a>;
<a name="l00217"></a>00217         <span class="comment">// Initialize leaf node if termination criteria met</span>
<a name="l00218"></a>00218         <span class="keywordflow">if</span> (nPrims &lt;= <a class="code" href="classKdTreeAccel.html#7402fb2d0d5763961bc8c82acbe91f3a">maxPrims</a> || depth == 0) {
<a name="l00219"></a>00219                 <a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[nodeNum].<a class="code" href="structKdAccelNode.html#6fc2201c22f04f078707674e8a410c05">initLeaf</a>(primNums, nPrims,
<a name="l00220"></a>00220                                        <a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a>, <a class="code" href="classKdTreeAccel.html#517b3a08d6596893b29f72e22e221016">arena</a>);
<a name="l00221"></a>00221                 <span class="keywordflow">return</span>;
<a name="l00222"></a>00222         }
<a name="l00223"></a>00223         <span class="comment">// Initialize interior node and continue recursion</span>
<a name="l00224"></a>00224         <span class="comment">// Choose split axis position for interior node</span>
<a name="l00225"></a>00225         <span class="keywordtype">int</span> bestAxis = -1, bestOffset = -1;
<a name="l00226"></a>00226         <span class="keywordtype">float</span> bestCost = <a class="code" href="pbrt_8h.html#956e2723d559858d08644ac99146e910">INFINITY</a>;
<a name="l00227"></a>00227         <span class="keywordtype">float</span> oldCost = <a class="code" href="classKdTreeAccel.html#5812c41fd50653c6331044d1989af185">isectCost</a> * float(nPrims);
<a name="l00228"></a>00228         <a class="code" href="classVector.html">Vector</a> d = nodeBounds.<a class="code" href="classBBox.html#144894960e2a634983f4d579d7cfc02e">pMax</a> - nodeBounds.<a class="code" href="classBBox.html#6efc252ac04a7236369d0ebdc11dab4c">pMin</a>;
<a name="l00229"></a>00229         <span class="keywordtype">float</span> totalSA = (2.f * (d.<a class="code" href="classVector.html#ca49165049a1e21ae47afcfc078819ed">x</a>*d.<a class="code" href="classVector.html#81be9102fca6d9beea3efef522c4c09d">y</a> + d.<a class="code" href="classVector.html#ca49165049a1e21ae47afcfc078819ed">x</a>*d.<a class="code" href="classVector.html#0e84237d0830d5c459bfa5676b5fbfba">z</a> + d.<a class="code" href="classVector.html#81be9102fca6d9beea3efef522c4c09d">y</a>*d.<a class="code" href="classVector.html#0e84237d0830d5c459bfa5676b5fbfba">z</a>));
<a name="l00230"></a>00230         <span class="keywordtype">float</span> invTotalSA = 1.f / totalSA;
<a name="l00231"></a>00231         <span class="comment">// Choose which axis to split along</span>
<a name="l00232"></a>00232         <span class="keywordtype">int</span> axis;
<a name="l00233"></a>00233         <span class="keywordflow">if</span> (d.<a class="code" href="classVector.html#ca49165049a1e21ae47afcfc078819ed">x</a> &gt; d.<a class="code" href="classVector.html#81be9102fca6d9beea3efef522c4c09d">y</a> &amp;&amp; d.<a class="code" href="classVector.html#ca49165049a1e21ae47afcfc078819ed">x</a> &gt; d.<a class="code" href="classVector.html#0e84237d0830d5c459bfa5676b5fbfba">z</a>) axis = 0;
<a name="l00234"></a>00234         <span class="keywordflow">else</span> axis = (d.<a class="code" href="classVector.html#81be9102fca6d9beea3efef522c4c09d">y</a> &gt; d.<a class="code" href="classVector.html#0e84237d0830d5c459bfa5676b5fbfba">z</a>) ? 1 : 2;
<a name="l00235"></a>00235         <span class="keywordtype">int</span> retries = 0;
<a name="l00236"></a>00236         retrySplit:
<a name="l00237"></a>00237         <span class="comment">// Initialize edges for _axis_</span>
<a name="l00238"></a>00238         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; nPrims; ++i) {
<a name="l00239"></a>00239                 <span class="keywordtype">int</span> pn = primNums[i];
<a name="l00240"></a>00240                 <span class="keyword">const</span> <a class="code" href="classBBox.html">BBox</a> &amp;bbox = allPrimBounds[pn];
<a name="l00241"></a>00241                 edges[axis][2*i] =
<a name="l00242"></a>00242                     <a class="code" href="structBoundEdge.html">BoundEdge</a>(bbox.<a class="code" href="classBBox.html#6efc252ac04a7236369d0ebdc11dab4c">pMin</a>[axis], pn, <span class="keyword">true</span>);
<a name="l00243"></a>00243                 edges[axis][2*i+1] =
<a name="l00244"></a>00244                         <a class="code" href="structBoundEdge.html">BoundEdge</a>(bbox.<a class="code" href="classBBox.html#144894960e2a634983f4d579d7cfc02e">pMax</a>[axis], pn, <span class="keyword">false</span>);
<a name="l00245"></a>00245         }
<a name="l00246"></a>00246         sort(&amp;edges[axis][0], &amp;edges[axis][2*nPrims]);
<a name="l00247"></a>00247         <span class="comment">// Compute cost of all splits for _axis_ to find best</span>
<a name="l00248"></a>00248         <span class="keywordtype">int</span> nBelow = 0, nAbove = nPrims;
<a name="l00249"></a>00249         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; 2*nPrims; ++i) {
<a name="l00250"></a>00250                 <span class="keywordflow">if</span> (edges[axis][i].type == <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80f376ce9156fc010604ed569d04ac9e688">BoundEdge::END</a>) --nAbove;
<a name="l00251"></a>00251                 <span class="keywordtype">float</span> edget = edges[axis][i].<a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a>;
<a name="l00252"></a>00252                 <span class="keywordflow">if</span> (edget &gt; nodeBounds.<a class="code" href="classBBox.html#6efc252ac04a7236369d0ebdc11dab4c">pMin</a>[axis] &amp;&amp;
<a name="l00253"></a>00253                         edget &lt; nodeBounds.<a class="code" href="classBBox.html#144894960e2a634983f4d579d7cfc02e">pMax</a>[axis]) {
<a name="l00254"></a>00254                         <span class="comment">// Compute cost for split at _i_th edge</span>
<a name="l00255"></a>00255                         <span class="keywordtype">int</span> otherAxis[3][2] = { {1,2}, {0,2}, {0,1} };
<a name="l00256"></a>00256                         <span class="keywordtype">int</span> otherAxis0 = otherAxis[axis][0];
<a name="l00257"></a>00257                         <span class="keywordtype">int</span> otherAxis1 = otherAxis[axis][1];
<a name="l00258"></a>00258                         <span class="keywordtype">float</span> belowSA = 2 * (d[otherAxis0] * d[otherAxis1] +
<a name="l00259"></a>00259                                                 (edget - nodeBounds.<a class="code" href="classBBox.html#6efc252ac04a7236369d0ebdc11dab4c">pMin</a>[axis]) *
<a name="l00260"></a>00260                                                 (d[otherAxis0] + d[otherAxis1]));
<a name="l00261"></a>00261                         <span class="keywordtype">float</span> aboveSA = 2 * (d[otherAxis0] * d[otherAxis1] +
<a name="l00262"></a>00262                                                                 (nodeBounds.<a class="code" href="classBBox.html#144894960e2a634983f4d579d7cfc02e">pMax</a>[axis] - edget) *
<a name="l00263"></a>00263                                                                 (d[otherAxis0] + d[otherAxis1]));
<a name="l00264"></a>00264                         <span class="keywordtype">float</span> pBelow = belowSA * invTotalSA;
<a name="l00265"></a>00265                         <span class="keywordtype">float</span> pAbove = aboveSA * invTotalSA;
<a name="l00266"></a>00266                         <span class="keywordtype">float</span> eb = (nAbove == 0 || nBelow == 0) ? <a class="code" href="classKdTreeAccel.html#7c30ec030e0340a801858bb6eb698d29">emptyBonus</a> : 0.f;
<a name="l00267"></a>00267                         <span class="keywordtype">float</span> cost = <a class="code" href="classKdTreeAccel.html#96d40a7cb14257932f589642862a72c5">traversalCost</a> + <a class="code" href="classKdTreeAccel.html#5812c41fd50653c6331044d1989af185">isectCost</a> * (1.f - eb) *
<a name="l00268"></a>00268                                 (pBelow * nBelow + pAbove * nAbove);
<a name="l00269"></a>00269                         <span class="comment">// Update best split if this is lowest cost so far</span>
<a name="l00270"></a>00270                         <span class="keywordflow">if</span> (cost &lt; bestCost)  {
<a name="l00271"></a>00271                                 bestCost = cost;
<a name="l00272"></a>00272                                 bestAxis = axis;
<a name="l00273"></a>00273                                 bestOffset = i;
<a name="l00274"></a>00274                         }
<a name="l00275"></a>00275                 }
<a name="l00276"></a>00276                 <span class="keywordflow">if</span> (edges[axis][i].type == <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80fad2c2d42b8b6d0315dd46136b45305de">BoundEdge::START</a>) ++nBelow;
<a name="l00277"></a>00277         }
<a name="l00278"></a>00278         <a class="code" href="pbrt_8h.html#ab1e54dcc40192f9704e8b252635450f">Assert</a>(nBelow == nPrims &amp;&amp; nAbove == 0); <span class="comment">// NOBOOK</span>
<a name="l00279"></a>00279         <span class="comment">// Create leaf if no good splits were found</span>
<a name="l00280"></a>00280         <span class="keywordflow">if</span> (bestAxis == -1 &amp;&amp; retries &lt; 2) {
<a name="l00281"></a>00281                 ++retries;
<a name="l00282"></a>00282                 axis = (axis+1) % 3;
<a name="l00283"></a>00283                 <span class="keywordflow">goto</span> retrySplit;
<a name="l00284"></a>00284         }
<a name="l00285"></a>00285         <span class="keywordflow">if</span> (bestCost &gt; oldCost) ++badRefines;
<a name="l00286"></a>00286         <span class="keywordflow">if</span> ((bestCost &gt; 4.f * oldCost &amp;&amp; nPrims &lt; 16) ||
<a name="l00287"></a>00287                 bestAxis == -1 || badRefines == 3) {
<a name="l00288"></a>00288                 <a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[nodeNum].<a class="code" href="structKdAccelNode.html#6fc2201c22f04f078707674e8a410c05">initLeaf</a>(primNums, nPrims,
<a name="l00289"></a>00289                                      <a class="code" href="classKdTreeAccel.html#370ba74787694e005d73857a6eea00ad">mailboxPrims</a>, <a class="code" href="classKdTreeAccel.html#517b3a08d6596893b29f72e22e221016">arena</a>);
<a name="l00290"></a>00290                 <span class="keywordflow">return</span>;
<a name="l00291"></a>00291         }
<a name="l00292"></a>00292         <span class="comment">// Classify primitives with respect to split</span>
<a name="l00293"></a>00293         <span class="keywordtype">int</span> n0 = 0, n1 = 0;
<a name="l00294"></a>00294         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; bestOffset; ++i)
<a name="l00295"></a>00295                 <span class="keywordflow">if</span> (edges[bestAxis][i].type == <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80fad2c2d42b8b6d0315dd46136b45305de">BoundEdge::START</a>)
<a name="l00296"></a>00296                         prims0[n0++] = edges[bestAxis][i].<a class="code" href="structBoundEdge.html#fc3ae70ceb7900b2ebecef81eb2644a9">primNum</a>;
<a name="l00297"></a>00297         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = bestOffset+1; i &lt; 2*nPrims; ++i)
<a name="l00298"></a>00298                 <span class="keywordflow">if</span> (edges[bestAxis][i].type == <a class="code" href="structBoundEdge.html#d45783d2344d9863442d396b21e0a80f376ce9156fc010604ed569d04ac9e688">BoundEdge::END</a>)
<a name="l00299"></a>00299                         prims1[n1++] = edges[bestAxis][i].<a class="code" href="structBoundEdge.html#fc3ae70ceb7900b2ebecef81eb2644a9">primNum</a>;
<a name="l00300"></a>00300         <span class="comment">// Recursively initialize children nodes</span>
<a name="l00301"></a>00301         <span class="keywordtype">float</span> tsplit = edges[bestAxis][bestOffset].<a class="code" href="structBoundEdge.html#8b7dafeb2032e73ac74be960741cd743">t</a>;
<a name="l00302"></a>00302         <a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[nodeNum].<a class="code" href="structKdAccelNode.html#41d3268a638d7635f2301cd26742668b">initInterior</a>(bestAxis, tsplit);
<a name="l00303"></a>00303         <a class="code" href="classBBox.html">BBox</a> bounds0 = nodeBounds, bounds1 = nodeBounds;
<a name="l00304"></a>00304         bounds0.<a class="code" href="classBBox.html#144894960e2a634983f4d579d7cfc02e">pMax</a>[bestAxis] = bounds1.pMin[bestAxis] = tsplit;
<a name="l00305"></a>00305         <a class="code" href="classKdTreeAccel.html#081525774974a4d860f28488cd5285c7">buildTree</a>(nodeNum+1, bounds0,
<a name="l00306"></a>00306                 allPrimBounds, prims0, n0, depth-1, edges,
<a name="l00307"></a>00307                 prims0, prims1 + nPrims, badRefines);
<a name="l00308"></a>00308         <a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[nodeNum].<a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">aboveChild</a> = <a class="code" href="classKdTreeAccel.html#75f5d9821e52aec562ea653e5c4d8ebd">nextFreeNode</a>;
<a name="l00309"></a>00309         <a class="code" href="classKdTreeAccel.html#081525774974a4d860f28488cd5285c7">buildTree</a>(<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[nodeNum].aboveChild, bounds1, allPrimBounds,
<a name="l00310"></a>00310                 prims1, n1, depth-1, edges,
<a name="l00311"></a>00311                 prims0, prims1 + nPrims, badRefines);
<a name="l00312"></a>00312 }
<a name="l00313"></a><a class="code" href="classKdTreeAccel.html#3e6620d44766ad36a06c2515c73c3f94">00313</a> <span class="keywordtype">bool</span> <a class="code" href="classKdTreeAccel.html#3e6620d44766ad36a06c2515c73c3f94">KdTreeAccel::Intersect</a>(<span class="keyword">const</span> <a class="code" href="classRay.html">Ray</a> &amp;ray,
<a name="l00314"></a>00314                 <a class="code" href="structIntersection.html">Intersection</a> *isect)<span class="keyword"> const </span>{
<a name="l00315"></a>00315         <span class="comment">// Compute initial parametric range of ray inside kd-tree extent</span>
<a name="l00316"></a>00316         <span class="keywordtype">float</span> tmin, tmax;
<a name="l00317"></a>00317         <span class="keywordflow">if</span> (!<a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>.<a class="code" href="classBBox.html#4415e7f6ce6461eacdeebd7869a84066">IntersectP</a>(ray, &amp;tmin, &amp;tmax))
<a name="l00318"></a>00318                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00319"></a>00319         <span class="comment">// Prepare to traverse kd-tree for ray</span>
<a name="l00320"></a>00320         <span class="keywordtype">int</span> rayId = <a class="code" href="classKdTreeAccel.html#f75252a3070a8413f49147c8340c65a8">curMailboxId</a>++;
<a name="l00321"></a>00321         <a class="code" href="classVector.html">Vector</a> invDir(1.f/ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>.<a class="code" href="classVector.html#ca49165049a1e21ae47afcfc078819ed">x</a>, 1.f/ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>.<a class="code" href="classVector.html#81be9102fca6d9beea3efef522c4c09d">y</a>, 1.f/ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>.<a class="code" href="classVector.html#0e84237d0830d5c459bfa5676b5fbfba">z</a>);
<a name="l00322"></a>00322 <span class="preprocessor">        #define MAX_TODO 64</span>
<a name="l00323"></a>00323 <span class="preprocessor"></span>        <a class="code" href="structKdToDo.html">KdToDo</a> todo[<a class="code" href="kdtree_8cpp.html#0392e4b1ac8ed28fc3991862cc4b47ef">MAX_TODO</a>];
<a name="l00324"></a>00324         <span class="keywordtype">int</span> todoPos = 0;
<a name="l00325"></a>00325         <span class="comment">// Traverse kd-tree nodes in order for ray</span>
<a name="l00326"></a>00326         <span class="keywordtype">bool</span> hit = <span class="keyword">false</span>;
<a name="l00327"></a>00327         <span class="keyword">const</span> <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *node = &amp;<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[0];
<a name="l00328"></a>00328         <span class="keywordflow">while</span> (node != NULL) {
<a name="l00329"></a>00329                 <span class="comment">// Bail out if we found a hit closer than the current node</span>
<a name="l00330"></a>00330                 <span class="keywordflow">if</span> (ray.<a class="code" href="classRay.html#aa6c29ceae8edc5c9d37e879daa1557a">maxt</a> &lt; tmin) <span class="keywordflow">break</span>;
<a name="l00331"></a>00331                 <span class="comment">//static StatsCounter nodesTraversed("Kd-Tree Accelerator", //NOBOOK</span>
<a name="l00332"></a>00332                 <span class="comment">//      "Number of kd-tree nodes traversed by normal rays"); //NOBOOK</span>
<a name="l00333"></a>00333                 <span class="comment">//++nodesTraversed; //NOBOOK</span>
<a name="l00334"></a>00334                 <span class="keywordflow">if</span> (!node-&gt;<a class="code" href="structKdAccelNode.html#2dd55e7aebd0c6cc67403e33b92d103e">IsLeaf</a>()) {
<a name="l00335"></a>00335                         <span class="comment">// Process kd-tree interior node</span>
<a name="l00336"></a>00336                         <span class="comment">// Compute parametric distance along ray to split plane</span>
<a name="l00337"></a>00337                         <span class="keywordtype">int</span> axis = node-&gt;<a class="code" href="structKdAccelNode.html#3bf5999b06774527309b3220644dd5d9">SplitAxis</a>();
<a name="l00338"></a>00338                         <span class="keywordtype">float</span> tplane = (node-&gt;<a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>() - ray.<a class="code" href="classRay.html#1014d000992e8ac3b92f150ad2a5cffe">o</a>[axis]) *
<a name="l00339"></a>00339                                 invDir[axis];
<a name="l00340"></a>00340                         <span class="comment">// Get node children pointers for ray</span>
<a name="l00341"></a>00341                         <span class="keyword">const</span> <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *firstChild, *secondChild;
<a name="l00342"></a>00342                         <span class="keywordtype">int</span> belowFirst = (ray.<a class="code" href="classRay.html#1014d000992e8ac3b92f150ad2a5cffe">o</a>[axis] &lt;= node-&gt;<a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>()) ||
<a name="l00343"></a>00343                                          (ray.<a class="code" href="classRay.html#1014d000992e8ac3b92f150ad2a5cffe">o</a>[axis] == node-&gt;<a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>() &amp;&amp; ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>[axis] &lt; 0);
<a name="l00344"></a>00344                         <span class="keywordflow">if</span> (belowFirst) {
<a name="l00345"></a>00345                                 firstChild = node + 1;
<a name="l00346"></a>00346                                 secondChild = &amp;<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[node-&gt;<a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">aboveChild</a>];
<a name="l00347"></a>00347                         }
<a name="l00348"></a>00348                         <span class="keywordflow">else</span> {
<a name="l00349"></a>00349                                 firstChild = &amp;<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[node-&gt;<a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">aboveChild</a>];
<a name="l00350"></a>00350                                 secondChild = node + 1;
<a name="l00351"></a>00351                         }
<a name="l00352"></a>00352                         <span class="comment">// Advance to next child node, possibly enqueue other child</span>
<a name="l00353"></a>00353                         <span class="keywordflow">if</span> (tplane &gt; tmax || tplane &lt;= 0)
<a name="l00354"></a>00354                                 node = firstChild;
<a name="l00355"></a>00355                         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (tplane &lt; tmin)
<a name="l00356"></a>00356                                 node = secondChild;
<a name="l00357"></a>00357                         <span class="keywordflow">else</span> {
<a name="l00358"></a>00358                                 <span class="comment">// Enqueue _secondChild_ in todo list</span>
<a name="l00359"></a>00359                                 todo[todoPos].<a class="code" href="structKdToDo.html#b481373c1ed09adca53e1c5004d2e83f">node</a> = secondChild;
<a name="l00360"></a>00360                                 todo[todoPos].<a class="code" href="structKdToDo.html#697d1bb71b5168c10372863f422df3fa">tmin</a> = tplane;
<a name="l00361"></a>00361                                 todo[todoPos].<a class="code" href="structKdToDo.html#8634eadf7b2289a771626a3aecc8fe12">tmax</a> = tmax;
<a name="l00362"></a>00362                                 ++todoPos;
<a name="l00363"></a>00363                                 node = firstChild;
<a name="l00364"></a>00364                                 tmax = tplane;
<a name="l00365"></a>00365                         }
<a name="l00366"></a>00366                 }
<a name="l00367"></a>00367                 <span class="keywordflow">else</span> {
<a name="l00368"></a>00368                         <span class="comment">// Check for intersections inside leaf node</span>
<a name="l00369"></a>00369                         <a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> nPrimitives = node-&gt;<a class="code" href="structKdAccelNode.html#130aad6aa2dc153a1e2ffacd45e44494">nPrimitives</a>();
<a name="l00370"></a>00370                         <span class="keywordflow">if</span> (nPrimitives == 1) {
<a name="l00371"></a>00371                                 <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *mp = node-&gt;<a class="code" href="structKdAccelNode.html#9321fe66117c7a99121db94cb77995ba">onePrimitive</a>;
<a name="l00372"></a>00372                                 <span class="comment">// Check one primitive inside leaf node</span>
<a name="l00373"></a>00373                                 <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> != rayId) {
<a name="l00374"></a>00374                                         mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> = rayId;
<a name="l00375"></a>00375                                         <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#6f38bbe89d239a2b92311f292ee3063a">primitive</a>-&gt;Intersect(ray, isect))
<a name="l00376"></a>00376                                                 hit = <span class="keyword">true</span>;
<a name="l00377"></a>00377                                 }
<a name="l00378"></a>00378                         }
<a name="l00379"></a>00379                         <span class="keywordflow">else</span> {
<a name="l00380"></a>00380                                 <a class="code" href="structMailboxPrim.html">MailboxPrim</a> **prims = node-&gt;<a class="code" href="structKdAccelNode.html#e63025f82b0ddee781b570123bfc52c8">primitives</a>;
<a name="l00381"></a>00381                                 <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; nPrimitives; ++i) {
<a name="l00382"></a>00382                                         <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *mp = prims[i];
<a name="l00383"></a>00383                                         <span class="comment">// Check one primitive inside leaf node</span>
<a name="l00384"></a>00384                                         <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> != rayId) {
<a name="l00385"></a>00385                                                 mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> = rayId;
<a name="l00386"></a>00386                                                 <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#6f38bbe89d239a2b92311f292ee3063a">primitive</a>-&gt;Intersect(ray, isect))
<a name="l00387"></a>00387                                                         hit = <span class="keyword">true</span>;
<a name="l00388"></a>00388                                         }
<a name="l00389"></a>00389                                 }
<a name="l00390"></a>00390                         }
<a name="l00391"></a>00391                         <span class="comment">// Grab next node to process from todo list</span>
<a name="l00392"></a>00392                         <span class="keywordflow">if</span> (todoPos &gt; 0) {
<a name="l00393"></a>00393                                 --todoPos;
<a name="l00394"></a>00394                                 node = todo[todoPos].<a class="code" href="structKdToDo.html#b481373c1ed09adca53e1c5004d2e83f">node</a>;
<a name="l00395"></a>00395                                 tmin = todo[todoPos].<a class="code" href="structKdToDo.html#697d1bb71b5168c10372863f422df3fa">tmin</a>;
<a name="l00396"></a>00396                                 tmax = todo[todoPos].<a class="code" href="structKdToDo.html#8634eadf7b2289a771626a3aecc8fe12">tmax</a>;
<a name="l00397"></a>00397                         }
<a name="l00398"></a>00398                         <span class="keywordflow">else</span>
<a name="l00399"></a>00399                                 <span class="keywordflow">break</span>;
<a name="l00400"></a>00400                 }
<a name="l00401"></a>00401         }
<a name="l00402"></a>00402         <span class="keywordflow">return</span> hit;
<a name="l00403"></a>00403 }
<a name="l00404"></a><a class="code" href="classKdTreeAccel.html#7c038872df7027e0f0d7be0d1108bb66">00404</a> <span class="keywordtype">bool</span> <a class="code" href="classKdTreeAccel.html#7c038872df7027e0f0d7be0d1108bb66">KdTreeAccel::IntersectP</a>(<span class="keyword">const</span> <a class="code" href="classRay.html">Ray</a> &amp;ray)<span class="keyword"> const </span>{
<a name="l00405"></a>00405         <span class="comment">// Compute initial parametric range of ray inside kd-tree extent</span>
<a name="l00406"></a>00406         <span class="keywordtype">float</span> tmin, tmax;
<a name="l00407"></a>00407         <span class="keywordflow">if</span> (!<a class="code" href="classKdTreeAccel.html#fbd463cb613f2aeea736a66bd970d00d">bounds</a>.<a class="code" href="classBBox.html#4415e7f6ce6461eacdeebd7869a84066">IntersectP</a>(ray, &amp;tmin, &amp;tmax))
<a name="l00408"></a>00408                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00409"></a>00409         <span class="comment">// Prepare to traverse kd-tree for ray</span>
<a name="l00410"></a>00410         <span class="keywordtype">int</span> rayId = <a class="code" href="classKdTreeAccel.html#f75252a3070a8413f49147c8340c65a8">curMailboxId</a>++;
<a name="l00411"></a>00411         <a class="code" href="classVector.html">Vector</a> invDir(1.f/ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>.<a class="code" href="classVector.html#ca49165049a1e21ae47afcfc078819ed">x</a>, 1.f/ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>.<a class="code" href="classVector.html#81be9102fca6d9beea3efef522c4c09d">y</a>, 1.f/ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>.<a class="code" href="classVector.html#0e84237d0830d5c459bfa5676b5fbfba">z</a>);
<a name="l00412"></a>00412 <span class="preprocessor">        #define MAX_TODO 64</span>
<a name="l00413"></a>00413 <span class="preprocessor"></span>        <a class="code" href="structKdToDo.html">KdToDo</a> todo[<a class="code" href="kdtree_8cpp.html#0392e4b1ac8ed28fc3991862cc4b47ef">MAX_TODO</a>];
<a name="l00414"></a>00414         <span class="keywordtype">int</span> todoPos = 0;
<a name="l00415"></a>00415         <span class="keyword">const</span> <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *node = &amp;<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[0];
<a name="l00416"></a>00416         <span class="keywordflow">while</span> (node != NULL) {
<a name="l00417"></a>00417                 <span class="comment">// Update kd-tree shadow ray traversal statistics</span>
<a name="l00418"></a>00418                 <span class="comment">//static StatsCounter nodesTraversed("Kd-Tree Accelerator",</span>
<a name="l00419"></a>00419                 <span class="comment">//      "Number of kd-tree nodes traversed by shadow rays");</span>
<a name="l00420"></a>00420                 <span class="comment">//++nodesTraversed;</span>
<a name="l00421"></a>00421                 <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structKdAccelNode.html#2dd55e7aebd0c6cc67403e33b92d103e">IsLeaf</a>()) {
<a name="l00422"></a>00422                         <span class="comment">// Check for shadow ray intersections inside leaf node</span>
<a name="l00423"></a>00423                         <a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> nPrimitives = node-&gt;<a class="code" href="structKdAccelNode.html#130aad6aa2dc153a1e2ffacd45e44494">nPrimitives</a>();
<a name="l00424"></a>00424                         <span class="keywordflow">if</span> (nPrimitives == 1) {
<a name="l00425"></a>00425                                 <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *mp = node-&gt;<a class="code" href="structKdAccelNode.html#9321fe66117c7a99121db94cb77995ba">onePrimitive</a>;
<a name="l00426"></a>00426                                 <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> != rayId) {
<a name="l00427"></a>00427                                         mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> = rayId;
<a name="l00428"></a>00428                                         <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#6f38bbe89d239a2b92311f292ee3063a">primitive</a>-&gt;IntersectP(ray))
<a name="l00429"></a>00429                                                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00430"></a>00430                                 }
<a name="l00431"></a>00431                         }
<a name="l00432"></a>00432                         <span class="keywordflow">else</span> {
<a name="l00433"></a>00433                                 <a class="code" href="structMailboxPrim.html">MailboxPrim</a> **prims = node-&gt;<a class="code" href="structKdAccelNode.html#e63025f82b0ddee781b570123bfc52c8">primitives</a>;
<a name="l00434"></a>00434                                 <span class="keywordflow">for</span> (<a class="code" href="pbrt_8h.html#c319c165d52643e43249fe003e18bdf3">u_int</a> i = 0; i &lt; nPrimitives; ++i) {
<a name="l00435"></a>00435                                         <a class="code" href="structMailboxPrim.html">MailboxPrim</a> *mp = prims[i];
<a name="l00436"></a>00436                                         <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> != rayId) {
<a name="l00437"></a>00437                                                 mp-&gt;<a class="code" href="structMailboxPrim.html#443b48b82d6f6f6e1e88202ea871e3fc">lastMailboxId</a> = rayId;
<a name="l00438"></a>00438                                                 <span class="keywordflow">if</span> (mp-&gt;<a class="code" href="structMailboxPrim.html#6f38bbe89d239a2b92311f292ee3063a">primitive</a>-&gt;IntersectP(ray))
<a name="l00439"></a>00439                                                         <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00440"></a>00440                                         }
<a name="l00441"></a>00441                                 }
<a name="l00442"></a>00442                         }
<a name="l00443"></a>00443                         <span class="comment">// Grab next node to process from todo list</span>
<a name="l00444"></a>00444                         <span class="keywordflow">if</span> (todoPos &gt; 0) {
<a name="l00445"></a>00445                                 --todoPos;
<a name="l00446"></a>00446                                 node = todo[todoPos].<a class="code" href="structKdToDo.html#b481373c1ed09adca53e1c5004d2e83f">node</a>;
<a name="l00447"></a>00447                                 tmin = todo[todoPos].<a class="code" href="structKdToDo.html#697d1bb71b5168c10372863f422df3fa">tmin</a>;
<a name="l00448"></a>00448                                 tmax = todo[todoPos].<a class="code" href="structKdToDo.html#8634eadf7b2289a771626a3aecc8fe12">tmax</a>;
<a name="l00449"></a>00449                         }
<a name="l00450"></a>00450                         <span class="keywordflow">else</span>
<a name="l00451"></a>00451                                 <span class="keywordflow">break</span>;
<a name="l00452"></a>00452                 }
<a name="l00453"></a>00453                 <span class="keywordflow">else</span> {
<a name="l00454"></a>00454                         <span class="comment">// Process kd-tree interior node</span>
<a name="l00455"></a>00455                         <span class="comment">// Compute parametric distance along ray to split plane</span>
<a name="l00456"></a>00456                         <span class="keywordtype">int</span> axis = node-&gt;<a class="code" href="structKdAccelNode.html#3bf5999b06774527309b3220644dd5d9">SplitAxis</a>();
<a name="l00457"></a>00457                         <span class="keywordtype">float</span> tplane = (node-&gt;<a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>() - ray.<a class="code" href="classRay.html#1014d000992e8ac3b92f150ad2a5cffe">o</a>[axis]) *
<a name="l00458"></a>00458                                 invDir[axis];
<a name="l00459"></a>00459                         <span class="comment">// Get node children pointers for ray</span>
<a name="l00460"></a>00460                         <span class="keyword">const</span> <a class="code" href="structKdAccelNode.html">KdAccelNode</a> *firstChild, *secondChild;
<a name="l00461"></a>00461                         <span class="keywordtype">int</span> belowFirst = (ray.<a class="code" href="classRay.html#1014d000992e8ac3b92f150ad2a5cffe">o</a>[axis] &lt;= node-&gt;<a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>()) ||
<a name="l00462"></a>00462                                          (ray.<a class="code" href="classRay.html#1014d000992e8ac3b92f150ad2a5cffe">o</a>[axis] == node-&gt;<a class="code" href="structKdAccelNode.html#d5916c3eb801ce741724798665b22d13">SplitPos</a>() &amp;&amp; ray.<a class="code" href="classRay.html#5bbfc94e178e0a050b51200acc579069">d</a>[axis] &lt; 0);
<a name="l00463"></a>00463                         <span class="keywordflow">if</span> (belowFirst) {
<a name="l00464"></a>00464                                 firstChild = node + 1;
<a name="l00465"></a>00465                                 secondChild = &amp;<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[node-&gt;<a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">aboveChild</a>];
<a name="l00466"></a>00466                         }
<a name="l00467"></a>00467                         <span class="keywordflow">else</span> {
<a name="l00468"></a>00468                                 firstChild = &amp;<a class="code" href="classKdTreeAccel.html#4108d382bc382c763d482c63cbf8361e">nodes</a>[node-&gt;<a class="code" href="structKdAccelNode.html#c6e9c0bb4a3b45dec3cce6ff0de5d493">aboveChild</a>];
<a name="l00469"></a>00469                                 secondChild = node + 1;
<a name="l00470"></a>00470                         }
<a name="l00471"></a>00471                         <span class="comment">// Advance to next child node, possibly enqueue other child</span>
<a name="l00472"></a>00472                         <span class="keywordflow">if</span> (tplane &gt; tmax || tplane &lt;= 0)
<a name="l00473"></a>00473                                 node = firstChild;
<a name="l00474"></a>00474                         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (tplane &lt; tmin)
<a name="l00475"></a>00475                                 node = secondChild;
<a name="l00476"></a>00476                         <span class="keywordflow">else</span> {
<a name="l00477"></a>00477                                 <span class="comment">// Enqueue _secondChild_ in todo list</span>
<a name="l00478"></a>00478                                 todo[todoPos].<a class="code" href="structKdToDo.html#b481373c1ed09adca53e1c5004d2e83f">node</a> = secondChild;
<a name="l00479"></a>00479                                 todo[todoPos].<a class="code" href="structKdToDo.html#697d1bb71b5168c10372863f422df3fa">tmin</a> = tplane;
<a name="l00480"></a>00480                                 todo[todoPos].<a class="code" href="structKdToDo.html#8634eadf7b2289a771626a3aecc8fe12">tmax</a> = tmax;
<a name="l00481"></a>00481                                 ++todoPos;
<a name="l00482"></a>00482                                 node = firstChild;
<a name="l00483"></a>00483                                 tmax = tplane;
<a name="l00484"></a>00484                         }
<a name="l00485"></a>00485                 }
<a name="l00486"></a>00486         }
<a name="l00487"></a>00487         <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00488"></a>00488 }
<a name="l00489"></a><a class="code" href="kdtree_8cpp.html#b562ac30bc85db4c70f213b50ea5f2b8">00489</a> <span class="keyword">extern</span> <span class="stringliteral">"C"</span> <a class="code" href="pbrt_8h.html#808e08638be3cba36e36759e5b150de0">DLLEXPORT</a> <a class="code" href="classPrimitive.html">Primitive</a> *<a class="code" href="grid_8cpp.html#b562ac30bc85db4c70f213b50ea5f2b8">CreateAccelerator</a>(<span class="keyword">const</span> vector&lt;<a class="code" href="classReference.html">Reference&lt;Primitive&gt;</a> &gt; &amp;prims,
<a name="l00490"></a>00490                 <span class="keyword">const</span> <a class="code" href="classParamSet.html">ParamSet</a> &amp;ps) {
<a name="l00491"></a>00491         <span class="keywordtype">int</span> <a class="code" href="classKdTreeAccel.html#5812c41fd50653c6331044d1989af185">isectCost</a> = ps.<a class="code" href="classParamSet.html#23f24db9c46375e33764910c4fa999d5">FindOneInt</a>(<span class="stringliteral">"intersectcost"</span>, 80);
<a name="l00492"></a>00492         <span class="keywordtype">int</span> travCost = ps.<a class="code" href="classParamSet.html#23f24db9c46375e33764910c4fa999d5">FindOneInt</a>(<span class="stringliteral">"traversalcost"</span>, 1);
<a name="l00493"></a>00493         <span class="keywordtype">float</span> <a class="code" href="classKdTreeAccel.html#7c30ec030e0340a801858bb6eb698d29">emptyBonus</a> = ps.<a class="code" href="classParamSet.html#87143fd8e73a75082179a110d42531a4">FindOneFloat</a>(<span class="stringliteral">"emptybonus"</span>, 0.5f);
<a name="l00494"></a>00494         <span class="keywordtype">int</span> <a class="code" href="classKdTreeAccel.html#7402fb2d0d5763961bc8c82acbe91f3a">maxPrims</a> = ps.<a class="code" href="classParamSet.html#23f24db9c46375e33764910c4fa999d5">FindOneInt</a>(<span class="stringliteral">"maxprims"</span>, 1);
<a name="l00495"></a>00495         <span class="keywordtype">int</span> maxDepth = ps.<a class="code" href="classParamSet.html#23f24db9c46375e33764910c4fa999d5">FindOneInt</a>(<span class="stringliteral">"maxdepth"</span>, -1);
<a name="l00496"></a>00496         <span class="keywordflow">return</span> <span class="keyword">new</span> <a class="code" href="classKdTreeAccel.html#62f9a15970262e8b316e35fcab2956e4">KdTreeAccel</a>(prims, isectCost, travCost,
<a name="l00497"></a>00497                 emptyBonus, maxPrims, maxDepth);
<a name="l00498"></a>00498 }
</pre></div></div>
<hr size="1"><address style="text-align: right;"><small>Generated on Mon Jul 20 17:31:53 2009 for pbrt by&nbsp;
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.6 </small></address>
</body>
</html>