MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
triangulation.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015, Simon Fuhrmann
3 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
4 * All rights reserved.
5 *
6 * This software may be modified and distributed under the terms
7 * of the BSD 3-Clause license. See the LICENSE.txt file for details.
8 */
9
10#include <stdexcept>
11
12#include "math/geometry.h"
13#include "fssr/defines.h"
14#include "fssr/triangulation.h"
15
17
18void
19MinAreaTriangulation::triangulate (std::vector<math::Vec3f> const& verts,
20 std::vector<unsigned int>* indices)
21{
22 if (verts.size() < 3)
23 throw std::invalid_argument("Invalid polygon with <3 vertices");
24
25 if (verts.size() == 3)
26 {
27 indices->push_back(0);
28 indices->push_back(1);
29 indices->push_back(2);
30 return;
31 }
32
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);
38 indices->clear();
39 this->compute_triangulation(indices, 0, 1, verts.size());
40}
41
42float
43MinAreaTriangulation::compute_table (std::vector<math::Vec3f> const& verts,
44 int start_id, int end_id)
45{
46 if (start_id == end_id)
47 return 0.0f;
48 if (start_id == (end_id + 1) % (int)verts.size())
49 return 0.0f;
50
51 int const index = start_id * verts.size() + end_id;
52 float& min_area = this->min_area_table[index];
53 if (min_area < 0.0f)
54 {
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())
58 {
59 float temp = this->compute_table(verts, start_id, mid_point)
60 + this->compute_table(verts, mid_point, end_id)
61 + math::geom::triangle_area(verts[start_id],
62 verts[end_id], verts[mid_point]);
63
64 if (temp < min_area || min_area < 0.0f)
65 {
66 min_area = temp;
67 this->mid_point_table[index] = mid_point;
68 }
69 }
70 }
71
72 return min_area;
73}
74
75void
76MinAreaTriangulation::compute_triangulation (std::vector<unsigned int>* indices,
77 int start_id, int end_id, int num_verts)
78{
79 int const index = start_id * num_verts + end_id;
80 int mid_point = this->mid_point_table[index];
81 if (mid_point < 0)
82 return;
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);
88}
89
#define FSSR_NAMESPACE_END
Definition defines.h:14
#define FSSR_NAMESPACE_BEGIN
Definition defines.h:13
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.
Definition geometry.h:208