nevrax.org : docs

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