--- a/src/triangulate.cpp Sun Jul 03 13:44:11 2022 +0300
+++ b/src/triangulate.cpp Sun Jul 03 14:35:06 2022 +0300
@@ -13,36 +13,58 @@
static constexpr float get(const glm::vec3& t) { return t.y; }
};
-using indextype = std::uint16_t;
-using indexpair = std::pair<indextype, indextype>;
-struct boundaryinfo
+namespace triangulate
{
- indextype third;
- std::size_t triangleid;
-};
-using boundarymap_t = std::map<indexpair, boundaryinfo>;
-
-struct MergedTriangles
-{
- std::vector<Quadrilateral> quadrilaterals;
- std::set<std::size_t> cutTriangles;
-};
+ struct triangleid
+ {
+ std::size_t id;
+ constexpr auto operator<=>(const triangleid&) const = default;
+ };
+ //! \brief Index type of vertex
+ using index_t = std::uint16_t;
+ //! \brief Pair of vertex indices, forming a triangle boundary
+ using boundary_t = std::pair<index_t, index_t>;
+ //! \brief Additional information about a triangle boundary
+ struct triangleinfo
+ {
+ //! \brief What's the third vertex of this triangle
+ index_t third_vertex;
+ //! \brief Id of triangle (starting position of the triangle in the result
+ //! value of mapbox::earcut)
+ triangleid triangleid;
+ };
+ using triangleinfomap_t = std::map<boundary_t, triangleinfo>;
+ struct MergedTriangles
+ {
+ //! \brief List of merged quadrilaterals
+ std::vector<Quadrilateral> quadrilaterals;
+ //! \brief Ids of cut triangles
+ std::set<triangleid> cutTriangles;
+ };
+ static MergedTriangles mergeTriangles(
+ const std::vector<std::uint16_t>& indices,
+ std::vector<glm::vec3>::const_iterator polyBegin);
+}
static bool findQuadsToMerge(
- const boundarymap_t& boundaries,
+ const triangulate::triangleinfomap_t& boundaries,
auto&& iscut,
auto&& addMergedQuad
) {
bool foundQuads = false;
// Go through triangle boundaries
- for (boundarymap_t::const_iterator it1 = boundaries.begin(); it1 != boundaries.end(); ++it1) {
- const indexpair& pair1 = it1->first;
- const boundaryinfo& boundary1 = it1->second;
+ for (
+ triangulate::triangleinfomap_t::const_iterator it1 = boundaries.begin();
+ it1 != boundaries.end();
+ ++it1
+ ) {
+ const triangulate::boundary_t& boundary = it1->first;
+ const triangulate::triangleinfo& earcut_triangle_1 = it1->second;
// .. the ones we haven't already been merged...
- if (not iscut(boundary1.triangleid)) {
+ if (not iscut(earcut_triangle_1.triangleid)) {
// Look for its inverse boundary to find the touching triangle
- const indexpair inverse_boundary_key = std::make_pair(pair1.second, pair1.first);
- const boundarymap_t::const_iterator it2 = boundaries.find(inverse_boundary_key);
+ const triangulate::boundary_t inverse_boundary = std::make_pair(boundary.second, boundary.first);
+ const triangulate::triangleinfomap_t::const_iterator it2 = boundaries.find(inverse_boundary);
// Also if that hasn't been cut
if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) {
// Continue until no more new quads are found
@@ -53,42 +75,45 @@
return foundQuads;
}
-static MergedTriangles mergeTriangles(
+static triangulate::MergedTriangles triangulate::mergeTriangles(
const std::vector<std::uint16_t>& indices,
std::vector<glm::vec3>::const_iterator polyBegin)
{
MergedTriangles result;
- const auto iscut = [&result](const std::size_t i){
+ const auto iscut = [&result](const triangleid i){
return result.cutTriangles.find(i) != result.cutTriangles.end();
};
const auto addMergedQuad = [&result, polyBegin](
- boundarymap_t::const_iterator it1,
- boundarymap_t::const_iterator it2
+ triangleinfomap_t::const_iterator it1,
+ triangleinfomap_t::const_iterator it2
) {
- const indexpair& common_indices = it1->first;
- const boundaryinfo& boundary_1 = it1->second;
- const boundaryinfo& boundary_2 = it2->second;
+ const boundary_t& shared_boundary = it1->first;
+ const triangleinfo& earcut_triangle_1 = it1->second;
+ const triangleinfo& earcut_triangle_2 = it2->second;
const Quadrilateral quad{
- *(polyBegin + common_indices.first),
- *(polyBegin + boundary_2.third),
- *(polyBegin + common_indices.second),
- *(polyBegin + boundary_1.third),
+ *(polyBegin + shared_boundary.first),
+ *(polyBegin + earcut_triangle_2.third_vertex),
+ *(polyBegin + shared_boundary.second),
+ *(polyBegin + earcut_triangle_1.third_vertex),
};
if (isConvex(quad)) {
result.quadrilaterals.push_back(quad);
- result.cutTriangles.insert(boundary_1.triangleid);
- result.cutTriangles.insert(boundary_2.triangleid);
+ result.cutTriangles.insert(earcut_triangle_1.triangleid);
+ result.cutTriangles.insert(earcut_triangle_2.triangleid);
return true;
}
else {
return false;
}
};
- boundarymap_t boundaries;
+ triangleinfomap_t boundaries;
for (std::size_t i = 0; i < indices.size(); i += 3) {
const auto add = [&](const std::size_t o1, const std::size_t o2, const std::size_t o3){
const auto key = std::make_pair(indices[i + o1], indices[i + o2]);
- boundaries[key] = {indices[i + o3], i};
+ boundaries[key] = triangleinfo{
+ .third_vertex = indices[i + o3],
+ .triangleid = {i},
+ };
};
add(0, 1, 2);
add(1, 2, 0);
@@ -101,41 +126,35 @@
return result;
}
+//! \brief Polygonize a polygon into triangles and try merge as many of them
+//! as possible into quadrilaterals. The polygons must all reside in the same
+//! plane.
std::vector<PlainPolygonElement> polygonize(
std::vector<glm::vec3>::const_iterator begin,
- std::vector<glm::vec3>::const_iterator end,
- const glm::mat4& planeMatrix)
+ std::vector<glm::vec3>::const_iterator end)
{
std::vector<PlainPolygonElement> result;
- const glm::mat4 inverseGrid = glm::inverse(planeMatrix);
- // mapbox::earcut will always produce a CCW polygon, so if we're drawing
- // a CW polygon, we should invert the result afterwards
- const float shouldInvert = glm::dot(
- glm::vec3{inverseGrid[2]},
- glm::cross(*begin - *(begin + 1), *(begin + 2) - *(begin + 1)));
+ const glm::vec3 xvec = *begin - *(begin + 1);
+ const glm::vec3 yvec = *(begin + 2) - *(begin + 1);
+ const glm::vec3 zvec = glm::cross(xvec, yvec);
+ const glm::mat3 inverseMatrix = glm::inverse(glm::mat3{xvec, yvec, zvec});
std::vector<std::vector<glm::vec3>> polygons{1};
std::vector<glm::vec3>& polygon2d = polygons.back();
polygon2d.reserve(static_cast<std::size_t>(end - begin));
for (std::vector<glm::vec3>::const_iterator it = begin; it != end; ++it) {
- polygon2d.push_back(inverseGrid * glm::vec4{*it, 1});
+ polygon2d.push_back(inverseMatrix * glm::vec4{*it, 1});
}
- const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
- MergedTriangles mergedTriangles = mergeTriangles(indices, begin);
+ const std::vector<triangulate::index_t> indices = mapbox::earcut<triangulate::index_t>(polygons);
+ triangulate::MergedTriangles mergedTriangles = triangulate::mergeTriangles(indices, begin);
for (Quadrilateral& quad : mergedTriangles.quadrilaterals) {
- if (shouldInvert < 0) {
- invert(quad);
- }
result.push_back(quad);
}
for (std::size_t i = 0; i < indices.size(); i += 3) {
- if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
+ if (not mergedTriangles.cutTriangles.contains({i})) {
Triangle tri = triangle(
*(begin + indices[i]),
*(begin + indices[i + 1]),
*(begin + indices[i + 2]));
- if (shouldInvert < 0) {
- invert(tri);
- }
result.push_back(tri);
}
}