src/document.cpp

/*
 *  LDForge: LDraw parts authoring CAD
 *  Copyright (C) 2013 - 2020 Teemu Piippo
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#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{}
{
}

EditTools::~EditTools()
{
}

void EditTools::setEditMode(EditingMode mode)
{
	this->mode = mode;
}

void EditTools::setGridMatrix(const glm::mat4& gridMatrix)
{
	this->gridMatrix = gridMatrix;
	this->gridPlane = planeFromTriangle({
		this->gridMatrix * glm::vec4{0, 0, 0, 1},
		this->gridMatrix * glm::vec4{1, 0, 0, 1},
		this->gridMatrix * glm::vec4{0, 1, 0, 1},
	});
}

void EditTools::mvpMatrixChanged(const glm::mat4& matrix)
{
	this->mvpMatrix = matrix;
}

void EditTools::mouseMoved(const QMouseEvent* event)
{
	this->worldPosition = this->renderer->screenToModelCoordinates(event->pos(), this->gridPlane);
	if (this->worldPosition.has_value())
	{
		// Snap the position to grid. This procedure is basically the "change of basis" and almost follows the
		// A⁻¹ × M × A formula which is used to perform a transformation in some other coordinate system, except
		// we actually use the inverted matrix first and the regular one last to perform the transformation of
		// grid coordinates in our XY coordinate system. Also, we're rounding the coordinates which is obviously
		// not a linear transformation, but fits the pattern anyway.
		// First transform the coordinates to the XY plane...
		this->worldPosition = glm::inverse(this->gridMatrix) * glm::vec4{*this->worldPosition, 1};
		// Then round the coordinates to integer precision...
		this->worldPosition = glm::round(*this->worldPosition);
		// And finally transform it back to grid coordinates by transforming it with the
		// grid matrix.
		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(
	const std::vector<glm::vec3> &worldPoints,
	const PartRenderer* renderer)
{
	QVector<QPointF> points2d;
	points2d.reserve(worldPoints.size());
	for (const glm::vec3& point : worldPoints)
	{
		points2d.push_back(renderer->modelToScreenCoordinates(point));
	}
	return points2d;
}

static Winding worldPolygonWinding(
	const std::vector<glm::vec3> &points,
	const PartRenderer* renderer)
{
	return winding(QPolygonF{convertWorldPointsToScreenPoints(points, renderer)});
}

static void drawWorldPoint(
	QPainter* painter,
	const glm::vec3& worldPoint,
	const PartRenderer* renderer)
{
	const QPointF center = renderer->modelToScreenCoordinates(worldPoint);
	painter->drawEllipse(inscribe(CircleF{center, 5}));
}

static void drawWorldPolyline(
	QPainter *painter,
	const std::vector<glm::vec3> &points,
	const PartRenderer* renderer)
{
	painter->drawPolyline(QPolygonF{convertWorldPointsToScreenPoints(points, renderer)});
}

static void drawWorldPolygon(
	QPainter* painter,
	const std::vector<glm::vec3> &points,
	const PartRenderer* renderer)
{
	painter->drawPolygon(QPolygonF{convertWorldPointsToScreenPoints(points, renderer)});
}

static opt<std::vector<glm::vec3>> modelActionPoints(const ModelAction& action)
{
	opt<std::vector<glm::vec3>> result;
	if (const AppendToModel* append = std::get_if<AppendToModel>(&action)) {
		const ModelElement& newElement = append->newElement;
		if (const LineSegment* seg = std::get_if<Colored<LineSegment>>(&newElement)) {
			result = {seg->p1, seg->p2};
		}
		else if (const Triangle* tri = std::get_if<Colored<Triangle>>(&newElement)) {
			result = {tri->p1, tri->p2, tri->p3};
		}
		else if (const Quadrilateral* quad = std::get_if<Colored<Quadrilateral>>(&newElement)) {
			result = {quad->p1, quad->p2, quad->p3, quad->p4};
		}
	}
	return result;
}

void EditTools::overpaint(QPainter* painter)
{
	struct Pens
	{
		const QBrush pointBrush;
		const QPen pointPen;
		const QPen polygonPen;
		const QPen badPolygonPen;
		const QBrush greenPolygonBrush;
		const QBrush redPolygonBrush;
	};
	static const Pens brightPens{
		.pointBrush = {Qt::white},
		.pointPen = {QBrush{Qt::black}, 2.0},
		.polygonPen = {QBrush{Qt::black}, 2.0, Qt::DashLine},
		.greenPolygonBrush = {QColor{64, 255, 128, 192}},
		.redPolygonBrush = {QColor{255, 96, 96, 192}},
	};
	static const Pens darkPens{
		.pointBrush = {Qt::black},
		.pointPen = {QBrush{Qt::white}, 2.0},
		.polygonPen = {QBrush{Qt::white}, 2.0, Qt::DashLine},
		.greenPolygonBrush = {QColor{64, 255, 128, 192}},
		.redPolygonBrush = {QColor{255, 96, 96, 192}},
	};
	const Pens& pens = (this->renderer->isDark() ? darkPens : brightPens);
	switch(this->mode) {
	case SelectMode:
		break;
	case DrawMode:
		painter->setPen(pens.polygonPen);
		for (const ModelAction& action : this->actions()) {
			const std::vector<glm::vec3> points = modelActionPoints(action).value_or(std::vector<glm::vec3>{});
			if (points.size() == 2) {
				drawWorldPolyline(painter, points, renderer);
			}
			else {
				if (worldPolygonWinding(points, this->renderer) == Winding::Clockwise) {
					painter->setBrush(pens.greenPolygonBrush);
				}
				else {
					painter->setBrush(pens.redPolygonBrush);
				}
				drawWorldPolygon(painter, points, this->renderer);
			}
		}
		//drawWorldPolyline(painter, this->previewPolygon, this->renderer);
		painter->setBrush(pens.pointBrush);
		painter->setPen(pens.pointPen);
		for (const glm::vec3& point : this->polygon) {
			drawWorldPoint(painter, point, this->renderer);
		}
		break;
	}
	if (this->worldPosition.has_value())
	{
		painter->setRenderHint(QPainter::Antialiasing);
		painter->setPen(Qt::white);
		painter->setBrush(Qt::green);
		const QPointF pos = this->renderer->modelToScreenCoordinates(*this->worldPosition);
		painter->drawEllipse(pos, 5, 5);
		painter->drawText(pos + QPointF{5, 5}, vectorToString(*this->worldPosition));
	}
}

void EditTools::removeLastPoint()
{
	if (this->polygon.size() > 1) {
		this->polygon.erase(this->polygon.end() - 1);
	}
}

bool EditTools::isCloseToExistingPoints() const
{
	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
{
	return this->mode;
}

void EditTools::mouseClick(const QMouseEvent* event)
{
	switch(this->mode) {
	case SelectMode:
		if (event->button() == Qt::LeftButton) {
			const ModelId highlighted = this->renderer->pick(event->pos());
			Q_EMIT this->select({highlighted}, false);
		}
		break;
	case DrawMode:
		if (event->button() == Qt::LeftButton and this->worldPosition.has_value()) {
			if (isCloseToExistingPoints()) {
				this->closeShape();
			}
			else {
				this->polygon.push_back(*this->worldPosition);
			}
		}
		else if (true
			and event->button() == Qt::RightButton
			and this->polygon.size() > 1
		) {
			this->removeLastPoint();
		}
		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;
		// 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->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<Quadrilateral>{quad, MAIN_COLOR},
			});
		}
		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;
}

void EditTools::closeShape()
{
	for (const ModelAction& action : this->actions()) {
		Q_EMIT this->modelAction(action);
	}
	this->polygon.clear();
	this->polygon.push_back(this->worldPosition.value_or(glm::vec3{0, 0, 0}));
}