source: Documentation/D5.3 Stand-alone computation package for illumination algorithms/appendix/pathmap/html/class_k_d_tree.html @ 2910

Revision 2910, 22.7 KB checked in by hbeneit, 16 years ago (diff)
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
3<title>Path Map Module: KDTree Class Reference</title>
4<link href="doxygen.css" rel="stylesheet" type="text/css">
5<link href="tabs.css" rel="stylesheet" type="text/css">
6</head><body>
7<!-- Generated by Doxygen 1.4.6-NO -->
8<div class="tabs">
9  <ul>
10    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
11    <li id="current"><a href="annotated.html"><span>Classes</span></a></li>
12  </ul></div>
13<div class="tabs">
14  <ul>
15    <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
16    <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
17    <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
18  </ul></div>
19<h1>KDTree Class Reference</h1><!-- doxytag: class="KDTree" --><a href="class_k_d_tree-members.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
20<tr><td></td></tr>
21<tr><td colspan="2"><br><h2>Private Member Functions</h2></td></tr>
22<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#87fed42fc407cd3b3fc48f817363b086">deleteLeaves</a> (unsigned int nodeID)</td></tr>
23
24<tr><td class="memItemLeft" nowrap align="right" valign="top">void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#76bcd994d6db73c97c31b326d3aca351">build</a> (unsigned int nodeID, unsigned int *boundsArray, unsigned int <a class="el" href="class_k_d_tree.html#41cda43f0503d8747cffeef2a5738621">nObjects</a>, BoundingBox &amp;limits, unsigned char axisNmask)</td></tr>
25
26<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">recursive algorithm to build the tree bits 1,0 identify cut axis to be used  <a href="#76bcd994d6db73c97c31b326d3aca351"></a><br></td></tr>
27<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="3af297547b85ab7f81ae4f10f6f8e98f"></a><!-- doxytag: member="KDTree::quickSort" ref="3af297547b85ab7f81ae4f10f6f8e98f" args="(unsigned int *lo0, unsigned int *hi0, unsigned char axis)" -->
28void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#3af297547b85ab7f81ae4f10f6f8e98f">quickSort</a> (unsigned int *lo0, unsigned int *hi0, unsigned char axis)</td></tr>
29
30<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">qSort an array segment of object extremes <br></td></tr>
31<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#1afbe38e70fc1e48465a05fa990b66b8">compare</a> (unsigned int aIndex, unsigned int bIndex, unsigned char axis)</td></tr>
32
33<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">compare two object extrema according to the coordinate specified  <a href="#1afbe38e70fc1e48465a05fa990b66b8"></a><br></td></tr>
34<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="800b31f66431519be13bf61d878d9095"></a><!-- doxytag: member="KDTree::getBoundValue" ref="800b31f66431519be13bf61d878d9095" args="(unsigned int *extremeIndex, unsigned char axis)" -->
35float&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#800b31f66431519be13bf61d878d9095">getBoundValue</a> (unsigned int *extremeIndex, unsigned char axis)</td></tr>
36
37<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">return the value of the object extreme referenced <br></td></tr>
38<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="105aef624bff8e8a0d228b17dcdb573f"></a><!-- doxytag: member="KDTree::findBound" ref="105aef624bff8e8a0d228b17dcdb573f" args="(unsigned int *extremeArrayStart, unsigned int nBounds, float loc, unsigned char axis)" -->
39unsigned int *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#105aef624bff8e8a0d228b17dcdb573f">findBound</a> (unsigned int *extremeArrayStart, unsigned int nBounds, float loc, unsigned char axis)</td></tr>
40
41<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">binary search: finds the position of value 'loc' in a sorted array partition <br></td></tr>
42<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="ee7d01501f9083d241954169fd629944"></a><!-- doxytag: member="KDTree::isLeaf" ref="ee7d01501f9083d241954169fd629944" args="(unsigned int xnode)" -->
43bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#ee7d01501f9083d241954169fd629944">isLeaf</a> (unsigned int xnode)</td></tr>
44
45<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">tell if a node is a leaf <br></td></tr>
46<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#cd6808333cc2366abd86b9db8ee431a6">followChildren</a> (unsigned int &amp;parent, unsigned int &amp;leftChild, unsigned int &amp;rightChild)</td></tr>
47
48<tr><td class="memItemLeft" nowrap align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#3d68e4e5ea6a01ec90f6fac0206db10b">getFreeNodes</a> (unsigned int parent, unsigned int &amp;leftFree, unsigned int &amp;rightFree)</td></tr>
49
50<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="b68b5752b8f6364d0da738b0712be9b4"></a><!-- doxytag: member="KDTree::createBoundingBox" ref="b68b5752b8f6364d0da738b0712be9b4" args="(Intersectable **iObjects, int nObjects)" -->
51void&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#b68b5752b8f6364d0da738b0712be9b4">createBoundingBox</a> (<a class="el" href="class_intersectable.html">Intersectable</a> **iObjects, int <a class="el" href="class_k_d_tree.html#41cda43f0503d8747cffeef2a5738621">nObjects</a>)</td></tr>
52
53<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">accumulate object extrema <br></td></tr>
54<tr><td class="memItemLeft" nowrap align="right" valign="top">unsigned int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#f6de48530830ab214b595b1d5fa953fa">makePointer</a> (unsigned int originalNode)</td></tr>
55
56<tr><td colspan="2"><br><h2>Private Attributes</h2></td></tr>
57<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="67906a4703fbdf02db9c64cf09558a9e"></a><!-- doxytag: member="KDTree::nCacheLines" ref="67906a4703fbdf02db9c64cf09558a9e" args="" -->
58unsigned int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#67906a4703fbdf02db9c64cf09558a9e">nCacheLines</a></td></tr>
59
60<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">cache line sized memory segments used <br></td></tr>
61<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="c5eca2d0e7180f8d326cedd1a868b522"></a><!-- doxytag: member="KDTree::maxNCacheLines" ref="c5eca2d0e7180f8d326cedd1a868b522" args="" -->
62unsigned int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#c5eca2d0e7180f8d326cedd1a868b522">maxNCacheLines</a></td></tr>
63
64<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">nodes per cache line <br></td></tr>
65<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="debce371c710f1a5c321c78c2698f7ab"></a><!-- doxytag: member="KDTree::nCacheLineNodes" ref="debce371c710f1a5c321c78c2698f7ab" args="" -->
66unsigned int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#debce371c710f1a5c321c78c2698f7ab">nCacheLineNodes</a></td></tr>
67
68<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">nodes per cache line <br></td></tr>
69<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="4df811dc96e1954918fd5d725a2d9d11"></a><!-- doxytag: member="KDTree::nCacheLineBytes" ref="4df811dc96e1954918fd5d725a2d9d11" args="" -->
70unsigned int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#4df811dc96e1954918fd5d725a2d9d11">nCacheLineBytes</a></td></tr>
71
72<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">bytes per cache line <br></td></tr>
73<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="631ac2d9a082e2744fcc035d7f3d91cc"></a><!-- doxytag: member="KDTree::boundingBox" ref="631ac2d9a082e2744fcc035d7f3d91cc" args="" -->
74BoundingBox&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#631ac2d9a082e2744fcc035d7f3d91cc">boundingBox</a></td></tr>
75
76<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">bounding box containing all objects <br></td></tr>
77<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="6cd111151b9938580fbf7d4201d917bd"></a><!-- doxytag: member="KDTree::poolNodeTable" ref="6cd111151b9938580fbf7d4201d917bd" args="" -->
78float *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#6cd111151b9938580fbf7d4201d917bd">poolNodeTable</a></td></tr>
79
80<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">memory allocated for nodes <br></td></tr>
81<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="c42dd9d141c754bf761abbe331a9b962"></a><!-- doxytag: member="KDTree::nodeTable" ref="c42dd9d141c754bf761abbe331a9b962" args="" -->
82float *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#c42dd9d141c754bf761abbe331a9b962">nodeTable</a></td></tr>
83
84<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">array aligned on cache lines <br></td></tr>
85<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="41cda43f0503d8747cffeef2a5738621"></a><!-- doxytag: member="KDTree::nObjects" ref="41cda43f0503d8747cffeef2a5738621" args="" -->
86unsigned int&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#41cda43f0503d8747cffeef2a5738621">nObjects</a></td></tr>
87
88<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight"><a class="el" href="class_k_d_tree.html#44c1da792f9896ac252d552db9cfc08c">objects</a> <br></td></tr>
89<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="44c1da792f9896ac252d552db9cfc08c"></a><!-- doxytag: member="KDTree::objects" ref="44c1da792f9896ac252d552db9cfc08c" args="" -->
90<a class="el" href="class_intersectable.html">Intersectable</a> **&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#44c1da792f9896ac252d552db9cfc08c">objects</a></td></tr>
91
92<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">array objects <br></td></tr>
93<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="ad4e64ac39a548aa6da0ad205e4754e4"></a><!-- doxytag: member="KDTree::freeNodes" ref="ad4e64ac39a548aa6da0ad205e4754e4" args="" -->
94Heap&lt; unsigned int &gt; *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#ad4e64ac39a548aa6da0ad205e4754e4">freeNodes</a></td></tr>
95
96<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">minimum heap to store indices of free nodes during the build <br></td></tr>
97<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="a3f696e96e55fa5bd6529c62c5c92d54"></a><!-- doxytag: member="KDTree::traverseStack" ref="a3f696e96e55fa5bd6529c62c5c92d54" args="" -->
98<a class="el" href="struct_k_d_tree_1_1_traverse_stack.html">KDTree::TraverseStack</a> *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_k_d_tree.html#a3f696e96e55fa5bd6529c62c5c92d54">traverseStack</a></td></tr>
99
100<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">stack to implement the recursive traversal algorithm <br></td></tr>
101<tr><td colspan="2"><br><h2>Classes</h2></td></tr>
102<tr><td class="memItemLeft" nowrap align="right" valign="top">struct &nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_k_d_tree_1_1_traverse_stack.html">TraverseStack</a></td></tr>
103
104<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">stack to implement the recursive traversal algorithm  <a href="struct_k_d_tree_1_1_traverse_stack.html#_details">More...</a><br></td></tr>
105</table>
106<hr><a name="_details"></a><h2>Detailed Description</h2>
107This class implements a kd-tree. Splitting, termination and cutting of empty space is based on cost estimation. Memory representation uses cache-line sized sub-trees and mapping of an unbalanced tree into an array.
108<p>
109<hr><h2>Member Function Documentation</h2>
110<a class="anchor" name="76bcd994d6db73c97c31b326d3aca351"></a><!-- doxytag: member="KDTree::build" ref="76bcd994d6db73c97c31b326d3aca351" args="(unsigned int nodeID, unsigned int *boundsArray, unsigned int nObjects, BoundingBox &amp;limits, unsigned char axisNmask)" --><p>
111<table class="mdTable" cellpadding="2" cellspacing="0">
112  <tr>
113    <td class="mdRow">
114      <table cellpadding="0" cellspacing="0" border="0">
115        <tr>
116          <td class="md" nowrap valign="top">void KDTree::build           </td>
117          <td class="md" valign="top">(&nbsp;</td>
118          <td class="md" nowrap valign="top">unsigned int&nbsp;</td>
119          <td class="mdname" nowrap> <em>nodeID</em>, </td>
120        </tr>
121        <tr>
122          <td class="md" nowrap align="right"></td>
123          <td class="md"></td>
124          <td class="md" nowrap>unsigned int *&nbsp;</td>
125          <td class="mdname" nowrap> <em>boundsArray</em>, </td>
126        </tr>
127        <tr>
128          <td class="md" nowrap align="right"></td>
129          <td class="md"></td>
130          <td class="md" nowrap>unsigned int&nbsp;</td>
131          <td class="mdname" nowrap> <em>nObjects</em>, </td>
132        </tr>
133        <tr>
134          <td class="md" nowrap align="right"></td>
135          <td class="md"></td>
136          <td class="md" nowrap>BoundingBox &amp;&nbsp;</td>
137          <td class="mdname" nowrap> <em>limits</em>, </td>
138        </tr>
139        <tr>
140          <td class="md" nowrap align="right"></td>
141          <td class="md"></td>
142          <td class="md" nowrap>unsigned char&nbsp;</td>
143          <td class="mdname" nowrap> <em>axisNmask</em></td>
144        </tr>
145        <tr>
146          <td class="md"></td>
147          <td class="md">)&nbsp;</td>
148          <td class="md" colspan="2"><code> [private]</code></td>
149        </tr>
150      </table>
151    </td>
152  </tr>
153</table>
154<table cellspacing="5" cellpadding="0" border="0">
155  <tr>
156    <td>
157      &nbsp;
158    </td>
159    <td>
160
161<p>
162recursive algorithm to build the tree bits 1,0 identify cut axis to be used
163<p>
164bits 5,4,3 indicate z,y,x failed cut attempts <dl compact><dt><b>Parameters: </b></dt><dd>
165<table border="0" cellspacing="2" cellpadding="0">
166<tr><td valign="top"><em>nodeID</em>&nbsp;</td><td>
167node index of kd-tree node to be created </td></tr>
168<tr><td valign="top"><em>boundsArray</em>&nbsp;</td><td>
169array of duplicated object indices, first bit tells mimima and maxima apart </td></tr>
170<tr><td valign="top"><em>nObjects</em>&nbsp;</td><td>
171<a class="el" href="class_k_d_tree.html#44c1da792f9896ac252d552db9cfc08c">objects</a> (boundsArray's size is 2*nObjects) </td></tr>
172<tr><td valign="top"><em>limits</em>&nbsp;</td><td>
173kd-tree node volume </td></tr>
174</table>
175</dl>    </td>
176  </tr>
177</table>
178<a class="anchor" name="1afbe38e70fc1e48465a05fa990b66b8"></a><!-- doxytag: member="KDTree::compare" ref="1afbe38e70fc1e48465a05fa990b66b8" args="(unsigned int aIndex, unsigned int bIndex, unsigned char axis)" --><p>
179<table class="mdTable" cellpadding="2" cellspacing="0">
180  <tr>
181    <td class="mdRow">
182      <table cellpadding="0" cellspacing="0" border="0">
183        <tr>
184          <td class="md" nowrap valign="top">bool KDTree::compare           </td>
185          <td class="md" valign="top">(&nbsp;</td>
186          <td class="md" nowrap valign="top">unsigned int&nbsp;</td>
187          <td class="mdname" nowrap> <em>aIndex</em>, </td>
188        </tr>
189        <tr>
190          <td class="md" nowrap align="right"></td>
191          <td class="md"></td>
192          <td class="md" nowrap>unsigned int&nbsp;</td>
193          <td class="mdname" nowrap> <em>bIndex</em>, </td>
194        </tr>
195        <tr>
196          <td class="md" nowrap align="right"></td>
197          <td class="md"></td>
198          <td class="md" nowrap>unsigned char&nbsp;</td>
199          <td class="mdname" nowrap> <em>axis</em></td>
200        </tr>
201        <tr>
202          <td class="md"></td>
203          <td class="md">)&nbsp;</td>
204          <td class="md" colspan="2"><code> [inline, private]</code></td>
205        </tr>
206      </table>
207    </td>
208  </tr>
209</table>
210<table cellspacing="5" cellpadding="0" border="0">
211  <tr>
212    <td>
213      &nbsp;
214    </td>
215    <td>
216
217<p>
218compare two object extrema according to the coordinate specified
219<p>
220this is more complicated then one would predict. rules are:<ul>
221<li>if values are significantly different, no problem</li><li>the minimum of a patch is smaller than its maximum</li><li>if a maximum and a minimum are near, the other extrema of the patches decide</li><li>if all four extrema are near, the 2 ends of a patch have to be simultaneusly smaller or bigger than the other two ends </li></ul>
222    </td>
223  </tr>
224</table>
225<a class="anchor" name="87fed42fc407cd3b3fc48f817363b086"></a><!-- doxytag: member="KDTree::deleteLeaves" ref="87fed42fc407cd3b3fc48f817363b086" args="(unsigned int nodeID)" --><p>
226<table class="mdTable" cellpadding="2" cellspacing="0">
227  <tr>
228    <td class="mdRow">
229      <table cellpadding="0" cellspacing="0" border="0">
230        <tr>
231          <td class="md" nowrap valign="top">void KDTree::deleteLeaves           </td>
232          <td class="md" valign="top">(&nbsp;</td>
233          <td class="md" nowrap valign="top">unsigned int&nbsp;</td>
234          <td class="mdname1" valign="top" nowrap> <em>nodeID</em>          </td>
235          <td class="md" valign="top">&nbsp;)&nbsp;</td>
236          <td class="md" nowrap><code> [private]</code></td>
237        </tr>
238      </table>
239    </td>
240  </tr>
241</table>
242<table cellspacing="5" cellpadding="0" border="0">
243  <tr>
244    <td>
245      &nbsp;
246    </td>
247    <td>
248
249<p>
250traces the tree defined by root node index 'nodeID', and frees the memory occupied by the object lists     </td>
251  </tr>
252</table>
253<a class="anchor" name="cd6808333cc2366abd86b9db8ee431a6"></a><!-- doxytag: member="KDTree::followChildren" ref="cd6808333cc2366abd86b9db8ee431a6" args="(unsigned int &amp;parent, unsigned int &amp;leftChild, unsigned int &amp;rightChild)" --><p>
254<table class="mdTable" cellpadding="2" cellspacing="0">
255  <tr>
256    <td class="mdRow">
257      <table cellpadding="0" cellspacing="0" border="0">
258        <tr>
259          <td class="md" nowrap valign="top">bool KDTree::followChildren           </td>
260          <td class="md" valign="top">(&nbsp;</td>
261          <td class="md" nowrap valign="top">unsigned int &amp;&nbsp;</td>
262          <td class="mdname" nowrap> <em>parent</em>, </td>
263        </tr>
264        <tr>
265          <td class="md" nowrap align="right"></td>
266          <td class="md"></td>
267          <td class="md" nowrap>unsigned int &amp;&nbsp;</td>
268          <td class="mdname" nowrap> <em>leftChild</em>, </td>
269        </tr>
270        <tr>
271          <td class="md" nowrap align="right"></td>
272          <td class="md"></td>
273          <td class="md" nowrap>unsigned int &amp;&nbsp;</td>
274          <td class="mdname" nowrap> <em>rightChild</em></td>
275        </tr>
276        <tr>
277          <td class="md"></td>
278          <td class="md">)&nbsp;</td>
279          <td class="md" colspan="2"><code> [inline, private]</code></td>
280        </tr>
281      </table>
282    </td>
283  </tr>
284</table>
285<table cellspacing="5" cellpadding="0" border="0">
286  <tr>
287    <td>
288      &nbsp;
289    </td>
290    <td>
291
292<p>
293retrieve the node indices corresponding to the children of the specified node return false if the node is a leaf     </td>
294  </tr>
295</table>
296<a class="anchor" name="3d68e4e5ea6a01ec90f6fac0206db10b"></a><!-- doxytag: member="KDTree::getFreeNodes" ref="3d68e4e5ea6a01ec90f6fac0206db10b" args="(unsigned int parent, unsigned int &amp;leftFree, unsigned int &amp;rightFree)" --><p>
297<table class="mdTable" cellpadding="2" cellspacing="0">
298  <tr>
299    <td class="mdRow">
300      <table cellpadding="0" cellspacing="0" border="0">
301        <tr>
302          <td class="md" nowrap valign="top">bool KDTree::getFreeNodes           </td>
303          <td class="md" valign="top">(&nbsp;</td>
304          <td class="md" nowrap valign="top">unsigned int&nbsp;</td>
305          <td class="mdname" nowrap> <em>parent</em>, </td>
306        </tr>
307        <tr>
308          <td class="md" nowrap align="right"></td>
309          <td class="md"></td>
310          <td class="md" nowrap>unsigned int &amp;&nbsp;</td>
311          <td class="mdname" nowrap> <em>leftFree</em>, </td>
312        </tr>
313        <tr>
314          <td class="md" nowrap align="right"></td>
315          <td class="md"></td>
316          <td class="md" nowrap>unsigned int &amp;&nbsp;</td>
317          <td class="mdname" nowrap> <em>rightFree</em></td>
318        </tr>
319        <tr>
320          <td class="md"></td>
321          <td class="md">)&nbsp;</td>
322          <td class="md" colspan="2"><code> [inline, private]</code></td>
323        </tr>
324      </table>
325    </td>
326  </tr>
327</table>
328<table cellspacing="5" cellpadding="0" border="0">
329  <tr>
330    <td>
331      &nbsp;
332    </td>
333    <td>
334
335<p>
336retrieve the node indices corresponding to the children of the specified node if they are not suitable to be the root of a free sub-tree, return false     </td>
337  </tr>
338</table>
339<a class="anchor" name="f6de48530830ab214b595b1d5fa953fa"></a><!-- doxytag: member="KDTree::makePointer" ref="f6de48530830ab214b595b1d5fa953fa" args="(unsigned int originalNode)" --><p>
340<table class="mdTable" cellpadding="2" cellspacing="0">
341  <tr>
342    <td class="mdRow">
343      <table cellpadding="0" cellspacing="0" border="0">
344        <tr>
345          <td class="md" nowrap valign="top">unsigned int KDTree::makePointer           </td>
346          <td class="md" valign="top">(&nbsp;</td>
347          <td class="md" nowrap valign="top">unsigned int&nbsp;</td>
348          <td class="mdname1" valign="top" nowrap> <em>originalNode</em>          </td>
349          <td class="md" valign="top">&nbsp;)&nbsp;</td>
350          <td class="md" nowrap><code> [inline, private]</code></td>
351        </tr>
352      </table>
353    </td>
354  </tr>
355</table>
356<table cellspacing="5" cellpadding="0" border="0">
357  <tr>
358    <td>
359      &nbsp;
360    </td>
361    <td>
362
363<p>
364If the node referenced by oNode is on the last level of a cache-line sized sub-tree, a pointer to a free node is placed, and the index of this free node is returned. Else, originalNode is returned.     </td>
365  </tr>
366</table>
367<hr>The documentation for this class was generated from the following files:<ul>
368<li>KDTree.hpp<li>KDTree.cpp</ul>
369<hr size="1"><address style="align: right;"><small>Generated on Thu Apr 27 17:17:42 2006 for Path Map Module by&nbsp;
370<a href="http://www.doxygen.org/index.html">
371<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.4.6-NO </small></address>
372</body>
373</html>
Note: See TracBrowser for help on using the repository browser.