[6] | 1 | #include <math.h> |
---|
| 2 | #include "lwPolygon.h" |
---|
| 3 | #include "BitArray.h" |
---|
| 4 | |
---|
| 5 | const float epsilon = 0.001F; // error margin |
---|
| 6 | |
---|
| 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 | |
---|
| 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 | |
---|
| 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 | |
---|
| 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 | } |
---|