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

Revision 1076, 11.7 KB checked in by mattausch, 18 years ago (diff)

version for performance testing

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