19MinAreaTriangulation::triangulate (std::vector<math::Vec3f>
const& verts,
20 std::vector<unsigned int>* indices)
23 throw std::invalid_argument(
"Invalid polygon with <3 vertices");
25 if (verts.size() == 3)
27 indices->push_back(0);
28 indices->push_back(1);
29 indices->push_back(2);
33 this->min_area_table.clear();
34 this->mid_point_table.clear();
35 this->min_area_table.resize(verts.size() * verts.size(), -1.0f);
36 this->mid_point_table.resize(verts.size() * verts.size(), -1);
37 this->compute_table(verts, 0, 1);
39 this->compute_triangulation(indices, 0, 1, verts.size());
43MinAreaTriangulation::compute_table (std::vector<math::Vec3f>
const& verts,
44 int start_id,
int end_id)
46 if (start_id == end_id)
48 if (start_id == (end_id + 1) % (
int)verts.size())
51 int const index = start_id * verts.size() + end_id;
52 float& min_area = this->min_area_table[index];
55 for (
int mid_point = (end_id + 1) % (
int)verts.size();
56 mid_point != start_id;
57 mid_point = (mid_point + 1) % (
int)verts.size())
59 float temp = this->compute_table(verts, start_id, mid_point)
60 + this->compute_table(verts, mid_point, end_id)
62 verts[end_id], verts[mid_point]);
64 if (temp < min_area || min_area < 0.0f)
67 this->mid_point_table[index] = mid_point;
76MinAreaTriangulation::compute_triangulation (std::vector<unsigned int>* indices,
77 int start_id,
int end_id,
int num_verts)
79 int const index = start_id * num_verts + end_id;
80 int mid_point = this->mid_point_table[index];
83 indices->push_back(start_id);
84 indices->push_back(end_id);
85 indices->push_back(mid_point);
86 this->compute_triangulation(indices, start_id, mid_point, num_verts);
87 this->compute_triangulation(indices, mid_point, end_id, num_verts);
#define FSSR_NAMESPACE_END
#define FSSR_NAMESPACE_BEGIN
T triangle_area(math::Vector< T, 3 > const &a, math::Vector< T, 3 > const &b, math::Vector< T, 3 > const &c)
Calculates the area of the given triangle.