diff options
Diffstat (limited to '')
| -rw-r--r-- | docs/doxygen/nel/quad__tree_8h-source.html | 845 |
1 files changed, 845 insertions, 0 deletions
diff --git a/docs/doxygen/nel/quad__tree_8h-source.html b/docs/doxygen/nel/quad__tree_8h-source.html new file mode 100644 index 00000000..90bd7e41 --- /dev/null +++ b/docs/doxygen/nel/quad__tree_8h-source.html @@ -0,0 +1,845 @@ +<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"> +<HTML> +<HEAD> + <TITLE>nevrax.org : docs</TITLE> + <LINK REL=stylesheet TYPE="text/css" HREF="http://www.nevrax.org/inc/css/nevrax.css"> + <link href="doxygen.css" rel="stylesheet" type="text/css"> +</HEAD> +<BODY MARGINHEIGHT="0" MARGINWIDTH="0"> + +<!-- uplinks --> +<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0> + <TR> + <TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD WIDTH=140 BGCOLOR=#dddddd><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD><IMG width=6 height=14 SRC="http://www.nevrax.org/inc/img/reddots.gif" ALT="#" VSPACE=2 HSPACE=2 BORDER=0 ></TD><TD VALIGN=middle> <A CLASS=uplinks HREF=http://www.nevrax.org><b>Home</B></FONT></A> </TD> + <TD><IMG width=6 height=14 SRC="http://www.nevrax.org/inc/img/reddots.gif" ALT="#" VSPACE=2 HSPACE=2 BORDER=0 ></TD><TD VALIGN=middle> <A CLASS=uplinks HREF=http://www.nevrax.com><b>nevrax.com</B></FONT></A> </TD> + </TR> +</TABLE> + +<!-- banner Nevrax --> +<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0 WIDTH=100%> + <TR><TD BGCOLOR="#000000" BACKGROUND="http://www.nevrax.org/inc/img/black_banner.jpg"><A HREF="http://www.nevrax.org"><IMG SRC="http://www.nevrax.org/inc/img/nevrax.gif" WIDTH="170" HEIGHT="45" BORDER=0 ALT="Nevrax" ></A></TD></TR> +</TABLE> + +<!-- main table --> +<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0 height=100%> + <TR> + <TD WIDTH=16><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="10" BORDER=0 ALT=""></TD> + <TD WIDTH=140 BGCOLOR=#dddddd VALIGN=TOP ALIGN=middle><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="10" BORDER=0 ALT=""> + + <!------ Begin Box ------> + <TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 BGCOLOR=black><TR><TD><TABLE border=0 cellspacing=2 cellpadding=0 width=120><tr><TD ALIGN=middle bgcolor=black> + <FONT COLOR=white FACE="sans-serif"><B>Nevrax.org</B></FONT></TD></TR><tr><td colspan=2 bgcolor=#FFFFFF> + <TABLE cellspacing=0 cellpadding=1 border=0> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/news/" TITLE="Rubrique news"><img width=13 height=15 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-news.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/news/" TITLE="News">News</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/mail/" TITLE="Rubrique mail"><img width=15 height=11 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-mail.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/mail/" TITLE="Mailing list archive">Mailing-list</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/docs/" TITLE="Rubrique docs"><img width=14 height=16 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-docs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/docs/" TITLE="Documentation">Documentation</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/cvs/" TITLE="Rubrique cvs"><img width=13 height=17 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-cvs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/cvs/" TITLE="CVS Web">CVS</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/bugs/" TITLE="Rubrique bugs"><img width=20 height=16 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-bugs.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/bugs/" TITLE="Bugtracking">Bugs</a></td></tr> + <tr><td ALIGN=middle><a class='linkbox' href="http://www.nevrax.org/GPL.php3" TITLE="Rubrique license"><img width=18 height=12 hspace=5 border=0 src=http://www.nevrax.org/inc/img/picto-gpl.gif ALT=#></A></td><td><a class='linkbox' href="http://www.nevrax.org/GPL.php3" TITLE="License">License</a></td></tr> + </TABLE> + </TD></TR></TABLE></TD></TR></TABLE> + <!------ End Box ------> + + </TD> + <TD WIDTH=15><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="16" HEIGHT="16" BORDER=0 ALT=""></TD> + <TD ALIGN=left valign=top><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="140" HEIGHT="10" BORDER=0 ALT=""> + +<!-- title --> +<TABLE background="http://www.nevrax.org/inc/img/redline.gif" CELLSPACING=0 CELLPADDING=0 BORDER=0 width=100%><tr><td> +<A HREF="http://www.nevrax.org/docs/"><img src="http://www.nevrax.org/inc/img/t_docs.gif" ALT="Docs" HEIGHT=20 BORDER=0></A> +</td><td><IMG SRC="http://www.nevrax.org/inc/img/pixel.gif" WIDTH="1" HEIGHT="1" BORDER=0 ALT=""> +</td></tr></table> + + +<!-- block --> +<TABLE bgcolor="#dddddd" CELLSPACING=0 CELLPADDING=0 BORDER=0 width=100%><tr><td width=1% valign=middle><img width=6 height=14 hspace=2 vspace=2 src="http://www.nevrax.org/inc/img/reddots.gif"></TD> + <TD><B>Documentation</B></TD> + <TD ALIGN=RIGHT> </td> +</tr></table> +<!-- Generated by Doxygen 1.2.14 --> +<center> +<a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="namespaces.html">Namespace List</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="classes.html">Alphabetical List</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="namespacemembers.html">Namespace Members</a> <a class="qindex" href="functions.html">Compound Members</a> <a class="qindex" href="globals.html">File Members</a> <a class="qindex" href="pages.html">Related Pages</a> <a class="qindexRef" doxygen="_cgi:http://www.nevrax.org/cgi-bin/nel-search.cgi" href="http://www.nevrax.org/cgi-bin/nel-search.cgi">Search</a> </center> +<hr><h1>quad_tree.h</h1><a href="quad__tree_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 +00007 <font class="comment">/* Copyright, 2000 Nevrax Ltd.</font> +00008 <font class="comment"> *</font> +00009 <font class="comment"> * This file is part of NEVRAX NEL.</font> +00010 <font class="comment"> * NEVRAX NEL is free software; you can redistribute it and/or modify</font> +00011 <font class="comment"> * it under the terms of the GNU General Public License as published by</font> +00012 <font class="comment"> * the Free Software Foundation; either version 2, or (at your option)</font> +00013 <font class="comment"> * any later version.</font> +00014 <font class="comment"></font> +00015 <font class="comment"> * NEVRAX NEL is distributed in the hope that it will be useful, but</font> +00016 <font class="comment"> * WITHOUT ANY WARRANTY; without even the implied warranty of</font> +00017 <font class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</font> +00018 <font class="comment"> * General Public License for more details.</font> +00019 <font class="comment"></font> +00020 <font class="comment"> * You should have received a copy of the GNU General Public License</font> +00021 <font class="comment"> * along with NEVRAX NEL; see the file COPYING. If not, write to the</font> +00022 <font class="comment"> * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,</font> +00023 <font class="comment"> * MA 02111-1307, USA.</font> +00024 <font class="comment"> */</font> +00025 +00026 +00027 <font class="preprocessor">#ifndef NL_QUAD_TREE_H</font> +00028 <font class="preprocessor"></font><font class="preprocessor">#define NL_QUAD_TREE_H</font> +00029 <font class="preprocessor"></font> +00030 <font class="preprocessor">#include "<a class="code" href="debug_8h.html">nel/misc/debug.h</a>"</font> +00031 <font class="preprocessor">#include "<a class="code" href="vector_8h.html">nel/misc/vector.h</a>"</font> +00032 <font class="preprocessor">#include "<a class="code" href="plane_8h.html">nel/misc/plane.h</a>"</font> +00033 <font class="preprocessor">#include "<a class="code" href="matrix_8h.html">nel/misc/matrix.h</a>"</font> +00034 <font class="preprocessor">#include <list></font> +00035 <font class="preprocessor">#include <vector></font> +00036 +00037 +00038 <font class="keyword">namespace </font>NL3D +00039 { +00040 +00041 +00042 +<a name="l00096"></a><a class="code" href="classNL3D_1_1CQuadTree.html">00096</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keyword">class </font>CQuadTree +00097 { +00098 +00099 <font class="keyword">public</font>: +00101 <font class="keyword">class </font><a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a>; +<a name="l00102"></a><a class="code" href="classNL3D_1_1CQuadTree.html#l0">00102</a> <font class="keyword">friend</font> <font class="keyword">class </font><a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a>; +00104 <font class="keyword">class </font><a class="code" href="classNL3D_1_1CQuadTree.html#l1">CConstIterator</a>; +<a name="l00105"></a><a class="code" href="classNL3D_1_1CQuadTree.html#l1">00105</a> <font class="keyword">friend</font> <font class="keyword">class </font><a class="code" href="classNL3D_1_1CQuadTree.html#l1">CConstIterator</a>; +00106 +00107 <font class="keyword">public</font>: +00108 +00110 <a class="code" href="classNL3D_1_1CQuadTree.html#a0">CQuadTree</a>(); +00111 +00113 <a class="code" href="classNL3D_1_1CQuadTree.html#a1">~CQuadTree</a>(); +00114 +00116 +00117 +00132 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z0_0">changeBase</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CMatrix.html">NLMISC::CMatrix</a>& base); +00133 +00140 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z0_1">create</a>(uint DepthMax, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& center, <font class="keywordtype">float</font> size); +00142 +00143 +00145 +00146 +00147 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z1_0">clear</a>(); +00148 +00151 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z1_1">eraseAll</a>(); +00152 +00157 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z1_2">erase</a>(<a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a> it); +00158 +00165 <a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a> <a class="code" href="classNL3D_1_1CQuadTree.html#z1_3">insert</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmax, <font class="keyword">const</font> T &val); +00167 +00168 +00170 +00171 +00173 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_0">clearSelection</a>(); +00174 +00177 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_1">selectAll</a>(); +00178 +00184 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_2">select</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmax); +00185 +00191 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_2">select</a>(<font class="keyword">const</font> std::vector<NLMISC::CPlane> &BVolume); +00192 +00198 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_4">selectRay</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& source, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& dir); +00199 +00205 <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_5">selectSegment</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& source, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& dest); +00206 +00209 <a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_6">begin</a>(); +00210 +00213 <a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a> <a class="code" href="classNL3D_1_1CQuadTree.html#z2_7">end</a>(); +00215 +00216 +00217 +00218 <font class="comment">// =================</font> +00219 <font class="comment">// =================</font> +00220 <font class="comment">// IMPLEMENTATION.</font> +00221 <font class="comment">// =================</font> +00222 <font class="comment">// =================</font> +00223 <font class="keyword">private</font>:<font class="comment">// Classes.</font> +00224 +00225 +00226 <font class="comment">// =================</font> +00227 <font class="comment">// =================</font> +00228 <font class="comment">// CBaseNode.</font> +00229 <font class="comment">// =================</font> +00230 <font class="comment">// =================</font> +00231 <font class="comment">// Links fo an element node class.</font> +<a name="l00232"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html">00232</a> <font class="keyword">class </font>CBaseNode +00233 { +00234 <font class="keyword">public</font>: +00235 <font class="comment">// for the Selection list.</font> +<a name="l00236"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m0">00236</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a0">CBaseNode</a> *<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m0">Prev</a>, *<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m1">Next</a>; +00237 <font class="comment">// for the quadnode list. A node MAY be pointed by 4 quad (each having the same level).</font> +<a name="l00238"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m2">00238</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a0">CBaseNode</a> *<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m2">QuadPrevs</a>[4]; +<a name="l00239"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m3">00239</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a0">CBaseNode</a> *<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m3">QuadNexts</a>[4]; +00240 +00241 +00242 <font class="keyword">public</font>: +<a name="l00243"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a0">00243</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a0">CBaseNode</a>() +00244 { +00245 Prev=Next=NULL; +00246 QuadPrevs[0]= QuadPrevs[1]= QuadPrevs[2]= QuadPrevs[3]= NULL; +00247 QuadNexts[0]= QuadNexts[1]= QuadNexts[2]= QuadNexts[3]= NULL; +00248 } +<a name="l00249"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a1">00249</a> <font class="keyword">virtual</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a1">~CBaseNode</a>() {} <font class="comment">// Empty destructor, but declare it as virtual...</font> +<a name="l00250"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a2">00250</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a2">clear</a>() <font class="comment">// update links.</font> +00251 { +00252 <font class="comment">// On le retire de la selection.</font> +00253 <font class="keywordflow">if</font>(Prev) Prev->Next= Next; +00254 <font class="keywordflow">if</font>(Next) Next->Prev= Prev; +00255 Prev=Next=NULL; +00256 <font class="comment">// On le retire des listes dans les quads.</font> +00257 <font class="keywordflow">for</font>(uint i=0;i<4;i++) +00258 { +00259 <font class="keywordflow">if</font>(QuadPrevs[i]) {<a class="code" href="debug_8h.html#a6">nlassert</a>(QuadPrevs[i]->QuadNexts[i]==<font class="keyword">this</font>); QuadPrevs[i]->QuadNexts[i]= QuadNexts[i];} +00260 <font class="keywordflow">if</font>(QuadNexts[i]) {<a class="code" href="debug_8h.html#a6">nlassert</a>(QuadNexts[i]->QuadPrevs[i]==<font class="keyword">this</font>); QuadNexts[i]->QuadPrevs[i]= QuadPrevs[i];} +00261 QuadPrevs[i]=NULL; +00262 QuadNexts[i]=NULL; +00263 } +00264 } +<a name="l00265"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a3">00265</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#a3">isSelected</a>() <font class="comment">// return true if Prev is not NULL!!!</font> +00266 { +00267 <font class="keywordflow">return</font> Prev!=NULL; +00268 } +00269 }; +00270 +00271 +00272 <font class="comment">// =================</font> +00273 <font class="comment">// =================</font> +00274 <font class="comment">// CNode.</font> +00275 <font class="comment">// =================</font> +00276 <font class="comment">// =================</font> +00277 <font class="comment">// An element node class.</font> +<a name="l00278"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CNode.html">00278</a> <font class="keyword">class </font>CNode : <font class="keyword">public</font> CBaseNode +00279 { +00280 <font class="keyword">public</font>: +00281 <font class="comment">// A base node, plus the Value.</font> +<a name="l00282"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CNode.html#m0">00282</a> T <a class="code" href="classNL3D_1_1CQuadTree_1_1CNode.html#m0">Value</a>; +<a name="l00283"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CNode.html#a0">00283</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CNode.html#a0">CNode</a>(<font class="keyword">const</font> T &val) : <a class="code" href="classNL3D_1_1CQuadTree_1_1CNode.html#m0">Value</a>(val) {} +00284 }; +00285 +00286 +00287 <font class="comment">// =================</font> +00288 <font class="comment">// =================</font> +00289 <font class="comment">// CQuadNode.</font> +00290 <font class="comment">// =================</font> +00291 <font class="comment">// =================</font> +<a name="l00292"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html">00292</a> <font class="keyword">class </font>CQuadNode +00293 { +00294 <font class="keyword">public</font>: +<a name="l00295"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m0">00295</a> uint <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m0">Level</a>; +<a name="l00296"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m1">00296</a> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m1">BBoxMin</a>, <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m2">BBoxMax</a>; +<a name="l00297"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m3">00297</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m3">BBoxNeverRescale</a>; +<a name="l00298"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m4">00298</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a0">CQuadNode</a> *<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m4">Sons</a>[4]; +<a name="l00299"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m5">00299</a> CBaseNode <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m5">RootNode</a>; <font class="comment">// First element of the element list in this quad.</font> +<a name="l00300"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">00300</a> uint <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>; <font class="comment">// [0,3]. index of wich list to follow in "Node.QuadNexts[]".</font> +00301 <font class="comment">/* Topology of sons (top view: axe x/z):</font> +00302 <font class="comment"> 0--1</font> +00303 <font class="comment"> | |</font> +00304 <font class="comment"> 2--3</font> +00305 <font class="comment"> */</font> +00306 +00307 +00308 <font class="keyword">public</font>: +00309 <font class="comment">// ============================================================================================</font> +<a name="l00310"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a0">00310</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a0">CQuadNode</a>() +00311 { +00312 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m0">Level</a>=0; Sons[0]= Sons[1]= Sons[2]= Sons[3]= NULL; +00313 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>= 0; +00314 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m3">BBoxNeverRescale</a>=<font class="keyword">true</font>; +00315 } +00316 <font class="comment">// ============================================================================================</font> +<a name="l00317"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">00317</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">isLeaf</a>() +00318 { +00319 <font class="keywordflow">return</font> Sons[0]==NULL; +00320 } +00321 <font class="comment">// ============================================================================================</font> +<a name="l00322"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a2">00322</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a2">clear</a>() +00323 { +00324 <font class="comment">// Deletons les element dans ce quad node.</font> +00325 CBaseNode *p; +00326 <font class="keywordflow">while</font>( (p=RootNode.QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]) ) +00327 { +00328 p->clear(); <font class="comment">// On clear les links. => RootNode.QuadNexts[ListIndex] modifié implicitement.</font> +00329 <font class="keyword">delete</font> p; <font class="comment">// On delete cet element!!</font> +00330 } +00331 +00332 <font class="comment">// Deletons les quad fils.</font> +00333 <font class="keywordflow">for</font>(uint i=0;i<4;i++) +00334 { +00335 <font class="keywordflow">if</font>(Sons[i]) +00336 { +00337 Sons[i]->clear(); +00338 <font class="keyword">delete</font> Sons[i]; +00339 Sons[i]= NULL; +00340 } +00341 } +00342 } +00343 <font class="comment">// ============================================================================================</font> +<a name="l00344"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a3">00344</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a3">split</a>() +00345 { +00346 <a class="code" href="debug_8h.html#a6">nlassert</a>(<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">isLeaf</a>()); +00347 sint i; +00348 +00349 <font class="keywordflow">for</font>(i=0;i<4;i++) +00350 { +00351 Sons[i]= <font class="keyword">new</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a0">CQuadNode</a>; +00352 Sons[i]->Level= <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m0">Level</a>+1; +00353 Sons[i]->ListIndex= i; +00354 } +00355 <font class="comment">// Middle compute.</font> +00356 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> MidLeft(0,0,0), MidRight(0,0,0), MidTop(0,0,0), MidBottom(0,0,0), Middle(0,0,0); +00357 MidLeft.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> = BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>; MidLeft.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> = (BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> + BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)/2; +00358 MidRight.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> = BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>; MidRight.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> = (BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> + BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)/2; +00359 MidTop.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> = (BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> + BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>)/2; MidTop.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> = BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>; +00360 MidBottom.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>= (BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> + BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>)/2; MidBottom.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>= BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>; +00361 Middle.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> = MidTop.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>; Middle.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> = MidLeft.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>; +00362 <font class="comment">// Sons compute.</font> +00363 <font class="comment">// Don't care of Y.</font> +00364 Sons[0]->BBoxMin = BBoxMin; Sons[0]->BBoxMax = Middle; +00365 Sons[1]->BBoxMin = MidTop ; Sons[1]->BBoxMax = MidRight; +00366 Sons[2]->BBoxMin = MidLeft; Sons[2]->BBoxMax = MidBottom; +00367 Sons[3]->BBoxMin = Middle; Sons[3]->BBoxMax = BBoxMax; +00368 +00369 } +00370 +00371 +00372 <font class="comment">// ============================================================================================</font> +00373 <font class="comment">// This is a quadtree, so those tests just test against x/z. (the base of the box).</font> +<a name="l00374"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a4">00374</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a4">includeBoxQuad</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmax) +00375 { +00376 <font class="keywordflow">if</font>( BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a><= boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> && BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>>= boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> && +00377 BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a><= boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> && BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>>= boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>) +00378 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00379 <font class="keywordflow">else</font> +00380 <font class="keywordflow">return</font> <font class="keyword">false</font>; +00381 } +00382 <font class="comment">// ============================================================================================</font> +<a name="l00383"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a5">00383</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a5">intersectBoxQuad</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmax) +00384 { +00385 <font class="comment">// inequality and equality is very important, to ensure that a element box will not fit in too many quad boxes.</font> +00386 <font class="keywordflow">if</font>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> > BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00387 <font class="keywordflow">if</font>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> > BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00388 <font class="keywordflow">if</font>(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> <= BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00389 <font class="keywordflow">if</font>(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> <= BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00390 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00391 } +00392 <font class="comment">// ============================================================================================</font> +<a name="l00393"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a6">00393</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a6">intersectBox</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmax) +00394 { +00395 <font class="comment">// inequality and equality is very important, to ensure that a element box will not fit in too many quad boxes.</font> +00396 <font class="keywordflow">if</font>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> > BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00397 <font class="keywordflow">if</font>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a> > BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00398 <font class="keywordflow">if</font>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> > BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00399 <font class="keywordflow">if</font>(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a> <= BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00400 <font class="keywordflow">if</font>(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a> <= BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00401 <font class="keywordflow">if</font>(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> <= BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>) <font class="keywordflow">return</font> <font class="keyword">false</font>; +00402 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00403 } +00404 <font class="comment">// ============================================================================================</font> +<a name="l00405"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a7">00405</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a6">intersectBox</a>(std::vector<NLMISC::CPlane> &BVolume) +00406 { +00407 <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &b1=BBoxMin; +00408 <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &b2=BBoxMax; +00409 +00410 <font class="keywordflow">for</font>(sint i=0;i<(int)BVolume.size();i++) +00411 { +00412 <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CPlane.html">NLMISC::CPlane</a> &plane=BVolume[i]; +00413 <font class="comment">// If only one of the box vertex is IN the plane, then all the box is IN this plane.</font> +00414 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b1.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00415 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b1.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00416 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b1.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00417 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b1.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00418 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00419 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00420 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b1.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00421 <font class="keywordflow">if</font>(plane* <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(b2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, b2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)<=0) <font class="keywordflow">continue</font>; +00422 <font class="comment">// If ALL box vertices are OUT of this plane, then the box is OUT of the entire volume.</font> +00423 <font class="keywordflow">return</font> <font class="keyword">false</font>; +00424 } +00425 <font class="comment">// TODO. This is a simple box detection. The box is not really clipped and sometimes, the box will said</font> +00426 <font class="comment">// it intersect but it is not the case... Here, We should test the real box volume, against BVolume.</font> +00427 <font class="comment">// But this is more expensive...</font> +00428 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00429 } +00430 +00431 <font class="comment">// ============================================================================================</font> +<a name="l00432"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a8">00432</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a8">addElement</a>(CNode *newNode) +00433 { +00434 <a class="code" href="debug_8h.html#a6">nlassert</a>(newNode->QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]==NULL); +00435 newNode->QuadPrevs[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]= &RootNode; +00436 newNode->QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]= RootNode.QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]; +00437 <font class="keywordflow">if</font>(RootNode.QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]) +00438 RootNode.QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]->QuadPrevs[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]= newNode; +00439 RootNode.QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]= newNode; +00440 } +00441 <font class="comment">// ============================================================================================</font> +00442 <font class="comment">// Insertion of a node in this quad node, or his sons...</font> +<a name="l00443"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a9">00443</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a9">insert</a>(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &boxmax, uint wantdepth, CNode *newNode) +00444 { +00445 <font class="keywordflow">if</font>(<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m0">Level</a>==0) +00446 { +00447 <font class="comment">// Tous les elements qui sortent du quadtree sont forcément dans le noeud root.</font> +00448 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a4">includeBoxQuad</a>(boxmin, boxmax)) +00449 { +00450 <font class="comment">// Il faut agrandir la BBox en Y du quadnode.</font> +00451 <font class="keywordflow">if</font>(BBoxNeverRescale) +00452 { +00453 BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>; +00454 BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>; +00455 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m3">BBoxNeverRescale</a>= <font class="keyword">false</font>; +00456 } +00457 <font class="keywordflow">else</font> +00458 { +00459 BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= <a class="code" href="bit__set_8cpp.html#a0">std::min</a>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>); +00460 BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= std::max(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>); +00461 } +00462 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a8">addElement</a>(newNode); +00463 <font class="keywordflow">return</font>; +00464 } +00465 } +00466 +00467 <font class="comment">// Si au moins une partie de l'element n'est pas dans le noeud de ce quad, exit.</font> +00468 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a5">intersectBoxQuad</a>(boxmin, boxmax)) +00469 <font class="keywordflow">return</font>; +00470 +00471 <font class="comment">// Que l'on insere ici ou dans les fils, il faut agrandir la BBox en Y du quadnode.</font> +00472 <font class="keywordflow">if</font>(BBoxNeverRescale) +00473 { +00474 BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>; +00475 BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>; +00476 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m3">BBoxNeverRescale</a>= <font class="keyword">false</font>; +00477 } +00478 <font class="keywordflow">else</font> +00479 { +00480 BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= <a class="code" href="bit__set_8cpp.html#a0">std::min</a>(boxmin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, BBoxMin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>); +00481 BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>= std::max(boxmax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, BBoxMax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>); +00482 } +00483 +00484 <font class="comment">// Si on est au bon, niveau, on a plus qu'à l'insérer dans ce node.</font> +00485 <font class="keywordflow">if</font>(wantdepth==<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m0">Level</a>) +00486 { +00487 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a8">addElement</a>(newNode); +00488 } +00489 <font class="keywordflow">else</font> +00490 { +00491 <font class="comment">// Si le quad est une feuille, il faut le splitter (car on est pas encore arrivé au bon niveau).</font> +00492 <font class="keywordflow">if</font>(<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">isLeaf</a>()) +00493 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a3">split</a>(); +00494 +00495 <font class="comment">// Et on cherche à mettre l'élément dans un de ces noeuds.</font> +00496 Sons[0]->insert(boxmin, boxmax, wantdepth, newNode); +00497 Sons[1]->insert(boxmin, boxmax, wantdepth, newNode); +00498 Sons[2]->insert(boxmin, boxmax, wantdepth, newNode); +00499 Sons[3]->insert(boxmin, boxmax, wantdepth, newNode); +00500 } +00501 +00502 } +00503 +00504 +00505 <font class="comment">// ============================================================================================</font> +00506 <font class="comment">// Selection.</font> +<a name="l00507"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a10">00507</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a10">selectLocalNodes</a>(CBaseNode &selroot) +00508 { +00509 CBaseNode *p= RootNode.QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]; +00510 <font class="keywordflow">while</font>(p) +00511 { +00512 <font class="keywordflow">if</font>(!p->isSelected()) +00513 { +00514 p->Prev= &selroot; +00515 p->Next= selroot.Next; +00516 <font class="keywordflow">if</font>(selroot.Next) +00517 selroot.Next->Prev= p; +00518 selroot.Next= p; +00519 } +00520 p=p->QuadNexts[<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m6">ListIndex</a>]; +00521 } +00522 } +00523 <font class="comment">// ============================================================================================</font> +<a name="l00524"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a11">00524</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a11">selectAll</a>(CBaseNode &selroot) +00525 { +00526 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a10">selectLocalNodes</a>(selroot); +00527 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">isLeaf</a>()) +00528 { +00529 Sons[0]->selectAll(selroot); +00530 Sons[1]->selectAll(selroot); +00531 Sons[2]->selectAll(selroot); +00532 Sons[3]->selectAll(selroot); +00533 } +00534 } +00535 <font class="comment">// ============================================================================================</font> +<a name="l00536"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a12">00536</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a12">select</a>(CBaseNode &selroot, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmax) +00537 { +00538 <font class="comment">// TODO:</font> +00539 <font class="comment">// ya un bug avec le level0: en effet la bbox n'a pas été agrandie pour contenir les elements.</font> +00540 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a6">intersectBox</a>(bboxmin, bboxmax)) +00541 <font class="keywordflow">return</font>; +00542 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a10">selectLocalNodes</a>(selroot); +00543 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">isLeaf</a>()) +00544 { +00545 Sons[0]->select(selroot, bboxmin, bboxmax); +00546 Sons[1]->select(selroot, bboxmin, bboxmax); +00547 Sons[2]->select(selroot, bboxmin, bboxmax); +00548 Sons[3]->select(selroot, bboxmin, bboxmax); +00549 } +00550 } +00551 <font class="comment">// ============================================================================================</font> +<a name="l00552"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a13">00552</a> <font class="keywordtype">void</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a12">select</a>(CBaseNode &selroot, std::vector<NLMISC::CPlane> &BVolume) +00553 { +00554 <font class="comment">// TODO:</font> +00555 <font class="comment">// ya un bug avec le level0: en effet la bbox n'a pas été agrandie pour contenir les elements.</font> +00556 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a6">intersectBox</a>(BVolume)) +00557 <font class="keywordflow">return</font>; +00558 <a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a10">selectLocalNodes</a>(selroot); +00559 <font class="keywordflow">if</font>(!<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a1">isLeaf</a>()) +00560 { +00561 Sons[0]->select(selroot, BVolume); +00562 Sons[1]->select(selroot, BVolume); +00563 Sons[2]->select(selroot, BVolume); +00564 Sons[3]->select(selroot, BVolume); +00565 } +00566 } +00567 }; +00568 +00569 +00570 +00571 <font class="comment">// =================</font> +00572 <font class="comment">// =================</font> +00573 <font class="comment">// Attributes/Methods/iterators..</font> +00574 <font class="comment">// =================</font> +00575 <font class="comment">// =================</font> +00576 <font class="keyword">private</font>:<font class="comment">// Attributes.</font> +<a name="l00577"></a><a class="code" href="classNL3D_1_1CQuadTree.html#o0">00577</a> CQuadNode <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>; +<a name="l00578"></a><a class="code" href="classNL3D_1_1CQuadTree.html#o1">00578</a> CBaseNode <a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>; +<a name="l00579"></a><a class="code" href="classNL3D_1_1CQuadTree.html#o2">00579</a> uint <a class="code" href="classNL3D_1_1CQuadTree.html#o2">_DepthMax</a>; +<a name="l00580"></a><a class="code" href="classNL3D_1_1CQuadTree.html#o3">00580</a> <font class="keywordtype">float</font> <a class="code" href="classNL3D_1_1CQuadTree.html#o3">_Size</a>; +<a name="l00581"></a><a class="code" href="classNL3D_1_1CQuadTree.html#o4">00581</a> <a class="code" href="classNLMISC_1_1CMatrix.html">NLMISC::CMatrix</a> <a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>; +00582 +00583 <font class="keyword">private</font>:<font class="comment">// Methods.</font> +00584 +00585 +00586 +00587 <font class="keyword">public</font>: +00588 <font class="comment">// CLASS const_iterator.</font> +<a name="l00589"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html">00589</a> <font class="keyword">class </font>const_iterator +00590 { +00591 <font class="keyword">public</font>: +<a name="l00592"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">00592</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>() {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>=NULL;} +<a name="l00593"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a1">00593</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>(CNode *p) : <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>(p) {} +<a name="l00594"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a2">00594</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>(<font class="keyword">const</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#l1">CIterator</a>& <a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>) : <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>(<a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>) {} +00595 +<a name="l00596"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a3">00596</a> <font class="keyword">const</font> T& <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a3">operator*</a>()<font class="keyword"> const</font> +00597 <font class="keyword"> </font>{<font class="keywordflow">return</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>->Value; } +00598 <font class="comment">// Doesn't work...</font> +00599 <font class="comment">/*const T* operator->() const</font> +00600 <font class="comment"> {return (&**this); }*/</font> +<a name="l00601"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a4">00601</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>& <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a4">operator++</a>() +00602 {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a> = (CNode*)(<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>->Next); <font class="keywordflow">return</font> (*this); } +<a name="l00603"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a5">00603</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a4">operator++</a>(<font class="keywordtype">int</font>) +00604 {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a> tmp = *<font class="keyword">this</font>; ++*<font class="keyword">this</font>; <font class="keywordflow">return</font> (tmp); } +<a name="l00605"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a6">00605</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>& <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a6">operator--</a>() +00606 {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a> = (CNode*)(<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>->Prev); <font class="keywordflow">return</font> (*this); } +<a name="l00607"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a7">00607</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a6">operator--</a>(<font class="keywordtype">int</font>) +00608 {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a> tmp = *<font class="keyword">this</font>; --*<font class="keyword">this</font>; <font class="keywordflow">return</font> (tmp); } +<a name="l00609"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a8">00609</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a8">operator==</a>(<font class="keyword">const</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>& <a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>)<font class="keyword"> const</font> +00610 <font class="keyword"> </font>{<font class="keywordflow">return</font> (<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a> == x._Ptr); } +<a name="l00611"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a9">00611</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a9">operator!=</a>(<font class="keyword">const</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>& <a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>)<font class="keyword"> const</font> +00612 <font class="keyword"> </font>{<font class="keywordflow">return</font> (!(*<font class="keyword">this</font> == x)); } +00613 <font class="keyword">protected</font>: +<a name="l00614"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">00614</a> CNode *<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>; +<a name="l00615"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#l0">00615</a> <font class="keyword">friend</font> <font class="keyword">class </font>CQuadTree<T>; +<a name="l00616"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#l1">00616</a> <font class="keyword">friend</font> <font class="keyword">class </font><a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#l1">CIterator</a>; +00617 }; +00618 +00619 <font class="comment">// CLASS CIterator</font> +<a name="l00620"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html">00620</a> <font class="keyword">class </font><a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a> : <font class="keyword">public</font> const_iterator +00621 { +00622 <font class="keyword">public</font>: +<a name="l00623"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">00623</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a>() {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>=NULL;} +<a name="l00624"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a1">00624</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a>(CNode *p) : <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>(p) {} +<a name="l00625"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a2">00625</a> T& <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a2">operator*</a>()<font class="keyword"> const</font> +00626 <font class="keyword"> </font>{<font class="keywordflow">return</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>->Value; } +00627 <font class="comment">// Doesn't work...</font> +00628 <font class="comment">/*T* operator->() const</font> +00629 <font class="comment"> {return (&**this); }*/</font> +<a name="l00630"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a3">00630</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a>& <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a3">operator++</a>() +00631 {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a> = (CNode*)(<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>->Next); <font class="keywordflow">return</font> (*this); } +<a name="l00632"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a4">00632</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a3">operator++</a>(<font class="keywordtype">int</font>) +00633 {<a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a> tmp = *<font class="keyword">this</font>; ++*<font class="keyword">this</font>; <font class="keywordflow">return</font> (tmp); } +<a name="l00634"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a5">00634</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a>& <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a5">operator--</a>() +00635 {<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a> = (CNode*)(<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a>->Prev); <font class="keywordflow">return</font> (*this); } +<a name="l00636"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a6">00636</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a5">operator--</a>(<font class="keywordtype">int</font>) +00637 {<a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a0">CIterator</a> tmp = *<font class="keyword">this</font>; --*<font class="keyword">this</font>; <font class="keywordflow">return</font> (tmp); } +<a name="l00638"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a7">00638</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a7">operator==</a>(<font class="keyword">const</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>& <a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>)<font class="keyword"> const</font> +00639 <font class="keyword"> </font>{<font class="keywordflow">return</font> (<a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#n0">_Ptr</a> == x._Ptr); } +<a name="l00640"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a8">00640</a> <font class="keywordtype">bool</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#a8">operator!=</a>(<font class="keyword">const</font> <a class="code" href="classNL3D_1_1CQuadTree_1_1const__iterator.html#a0">const_iterator</a>& <a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>)<font class="keyword"> const</font> +00641 <font class="keyword"> </font>{<font class="keywordflow">return</font> (!(*<font class="keyword">this</font> == x)); } +00642 <font class="keyword">protected</font>: +<a name="l00643"></a><a class="code" href="classNL3D_1_1CQuadTree_1_1CIterator.html#l0">00643</a> <font class="keyword">friend</font> <font class="keyword">class </font>CQuadTree<T>; +00644 }; +00645 +00646 }; +00647 +00648 +00649 +00650 <font class="comment">// ============================================================================================</font> +00651 <font class="comment">// ============================================================================================</font> +00652 <font class="comment">// Template CQuadTree implementation. Construction/Destruction.</font> +00653 <font class="comment">// ============================================================================================</font> +00654 <font class="comment">// ============================================================================================</font> +00655 +00656 +00657 <font class="comment">// ============================================================================================</font> +<a name="l00658"></a><a class="code" href="classNL3D_1_1CQuadTree.html#a0">00658</a> <font class="keyword">template</font><<font class="keyword">class</font> T> CQuadTree<T>::CQuadTree() +00659 { +00660 <a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m1">Next</a>= NULL; +00661 <a class="code" href="classNL3D_1_1CQuadTree.html#o2">_DepthMax</a>= 0; +00662 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m1">BBoxMin</a>.<a class="code" href="classNLMISC_1_1CVector.html#z332_0">set</a>(-0.5, 0, -0.5); +00663 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m2">BBoxMax</a>.<a class="code" href="classNLMISC_1_1CVector.html#z332_0">set</a>( 0.5, 0, 0.5); +00664 <a class="code" href="classNL3D_1_1CQuadTree.html#o3">_Size</a>=1; +00665 +00666 <a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>.<a class="code" href="classNLMISC_1_1CMatrix.html#z290_0">identity</a>(); +00667 } +00668 <font class="comment">// ============================================================================================</font> +<a name="l00669"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z0_0">00669</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::changeBase(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CMatrix.html">NLMISC::CMatrix</a>& base) +00670 { +00671 <a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>=base; +00672 } +00673 <font class="comment">// ============================================================================================</font> +00674 <font class="keyword">template</font><<font class="keyword">class</font> T> CQuadTree<T>::~CQuadTree<T>() +00675 { +00676 clear(); +00677 } +00678 <font class="comment">// ============================================================================================</font> +<a name="l00679"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z1_0">00679</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::clear() +00680 { +00681 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a2">clear</a>(); +00682 <a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m1">Next</a>= NULL; +00683 } +00684 <font class="comment">// ============================================================================================</font> +<a name="l00685"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z0_1">00685</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::create(uint DepthMax, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& center, <font class="keywordtype">float</font> size) +00686 { +00687 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> mycenter=<a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>*center; +00688 <a class="code" href="classNL3D_1_1CQuadTree.html#z1_0">clear</a>(); +00689 <a class="code" href="classNL3D_1_1CQuadTree.html#o2">_DepthMax</a>= DepthMax; +00690 <a class="code" href="classNL3D_1_1CQuadTree.html#o3">_Size</a>= size; +00691 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m1">BBoxMin</a>= mycenter-<a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(size/2, 0 , size/2); +00692 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#m2">BBoxMax</a>= mycenter+<a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>(size/2, 0 , size/2); +00693 } +00694 +00695 +00696 <font class="comment">// ============================================================================================</font> +00697 <font class="comment">// ============================================================================================</font> +00698 <font class="comment">// Template CQuadTree implementation. Element Insertion/Deletion.</font> +00699 <font class="comment">// ============================================================================================</font> +00700 <font class="comment">// ============================================================================================</font> +00701 +00702 +00703 <font class="comment">// ============================================================================================</font> +<a name="l00704"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z1_1">00704</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::eraseAll() +00705 { +00706 <a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a> it; +00707 std::vector<CIterator> its; +00708 +00709 <font class="comment">// First, make a copy of all elements.</font> +00710 <a class="code" href="classNL3D_1_1CQuadTree.html#z2_1">selectAll</a>(); +00711 <font class="keywordflow">for</font>(it= <a class="code" href="classNL3D_1_1CQuadTree.html#z2_6">begin</a>();it!=<a class="code" href="classNL3D_1_1CQuadTree.html#z2_7">end</a>();it++) +00712 { +00713 its.push_back(it); +00714 } +00715 +00716 <font class="comment">// Then erase them. Must do it OUTSIDE the select loop.</font> +00717 <font class="keywordflow">for</font>(sint i=0;i<(sint)its.size();i++) +00718 { +00719 <a class="code" href="classNL3D_1_1CQuadTree.html#z1_2">erase</a>(its[i]); +00720 } +00721 } +00722 <font class="comment">// ============================================================================================</font> +<a name="l00723"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z1_2">00723</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::erase(CIterator it) +00724 { +00725 CNode *p=it._Ptr; +00726 <font class="keywordflow">if</font>(p) +00727 { +00728 <font class="comment">// Clear links.</font> +00729 p->clear(); +00730 +00731 <font class="comment">// delete it!!</font> +00732 <font class="keyword">delete</font> p; +00733 } +00734 } +00735 <font class="comment">// ============================================================================================</font> +<a name="l00736"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z1_3">00736</a> <font class="keyword">template</font><<font class="keyword">class</font> T> CQuadTree<T>::CIterator CQuadTree<T>::insert(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmax, <font class="keyword">const</font> T &val) +00737 { +00738 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> myboxmin2=<a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>*bboxmin; +00739 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> myboxmax2=<a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>*bboxmax; +00740 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> myboxmin (std::min (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>), std::min (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>), std::min (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)); +00741 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> myboxmax (std::max (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>), std::max (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>), std::max (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)); +00742 +00743 CNode *newNode=<font class="keyword">new</font> CNode(val); +00744 +00745 <a class="code" href="debug_8h.html#a6">nlassert</a>(myboxmax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>>=myboxmin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>); +00746 <a class="code" href="debug_8h.html#a6">nlassert</a>(myboxmax.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>>=myboxmin.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>); +00747 <a class="code" href="debug_8h.html#a6">nlassert</a>(myboxmax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>>=myboxmin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>); +00748 +00749 <font class="keywordtype">float</font> boxsize= std::max(myboxmax.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>-myboxmin.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, myboxmax.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>-myboxmin.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a> ); +00750 <font class="comment">// Prevent float precision problems. Increase bbox size a little.</font> +00751 boxsize*=1.01f; +00752 <font class="comment">// We must find the level quad which is just bigger.</font> +00753 <font class="keywordtype">float</font> wantsize=<a class="code" href="classNL3D_1_1CQuadTree.html#o3">_Size</a>; +00754 uint wantdepth=0; +00755 <font class="keywordflow">while</font>(boxsize<wantsize/2 && wantdepth<<a class="code" href="classNL3D_1_1CQuadTree.html#o2">_DepthMax</a>) +00756 { +00757 wantsize/=2; +00758 wantdepth++; +00759 } +00760 +00761 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a9">insert</a>(myboxmin, myboxmax, wantdepth, newNode); +00762 +00763 <font class="keywordflow">return</font> <a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a>(newNode); +00764 } +00765 +00766 +00767 <font class="comment">// ============================================================================================</font> +00768 <font class="comment">// ============================================================================================</font> +00769 <font class="comment">// Template CQuadTree implementation. Quad Selection, element iteration.</font> +00770 <font class="comment">// ============================================================================================</font> +00771 <font class="comment">// ============================================================================================</font> +00772 +00773 +00774 <font class="comment">// ============================================================================================</font> +<a name="l00775"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_0">00775</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::clearSelection() +00776 { +00777 CBaseNode *p; +00778 <font class="keywordflow">while</font>(p=<a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m1">Next</a>) +00779 { +00780 <font class="comment">// On retire ce noeud de la selection. Ce qui va modifier implicitement _Selection.Next.</font> +00781 <font class="keywordflow">if</font>(p->Prev) p->Prev->Next= p->Next; +00782 <font class="keywordflow">if</font>(p->Next) p->Next->Prev= p->Prev; +00783 p->Prev=p->Next=NULL; +00784 } +00785 } +00786 <font class="comment">// ============================================================================================</font> +<a name="l00787"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_1">00787</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::selectAll() +00788 { +00789 <a class="code" href="classNL3D_1_1CQuadTree.html#z2_0">clearSelection</a>(); +00790 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a11">selectAll</a>(<a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>); +00791 } +00792 <font class="comment">// ============================================================================================</font> +<a name="l00793"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_2">00793</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::select(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmin, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> &bboxmax) +00794 { +00795 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> myboxmin2=<a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>*bboxmin; +00796 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> myboxmax2=<a class="code" href="classNL3D_1_1CQuadTree.html#o4">_ChangeBasis</a>*bboxmax; +00797 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> bboxminCopy (std::min (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>), std::min (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>), std::min (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)); +00798 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> bboxmaxCopy (std::max (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m0">x</a>), std::max (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m1">y</a>), std::max (myboxmin2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>, myboxmax2.<a class="code" href="classNLMISC_1_1CVector.html#m2">z</a>)); +00799 +00800 <a class="code" href="classNL3D_1_1CQuadTree.html#z2_0">clearSelection</a>(); +00801 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a12">select</a>(<a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>, bboxminCopy, bboxmaxCopy); +00802 } +00803 <font class="comment">// ============================================================================================</font> +<a name="l00804"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_3">00804</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::select(<font class="keyword">const</font> std::vector<NLMISC::CPlane> &BVolume) +00805 { +00806 std::vector<NLMISC::CPlane> BVolumeCopy; +00807 BVolumeCopy.resize (BVolume.size()); +00808 <font class="keywordflow">for</font> (<font class="keywordtype">int</font> i=0; i<(int)BVolumeCopy.size(); i++) +00809 { +00810 BVolumeCopy[i]=BVolume[i]*((_ChangeBasis).inverted()); +00811 } +00812 +00813 <a class="code" href="classNL3D_1_1CQuadTree.html#z2_0">clearSelection</a>(); +00814 <a class="code" href="classNL3D_1_1CQuadTree.html#o0">_QuadRoot</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CQuadNode.html#a12">select</a>(<a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>, BVolumeCopy); +00815 } +00816 <font class="comment">// ============================================================================================</font> +<a name="l00817"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_4">00817</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::selectRay(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& source, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& dir) +00818 { +00819 <a class="code" href="classNLMISC_1_1CMatrix.html">NLMISC::CMatrix</a> mat; +00820 mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z290_0">identity</a> (); +00821 +00822 <font class="comment">// Set a wrong matrix</font> +00823 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> vTmp=dir^((fabs(vTmp*CVector(1,0,0))>0.f)?CVector(1,0,0):CVector(0,1,0)); +00824 mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z290_1">setRot</a> (dir, vTmp, dir^vTmp); +00825 +00826 <font class="comment">// Normalize it Yoyo!</font> +00827 mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z293_8">normalize</a> (<a class="code" href="classNLMISC_1_1CMatrix.html#s6s0">NLMISC::CMatrix::XYZ</a>); +00828 +00829 <font class="comment">// Get the planes..</font> +00830 std::vector<NLMISC::CPlane> BVolume; +00831 BVolume.reserve (4); +00832 +00833 <font class="comment">// Setup the planes</font> +00834 <a class="code" href="classNLMISC_1_1CPlane.html">NLMISC::CPlane</a> plane; +00835 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_8">getJ</a>(), source); +00836 BVolume.push_back (plane); +00837 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_9">getK</a>(), source); +00838 BVolume.push_back (plane); +00839 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (-mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_8">getJ</a>(), source); +00840 BVolume.push_back (plane); +00841 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (-mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_9">getK</a>(), source); +00842 BVolume.push_back (plane); +00843 +00844 <font class="comment">// Select the nodes</font> +00845 <a class="code" href="classNL3D_1_1CQuadTree.html#z2_2">select</a> (BVolume); +00846 } +00847 <font class="comment">// ============================================================================================</font> +<a name="l00848"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_5">00848</a> <font class="keyword">template</font><<font class="keyword">class</font> T> <font class="keywordtype">void</font> CQuadTree<T>::selectSegment(<font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& source, <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a>& dest) +00849 { +00850 <a class="code" href="classNLMISC_1_1CMatrix.html">NLMISC::CMatrix</a> mat; +00851 mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z290_0">identity</a> (); +00852 +00853 <font class="comment">// Set a wrong matrix</font> +00854 CVector dir=dest-source; +00855 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> vTmp=dir^((fabs(vTmp*CVector(1,0,0))>0.f)?CVector(1,0,0):CVector(0,1,0)); +00856 mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z290_1">setRot</a> (dir, vTmp, dir^vTmp); +00857 +00858 <font class="comment">// Normalize it Yoyo!</font> +00859 mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z293_8">normalize</a> (<a class="code" href="classNLMISC_1_1CMatrix.html#s6s0">NLMISC::CMatrix::XYZ</a>); +00860 +00861 <font class="comment">// Get the planes..</font> +00862 std::vector<NLMISC::CPlane> BVolume; +00863 BVolume.reserve (4); +00864 +00865 <font class="comment">// Setup the planes</font> +00866 <a class="code" href="classNLMISC_1_1CPlane.html">NLMISC::CPlane</a> plane; +00867 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_8">getJ</a>(), source); +00868 BVolume.push_back (plane); +00869 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_9">getK</a>(), source); +00870 BVolume.push_back (plane); +00871 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (-mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_8">getJ</a>(), source); +00872 BVolume.push_back (plane); +00873 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (-mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_9">getK</a>(), source); +00874 BVolume.push_back (plane); +00875 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_7">getI</a>(), dest); +00876 BVolume.push_back (plane); +00877 plane.<a class="code" href="classNLMISC_1_1CPlane.html#z305_0">make</a> (-mat.<a class="code" href="classNLMISC_1_1CMatrix.html#z291_7">getI</a>(), source); +00878 BVolume.push_back (plane); +00879 +00880 <font class="comment">// Select the nodes</font> +00881 <a class="code" href="classNL3D_1_1CQuadTree.html#z2_2">select</a> (BVolume); +00882 } +00883 <font class="comment">// ============================================================================================</font> +<a name="l00884"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_6">00884</a> <font class="keyword">template</font><<font class="keyword">class</font> T> CQuadTree<T>::CIterator CQuadTree<T>::begin() +00885 { +00886 <font class="keywordflow">return</font> (CNode*)(<a class="code" href="classNL3D_1_1CQuadTree.html#o1">_Selection</a>.<a class="code" href="classNL3D_1_1CQuadTree_1_1CBaseNode.html#m1">Next</a>); +00887 } +00888 <font class="comment">// ============================================================================================</font> +<a name="l00889"></a><a class="code" href="classNL3D_1_1CQuadTree.html#z2_7">00889</a> <font class="keyword">template</font><<font class="keyword">class</font> T> CQuadTree<T>::CIterator CQuadTree<T>::end() +00890 { +00891 <font class="keywordflow">return</font> <a class="code" href="classNL3D_1_1CQuadTree.html#l0">CIterator</a>(NULL); +00892 } +00893 +00894 +00895 } +00896 +00897 <font class="preprocessor">#endif</font> +00898 <font class="preprocessor"></font> +</pre></div> + +<!-- footer --> +<BR><FONT Size=+5> </FONT> +</TD> +<TD WIDTH=15><IMG SRC=http://www.nevrax.org/inc/img/pixel.gif WIDTH=15 HEIGHT=15 BORDER=0 ALT=""></TD> +</TR> +</TABLE> +</BODY> +</HTML> |