| 86 | } |
| 87 | |
| 88 | void addTriangle(s32 i0, s32 i1, s32 i2) |
| 89 | { |
| 90 | Triangle* tri = nullptr; |
| 91 | s32 id = -1; |
| 92 | if (!s_freeList.empty()) |
| 93 | { |
| 94 | id = s_freeList.back(); |
| 95 | tri = &s_triangles[id]; |
| 96 | PolyAssert(tri->id == id); |
| 97 | s_freeList.pop_back(); |
| 98 | } |
| 99 | else |
| 100 | { |
| 101 | id = (s32)s_triangles.size(); |
| 102 | s_triangles.push_back({}); |
| 103 | tri = &s_triangles[id]; |
| 104 | tri->id = id; |
| 105 | } |
| 106 | |
| 107 | tri->allocated = true; |
| 108 | |
| 109 | tri->idx[0] = i0; |
| 110 | tri->idx[1] = i1; |
| 111 | tri->idx[2] = i2; |
| 112 | |
| 113 | tri->adj[0] = computeAdjacency(i0, i1, id); |
| 114 | tri->adj[1] = computeAdjacency(i1, i2, id); |
| 115 | tri->adj[2] = computeAdjacency(i2, i0, id); |
| 116 | |
| 117 | Vec2f v0 = s_vertices[i0]; |
| 118 | Vec2f v1 = s_vertices[i1]; |
| 119 | Vec2f v2 = s_vertices[i2]; |
| 120 | |
| 121 | // Compute the centroid. |
| 122 | tri->centroid.x = (v0.x + v1.x + v2.x) / 3.0f; |
| 123 | tri->centroid.z = (v0.z + v1.z + v2.z) / 3.0f; |
| 124 | |
| 125 | // Compute the circumcircle. |
| 126 | Vec2f a = { v1.x - v0.x, v1.z - v0.z }; |
| 127 | Vec2f b = { v2.x - v0.x, v2.z - v0.z }; |
| 128 | f32 m = v1.x*v1.x - v0.x*v0.x + v1.z*v1.z - v0.z*v0.z; |
| 129 | f32 u = v2.x*v2.x - v0.x*v0.x + v2.z*v2.z - v0.z*v0.z; |
| 130 | f32 s = 1.0f / (2.0f * (a.x*b.z - a.z*b.x)); |
| 131 | |
| 132 | tri->circle.x = ((v2.z - v0.z)*m + (v0.z - v1.z)*u) * s; |
| 133 | tri->circle.z = ((v0.x - v2.x)*m + (v1.x - v0.x)*u) * s; |
| 134 | |
| 135 | Vec2f offset = { v0.x - tri->circle.x, v0.z - tri->circle.z }; |
| 136 | tri->radiusSq = offset.x*offset.x + offset.z*offset.z; |
| 137 | |
| 138 | // Deal with small errors. |
| 139 | // TODO: Use an epsilon instead? |
| 140 | const Vec2f offset1 = { v1.x - tri->circle.x, v1.z - tri->circle.z }; |
| 141 | const Vec2f offset2 = { v2.x - tri->circle.x, v2.z - tri->circle.z }; |
| 142 | f32 r1 = offset1.x*offset1.x + offset1.z*offset1.z; |
| 143 | f32 r2 = offset2.x*offset2.x + offset2.z*offset2.z; |
| 144 | tri->radiusSq = std::max(tri->radiusSq, r1); |
| 145 | tri->radiusSq = std::max(tri->radiusSq, r2); |
no test coverage detected