#include <polygon.h>
Nevrax France
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.
Definition at line 60 of file polygon.h. Referenced by toConvexPolygons().
00060 {} |
|
Constructor. Init with a triangle.
Definition at line 46 of file polygon.cpp.
|
|
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.
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 } |
|
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.
Definition at line 624 of file polygon.cpp. References index, NLMISC::CBSPNode2v::intersect(), toConvexPolygonsLocalAndBSP(), uint, and Vertices.
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 } |
|
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().
00090 { 00091 if(planes.size()==0) 00092 return; 00093 clip(&(*planes.begin()), planes.size()); 00094 } |
|
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().
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 } |
|
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().
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 } |
|
Definition at line 64 of file polygon.h. References sint. Referenced by clip(), NLMISC::CAABBox::intersect(), and NL3D::CZoneLighter::lightWater().
00064 {return Vertices.size();} |
|
Serial this polygon.
Definition at line 99 of file polygon.cpp.
00100 { 00101 f.serialVersion(0); 00102 f.serialCont(Vertices); 00103 } |
|
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.
Definition at line 440 of file polygon.cpp. References CPolygon(), nlassert, toConvexPolygonsDiagonal(), toConvexPolygonsLocalAndBSP(), uint, and Vertices.
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 } |
|
Definition at line 375 of file polygon.cpp. References NLMISC::CBSPNode2v::intersect(), toConvexPolygonsInCone(), and uint. Referenced by toConvexPolygons().
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 } |
|
Definition at line 177 of file polygon.cpp. References NLMISC::CVector2f::x, and NLMISC::CVector2f::y.
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 } |
|
Definition at line 351 of file polygon.cpp. References toConvexPolygonsLeft(), toConvexPolygonsLeftOn(), and uint. Referenced by toConvexPolygonsDiagonal().
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 } |
|
Definition at line 337 of file polygon.cpp. References uint. Referenced by toConvexPolygonsInCone().
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 }
|
|
Definition at line 344 of file polygon.cpp. References uint. Referenced by toConvexPolygonsInCone().
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 }
|
|
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().
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 } |
|