?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'fixes' into main/rendor-staging
[ryzomcore.git] / nel / src / misc / polygon.cpp
blob856255c3480c0e68b5878941867a2d5ed3700350
1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
2 // Copyright (C) 2010 Winch Gate Property Limited
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU Affero General Public License as
6 // published by the Free Software Foundation, either version 3 of the
7 // License, or (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU Affero General Public License for more details.
13 //
14 // You should have received a copy of the GNU Affero General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16
17 #include "stdmisc.h"
18
19 #include "nel/misc/polygon.h"
20 #include "nel/misc/plane.h"
21 #include "nel/misc/triangle.h"
22
23
24 using namespace std;
25 using namespace NLMISC;
26
27 #ifdef DEBUG_NEW
28 #define new DEBUG_NEW
29 #endif
30
31 namespace NLMISC
32 {
33
34
35 //==================================//
36 // CPolygon implementation //
37 //==================================//
38
39 // ***************************************************************************
40 CPolygon::CPolygon(const CVector &a, const CVector &b, const CVector &c)
41 {
42 Vertices.reserve(3);
43 Vertices.push_back(a);
44 Vertices.push_back(b);
45 Vertices.push_back(c);
46 }
47
48 // ***************************************************************************
49 void CPolygon::toTriFan(std::vector<NLMISC::CTriangle> &dest) const
50 {
51 sint count = (sint) Vertices.size() - 2;
52 for(sint k = 0; k < count; ++k)
53 {
54 dest.push_back(CTriangle(Vertices[0], Vertices[k + 1], Vertices[k + 2]));
55 }
56 }
57
58 // ***************************************************************************
59 float CPolygon::computeArea() const
60 {
61 float area = 0.f;
62 sint numVerts = (sint) Vertices.size();
63 for(sint k = 0; k < numVerts - 2; ++k)
64 {
65 CVector v0 = Vertices[k + 1] - Vertices[0];
66 CVector v1 = Vertices[k + 2] - Vertices[0];
67 area += (v0 ^ v1).norm();
68 }
69 return 0.5f * fabsf(area);
70 }
71
72 // ***************************************************************************
73 void CPolygon::clip(const CPlane *planes, uint nPlanes)
74 {
75 if(nPlanes==0 || getNumVertices()==0)
76 return;
77
78 // The final polygon has at maximum currentVertices+number of clipping planes.
79 // For performance, the vectors are static, so reallocation rarely occurs.
80 static vector<CVector> tab0, tab1;
81 tab0.resize(getNumVertices()+nPlanes);
82 tab1.resize(getNumVertices()+nPlanes);
83 // Init tab0 with Vertices.
84 copy(Vertices.begin(), Vertices.end(), tab0.begin());
85 CVector *in=&(*tab0.begin()), *out= &(*tab1.begin());
86 sint nin= getNumVertices(), nout;
87 for(sint i=0;i<(sint)nPlanes;i++)
88 {
89 nout= planes[i].clipPolygonBack(in, out, nin);
90 swap(in, out);
91 nin= nout;
92 if(nin==0)
93 break;
94 }
95
96 // Final result in "in".
97 Vertices.resize(nin);
98 if(nin>0)
99 {
100 memcpy(&(*Vertices.begin()), in, nin*sizeof(CVector));
101 }
102 }
103
104
105 // ***************************************************************************
106 void CPolygon::clip(const std::vector<CPlane> &planes)
107 {
108 if(planes.empty())
109 return;
110 clip(&(*planes.begin()), (uint)planes.size());
111 }
112
113
114
115 // ***************************************************************************
116 void CPolygon::serial(NLMISC::IStream &f)
117 {
118 f.serialVersion(0);
119 f.serialCont(Vertices);
120 }
121
122 // ***************************************************************************
123 void CPolygon::getBestTriplet(uint &index0,uint &index1,uint &index2)
124 {
125 nlassert(Vertices.size() >= 3);
126 uint i, j, k;
127 float bestArea = 0.f;
128 const uint numVerts = (uint)Vertices.size();
129 for (i = 0; i < numVerts; ++i)
130 {
131 for (j = 0; j < numVerts; ++j)
132 {
133 if (i != j)
134 {
135 for (k = 0; k < numVerts; ++k)
136 {
137 if (k != i && k != j)
138 {
139 CVector v0 = Vertices[j] - Vertices[i];
140 CVector v1 = Vertices[k] - Vertices[i];
141 float area = (v0 ^ v1).norm();
142 if (area > bestArea)
143 {
144 bestArea = area;
145 index0 = i;
146 index1 = j;
147 index2 = k;
148 }
149 }
150 }
151 }
152 }
153 }
154
155 }
156
157 // ***************************************************************************
158 void CPolygon::buildBasis(CMatrix &dest)
159 {
160 nlassert(Vertices.size() > 3);
161 uint i1, i2, i3;
162 getBestTriplet(i1, i2, i3);
163 CVector v1 = (Vertices[i2] - Vertices[i1]).normed();
164 CVector v2 = (Vertices[i3] - Vertices[i1]).normed();
165 CVector K = v2 ^ v1;
166 CVector I = v1 - (v1 * K) * v1;
167 CVector J = K ^ I;
168 dest.setRot(I, J, K);
169 dest.setPos(Vertices[i1]);
170 }
171
172 // ***************************************************************************
173
174 class CConcavePolygonsVertexDesc
175 {
176 public:
177
178 CConcavePolygonsVertexDesc (float length, uint index)
179 {
180 Length = length;
181 Index = index;
182 }
183
184 // Length > 0
185 float Length;
186
187 // First vertex index
188 uint Index;
189 };
190 typedef std::map<float, CConcavePolygonsVertexDesc> TCConcavePolygonsVertexMap;
191
192
193 // ***************************************************************************
194 bool CPolygon::toConvexPolygonsEdgeIntersect (const CVector2f& a0, const CVector2f& a1, const CVector2f& b0, const CVector2f& b1)
195 {
196 // both vertical?
197 if( a0.x-a1.x==0 && b0.x-b1.x==0 )
198 return false;
199
200 // compute intersection of both lines
201 CVector2f intersection;
202
203 // first edge vertical?
204 if(a0.x - a1.x==0)
205 {
206 float Ab = (b0.y - b1.y) / (b0.x - b1.x);
207
208 // Intersection
209 intersection.x = a0.x;
210 intersection.y = b0.y + (a0.x-b0.x) * Ab;
211 }
212 // second edge vertical?
213 else if(b0.x - b1.x==0)
214 {
215 float Aa = (a0.y - a1.y) / (a0.x - a1.x);
216
217 // Intersection
218 intersection.x = b0.x;
219 intersection.y = a0.y + (b0.x-a0.x) * Aa;
220 }
221 // standard case
222 else
223 {
224 float Aa = (a0.y - a1.y) / (a0.x - a1.x);
225 float Ba = a0.y - a0.x * Aa;
226 float Ab = (b0.y - b1.y) / (b0.x - b1.x);
227 float Bb = b0.y - b0.x * Ab;
228
229 // colinear?
230 if(Aa==Ab)
231 return false;
232
233 // Intersection
234 intersection.x = (Bb - Ba) / (Aa - Ab);
235 intersection.y = Aa * intersection.x + Ba;
236 }
237
238 // In it ?
239 return ( ( (a0-intersection)*(a1-intersection) < 0 ) && ( (b0-intersection)*(b1-intersection) < 0 ) );
240 }
241
242 // ***************************************************************************
243
244 class CBSPNode2v
245 {
246 public:
247 CBSPNode2v ()
248 {
249 Back = NULL;
250 Front = NULL;
251 }
252 CBSPNode2v ( const CPlane &plane, CVector p0, CVector p1, uint v0, uint v1 ) : Plane (plane), P0 (p0), P1 (p1)
253 {
254 Back = NULL;
255 Front = NULL;
256 Parent = NULL;
257 V0 = v0;
258 V1 = v1;
259 }
260 ~CBSPNode2v ()
261 {
262 if (Front)
263 delete Front;
264 if (Back)
265 delete Back;
266 }
267
268 void insert (CBSPNode2v *node)
269 {
270 // Front ?
271 bool p0Front = (Plane * node->P0) > 0;
272 bool p1Front = (Plane * node->P1) > 0;
273 if (p0Front && p1Front)
274 {
275 // Front child ?
276 if (Front)
277 Front->insert (node);
278 else
279 {
280 // Link left
281 Front = node;
282 node->Parent = this;
283 }
284 }
285 else if ((!p0Front) && (!p1Front))
286 {
287 // Back child ?
288 if (Back)
289 Back->insert (node);
290 else
291 {
292 // Link left
293 Back = node;
294 node->Parent = this;
295 }
296 }
297 else
298 {
299 // Split vertex
300 CVector newVertex = Plane.intersect (node->P0, node->P1);
301
302 // New node
303 CBSPNode2v *newNode = new CBSPNode2v (node->Plane, node->P0, newVertex, node->V0, node->V1);
304
305 // Old node
306 node->P0 = newVertex;
307
308 // Insert child
309 CBSPNode2v **p0Parent;
310 CBSPNode2v **p1Parent;
311
312 // Get insertion pointer
313 if (p0Front)
314 {
315 p0Parent = &Front;
316 p1Parent = &Back;
317 }
318 else
319 {
320 p0Parent = &Back;
321 p1Parent = &Front;
322 }
323
324 // Insert children
325 if (*p0Parent)
326 {
327 (*p0Parent)->insert (newNode);
328 }
329 else
330 {
331 *p0Parent = newNode;
332 newNode->Parent = this;
333 }
334
335 // Insert children
336 if (*p1Parent)
337 {
338 (*p1Parent)->insert (node);
339 }
340 else
341 {
342 *p1Parent = node;
343 node->Parent = this;
344 }
345 }
346 }
347
348 bool intersect (const CVector &p0, const CVector &p1, uint v0, uint v1) const
349 {
350 // Front ?
351 bool p0Front = (Plane * p0) > 0;
352 bool p1Front = (Plane * p1) > 0;
353
354 if (p0Front != p1Front)
355 if ( (v0 != V0) && (v0 != V1) && (v1 != V0) && (v1 != V1) )
356 if (CPolygon::toConvexPolygonsEdgeIntersect ((CVector2f) P0, (CVector2f) P1, (CVector2f) p0, (CVector2f) p1))
357 return true;
358
359 if (p0Front || p1Front)
360 {
361 if (Front)
362 if (Front->intersect (p0, p1, v0, v1))
363 return true;
364 }
365
366 if ((!p0Front) || (!p1Front))
367 {
368 if (Back)
369 if (Back->intersect (p0, p1, v0, v1))
370 return true;
371 }
372
373 return false;
374 }
375
376 CBSPNode2v *Back, *Front, *Parent;
377 CPlane Plane;
378 CVector P0;
379 CVector P1;
380 uint V0;
381 uint V1;
382 };
383
384 // ***************************************************************************
385
386 bool CPolygon::toConvexPolygonsLeft (const std::vector<CVector> &vertex, uint a, uint b, uint c)
387 {
388 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;
389 }
390
391 // ***************************************************************************
392
393 bool CPolygon::toConvexPolygonsLeftOn (const std::vector<CVector> &vertex, uint a, uint b, uint c)
394 {
395 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;
396 }
397
398 // ***************************************************************************
399
400 bool CPolygon::toConvexPolygonsInCone (const std::vector<CVector> &vertex, uint a, uint b)
401 {
402 // Prev and next
403 uint a0 = a+1;
404 if (a0==vertex.size())
405 a0=0;
406 uint a1;
407 if (a==0)
408 a1= (uint)vertex.size()-1;
409 else
410 a1= a-1;
411
412 if (toConvexPolygonsLeftOn (vertex, a, a1, a0) )
413 {
414 return toConvexPolygonsLeft ( vertex, a, b, a0) && toConvexPolygonsLeft ( vertex, b, a, a1);
415 }
416 else
417 {
418 return !( toConvexPolygonsLeft ( vertex, a, b, a1) && toConvexPolygonsLeft ( vertex, b, a, a0) );
419 }
420 }
421
422 // ***************************************************************************
423
424 bool CPolygon::toConvexPolygonsDiagonal (const std::vector<CVector> &vertex, const CBSPNode2v &bsp, uint a, uint b)
425 {
426 // Check it is a border
427 if ( ( (b - a) == 1) || ( (a - b) == 1) || ( (a==0) && (b ==(vertex.size()-1))) || ( (b==0) && (a ==(vertex.size()-1))) )
428 return true;
429
430 // Check visibility
431 if (toConvexPolygonsInCone (vertex, a, b) && toConvexPolygonsInCone (vertex, b, a))
432 {
433 // Intersection ?
434 return !bsp.intersect (vertex[a], vertex[b], a, b);
435 }
436 return false;
437 }
438
439 // ***************************************************************************
440
441 void CPolygon::toConvexPolygonsLocalAndBSP (std::vector<CVector> &localVertices, CBSPNode2v &root, const CMatrix &basis) const
442 {
443 // Invert matrix
444 CMatrix invert = basis;
445 invert.invert ();
446
447 // Insert vertices in an ordered table
448 uint vertexCount = (uint)Vertices.size();
449 TCConcavePolygonsVertexMap vertexMap;
450 localVertices.resize (vertexCount);
451 uint i, j;
452
453 // Transform the vertex
454 for (i=0; i<vertexCount; i++)
455 {
456 CVector local = invert*Vertices[i];
457 localVertices[i] = CVector (local.x, local.y, 0);
458 }
459
460 // Plane direction
461 i=0;
462 j=(uint)Vertices.size()-1;
463 CVector normal = localVertices[i] - localVertices[j];
464 normal = normal ^ CVector::K;
465 CPlane clipPlane;
466 clipPlane.make(normal, localVertices[i]);
467
468 // Build the BSP root
469 root = CBSPNode2v (clipPlane, localVertices[i], localVertices[j], i, j);
470
471 // Insert all others edges
472 j=i++;
473 for (; i<Vertices.size(); i++)
474 {
475 // Plane direction
476 normal = localVertices[i] - localVertices[j];
477 normal = normal ^ CVector::K;
478 clipPlane.make(normal, localVertices[i]);
479
480 // Build the BSP root
481 root.insert ( new CBSPNode2v (clipPlane, localVertices[i], localVertices[j], i, j) );
482
483 j=i;
484 }
485 }
486
487
488 // ***************************************************************************
489 bool CPolygon::toConvexPolygons (std::list<CPolygon>& outputPolygons, const CMatrix& basis) const
490 {
491 // Some vertices ?
492 if (Vertices.size()>2)
493 {
494 // Local vertices
495 std::vector<CVector> localVertices;
496
497 // Build the BSP root
498 CBSPNode2v root;
499
500 // Build the local array and the BSP
501 toConvexPolygonsLocalAndBSP (localVertices, root, basis);
502
503 // Build a vertex list
504 std::list<uint> vertexList;
505 uint i;
506 for (i=0; i<Vertices.size(); i++)
507 vertexList.push_back (i);
508
509 // Clip ears while there is some polygons
510 std::list<uint>::iterator current=vertexList.begin();
511 std::list<uint>::iterator begin=vertexList.begin();
512 do
513 {
514 again:;
515 // Search for a diagonal
516 bool found = false;
517
518 // Get next vertex
519 std::list<uint>::iterator first = current;
520 std::list<uint>::iterator lastPreviousPrevious=current;
521 std::list<uint>::iterator lastPrevious=current;
522 lastPrevious++;
523 if (lastPrevious==vertexList.end())
524 lastPrevious = vertexList.begin();
525 std::list<uint>::iterator currentNext = lastPrevious;
526 std::list<uint>::iterator last = lastPrevious;
527 last++;
528 if (last==vertexList.end())
529 last = vertexList.begin();
530 while (last != current)
531 {
532 // Is a diagonal ?
533 if (
534 (toConvexPolygonsDiagonal (localVertices, root, *lastPreviousPrevious, *last)) &&
535 (toConvexPolygonsDiagonal (localVertices, root, *currentNext, *last)) &&
536 (toConvexPolygonsDiagonal (localVertices, root, *last, *current))
537 )
538 {
539 // Find one
540 found = true;
541 }
542 else
543 {
544 // Come back
545 last = lastPrevious;
546 lastPrevious = lastPreviousPrevious;
547 break;
548 }
549
550 // Next vertex
551 lastPreviousPrevious = lastPrevious;
552 lastPrevious = last++;
553 if (last==vertexList.end())
554 last = vertexList.begin();
555 }
556
557 // Last polygon ?
558 if (last==current)
559 {
560 // Add a polygon
561 outputPolygons.push_back (CPolygon());
562 CPolygon &back = outputPolygons.back ();
563 back.Vertices.reserve (vertexList.size());
564
565 // Add each vertex in the new polygon
566 current=vertexList.begin();
567 while (current!=vertexList.end())
568 {
569 back.Vertices.push_back (Vertices[*current]);
570 current++;
571 }
572
573 // Exit
574 return true;
575 }
576 else
577 {
578 std::list<uint>::iterator firstNext = current;
579 std::list<uint>::iterator firstNextNext = currentNext;
580 if (first != vertexList.begin())
581 first--;
582 else
583 {
584 first = vertexList.end();
585 first--;
586 }
587
588 while (current != first)
589 {
590 // Is a diagonal ?
591 if (
592 (toConvexPolygonsDiagonal (localVertices, root, *firstNextNext, *first)) &&
593 (toConvexPolygonsDiagonal (localVertices, root, *lastPrevious, *first)) &&
594 (toConvexPolygonsDiagonal (localVertices, root, *last, *first))
595 )
596 {
597 // Find one
598 found = true;
599 }
600 else
601 {
602 // Come back
603 first = firstNext;
604 break;
605 }
606
607 // Next vertex
608 firstNextNext = firstNext;
609 firstNext = first;
610 if (first==vertexList.begin())
611 {
612 first = vertexList.end();
613 first--;
614 }
615 else
616 first--;
617 }
618 }
619
620 // Found ?
621 if (found)
622 {
623 // Count vertex
624 outputPolygons.push_back (CPolygon());
625 CPolygon &back = outputPolygons.back ();
626
627 // Vertex count
628 uint vertexCount = 1;
629 current = first;
630 while (current != last)
631 {
632 vertexCount++;
633 current++;
634 if (current == vertexList.end())
635 current = vertexList.begin();
636 }
637
638 // Alloc vertices
639 back.Vertices.reserve (vertexCount);
640
641 // Copy and remove vertices
642 back.Vertices.push_back (Vertices[*first]);
643 first++;
644 if (first == vertexList.end())
645 first = vertexList.begin();
646 while (first != last)
647 {
648 back.Vertices.push_back (Vertices[*first]);
649
650 // Remove from list
651 first = vertexList.erase (first);
652 if (first == vertexList.end())
653 first = vertexList.begin();
654 nlassert (first != vertexList.end());
655 }
656 back.Vertices.push_back (Vertices[*first]);
657 current = begin = last;
658 goto again;
659 }
660
661 // Next current
662 current++;
663 if (current == vertexList.end())
664 current = vertexList.begin ();
665 }
666 while (current != begin);
667 }
668 return false;
669 }
670
671 // ***************************************************************************
672
673 bool CPolygon::chain (const std::vector<CPolygon> &other, const CMatrix& basis)
674 {
675 // Local vertices
676 std::vector<CVector> localVertices;
677
678 // Build the BSP root
679 CBSPNode2v root;
680
681 // Build the local array and the BSP
682 toConvexPolygonsLocalAndBSP (localVertices, root, basis);
683
684 // Local vertices
685 std::vector<std::vector<CVector> > localVerticesOther (other.size());
686
687 // Build the BSP root
688 std::vector<CBSPNode2v> rootOther (other.size());
689
690 // Build a copy of the polygons
691 std::vector<CPolygon> copy = other;
692
693 // Main copy
694 CPolygon mainCopy = *this;
695
696 // For each other polygons
697 uint o;
698 for (o=0; o<other.size(); o++)
699 {
700 // Build the local array and the BSP
701 other[o].toConvexPolygonsLocalAndBSP (localVerticesOther[o], rootOther[o], basis);
702 }
703
704 // Look for a couple..
705 uint thisCount = (uint)Vertices.size();
706 uint i, j;
707 for (o=0; o<other.size(); o++)
708 {
709 uint otherCount = (uint)other[o].Vertices.size();
710
711 // Try to link in the main polygon
712 for (i=0; i<thisCount; i++)
713 {
714 for (j=0; j<otherCount; j++)
715 {
716 // Test this segement
717 if (!root.intersect (localVertices[i], localVerticesOther[o][j], i, 0xffffffff))
718 {
719 // Test each other polygons
720 uint otherO;
721 for (otherO=0; otherO<other.size(); otherO++)
722 {
723 // Intersect ?
724 if (rootOther[otherO].intersect (localVertices[i], localVerticesOther[o][j], 0xffffffff, (otherO == o)?j:0xffffffff))
725 break;
726 }
727
728 // Continue ?
729 if (otherO==other.size())
730 {
731 // Insert new vertices
732 mainCopy.Vertices.insert (mainCopy.Vertices.begin()+i, 2+otherCount, CVector());
733
734 // Copy the first vertex
735 mainCopy.Vertices[i] = mainCopy.Vertices[i+otherCount+2];
736
737 // Copy the new vertices
738 uint k;
739 for (k=0; k<otherCount; k++)
740 {
741 uint index = j+k;
742 if (index>=otherCount)
743 index -= otherCount;
744 mainCopy.Vertices[i+k+1] = copy[o].Vertices[index];
745 }
746
747 // Copy the last one
748 mainCopy.Vertices[i+otherCount+1] = copy[o].Vertices[j];
749 break;
750 }
751 }
752 }
753 if (j!=otherCount)
754 break;
755 }
756
757 // Not found ?
758 if (i==thisCount)
759 {
760 // Try to link in the sub polygons
761 uint otherToCheck;
762 for (otherToCheck=o+1; otherToCheck<other.size(); otherToCheck++)
763 {
764 uint otherToCheckCount = (uint)other[otherToCheck].Vertices.size();
765 for (i=0; i<otherToCheckCount; i++)
766 {
767 for (j=0; j<otherCount; j++)
768 {
769 // Test this segement
770 if (!rootOther[otherToCheck].intersect (localVerticesOther[otherToCheck][i], localVerticesOther[o][j], i, 0xffffffff))
771 {
772 // Test each other polygons
773 uint otherO;
774 for (otherO=0; otherO<other.size(); otherO++)
775 {
776 // Intersect ?
777 if (rootOther[otherO].intersect (localVerticesOther[otherToCheck][i], localVerticesOther[o][j], (otherToCheck == otherO)?i:0xffffffff, (otherO == o)?j:0xffffffff))
778 break;
779 }
780
781 // Continue ?
782 if (otherO==other.size())
783 {
784 // Insert new vertices
785 copy[otherToCheck].Vertices.insert (copy[otherToCheck].Vertices.begin()+i, 2+otherCount, CVector());
786
787 // Copy the first vertex
788 copy[otherToCheck].Vertices[i] = copy[otherToCheck].Vertices[i+otherCount+2];
789
790 // Copy the new vertices
791 uint k;
792 for (k=0; k<otherCount; k++)
793 {
794 uint index = j+k;
795 if (index>=otherCount)
796 index -= otherCount;
797 copy[otherToCheck].Vertices[i+k+1] = copy[otherO].Vertices[index];
798 }
799
800 // Copy the last one
801 copy[otherToCheck].Vertices[i+otherCount+1] = copy[otherO].Vertices[j];
802 break;
803 }
804 }
805 }
806 if (j!=otherCount)
807 break;
808 }
809 if (i!=otherToCheckCount)
810 break;
811 }
812 if (otherToCheck==other.size())
813 {
814 // Not ok
815 return false;
816 }
817 }
818 }
819
820 // Ok
821 *this = mainCopy;
822 return true;
823 }
824
825 // ***************************************************************************
826
827
828 //====================================//
829 // CPolygon2d implementation //
830 //====================================//
831
832
833
834 // ***************************************************************************
835 CPolygon2D::CPolygon2D(const CPolygon &src, const CMatrix &projMat)
836 {
837 fromPolygon(src, projMat);
838 }
839
840 // ***************************************************************************
841 void CPolygon2D::fromPolygon(const CPolygon &src, const CMatrix &projMat /*=CMatrix::Identity*/)
842 {
843 uint size = (uint)src.Vertices.size();
844 Vertices.resize(size);
845 for (uint k = 0; k < size; ++k)
846 {
847 CVector proj = projMat * src.Vertices[k];
848 Vertices[k].set(proj.x, proj.y);
849 }
850 }
851
852 // ***************************************************************************
853 bool CPolygon2D::isConvex()
854 {
855 bool Front = true, Back = false;
856 // we apply a dummy algo for now : check whether every vertex is in the same side
857 // of every plane defined by a segment of this poly
858 uint numVerts = (uint)Vertices.size();
859 if (numVerts < 3) return true;
860 CVector segStart, segEnd;
861 CPlane clipPlane;
862 for (TVec2fVect::const_iterator it = Vertices.begin(); it != Vertices.end(); ++it)
863 {
864 segStart.set(it->x, it->y, 0); // segment start
865 segEnd.set((it + 1)->x, (it + 1)->y, 0); // segment end
866 float n = (segStart - segEnd).norm(); // segment norm
867 if (n != 0)
868 {
869 clipPlane.make(segStart, segEnd, (n > 10 ? n : 10) * CVector::K + segStart); // make a plane, with this segment and the poly normal
870 // check each other vertices against this plane
871 for (TVec2fVect::const_iterator it2 = Vertices.begin(); it2 != Vertices.end(); ++it2)
872 {
873 if (it2 != it && it2 != (it + 1)) // the vertices must not be part of the test plane (because of imprecision)
874 {
875
876 float dist = clipPlane * CVector(it2->x, it2-> y, 0);
877 if (dist != 0) // midlle pos
878 {
879 if (dist > 0) Front = true; else Back = true;
880 if (Front && Back) return false; // there are both front end back vertices -> failure
881 }
882 }
883 }
884 }
885 }
886 return true;
887 }
888
889 // ***************************************************************************
890
891 void CPolygon2D::buildConvexHull(CPolygon2D &dest) const
892 {
893 nlassert(&dest != this);
894
895 if (this->Vertices.size() == 3) // with 3 points it is always convex
896 {
897 dest = *this;
898 return;
899 }
900 uint k, l;
901 uint numVerts = (uint)Vertices.size();
902 CVector2f p, curr, prev;
903 uint pIndex, p1Index, p2Index, pCurr, pPrev;
904 // this is not optimized, but not used in realtime.. =)
905 nlassert(numVerts >= 3);
906 dest.Vertices.clear();
907
908 typedef std::set<uint> TIndexSet;
909 TIndexSet leftIndex;
910 for (k = 0; k < Vertices.size(); ++k)
911 {
912 leftIndex.insert(k);
913 }
914
915
916 // 1) find the highest point p of the set. We are sure it belongs to the hull
917 pIndex = 0;
918 p = Vertices[0];
919 for (k = 1; k < numVerts; ++k)
920 {
921 if (Vertices[k].y < p.y)
922 {
923 pIndex = k;
924 p = Vertices[k];
925 }
926 }
927
928 leftIndex.erase(pIndex);
929
930
931 float bestCP = 1.1f;
932 p1Index = p2Index = pIndex;
933
934 for (k = 0; k < numVerts; ++k)
935 {
936 if (k != pIndex)
937 {
938 for (l = 0; l < numVerts; ++l)
939 {
940 if (l != pIndex && l != k)
941 {
942 CVector2f seg1 = (Vertices[l] - p).normed();
943 CVector2f seg2 = (Vertices[k] - p).normed();
944
945 //CVector cp = CVector(seg1.x, seg1.y, 0) ^ CVector(seg2.x, seg2.y, 0);
946 //float n = fabsf(cp.z);
947 float n = seg1 * seg2;
948 if (n < bestCP)
949 {
950 p1Index = l;
951 p2Index = k;
952 bestCP = n;
953 }
954 }
955 }
956 }
957 }
958
959
960 leftIndex.erase(p2Index);
961
962
963
964 // start from the given triplet, and complete the poly until we reach the first point
965 pCurr = p2Index;
966 pPrev = pIndex;
967
968 curr = Vertices[pCurr];
969 prev = Vertices[pPrev];
970
971 // create the first triplet vertices
972 dest.Vertices.push_back(Vertices[p1Index]);
973 dest.Vertices.push_back(prev);
974 dest.Vertices.push_back(curr);
975
976 uint step = 0;
977
978 for(;;)
979 {
980 bestCP = 1.1f;
981 CVector2f seg2 = (prev - curr).normed();
982 TIndexSet::iterator bestIt = leftIndex.end();
983 for (TIndexSet::iterator it = leftIndex.begin(); it != leftIndex.end(); ++it)
984 {
985 if (step == 0 && *it == p1Index) continue;
986 CVector2f seg1 = (Vertices[*it] - curr).normed();
987 float n = seg1 * seg2;
988 if (n < bestCP)
989 {
990 bestCP = n;
991 bestIt = it;
992 }
993 }
994
995 nlassert(bestIt != leftIndex.end());
996 if (*bestIt == p1Index)
997 {
998 return; // if we reach the start point we have finished
999 }
1000 prev = curr;
1001 curr = Vertices[*bestIt];
1002 pPrev = pCurr;
1003 pCurr = *bestIt;
1004 // add new point to the destination
1005 dest.Vertices.push_back(curr);
1006 ++step;
1007 leftIndex.erase(bestIt);
1008 }
1009 }
1010
1011 // ***************************************************************************
1012
1013
1014 void CPolygon2D::serial(NLMISC::IStream &f)
1015 {
1016 (void)f.serialVersion(0);
1017 f.serialCont(Vertices);
1018 }
1019
1020 // ***************************************************************************
1021 /// get the best triplet of vector. e.g the triplet that has the best surface
1022 void CPolygon2D::getBestTriplet(uint &index0, uint &index1, uint &index2)
1023 {
1024 nlassert(Vertices.size() >= 3);
1025 uint i, j, k;
1026 float bestArea = 0.f;
1027 const uint numVerts = (uint)Vertices.size();
1028 for (i = 0; i < numVerts; ++i)
1029 {
1030 for (j = 0; j < numVerts; ++j)
1031 {
1032 if (i != j)
1033 {
1034 for (k = 0; k < numVerts; ++k)
1035 {
1036 if (k != i && k != j)
1037 {
1038 CVector2f v0 = Vertices[j] - Vertices[i];
1039 CVector2f v1 = Vertices[k] - Vertices[i];
1040 float area = fabsf((CVector(v0.x, v0.y, 0) ^ CVector(v1.x, v1.y, 0)).norm());
1041 if (area > bestArea)
1042 {
1043 bestArea = area;
1044 index0 = i;
1045 index1 = j;
1046 index2 = k;
1047 }
1048 }
1049 }
1050 }
1051 }
1052 }
1053 }
1054
1055
1056 /// ***************************************************************************************
1057 // scan a an edge of a poly and write it into a table
1058 static void ScanEdge(CPolygon2D::TRasterVect &outputVect, sint topY, const CVector2f &v1, const CVector2f &v2, bool rightEdge = true)
1059 {
1060 const uint rol16 = 65536;
1061 sint ceilY1 = (sint) ceilf(v1.y);
1062 sint height;
1063 float deltaX, deltaY;
1064 float fInverseSlope;
1065 sint iInverseSlope, iPosX;
1066
1067 // check whether this segment gives a contribution to the final poly
1068 height = (sint) (ceilf(v2.y) - ceilY1);
1069 if (height <= 0) return;
1070
1071 // compute slope
1072 deltaY = v2.y - v1.y;
1073 deltaX = v2.x - v1.x;
1074 fInverseSlope = deltaX / deltaY;
1075
1076
1077 CPolygon2D::TRasterVect::iterator outputIt = outputVect.begin() + (ceilY1 - topY);
1078
1079 // slope with ints
1080 iInverseSlope = (sint) (rol16 * fInverseSlope);
1081
1082 // sub-pixel accuracy
1083 iPosX = (int) (rol16 * (v1.x + fInverseSlope * (ceilY1 - v1.y)));
1084
1085 const CPolygon2D::TRasterVect::iterator endIt = outputIt + height;
1086 if (rightEdge)
1087 {
1088 do
1089 {
1090 outputIt->second = iPosX >> 16;
1091 iPosX += iInverseSlope;
1092 ++outputIt;
1093 }
1094 while (outputIt != endIt);
1095 }
1096 else
1097 {
1098 iPosX += (rol16 - 1);
1099 do
1100 {
1101 outputIt->first = iPosX >> 16;
1102 iPosX += iInverseSlope;
1103 ++outputIt;
1104 }
1105 while (outputIt != endIt);
1106 }
1107 }
1108
1109
1110 // *******************************************************************************
1111 // This function alow to cycle forward through a vertex vector like if it was a circular list
1112 static inline CPolygon2D::TVec2fVect::const_iterator Next(const CPolygon2D::TVec2fVect::const_iterator &it, const CPolygon2D::TVec2fVect &cont)
1113 {
1114 nlassert(cont.size() != 0);
1115 if ((it + 1) == cont.end()) return cont.begin();
1116 return (it + 1);
1117 }
1118
1119
1120 // *******************************************************************************
1121 // This function alow to cycle backward through a (non null) vertex vector like if it was a circular list
1122 static inline CPolygon2D::TVec2fVect::const_iterator Prev(const CPolygon2D::TVec2fVect::const_iterator &it, const CPolygon2D::TVec2fVect &cont)
1123 {
1124 nlassert(cont.size() != 0);
1125 if (it == cont.begin()) return cont.end() - 1;
1126 return (it - 1);
1127 }
1128
1129
1130 // *******************************************************************************
1131 bool CPolygon2D::isCCWOriented() const
1132 {
1133 const TVec2fVect &V = Vertices;
1134 nlassert(Vertices.size() >= 3);
1135 // compute highest and lowest pos of the poly
1136 float fHighest = V[0].y;
1137 float fLowest = fHighest;
1138 // iterators to the highest and lowest vertex
1139 TVec2fVect::const_iterator it = V.begin() ;
1140 const TVec2fVect::const_iterator endIt = V.end();
1141 TVec2fVect::const_iterator pHighest = V.begin();
1142 do
1143 {
1144 if (it->y < fHighest)
1145 {
1146 fHighest = it->y;
1147 pHighest = it;
1148 }
1149 fLowest = std::max(fLowest, it->y);
1150 ++it;
1151 }
1152 while (it != endIt);
1153 // we seek this vertex
1154 TVec2fVect::const_iterator pHighestRight = pHighest;
1155 if (fLowest == fHighest)
1156 {
1157 // special case : degenerate poly
1158 while (pHighestRight->x == pHighest->x)
1159 {
1160 pHighestRight = Next(pHighestRight, V);
1161 if (pHighestRight == pHighest) return false; // the poly is reduced to a point, returns an abritrary value
1162 }
1163 return pHighest->x <= pHighestRight->x;
1164 }
1165 // iterator to the first vertex that has an y different from the top vertex
1166 while (Next(pHighestRight, V)->y == fHighest)
1167 {
1168 pHighestRight = Next(pHighestRight, V);
1169 }
1170
1171 // iterator to the first vertex after pHighestRight, that has the same y than the highest vertex
1172 TVec2fVect::const_iterator pHighestLeft = Next(pHighestRight, V);
1173 // seek the vertex
1174 while (pHighestLeft->y != fHighest)
1175 {
1176 pHighestLeft = Next(pHighestLeft, V);
1177 }
1178 TVec2fVect::const_iterator pPrevHighestLeft = Prev(pHighestLeft, V);
1179 // we need to get the orientation of the polygon
1180 // There are 2 case : flat, and non-flat top
1181 // check for flat top
1182 if (pHighestLeft->x != pHighestRight->x)
1183 {
1184 // compare right and left side
1185 return pHighestLeft->x <= pHighestRight->x;
1186 }
1187 // The top of the poly is sharp
1188 // We perform a cross product of the 2 highest vect to get its orientation
1189 float deltaXN = Next(pHighestRight, V)->x - pHighestRight->x;
1190 float deltaYN = Next(pHighestRight, V)->y - pHighestRight->y;
1191 float deltaXP = pPrevHighestLeft->x - pHighestLeft->x;
1192 float deltaYP = pPrevHighestLeft->y - pHighestLeft->y;
1193 return (deltaXN * deltaYP - deltaYN * deltaXP) >= 0;
1194 }
1195
1196 // *******************************************************************************
1197 void CPolygon2D::computeBorders(TRasterVect &borders, sint &highestY) const
1198 {
1199 #ifdef NL_DEBUG
1200 checkValidBorders();
1201 #endif
1202 // an 'alias' to the vertices
1203 const TVec2fVect &V = Vertices;
1204 if (Vertices.size() < 3)
1205 {
1206 borders.clear();
1207 return;
1208 }
1209 bool ccw; // set to true when it has a counter clock wise orientation
1210
1211 // compute highest and lowest pos of the poly
1212 float fHighest = V[0].y;
1213 float fLowest = fHighest;
1214
1215 // iterators to the thighest and lowest vertex
1216 TVec2fVect::const_iterator pLowest = V.begin(), pHighest = V.begin();
1217 TVec2fVect::const_iterator it = V.begin() ;
1218 const TVec2fVect::const_iterator endIt = V.end();
1219 do
1220 {
1221 if (it->y > fLowest)
1222 {
1223 fLowest = it->y;
1224 pLowest = it;
1225 }
1226 else
1227 if (it->y < fHighest)
1228 {
1229 fHighest = it->y;
1230 pHighest = it;
1231 }
1232 ++it;
1233 }
1234 while (it != endIt);
1235
1236
1237 sint iHighest = (sint) ceilf(fHighest) ;
1238 sint iLowest = (sint) ceilf(fLowest) ;
1239
1240 highestY = iHighest;
1241
1242
1243 /// check poly height, and discard null height
1244 uint polyHeight = iLowest - iHighest;
1245 if (polyHeight <= 0)
1246 {
1247 borders.clear();
1248 return;
1249 }
1250
1251 borders.resize(polyHeight);
1252
1253 // iterator to the first vertex that has an y different from the top vertex
1254 TVec2fVect::const_iterator pHighestRight = pHighest;
1255 // we seek this vertex
1256 while (Next(pHighestRight, V)->y == fHighest)
1257 {
1258 pHighestRight = Next(pHighestRight, V);
1259 }
1260
1261 // iterator to the first vertex after pHighestRight, that has the same y than the highest vertex
1262 TVec2fVect::const_iterator pHighestLeft = Next(pHighestRight, V);
1263 // seek the vertex
1264 while (pHighestLeft->y != fHighest)
1265 {
1266 pHighestLeft = Next(pHighestLeft, V);
1267 }
1268
1269 TVec2fVect::const_iterator pPrevHighestLeft = Prev(pHighestLeft, V);
1270
1271 // we need to get the orientation of the polygon
1272 // There are 2 case : flat, and non-flat top
1273
1274 // check for flat top
1275 if (pHighestLeft->x != pHighestRight->x)
1276 {
1277 // compare right and left side
1278 if (pHighestLeft->x > pHighestRight->x)
1279 {
1280 ccw = true; // the list is CCW oriented
1281 std::swap(pHighestLeft, pHighestRight);
1282 }
1283 else
1284 {
1285 ccw = false; // the list is CW oriented
1286 }
1287 }
1288 else
1289 {
1290 // The top of the poly is sharp
1291 // We perform a cross product of the 2 highest vect to get its orientation
1292
1293 const float deltaXN = Next(pHighestRight, V)->x - pHighestRight->x;
1294 const float deltaYN = Next(pHighestRight, V)->y - pHighestRight->y;
1295 const float deltaXP = pPrevHighestLeft->x - pHighestLeft->x;
1296 const float deltaYP = pPrevHighestLeft->y - pHighestLeft->y;
1297 if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0)
1298 {
1299 ccw = true; // the list is CCW oriented
1300 std::swap(pHighestLeft, pHighestRight);
1301 }
1302 else
1303 {
1304 ccw = false; // the list is CW oriented
1305 }
1306 }
1307
1308
1309 // compute borders
1310 TVec2fVect::const_iterator currV, nextV; // current and next vertex
1311 if (!ccw) // clock wise order ?
1312 {
1313 currV = pHighestRight ;
1314 // compute right edge from top to bottom
1315 do
1316 {
1317 nextV = Next(currV, V);
1318 ScanEdge(borders, iHighest, *currV, *nextV, true);
1319 currV = nextV;
1320 }
1321 while (currV != pLowest); // repeat until we reach the bottom vertex
1322
1323 // compute left edge from bottom to top
1324 do
1325 {
1326 nextV = Next(currV, V);
1327 ScanEdge(borders, iHighest, *nextV, *currV, false);
1328 currV = nextV;
1329 }
1330 while (currV != pHighestLeft);
1331 }
1332 else // ccw order
1333 {
1334 currV = pHighestLeft;
1335 // compute left edge from top to bottom
1336 do
1337 {
1338 nextV = Next(currV, V);
1339 ScanEdge(borders, iHighest, *currV, *nextV, false) ;
1340 currV = nextV;
1341 }
1342 while (currV != pLowest) ;
1343
1344 // compute right edge from bottom to top
1345 do
1346 {
1347 nextV = Next(currV, V);
1348 ScanEdge(borders, iHighest, *nextV, *currV, true);
1349 currV = nextV;
1350 }
1351 while (currV != pHighestRight) ;
1352 }
1353 }
1354
1355 //=========================================================================
1356 // scan outer right edge of a poly
1357 static void ScanOuterEdgeRight(CPolygon2D::TRaster *r, float x1, float y1, float x2, float y2, sint minY)
1358 {
1359 CPolygon2D::TRaster *currRaster;
1360 float deltaX, deltaY;
1361 float inverseSlope;
1362 sint32 iInverseSlope, iposx;
1363 sint height;
1364 deltaX = x2 - x1;
1365 height = (sint) (ceilf(y2) - floorf(y1)) ;
1366 if (height <= 0) return;
1367 if (deltaX >= 0.f)
1368 {
1369 if (height == 1)
1370 {
1371 currRaster = r + ((sint) floorf(y1) - minY);
1372 currRaster->second = std::max((sint) floorf(x2), currRaster->second);
1373 }
1374 else
1375 {
1376 deltaY = y2 - y1;
1377 if(deltaY)
1378 inverseSlope = deltaX / deltaY;
1379 else
1380 inverseSlope = 0;
1381 iInverseSlope = (sint32) (65536.0 * inverseSlope);
1382 currRaster = r + ((sint) floorf(y1) - minY);
1383 iposx = (sint32) (65536.0 * (x1 + inverseSlope * (ceilf(y1) - y1))); // sub-pixel accuracy
1384 if (ceilf(y1) == y1)
1385 {
1386 iposx += iInverseSlope;
1387 }
1388 do
1389 {
1390 currRaster->second = std::max((sint) (iposx >> 16), currRaster->second);
1391 iposx += iInverseSlope;
1392 ++ currRaster;
1393 -- height;
1394 }
1395 while (height != 1);
1396 // correction for last line
1397 currRaster->second = std::max((sint) floorf(x2), currRaster->second);
1398 }
1399 }
1400 else
1401 {
1402 deltaY = y2 - y1;
1403 if(deltaY)
1404 inverseSlope = deltaX / deltaY;
1405 else
1406 inverseSlope = 0;
1407 iInverseSlope = (sint32) (65536.0 * inverseSlope);
1408 currRaster = r + ((sint) floorf(y1) - minY);
1409 currRaster->second = std::max((sint) floorf(x1), currRaster->second);
1410 ++ currRaster;
1411 iposx = (sint32) (65536.0 * (x1 + inverseSlope * (ceilf(y1) - y1))); // sub-pixel accuracy
1412 if (ceilf(y1) == y1)
1413 {
1414 iposx += iInverseSlope;
1415 }
1416 while (--height)
1417 {
1418 currRaster->second = std::max((sint) (iposx >> 16), currRaster->second);
1419 iposx += iInverseSlope;
1420 ++ currRaster;
1421 }
1422 }
1423 }
1424
1425 //=========================================================================
1426 // scan outer left edge of a poly
1427 static void ScanOuterEdgeLeft(CPolygon2D::TRaster *r, float x1, float y1, float x2, float y2, sint minY)
1428 {
1429 CPolygon2D::TRaster *currRaster;
1430 float deltaX, deltaY;
1431 float inverseSlope;
1432 sint32 iInverseSlope, iposx;
1433 sint height;
1434 deltaX = x2 - x1;
1435 height = (sint) (ceilf(y2) - floorf(y1)) ;
1436 if (height <= 0) return;
1437 if (deltaX < 0.f)
1438 {
1439 if (height == 1)
1440 {
1441 currRaster = r + ((sint) floorf(y1) - minY);
1442 currRaster->first = std::min((sint) floorf(x2), currRaster->first);
1443 }
1444 else
1445 {
1446 deltaY = y2 - y1;
1447 if(deltaY)
1448 inverseSlope = deltaX / deltaY;
1449 else
1450 inverseSlope = 0;
1451 iInverseSlope = (sint32) (65536.0 * inverseSlope);
1452 currRaster = r + ((sint) floorf(y1) - minY);
1453 iposx = (sint32) (65536.0 * (x1 + inverseSlope * (ceilf(y1) - y1))); // sub-pixel accuracy
1454 if (ceilf(y1) == y1)
1455 {
1456 iposx += iInverseSlope;
1457 }
1458 do
1459 {
1460 currRaster->first = std::min((sint) (iposx >> 16), currRaster->first);
1461 iposx += iInverseSlope;
1462 ++ currRaster;
1463 -- height;
1464 }
1465 while (height != 1);
1466 // correction for last line
1467 currRaster->first = std::min((sint) floorf(x2), currRaster->first);
1468 }
1469 }
1470 else
1471 {
1472 deltaY = y2 - y1;
1473 if(deltaY)
1474 inverseSlope = deltaX / deltaY;
1475 else
1476 inverseSlope = 0;
1477 iInverseSlope = (sint32) (65536.0 * inverseSlope);
1478 currRaster = r + ((sint) floorf(y1) - minY);
1479 currRaster->first = std::min((sint) floorf(x1), currRaster->first);
1480 ++ currRaster;
1481 iposx = (sint32) (65536.0 * (x1 + inverseSlope * (ceilf(y1) - y1))); // sub-pixel accuracy
1482 if (ceilf(y1) == y1)
1483 {
1484 iposx += iInverseSlope;
1485 }
1486 while (--height)
1487 {
1488 currRaster->first = std::min((sint) (iposx >> 16), currRaster->first);
1489 iposx += iInverseSlope;
1490 ++ currRaster;
1491 }
1492 }
1493 }
1494
1495
1496 // *******************************************************************************
1497 void CPolygon2D::computeOuterBorders(TRasterVect &borders, sint &minimumY) const
1498 {
1499 #ifdef NL_DEBUG
1500 checkValidBorders();
1501 #endif
1502 borders.clear();
1503 // NB : this version is not much optimized, because of the min/max test
1504 // during rasterization.
1505 // TODO : optimize if needed ...
1506
1507 if (Vertices.empty())
1508 {
1509 minimumY = -1;
1510 return;
1511 }
1512 const CVector2f *first = &Vertices[0];
1513 const CVector2f *last = first + Vertices.size();
1514
1515 const CVector2f *curr = first, *next, *plowest ,*phighest;
1516 const CVector2f *pHighestRight, *pHighestRightNext, *pHighestLeft;
1517 const CVector2f *pPrevHighestLeft;
1518 double deltaXN, deltaYN, deltaXP, deltaYP;
1519 bool ccw; // true if CCW oriented
1520 sint polyHeight;
1521 sint highest, lowest;
1522
1523 float fright = curr->x;
1524 float fleft = curr->x;
1525 float fhighest = curr->y;
1526 float flowest = curr->y;
1527 plowest = phighest = curr;
1528
1529 // compute highest and lowest pos of the poly
1530 do
1531 {
1532 fright = std::max(fright, curr->x);
1533 fleft = std::min(fleft, curr->x);
1534 if (curr->y > flowest)
1535 {
1536 flowest = curr->y;
1537 plowest = curr;
1538 }
1539 if (curr->y < fhighest)
1540 {
1541 fhighest = curr->y;
1542 phighest = curr;
1543 }
1544 ++curr;
1545 }
1546 while (curr != last);
1547
1548
1549 highest = (sint) floorf(fhighest);
1550 lowest = (sint) floorf(flowest);
1551
1552 polyHeight = lowest - highest + 1;
1553 nlassert(polyHeight > 0);
1554
1555 // make room for rasters
1556 borders.resize(polyHeight);
1557 // fill with xmin / xman
1558 sint ileft = (sint) floorf(fleft);
1559 sint iright = (sint) ceilf(fright);
1560 minimumY = highest;
1561 if (flowest == fhighest) // special case : degenerate poly
1562 {
1563
1564 borders.resize(1);
1565 borders.front().first = ileft;
1566 borders.front().second = ileft;
1567 return;
1568 }
1569 //
1570 for(TRasterVect::iterator it = borders.begin(); it != borders.end(); ++it)
1571 {
1572 it->second = ileft;
1573 it->first = iright;
1574 }
1575
1576
1577
1578 pHighestRight = phighest;
1579 for (;;)
1580 {
1581 pHighestRightNext = pHighestRight + 1;
1582 if (pHighestRightNext == last) pHighestRightNext = first;
1583 if (pHighestRightNext->y != pHighestRight->y) break;
1584 pHighestRight = pHighestRightNext;
1585 }
1586
1587 pPrevHighestLeft = pHighestRight;
1588 pHighestLeft = pHighestRight;
1589 ++pHighestLeft;
1590 if (pHighestLeft == last) pHighestLeft = first;
1591
1592 while (pHighestLeft->y != fhighest)
1593 {
1594 pPrevHighestLeft = pHighestLeft;
1595 ++pHighestLeft;
1596 if (pHighestLeft == last) pHighestLeft = first;
1597 }
1598
1599
1600 // we need to get the orientation of the polygon
1601 // There are 2 case : flat, and non-flat top
1602
1603 // check for flat top
1604 if (pHighestLeft->x != pHighestRight->x)
1605 {
1606 // compare right and left side
1607 if (pHighestLeft->x > pHighestRight->x)
1608 {
1609 ccw = true; // the list is CCW oriented
1610 std::swap(pHighestLeft, pHighestRight);
1611 }
1612 else
1613 {
1614 ccw = false; // the list is CW oriented
1615 }
1616 }
1617 else
1618 {
1619 pHighestRightNext = pHighestRight + 1;
1620 if (pHighestRightNext == last) pHighestRightNext = first;
1621 deltaXN = pHighestRightNext->x - pHighestRight->x;
1622 deltaYN = pHighestRightNext->y - pHighestRight->y;
1623 deltaXP = pPrevHighestLeft->x - pHighestLeft->x;
1624 deltaYP = pPrevHighestLeft->y - pHighestLeft->y;
1625 if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0)
1626 {
1627 ccw = true;
1628 std::swap(pHighestLeft, pHighestRight);
1629 }
1630 else
1631 {
1632 ccw = false;
1633 }
1634 }
1635
1636 if (!ccw)
1637 {
1638 // clock wise oriented list
1639 curr = pHighestRight;
1640 do
1641 {
1642 next = curr + 1;
1643 if (next == last) next = first;
1644 ScanOuterEdgeRight(&borders[0], curr->x, curr->y, next->x, next->y, minimumY);
1645 curr = next;
1646 }
1647 while (curr != plowest);
1648 do
1649 {
1650 next = curr + 1;
1651 if (next == last) next = first;
1652 ScanOuterEdgeLeft(&borders[0], next->x, next->y, curr->x, curr->y, minimumY);
1653 curr = next;
1654 }
1655 while (curr != pHighestLeft);
1656 }
1657 else
1658 {
1659 // ccw oriented
1660 curr = pHighestLeft;
1661 do
1662 {
1663 next = curr + 1;
1664 if (next == last) next = first;
1665 ScanOuterEdgeLeft(&borders[0], curr->x, curr->y, next->x, next->y, minimumY);
1666 curr = next;
1667 }
1668 while (curr != plowest);
1669 do
1670 {
1671 next = curr + 1;
1672 if (next == last) next = first;
1673 ScanOuterEdgeRight(&borders[0], next->x, next->y, curr->x, curr->y, minimumY);
1674 curr = next;
1675 }
1676 while (curr != pHighestRight);
1677 }
1678 }
1679
1680
1681 //=========================================================================
1682 // scan inner right edge of a poly
1683 static void ScanInnerEdge(CPolygon2D::TRaster *r, float x1, float y1, float x2, float y2, sint minY, bool rightEdge)
1684 {
1685 const uint rol16 = 65536;
1686 CPolygon2D::TRaster *currRaster;
1687 float deltaX, deltaY;
1688 float inverseSlope;
1689 sint32 iInverseSlope, iposx;
1690 sint height;
1691 deltaX = x2 - x1;
1692 height = (sint) (ceilf(y2) - floorf(y1));
1693 if (height <= 0) return;
1694 deltaY = y2 - y1;
1695 if(deltaY)
1696 inverseSlope = deltaX / deltaY;
1697 else
1698 inverseSlope = 0;
1699 iInverseSlope = (sint32) (rol16 * inverseSlope);
1700 currRaster = r + ((sint) floorf(y1) - minY);
1701 //
1702 iposx = (sint32) (rol16 * (x1 + inverseSlope * (ceilf(y1) - y1))); // sub-pixel accuracy
1703 if (rightEdge)
1704 {
1705 iposx -= rol16 - 1;
1706 if (deltaX >= 0.f)
1707 {
1708 // start of segment
1709 if (floorf(y1) != y1)
1710 {
1711 currRaster->second = std::min((sint) floorf(x1) - 1, currRaster->second);
1712 ++ currRaster;
1713 -- height;
1714 if (height == 0) return;
1715 }
1716 do
1717 {
1718 currRaster->second = std::min((sint) (iposx >> 16), currRaster->second);
1719 iposx += iInverseSlope;
1720 ++ currRaster;
1721 }
1722 while (--height);
1723 }
1724 else
1725 {
1726 // start of segment
1727 if (floorf(y1) != y1)
1728 {
1729 currRaster->second = std::min((sint) (iposx >> 16), currRaster->second);
1730 ++ currRaster;
1731 -- height;
1732 if (height == 0) return;
1733 }
1734 while (--height)
1735 {
1736 iposx += iInverseSlope;
1737 currRaster->second = std::min((sint) (iposx >> 16), currRaster->second);
1738 ++ currRaster;
1739 }
1740 // fill bottom of segment
1741 currRaster->second = std::min((sint) floorf(x2) - 1, currRaster->second);
1742 }
1743 }
1744 else
1745 {
1746 iposx += rol16 - 1;
1747 if (deltaX < 0.f)
1748 {
1749 // start of segment
1750 if (floorf(y1) != y1)
1751 {
1752 currRaster->first = std::max((sint) ceilf(x1), currRaster->first);
1753 ++ currRaster;
1754 -- height;
1755 if (height == 0) return;
1756 }
1757 do
1758 {
1759 currRaster->first = std::max((sint) (iposx >> 16), currRaster->first);
1760 iposx += iInverseSlope;
1761 ++ currRaster;
1762 }
1763 while (--height);
1764 }
1765 else
1766 {
1767 // start of segment
1768 if (floorf(y1) != y1)
1769 {
1770 currRaster->first = std::max((sint) (iposx >> 16), currRaster->first);
1771 ++ currRaster;
1772 -- height;
1773 if (height == 0) return;
1774 }
1775 while (--height)
1776 {
1777 iposx += iInverseSlope;
1778 currRaster->first = std::max((sint) (iposx >> 16), currRaster->first);
1779 ++ currRaster;
1780 }
1781 // fill bottom of segment
1782 currRaster->first = std::max((sint) ceilf(x2), currRaster->first);
1783 }
1784 }
1785 }
1786
1787 // *******************************************************************************
1788 void CPolygon2D::computeInnerBorders(TRasterVect &borders, sint &minimumY) const
1789 {
1790 #ifdef NL_DEBUG
1791 checkValidBorders();
1792 #endif
1793 borders.clear();
1794 if (Vertices.empty())
1795 {
1796 minimumY = -1;
1797 return;
1798 }
1799 const CVector2f *first = &Vertices[0];
1800 const CVector2f *last = first + Vertices.size();
1801
1802 const CVector2f *curr = first, *next, *plowest ,*phighest;
1803 const CVector2f *pHighestRight, *pHighestRightNext, *pHighestLeft;
1804 const CVector2f *pPrevHighestLeft;
1805 double deltaXN, deltaYN, deltaXP, deltaYP;
1806 bool ccw; // true if CCW oriented
1807 sint polyHeight;
1808 sint highest, lowest;
1809
1810 float fright = curr->x;
1811 float fleft = curr->x;
1812 float fhighest = curr->y;
1813 float flowest = curr->y;
1814 plowest = phighest = curr;
1815
1816 // compute highest (with lowest y) and lowest (with highest y) points of the poly
1817 do
1818 {
1819 fright = std::max(fright, curr->x);
1820 fleft = std::min(fleft, curr->x);
1821 if (curr->y > flowest)
1822 {
1823 flowest = curr->y;
1824 plowest = curr;
1825 }
1826 if (curr->y < fhighest)
1827 {
1828 fhighest = curr->y;
1829 phighest = curr;
1830 }
1831 ++curr;
1832 }
1833 while (curr != last);
1834 if (flowest == fhighest)
1835 {
1836 minimumY = -1;
1837 return;
1838 }
1839 highest = (sint) floorf(fhighest);
1840 lowest = (sint) ceilf(flowest);
1841
1842 polyHeight = lowest - highest;
1843 minimumY = highest;
1844 if (polyHeight == 0)
1845 {
1846 minimumY = -1;
1847 return;
1848 }
1849 // make room for rasters
1850 borders.resize(polyHeight);
1851 // fill with xmin / xman
1852 sint ileft = (sint) floorf(fleft) - 1;
1853 sint iright = (sint) ceilf(fright);
1854 for(TRasterVect::iterator it = borders.begin(); it != borders.end(); ++it)
1855 {
1856 it->second = iright;
1857 it->first = ileft;
1858 }
1859 pHighestRight = phighest;
1860 for (;;)
1861 {
1862 pHighestRightNext = pHighestRight + 1;
1863 if (pHighestRightNext == last) pHighestRightNext = first;
1864 if (pHighestRightNext->y != pHighestRight->y) break;
1865 pHighestRight = pHighestRightNext;
1866 }
1867
1868 pPrevHighestLeft = pHighestRight;
1869 pHighestLeft = pHighestRight;
1870 ++pHighestLeft;
1871 if (pHighestLeft == last) pHighestLeft = first;
1872
1873 while (pHighestLeft->y != fhighest)
1874 {
1875 pPrevHighestLeft = pHighestLeft;
1876 ++pHighestLeft;
1877 if (pHighestLeft == last) pHighestLeft = first;
1878 }
1879
1880
1881 // we need to get the orientation of the polygon
1882 // There are 2 case : flat, and non-flat top
1883
1884 // check for flat top
1885 if (pHighestLeft->x != pHighestRight->x)
1886 {
1887 // compare right and left side
1888 if (pHighestLeft->x > pHighestRight->x)
1889 {
1890 ccw = true; // the list is CCW oriented
1891 std::swap(pHighestLeft, pHighestRight);
1892 }
1893 else
1894 {
1895 ccw = false; // the list is CW oriented
1896 }
1897 }
1898 else
1899 {
1900 pHighestRightNext = pHighestRight + 1;
1901 if (pHighestRightNext == last) pHighestRightNext = first;
1902 deltaXN = pHighestRightNext->x - pHighestRight->x;
1903 deltaYN = pHighestRightNext->y - pHighestRight->y;
1904 deltaXP = pPrevHighestLeft->x - pHighestLeft->x;
1905 deltaYP = pPrevHighestLeft->y - pHighestLeft->y;
1906 if ((deltaXN * deltaYP - deltaYN * deltaXP) < 0)
1907 {
1908 ccw = true;
1909 std::swap(pHighestLeft, pHighestRight);
1910 }
1911 else
1912 {
1913 ccw = false;
1914 }
1915 }
1916
1917 if (!ccw)
1918 {
1919 // cw oriented
1920 curr = pHighestRight;
1921 do
1922 {
1923 next = curr + 1;
1924 if (next == last) next = first;
1925 ScanInnerEdge(&borders[0], curr->x, curr->y, next->x, next->y, minimumY, true);
1926 curr = next;
1927 }
1928 while (curr != plowest);
1929 do
1930 {
1931 next = curr + 1;
1932 if (next == last) next = first;
1933 ScanInnerEdge(&borders[0], next->x, next->y, curr->x, curr->y, minimumY, false);
1934 curr = next;
1935 }
1936 while (curr != pHighestLeft);
1937 }
1938 else
1939 {
1940 // ccw oriented
1941 curr = pHighestLeft;
1942 do
1943 {
1944 next = curr + 1;
1945 if (next == last) next = first;
1946 ScanInnerEdge(&borders[0], curr->x, curr->y, next->x, next->y, minimumY, false);
1947 curr = next;
1948 }
1949 while (curr != plowest);
1950 do
1951 {
1952 next = curr + 1;
1953 if (next == last) next = first;
1954 ScanInnerEdge(&borders[0], next->x, next->y, curr->x, curr->y, minimumY, true);
1955 curr = next;
1956 }
1957 while (curr != pHighestRight);
1958 }
1959 // fix for top
1960 if (floorf(fhighest) != fhighest)
1961 {
1962 borders[0].first = 1;
1963 borders[0].second = 0;
1964 }
1965 // fix for bottom
1966 if (floorf(flowest) != flowest)
1967 {
1968 borders.back().first = 1;
1969 borders.back().second = 0;
1970 }
1971 }
1972
1973 // *******************************************************************************
1974 void CPolygon2D::checkValidBorders() const
1975 {
1976 for (uint k = 0; k < Vertices.size(); ++k)
1977 {
1978 nlassert(Vertices[k].x >= -32000.f); // coordinate too big !
1979 nlassert(Vertices[k].x < 32000.f); // coordinate too big !
1980 nlassert(Vertices[k].y >= -32000.f); // coordinate too big !
1981 nlassert(Vertices[k].y < 32000.f); // coordinate too big !
1982 }
1983 }
1984
1985 // *******************************************************************************
1986 /// Sum the dot product of this poly vertices against a plane
1987 float CPolygon2D::sumDPAgainstLine(float a, float b, float c) const
1988 {
1989 float sum = 0.f;
1990 for (uint k = 0; k < Vertices.size(); ++k)
1991 {
1992 const CVector2f &p = Vertices[k];
1993 sum += a * p.x + b * p.y + c;
1994 }
1995 return sum;
1996 }
1997
1998
1999 // *******************************************************************************
2000 bool CPolygon2D::getNonNullSeg(uint &index) const
2001 {
2002 nlassert(!Vertices.empty());
2003 float bestLength = 0.f;
2004 sint bestIndex = -1;
2005 for (uint k = 0; k < Vertices.size() - 1; ++k)
2006 {
2007 float norm2 = (Vertices[k + 1] - Vertices[k]).sqrnorm();
2008 if ( norm2 > bestLength)
2009 {
2010 bestLength = norm2;
2011 bestIndex = (int) k;
2012 }
2013 }
2014 float norm2 = (Vertices[Vertices.size() - 1] - Vertices[0]).sqrnorm();
2015 if ( norm2 > bestLength)
2016 {
2017 index = (uint)Vertices.size() - 1;
2018 return true;
2019 }
2020
2021 if (bestIndex != -1)
2022 {
2023 index = bestIndex;
2024 return true;
2025 }
2026 else
2027 {
2028 return false;
2029 }
2030 }
2031
2032
2033 // *******************************************************************************
2034 void CPolygon2D::getLineEquation(uint index, float &a, float &b, float &c) const
2035 {
2036 nlassert(index < Vertices.size());
2037 const CVector2f &v0 = getSegRef0(index);
2038 const CVector2f &v1 = getSegRef1(index);
2039
2040 NLMISC::CVector2f seg = v0 - v1;
2041 a = seg.y;
2042 b = - seg.x;
2043 c = - v0.x * a - v0.y * b;
2044 }
2045
2046 // *******************************************************************************
2047 bool CPolygon2D::intersect(const CPolygon2D &other) const
2048 {
2049 nlassert(!other.Vertices.empty());
2050 uint nonNullSegIndex;
2051 /// get the orientation of this poly
2052 if (getNonNullSeg(nonNullSegIndex))
2053 {
2054 float a0, b0, c0; /// contains the seg 2d equation
2055 getLineEquation(nonNullSegIndex, a0, b0, c0);
2056 float orient = sumDPAgainstLine(a0, b0, c0);
2057
2058 for (uint k = 0; k < Vertices.size(); ++k)
2059 {
2060 /// don't check against a null segment
2061 if ( (getSegRef0(k) - getSegRef1(k)).sqrnorm() == 0.f) continue;
2062
2063 /// get the line equation of the current segment
2064 float a, b, c; /// contains the seg 2d equation
2065 getLineEquation(k, a, b, c);
2066 uint l;
2067 for (l = 0; l < other.Vertices.size(); ++l)
2068 {
2069 const CVector2f &ov = other.Vertices[l];
2070 if ( orient * (ov.x * a + ov.y * b +c) > 0.f) break;
2071 }
2072 if (l == other.Vertices.size()) // all point on the outside
2073 {
2074 return false; // outside
2075 }
2076 }
2077 return true;
2078 }
2079 else // this poly is just a point
2080 {
2081 return other.contains(Vertices[0]);
2082 }
2083 }
2084
2085 // *******************************************************************************
2086 bool CPolygon2D::contains(const CVector2f &p, bool hintIsConvex /*= true*/) const
2087 {
2088 if (hintIsConvex)
2089 {
2090 uint numVerts = (uint)Vertices.size();
2091 nlassert(numVerts >= 0.f);
2092 for (uint k = 0; k < numVerts; ++k)
2093 {
2094 if (getSegRef0(k) != getSegRef1(k))
2095 {
2096 float a, b, c; /// contains the seg 2d equation
2097 getLineEquation(k, a, b, c);
2098 float orient = a * p.x + b * p.y + c;
2099 for(uint l = k + 1; l < numVerts; ++l)
2100 {
2101 getLineEquation(l, a, b, c);
2102 float newOrient = a * p.x + b * p.y + c;
2103 if (newOrient * orient < 0.f) return false;
2104 }
2105 return true;
2106 }
2107 }
2108 // the poly reduces to a point
2109 return p == Vertices[0];
2110 }
2111 else
2112 {
2113 // concave case
2114 static std::vector<float> xInter;
2115 xInter.clear();
2116 for(uint k = 0; k < Vertices.size(); ++k)
2117 {
2118 const CVector2f &p0 = getSegRef0(k);
2119 const CVector2f &p1 = getSegRef1(k);
2120 if (p0.y == p1.y)
2121 {
2122 if (p.y == p0.y)
2123 {
2124 if ((p.x >= p0.x && p.x <= p1.x)
2125 || (p.x >= p1.x && p.x <= p0.x))
2126 {
2127 return true;
2128 }
2129 }
2130 }
2131 if ((p.y >= p0.y && p.y < p1.y) ||
2132 (p.y >= p1.y && p.y < p0.y)
2133 )
2134 {
2135
2136 float inter = p0.x + (p.y - p0.y) * (p1.x - p0.x) / (p1.y- p0.y);
2137 xInter.push_back(inter);
2138 }
2139 }
2140 if (xInter.size() < 2) return false;
2141 std::sort(xInter.begin(), xInter.end());
2142 for(uint k = 0; k < xInter.size() - 1; ++k)
2143 {
2144 if (p.x >= xInter[k] && p.x <= xInter[k + 1])
2145 {
2146 return (k & 1) == 0;
2147 }
2148 }
2149 return false;
2150 }
2151 }
2152
2153
2154 // *******************************************************************************
2155 CPolygon2D::CPolygon2D(const CTriangle &tri, const CMatrix &projMat)
2156 {
2157 Vertices.resize(3);
2158 NLMISC::CVector proj[3] = { projMat * tri.V0, projMat * tri.V1, projMat * tri.V2 };
2159 Vertices[0].set(proj[0].x, proj[0].y);
2160 Vertices[1].set(proj[1].x, proj[1].y);
2161 Vertices[2].set(proj[2].x, proj[2].y);
2162 }
2163
2164 // *******************************************************************************
2165 void CPolygon2D::getBoundingRect(CVector2f &minCorner, CVector2f &maxCorner) const
2166 {
2167 nlassert(!Vertices.empty());
2168 minCorner = maxCorner = Vertices[0];
2169 uint numVertices = (uint)Vertices.size();
2170 for(uint k = 0; k < numVertices; ++k)
2171 {
2172 minCorner.minof(minCorner, Vertices[k]);
2173 maxCorner.maxof(minCorner, Vertices[k]);
2174 }
2175 }
2176
2177 // *******************************************************************************
2178 bool operator ==(const CPolygon2D &lhs,const CPolygon2D &rhs)
2179 {
2180 if (lhs.Vertices.size() != rhs.Vertices.size()) return false;
2181 return std::equal(lhs.Vertices.begin(), lhs.Vertices.end(), rhs.Vertices.begin());
2182 }
2183
2184 // *******************************************************************************
2185 bool operator < (const CPolygon2D &lhs, const CPolygon2D &rhs)
2186 {
2187 if (lhs.Vertices.size() != rhs.Vertices.size()) return lhs.Vertices.size() < rhs.Vertices.size();
2188 for(uint k = 0; k < lhs.Vertices.size(); ++k)
2189 {
2190 if (lhs.Vertices[k] != rhs.Vertices[k]) return lhs.Vertices[k] < rhs.Vertices[k];
2191 }
2192 return false;
2193 }
2194
2195
2196 // *******************************************************************************
2197 static inline bool testSegmentIntersection(const CVector2f &a, const CVector2f &b,
2198 const CVector2f &c, const CVector2f &d)
2199 {
2200 double denom = a.x * double(d.y - c.y) +
2201 b.x * double(c.y - d.y) +
2202 d.x * double(b.y - a.y) +
2203 c.x * double(a.y - b.y);
2204
2205 if (denom == 0) return false;
2206 //
2207 double num = a.x * double(d.y - c.y) +
2208 c.x * double(a.y - d.y) +
2209 d.x * double(c.y - a.y);
2210
2211 if (num == 0 || (num == denom)) return false;
2212 double lambda = num / denom;
2213 if (lambda <= 0 || lambda >= 1) return false;
2214 //
2215 num = - (a.x * double(c.y - b.y) +
2216 b.x * double(a.y - c.y) +
2217 c.x * double(b.y - a.y));
2218
2219 if (num == 0 || (num == denom)) return false;
2220 lambda = num / denom;
2221 if (lambda <= 0 || lambda >= 1) return false;
2222 return true;
2223 }
2224
2225
2226 // *******************************************************************************
2227 bool CPolygon2D::selfIntersect() const
2228 {
2229 if (Vertices.size() < 3) return false;
2230 uint numEdges = (uint)Vertices.size();
2231 for(uint k = 0; k < numEdges; ++k)
2232 {
2233 // test intersection with all other edges that don't share a vertex with this one
2234 const CVector2f &p0 = getSegRef0(k);
2235 const CVector2f &p1 = getSegRef1(k);
2236 for(uint l = 0; l < k; ++l)
2237 {
2238 const CVector2f &v0 = getSegRef0(l);
2239 const CVector2f &v1 = getSegRef1(l);
2240 if (v0 == p0 || v0 == p1 || v1 == p0 || v1 == p1) continue;
2241 //
2242 if (testSegmentIntersection(p0, p1, v0, v1)) return true;
2243 }
2244 }
2245 return false;
2246 }
2247
2248
2249
2250 } // NLMISC
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271