diff options
Diffstat (limited to '')
| -rw-r--r-- | docs/doxygen/nel/polygon_8cpp-source.html | 1431 |
1 files changed, 1431 insertions, 0 deletions
diff --git a/docs/doxygen/nel/polygon_8cpp-source.html b/docs/doxygen/nel/polygon_8cpp-source.html new file mode 100644 index 00000000..d6fb8b63 --- /dev/null +++ b/docs/doxygen/nel/polygon_8cpp-source.html @@ -0,0 +1,1431 @@ +<!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>polygon.cpp</h1><a href="polygon_8cpp.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 <font class="preprocessor">#include "<a class="code" href="stdmisc_8h.html">stdmisc.h</a>"</font> +00027 +00028 <font class="preprocessor">#include "<a class="code" href="polygon_8h.html">nel/misc/polygon.h</a>"</font> +00029 <font class="preprocessor">#include "<a class="code" href="plane_8h.html">nel/misc/plane.h</a>"</font> +00030 <font class="preprocessor">#include "<a class="code" href="triangle_8h.html">nel/misc/triangle.h</a>"</font> +00031 +00032 +00033 <font class="keyword">using</font> <font class="keyword">namespace </font>std; +00034 <font class="keyword">using</font> <font class="keyword">namespace </font>NLMISC; +00035 +00036 +00037 <font class="keyword">namespace </font>NLMISC +00038 { +00039 +00040 +00041 <font class="comment">//==================================//</font> +00042 <font class="comment">// CPolygon implementation //</font> +00043 <font class="comment">//==================================//</font> +00044 +00045 <font class="comment">// ***************************************************************************</font> +<a name="l00046"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a1">00046</a> CPolygon::CPolygon(<font class="keyword">const</font> CVector &a, <font class="keyword">const</font> CVector &b, <font class="keyword">const</font> CVector &c) +00047 { +00048 <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.reserve(3); +00049 <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.push_back(a); +00050 <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.push_back(b); +00051 <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.push_back(c); +00052 } +00053 +00054 +00055 <font class="comment">// ***************************************************************************</font> +<a name="l00056"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a3">00056</a> <font class="keywordtype">void</font> CPolygon::clip(<font class="keyword">const</font> CPlane *planes, uint nPlanes) +00057 { +00058 <font class="keywordflow">if</font>(nPlanes==0 || <a class="code" href="classNLMISC_1_1CPolygon.html#a2">getNumVertices</a>()==0) +00059 <font class="keywordflow">return</font>; +00060 +00061 <font class="comment">// The final polygon has at maximum currentVertices+number of clipping planes.</font> +00062 <font class="comment">// For performance, the vectors are static, so reallocation rarely occurs.</font> +00063 <font class="keyword">static</font> vector<CVector> tab0, tab1; +00064 tab0.resize(<a class="code" href="classNLMISC_1_1CPolygon.html#a2">getNumVertices</a>()+nPlanes); +00065 tab1.resize(<a class="code" href="classNLMISC_1_1CPolygon.html#a2">getNumVertices</a>()+nPlanes); +00066 <font class="comment">// Init tab0 with Vertices.</font> +00067 copy(<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.begin(), <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.end(), tab0.begin()); +00068 CVector *<a class="code" href="driver__opengl__extension__def_8h.html#a404">in</a>=&(*tab0.begin()), *out= &(*tab1.begin()); +00069 sint nin= <a class="code" href="classNLMISC_1_1CPolygon.html#a2">getNumVertices</a>(), nout; +00070 <font class="keywordflow">for</font>(sint i=0;i<(sint)nPlanes;i++) +00071 { +00072 nout= planes[i].clipPolygonBack(<a class="code" href="driver__opengl__extension__def_8h.html#a404">in</a>, out, nin); +00073 swap(<a class="code" href="driver__opengl__extension__def_8h.html#a404">in</a>, out); +00074 nin= nout; +00075 <font class="keywordflow">if</font>(nin==0) +00076 <font class="keywordflow">break</font>; +00077 } +00078 +00079 <font class="comment">// Final result in "in".</font> +00080 <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.resize(nin); +00081 <font class="keywordflow">if</font>(nin>0) +00082 { +00083 memcpy(&(*<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.begin()), <a class="code" href="driver__opengl__extension__def_8h.html#a404">in</a>, nin*<font class="keyword">sizeof</font>(CVector)); +00084 } +00085 } +00086 +00087 +00088 <font class="comment">// ***************************************************************************</font> +<a name="l00089"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a4">00089</a> <font class="keywordtype">void</font> CPolygon::clip(<font class="keyword">const</font> std::vector<CPlane> &planes) +00090 { +00091 <font class="keywordflow">if</font>(planes.size()==0) +00092 <font class="keywordflow">return</font>; +00093 <a class="code" href="classNLMISC_1_1CPolygon.html#a3">clip</a>(&(*planes.begin()), planes.size()); +00094 } +00095 +00096 +00097 +00098 <font class="comment">// ***************************************************************************</font> +<a name="l00099"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a5">00099</a> <font class="keywordtype">void</font> CPolygon::serial(<a class="code" href="classNLMISC_1_1IStream.html">NLMISC::IStream</a> &f) <font class="keywordflow">throw</font>(NLMISC::EStream) +00100 { +00101 f.serialVersion(0); +00102 f.serialCont(Vertices); +00103 } +00104 +00105 <font class="comment">// ***************************************************************************</font> +<a name="l00106"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a8">00106</a> <font class="keywordtype">void</font> CPolygon::getBestTriplet(uint &index0,uint &index1,uint &index2) +00107 { +00108 <a class="code" href="debug_8h.html#a6">nlassert</a>(<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size() >= 3); +00109 uint i, j, k; +00110 <font class="keywordtype">float</font> bestArea = 0.f; +00111 <font class="keyword">const</font> uint numVerts = <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size(); +00112 <font class="keywordflow">for</font> (i = 0; i < numVerts; ++i) +00113 { +00114 <font class="keywordflow">for</font> (j = 0; j < numVerts; ++j) +00115 { +00116 <font class="keywordflow">if</font> (i != j) +00117 { +00118 <font class="keywordflow">for</font> (k = 0; k < numVerts; ++k) +00119 { +00120 <font class="keywordflow">if</font> (k != i && k != j) +00121 { +00122 CVector v0 = <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[j] - <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i]; +00123 CVector v1 = <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[k] - <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i]; +00124 <font class="keywordtype">float</font> area = (v0 ^ v1).norm(); +00125 <font class="keywordflow">if</font> (area > bestArea) +00126 { +00127 bestArea = area; +00128 index0 = i; +00129 index1 = j; +00130 index2 = k; +00131 } +00132 } +00133 } +00134 } +00135 } +00136 } +00137 +00138 } +00139 +00140 <font class="comment">// ***************************************************************************</font> +<a name="l00141"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a9">00141</a> <font class="keywordtype">void</font> CPolygon::buildBasis(CMatrix &dest) +00142 { +00143 <a class="code" href="debug_8h.html#a6">nlassert</a>(<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size() > 3); +00144 uint i1, i2, i3; +00145 <a class="code" href="classNLMISC_1_1CPolygon.html#a8">getBestTriplet</a>(i1, i2, i3); +00146 CVector v1 = (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i2] - <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i1]).normed(); +00147 CVector v2 = (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i3] - <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i1]).normed(); +00148 CVector K = v2 ^ v1; +00149 CVector I = v1 - (v1 * K) * v1; +00150 CVector J = K ^ I; +00151 dest.setRot(I, J, K); +00152 dest.setPos(<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i1]); +00153 } +00154 +00155 <font class="comment">// ***************************************************************************</font> +00156 +<a name="l00157"></a><a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html">00157</a> <font class="keyword">class </font>CConcavePolygonsVertexDesc +00158 { +00159 <font class="keyword">public</font>: +00160 +<a name="l00161"></a><a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#a0">00161</a> <a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#a0">CConcavePolygonsVertexDesc</a> (<font class="keywordtype">float</font> length, uint <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>) +00162 { +00163 <a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#m0">Length</a> = length; +00164 <a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#m1">Index</a> = <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>; +00165 } +00166 +00167 <font class="comment">// Length > 0</font> +<a name="l00168"></a><a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#m0">00168</a> <font class="keywordtype">float</font> <a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#m0">Length</a>; +00169 +00170 <font class="comment">// First vertex index</font> +<a name="l00171"></a><a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#m1">00171</a> uint <a class="code" href="classNLMISC_1_1CConcavePolygonsVertexDesc.html#m1">Index</a>; +00172 }; +00173 <font class="keyword">typedef</font> std::map<float, CConcavePolygonsVertexDesc> <a class="code" href="namespaceNLMISC.html#a199">TCConcavePolygonsVertexMap</a>; +00174 +00175 <font class="comment">// ***************************************************************************</font> +00176 +<a name="l00177"></a><a class="code" href="classNLMISC_1_1CPolygon.html#d0">00177</a> <font class="keywordtype">bool</font> CPolygon::toConvexPolygonsEdgeIntersect (<font class="keyword">const</font> CVector2f& a0, <font class="keyword">const</font> CVector2f& a1, <font class="keyword">const</font> CVector2f& b0, <font class="keyword">const</font> CVector2f& b1) +00178 { +00179 <font class="keywordtype">float</font> Aa = (a0.y - a1.y) / (a0.x - a1.x); +00180 <font class="keywordtype">float</font> Ba = a0.y - a0.x * Aa; +00181 <font class="keywordtype">float</font> Ab = (b0.y - b1.y) / (b0.x - b1.x); +00182 <font class="keywordtype">float</font> Bb = b0.y - b0.x * Ab; +00183 +00184 <font class="comment">// Intersection </font> +00185 CVector2f intersection; +00186 intersection.x = (Bb - Ba) / (Aa - Ab); +00187 intersection.y = Aa * intersection.x + Ba; +00188 +00189 <font class="comment">// In it ?</font> +00190 <font class="keywordflow">return</font> ( ( (a0-intersection)*(a1-intersection) < 0 ) && ( (b0-intersection)*(b1-intersection) < 0 ) ); +00191 } +00192 +00193 <font class="comment">// ***************************************************************************</font> +00194 +<a name="l00195"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html">00195</a> <font class="keyword">class </font>CBSPNode2v +00196 { +00197 <font class="keyword">public</font>: +<a name="l00198"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">00198</a> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">CBSPNode2v</a> () +00199 { +00200 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a> = NULL; +00201 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a> = NULL; +00202 } +<a name="l00203"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#a1">00203</a> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">CBSPNode2v</a> ( <font class="keyword">const</font> CPlane &plane, CVector p0, CVector p1, uint v0, uint v1 ) : <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a> (plane), <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m4">P0</a> (p0), <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m5">P1</a> (p1) +00204 { +00205 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a> = NULL; +00206 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a> = NULL; +00207 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m2">Parent</a> = NULL; +00208 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m6">V0</a> = v0; +00209 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m7">V1</a> = v1; +00210 } +<a name="l00211"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#a2">00211</a> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a2">~CBSPNode2v</a> () +00212 { +00213 <font class="keywordflow">if</font> (Front) +00214 <font class="keyword">delete</font> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a>; +00215 <font class="keywordflow">if</font> (Back) +00216 <font class="keyword">delete</font> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a>; +00217 } +00218 +<a name="l00219"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#a3">00219</a> <font class="keywordtype">void</font> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a3">insert</a> (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">CBSPNode2v</a> *node) +00220 { +00221 <font class="comment">// Front ?</font> +00222 <font class="keywordtype">bool</font> p0Front = (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a> * node->P0) > 0; +00223 <font class="keywordtype">bool</font> p1Front = (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a> * node->P1) > 0; +00224 <font class="keywordflow">if</font> (p0Front && p1Front) +00225 { +00226 <font class="comment">// Front child ?</font> +00227 <font class="keywordflow">if</font> (Front) +00228 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a>->insert (node); +00229 <font class="keywordflow">else</font> +00230 { +00231 <font class="comment">// Link left</font> +00232 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a> = node; +00233 node->Parent = <font class="keyword">this</font>; +00234 } +00235 } +00236 <font class="keywordflow">else</font> <font class="keywordflow">if</font> ((!p0Front) && (!p1Front)) +00237 { +00238 <font class="comment">// Back child ?</font> +00239 <font class="keywordflow">if</font> (Back) +00240 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a>->insert (node); +00241 <font class="keywordflow">else</font> +00242 { +00243 <font class="comment">// Link left</font> +00244 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a> = node; +00245 node->Parent = <font class="keyword">this</font>; +00246 } +00247 } +00248 <font class="keywordflow">else</font> +00249 { +00250 <font class="comment">// Split vertex</font> +00251 CVector newVertex = <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a>.intersect (node->P0, node->P1); +00252 +00253 <font class="comment">// New node</font> +00254 <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">CBSPNode2v</a> *newNode = <font class="keyword">new</font> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">CBSPNode2v</a> (node->Plane, node->P0, newVertex, node->V0, node->V1); +00255 +00256 <font class="comment">// Old node</font> +00257 node->P0 = newVertex; +00258 +00259 <font class="comment">// Insert child</font> +00260 CBSPNode2v **p0Parent; +00261 CBSPNode2v **p1Parent; +00262 +00263 <font class="comment">// Get insertion pointer</font> +00264 <font class="keywordflow">if</font> (p0Front) +00265 { +00266 p0Parent = &<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a>; +00267 p1Parent = &<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a>; +00268 } +00269 <font class="keywordflow">else</font> +00270 { +00271 p0Parent = &<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a>; +00272 p1Parent = &<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a>; +00273 } +00274 +00275 <font class="comment">// Insert children</font> +00276 <font class="keywordflow">if</font> (*p0Parent) +00277 { +00278 (*p0Parent)->insert (newNode); +00279 } +00280 <font class="keywordflow">else</font> +00281 { +00282 *p0Parent = newNode; +00283 newNode->Parent = <font class="keyword">this</font>; +00284 } +00285 +00286 <font class="comment">// Insert children</font> +00287 <font class="keywordflow">if</font> (*p1Parent) +00288 { +00289 (*p1Parent)->insert (node); +00290 } +00291 <font class="keywordflow">else</font> +00292 { +00293 *p1Parent = node; +00294 node->Parent = <font class="keyword">this</font>; +00295 } +00296 } +00297 } +00298 +<a name="l00299"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#a4">00299</a> <font class="keywordtype">bool</font> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a4">intersect</a> (<font class="keyword">const</font> CVector &p0, <font class="keyword">const</font> CVector &p1, uint v0, uint v1)<font class="keyword"> const</font> +00300 <font class="keyword"> </font>{ +00301 <font class="comment">// Front ?</font> +00302 <font class="keywordtype">bool</font> p0Front = (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a> * p0) > 0; +00303 <font class="keywordtype">bool</font> p1Front = (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a> * p1) > 0; +00304 +00305 <font class="keywordflow">if</font> (p0Front != p1Front) +00306 <font class="keywordflow">if</font> ( (v0 != <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m6">V0</a>) && (v0 != <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m7">V1</a>) && (v1 != <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m6">V0</a>) && (v1 != <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m7">V1</a>) ) +00307 <font class="keywordflow">if</font> (CPolygon::toConvexPolygonsEdgeIntersect ((CVector2f) <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m4">P0</a>, (CVector2f) <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m5">P1</a>, (CVector2f) p0, (CVector2f) p1)) +00308 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00309 +00310 <font class="keywordflow">if</font> (p0Front || p1Front) +00311 { +00312 <font class="keywordflow">if</font> (Front) +00313 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a>->intersect (p0, p1, v0, v1)) +00314 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00315 } +00316 +00317 <font class="keywordflow">if</font> ((!p0Front) || (!p1Front)) +00318 { +00319 <font class="keywordflow">if</font> (Back) +00320 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a>->intersect (p0, p1, v0, v1)) +00321 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00322 } +00323 +00324 <font class="keywordflow">return</font> <font class="keyword">false</font>; +00325 } +00326 +<a name="l00327"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#m2">00327</a> <a class="code" href="classNLMISC_1_1CBSPNode2v.html#a0">CBSPNode2v</a> *<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m0">Back</a>, *<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m1">Front</a>, *<a class="code" href="classNLMISC_1_1CBSPNode2v.html#m2">Parent</a>; +<a name="l00328"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">00328</a> CPlane <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m3">Plane</a>; +<a name="l00329"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#m4">00329</a> CVector <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m4">P0</a>; +<a name="l00330"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#m5">00330</a> CVector <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m5">P1</a>; +<a name="l00331"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#m6">00331</a> uint <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m6">V0</a>; +<a name="l00332"></a><a class="code" href="classNLMISC_1_1CBSPNode2v.html#m7">00332</a> uint <a class="code" href="classNLMISC_1_1CBSPNode2v.html#m7">V1</a>; +00333 }; +00334 +00335 <font class="comment">// ***************************************************************************</font> +00336 +<a name="l00337"></a><a class="code" href="classNLMISC_1_1CPolygon.html#d1">00337</a> <font class="keywordtype">bool</font> CPolygon::toConvexPolygonsLeft (<font class="keyword">const</font> std::vector<CVector> &vertex, uint a, uint b, uint c) +00338 { +00339 <font class="keywordflow">return</font> ( (vertex[b].x - vertex[a].x) * (vertex[c].y - vertex[a].y) - (vertex[c].x - vertex[a].x) * (vertex[b].y - vertex[a].y) ) < 0; +00340 } +00341 +00342 <font class="comment">// ***************************************************************************</font> +00343 +<a name="l00344"></a><a class="code" href="classNLMISC_1_1CPolygon.html#d2">00344</a> <font class="keywordtype">bool</font> CPolygon::toConvexPolygonsLeftOn (<font class="keyword">const</font> std::vector<CVector> &vertex, uint a, uint b, uint c) +00345 { +00346 <font class="keywordflow">return</font> ( (vertex[b].x - vertex[a].x) * (vertex[c].y - vertex[a].y) - (vertex[c].x - vertex[a].x) * (vertex[b].y - vertex[a].y) ) <= 0; +00347 } +00348 +00349 <font class="comment">// ***************************************************************************</font> +00350 +<a name="l00351"></a><a class="code" href="classNLMISC_1_1CPolygon.html#d3">00351</a> <font class="keywordtype">bool</font> CPolygon::toConvexPolygonsInCone (<font class="keyword">const</font> std::vector<CVector> &vertex, uint a, uint b) +00352 { +00353 <font class="comment">// Prev and next</font> +00354 uint a0 = a+1; +00355 <font class="keywordflow">if</font> (a0==vertex.size()) +00356 a0=0; +00357 uint a1; +00358 <font class="keywordflow">if</font> (a==0) +00359 a1=vertex.size()-1; +00360 <font class="keywordflow">else</font> +00361 a1= a-1; +00362 +00363 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon.html#d2">toConvexPolygonsLeftOn</a> (vertex, a, a1, a0) ) +00364 { +00365 <font class="keywordflow">return</font> <a class="code" href="classNLMISC_1_1CPolygon.html#d1">toConvexPolygonsLeft</a> ( vertex, a, b, a0) && <a class="code" href="classNLMISC_1_1CPolygon.html#d1">toConvexPolygonsLeft</a> ( vertex, b, a, a1); +00366 } +00367 <font class="keywordflow">else</font> +00368 { +00369 <font class="keywordflow">return</font> !( <a class="code" href="classNLMISC_1_1CPolygon.html#d1">toConvexPolygonsLeft</a> ( vertex, a, b, a1) && <a class="code" href="classNLMISC_1_1CPolygon.html#d1">toConvexPolygonsLeft</a> ( vertex, b, a, a0) ); +00370 } +00371 } +00372 +00373 <font class="comment">// ***************************************************************************</font> +00374 +<a name="l00375"></a><a class="code" href="classNLMISC_1_1CPolygon.html#d4">00375</a> <font class="keywordtype">bool</font> CPolygon::toConvexPolygonsDiagonal (<font class="keyword">const</font> std::vector<CVector> &vertex, <font class="keyword">const</font> CBSPNode2v &bsp, uint a, uint b) +00376 { +00377 <font class="comment">// Check it is a border</font> +00378 <font class="keywordflow">if</font> ( ( (b - a) == 1) || ( (a - b) == 1) || ( (a==0) && (b ==(vertex.size()-1))) || ( (b==0) && (a ==(vertex.size()-1))) ) +00379 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00380 +00381 <font class="comment">// Check visibility</font> +00382 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon.html#d3">toConvexPolygonsInCone</a> (vertex, a, b) && <a class="code" href="classNLMISC_1_1CPolygon.html#d3">toConvexPolygonsInCone</a> (vertex, b, a)) +00383 { +00384 <font class="comment">// Intersection ?</font> +00385 <font class="keywordflow">return</font> !bsp.intersect (vertex[a], vertex[b], a, b); +00386 } +00387 <font class="keywordflow">return</font> <font class="keyword">false</font>; +00388 } +00389 +00390 <font class="comment">// ***************************************************************************</font> +00391 +<a name="l00392"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a10">00392</a> <font class="keywordtype">void</font> CPolygon::toConvexPolygonsLocalAndBSP (std::vector<CVector> &localVertices, CBSPNode2v &root, <font class="keyword">const</font> CMatrix &basis)<font class="keyword"> const</font> +00393 <font class="keyword"></font>{ +00394 <font class="comment">// Invert matrix</font> +00395 CMatrix invert = basis; +00396 invert.invert (); +00397 +00398 <font class="comment">// Insert vertices in an ordered table</font> +00399 uint vertexCount = <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size(); +00400 <a class="code" href="namespaceNLMISC.html#a199">TCConcavePolygonsVertexMap</a> vertexMap; +00401 localVertices.resize (vertexCount); +00402 uint i, j; +00403 +00404 <font class="comment">// Transform the vertex</font> +00405 <font class="keywordflow">for</font> (i=0; i<vertexCount; i++) +00406 { +00407 CVector local = invert*<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[i]; +00408 localVertices[i] = CVector (local.x, local.y, 0); +00409 } +00410 +00411 <font class="comment">// Plane direction</font> +00412 i=0; +00413 j=<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size()-1; +00414 CVector normal = localVertices[i] - localVertices[j]; +00415 normal = normal ^ CVector::K; +00416 CPlane clipPlane; +00417 clipPlane.make(normal, localVertices[i]); +00418 +00419 <font class="comment">// Build the BSP root</font> +00420 root = CBSPNode2v (clipPlane, localVertices[i], localVertices[j], i, j); +00421 +00422 <font class="comment">// Insert all others edges</font> +00423 j=i++; +00424 <font class="keywordflow">for</font> (; i<<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size(); i++) +00425 { +00426 <font class="comment">// Plane direction</font> +00427 normal = localVertices[i] - localVertices[j]; +00428 normal = normal ^ CVector::K; +00429 clipPlane.make(normal, localVertices[i]); +00430 +00431 <font class="comment">// Build the BSP root</font> +00432 root.insert ( <font class="keyword">new</font> CBSPNode2v (clipPlane, localVertices[i], localVertices[j], i, j) ); +00433 +00434 j=i; +00435 } +00436 } +00437 +00438 <font class="comment">// ***************************************************************************</font> +00439 +<a name="l00440"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a6">00440</a> <font class="keywordtype">bool</font> CPolygon::toConvexPolygons (<a class="code" href="classstd_1_1list.html">std::list<CPolygon></a>& outputPolygons, <font class="keyword">const</font> CMatrix& basis)<font class="keyword"> const</font> +00441 <font class="keyword"></font>{ +00442 <font class="comment">// Some vertices ?</font> +00443 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size()>2) +00444 { +00445 <font class="comment">// Local vertices</font> +00446 std::vector<CVector> localVertices; +00447 +00448 <font class="comment">// Build the BSP root</font> +00449 CBSPNode2v root; +00450 +00451 <font class="comment">// Build the local array and the BSP</font> +00452 <a class="code" href="classNLMISC_1_1CPolygon.html#a10">toConvexPolygonsLocalAndBSP</a> (localVertices, root, basis); +00453 +00454 <font class="comment">// Build a vertex list</font> +00455 <a class="code" href="classstd_1_1list.html">std::list<uint></a> vertexList; +00456 uint i; +00457 <font class="keywordflow">for</font> (i=0; i<<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size(); i++) +00458 vertexList.push_back (i); +00459 +00460 <font class="comment">// Clip ears while there is some polygons</font> +00461 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator current=vertexList.begin(); +00462 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator begin=vertexList.begin(); +00463 <font class="keywordflow">do</font> +00464 { +00465 again:; +00466 <font class="comment">// Search for a diagonal</font> +00467 <font class="keywordtype">bool</font> found = <font class="keyword">false</font>; +00468 +00469 <font class="comment">// Get next vertex</font> +00470 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator first = current; +00471 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator lastPreviousPrevious=current; +00472 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator lastPrevious=current; +00473 lastPrevious++; +00474 <font class="keywordflow">if</font> (lastPrevious==vertexList.end()) +00475 lastPrevious = vertexList.begin(); +00476 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator currentNext = lastPrevious; +00477 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator last = lastPrevious; +00478 last++; +00479 <font class="keywordflow">if</font> (last==vertexList.end()) +00480 last = vertexList.begin(); +00481 <font class="keywordflow">while</font> (last != current) +00482 { +00483 <font class="comment">// Is a diagonal ?</font> +00484 <font class="keywordflow">if</font> ( +00485 (<a class="code" href="classNLMISC_1_1CPolygon.html#d4">toConvexPolygonsDiagonal</a> (localVertices, root, *lastPreviousPrevious, *last)) && +00486 (<a class="code" href="classNLMISC_1_1CPolygon.html#d4">toConvexPolygonsDiagonal</a> (localVertices, root, *currentNext, *last)) && +00487 (<a class="code" href="classNLMISC_1_1CPolygon.html#d4">toConvexPolygonsDiagonal</a> (localVertices, root, *last, *current)) +00488 ) +00489 { +00490 <font class="comment">// Find one</font> +00491 found = <font class="keyword">true</font>; +00492 } +00493 <font class="keywordflow">else</font> +00494 { +00495 <font class="comment">// Come back</font> +00496 last = lastPrevious; +00497 lastPrevious = lastPreviousPrevious; +00498 <font class="keywordflow">break</font>; +00499 } +00500 +00501 <font class="comment">// Next vertex</font> +00502 lastPreviousPrevious = lastPrevious; +00503 lastPrevious = last++; +00504 <font class="keywordflow">if</font> (last==vertexList.end()) +00505 last = vertexList.begin(); +00506 } +00507 +00508 <font class="comment">// Last polygon ?</font> +00509 <font class="keywordflow">if</font> (last==current) +00510 { +00511 <font class="comment">// Add a polygon</font> +00512 outputPolygons.push_back (<a class="code" href="classNLMISC_1_1CPolygon.html#a0">CPolygon</a>()); +00513 <a class="code" href="classNLMISC_1_1CPolygon.html#a0">CPolygon</a> &back = outputPolygons.back (); +00514 back.Vertices.reserve (vertexList.size()); +00515 +00516 <font class="comment">// Add each vertex in the new polygon</font> +00517 current=vertexList.begin(); +00518 <font class="keywordflow">while</font> (current!=vertexList.end()) +00519 { +00520 back.Vertices.push_back (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[*current]); +00521 current++; +00522 } +00523 +00524 <font class="comment">// Exit</font> +00525 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00526 } +00527 <font class="keywordflow">else</font> +00528 { +00529 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator firstNext = current; +00530 <a class="code" href="classstd_1_1list.html">std::list<uint></a>::iterator firstNextNext = currentNext; +00531 <font class="keywordflow">if</font> (first != vertexList.begin()) +00532 first--; +00533 <font class="keywordflow">else</font> +00534 { +00535 first = vertexList.end(); +00536 first--; +00537 } +00538 +00539 <font class="keywordflow">while</font> (current != first) +00540 { +00541 <font class="comment">// Is a diagonal ?</font> +00542 <font class="keywordflow">if</font> ( +00543 (<a class="code" href="classNLMISC_1_1CPolygon.html#d4">toConvexPolygonsDiagonal</a> (localVertices, root, *firstNextNext, *first)) && +00544 (<a class="code" href="classNLMISC_1_1CPolygon.html#d4">toConvexPolygonsDiagonal</a> (localVertices, root, *lastPrevious, *first)) && +00545 (<a class="code" href="classNLMISC_1_1CPolygon.html#d4">toConvexPolygonsDiagonal</a> (localVertices, root, *last, *first)) +00546 ) +00547 { +00548 <font class="comment">// Find one</font> +00549 found = <font class="keyword">true</font>; +00550 } +00551 <font class="keywordflow">else</font> +00552 { +00553 <font class="comment">// Come back</font> +00554 first = firstNext; +00555 <font class="keywordflow">break</font>; +00556 } +00557 +00558 <font class="comment">// Next vertex</font> +00559 firstNextNext = firstNext; +00560 firstNext = first; +00561 <font class="keywordflow">if</font> (first==vertexList.begin()) +00562 { +00563 first = vertexList.end(); +00564 first--; +00565 } +00566 <font class="keywordflow">else</font> +00567 first--; +00568 } +00569 } +00570 +00571 <font class="comment">// Found ?</font> +00572 <font class="keywordflow">if</font> (found) +00573 { +00574 <font class="comment">// Count vertex</font> +00575 outputPolygons.push_back (<a class="code" href="classNLMISC_1_1CPolygon.html#a0">CPolygon</a>()); +00576 <a class="code" href="classNLMISC_1_1CPolygon.html#a0">CPolygon</a> &back = outputPolygons.back (); +00577 +00578 <font class="comment">// Vertex count</font> +00579 uint vertexCount = 1; +00580 current = first; +00581 <font class="keywordflow">while</font> (current != last) +00582 { +00583 vertexCount++; +00584 current++; +00585 <font class="keywordflow">if</font> (current == vertexList.end()) +00586 current = vertexList.begin(); +00587 } +00588 +00589 <font class="comment">// Alloc vertices</font> +00590 back.Vertices.reserve (vertexCount); +00591 +00592 <font class="comment">// Copy and remove vertices</font> +00593 back.Vertices.push_back (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[*first]); +00594 first++; +00595 <font class="keywordflow">if</font> (first == vertexList.end()) +00596 first = vertexList.begin(); +00597 <font class="keywordflow">while</font> (first != last) +00598 { +00599 back.Vertices.push_back (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[*first]); +00600 +00601 <font class="comment">// Remove from list</font> +00602 first = vertexList.erase (first); +00603 <font class="keywordflow">if</font> (first == vertexList.end()) +00604 first = vertexList.begin(); +00605 <a class="code" href="debug_8h.html#a6">nlassert</a> (first != vertexList.end()); +00606 } +00607 back.Vertices.push_back (<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>[*first]); +00608 current = begin = last; +00609 <font class="keywordflow">goto</font> again; +00610 } +00611 +00612 <font class="comment">// Next current</font> +00613 current++; +00614 <font class="keywordflow">if</font> (current == vertexList.end()) +00615 current = vertexList.begin (); +00616 } +00617 <font class="keywordflow">while</font> (current != begin); +00618 } +00619 <font class="keywordflow">return</font> <font class="keyword">false</font>; +00620 } +00621 +00622 <font class="comment">// ***************************************************************************</font> +00623 +<a name="l00624"></a><a class="code" href="classNLMISC_1_1CPolygon.html#a7">00624</a> <font class="keywordtype">bool</font> CPolygon::chain (<font class="keyword">const</font> std::vector<CPolygon> &other, <font class="keyword">const</font> CMatrix& basis) +00625 { +00626 <font class="comment">// Local vertices</font> +00627 std::vector<CVector> localVertices; +00628 +00629 <font class="comment">// Build the BSP root</font> +00630 CBSPNode2v root; +00631 +00632 <font class="comment">// Build the local array and the BSP</font> +00633 <a class="code" href="classNLMISC_1_1CPolygon.html#a10">toConvexPolygonsLocalAndBSP</a> (localVertices, root, basis); +00634 +00635 <font class="comment">// Local vertices</font> +00636 std::vector<std::vector<CVector> > localVerticesOther (other.size()); +00637 +00638 <font class="comment">// Build the BSP root</font> +00639 std::vector<CBSPNode2v> rootOther (other.size()); +00640 +00641 <font class="comment">// Build a copy of the polygons</font> +00642 std::vector<CPolygon> copy = other; +00643 +00644 <font class="comment">// Main copy</font> +00645 <a class="code" href="classNLMISC_1_1CPolygon.html#a0">CPolygon</a> mainCopy = *<font class="keyword">this</font>; +00646 +00647 <font class="comment">// For each other polygons</font> +00648 uint o; +00649 <font class="keywordflow">for</font> (o=0; o<other.size(); o++) +00650 { +00651 <font class="comment">// Build the local array and the BSP</font> +00652 other[o].toConvexPolygonsLocalAndBSP (localVerticesOther[o], rootOther[o], basis); +00653 } +00654 +00655 <font class="comment">// Look for a couple..</font> +00656 uint thisCount = <a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.size(); +00657 uint i, j; +00658 <font class="keywordflow">for</font> (o=0; o<other.size(); o++) +00659 { +00660 uint otherCount = other[o].Vertices.size(); +00661 +00662 <font class="comment">// Try to link in the main polygon</font> +00663 <font class="keywordflow">for</font> (i=0; i<thisCount; i++) +00664 { +00665 <font class="keywordflow">for</font> (j=0; j<otherCount; j++) +00666 { +00667 <font class="comment">// Test this segement</font> +00668 <font class="keywordflow">if</font> (!root.intersect (localVertices[i], localVerticesOther[o][j], i, 0xffffffff)) +00669 { +00670 <font class="comment">// Test each other polygons</font> +00671 uint otherO; +00672 <font class="keywordflow">for</font> (otherO=0; otherO<other.size(); otherO++) +00673 { +00674 <font class="comment">// Intersect ?</font> +00675 <font class="keywordflow">if</font> (rootOther[otherO].intersect (localVertices[i], localVerticesOther[o][j], 0xffffffff, (otherO == o)?j:0xffffffff)) +00676 <font class="keywordflow">break</font>; +00677 } +00678 +00679 <font class="comment">// Continue ?</font> +00680 <font class="keywordflow">if</font> (otherO==other.size()) +00681 { +00682 <font class="comment">// Insert new vertices</font> +00683 mainCopy.Vertices.insert (mainCopy.Vertices.begin()+i, 2+otherCount, CVector()); +00684 +00685 <font class="comment">// Copy the first vertex</font> +00686 mainCopy.Vertices[i] = mainCopy.Vertices[i+otherCount+2]; +00687 +00688 <font class="comment">// Copy the new vertices</font> +00689 uint k; +00690 <font class="keywordflow">for</font> (k=0; k<otherCount; k++) +00691 { +00692 uint <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> = j+k; +00693 <font class="keywordflow">if</font> (<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>>=otherCount) +00694 <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> -= otherCount; +00695 mainCopy.Vertices[i+k+1] = copy[o].Vertices[<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>]; +00696 } +00697 +00698 <font class="comment">// Copy the last one</font> +00699 mainCopy.Vertices[i+otherCount+1] = copy[o].Vertices[j]; +00700 <font class="keywordflow">break</font>; +00701 } +00702 } +00703 } +00704 <font class="keywordflow">if</font> (j!=otherCount) +00705 <font class="keywordflow">break</font>; +00706 } +00707 +00708 <font class="comment">// Not found ?</font> +00709 <font class="keywordflow">if</font> (i==thisCount) +00710 { +00711 <font class="comment">// Try to link in the sub polygons</font> +00712 uint otherToCheck; +00713 <font class="keywordflow">for</font> (otherToCheck=o+1; otherToCheck<other.size(); otherToCheck++) +00714 { +00715 uint otherToCheckCount = other[otherToCheck].Vertices.size(); +00716 <font class="keywordflow">for</font> (i=0; i<otherToCheckCount; i++) +00717 { +00718 <font class="keywordflow">for</font> (j=0; j<otherCount; j++) +00719 { +00720 <font class="comment">// Test this segement</font> +00721 <font class="keywordflow">if</font> (!rootOther[otherToCheck].intersect (localVerticesOther[otherToCheck][i], localVerticesOther[o][j], i, 0xffffffff)) +00722 { +00723 <font class="comment">// Test each other polygons</font> +00724 uint otherO; +00725 <font class="keywordflow">for</font> (otherO=0; otherO<other.size(); otherO++) +00726 { +00727 <font class="comment">// Intersect ?</font> +00728 <font class="keywordflow">if</font> (rootOther[otherO].intersect (localVerticesOther[otherToCheck][i], localVerticesOther[o][j], (otherToCheck == otherO)?i:0xffffffff, (otherO == o)?j:0xffffffff)) +00729 <font class="keywordflow">break</font>; +00730 } +00731 +00732 <font class="comment">// Continue ?</font> +00733 <font class="keywordflow">if</font> (otherO==other.size()) +00734 { +00735 <font class="comment">// Insert new vertices</font> +00736 copy[otherToCheck].Vertices.insert (copy[otherToCheck].<a class="code" href="classNLMISC_1_1CPolygon.html#m0">Vertices</a>.begin()+i, 2+otherCount, CVector()); +00737 +00738 <font class="comment">// Copy the first vertex</font> +00739 copy[otherToCheck].Vertices[i] = copy[otherToCheck].Vertices[i+otherCount+2]; +00740 +00741 <font class="comment">// Copy the new vertices</font> +00742 uint k; +00743 <font class="keywordflow">for</font> (k=0; k<otherCount; k++) +00744 { +00745 uint <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> = j+k; +00746 <font class="keywordflow">if</font> (<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>>=otherCount) +00747 <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> -= otherCount; +00748 copy[otherToCheck].Vertices[i+k+1] = copy[otherO].Vertices[<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>]; +00749 } +00750 +00751 <font class="comment">// Copy the last one</font> +00752 copy[otherToCheck].Vertices[i+otherCount+1] = copy[otherO].Vertices[j]; +00753 <font class="keywordflow">break</font>; +00754 } +00755 } +00756 } +00757 <font class="keywordflow">if</font> (j!=otherCount) +00758 <font class="keywordflow">break</font>; +00759 } +00760 <font class="keywordflow">if</font> (i!=otherToCheckCount) +00761 <font class="keywordflow">break</font>; +00762 } +00763 <font class="keywordflow">if</font> (otherToCheck==other.size()) +00764 { +00765 <font class="comment">// Not ok</font> +00766 <font class="keywordflow">return</font> <font class="keyword">false</font>; +00767 } +00768 } +00769 } +00770 +00771 <font class="comment">// Ok</font> +00772 *<font class="keyword">this</font> = mainCopy; +00773 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00774 } +00775 +00776 <font class="comment">// ***************************************************************************</font> +00777 +00778 +00779 <font class="comment">//====================================//</font> +00780 <font class="comment">// CPolygon2d implementation //</font> +00781 <font class="comment">//====================================//</font> +00782 +00783 +00784 +<a name="l00785"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a1">00785</a> CPolygon2D::CPolygon2D(<font class="keyword">const</font> CPolygon &<a class="code" href="driver__opengl__extension__def_8h.html#a409">src</a>, <font class="keyword">const</font> CMatrix &projMat) +00786 { +00787 uint size = <a class="code" href="driver__opengl__extension__def_8h.html#a409">src</a>.Vertices.size(); +00788 <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.resize(size); +00789 <font class="keywordflow">for</font> (uint k = 0; k < size; ++k) +00790 { +00791 CVector proj = projMat * <a class="code" href="driver__opengl__extension__def_8h.html#a409">src</a>.Vertices[k]; +00792 <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[k].set(proj.x, proj.y); +00793 } +00794 } +00795 +00796 <font class="comment">// ***************************************************************************</font> +00797 +<a name="l00798"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a3">00798</a> <font class="keywordtype">bool</font> CPolygon2D::isConvex() +00799 { +00800 <font class="keywordtype">bool</font> Front = <font class="keyword">true</font>, Back = <font class="keyword">false</font>; +00801 <font class="comment">// we apply a dummy algo for now : check wether every vertex is in the same side </font> +00802 <font class="comment">// of every plane defined by a segment of this poly</font> +00803 uint numVerts = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size(); +00804 <font class="keywordflow">if</font> (numVerts < 3) <font class="keywordflow">return</font> <font class="keyword">true</font>; +00805 CVector segStart, segEnd; +00806 CPlane clipPlane; +00807 <font class="keywordflow">for</font> (TVec2fVect::const_iterator it = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.begin(); it != <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.end(); ++it) +00808 { +00809 segStart.set(it->x, it->y, 0); <font class="comment">// segment start</font> +00810 segEnd.set((it + 1)-><a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>, (it + 1)-><a class="code" href="driver__opengl__extension__def_8h.html#a365">y</a>, 0); <font class="comment">// segment end</font> +00811 <font class="keywordtype">float</font> n = (segStart - segEnd).norm(); <font class="comment">// segment norm</font> +00812 <font class="keywordflow">if</font> (n != 0) +00813 { +00814 clipPlane.make(segStart, segEnd, (n > 10 ? n : 10) * CVector::K + segStart); <font class="comment">// make a plane, with this segment and the poly normal</font> +00815 <font class="comment">// check each other vertices against this plane</font> +00816 <font class="keywordflow">for</font> (TVec2fVect::const_iterator it2 = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.begin(); it2 != <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.end(); ++it2) +00817 { +00818 <font class="keywordflow">if</font> (it2 != it && it2 != (it + 1)) <font class="comment">// the vertices must not be part of the test plane (because of imprecision)</font> +00819 { +00820 +00821 <font class="keywordtype">float</font> dist = clipPlane * CVector(it2->x, it2-> <a class="code" href="driver__opengl__extension__def_8h.html#a365">y</a>, 0); +00822 <font class="keywordflow">if</font> (dist != 0) <font class="comment">// midlle pos</font> +00823 { +00824 <font class="keywordflow">if</font> (dist > 0) Front = <font class="keyword">true</font>; <font class="keywordflow">else</font> Back = <font class="keyword">true</font>; +00825 <font class="keywordflow">if</font> (Front && Back) <font class="keywordflow">return</font> <font class="keyword">false</font>; <font class="comment">// there are both front end back vertices -> failure</font> +00826 } +00827 } +00828 } +00829 } +00830 } +00831 <font class="keywordflow">return</font> <font class="keyword">true</font>; +00832 } +00833 +00834 <font class="comment">// ***************************************************************************</font> +00835 +<a name="l00836"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a4">00836</a> <font class="keywordtype">void</font> CPolygon2D::buildConvexHull(CPolygon2D &dest)<font class="keyword"> const</font> +00837 <font class="keyword"></font>{ +00838 <a class="code" href="debug_8h.html#a6">nlassert</a>(&dest != <font class="keyword">this</font>); +00839 +00840 <font class="keywordflow">if</font> (this-><a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() == 3) <font class="comment">// with 3 points it is always convex</font> +00841 { +00842 dest = *<font class="keyword">this</font>; +00843 <font class="keywordflow">return</font>; +00844 } +00845 uint k, <a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>; +00846 uint numVerts = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size(); +00847 CVector2f p, curr, prev; +00848 uint pIndex, p1Index, p2Index, pCurr, pPrev; +00849 <font class="comment">// this is not optimized, but not used in realtime.. =)</font> +00850 <a class="code" href="debug_8h.html#a6">nlassert</a>(numVerts >= 3); +00851 dest.Vertices.clear(); +00852 +00853 <font class="keyword">typedef</font> std::set<uint> TIndexSet; +00854 TIndexSet leftIndex; +00855 <font class="keywordflow">for</font> (k = 0; k < <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size(); ++k) +00856 { +00857 leftIndex.insert(k); +00858 } +00859 +00860 +00861 <font class="comment">// 1°) find the highest point p of the set. We are sure it belongs to the hull</font> +00862 pIndex = 0; +00863 p = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[0]; +00864 <font class="keywordflow">for</font> (k = 1; k < numVerts; ++k) +00865 { +00866 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[k].y < p.y) +00867 { +00868 pIndex = k; +00869 p = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[k]; +00870 } +00871 } +00872 +00873 leftIndex.erase(pIndex); +00874 +00875 +00876 <font class="keywordtype">float</font> bestCP = 1.1f; +00877 p1Index = p2Index = pIndex; +00878 +00879 <font class="keywordflow">for</font> (k = 0; k < numVerts; ++k) +00880 { +00881 <font class="keywordflow">if</font> (k != pIndex) +00882 { +00883 <font class="keywordflow">for</font> (<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> = 0; <a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> < numVerts; ++<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>) +00884 { +00885 <font class="keywordflow">if</font> (<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> != pIndex && <a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> != k) +00886 { +00887 CVector2f seg1 = (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>] - p).normed(); +00888 CVector2f seg2 = (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[k] - p).normed(); +00889 +00890 <font class="comment">//CVector cp = CVector(seg1.x, seg1.y, 0) ^ CVector(seg2.x, seg2.y, 0);</font> +00891 <font class="comment">//float n = fabsf(cp.z);</font> +00892 <font class="keywordtype">float</font> n = seg1 * seg2; +00893 <font class="keywordflow">if</font> (n < bestCP) +00894 { +00895 p1Index = <a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>; +00896 p2Index = k; +00897 bestCP = n; +00898 } +00899 } +00900 } +00901 } +00902 } +00903 +00904 +00905 leftIndex.erase(p2Index); +00906 +00907 +00908 +00909 <font class="comment">// start from the given triplet, and complete the poly until we reach the first point</font> +00910 pCurr = p2Index; +00911 pPrev = pIndex; +00912 +00913 curr = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[pCurr]; +00914 prev = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[pPrev]; +00915 +00916 <font class="comment">// create the first triplet vertices</font> +00917 dest.Vertices.push_back(<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[p1Index]); +00918 dest.Vertices.push_back(prev); +00919 dest.Vertices.push_back(curr); +00920 +00921 uint step = 0; +00922 +00923 <font class="keywordflow">for</font>(;;) +00924 { +00925 bestCP = 1.1f; +00926 CVector2f seg2 = (prev - curr).normed(); +00927 TIndexSet::const_iterator bestIt = leftIndex.end(); +00928 <font class="keywordflow">for</font> (TIndexSet::const_iterator it = leftIndex.begin(); it != leftIndex.end(); ++it) +00929 { +00930 <font class="keywordflow">if</font> (step == 0 && *it == p1Index) <font class="keywordflow">continue</font>; +00931 CVector2f seg1 = (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[*it] - curr).normed(); +00932 <font class="keywordtype">float</font> n = seg1 * seg2; +00933 <font class="keywordflow">if</font> (n < bestCP) +00934 { +00935 bestCP = n; +00936 bestIt = it; +00937 } +00938 } +00939 +00940 <a class="code" href="debug_8h.html#a6">nlassert</a>(bestIt != leftIndex.end()); +00941 <font class="keywordflow">if</font> (*bestIt == p1Index) +00942 { +00943 <font class="keywordflow">return</font>; <font class="comment">// if we reach the start point we have finished</font> +00944 } +00945 prev = curr; +00946 curr = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[*bestIt]; +00947 pPrev = pCurr; +00948 pCurr = *bestIt; +00949 <font class="comment">// add new point to the destination</font> +00950 dest.Vertices.push_back(curr); +00951 ++step; +00952 leftIndex.erase(bestIt); +00953 } +00954 } +00955 +00956 <font class="comment">// ***************************************************************************</font> +00957 +00958 +<a name="l00959"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a6">00959</a> <font class="keywordtype">void</font> CPolygon2D::serial(<a class="code" href="classNLMISC_1_1IStream.html">NLMISC::IStream</a> &f) <font class="keywordflow">throw</font>(NLMISC::EStream) +00960 { +00961 (void)f.serialVersion(0); +00962 f.serialCont(Vertices); +00963 } +00964 +00965 <font class="comment">// ***************************************************************************</font> +<a name="l00967"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a5">00967</a> <font class="comment">void CPolygon2D::getBestTriplet(uint &index0, uint &index1, uint &index2)</font> +00968 { +00969 <a class="code" href="debug_8h.html#a6">nlassert</a>(Vertices.size() >= 3); +00970 uint i, j, k; +00971 <font class="keywordtype">float</font> bestArea = 0.f; +00972 <font class="keyword">const</font> uint numVerts = Vertices.size(); +00973 <font class="keywordflow">for</font> (i = 0; i < numVerts; ++i) +00974 { +00975 <font class="keywordflow">for</font> (j = 0; j < numVerts; ++j) +00976 { +00977 <font class="keywordflow">if</font> (i != j) +00978 { +00979 <font class="keywordflow">for</font> (k = 0; k < numVerts; ++k) +00980 { +00981 <font class="keywordflow">if</font> (k != i && k != j) +00982 { +00983 CVector2f v0 = Vertices[j] - Vertices[i]; +00984 CVector2f v1 = Vertices[k] - Vertices[i]; +00985 <font class="keywordtype">float</font> area = fabsf((CVector(v0.x, v0.y, 0) ^ CVector(v1.x, v1.y, 0)).norm()); +00986 <font class="keywordflow">if</font> (area > bestArea) +00987 { +00988 bestArea = area; +00989 index0 = i; +00990 index1 = j; +00991 index2 = k; +00992 } +00993 } +00994 } +00995 } +00996 } +00997 } +00998 } +00999 +01000 +01002 <font class="comment">// scan a an edge of a poly and write it into a table</font> +01003 <font class="keyword">static</font> <font class="keywordtype">void</font> <a class="code" href="namespaceNLMISC.html#a309">ScanEdge</a>(CPolygon2D::TRasterVect &outputVect, sint topY, <font class="keyword">const</font> CVector2f &v1, <font class="keyword">const</font> CVector2f &v2, <font class="keywordtype">bool</font> rightEdge = <font class="keyword">true</font>) +01004 { +01005 <font class="keyword">const</font> uint rol16 = 65536; +01006 sint ceilY1 = (sint) ceilf(v1.y); +01007 sint <a class="code" href="driver__opengl__extension__def_8h.html#a390">height</a>; +01008 <font class="keywordtype">float</font> deltaX, deltaY; +01009 <font class="keywordtype">float</font> fInverseSlope; +01010 sint iInverseSlope, iPosX; +01011 +01012 <font class="comment">// check wether this segment gives a contribution to the final poly</font> +01013 <a class="code" href="driver__opengl__extension__def_8h.html#a390">height</a> = (sint) (ceilf(v2.y) - ceilY1); +01014 <font class="keywordflow">if</font> (<a class="code" href="driver__opengl__extension__def_8h.html#a390">height</a> <= 0) <font class="keywordflow">return</font>; +01015 +01016 <font class="comment">// compute slope</font> +01017 deltaY = v2.y - v1.y; +01018 deltaX = v2.x - v1.x; +01019 fInverseSlope = deltaX / deltaY; +01020 +01021 +01022 CPolygon2D::TRasterVect::iterator outputIt = outputVect.begin() + (ceilY1 - topY); +01023 +01024 <font class="comment">// slope with ints</font> +01025 iInverseSlope = (sint) (rol16 * fInverseSlope); +01026 +01027 <font class="comment">// sub-pixel accuracy</font> +01028 iPosX = (int) (rol16 * (v1.x + fInverseSlope * (ceilY1 - v1.y))); +01029 +01030 <font class="keyword">const</font> CPolygon2D::TRasterVect::iterator endIt = outputIt + <a class="code" href="driver__opengl__extension__def_8h.html#a390">height</a>; +01031 <font class="keywordflow">if</font> (rightEdge) +01032 { +01033 <font class="keywordflow">do</font> +01034 { +01035 outputIt->second = iPosX >> 16; +01036 iPosX += iInverseSlope; +01037 ++outputIt; +01038 } +01039 <font class="keywordflow">while</font> (outputIt != endIt); +01040 } +01041 <font class="keywordflow">else</font> +01042 { +01043 iPosX += (rol16 - 1); +01044 <font class="keywordflow">do</font> +01045 { +01046 outputIt->first = iPosX >> 16; +01047 iPosX += iInverseSlope; +01048 ++outputIt; +01049 } +01050 <font class="keywordflow">while</font> (outputIt != endIt); +01051 } +01052 } +01053 +01054 +01055 <font class="comment">// *******************************************************************************</font> +01056 <font class="comment">// This function alow to cycle forward through a vertex vector like if it was a circular list</font> +01057 <font class="keyword">static</font> <font class="keyword">inline</font> CPolygon2D::TVec2fVect::const_iterator <a class="code" href="namespaceNLMISC.html#a310">Next</a>(<font class="keyword">const</font> CPolygon2D::TVec2fVect::const_iterator &it, <font class="keyword">const</font> CPolygon2D::TVec2fVect &cont) +01058 { +01059 <a class="code" href="debug_8h.html#a6">nlassert</a>(cont.size() != 0); +01060 <font class="keywordflow">if</font> ((it + 1) == cont.end()) <font class="keywordflow">return</font> cont.begin(); +01061 <font class="keywordflow">return</font> (it + 1); +01062 } +01063 +01064 +01065 <font class="comment">// *******************************************************************************</font> +01066 <font class="comment">// This function alow to cycle backward through a (non null) vertex vector like if it was a circular list</font> +01067 <font class="keyword">static</font> <font class="keyword">inline</font> CPolygon2D::TVec2fVect::const_iterator <a class="code" href="namespaceNLMISC.html#a311">Prev</a>(<font class="keyword">const</font> CPolygon2D::TVec2fVect::const_iterator &it, <font class="keyword">const</font> CPolygon2D::TVec2fVect &cont) +01068 { +01069 <a class="code" href="debug_8h.html#a6">nlassert</a>(cont.size() != 0); +01070 <font class="keywordflow">if</font> (it == cont.begin()) <font class="keywordflow">return</font> cont.end() - 1; +01071 <font class="keywordflow">return</font> (it - 1); +01072 } +01073 +01074 <font class="comment">// *******************************************************************************</font> +<a name="l01075"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a7">01075</a> <font class="keywordtype">void</font> CPolygon2D::computeBorders(TRasterVect &borders, sint &highestY) +01076 { +01077 <font class="comment">// an 'alias' to the vertices</font> +01078 <font class="keyword">const</font> <a class="code" href="classNLMISC_1_1CPolygon2D.html#s0">TVec2fVect</a> &V = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>; +01079 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() < 3) +01080 { +01081 borders.clear(); +01082 <font class="keywordflow">return</font>; +01083 } +01084 <font class="keywordtype">bool</font> ccw; <font class="comment">// set to true when it has a counter clock wise orientation</font> +01085 +01086 <font class="comment">// compute highest and lowest pos of the poly</font> +01087 <font class="keywordtype">float</font> fHighest = V[0].y; +01088 <font class="keywordtype">float</font> fLowest = fHighest; +01089 +01090 <font class="comment">// iterators to the thighest and lowest vertex</font> +01091 TVec2fVect::const_iterator pLowest = V.begin(), pHighest = V.begin(); +01092 TVec2fVect::const_iterator it = V.begin() ; +01093 <font class="keyword">const</font> TVec2fVect::const_iterator endIt = V.end(); +01094 <font class="keywordflow">do</font> +01095 { +01096 <font class="keywordflow">if</font> (it->y > fLowest) +01097 { +01098 fLowest = it->y; +01099 pLowest = it; +01100 } +01101 <font class="keywordflow">else</font> +01102 <font class="keywordflow">if</font> (it->y < fHighest) +01103 { +01104 fHighest = it->y; +01105 pHighest = it; +01106 } +01107 ++it; +01108 } +01109 <font class="keywordflow">while</font> (it != endIt); +01110 +01111 +01112 sint iHighest = (sint) ceilf(fHighest) ; +01113 sint iLowest = (sint) ceilf(fLowest) ; +01114 +01115 highestY = iHighest; +01116 +01117 +01119 uint polyHeight = iLowest - iHighest; +01120 <font class="keywordflow">if</font> (polyHeight <= 0) +01121 { +01122 borders.clear(); +01123 <font class="keywordflow">return</font>; +01124 } +01125 +01126 borders.resize(polyHeight); +01127 +01128 <font class="comment">// iterator to the first vertex that has an y different from the top vertex</font> +01129 TVec2fVect::const_iterator pHighestRight = pHighest; +01130 <font class="comment">// we seek this vertex </font> +01131 <font class="keywordflow">while</font> (<a class="code" href="namespaceNLMISC.html#a310">Next</a>(pHighestRight, V)->y == fHighest) +01132 { +01133 pHighestRight = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(pHighestRight, V); +01134 } +01135 +01136 <font class="comment">// iterator to the first vertex after pHighestRight, that has the same y than the highest vertex</font> +01137 TVec2fVect::const_iterator pHighestLeft = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(pHighestRight, V); +01138 <font class="comment">// seek the vertex</font> +01139 <font class="keywordflow">while</font> (pHighestLeft->y != fHighest) +01140 { +01141 pHighestLeft = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(pHighestLeft, V); +01142 } +01143 +01144 TVec2fVect::const_iterator pPrevHighestLeft = <a class="code" href="namespaceNLMISC.html#a311">Prev</a>(pHighestLeft, V); +01145 +01146 <font class="comment">// we need to get the orientation of the polygon</font> +01147 <font class="comment">// There are 2 case : flat, and non-flat top</font> +01148 +01149 <font class="comment">// check for flat top</font> +01150 <font class="keywordflow">if</font> (pHighestLeft->x != pHighestRight->x) +01151 { +01152 <font class="comment">// compare right and left side</font> +01153 <font class="keywordflow">if</font> (pHighestLeft->x> pHighestRight->x) +01154 { +01155 ccw = <font class="keyword">true</font>; <font class="comment">// the list is CCW oriented</font> +01156 std::swap(pHighestLeft, pHighestRight); +01157 } +01158 <font class="keywordflow">else</font> +01159 { +01160 ccw = <font class="keyword">false</font>; <font class="comment">// the list is CW oriented </font> +01161 } +01162 } +01163 <font class="keywordflow">else</font> +01164 { +01165 <font class="comment">// The top of the poly is sharp</font> +01166 <font class="comment">// We perform a cross product of the 2 highest vect to get its orientation</font> +01167 +01168 <font class="keyword">const</font> <font class="keywordtype">float</font> deltaXN = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(pHighestRight, V)->x - pHighestRight->x; +01169 <font class="keyword">const</font> <font class="keywordtype">float</font> deltaYN = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(pHighestRight, V)->y - pHighestRight->y; +01170 <font class="keyword">const</font> <font class="keywordtype">float</font> deltaXP = pPrevHighestLeft->x - pHighestLeft->x; +01171 <font class="keyword">const</font> <font class="keywordtype">float</font> deltaYP = pPrevHighestLeft->y - pHighestLeft->y; +01172 <font class="keywordflow">if</font> ((deltaXN * deltaYP - deltaYN * deltaXP) < 0) +01173 { +01174 ccw = <font class="keyword">true</font>; <font class="comment">// the list is CCW oriented</font> +01175 std::swap(pHighestLeft, pHighestRight); +01176 } +01177 <font class="keywordflow">else</font> +01178 { +01179 ccw = <font class="keyword">false</font>; <font class="comment">// the list is CW oriented</font> +01180 } +01181 } +01182 +01183 +01184 <font class="comment">// compute borders</font> +01185 TVec2fVect::const_iterator currV, nextV; <font class="comment">// current and next vertex</font> +01186 <font class="keywordflow">if</font> (!ccw) <font class="comment">// clock wise order ?</font> +01187 { +01188 currV = pHighestRight ; +01189 <font class="comment">// compute right edge from top to bottom</font> +01190 <font class="keywordflow">do</font> +01191 { +01192 nextV = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(currV, V); +01193 <a class="code" href="namespaceNLMISC.html#a309">ScanEdge</a>(borders, iHighest, *currV, *nextV, <font class="keyword">true</font>); +01194 currV = nextV; +01195 } +01196 <font class="keywordflow">while</font> (currV != pLowest); <font class="comment">// repeat until we reach the bottom vertex</font> +01197 +01198 <font class="comment">// compute left edge from bottom to top</font> +01199 <font class="keywordflow">do</font> +01200 { +01201 nextV = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(currV, V); +01202 <a class="code" href="namespaceNLMISC.html#a309">ScanEdge</a>(borders, iHighest, *nextV, *currV, <font class="keyword">false</font>); +01203 currV = nextV; +01204 } +01205 <font class="keywordflow">while</font> (currV != pHighestLeft); +01206 } +01207 <font class="keywordflow">else</font> <font class="comment">// ccw order</font> +01208 { +01209 currV = pHighestLeft; +01210 <font class="comment">// compute left edge from top to bottom</font> +01211 <font class="keywordflow">do</font> +01212 { +01213 nextV = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(currV, V); +01214 <a class="code" href="namespaceNLMISC.html#a309">ScanEdge</a>(borders, iHighest, *currV, *nextV, <font class="keyword">false</font>) ; +01215 currV = nextV; +01216 } +01217 <font class="keywordflow">while</font> (currV != pLowest) ; +01218 +01219 <font class="comment">// compute right edge from bottom to top</font> +01220 <font class="keywordflow">do</font> +01221 { +01222 nextV = <a class="code" href="namespaceNLMISC.html#a310">Next</a>(currV, V); +01223 <a class="code" href="namespaceNLMISC.html#a309">ScanEdge</a>(borders, iHighest, *nextV, *currV, <font class="keyword">true</font>); +01224 currV = nextV; +01225 } +01226 <font class="keywordflow">while</font> (currV != pHighestRight) ; +01227 } +01228 } +01229 +01230 <font class="comment">// *******************************************************************************</font> +<a name="l01232"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#c0">01232</a> <font class="comment">float CPolygon2D::sumDPAgainstLine(float a, float b, float c) const</font> +01233 { +01234 <font class="keywordtype">float</font> sum = 0.f; +01235 <font class="keywordflow">for</font> (uint k = 0; k < Vertices.size(); ++k) +01236 { +01237 <font class="keyword">const</font> CVector2f &p = Vertices[k]; +01238 sum += a * p.x + b * p.y + c; +01239 } +01240 <font class="keywordflow">return</font> sum; +01241 } +01242 +01243 +01244 <font class="comment">// ******************************************************************************* </font> +<a name="l01245"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a10">01245</a> <font class="keywordtype">bool</font> CPolygon2D::getNonNullSeg(uint &<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>)<font class="keyword"> const</font> +01246 <font class="keyword"></font>{ +01247 <a class="code" href="debug_8h.html#a6">nlassert</a>(<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() > 0); +01248 <font class="keywordtype">float</font> bestLength = 0.f; +01249 sint bestIndex = -1; +01250 <font class="keywordflow">for</font> (uint k = 0; k < <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() - 1; ++k) +01251 { +01252 <font class="keywordtype">float</font> norm2 = (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[k + 1] - <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[k]).sqrnorm(); +01253 <font class="keywordflow">if</font> ( norm2 > bestLength) +01254 { +01255 bestLength = norm2; +01256 bestIndex = (int) k; +01257 } +01258 } +01259 <font class="keywordtype">float</font> norm2 = (<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() - 1] - <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[0]).sqrnorm(); +01260 <font class="keywordflow">if</font> ( norm2 > bestLength) +01261 { +01262 <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> = <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() - 1; +01263 <font class="keywordflow">return</font> <font class="keyword">true</font>; +01264 } +01265 +01266 <font class="keywordflow">if</font> (bestIndex != -1) +01267 { +01268 <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> = bestIndex; +01269 <font class="keywordflow">return</font> <font class="keyword">true</font>; +01270 } +01271 <font class="keywordflow">else</font> +01272 { +01273 <font class="keywordflow">return</font> <font class="keyword">false</font>; +01274 } +01275 } +01276 +01277 +01278 <font class="comment">// ******************************************************************************* </font> +<a name="l01279"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a11">01279</a> <font class="keywordtype">void</font> CPolygon2D::getLineEquation(uint <a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>, <font class="keywordtype">float</font> &a, <font class="keywordtype">float</font> &b, <font class="keywordtype">float</font> &c)<font class="keyword"> const</font> +01280 <font class="keyword"></font>{ +01281 <a class="code" href="debug_8h.html#a6">nlassert</a>(<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a> < <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size()); +01282 <font class="keyword">const</font> CVector2f &v0 = <a class="code" href="classNLMISC_1_1CPolygon2D.html#c1">getSegRef0</a>(<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>); +01283 <font class="keyword">const</font> CVector2f &v1 = <a class="code" href="classNLMISC_1_1CPolygon2D.html#c2">getSegRef1</a>(<a class="code" href="driver__opengl__extension__def_8h.html#a358">index</a>); +01284 +01285 <a class="code" href="classNLMISC_1_1CVector2f.html">NLMISC::CVector2f</a> seg = v0 - v1; +01286 a = seg.<a class="code" href="classNLMISC_1_1CVector2f.html#m1">y</a>; +01287 b = - seg.<a class="code" href="classNLMISC_1_1CVector2f.html#m0">x</a>; +01288 c = - v0.x * a - v0.y * b; +01289 } +01290 +01291 <font class="comment">// *******************************************************************************</font> +<a name="l01292"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a8">01292</a> <font class="keywordtype">bool</font> CPolygon2D::intersect(<font class="keyword">const</font> CPolygon2D &other)<font class="keyword"> const</font> +01293 <font class="keyword"></font>{ +01294 <a class="code" href="debug_8h.html#a6">nlassert</a>(other.Vertices.size() > 0); +01295 uint nonNullSegIndex; +01297 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon2D.html#a10">getNonNullSeg</a>(nonNullSegIndex)) +01298 { +01299 <font class="keywordtype">float</font> a0, b0, c0; +01300 <a class="code" href="classNLMISC_1_1CPolygon2D.html#a11">getLineEquation</a>(nonNullSegIndex, a0, b0, c0); +01301 <font class="keywordtype">float</font> orient = <a class="code" href="classNLMISC_1_1CPolygon2D.html#c0">sumDPAgainstLine</a>(a0, b0, c0); +01302 +01303 <font class="keywordflow">for</font> (uint k = 0; k < <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size(); ++k) +01304 { +01306 <font class="keywordflow">if</font> ( (<a class="code" href="classNLMISC_1_1CPolygon2D.html#c1">getSegRef0</a>(k) - <a class="code" href="classNLMISC_1_1CPolygon2D.html#c2">getSegRef1</a>(k)).sqrnorm() == 0.f) <font class="keywordflow">continue</font>; +01307 +01309 <font class="keywordtype">float</font> a, b, c; +01310 <a class="code" href="classNLMISC_1_1CPolygon2D.html#a11">getLineEquation</a>(k, a, b, c); +01311 uint <a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>; +01312 <font class="keywordflow">for</font> (<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> = 0; <a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> < other.Vertices.size(); ++<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>) +01313 { +01314 <font class="keyword">const</font> CVector2f &ov = other.Vertices[<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a>]; +01315 <font class="keywordflow">if</font> ( orient * (ov.x * a + ov.y * b +c) > 0.f) <font class="keywordflow">break</font>; +01316 } +01317 <font class="keywordflow">if</font> (<a class="code" href="namespaceNLAISCRIPT.html#a20">l</a> == other.Vertices.size()) <font class="comment">// all point on the outside</font> +01318 { +01319 <font class="keywordflow">return</font> <font class="keyword">false</font>; <font class="comment">// outside</font> +01320 } +01321 } +01322 <font class="keywordflow">return</font> <font class="keyword">true</font>; +01323 } +01324 <font class="keywordflow">else</font> <font class="comment">// this poly is just a point</font> +01325 { +01326 <font class="keywordflow">return</font> other.contains(<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[0]); +01327 } +01328 } +01329 +01330 <font class="comment">// *******************************************************************************</font> +<a name="l01331"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a9">01331</a> <font class="keywordtype">bool</font> CPolygon2D::contains(<font class="keyword">const</font> CVector2f &p)<font class="keyword"> const</font> +01332 <font class="keyword"></font>{ +01333 <a class="code" href="debug_8h.html#a6">nlassert</a>(<a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size() > 0); +01334 uint nonNullSegIndex; +01336 <font class="keywordflow">if</font> (<a class="code" href="classNLMISC_1_1CPolygon2D.html#a10">getNonNullSeg</a>(nonNullSegIndex)) +01337 { +01338 <font class="keywordtype">float</font> a0, b0, c0; +01339 <a class="code" href="classNLMISC_1_1CPolygon2D.html#a11">getLineEquation</a>(nonNullSegIndex, a0, b0, c0); +01340 +01341 <font class="keywordflow">for</font> (uint k = 0; k < <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.size(); ++k) +01342 { +01344 <font class="keywordflow">if</font> ( (<a class="code" href="classNLMISC_1_1CPolygon2D.html#c1">getSegRef0</a>(k) - <a class="code" href="classNLMISC_1_1CPolygon2D.html#c2">getSegRef1</a>(k)).sqrnorm() == 0.f) <font class="keywordflow">continue</font>; +01345 +01347 <font class="keywordtype">float</font> a, b, c; +01348 <a class="code" href="classNLMISC_1_1CPolygon2D.html#a11">getLineEquation</a>(k, a, b, c); +01349 +01350 <font class="keywordflow">if</font> (a * p.x + b * p.y + c < 0) <font class="keywordflow">return</font> <font class="keyword">false</font>; +01351 +01352 } +01353 <font class="keywordflow">return</font> <font class="keyword">true</font>; +01354 } +01355 <font class="keywordflow">else</font> <font class="comment">// this poly is just a point</font> +01356 { +01357 <font class="keywordflow">return</font> p == <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[0]; +01358 } +01359 } +01360 +01361 +01362 <font class="comment">// *******************************************************************************</font> +<a name="l01363"></a><a class="code" href="classNLMISC_1_1CPolygon2D.html#a2">01363</a> CPolygon2D::CPolygon2D(<font class="keyword">const</font> CTriangle &tri, <font class="keyword">const</font> CMatrix &projMat) +01364 { +01365 <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>.resize(3); +01366 <a class="code" href="classNLMISC_1_1CVector.html">NLMISC::CVector</a> proj[3] = { projMat * tri.V0, projMat * tri.V1, projMat * tri.V2 }; +01367 <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[0].set(proj[0].<a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>, proj[0].<a class="code" href="driver__opengl__extension__def_8h.html#a365">y</a>); +01368 <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[1].set(proj[1].<a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>, proj[1].<a class="code" href="driver__opengl__extension__def_8h.html#a365">y</a>); +01369 <a class="code" href="classNLMISC_1_1CPolygon2D.html#m0">Vertices</a>[2].set(proj[2].<a class="code" href="driver__opengl__extension__def_8h.html#a364">x</a>, proj[2].<a class="code" href="driver__opengl__extension__def_8h.html#a365">y</a>); +01370 } +01371 +01372 } <font class="comment">// NLMISC</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> |