1 #include <math.h>
2 #include "lwPolygon.h"
3 #include "BitArray.h"
4
5 const float epsilon = 0.001F; // error margin
6
flip(void)7 void lwPolygon::flip(void)
8 {
9 vvertices flipvertices;
10 flipvertices.reserve(vertices.size());
11 vvertices::reverse_iterator i = vertices.rbegin();
12 vvertices::reverse_iterator end = vertices.rend();
13 for(; i!=end ; ++i)
14 flipvertices.push_back(*i);
15 vertices = flipvertices;
16 }
17
makeTriangle(long ia,long ib,long ic)18 lwPolygon *lwPolygon::makeTriangle(long ia, long ib, long ic)
19 {
20 lwPolygon *triangle = new lwPolygon(*this);
21
22 triangle->vertices.push_back(new lwVertex(*vertices[ia]));
23 triangle->vertices.push_back(new lwVertex(*vertices[ib]));
24 triangle->vertices.push_back(new lwVertex(*vertices[ic]));
25
26 return triangle;
27 }
28
calculateNormal()29 Vector3 &lwPolygon::calculateNormal()
30 {
31 if ( vertices.size() < 3 ) return normal;
32
33 Point3 *p1 = vertices[ 0 ]->point;
34 Point3 *p2 = vertices[ 1 ]->point;
35 Point3 *pn = vertices[vertices.size() - 1]->point;
36
37 normal = (*p2 - *p1).crossProduct(*pn - *p1);
38 normal.normalise();
39
40 return normal;
41 }
42
triangulate()43 vpolygons lwPolygon::triangulate()
44 {
45 vpolygons triangles;
46
47 BitArray active(vertices.size(), true); // vertex part of polygon ?
48
49 long vertexCount = vertices.size();
50
51 long triangleCount = 0;
52 long start = 0;
53
54 long p1 = 0;
55 long p2 = 1;
56 long m1 = vertexCount - 1;
57 long m2 = vertexCount - 2;
58
59 bool lastPositive = false;
60 for (;;)
61 {
62 if (p2 == m2)
63 {
64 triangles.push_back(makeTriangle(m1, p1, p2));
65 break;
66 }
67
68 const Point3 vp1 = *vertices[p1]->point;
69 const Point3 vp2 = *vertices[p2]->point;
70 const Point3 vm1 = *vertices[m1]->point;
71 const Point3 vm2 = *vertices[m2]->point;
72
73 bool positive = false;
74 bool negative = false;
75
76 Vector3 n1 = normal.crossProduct((vm1 - vp2).normalise());
77 if (n1.dotProduct(vp1 - vp2) > epsilon)
78 {
79 positive = true;
80
81 Vector3 n2 = normal.crossProduct((vp1 - vm1).normalise());
82 Vector3 n3 = normal.crossProduct((vp2 - vp1).normalise());
83
84 for (long a = 0; a < vertexCount; a++)
85 {
86 if ((a != p1) && (a != p2) && (a != m1) && active.bitSet(a))
87 {
88 const Point3 v = *vertices[a]->point;
89 if (n1.dotProduct((v - vp2).normalise()) > -epsilon && n2.dotProduct((v - vm1).normalise()) > -epsilon && n3.dotProduct((v - vp1).normalise()) > -epsilon)
90 {
91 positive = false;
92 break;
93 }
94 }
95 }
96 }
97
98 n1 = normal.crossProduct((vm2 - vp1).normalise());
99 if (n1.dotProduct(vm1 - vp1) > epsilon)
100 {
101 negative = true;
102
103 Vector3 n2 = normal.crossProduct((vm1 - vm2).normalise());
104 Vector3 n3 = normal.crossProduct((vp1 - vm1).normalise());
105
106 for (long a = 0; a < vertexCount; a++)
107 {
108 if ((a != m1) && (a != m2) && (a != p1) && active.bitSet(a))
109 {
110 const Point3 v = *vertices[a]->point;
111 if (n1.dotProduct((v - vp1).normalise()) > -epsilon && n2.dotProduct((v - vm2).normalise()) > -epsilon && n3.dotProduct((v - vm1).normalise()) > -epsilon)
112 {
113 negative = false;
114 break;
115 }
116 }
117 }
118 }
119
120 if ((positive) && (negative))
121 {
122 float pd = (vp2 - vm1).normalise().dotProduct((vm2 - vm1).normalise());
123 float md = (vm2 - vp1).normalise().dotProduct((vp2 - vp1).normalise());
124
125 if (fabs(pd - md) < epsilon)
126 {
127 if (lastPositive) positive = false;
128 else negative = false;
129 }
130 else
131 {
132 if (pd < md) negative = false;
133 else positive = false;
134 }
135 }
136
137 if (positive)
138 {
139 active.clearBit(p1);
140 triangles.push_back(makeTriangle(m1, p1, p2));
141
142 p1 = active.getNextSet(p1);
143 p2 = active.getNextSet(p2);
144
145 lastPositive = true;
146 start = -1;
147 }
148 else if (negative)
149 {
150 active.clearBit(m1);
151 triangles.push_back(makeTriangle(m2, m1, p1));
152
153 m1 = active.getPreviousSet(m1);
154 m2 = active.getPreviousSet(m2);
155
156 lastPositive = false;
157 start = -1;
158 }
159 else
160 {
161 if (start == -1) start = p2;
162 else if (p2 == start) break;
163
164 m2 = m1;
165 m1 = p1;
166 p1 = p2;
167 p2 = active.getNextSet(p2);
168 }
169 }
170
171 return triangles;
172 }
173