--- a/src/document.cpp Tue Jun 14 23:04:49 2022 +0300
+++ b/src/document.cpp Wed Jun 15 12:17:29 2022 +0300
@@ -18,11 +18,26 @@
#include <QMouseEvent>
#include <QPainter>
+#include "algorithm/earcut.h"
#include "document.h"
#include "model.h"
#include "ui/objecteditor.h"
#include "gl/partrenderer.h"
+// Make mapbox::earcut work with glm::vec3
+namespace mapbox {
+namespace util {
+template<> struct nth<0, glm::vec3>
+{
+ static constexpr float get(const glm::vec3& t) { return t.x; };
+};
+template<> struct nth<1, glm::vec3>
+{
+ static constexpr float get(const glm::vec3& t) { return t.y; };
+};
+}
+}
+
EditTools::EditTools(QObject* parent) :
QObject{parent},
RenderLayer{}
@@ -72,6 +87,10 @@
this->worldPosition = this->gridMatrix * glm::vec4{*this->worldPosition, 1};
this->polygon.back() = *this->worldPosition;
}
+ this->numpoints = this->polygon.size();
+ if (this->isCloseToExistingPoints()) {
+ this->numpoints -= 1;
+ }
}
static QVector<QPointF> convertWorldPointsToScreenPoints(
@@ -152,7 +171,6 @@
.pointBrush = {Qt::white},
.pointPen = {QBrush{Qt::black}, 2.0},
.polygonPen = {QBrush{Qt::black}, 2.0, Qt::DashLine},
- .badPolygonPen = {QBrush{Qt::red}, 2.0, Qt::DashLine},
.greenPolygonBrush = {QColor{64, 255, 128, 192}},
.redPolygonBrush = {QColor{255, 96, 96, 192}},
};
@@ -160,7 +178,6 @@
.pointBrush = {Qt::black},
.pointPen = {QBrush{Qt::white}, 2.0},
.polygonPen = {QBrush{Qt::white}, 2.0, Qt::DashLine},
- .badPolygonPen = {QBrush{Qt::red}, 2.0, Qt::DashLine},
.greenPolygonBrush = {QColor{64, 255, 128, 192}},
.redPolygonBrush = {QColor{255, 96, 96, 192}},
};
@@ -169,7 +186,7 @@
case SelectMode:
break;
case DrawMode:
- painter->setPen(this->isconcave ? pens.badPolygonPen : pens.polygonPen);
+ painter->setPen(pens.polygonPen);
for (const ModelAction& action : this->actions()) {
const opt<std::vector<glm::vec3>> points = modelActionPoints(action);
if (points.has_value()) {
@@ -201,13 +218,6 @@
}
}
-void EditTools::updatePreviewPolygon()
-{
- if (this->polygon.size() > 2) {
- this->isconcave = not isConvex(this->polygon);
- }
-}
-
void EditTools::removeLastPoint()
{
if (this->polygon.size() > 1) {
@@ -215,12 +225,17 @@
}
}
-template<typename T>
-bool isCloseToExistingPoints(T begin, T end, const glm::vec3 &pos)
+bool EditTools::isCloseToExistingPoints() const
{
- return std::any_of(begin, end, [&pos](const glm::vec3& p){
- return isclose(pos, p);
- });
+ if (this->worldPosition.has_value()) {
+ const glm::vec3& pos = *this->worldPosition;
+ return std::any_of(this->polygon.begin(), this->polygon.end() - 1, [&pos](const glm::vec3& p){
+ return isclose(pos, p);
+ });
+ }
+ else {
+ return false;
+ }
}
EditingMode EditTools::currentEditingMode() const
@@ -239,12 +254,11 @@
break;
case DrawMode:
if (event->button() == Qt::LeftButton and this->worldPosition.has_value()) {
- if (isCloseToExistingPoints(this->polygon.begin(), this->polygon.end() - 1, *this->worldPosition)) {
+ if (isCloseToExistingPoints()) {
this->closeShape();
}
else {
this->polygon.push_back(*this->worldPosition);
- this->updatePreviewPolygon();
}
}
else if (true
@@ -252,53 +266,142 @@
and this->polygon.size() > 1
) {
this->removeLastPoint();
- updatePreviewPolygon();
}
break;
}
}
+constexpr float distancesquared(const glm::vec3& p1, const glm::vec3& p2)
+{
+ const float dx = p2.x - p1.x;
+ const float dy = p2.y - p1.y;
+ const float dz = p2.z - p1.z;
+ return (dx * dx) + (dy * dy) + (dz * dz);
+}
+
+inline float area(const Quadrilateral& q)
+{
+ return 0.5 * (
+ glm::length(glm::cross(q.p2 - q.p1, q.p3 - q.p1)) +
+ glm::length(glm::cross(q.p3 - q.p2, q.p4 - q.p2))
+ );
+}
+
+inline float energy(const Quadrilateral& q)
+{
+ const float L2 = distancesquared(q.p1, q.p2)
+ + distancesquared(q.p2, q.p3)
+ + distancesquared(q.p3, q.p4)
+ + distancesquared(q.p4, q.p1);
+ return 1 - 6.928203230275509 * area(q) / L2;
+}
+
+struct MergedTriangles
+{
+ std::vector<Quadrilateral> quadrilaterals;
+ std::set<std::size_t> cutTriangles;
+};
+
+static MergedTriangles mergeTriangles(
+ const std::vector<std::uint16_t>& indices,
+ const std::vector<glm::vec3>& polygon)
+{
+ MergedTriangles result;
+ using indextype = std::uint16_t;
+ using indexpair = std::pair<indextype, indextype>;
+ struct boundaryinfo { indextype third; std::size_t triangleid; };
+ std::map<indexpair, boundaryinfo> boundaries;
+ for (std::size_t i = 0; i < indices.size(); i += 3) {
+ const auto add = [&](int o1, int o2, int o3){
+ const auto key = std::make_pair(indices[i + o1], indices[i + o2]);
+ boundaries[key] = {indices[i + o3], i};
+ };
+ add(0, 1, 2);
+ add(1, 2, 0);
+ add(2, 0, 1);
+ }
+ std::vector<std::array<indextype, 4>> quadindices;
+ std::vector<Quadrilateral> quads;
+ bool repeat = true;
+ const auto iscut = [&result](const std::size_t i){
+ return result.cutTriangles.find(i) != result.cutTriangles.end();
+ };
+ while (repeat) {
+ repeat = false;
+ // TODO: make this a function that returns quadrilateral indices
+ // Go through triangle boundaries
+ for (const auto& it1 : boundaries) {
+ const indexpair& pair1 = it1.first;
+ const boundaryinfo& boundary1 = it1.second;
+ // .. the ones we haven't already merged anyway
+ if (not iscut(boundary1.triangleid)) {
+ // Look for its inverse boundary to find the touching triangle
+ const auto pair2 = std::make_pair(pair1.second, pair1.first);
+ const auto it2 = boundaries.find(pair2);
+ // Also if that hasn't been cut
+ if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) {
+ const Quadrilateral quad{
+ polygon[pair1.first],
+ polygon[it2->second.third],
+ polygon[pair1.second],
+ polygon[boundary1.third],
+ };
+ if (isConvex(quad)) {
+ result.quadrilaterals.push_back(quad);
+ result.cutTriangles.insert(boundary1.triangleid);
+ result.cutTriangles.insert(it2->second.triangleid);
+ repeat = true;
+ }
+ }
+ }
+ }
+ }
+ return result;
+}
+
const std::vector<ModelAction> EditTools::actions() const
{
std::vector<ModelAction> result;
- if (this->polygon.size() >= 2 and this->polygon.size() <= 4) {
- switch (this->polygon.size()) {
- case 2:
- result.push_back(AppendToModel{
- .newElement = Colored<LineSegment>{
- LineSegment{
- .p1 = this->polygon[0],
- .p2 = this->polygon[1],
- },
- EDGE_COLOR,
- }
- });
- break;
- case 3:
+ if (this->numpoints == 2) {
+ result.push_back(AppendToModel{
+ .newElement = Colored<LineSegment>{
+ LineSegment{
+ .p1 = this->polygon[0],
+ .p2 = this->polygon[1],
+ },
+ EDGE_COLOR,
+ }
+ });
+ }
+ else if (this->numpoints > 2) {
+ const glm::mat4 inverseGrid = glm::inverse(this->gridMatrix);
+ std::vector<std::vector<glm::vec3>> polygons{1};
+ std::vector<glm::vec3>& polygon2d = polygons.back();
+ polygon2d.reserve(this->numpoints);
+ for (std::size_t i = 0; i < this->numpoints; ++i) {
+ polygon2d.push_back(inverseGrid * glm::vec4{this->polygon[i], 1});
+ }
+ using indextype = std::uint16_t;
+ const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
+ MergedTriangles mergedTriangles = mergeTriangles(indices, this->polygon);
+ for (const Quadrilateral& quad : mergedTriangles.quadrilaterals) {
result.push_back(AppendToModel{
- .newElement = Colored<Triangle>{
- Triangle{
- .p1 = this->polygon[0],
- .p2 = this->polygon[1],
- .p3 = this->polygon[2],
- },
- MAIN_COLOR,
- }
+ .newElement = Colored<Quadrilateral>{quad, MAIN_COLOR},
});
- break;
- case 4:
- result.push_back(AppendToModel{
- .newElement = Colored<Quadrilateral>{
- Quadrilateral{
- .p1 = this->polygon[0],
- .p2 = this->polygon[1],
- .p3 = this->polygon[2],
- .p4 = this->polygon[3],
- },
- MAIN_COLOR,
- }
- });
- break;
+ }
+ for (std::size_t i = 0; i < indices.size(); i += 3) {
+ if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
+ result.push_back(AppendToModel{
+ .newElement = Colored<Triangle>{
+ Triangle{
+ .p1 = this->polygon[indices[i]],
+ .p2 = this->polygon[indices[i + 1]],
+ .p3 = this->polygon[indices[i + 2]],
+ },
+ MAIN_COLOR,
+ }
+ });
+ }
}
}
return result;
@@ -310,5 +413,4 @@
Q_EMIT this->modelAction(action);
}
this->polygon.clear();
- this->updatePreviewPolygon();
}