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

Revision 2183, 12.6 KB checked in by mattausch, 18 years ago (diff)
RevLine 
[235]1#include "Polygon3.h"
2#include "Mesh.h"
[372]3#include "AxisAlignedBox3.h"
4#include "Ray.h"
[503]5#include "Triangle3.h"
[372]6
[860]7
[863]8namespace GtpVisibilityPreprocessor {
[860]9
10
[372]11Polygon3::Polygon3():
[1344]12mMaterial(NULL),
13mParent(NULL),
14mPiercingRays(0)
[1076]15, mPlane(NULL)
[574]16{
17}
[372]18
[2116]19
[372]20Polygon3::Polygon3(const VertexContainer &vertices):
[1344]21mMaterial(NULL),
22mParent(NULL),
23mPiercingRays(0)
[1076]24, mPlane(NULL)
[574]25{
26        mVertices.reserve(vertices.size());
27        mVertices = vertices;
28}
[372]29
[574]30
[372]31Polygon3::Polygon3(MeshInstance *parent):
[1344]32mMaterial(NULL),
33mParent(parent),
34mPiercingRays(0)
[1076]35, mPlane(NULL)
[372]36{}
37
[574]38
[372]39Polygon3::Polygon3(Face *face, Mesh *parentMesh):
[1344]40mMaterial(NULL),
41mParent(NULL),
42mPiercingRays(0),
43mPlane(NULL)
[372]44{       
[574]45        mVertices.reserve(face->mVertexIndices.size());
[1344]46        VertexIndexContainer::iterator it, it_end = face->mVertexIndices.end();
47
[1420]48        for (it = face->mVertexIndices.begin(); it != it_end; ++ it)
[372]49        {
50                mVertices.push_back(parentMesh->mVertices[*it]);
51        }
[574]52
53        mMaterial = parentMesh->mMaterial;
[372]54}
55
[574]56
[1404]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
[2116]71Polygon3::~Polygon3()
72{
73        DEL_PTR(mPlane);
74}
75
[1076]76Plane3 Polygon3::GetSupportingPlane()// const
[372]77{
[1076]78#if 0
[372]79        return Plane3(mVertices[0], mVertices[1], mVertices[2]);
[1076]80#else
81        if (!mPlane)
[1344]82        {
[1076]83                mPlane = new Plane3(mVertices[0], mVertices[1], mVertices[2]);
[1344]84        }
85
[1076]86        return *mPlane;
87#endif
[372]88}
89
[574]90
[306]91Vector3 Polygon3::GetNormal() const
92{
[321]93    return Normalize(CrossProd(mVertices[2] - mVertices[1],
94                                                           mVertices[0] - mVertices[1]));
[372]95}
96
[1344]97
[372]98void Polygon3::Split(const Plane3 &partition,
99                                         Polygon3 &front,
[448]100                                         Polygon3 &back,
101                                         const float epsilon)
[372]102{
103        Vector3 ptA = mVertices.back();
[448]104        int sideA = partition.Side(ptA, epsilon);
[372]105        bool foundSplit = false;
[1344]106    Vector3 lastSplit;
107               
[2053]108        /////////////
[1344]109        //-- find line - plane intersections
[448]110
[1344]111        VertexContainer::const_iterator it, it_end = mVertices.end();
112
113        for (it = mVertices.begin(); it != it_end; ++ it)
[372]114        {
115                Vector3 ptB = *it;
[448]116                int sideB = partition.Side(ptB, epsilon);
[372]117       
118                // vertices on different sides => split
[237]119            if (sideB > 0)
120                {
121                        if (sideA < 0)
[372]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
[448]127                                if (!foundSplit || (!EpsilonEqualV3(splitPt, lastSplit, epsilon)))
[372]128                                {
129                                        // add vertex to both polygons
130                                        front.mVertices.push_back(splitPt);
131                                        back.mVertices.push_back(splitPt);
132                                       
[436]133                                        lastSplit = splitPt;
[372]134                                        foundSplit = true;
135                                }
136                        }
137                        front.mVertices.push_back(ptB);
138                }
[237]139                else if (sideB < 0)
140                {
141                        if (sideA > 0)
[372]142                        {
[2053]143                                ////////////
[372]144                                //-- plane - line intersection
[2053]145
[372]146                                Vector3 splitPt = partition.FindIntersection(ptA, ptB);
[2053]147                               
148                                // test if split point not too close to previous split point
[448]149                                if (!foundSplit || (!EpsilonEqualV3(splitPt, lastSplit, epsilon)))
[372]150                                {
151                                        // add vertex to both polygons
152                                        front.mVertices.push_back(splitPt);
153                                        back.mVertices.push_back(splitPt);
154
[436]155                                        lastSplit = splitPt;
[372]156                                        foundSplit = true;
157                                }       
158                        }
[2053]159
[372]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
[574]174
[372]175float Polygon3::GetArea() const
176{
[306]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   
[544]182    return 0.5f * fabs(DotProd(GetNormal(), v));
[372]183}
[235]184
[574]185
[448]186int Polygon3::Side(const Plane3 &plane,
187                                   const float epsilon) const
[372]188{
[448]189        int classification = ClassifyPlane(plane, epsilon);
[372]190       
191        if (classification == BACK_SIDE)
192                return -1;
193        else if (classification == FRONT_SIDE)
194                return 1;
[538]195        // plane splits polygon
[372]196        return 0;
197}
198
[574]199
[448]200int Polygon3::ClassifyPlane(const Plane3 &plane,
201                                                        const float epsilon) const
[372]202{
[574]203        VertexContainer::const_iterator it, it_end = mVertices.end();
[372]204
205        bool onFrontSide = false;
206        bool onBackSide = false;
207       
208        int count = 0;
209        // find possible line-plane intersections
[574]210        for (it = mVertices.begin(); it != it_end; ++ it)
[372]211        {
[448]212                const int side = plane.Side(*it, epsilon);
[372]213               
214                if (side > 0)
[683]215                {
[372]216                        onFrontSide = true;
[683]217                }
[372]218                else if (side < 0)
[683]219                {
[372]220                        onBackSide = true;
[683]221                }
222
[372]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       
[2053]256        return sum / (float)i;
[372]257}
258
259
260void
261Polygon3::Scale(const float scale)
262{
263        int i;
264        Vector3 center = Center();
[2053]265       
266        for (i=0; i < mVertices.size(); i++)
267        {
268                mVertices[i] = center + scale * (mVertices[i] - center);
[372]269        }
270}
271
[1420]272
[448]273bool Polygon3::Valid(const float epsilon) const
[372]274{
[1571]275        if ((int)mVertices.size() < 3)
[372]276                return false;
277
[1420]278        // matt: removed for performance issues
279#if _DEBUG
280        if (0)
[372]281        {
[574]282                // check if area exceeds certain size
283                if (GetArea() < AREA_LIMIT)
284                {
[2183]285                        Debug << "area too small: " << GetArea() << std::endl;
[574]286                        return false;
287                }
[372]288        }
[645]289       
290        if (1)
[574]291        {
292                Vector3 vtx = mVertices.back();
293                VertexContainer::const_iterator it, it_end = mVertices.end();
[372]294
[574]295                for (it = mVertices.begin(); it != it_end; ++it)
[372]296                {
[1420]297                        if (EpsilonEqualV3(vtx, *it, epsilon))
[574]298                        {
[1420]299                                //cout << "Malformed vertices:\n" << *this << endl;
[574]300                                return false;
301                        }
302                        vtx = *it;
[372]303                }
304        }
[574]305#endif
306
[372]307        return true;
308}
309
[574]310
[314]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
[574]350
[314]351int Polygon3::CastRay(const Ray &ray, float &t, const float nearestT)
352{
[1328]353        const Plane3 plane = GetSupportingPlane();
354        const float dot = DotProd(plane.mNormal, ray.GetDir());
[314]355
356        // Watch for near-zero denominator
357        // ONLY single sided polygons!!!!!
358        if (dot > -Limits::Small)
[1328]359        {
360                //  if (fabs(dot) < Limits::Small)
361                return Ray::NO_INTERSECTION;
362        }
[314]363
364        t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
365
366        if (t <= Limits::Small)
[1328]367        {
368                return Ray::INTERSECTION_OUT_OF_LIMITS;
369        }
[314]370
[1328]371        if (t >= nearestT)
372        {
373                return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
[314]374        }
375
376        int count = 0;
377        float u, v, u1, v1, u2, v2;
378        int i;
379
[1328]380        const int paxis = plane.mNormal.DrivingAxis();
[314]381
382        // Project the intersection point onto the coordinate plane
383        // specified by which.
384        ray.Extrap(t).ExtractVerts(&u, &v, paxis);
385
[1328]386        const int size = (int)mVertices.size();
[314]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);
[1328]396           
[314]397                        // line u1, v1, u2, v2
[1328]398                        if ((v2 - v1) * (u1 - u) > (u2 - u1)*(v1 - v))
[314]399                                return Ray::NO_INTERSECTION;
400
401                        u1 = u2;
402                        v1 = v2;
[1328]403                }
404               
405                return Ray::INTERSECTION;
[314]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
[574]426
[372]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
[574]458
[448]459int Polygon3::ClassifyPlane(const PolygonContainer &polys,
460                                                        const Plane3 &plane,
461                                                        const float epsilon)
[372]462{
[683]463        bool onFrontSide = false;
464        bool onBackSide = false;
[372]465        PolygonContainer::const_iterator it;
466
467        // find intersections
468        for (it = polys.begin(); it != polys.end(); ++ it)
469        {
[448]470        const int cf = (*it)->ClassifyPlane(plane, epsilon);
[372]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
[574]495
[375]496int Polygon3::ParentObjectsSize(const PolygonContainer &polys)
[372]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;
[384]513}
514
[574]515
[384]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)
[448]522        {
[384]523                area += (*pit)->GetArea();
[448]524        }
[396]525
[384]526        return area;
[396]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)
[448]538                revPoly->mVertices.push_back(*rit);
539
540        return revPoly;
[503]541}
542
543
[840]544void Polygon3::Triangulate(vector<Triangle3> &triangles) const
[503]545{
546        int i = 1;
547        int j = 0;
[508]548        int k = (int)mVertices.size() - 1;
[503]549        int count = 0;
550
551        while (i < k)
552        {
[1418]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]));
[503]557
558                if ((count ++) % 2)
559                        j = i ++;
560                else
561                        j = k --;
562        }
563}
[508]564
565
[840]566void Polygon3::Triangulate(VertexIndexContainer &indices) const
[508]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)
[1328]581                {
[508]582                        j = i ++;
[1328]583                }
[508]584                else
[1328]585                {
[508]586                        j = k --;
[1328]587                }
[508]588        }
589}
590
591
[840]592void IncludePolyInMesh(const Polygon3 &poly, Mesh &mesh)
[508]593{
594        const int n = (int)mesh.mVertices.size();
595
[1420]596
[1419]597        /////////////
598    //-- add the vertices to the mesh
599
[840]600    VertexContainer::const_iterator vit, vit_end = poly.mVertices.end();
601        for (vit = poly.mVertices.begin(); vit != vit_end; ++ vit)
[508]602        {
603                mesh.mVertices.push_back(*vit);
604        }
605
606        // one quad => no triangulation necessary
[840]607        if (poly.mVertices.size() == 4)
[508]608        {
609                mesh.AddFace(new Face(n, n + 1, n + 2, n + 3));
[840]610                return;
[508]611        }
[840]612       
613        VertexIndexContainer indices;
614        poly.Triangulate(indices);
[508]615
[1420]616        //if (indices.size() < 3) return; // something is wrong
617       
[840]618        // add indices of triangle strip
[1420]619        for (int i = 0; i < (int)indices.size(); i += 3)
[840]620        {
[1420]621                Face *face = new Face(indices[i] + n,
622                                                          indices[i + 1] + n,
623                                                          indices[i + 2] + n);
[840]624                mesh.AddFace(face);
[508]625        }
[860]626}
627
[1328]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
[508]645}
Note: See TracBrowser for help on using the repository browser.