Date: Sat, 11 Aug 2018 20:21:34 +0200 Subject: Initial commit --- docs/doxygen/nel/a03101.html | 1770 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1770 insertions(+) create mode 100644 docs/doxygen/nel/a03101.html (limited to 'docs/doxygen/nel/a03101.html') diff --git a/docs/doxygen/nel/a03101.html b/docs/doxygen/nel/a03101.html new file mode 100644 index 00000000..ad9605cc --- /dev/null +++ b/docs/doxygen/nel/a03101.html @@ -0,0 +1,1770 @@ + + +NeL: NLMISC::CPolygon2D class Reference + + + +

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. +
+
00129 {} +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + +
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. +
+
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 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + +
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. +
+
01929 { +01930 Vertices.resize(3); +01931 NLMISC::CVector proj[3] = { projMat * tri.V0, projMat * tri.V1, projMat * tri.V2 }; +01932 Vertices[0].set(proj[0].x, proj[0].y); +01933 Vertices[1].set(proj[1].x, proj[1].y); +01934 Vertices[2].set(proj[2].x, proj[2].y); +01935 } +

+

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. +
+
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 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + +
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(). +
+
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 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + +
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. +
+
01619 { +01620 if (Vertices.empty()) +01621 { +01622 borders.clear(); +01623 minimumY = -1; +01624 return; +01625 } +01626 const CVector2f *first = &Vertices[0]; +01627 const CVector2f *last = first + Vertices.size(); +01628 +01629 const CVector2f *curr = first, *next, *plowest ,*phighest; +01630 const CVector2f *pHighestRight, *pHighestRightNext, *pHighestLeft; +01631 const CVector2f *pPrevHighestLeft; +01632 double deltaXN, deltaYN, deltaXP, deltaYP; +01633 bool ccw; // true if CCW oriented +01634 sint polyHeight; +01635 sint highest, lowest; +01636 +01637 float fright = curr->x; +01638 float fleft = curr->x; +01639 float fhighest = curr->y; +01640 float flowest = curr->y; +01641 plowest = phighest = curr; +01642 +01643 // compute highest (with lowest y) and lowest (with highest y) points of the poly +01644 do +01645 { +01646 fright = std::max(fright, curr->x); +01647 fleft = std::min(fleft, curr->x); +01648 if (curr->y > flowest) +01649 { +01650 flowest = curr->y; +01651 plowest = curr; +01652 } +01653 if (curr->y < fhighest) +01654 { +01655 fhighest = curr->y; +01656 phighest = curr; +01657 } +01658 ++curr; +01659 } +01660 while (curr != last); +01661 +01662 +01663 highest = (sint) floorf(fhighest); +01664 lowest = (sint) ceilf(flowest); +01665 +01666 polyHeight = lowest - highest; +01667 if (polyHeight == 0) return; +01668 +01669 // make room for rasters +01670 borders.resize(polyHeight); +01671 // fill with xmin / xman +01672 sint ileft = (sint) floorf(fleft) - 1; +01673 sint iright = (sint) ceilf(fright); +01674 for(TRasterVect::iterator it = borders.begin(); it != borders.end(); ++it) +01675 { +01676 it->second = iright; +01677 it->first = ileft; +01678 } +01679 +01680 minimumY = highest; +01681 pHighestRight = phighest; +01682 for (;;) +01683 { +01684 pHighestRightNext = pHighestRight + 1; +01685 if (pHighestRightNext == last) pHighestRightNext = first; +01686 if (pHighestRightNext->y != pHighestRight->y) break; +01687 pHighestRight = pHighestRightNext; +01688 } +01689 +01690 pPrevHighestLeft = pHighestRight; +01691 pHighestLeft = pHighestRight; +01692 ++pHighestLeft; +01693 if (pHighestLeft == last) pHighestLeft = first; +01694 +01695 while (pHighestLeft->y != fhighest) +01696 { +01697 pPrevHighestLeft = pHighestLeft; +01698 ++pHighestLeft; +01699 if (pHighestLeft == last) pHighestLeft = first; +01700 } +01701 +01702 +01703 // we need to get the orientation of the polygon +01704 // There are 2 case : flat, and non-flat top +01705 +01706 // check for flat top +01707 if (pHighestLeft->x != pHighestRight->x) +01708 { +01709 // compare right and left side +01710 if (pHighestLeft->x > pHighestRight->x) +01711 { +01712 ccw = true; // the list is CCW oriented +01713 std::swap(pHighestLeft, pHighestRight); +01714 } +01715 else +01716 { +01717 ccw = false; // the list is CW oriented +01718 } +01719 } +01720 else +01721 { +01722 pHighestRightNext = pHighestRight + 1; +01723 if (pHighestRightNext == last) pHighestRightNext = first; +01724 deltaXN = pHighestRightNext->x - pHighestRight->x; +01725 deltaYN = pHighestRightNext->y - pHighestRight->y; +01726 deltaXP = pPrevHighestLeft->x - pHighestLeft->x; +01727 deltaYP = pPrevHighestLeft->y - pHighestLeft->y; +01728 if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0) +01729 { +01730 ccw = true; +01731 std::swap(pHighestLeft, pHighestRight); +01732 } +01733 else +01734 { +01735 ccw = false; +01736 } +01737 } +01738 +01739 if (!ccw) +01740 { +01741 // cw oriented +01742 curr = pHighestRight; +01743 do +01744 { +01745 next = curr + 1; +01746 if (next == last) next = first; +01747 ScanInnerEdge(&borders[0], curr->x, curr->y, next->x, next->y, minimumY, true); +01748 curr = next; +01749 } +01750 while (curr != plowest); +01751 do +01752 { +01753 next = curr + 1; +01754 if (next == last) next = first; +01755 ScanInnerEdge(&borders[0], next->x, next->y, curr->x, curr->y, minimumY, false); +01756 curr = next; +01757 } +01758 while (curr != pHighestLeft); +01759 } +01760 else +01761 { +01762 // ccw oriented +01763 curr = pHighestLeft; +01764 do +01765 { +01766 next = curr + 1; +01767 if (next == last) next = first; +01768 ScanInnerEdge(&borders[0], curr->x, curr->y, next->x, next->y, minimumY, false); +01769 curr = next; +01770 } +01771 while (curr != plowest); +01772 do +01773 { +01774 next = curr + 1; +01775 if (next == last) next = first; +01776 ScanInnerEdge(&borders[0], next->x, next->y, curr->x, curr->y, minimumY, true); +01777 curr = next; +01778 } +01779 while (curr != pHighestRight); +01780 } +01781 // fix for top +01782 if (floorf(fhighest) != fhighest) +01783 { +01784 borders[0].first = 1; +01785 borders[0].second = 0; +01786 } +01787 // fix for bottom +01788 if (floorf(flowest) != flowest) +01789 { +01790 borders.back().first = 1; +01791 borders.back().second = 0; +01792 } +01793 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + +
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. +
+
01345 { +01346 // NB : this version is not much optimized, because of the min/max test +01347 // during rasterization. +01348 // TODO : optimize if needed ... +01349 +01350 if (Vertices.empty()) +01351 { +01352 borders.clear(); +01353 minimumY = -1; +01354 return; +01355 } +01356 const CVector2f *first = &Vertices[0]; +01357 const CVector2f *last = first + Vertices.size(); +01358 +01359 const CVector2f *curr = first, *next, *plowest ,*phighest; +01360 const CVector2f *pHighestRight, *pHighestRightNext, *pHighestLeft; +01361 const CVector2f *pPrevHighestLeft; +01362 double deltaXN, deltaYN, deltaXP, deltaYP; +01363 bool ccw; // true if CCW oriented +01364 sint polyHeight; +01365 sint highest, lowest; +01366 +01367 float fright = curr->x; +01368 float fleft = curr->x; +01369 float fhighest = curr->y; +01370 float flowest = curr->y; +01371 plowest = phighest = curr; +01372 +01373 // compute highest and lowest pos of the poly +01374 do +01375 { +01376 fright = std::max(fright, curr->x); +01377 fleft = std::min(fleft, curr->x); +01378 if (curr->y > flowest) +01379 { +01380 flowest = curr->y; +01381 plowest = curr; +01382 } +01383 if (curr->y < fhighest) +01384 { +01385 fhighest = curr->y; +01386 phighest = curr; +01387 } +01388 ++curr; +01389 } +01390 while (curr != last); +01391 +01392 +01393 highest = (sint) floorf(fhighest); +01394 lowest = (sint) floorf(flowest); +01395 +01396 polyHeight = lowest - highest + 1; +01397 nlassert(polyHeight > 0); +01398 +01399 // make room for rasters +01400 borders.resize(polyHeight); +01401 // fill with xmin / xman +01402 sint ileft = (sint) floorf(fleft); +01403 sint iright = (sint) ceilf(fright); +01404 for(TRasterVect::iterator it = borders.begin(); it != borders.end(); ++it) +01405 { +01406 it->second = ileft; +01407 it->first = iright; +01408 } +01409 +01410 +01411 minimumY = highest; +01412 pHighestRight = phighest; +01413 for (;;) +01414 { +01415 pHighestRightNext = pHighestRight + 1; +01416 if (pHighestRightNext == last) pHighestRightNext = first; +01417 if (pHighestRightNext->y != pHighestRight->y) break; +01418 pHighestRight = pHighestRightNext; +01419 } +01420 +01421 pPrevHighestLeft = pHighestRight; +01422 pHighestLeft = pHighestRight; +01423 ++pHighestLeft; +01424 if (pHighestLeft == last) pHighestLeft = first; +01425 +01426 while (pHighestLeft->y != fhighest) +01427 { +01428 pPrevHighestLeft = pHighestLeft; +01429 ++pHighestLeft; +01430 if (pHighestLeft == last) pHighestLeft = first; +01431 } +01432 +01433 +01434 // we need to get the orientation of the polygon +01435 // There are 2 case : flat, and non-flat top +01436 +01437 // check for flat top +01438 if (pHighestLeft->x != pHighestRight->x) +01439 { +01440 // compare right and left side +01441 if (pHighestLeft->x > pHighestRight->x) +01442 { +01443 ccw = true; // the list is CCW oriented +01444 std::swap(pHighestLeft, pHighestRight); +01445 } +01446 else +01447 { +01448 ccw = false; // the list is CW oriented +01449 } +01450 } +01451 else +01452 { +01453 pHighestRightNext = pHighestRight + 1; +01454 if (pHighestRightNext == last) pHighestRightNext = first; +01455 deltaXN = pHighestRightNext->x - pHighestRight->x; +01456 deltaYN = pHighestRightNext->y - pHighestRight->y; +01457 deltaXP = pPrevHighestLeft->x - pHighestLeft->x; +01458 deltaYP = pPrevHighestLeft->y - pHighestLeft->y; +01459 if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0) +01460 { +01461 ccw = true; +01462 std::swap(pHighestLeft, pHighestRight); +01463 } +01464 else +01465 { +01466 ccw = false; +01467 } +01468 } +01469 +01470 if (!ccw) +01471 { +01472 // clock wise oriented list +01473 curr = pHighestRight; +01474 do +01475 { +01476 next = curr + 1; +01477 if (next == last) next = first; +01478 ScanOuterEdgeRight(&borders[0], curr->x, curr->y, next->x, next->y, minimumY); +01479 curr = next; +01480 } +01481 while (curr != plowest); +01482 do +01483 { +01484 next = curr + 1; +01485 if (next == last) next = first; +01486 ScanOuterEdgeLeft(&borders[0], next->x, next->y, curr->x, curr->y, minimumY); +01487 curr = next; +01488 } +01489 while (curr != pHighestLeft); +01490 } +01491 else +01492 { +01493 // ccw oriented +01494 curr = pHighestLeft; +01495 do +01496 { +01497 next = curr + 1; +01498 if (next == last) next = first; +01499 ScanOuterEdgeLeft(&borders[0], curr->x, curr->y, next->x, next->y, minimumY); +01500 curr = next; +01501 } +01502 while (curr != plowest); +01503 do +01504 { +01505 next = curr + 1; +01506 if (next == last) next = first; +01507 ScanOuterEdgeRight(&borders[0], next->x, next->y, curr->x, curr->y, minimumY); +01508 curr = next; +01509 } +01510 while (curr != pHighestRight); +01511 } +01512 } +

+

+ + + + +
+ + + + + + + + + + +
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(). +
+
01897 { +01898 nlassert(Vertices.size() > 0); +01899 uint nonNullSegIndex; +01901 if (getNonNullSeg(nonNullSegIndex)) +01902 { +01903 float a0, b0, c0; +01904 getLineEquation(nonNullSegIndex, a0, b0, c0); +01905 +01906 for (uint k = 0; k < Vertices.size(); ++k) +01907 { +01909 if ( (getSegRef0(k) - getSegRef1(k)).sqrnorm() == 0.f) continue; +01910 +01912 float a, b, c; +01913 getLineEquation(k, a, b, c); +01914 +01915 if (a * p.x + b * p.y + c < 0) return false; +01916 +01917 } +01918 return true; +01919 } +01920 else // this poly is just a point +01921 { +01922 return p == Vertices[0]; +01923 } +01924 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + +
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. +
+
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 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
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(). +
+
01845 { +01846 nlassert(index < Vertices.size()); +01847 const CVector2f &v0 = getSegRef0(index); +01848 const CVector2f &v1 = getSegRef1(index); +01849 +01850 NLMISC::CVector2f seg = v0 - v1; +01851 a = seg.y; +01852 b = - seg.x; +01853 c = - v0.x * a - v0.y * b; +01854 } +

+

+ + + + +
+ + + + + + + + + + +
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(). +
+
01811 { +01812 nlassert(Vertices.size() > 0); +01813 float bestLength = 0.f; +01814 sint bestIndex = -1; +01815 for (uint k = 0; k < Vertices.size() - 1; ++k) +01816 { +01817 float norm2 = (Vertices[k + 1] - Vertices[k]).sqrnorm(); +01818 if ( norm2 > bestLength) +01819 { +01820 bestLength = norm2; +01821 bestIndex = (int) k; +01822 } +01823 } +01824 float norm2 = (Vertices[Vertices.size() - 1] - Vertices[0]).sqrnorm(); +01825 if ( norm2 > bestLength) +01826 { +01827 index = Vertices.size() - 1; +01828 return true; +01829 } +01830 +01831 if (bestIndex != -1) +01832 { +01833 index = bestIndex; +01834 return true; +01835 } +01836 else +01837 { +01838 return false; +01839 } +01840 } +

+

+ + + + +
+ + + + + + + + + + +
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(). +
+
00198 { +00199 nlassert(index < Vertices.size()); return Vertices[index]; +00200 } +

+

+ + + + +
+ + + + + + + + + + +
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(). +
+
00202 { +00203 nlassert(index < Vertices.size()); +00204 return index == Vertices.size() - 1 ? +00205 Vertices[0] : +00206 Vertices[index + 1]; +00207 } +

+

+ + + + +
+ + + + + + + + + + +
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(). +
+
01858 { +01859 nlassert(other.Vertices.size() > 0); +01860 uint nonNullSegIndex; +01862 if (getNonNullSeg(nonNullSegIndex)) +01863 { +01864 float a0, b0, c0; +01865 getLineEquation(nonNullSegIndex, a0, b0, c0); +01866 float orient = sumDPAgainstLine(a0, b0, c0); +01867 +01868 for (uint k = 0; k < Vertices.size(); ++k) +01869 { +01871 if ( (getSegRef0(k) - getSegRef1(k)).sqrnorm() == 0.f) continue; +01872 +01874 float a, b, c; +01875 getLineEquation(k, a, b, c); +01876 uint l; +01877 for (l = 0; l < other.Vertices.size(); ++l) +01878 { +01879 const CVector2f &ov = other.Vertices[l]; +01880 if ( orient * (ov.x * a + ov.y * b +c) > 0.f) break; +01881 } +01882 if (l == other.Vertices.size()) // all point on the outside +01883 { +01884 return false; // outside +01885 } +01886 } +01887 return true; +01888 } +01889 else // this poly is just a point +01890 { +01891 return other.contains(Vertices[0]); +01892 } +01893 } +

+

+ + + + +
+ + + + + + + + + +
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. +
+
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 } +

+

+ + + + +
+ + + + + + + + + + +
void NLMISC::CPolygon2D::serial ( NLMISC::IStream & f ) throw (NLMISC::EStream)
+
+ + + + + +
+ + + +
+Serial this polygon. +
+ +
+Definition at line 959 of file polygon.cpp. +
+
00960 { +00961 (void)f.serialVersion(0); +00962 f.serialCont(Vertices); +00963 } +

+

+ + + + +
+ + + + + + + + + + + + + + + + + + + + + + + + + +
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(). +
+
01798 { +01799 float sum = 0.f; +01800 for (uint k = 0; k < Vertices.size(); ++k) +01801 { +01802 const CVector2f &p = Vertices[k]; +01803 sum += a * p.x + b * p.y + c; +01804 } +01805 return sum; +01806 } +

+

+ + + + +
+ + + + + + + + + + +
void NLMISC::CPolygon2D::swap ( CPolygon2D & other ) [inline]
+
+ + + + + +
+ + + +
+ +
+Definition at line 132 of file polygon.h. +
+References Vertices. +
+
00132 { 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:

Generated on Tue Mar 16 13:28:15 2004 for NeL by + +

+1.3.6

+ + -- cgit v1.2.1


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.