source: trunk/VUT/GtpVisibilityPreprocessor/src/Polygon3.cpp @ 544

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