NLMISC::CPolygon Class Reference

#include <polygon.h>

---

Detailed Description

A polygon, with an unlimited size of vertices.

Author:

Lionel Berenguier

Nevrax France

Date:

2000

Definition at line 52 of file polygon.h.

Public Member Functions
void	buildBasis (CMatrix &dest)
bool	chain (const std::vector< CPolygon > &other, const CMatrix &basis)
void	clip (const std::vector< CPlane > &planes)
	Clip a polygon with a set of planes. Cohen-sutherland clipping... clipPolygonBack() is used on planes.
void	clip (const CPlane *planes, uint nPlanes)
	Clip a polygon with a set of planes. Cohen-sutherland... clipPolygonBack() is used on planes.
	CPolygon (const CVector &a, const CVector &b, const CVector &c)
	Constructor. Init with a triangle.
	CPolygon ()
	Constructor.
void	getBestTriplet (uint &index0, uint &index1, uint &index2)
	get the best triplet from this poly (the one that has the highest area)
sint	getNumVertices () const
void	serial (NLMISC::IStream &f) throw (NLMISC::EStream)
	Serial this polygon.
bool	toConvexPolygons (std::list< CPolygon > &outputPolygons, const CMatrix &basis) const
void	toConvexPolygonsLocalAndBSP (std::vector< CVector > &localVertices, CBSPNode2v &root, const CMatrix &basis) const
Static Public Member Functions
bool	toConvexPolygonsDiagonal (const std::vector< CVector > &vertex, const CBSPNode2v &bsp, uint a, uint b)
bool	toConvexPolygonsEdgeIntersect (const CVector2f &a0, const CVector2f &a1, const CVector2f &b0, const CVector2f &b1)
bool	toConvexPolygonsInCone (const std::vector< CVector > &vertex, uint a, uint b)
bool	toConvexPolygonsLeft (const std::vector< CVector > &vertex, uint a, uint b, uint c)
bool	toConvexPolygonsLeftOn (const std::vector< CVector > &vertex, uint a, uint b, uint c)
Data Fields
std::vector< CVector >	Vertices

---

Constructor & Destructor Documentation

NLMISC::CPolygon::CPolygon (   )  [inline]

Constructor. Definition at line 60 of file polygon.h. Referenced by toConvexPolygons(). {}

NLMISC::CPolygon::CPolygon (  const CVector &  a, const CVector &  b, const CVector &  c )

Constructor. Init with a triangle. Definition at line 46 of file polygon.cpp. { Vertices.reserve(3); Vertices.push_back(a); Vertices.push_back(b); Vertices.push_back(c); }

---

Member Function Documentation

void NLMISC::CPolygon::buildBasis (  CMatrix &  dest  )

Takes the best triplet from this poly to build a normal. From this normal and a points, build a basis (the normal is the K vector of the basis) This can be used to transform the poly in 2D after it has been inverted Definition at line 141 of file polygon.cpp. References getBestTriplet(), nlassert, NLMISC::CMatrix::setPos(), NLMISC::CMatrix::setRot(), and uint. { nlassert(Vertices.size() > 3); uint i1, i2, i3; getBestTriplet(i1, i2, i3); CVector v1 = (Vertices[i2] - Vertices[i1]).normed(); CVector v2 = (Vertices[i3] - Vertices[i1]).normed(); CVector K = v2 ^ v1; CVector I = v1 - (v1 * K) * v1; CVector J = K ^ I; dest.setRot(I, J, K); dest.setPos(Vertices[i1]); }

bool NLMISC::CPolygon::chain (  const std::vector< CPolygon > &  other, const CMatrix &  basis )

Chain the arg polygons with this polygon testing 2d intersections. The 2d intersection test has been done in the XY plane of the basis passed at the function. The polygon a-b-c-d-e chained with f-g-h-i-j will give the polygon a-b-f-g-h-i-j-f-b-c-d-e if the edge b-f is not 2d clipped by any edge plane in the XY plane of basis. Parameters: basis  is the basis of the polygon projection. Returns: false if chain failed. else true. Definition at line 624 of file polygon.cpp. References index, NLMISC::CBSPNode2v::intersect(), toConvexPolygonsLocalAndBSP(), uint, and Vertices. { // Local vertices std::vector<CVector> localVertices; // Build the BSP root CBSPNode2v root; // Build the local array and the BSP toConvexPolygonsLocalAndBSP (localVertices, root, basis); // Local vertices std::vector<std::vector<CVector> > localVerticesOther (other.size()); // Build the BSP root std::vector<CBSPNode2v> rootOther (other.size()); // Build a copy of the polygons std::vector<CPolygon> copy = other; // Main copy CPolygon mainCopy = *this; // For each other polygons uint o; for (o=0; o<other.size(); o++) { // Build the local array and the BSP other[o].toConvexPolygonsLocalAndBSP (localVerticesOther[o], rootOther[o], basis); } // Look for a couple.. uint thisCount = Vertices.size(); uint i, j; for (o=0; o<other.size(); o++) { uint otherCount = other[o].Vertices.size(); // Try to link in the main polygon for (i=0; i<thisCount; i++) { for (j=0; j<otherCount; j++) { // Test this segement if (!root.intersect (localVertices[i], localVerticesOther[o][j], i, 0xffffffff)) { // Test each other polygons uint otherO; for (otherO=0; otherO<other.size(); otherO++) { // Intersect ? if (rootOther[otherO].intersect (localVertices[i], localVerticesOther[o][j], 0xffffffff, (otherO == o)?j:0xffffffff)) break; } // Continue ? if (otherO==other.size()) { // Insert new vertices mainCopy.Vertices.insert (mainCopy.Vertices.begin()+i, 2+otherCount, CVector()); // Copy the first vertex mainCopy.Vertices[i] = mainCopy.Vertices[i+otherCount+2]; // Copy the new vertices uint k; for (k=0; k<otherCount; k++) { uint index = j+k; if (index>=otherCount) index -= otherCount; mainCopy.Vertices[i+k+1] = copy[o].Vertices[index]; } // Copy the last one mainCopy.Vertices[i+otherCount+1] = copy[o].Vertices[j]; break; } } } if (j!=otherCount) break; } // Not found ? if (i==thisCount) { // Try to link in the sub polygons uint otherToCheck; for (otherToCheck=o+1; otherToCheck<other.size(); otherToCheck++) { uint otherToCheckCount = other[otherToCheck].Vertices.size(); for (i=0; i<otherToCheckCount; i++) { for (j=0; j<otherCount; j++) { // Test this segement if (!rootOther[otherToCheck].intersect (localVerticesOther[otherToCheck][i], localVerticesOther[o][j], i, 0xffffffff)) { // Test each other polygons uint otherO; for (otherO=0; otherO<other.size(); otherO++) { // Intersect ? if (rootOther[otherO].intersect (localVerticesOther[otherToCheck][i], localVerticesOther[o][j], (otherToCheck == otherO)?i:0xffffffff, (otherO == o)?j:0xffffffff)) break; } // Continue ? if (otherO==other.size()) { // Insert new vertices copy[otherToCheck].Vertices.insert (copy[otherToCheck].Vertices.begin()+i, 2+otherCount, CVector()); // Copy the first vertex copy[otherToCheck].Vertices[i] = copy[otherToCheck].Vertices[i+otherCount+2]; // Copy the new vertices uint k; for (k=0; k<otherCount; k++) { uint index = j+k; if (index>=otherCount) index -= otherCount; copy[otherToCheck].Vertices[i+k+1] = copy[otherO].Vertices[index]; } // Copy the last one copy[otherToCheck].Vertices[i+otherCount+1] = copy[otherO].Vertices[j]; break; } } } if (j!=otherCount) break; } if (i!=otherToCheckCount) break; } if (otherToCheck==other.size()) { // Not ok return false; } } } // Ok *this = mainCopy; return true; }

void NLMISC::CPolygon::clip (  const std::vector< CPlane > &  planes  )

Clip a polygon with a set of planes. Cohen-sutherland clipping... clipPolygonBack() is used on planes. Definition at line 89 of file polygon.cpp. References clip(). { if(planes.size()==0) return; clip(&(*planes.begin()), planes.size()); }

void NLMISC::CPolygon::clip (  const CPlane *  planes, uint  nPlanes )

Clip a polygon with a set of planes. Cohen-sutherland... clipPolygonBack() is used on planes. Definition at line 56 of file polygon.cpp. References NLMISC::CPlane::clipPolygonBack(), getNumVertices(), in, sint, and uint. Referenced by clip(), NL3D::CPortal::clipPyramid(), NL3D::CWaterModel::computeClippedPoly(), NL3D::CWaterModel::computeSimpleClippedPoly(), NL3D::CInstanceGroup::displayDebugClusters(), and NLMISC::CAABBox::intersect(). { if(nPlanes==0 || getNumVertices()==0) return; // The final polygon has at maximum currentVertices+number of clipping planes. // For performance, the vectors are static, so reallocation rarely occurs. static vector<CVector> tab0, tab1; tab0.resize(getNumVertices()+nPlanes); tab1.resize(getNumVertices()+nPlanes); // Init tab0 with Vertices. copy(Vertices.begin(), Vertices.end(), tab0.begin()); CVector *in=&(*tab0.begin()), *out= &(*tab1.begin()); sint nin= getNumVertices(), nout; for(sint i=0;i<(sint)nPlanes;i++) { nout= planes[i].clipPolygonBack(in, out, nin); swap(in, out); nin= nout; if(nin==0) break; } // Final result in "in". Vertices.resize(nin); if(nin>0) { memcpy(&(*Vertices.begin()), in, nin*sizeof(CVector)); } }

void NLMISC::CPolygon::getBestTriplet (  uint &  index0, uint &  index1, uint &  index2 )

get the best triplet from this poly (the one that has the highest area) Definition at line 106 of file polygon.cpp. References nlassert, NLMISC::CVector::norm(), and uint. Referenced by buildBasis(). { nlassert(Vertices.size() >= 3); uint i, j, k; float bestArea = 0.f; const uint numVerts = Vertices.size(); for (i = 0; i < numVerts; ++i) { for (j = 0; j < numVerts; ++j) { if (i != j) { for (k = 0; k < numVerts; ++k) { if (k != i && k != j) { CVector v0 = Vertices[j] - Vertices[i]; CVector v1 = Vertices[k] - Vertices[i]; float area = (v0 ^ v1).norm(); if (area > bestArea) { bestArea = area; index0 = i; index1 = j; index2 = k; } } } } } } }

sint NLMISC::CPolygon::getNumVertices (  void   )  const [inline]

Definition at line 64 of file polygon.h. References sint. Referenced by clip(), NLMISC::CAABBox::intersect(), and NL3D::CZoneLighter::lightWater(). {return Vertices.size();}

void NLMISC::CPolygon::serial (  NLMISC::IStream &  f  )  throw (NLMISC::EStream)

Serial this polygon. Definition at line 99 of file polygon.cpp. { f.serialVersion(0); f.serialCont(Vertices); }

bool NLMISC::CPolygon::toConvexPolygons (  std::list< CPolygon > &  outputPolygons, const CMatrix &  basis )  const

Convert a concave polygon into a list of convex polygons using a 2d projection. The polygon mustn't overlap itself in the XY plane of the basis passed in parameter. The polygon must be direct in the XY plane of the basis passed in parameter. (Counter clock wise) The subdivison is in non-constant n*log(n) with n is the number of vertices. Parameters: outputPolygons  is the list filled with clipped convex polygons. The list is not cleared at the begining. New polygons are just appended at the end. basis  is the basis of the polygon projection. Returns: true if the polygon has been subdivided. false if the polygon overlap itself in the XY plane of the basis or if the polygon is not direct (clock wise). Definition at line 440 of file polygon.cpp. References CPolygon(), nlassert, toConvexPolygonsDiagonal(), toConvexPolygonsLocalAndBSP(), uint, and Vertices. { // Some vertices ? if (Vertices.size()>2) { // Local vertices std::vector<CVector> localVertices; // Build the BSP root CBSPNode2v root; // Build the local array and the BSP toConvexPolygonsLocalAndBSP (localVertices, root, basis); // Build a vertex list std::list<uint> vertexList; uint i; for (i=0; i<Vertices.size(); i++) vertexList.push_back (i); // Clip ears while there is some polygons std::list<uint>::iterator current=vertexList.begin(); std::list<uint>::iterator begin=vertexList.begin(); do { again:; // Search for a diagonal bool found = false; // Get next vertex std::list<uint>::iterator first = current; std::list<uint>::iterator lastPreviousPrevious=current; std::list<uint>::iterator lastPrevious=current; lastPrevious++; if (lastPrevious==vertexList.end()) lastPrevious = vertexList.begin(); std::list<uint>::iterator currentNext = lastPrevious; std::list<uint>::iterator last = lastPrevious; last++; if (last==vertexList.end()) last = vertexList.begin(); while (last != current) { // Is a diagonal ? if ( (toConvexPolygonsDiagonal (localVertices, root, *lastPreviousPrevious, *last)) && (toConvexPolygonsDiagonal (localVertices, root, *currentNext, *last)) && (toConvexPolygonsDiagonal (localVertices, root, *last, *current)) ) { // Find one found = true; } else { // Come back last = lastPrevious; lastPrevious = lastPreviousPrevious; break; } // Next vertex lastPreviousPrevious = lastPrevious; lastPrevious = last++; if (last==vertexList.end()) last = vertexList.begin(); } // Last polygon ? if (last==current) { // Add a polygon outputPolygons.push_back (CPolygon()); CPolygon &back = outputPolygons.back (); back.Vertices.reserve (vertexList.size()); // Add each vertex in the new polygon current=vertexList.begin(); while (current!=vertexList.end()) { back.Vertices.push_back (Vertices[*current]); current++; } // Exit return true; } else { std::list<uint>::iterator firstNext = current; std::list<uint>::iterator firstNextNext = currentNext; if (first != vertexList.begin()) first--; else { first = vertexList.end(); first--; } while (current != first) { // Is a diagonal ? if ( (toConvexPolygonsDiagonal (localVertices, root, *firstNextNext, *first)) && (toConvexPolygonsDiagonal (localVertices, root, *lastPrevious, *first)) && (toConvexPolygonsDiagonal (localVertices, root, *last, *first)) ) { // Find one found = true; } else { // Come back first = firstNext; break; } // Next vertex firstNextNext = firstNext; firstNext = first; if (first==vertexList.begin()) { first = vertexList.end(); first--; } else first--; } } // Found ? if (found) { // Count vertex outputPolygons.push_back (CPolygon()); CPolygon &back = outputPolygons.back (); // Vertex count uint vertexCount = 1; current = first; while (current != last) { vertexCount++; current++; if (current == vertexList.end()) current = vertexList.begin(); } // Alloc vertices back.Vertices.reserve (vertexCount); // Copy and remove vertices back.Vertices.push_back (Vertices[*first]); first++; if (first == vertexList.end()) first = vertexList.begin(); while (first != last) { back.Vertices.push_back (Vertices[*first]); // Remove from list first = vertexList.erase (first); if (first == vertexList.end()) first = vertexList.begin(); nlassert (first != vertexList.end()); } back.Vertices.push_back (Vertices[*first]); current = begin = last; goto again; } // Next current current++; if (current == vertexList.end()) current = vertexList.begin (); } while (current != begin); } return false; }

bool NLMISC::CPolygon::toConvexPolygonsDiagonal (  const std::vector< CVector > &  vertex, const CBSPNode2v &  bsp, uint  a, uint  b )  [static]

Definition at line 375 of file polygon.cpp. References NLMISC::CBSPNode2v::intersect(), toConvexPolygonsInCone(), and uint. Referenced by toConvexPolygons(). { // Check it is a border if ( ( (b - a) == 1) || ( (a - b) == 1) || ( (a==0) && (b ==(vertex.size()-1))) || ( (b==0) && (a ==(vertex.size()-1))) ) return true; // Check visibility if (toConvexPolygonsInCone (vertex, a, b) && toConvexPolygonsInCone (vertex, b, a)) { // Intersection ? return !bsp.intersect (vertex[a], vertex[b], a, b); } return false; }

bool NLMISC::CPolygon::toConvexPolygonsEdgeIntersect (  const CVector2f &  a0, const CVector2f &  a1, const CVector2f &  b0, const CVector2f &  b1 )  [static]

Definition at line 177 of file polygon.cpp. References NLMISC::CVector2f::x, and NLMISC::CVector2f::y. { float Aa = (a0.y - a1.y) / (a0.x - a1.x); float Ba = a0.y - a0.x * Aa; float Ab = (b0.y - b1.y) / (b0.x - b1.x); float Bb = b0.y - b0.x * Ab; // Intersection CVector2f intersection; intersection.x = (Bb - Ba) / (Aa - Ab); intersection.y = Aa * intersection.x + Ba; // In it ? return ( ( (a0-intersection)*(a1-intersection) < 0 ) && ( (b0-intersection)*(b1-intersection) < 0 ) ); }

bool NLMISC::CPolygon::toConvexPolygonsInCone (  const std::vector< CVector > &  vertex, uint  a, uint  b )  [static]

Definition at line 351 of file polygon.cpp. References toConvexPolygonsLeft(), toConvexPolygonsLeftOn(), and uint. Referenced by toConvexPolygonsDiagonal(). { // Prev and next uint a0 = a+1; if (a0==vertex.size()) a0=0; uint a1; if (a==0) a1=vertex.size()-1; else a1= a-1; if (toConvexPolygonsLeftOn (vertex, a, a1, a0) ) { return toConvexPolygonsLeft ( vertex, a, b, a0) && toConvexPolygonsLeft ( vertex, b, a, a1); } else { return !( toConvexPolygonsLeft ( vertex, a, b, a1) && toConvexPolygonsLeft ( vertex, b, a, a0) ); } }

bool NLMISC::CPolygon::toConvexPolygonsLeft (  const std::vector< CVector > &  vertex, uint  a, uint  b, uint  c )  [static]

Definition at line 337 of file polygon.cpp. References uint. Referenced by toConvexPolygonsInCone(). { 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; }

bool NLMISC::CPolygon::toConvexPolygonsLeftOn (  const std::vector< CVector > &  vertex, uint  a, uint  b, uint  c )  [static]

Definition at line 344 of file polygon.cpp. References uint. Referenced by toConvexPolygonsInCone(). { 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; }

void NLMISC::CPolygon::toConvexPolygonsLocalAndBSP (  std::vector< CVector > &  localVertices, CBSPNode2v &  root, const CMatrix &  basis )  const

Definition at line 392 of file polygon.cpp. References NLMISC::CBSPNode2v::insert(), NLMISC::CMatrix::invert(), NLMISC::CPlane::make(), NLMISC::TCConcavePolygonsVertexMap, uint, NLMISC::CVector::x, and NLMISC::CVector::y. Referenced by chain(), and toConvexPolygons(). { // Invert matrix CMatrix invert = basis; invert.invert (); // Insert vertices in an ordered table uint vertexCount = Vertices.size(); TCConcavePolygonsVertexMap vertexMap; localVertices.resize (vertexCount); uint i, j; // Transform the vertex for (i=0; i<vertexCount; i++) { CVector local = invert*Vertices[i]; localVertices[i] = CVector (local.x, local.y, 0); } // Plane direction i=0; j=Vertices.size()-1; CVector normal = localVertices[i] - localVertices[j]; normal = normal ^ CVector::K; CPlane clipPlane; clipPlane.make(normal, localVertices[i]); // Build the BSP root root = CBSPNode2v (clipPlane, localVertices[i], localVertices[j], i, j); // Insert all others edges j=i++; for (; i<Vertices.size(); i++) { // Plane direction normal = localVertices[i] - localVertices[j]; normal = normal ^ CVector::K; clipPlane.make(normal, localVertices[i]); // Build the BSP root root.insert ( new CBSPNode2v (clipPlane, localVertices[i], localVertices[j], i, j) ); j=i; } }

---

Field Documentation

std::vector<CVector> NLMISC::CPolygon::Vertices

Definition at line 55 of file polygon.h. Referenced by NLPACS::CLocalRetriever::build3dSurfacePolygons(), NLPACS::CLocalRetriever::buildSurfacePolygons(), chain(), NL3D::CWaterModel::clip(), NL3D::CPortal::clipPyramid(), NL3D::CWaterModel::computeClippedPoly(), NL3D::CWaterModel::computeSimpleClippedPoly(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CInstanceGroup::displayDebugClusters(), NL3D::CWaterModel::doSimpleRender(), NL3D::DrawPoly2D(), NL3D::CWaterShape::getShapeInWorldSpace(), NL3D::CZoneLighter::lightWater(), toConvexPolygons(), and NL3D::CWaterModel::traverseRender().

---

The documentation for this class was generated from the following files:

• polygon.h
• polygon.cpp

---