source: GTP/trunk/Lib/Vis/Preprocessing/src/Polygon3.cpp @ 2183

Revision 2183, 12.6 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include "Polygon3.h"
2#include "Mesh.h"
3#include "AxisAlignedBox3.h"
4#include "Ray.h"
5#include "Triangle3.h"
6
7
8namespace GtpVisibilityPreprocessor {
9
10
11Polygon3::Polygon3():
12mMaterial(NULL),
13mParent(NULL),
14mPiercingRays(0)
15, mPlane(NULL)
16{
17}
18
19
20Polygon3::Polygon3(const VertexContainer &vertices):
21mMaterial(NULL),
22mParent(NULL),
23mPiercingRays(0)
24, mPlane(NULL)
25{
26        mVertices.reserve(vertices.size());
27        mVertices = vertices;
28}
29
30
31Polygon3::Polygon3(MeshInstance *parent):
32mMaterial(NULL),
33mParent(parent),
34mPiercingRays(0)
35, mPlane(NULL)
36{}
37
38
39Polygon3::Polygon3(Face *face, Mesh *parentMesh):
40mMaterial(NULL),
41mParent(NULL),
42mPiercingRays(0),
43mPlane(NULL)
44{       
45        mVertices.reserve(face->mVertexIndices.size());
46        VertexIndexContainer::iterator it, it_end = face->mVertexIndices.end();
47
48        for (it = face->mVertexIndices.begin(); it != it_end; ++ it)
49        {
50                mVertices.push_back(parentMesh->mVertices[*it]);
51        }
52
53        mMaterial = parentMesh->mMaterial;
54}
55
56
57Polygon3::Polygon3(const Triangle3 &tri):
58mMaterial(NULL),
59mParent(NULL),
60mPiercingRays(0),
61mPlane(NULL)
62{       
63        mVertices.reserve(3);
64       
65        mVertices.push_back(tri.mVertices[0]);
66        mVertices.push_back(tri.mVertices[1]);
67        mVertices.push_back(tri.mVertices[2]);
68}
69
70
71Polygon3::~Polygon3()
72{
73        DEL_PTR(mPlane);
74}
75
76Plane3 Polygon3::GetSupportingPlane()// const
77{
78#if 0
79        return Plane3(mVertices[0], mVertices[1], mVertices[2]);
80#else
81        if (!mPlane)
82        {
83                mPlane = new Plane3(mVertices[0], mVertices[1], mVertices[2]);
84        }
85
86        return *mPlane;
87#endif
88}
89
90
91Vector3 Polygon3::GetNormal() const
92{
93    return Normalize(CrossProd(mVertices[2] - mVertices[1],
94                                                           mVertices[0] - mVertices[1]));
95}
96
97
98void Polygon3::Split(const Plane3 &partition,
99                                         Polygon3 &front,
100                                         Polygon3 &back,
101                                         const float epsilon)
102{
103        Vector3 ptA = mVertices.back();
104        int sideA = partition.Side(ptA, epsilon);
105        bool foundSplit = false;
106    Vector3 lastSplit;
107               
108        /////////////
109        //-- find line - plane intersections
110
111        VertexContainer::const_iterator it, it_end = mVertices.end();
112
113        for (it = mVertices.begin(); it != it_end; ++ it)
114        {
115                Vector3 ptB = *it;
116                int sideB = partition.Side(ptB, epsilon);
117       
118                // vertices on different sides => split
119            if (sideB > 0)
120                {
121                        if (sideA < 0)
122                        {
123                                //-- plane - line intersection
124                                Vector3 splitPt = partition.FindIntersection(ptA, ptB);
125                       
126                                // test if split point not too close to previous split point
127                                if (!foundSplit || (!EpsilonEqualV3(splitPt, lastSplit, epsilon)))
128                                {
129                                        // add vertex to both polygons
130                                        front.mVertices.push_back(splitPt);
131                                        back.mVertices.push_back(splitPt);
132                                       
133                                        lastSplit = splitPt;
134                                        foundSplit = true;
135                                }
136                        }
137                        front.mVertices.push_back(ptB);
138                }
139                else if (sideB < 0)
140                {
141                        if (sideA > 0)
142                        {
143                                ////////////
144                                //-- plane - line intersection
145
146                                Vector3 splitPt = partition.FindIntersection(ptA, ptB);
147                               
148                                // test if split point not too close to previous split point
149                                if (!foundSplit || (!EpsilonEqualV3(splitPt, lastSplit, epsilon)))
150                                {
151                                        // add vertex to both polygons
152                                        front.mVertices.push_back(splitPt);
153                                        back.mVertices.push_back(splitPt);
154
155                                        lastSplit = splitPt;
156                                        foundSplit = true;
157                                }       
158                        }
159
160                        back.mVertices.push_back(ptB);
161                }
162                else
163                {
164                        // vertex on plane => add vertex to both polygons
165                        front.mVertices.push_back(ptB);
166                        back.mVertices.push_back(ptB);
167                }
168       
169                ptA = ptB;
170                sideA = sideB;
171        }
172}
173
174
175float Polygon3::GetArea() const
176{
177        Vector3 v = CrossProd(mVertices.back(), mVertices.front());
178   
179    for (int i=0; i < mVertices.size() - 1; ++i)
180                v += CrossProd(mVertices[i], mVertices[i+1]);
181   
182    return 0.5f * fabs(DotProd(GetNormal(), v));
183}
184
185
186int Polygon3::Side(const Plane3 &plane,
187                                   const float epsilon) const
188{
189        int classification = ClassifyPlane(plane, epsilon);
190       
191        if (classification == BACK_SIDE)
192                return -1;
193        else if (classification == FRONT_SIDE)
194                return 1;
195        // plane splits polygon
196        return 0;
197}
198
199
200int Polygon3::ClassifyPlane(const Plane3 &plane,
201                                                        const float epsilon) const
202{
203        VertexContainer::const_iterator it, it_end = mVertices.end();
204
205        bool onFrontSide = false;
206        bool onBackSide = false;
207       
208        int count = 0;
209        // find possible line-plane intersections
210        for (it = mVertices.begin(); it != it_end; ++ it)
211        {
212                const int side = plane.Side(*it, epsilon);
213               
214                if (side > 0)
215                {
216                        onFrontSide = true;
217                }
218                else if (side < 0)
219                {
220                        onBackSide = true;
221                }
222
223                //TODO: check if split goes through vertex
224                if (onFrontSide && onBackSide) // split
225                {
226                        return SPLIT;
227                }
228                // 3 vertices enough to decide coincident
229                else if (((++ count) >= 3) && !onFrontSide && !onBackSide)
230                {   
231                        return COINCIDENT;
232                }
233        }
234
235        if (onBackSide)
236        {
237                return BACK_SIDE;
238        }
239        else if (onFrontSide)
240        {
241                return FRONT_SIDE;
242        }
243       
244        return COINCIDENT; // plane and polygon are coincident
245}
246
247
248Vector3
249Polygon3::Center() const
250{
251        int i;
252        Vector3 sum = mVertices[0];
253        for (i=1; i < mVertices.size(); i++)
254                sum += mVertices[i];
255       
256        return sum / (float)i;
257}
258
259
260void
261Polygon3::Scale(const float scale)
262{
263        int i;
264        Vector3 center = Center();
265       
266        for (i=0; i < mVertices.size(); i++)
267        {
268                mVertices[i] = center + scale * (mVertices[i] - center);
269        }
270}
271
272
273bool Polygon3::Valid(const float epsilon) const
274{
275        if ((int)mVertices.size() < 3)
276                return false;
277
278        // matt: removed for performance issues
279#if _DEBUG
280        if (0)
281        {
282                // check if area exceeds certain size
283                if (GetArea() < AREA_LIMIT)
284                {
285                        Debug << "area too small: " << GetArea() << std::endl;
286                        return false;
287                }
288        }
289       
290        if (1)
291        {
292                Vector3 vtx = mVertices.back();
293                VertexContainer::const_iterator it, it_end = mVertices.end();
294
295                for (it = mVertices.begin(); it != it_end; ++it)
296                {
297                        if (EpsilonEqualV3(vtx, *it, epsilon))
298                        {
299                                //cout << "Malformed vertices:\n" << *this << endl;
300                                return false;
301                        }
302                        vtx = *it;
303                }
304        }
305#endif
306
307        return true;
308}
309
310
311// int_lineseg returns 1 if the given line segment intersects a 2D
312// ray travelling in the positive X direction.  This is used in the
313// Jordan curve computation for polygon intersection.
314inline int
315int_lineseg(float px,
316            float py,
317            float u1,
318            float v1,
319            float u2,
320            float v2)
321{
322        float t;
323        float ydiff;
324
325        u1 -= px; u2 -= px;       // translate line
326        v1 -= py; v2 -= py;
327
328        if ((v1 > 0 && v2 > 0) ||
329                (v1 < 0 && v2 < 0) ||
330                (u1 < 0 && u2 < 0))
331        return 0;
332
333        if (u1 > 0 && u2 > 0)
334        return 1;
335
336        ydiff = v2 - v1;
337
338        if (fabs(ydiff) < Limits::Small)
339        {         // denominator near 0
340                if (((fabs(v1) > Limits::Small) || (u1 > 0) || (u2 > 0)))
341                        return 0;
342                return 1;
343        }
344
345        t = -v1 / ydiff;                  // Compute parameter
346
347        return (u1 + t * (u2 - u1)) > 0;
348}
349
350
351int Polygon3::CastRay(const Ray &ray, float &t, const float nearestT)
352{
353        const Plane3 plane = GetSupportingPlane();
354        const float dot = DotProd(plane.mNormal, ray.GetDir());
355
356        // Watch for near-zero denominator
357        // ONLY single sided polygons!!!!!
358        if (dot > -Limits::Small)
359        {
360                //  if (fabs(dot) < Limits::Small)
361                return Ray::NO_INTERSECTION;
362        }
363
364        t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
365
366        if (t <= Limits::Small)
367        {
368                return Ray::INTERSECTION_OUT_OF_LIMITS;
369        }
370
371        if (t >= nearestT)
372        {
373                return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
374        }
375
376        int count = 0;
377        float u, v, u1, v1, u2, v2;
378        int i;
379
380        const int paxis = plane.mNormal.DrivingAxis();
381
382        // Project the intersection point onto the coordinate plane
383        // specified by which.
384        ray.Extrap(t).ExtractVerts(&u, &v, paxis);
385
386        const int size = (int)mVertices.size();
387
388        mVertices.back().ExtractVerts(&u1, &v1, paxis );
389
390        if (0 && size <= 4)
391        {
392                // assume a convex face
393                for (i = 0; i < size; i++)
394                {
395                mVertices[i].ExtractVerts(&u2, &v2, paxis);
396           
397                        // line u1, v1, u2, v2
398                        if ((v2 - v1) * (u1 - u) > (u2 - u1)*(v1 - v))
399                                return Ray::NO_INTERSECTION;
400
401                        u1 = u2;
402                        v1 = v2;
403                }
404               
405                return Ray::INTERSECTION;
406        }
407
408        // We're stuck with the Jordan curve computation.  Count number
409        // of intersections between the line segments the polygon comprises
410        // with a ray originating at the point of intersection and
411        // travelling in the positive X direction.
412        for (i = 0; i < size; i++)
413        {
414                mVertices[i].ExtractVerts(&u2, &v2, paxis);
415
416                count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
417
418                u1 = u2;
419                v1 = v2;
420        }
421
422        // We hit polygon if number of intersections is odd.
423        return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
424}
425
426
427void Polygon3::InheritRays(Polygon3 &front_piece,
428                                               Polygon3 &back_piece) const
429{
430        if (mPiercingRays.empty())
431                return;
432
433        RayContainer::const_iterator it,
434                it_end = mPiercingRays.end();
435
436        for (it = mPiercingRays.begin(); it != it_end; ++ it)
437        {
438                switch((*it)->GetId())
439                {
440                case Ray::BACK:
441                        back_piece.mPiercingRays.push_back(*it);
442                        break;
443                case Ray::FRONT:
444                        front_piece.mPiercingRays.push_back(*it);
445                        break;
446                case Ray::FRONT_BACK:
447                        back_piece.mPiercingRays.push_back(*it);
448                        break;
449                case Ray::BACK_FRONT:
450                        front_piece.mPiercingRays.push_back(*it);
451                        break;
452                default:
453                        break;
454                }
455        }
456}
457
458
459int Polygon3::ClassifyPlane(const PolygonContainer &polys,
460                                                        const Plane3 &plane,
461                                                        const float epsilon)
462{
463        bool onFrontSide = false;
464        bool onBackSide = false;
465        PolygonContainer::const_iterator it;
466
467        // find intersections
468        for (it = polys.begin(); it != polys.end(); ++ it)
469        {
470        const int cf = (*it)->ClassifyPlane(plane, epsilon);
471               
472        if (cf == FRONT_SIDE)
473                        onFrontSide = true;
474                else if (cf == BACK_SIDE)
475                        onBackSide = true;
476               
477                if ((cf == SPLIT) || (cf == COINCIDENT) || (onFrontSide && onBackSide))
478                {
479                        return SPLIT;
480                }
481        }
482
483        if (onBackSide)
484        {
485                return BACK_SIDE;
486        }
487        else if (onFrontSide)
488        {
489                return FRONT_SIDE;
490        }
491       
492        return SPLIT;
493}
494
495
496int Polygon3::ParentObjectsSize(const PolygonContainer &polys)
497{
498        int count = 0;
499
500        PolygonContainer::const_iterator it, it_end = polys.end();
501
502        MeshInstance::NewMail();
503
504        for (it = polys.begin(); it != it_end; ++ it)
505        {
506                if ((*it)->mParent && !(*it)->mParent->Mailed())
507                {
508                        ++ count;
509                        (*it)->mParent->Mail();
510                }
511        }
512        return count;
513}
514
515
516float Polygon3::GetArea(const PolygonContainer &cell)
517{
518        float area = 0;
519        PolygonContainer::const_iterator pit;
520
521        for (pit = cell.begin(); pit != cell.end(); ++ pit)
522        {
523                area += (*pit)->GetArea();
524        }
525
526        return area;
527}
528
529
530Polygon3 *Polygon3::CreateReversePolygon() const
531{
532        Polygon3 *revPoly = new Polygon3();
533
534        VertexContainer::const_reverse_iterator rit,
535                        rit_end = mVertices.rend();
536
537        for(rit = mVertices.rbegin(); rit != rit_end; ++ rit)
538                revPoly->mVertices.push_back(*rit);
539
540        return revPoly;
541}
542
543
544void Polygon3::Triangulate(vector<Triangle3> &triangles) const
545{
546        int i = 1;
547        int j = 0;
548        int k = (int)mVertices.size() - 1;
549        int count = 0;
550
551        while (i < k)
552        {
553                if (0) // matt: I don't know why i made it like this because the normals are wrong!!
554                        triangles.push_back(Triangle3(mVertices[i], mVertices[j], mVertices[k]));
555                else
556                        triangles.push_back(Triangle3(mVertices[k], mVertices[j], mVertices[i]));
557
558                if ((count ++) % 2)
559                        j = i ++;
560                else
561                        j = k --;
562        }
563}
564
565
566void Polygon3::Triangulate(VertexIndexContainer &indices) const
567{
568        int i = 1;
569        int j = 0;
570        int k = (int)mVertices.size() - 1;
571
572        int count = 0;
573
574        while (i < k)
575        {
576                indices.push_back(k);
577                indices.push_back(j);
578                indices.push_back(i);
579
580                if ((count ++) % 2)
581                {
582                        j = i ++;
583                }
584                else
585                {
586                        j = k --;
587                }
588        }
589}
590
591
592void IncludePolyInMesh(const Polygon3 &poly, Mesh &mesh)
593{
594        const int n = (int)mesh.mVertices.size();
595
596
597        /////////////
598    //-- add the vertices to the mesh
599
600    VertexContainer::const_iterator vit, vit_end = poly.mVertices.end();
601        for (vit = poly.mVertices.begin(); vit != vit_end; ++ vit)
602        {
603                mesh.mVertices.push_back(*vit);
604        }
605
606        // one quad => no triangulation necessary
607        if (poly.mVertices.size() == 4)
608        {
609                mesh.AddFace(new Face(n, n + 1, n + 2, n + 3));
610                return;
611        }
612       
613        VertexIndexContainer indices;
614        poly.Triangulate(indices);
615
616        //if (indices.size() < 3) return; // something is wrong
617       
618        // add indices of triangle strip
619        for (int i = 0; i < (int)indices.size(); i += 3)
620        {
621                Face *face = new Face(indices[i] + n,
622                                                          indices[i + 1] + n,
623                                                          indices[i + 2] + n);
624                mesh.AddFace(face);
625        }
626}
627
628
629AxisAlignedBox3 Polygon3::GetBoundingBox() const
630{
631        VertexContainer::const_iterator vit, vit_end = mVertices.end();
632       
633        AxisAlignedBox3 box;
634        box.Initialize();
635
636        for (vit = mVertices.begin(); vit != vit_end; ++ vit)
637        {
638                box.Include(*vit);
639        }
640
641        return box;
642}
643
644
645}
Note: See TracBrowser for help on using the repository browser.