NLMISC::CPolygon2D Class Reference

#include <polygon.h>

---

Detailed Description

A 2d convex polygon

Definition at line 122 of file polygon.h.

Public Types
typedef std::pair< sint, sint >	TRaster
typedef std::vector< TRaster >	TRasterVect
typedef std::vector< CVector2f >	TVec2fVect
Public Member Functions
void	buildConvexHull (CPolygon2D &dest) const
void	computeBorders (TRasterVect &borders, sint &minimumY)
void	computeInnerBorders (TRasterVect &borders, sint &minimumY)
void	computeOuterBorders (TRasterVect &borders, sint &minimumY)
bool	contains (const CVector2f &p) const
	Check wether a point is contained by this poly.
	CPolygon2D (const CTriangle &tri, const CMatrix &projMat=CMatrix::Identity)
	CPolygon2D (const CPolygon &src, const CMatrix &projMat=CMatrix::Identity)
	CPolygon2D ()
	default ctor
void	getBestTriplet (uint &index0, uint &index1, uint &index2)
	get the best triplet of vector. e.g the triplet that has the best surface
void	getLineEquation (uint index, float &a, float &b, float &c) const
	Get a line equation of the seg starting at the given index.
bool	getNonNullSeg (uint &seg) const
bool	intersect (const CPolygon2D &other) const
	Test wether this polygon intersect another convex polygon. Currently not optimized.
bool	isConvex ()
	Check wether this polygon is convex;.
void	serial (NLMISC::IStream &f) throw (NLMISC::EStream)
	Serial this polygon.
void	swap (CPolygon2D &other)
Data Fields
TVec2fVect	Vertices
Private Member Functions
const CVector2f &	getSegRef0 (uint index) const
	Get ref to the first vertex that start at index.
const CVector2f &	getSegRef1 (uint index) const
float	sumDPAgainstLine (float a, float b, float c) const
	Sum the dot product of this poly vertices against a plane.

---

Member Typedef Documentation

typedef std::pair<sint, sint> NLMISC::CPolygon2D::TRaster

Definition at line 159 of file polygon.h. Referenced by RenderTriangle(), NLMISC::ScanInnerEdge(), NLMISC::ScanOuterEdgeLeft(), and NLMISC::ScanOuterEdgeRight().

typedef std::vector<TRaster> NLMISC::CPolygon2D::TRasterVect

Definition at line 160 of file polygon.h. Referenced by NL3D::CLodCharacterShapeBuild::compile(), computeBorders(), computeInnerBorders(), computeOuterBorders(), RenderTriangle(), NL3D::CRenderZBuffer::run(), NLMISC::ScanEdge(), and NL3D::CWaterModel::traverseRender().

typedef std::vector<CVector2f> NLMISC::CPolygon2D::TVec2fVect

Definition at line 125 of file polygon.h. Referenced by computeBorders(), NLMISC::Next(), and NLMISC::Prev().

---

Constructor & Destructor Documentation

NLMISC::CPolygon2D::CPolygon2D (   )  [inline]

default ctor Definition at line 129 of file polygon.h. {}

NLMISC::CPolygon2D::CPolygon2D (  const CPolygon &  src, const CMatrix &  projMat = CMatrix::Identity )

Build a 2D polygon from this 3D polygon, by using the given projection matrix The x and y components of projected vertices are used to create the 2D polygon Definition at line 785 of file polygon.cpp. References size, src, uint, NLMISC::CVector::x, and NLMISC::CVector::y. { uint size = src.Vertices.size(); Vertices.resize(size); for (uint k = 0; k < size; ++k) { CVector proj = projMat * src.Vertices[k]; Vertices[k].set(proj.x, proj.y); } }

NLMISC::CPolygon2D::CPolygon2D (  const CTriangle &  tri, const CMatrix &  projMat = CMatrix::Identity )

Build a 2D polygon from the given triangle, by using the given projection matrix The x and y components of projected vertices are used to create the 2D polygon Definition at line 1928 of file polygon.cpp. References NLMISC::CTriangle::V0, NLMISC::CTriangle::V1, NLMISC::CTriangle::V2, x, and y. { Vertices.resize(3); NLMISC::CVector proj[3] = { projMat * tri.V0, projMat * tri.V1, projMat * tri.V2 }; Vertices[0].set(proj[0].x, proj[0].y); Vertices[1].set(proj[1].x, proj[1].y); Vertices[2].set(proj[2].x, proj[2].y); }

---

Member Function Documentation

void NLMISC::CPolygon2D::buildConvexHull (  CPolygon2D &  dest  )  const

Build a convex hull from this polygon. The result poly is ordered, so it can also be used to order a convex poly given its set of vertices. NB: require this != &dest Definition at line 836 of file polygon.cpp. References nlassert, uint, Vertices, and NLMISC::CVector2f::y. { nlassert(&dest != this); if (this->Vertices.size() == 3) // with 3 points it is always convex { dest = *this; return; } uint k, l; uint numVerts = Vertices.size(); CVector2f p, curr, prev; uint pIndex, p1Index, p2Index, pCurr, pPrev; // this is not optimized, but not used in realtime.. =) nlassert(numVerts >= 3); dest.Vertices.clear(); typedef std::set<uint> TIndexSet; TIndexSet leftIndex; for (k = 0; k < Vertices.size(); ++k) { leftIndex.insert(k); } // 1) find the highest point p of the set. We are sure it belongs to the hull pIndex = 0; p = Vertices[0]; for (k = 1; k < numVerts; ++k) { if (Vertices[k].y < p.y) { pIndex = k; p = Vertices[k]; } } leftIndex.erase(pIndex); float bestCP = 1.1f; p1Index = p2Index = pIndex; for (k = 0; k < numVerts; ++k) { if (k != pIndex) { for (l = 0; l < numVerts; ++l) { if (l != pIndex && l != k) { CVector2f seg1 = (Vertices[l] - p).normed(); CVector2f seg2 = (Vertices[k] - p).normed(); //CVector cp = CVector(seg1.x, seg1.y, 0) ^ CVector(seg2.x, seg2.y, 0); //float n = fabsf(cp.z); float n = seg1 * seg2; if (n < bestCP) { p1Index = l; p2Index = k; bestCP = n; } } } } } leftIndex.erase(p2Index); // start from the given triplet, and complete the poly until we reach the first point pCurr = p2Index; pPrev = pIndex; curr = Vertices[pCurr]; prev = Vertices[pPrev]; // create the first triplet vertices dest.Vertices.push_back(Vertices[p1Index]); dest.Vertices.push_back(prev); dest.Vertices.push_back(curr); uint step = 0; for(;;) { bestCP = 1.1f; CVector2f seg2 = (prev - curr).normed(); TIndexSet::const_iterator bestIt = leftIndex.end(); for (TIndexSet::const_iterator it = leftIndex.begin(); it != leftIndex.end(); ++it) { if (step == 0 && *it == p1Index) continue; CVector2f seg1 = (Vertices[*it] - curr).normed(); float n = seg1 * seg2; if (n < bestCP) { bestCP = n; bestIt = it; } } nlassert(bestIt != leftIndex.end()); if (*bestIt == p1Index) { return; // if we reach the start point we have finished } prev = curr; curr = Vertices[*bestIt]; pPrev = pCurr; pCurr = *bestIt; // add new point to the destination dest.Vertices.push_back(curr); ++step; leftIndex.erase(bestIt); } }

void NLMISC::CPolygon2D::computeBorders (  TRasterVect &  borders, sint &  minimumY )

Compute the borders of this poly with sub-pixel accuracy. No clipping is performed. Only points exactly inside or exactly on the left border of the polygon are kept. This means that pixels are seen as points, not as surfaces. The output is in a vector of sint pairs. minimumY is filled with the minimum y value of the poly. Each pairs gives [xmin, xmax] for the current segment. if xmin > xmax, then no point is valid for this segment. Otherwise, all points from x = xmin (included) to x = xmax (included) are valids. Definition at line 1075 of file polygon.cpp. References NLMISC::Next(), NLMISC::Prev(), NLMISC::ScanEdge(), sint, TRasterVect, TVec2fVect, and uint. Referenced by NL3D::CLodCharacterShapeBuild::compile(), RenderTriangle(), and NL3D::CWaterModel::traverseRender(). { // an 'alias' to the vertices const TVec2fVect &V = Vertices; if (Vertices.size() < 3) { borders.clear(); return; } bool ccw; // set to true when it has a counter clock wise orientation // compute highest and lowest pos of the poly float fHighest = V[0].y; float fLowest = fHighest; // iterators to the thighest and lowest vertex TVec2fVect::const_iterator pLowest = V.begin(), pHighest = V.begin(); TVec2fVect::const_iterator it = V.begin() ; const TVec2fVect::const_iterator endIt = V.end(); do { if (it->y > fLowest) { fLowest = it->y; pLowest = it; } else if (it->y < fHighest) { fHighest = it->y; pHighest = it; } ++it; } while (it != endIt); sint iHighest = (sint) ceilf(fHighest) ; sint iLowest = (sint) ceilf(fLowest) ; highestY = iHighest; uint polyHeight = iLowest - iHighest; if (polyHeight <= 0) { borders.clear(); return; } borders.resize(polyHeight); // iterator to the first vertex that has an y different from the top vertex TVec2fVect::const_iterator pHighestRight = pHighest; // we seek this vertex while (Next(pHighestRight, V)->y == fHighest) { pHighestRight = Next(pHighestRight, V); } // iterator to the first vertex after pHighestRight, that has the same y than the highest vertex TVec2fVect::const_iterator pHighestLeft = Next(pHighestRight, V); // seek the vertex while (pHighestLeft->y != fHighest) { pHighestLeft = Next(pHighestLeft, V); } TVec2fVect::const_iterator pPrevHighestLeft = Prev(pHighestLeft, V); // we need to get the orientation of the polygon // There are 2 case : flat, and non-flat top // check for flat top if (pHighestLeft->x != pHighestRight->x) { // compare right and left side if (pHighestLeft->x > pHighestRight->x) { ccw = true; // the list is CCW oriented std::swap(pHighestLeft, pHighestRight); } else { ccw = false; // the list is CW oriented } } else { // The top of the poly is sharp // We perform a cross product of the 2 highest vect to get its orientation const float deltaXN = Next(pHighestRight, V)->x - pHighestRight->x; const float deltaYN = Next(pHighestRight, V)->y - pHighestRight->y; const float deltaXP = pPrevHighestLeft->x - pHighestLeft->x; const float deltaYP = pPrevHighestLeft->y - pHighestLeft->y; if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0) { ccw = true; // the list is CCW oriented std::swap(pHighestLeft, pHighestRight); } else { ccw = false; // the list is CW oriented } } // compute borders TVec2fVect::const_iterator currV, nextV; // current and next vertex if (!ccw) // clock wise order ? { currV = pHighestRight ; // compute right edge from top to bottom do { nextV = Next(currV, V); ScanEdge(borders, iHighest, *currV, *nextV, true); currV = nextV; } while (currV != pLowest); // repeat until we reach the bottom vertex // compute left edge from bottom to top do { nextV = Next(currV, V); ScanEdge(borders, iHighest, *nextV, *currV, false); currV = nextV; } while (currV != pHighestLeft); } else // ccw order { currV = pHighestLeft; // compute left edge from top to bottom do { nextV = Next(currV, V); ScanEdge(borders, iHighest, *currV, *nextV, false) ; currV = nextV; } while (currV != pLowest) ; // compute right edge from bottom to top do { nextV = Next(currV, V); ScanEdge(borders, iHighest, *nextV, *currV, true); currV = nextV; } while (currV != pHighestRight) ; } }

void NLMISC::CPolygon2D::computeInnerBorders (  TRasterVect &  borders, sint &  minimumY )

The same as compute borders, but pixel are seen as surfaces and not as points In this version, only pixels that are entirely INSIDE the poly are kept Definition at line 1618 of file polygon.cpp. References min, NLMISC::ScanInnerEdge(), sint, TRasterVect, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. { if (Vertices.empty()) { borders.clear(); minimumY = -1; return; } const CVector2f *first = &Vertices[0]; const CVector2f *last = first + Vertices.size(); const CVector2f *curr = first, *next, *plowest ,*phighest; const CVector2f *pHighestRight, *pHighestRightNext, *pHighestLeft; const CVector2f *pPrevHighestLeft; double deltaXN, deltaYN, deltaXP, deltaYP; bool ccw; // true if CCW oriented sint polyHeight; sint highest, lowest; float fright = curr->x; float fleft = curr->x; float fhighest = curr->y; float flowest = curr->y; plowest = phighest = curr; // compute highest (with lowest y) and lowest (with highest y) points of the poly do { fright = std::max(fright, curr->x); fleft = std::min(fleft, curr->x); if (curr->y > flowest) { flowest = curr->y; plowest = curr; } if (curr->y < fhighest) { fhighest = curr->y; phighest = curr; } ++curr; } while (curr != last); highest = (sint) floorf(fhighest); lowest = (sint) ceilf(flowest); polyHeight = lowest - highest; if (polyHeight == 0) return; // make room for rasters borders.resize(polyHeight); // fill with xmin / xman sint ileft = (sint) floorf(fleft) - 1; sint iright = (sint) ceilf(fright); for(TRasterVect::iterator it = borders.begin(); it != borders.end(); ++it) { it->second = iright; it->first = ileft; } minimumY = highest; pHighestRight = phighest; for (;;) { pHighestRightNext = pHighestRight + 1; if (pHighestRightNext == last) pHighestRightNext = first; if (pHighestRightNext->y != pHighestRight->y) break; pHighestRight = pHighestRightNext; } pPrevHighestLeft = pHighestRight; pHighestLeft = pHighestRight; ++pHighestLeft; if (pHighestLeft == last) pHighestLeft = first; while (pHighestLeft->y != fhighest) { pPrevHighestLeft = pHighestLeft; ++pHighestLeft; if (pHighestLeft == last) pHighestLeft = first; } // we need to get the orientation of the polygon // There are 2 case : flat, and non-flat top // check for flat top if (pHighestLeft->x != pHighestRight->x) { // compare right and left side if (pHighestLeft->x > pHighestRight->x) { ccw = true; // the list is CCW oriented std::swap(pHighestLeft, pHighestRight); } else { ccw = false; // the list is CW oriented } } else { pHighestRightNext = pHighestRight + 1; if (pHighestRightNext == last) pHighestRightNext = first; deltaXN = pHighestRightNext->x - pHighestRight->x; deltaYN = pHighestRightNext->y - pHighestRight->y; deltaXP = pPrevHighestLeft->x - pHighestLeft->x; deltaYP = pPrevHighestLeft->y - pHighestLeft->y; if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0) { ccw = true; std::swap(pHighestLeft, pHighestRight); } else { ccw = false; } } if (!ccw) { // cw oriented curr = pHighestRight; do { next = curr + 1; if (next == last) next = first; ScanInnerEdge(&borders[0], curr->x, curr->y, next->x, next->y, minimumY, true); curr = next; } while (curr != plowest); do { next = curr + 1; if (next == last) next = first; ScanInnerEdge(&borders[0], next->x, next->y, curr->x, curr->y, minimumY, false); curr = next; } while (curr != pHighestLeft); } else { // ccw oriented curr = pHighestLeft; do { next = curr + 1; if (next == last) next = first; ScanInnerEdge(&borders[0], curr->x, curr->y, next->x, next->y, minimumY, false); curr = next; } while (curr != plowest); do { next = curr + 1; if (next == last) next = first; ScanInnerEdge(&borders[0], next->x, next->y, curr->x, curr->y, minimumY, true); curr = next; } while (curr != pHighestRight); } // fix for top if (floorf(fhighest) != fhighest) { borders[0].first = 1; borders[0].second = 0; } // fix for bottom if (floorf(flowest) != flowest) { borders.back().first = 1; borders.back().second = 0; } }

void NLMISC::CPolygon2D::computeOuterBorders (  TRasterVect &  borders, sint &  minimumY )

The same as compute borders, but pixel are seen as surfaces and not as points. Any pixel that is touched by the poly will be selected Definition at line 1344 of file polygon.cpp. References min, nlassert, NLMISC::ScanOuterEdgeLeft(), NLMISC::ScanOuterEdgeRight(), sint, TRasterVect, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. { // NB : this version is not much optimized, because of the min/max test // during rasterization. // TODO : optimize if needed ... if (Vertices.empty()) { borders.clear(); minimumY = -1; return; } const CVector2f *first = &Vertices[0]; const CVector2f *last = first + Vertices.size(); const CVector2f *curr = first, *next, *plowest ,*phighest; const CVector2f *pHighestRight, *pHighestRightNext, *pHighestLeft; const CVector2f *pPrevHighestLeft; double deltaXN, deltaYN, deltaXP, deltaYP; bool ccw; // true if CCW oriented sint polyHeight; sint highest, lowest; float fright = curr->x; float fleft = curr->x; float fhighest = curr->y; float flowest = curr->y; plowest = phighest = curr; // compute highest and lowest pos of the poly do { fright = std::max(fright, curr->x); fleft = std::min(fleft, curr->x); if (curr->y > flowest) { flowest = curr->y; plowest = curr; } if (curr->y < fhighest) { fhighest = curr->y; phighest = curr; } ++curr; } while (curr != last); highest = (sint) floorf(fhighest); lowest = (sint) floorf(flowest); polyHeight = lowest - highest + 1; nlassert(polyHeight > 0); // make room for rasters borders.resize(polyHeight); // fill with xmin / xman sint ileft = (sint) floorf(fleft); sint iright = (sint) ceilf(fright); for(TRasterVect::iterator it = borders.begin(); it != borders.end(); ++it) { it->second = ileft; it->first = iright; } minimumY = highest; pHighestRight = phighest; for (;;) { pHighestRightNext = pHighestRight + 1; if (pHighestRightNext == last) pHighestRightNext = first; if (pHighestRightNext->y != pHighestRight->y) break; pHighestRight = pHighestRightNext; } pPrevHighestLeft = pHighestRight; pHighestLeft = pHighestRight; ++pHighestLeft; if (pHighestLeft == last) pHighestLeft = first; while (pHighestLeft->y != fhighest) { pPrevHighestLeft = pHighestLeft; ++pHighestLeft; if (pHighestLeft == last) pHighestLeft = first; } // we need to get the orientation of the polygon // There are 2 case : flat, and non-flat top // check for flat top if (pHighestLeft->x != pHighestRight->x) { // compare right and left side if (pHighestLeft->x > pHighestRight->x) { ccw = true; // the list is CCW oriented std::swap(pHighestLeft, pHighestRight); } else { ccw = false; // the list is CW oriented } } else { pHighestRightNext = pHighestRight + 1; if (pHighestRightNext == last) pHighestRightNext = first; deltaXN = pHighestRightNext->x - pHighestRight->x; deltaYN = pHighestRightNext->y - pHighestRight->y; deltaXP = pPrevHighestLeft->x - pHighestLeft->x; deltaYP = pPrevHighestLeft->y - pHighestLeft->y; if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0) { ccw = true; std::swap(pHighestLeft, pHighestRight); } else { ccw = false; } } if (!ccw) { // clock wise oriented list curr = pHighestRight; do { next = curr + 1; if (next == last) next = first; ScanOuterEdgeRight(&borders[0], curr->x, curr->y, next->x, next->y, minimumY); curr = next; } while (curr != plowest); do { next = curr + 1; if (next == last) next = first; ScanOuterEdgeLeft(&borders[0], next->x, next->y, curr->x, curr->y, minimumY); curr = next; } while (curr != pHighestLeft); } else { // ccw oriented curr = pHighestLeft; do { next = curr + 1; if (next == last) next = first; ScanOuterEdgeLeft(&borders[0], curr->x, curr->y, next->x, next->y, minimumY); curr = next; } while (curr != plowest); do { next = curr + 1; if (next == last) next = first; ScanOuterEdgeRight(&borders[0], next->x, next->y, curr->x, curr->y, minimumY); curr = next; } while (curr != pHighestRight); } }

bool NLMISC::CPolygon2D::contains (  const CVector2f &  p  )  const

Check wether a point is contained by this poly. get the orientation of this poly contains the seg 2d equation don't check against a null segment get the line equation of the current segment contains the seg 2d equation Definition at line 1896 of file polygon.cpp. References getLineEquation(), getNonNullSeg(), getSegRef0(), getSegRef1(), nlassert, uint, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. Referenced by intersect(). { nlassert(Vertices.size() > 0); uint nonNullSegIndex; if (getNonNullSeg(nonNullSegIndex)) { float a0, b0, c0; getLineEquation(nonNullSegIndex, a0, b0, c0); for (uint k = 0; k < Vertices.size(); ++k) { if ( (getSegRef0(k) - getSegRef1(k)).sqrnorm() == 0.f) continue; float a, b, c; getLineEquation(k, a, b, c); if (a * p.x + b * p.y + c < 0) return false; } return true; } else // this poly is just a point { return p == Vertices[0]; } }

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

get the best triplet of vector. e.g the triplet that has the best surface Definition at line 967 of file polygon.cpp. References nlassert, uint, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. { 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) { CVector2f v0 = Vertices[j] - Vertices[i]; CVector2f v1 = Vertices[k] - Vertices[i]; float area = fabsf((CVector(v0.x, v0.y, 0) ^ CVector(v1.x, v1.y, 0)).norm()); if (area > bestArea) { bestArea = area; index0 = i; index1 = j; index2 = k; } } } } } } }

void NLMISC::CPolygon2D::getLineEquation (  uint  index, float &  a, float &  b, float &  c )  const

Get a line equation of the seg starting at the given index. Definition at line 1844 of file polygon.cpp. References getSegRef0(), getSegRef1(), index, nlassert, uint, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. Referenced by contains(), and intersect(). { nlassert(index < Vertices.size()); const CVector2f &v0 = getSegRef0(index); const CVector2f &v1 = getSegRef1(index); NLMISC::CVector2f seg = v0 - v1; a = seg.y; b = - seg.x; c = - v0.x * a - v0.y * b; }

bool NLMISC::CPolygon2D::getNonNullSeg (  uint &  seg  )  const

Get the index of a segment of this poly that is a non null segment. Returns: true if such a segment was found Definition at line 1810 of file polygon.cpp. References index, nlassert, sint, and uint. Referenced by contains(), and intersect(). { nlassert(Vertices.size() > 0); float bestLength = 0.f; sint bestIndex = -1; for (uint k = 0; k < Vertices.size() - 1; ++k) { float norm2 = (Vertices[k + 1] - Vertices[k]).sqrnorm(); if ( norm2 > bestLength) { bestLength = norm2; bestIndex = (int) k; } } float norm2 = (Vertices[Vertices.size() - 1] - Vertices[0]).sqrnorm(); if ( norm2 > bestLength) { index = Vertices.size() - 1; return true; } if (bestIndex != -1) { index = bestIndex; return true; } else { return false; } }

const CVector2f& NLMISC::CPolygon2D::getSegRef0 (  uint  index  )  const [inline, private]

Get ref to the first vertex that start at index. Definition at line 197 of file polygon.h. References index, nlassert, and uint. Referenced by contains(), getLineEquation(), and intersect(). { nlassert(index < Vertices.size()); return Vertices[index]; }

const CVector2f& NLMISC::CPolygon2D::getSegRef1 (  uint  index  )  const [inline, private]

Definition at line 201 of file polygon.h. References index, nlassert, and uint. Referenced by contains(), getLineEquation(), and intersect(). { nlassert(index < Vertices.size()); return index == Vertices.size() - 1 ? Vertices[0] : Vertices[index + 1]; }

bool NLMISC::CPolygon2D::intersect (  const CPolygon2D &  other  )  const

Test wether this polygon intersect another convex polygon. Currently not optimized. get the orientation of this poly contains the seg 2d equation don't check against a null segment get the line equation of the current segment contains the seg 2d equation Definition at line 1857 of file polygon.cpp. References contains(), getLineEquation(), getNonNullSeg(), getSegRef0(), getSegRef1(), nlassert, sumDPAgainstLine(), uint, Vertices, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. Referenced by NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(). { nlassert(other.Vertices.size() > 0); uint nonNullSegIndex; if (getNonNullSeg(nonNullSegIndex)) { float a0, b0, c0; getLineEquation(nonNullSegIndex, a0, b0, c0); float orient = sumDPAgainstLine(a0, b0, c0); for (uint k = 0; k < Vertices.size(); ++k) { if ( (getSegRef0(k) - getSegRef1(k)).sqrnorm() == 0.f) continue; float a, b, c; getLineEquation(k, a, b, c); uint l; for (l = 0; l < other.Vertices.size(); ++l) { const CVector2f &ov = other.Vertices[l]; if ( orient * (ov.x * a + ov.y * b +c) > 0.f) break; } if (l == other.Vertices.size()) // all point on the outside { return false; // outside } } return true; } else // this poly is just a point { return other.contains(Vertices[0]); } }

bool NLMISC::CPolygon2D::isConvex (   )

Check wether this polygon is convex;. Definition at line 798 of file polygon.cpp. References NLMISC::CPlane::make(), NLMISC::CVector::set(), uint, x, and y. { bool Front = true, Back = false; // we apply a dummy algo for now : check wether every vertex is in the same side // of every plane defined by a segment of this poly uint numVerts = Vertices.size(); if (numVerts < 3) return true; CVector segStart, segEnd; CPlane clipPlane; for (TVec2fVect::const_iterator it = Vertices.begin(); it != Vertices.end(); ++it) { segStart.set(it->x, it->y, 0); // segment start segEnd.set((it + 1)->x, (it + 1)->y, 0); // segment end float n = (segStart - segEnd).norm(); // segment norm if (n != 0) { clipPlane.make(segStart, segEnd, (n > 10 ? n : 10) * CVector::K + segStart); // make a plane, with this segment and the poly normal // check each other vertices against this plane for (TVec2fVect::const_iterator it2 = Vertices.begin(); it2 != Vertices.end(); ++it2) { if (it2 != it && it2 != (it + 1)) // the vertices must not be part of the test plane (because of imprecision) { float dist = clipPlane * CVector(it2->x, it2-> y, 0); if (dist != 0) // midlle pos { if (dist > 0) Front = true; else Back = true; if (Front && Back) return false; // there are both front end back vertices -> failure } } } } } return true; }

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

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

float NLMISC::CPolygon2D::sumDPAgainstLine (  float  a, float  b, float  c )  const [private]

Sum the dot product of this poly vertices against a plane. Definition at line 1797 of file polygon.cpp. References uint, NLMISC::CVector2f::x, and NLMISC::CVector2f::y. Referenced by intersect(). { float sum = 0.f; for (uint k = 0; k < Vertices.size(); ++k) { const CVector2f &p = Vertices[k]; sum += a * p.x + b * p.y + c; } return sum; }

void NLMISC::CPolygon2D::swap (  CPolygon2D &  other  )  [inline]

Definition at line 132 of file polygon.h. References Vertices. { Vertices.swap(other.Vertices); }

---

Field Documentation

TVec2fVect NLMISC::CPolygon2D::Vertices

Definition at line 126 of file polygon.h. Referenced by buildConvexHull(), NL3D::CLodCharacterShapeBuild::compile(), NL3D::CWaterShape::computeBBox(), NL3D::CWaterModel::computeClippedPoly(), NL3D::CWaterModel::computeSimpleClippedPoly(), NL3D::CZoneLighter::computeTileFlagsForPositionTowardWater(), NL3D::CWaterModel::doSimpleRender(), NL3D::CWaterShape::getShapeInWorldSpace(), intersect(), NLMISC::operator<(), NLMISC::operator==(), RenderTriangle(), NL3D::CWaterShape::setShape(), swap(), and NL3D::CWaterModel::traverseRender().

---

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

• polygon.h
• polygon.cpp

---