summaryrefslogtreecommitdiff
path: root/thirdparty/thekla_atlas/nvmesh/halfedge
diff options
context:
space:
mode:
Diffstat (limited to 'thirdparty/thekla_atlas/nvmesh/halfedge')
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp57
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Edge.h70
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Face.cpp268
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Face.h106
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.cpp1284
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.h274
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.cpp94
-rw-r--r--thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.h221
8 files changed, 2374 insertions, 0 deletions
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp b/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp
new file mode 100644
index 0000000000..671650296c
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp
@@ -0,0 +1,57 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#include "nvmesh.h" // pch
+
+#include "Edge.h"
+#include "Vertex.h"
+
+#include "nvmath/Vector.inl"
+
+using namespace nv;
+using namespace HalfEdge;
+
+Vector3 Edge::midPoint() const
+{
+ return (to()->pos + from()->pos) * 0.5f;
+}
+
+float Edge::length() const
+{
+ return ::length(to()->pos - from()->pos);
+}
+
+// Return angle between this edge and the previous one.
+float Edge::angle() const {
+ Vector3 p = vertex->pos;
+ Vector3 a = prev->vertex->pos;
+ Vector3 b = next->vertex->pos;
+
+ Vector3 v0 = a - p;
+ Vector3 v1 = b - p;
+
+ return acosf(dot(v0, v1) / (nv::length(v0) * nv::length(v1)));
+}
+
+bool Edge::isValid() const
+{
+ // null face is OK.
+ if (next == NULL || prev == NULL || pair == NULL || vertex == NULL) return false;
+ if (next->prev != this) return false;
+ if (prev->next != this) return false;
+ if (pair->pair != this) return false;
+ return true;
+}
+
+/*
+Edge * Edge::nextBoundary() {
+ nvDebugCheck(this->m_pair == NULL);
+
+}
+
+Edge * Edge::prevBoundary() {
+ nvDebugCheck(this->m_pair == NULL);
+
+}
+*/
+
+
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.h b/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.h
new file mode 100644
index 0000000000..25c47f4860
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.h
@@ -0,0 +1,70 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#pragma once
+#ifndef NV_MESH_HALFEDGE_EDGE_H
+#define NV_MESH_HALFEDGE_EDGE_H
+
+#include "nvmath/Vector.h"
+
+namespace nv
+{
+ namespace HalfEdge { class Vertex; class Face; class Edge; }
+
+ /// Half edge edge.
+ class HalfEdge::Edge
+ {
+ NV_FORBID_COPY(Edge);
+ public:
+
+ uint id;
+
+ Edge * next;
+ Edge * prev; // This is not strictly half-edge, but makes algorithms easier and faster.
+ Edge * pair;
+ Vertex * vertex;
+ Face * face;
+
+
+ // Default constructor.
+ Edge(uint id) : id(id), next(NULL), prev(NULL), pair(NULL), vertex(NULL), face(NULL)
+ {
+ }
+
+
+ // Vertex queries.
+ const Vertex * from() const { return vertex; }
+ Vertex * from() { return vertex; }
+
+ const Vertex * to() const { return pair->vertex; } // This used to be 'next->vertex', but that changed often when the connectivity of the mesh changes.
+ Vertex * to() { return pair->vertex; }
+
+
+ // Edge queries.
+ void setNext(Edge * e) { next = e; if (e != NULL) e->prev = this; }
+ void setPrev(Edge * e) { prev = e; if (e != NULL) e->next = this; }
+
+ // @@ Add these helpers:
+ //Edge * nextBoundary();
+ //Edge * prevBoundary();
+
+
+ // @@ It would be more simple to only check m_pair == NULL
+ // Face queries.
+ bool isBoundary() const { return !(face && pair->face); }
+
+ // @@ This is not exactly accurate, we should compare the texture coordinates...
+ bool isSeam() const { return vertex != pair->next->vertex || next->vertex != pair->vertex; }
+
+ bool isValid() const;
+
+ // Geometric queries.
+ Vector3 midPoint() const;
+ float length() const;
+ float angle() const;
+
+ };
+
+} // nv namespace
+
+
+#endif // NV_MESH_HALFEDGE_EDGE_H
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Face.cpp b/thirdparty/thekla_atlas/nvmesh/halfedge/Face.cpp
new file mode 100644
index 0000000000..9f6987154e
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Face.cpp
@@ -0,0 +1,268 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#include "nvmesh.h" // pch
+
+#include "Face.h"
+#include "Vertex.h"
+
+#include "nvmath/Fitting.h"
+#include "nvmath/Plane.h"
+#include "nvmath/Vector.inl"
+
+#include "nvcore/Array.h"
+
+
+using namespace nv;
+using namespace HalfEdge;
+
+/// Get face area.
+float Face::area() const
+{
+ float area = 0;
+ const Vector3 & v0 = edge->from()->pos;
+
+ for (ConstEdgeIterator it(edges(edge->next)); it.current() != edge->prev; it.advance())
+ {
+ const Edge * e = it.current();
+
+ const Vector3 & v1 = e->vertex->pos;
+ const Vector3 & v2 = e->next->vertex->pos;
+
+ area += length(cross(v1-v0, v2-v0));
+ }
+
+ return area * 0.5f;
+}
+
+float Face::parametricArea() const
+{
+ float area = 0;
+ const Vector2 & v0 = edge->from()->tex;
+
+ for (ConstEdgeIterator it(edges(edge->next)); it.current() != edge->prev; it.advance())
+ {
+ const Edge * e = it.current();
+
+ const Vector2 & v1 = e->vertex->tex;
+ const Vector2 & v2 = e->next->vertex->tex;
+
+ area += triangleArea(v0, v1, v2);
+ }
+
+ return area * 0.5f;
+}
+
+
+/// Get boundary length.
+float Face::boundaryLength() const
+{
+ float bl = 0;
+
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ bl += edge->length();
+ }
+
+ return bl;
+}
+
+
+/// Get face normal.
+Vector3 Face::normal() const
+{
+ Vector3 n(0);
+
+ const Vertex * vertex0 = NULL;
+
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ nvCheck(edge != NULL);
+
+ if (vertex0 == NULL)
+ {
+ vertex0 = edge->vertex;
+ }
+ else if (edge->next->vertex != vertex0)
+ {
+ const HalfEdge::Vertex * vertex1 = edge->from();
+ const HalfEdge::Vertex * vertex2 = edge->to();
+
+ const Vector3 & p0 = vertex0->pos;
+ const Vector3 & p1 = vertex1->pos;
+ const Vector3 & p2 = vertex2->pos;
+
+ Vector3 v10 = p1 - p0;
+ Vector3 v20 = p2 - p0;
+
+ n += cross(v10, v20);
+ }
+ }
+
+ return normalizeSafe(n, Vector3(0, 0, 1), 0.0f);
+
+
+ // Get face points eliminating duplicates.
+ /*Array<Vector3> points(4);
+
+ points.append(m_edge->prev()->from()->pos);
+
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ nvDebugCheck(edge != NULL);
+
+ const Vector3 & p = edge->from()->pos;
+ if (points.back() != p)
+ {
+ points.append(edge->from()->pos);
+ }
+ }
+
+ points.popBack();
+
+ if (points.count() < 3)
+ {
+ // Invalid normal.
+ return Vector3(0.0f);
+ }
+ else
+ {
+ // Compute regular normal.
+ Vector3 normal = normalizeSafe(cross(points[1] - points[0], points[2] - points[0]), Vector3(0.0f), 0.0f);
+
+#pragma NV_MESSAGE("TODO: make sure these three points are not colinear")
+
+ if (points.count() > 3)
+ {
+ // Compute best fitting plane to the points.
+ Plane plane = Fit::bestPlane(points.count(), points.buffer());
+
+ // Adjust normal orientation.
+ if (dot(normal, plane.vector()) > 0) {
+ normal = plane.vector();
+ }
+ else {
+ normal = -plane.vector();
+ }
+ }
+
+ nvDebugCheck(isNormalized(normal));
+ return normal;
+ }*/
+}
+
+Vector3 Face::centroid() const
+{
+ Vector3 sum(0.0f);
+ uint count = 0;
+
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ sum += edge->from()->pos;
+ count++;
+ }
+
+ return sum / float(count);
+}
+
+
+bool Face::isValid() const
+{
+ uint count = 0;
+
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ if (edge->face != this) return false;
+ if (!edge->isValid()) return false;
+ if (!edge->pair->isValid()) return false;
+ count++;
+ }
+
+ if (count < 3) return false;
+
+ return true;
+}
+
+
+// Determine if this face contains the given edge.
+bool Face::contains(const Edge * e) const
+{
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ if(it.current() == e) return true;
+ }
+ return false;
+}
+
+// Returns index in this face of the given edge.
+uint Face::edgeIndex(const Edge * e) const
+{
+ int i = 0;
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance(), i++)
+ {
+ if(it.current() == e) return i;
+ }
+ return NIL;
+}
+
+
+Edge * Face::edgeAt(uint idx)
+{
+ int i = 0;
+ for(EdgeIterator it(edges()); !it.isDone(); it.advance(), i++) {
+ if (i == idx) return it.current();
+ }
+ return NULL;
+}
+const Edge * Face::edgeAt(uint idx) const
+{
+ int i = 0;
+ for(ConstEdgeIterator it(edges()); !it.isDone(); it.advance(), i++) {
+ if (i == idx) return it.current();
+ }
+ return NULL;
+}
+
+
+// Count the number of edges in this face.
+uint Face::edgeCount() const
+{
+ uint count = 0;
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance()) { ++count; }
+ return count;
+}
+
+// Determine if this is a boundary face.
+bool Face::isBoundary() const
+{
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ nvDebugCheck(edge->pair != NULL);
+
+ if (edge->pair->face == NULL) {
+ return true;
+ }
+ }
+ return false;
+}
+
+// Count the number of boundary edges in the face.
+uint Face::boundaryCount() const
+{
+ uint count = 0;
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance())
+ {
+ const Edge * edge = it.current();
+ nvDebugCheck(edge->pair != NULL);
+
+ if (edge->pair->face == NULL) {
+ count++;
+ }
+ }
+ return count;
+}
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Face.h b/thirdparty/thekla_atlas/nvmesh/halfedge/Face.h
new file mode 100644
index 0000000000..677f8666f0
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Face.h
@@ -0,0 +1,106 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#pragma once
+#ifndef NV_MESH_HALFEDGE_FACE_H
+#define NV_MESH_HALFEDGE_FACE_H
+
+#include <nvmesh/halfedge/Edge.h>
+
+namespace nv
+{
+ namespace HalfEdge { class Vertex; class Face; class Edge; }
+
+ /// Face of a half-edge mesh.
+ class HalfEdge::Face
+ {
+ NV_FORBID_COPY(Face);
+ public:
+
+ uint id;
+ uint16 group;
+ uint16 material;
+ Edge * edge;
+
+
+ Face(uint id) : id(id), group(~0), material(~0), edge(NULL) {}
+
+ float area() const;
+ float parametricArea() const;
+ float boundaryLength() const;
+ Vector3 normal() const;
+ Vector3 centroid() const;
+
+ bool isValid() const;
+
+ bool contains(const Edge * e) const;
+ uint edgeIndex(const Edge * e) const;
+
+ Edge * edgeAt(uint idx);
+ const Edge * edgeAt(uint idx) const;
+
+ uint edgeCount() const;
+ bool isBoundary() const;
+ uint boundaryCount() const;
+
+
+ // The iterator that visits the edges of this face in clockwise order.
+ class EdgeIterator //: public Iterator<Edge *>
+ {
+ public:
+ EdgeIterator(Edge * e) : m_end(NULL), m_current(e) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->next;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual Edge * current() const { return m_current; }
+ Vertex * vertex() const { return m_current->vertex; }
+
+ private:
+ Edge * m_end;
+ Edge * m_current;
+ };
+
+ EdgeIterator edges() { return EdgeIterator(edge); }
+ EdgeIterator edges(Edge * e)
+ {
+ nvDebugCheck(contains(e));
+ return EdgeIterator(e);
+ }
+
+ // The iterator that visits the edges of this face in clockwise order.
+ class ConstEdgeIterator //: public Iterator<const Edge *>
+ {
+ public:
+ ConstEdgeIterator(const Edge * e) : m_end(NULL), m_current(e) { }
+ ConstEdgeIterator(const EdgeIterator & it) : m_end(NULL), m_current(it.current()) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->next;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual const Edge * current() const { return m_current; }
+ const Vertex * vertex() const { return m_current->vertex; }
+
+ private:
+ const Edge * m_end;
+ const Edge * m_current;
+ };
+
+ ConstEdgeIterator edges() const { return ConstEdgeIterator(edge); }
+ ConstEdgeIterator edges(const Edge * e) const
+ {
+ nvDebugCheck(contains(e));
+ return ConstEdgeIterator(e);
+ }
+ };
+
+} // nv namespace
+
+#endif // NV_MESH_HALFEDGE_FACE_H
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.cpp b/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.cpp
new file mode 100644
index 0000000000..0012513bce
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.cpp
@@ -0,0 +1,1284 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#include "nvmesh.h" // pch
+
+#include "Mesh.h"
+#include "Edge.h"
+#include "Vertex.h"
+#include "Face.h"
+
+#include "nvmesh/TriMesh.h"
+#include "nvmesh/QuadTriMesh.h"
+#include "nvmesh/MeshBuilder.h"
+
+#include "nvmath/Vector.inl"
+#include "nvcore/Array.inl"
+#include "nvcore/HashMap.inl"
+
+
+using namespace nv;
+using namespace HalfEdge;
+
+Mesh::Mesh() : m_colocalVertexCount(0)
+{
+ errorCount = 0;
+}
+
+Mesh::Mesh(const Mesh * mesh)
+{
+ errorCount = 0;
+
+ // Copy mesh vertices.
+ const uint vertexCount = mesh->vertexCount();
+ m_vertexArray.resize(vertexCount);
+
+ for (uint v = 0; v < vertexCount; v++)
+ {
+ const Vertex * vertex = mesh->vertexAt(v);
+ nvDebugCheck(vertex->id == v);
+
+ m_vertexArray[v] = new Vertex(v);
+ m_vertexArray[v]->pos = vertex->pos;
+ m_vertexArray[v]->nor = vertex->nor;
+ m_vertexArray[v]->tex = vertex->tex;
+ }
+
+ m_colocalVertexCount = vertexCount;
+
+
+ // Copy mesh faces.
+ const uint faceCount = mesh->faceCount();
+
+ Array<uint> indexArray(3);
+
+ for (uint f = 0; f < faceCount; f++)
+ {
+ const Face * face = mesh->faceAt(f);
+
+ for(Face::ConstEdgeIterator it(face->edges()); !it.isDone(); it.advance()) {
+ const Vertex * vertex = it.current()->from();
+ indexArray.append(vertex->id);
+ }
+
+ addFace(indexArray);
+ indexArray.clear();
+ }
+}
+
+Mesh::~Mesh()
+{
+ clear();
+}
+
+
+void Mesh::clear()
+{
+ deleteAll(m_vertexArray);
+ m_vertexArray.clear();
+
+ foreach(i, m_edgeMap)
+ {
+ delete m_edgeMap[i].value;
+ }
+ //deleteAll(m_edgeArray); // edgeArray only contains 1/2 of the edges!
+ m_edgeArray.clear();
+ m_edgeMap.clear();
+
+ deleteAll(m_faceArray);
+ m_faceArray.clear();
+}
+
+
+Vertex * Mesh::addVertex(const Vector3 & pos)
+{
+ nvDebugCheck(isFinite(pos));
+
+ Vertex * v = new Vertex(m_vertexArray.count());
+ v->pos = pos;
+ m_vertexArray.append(v);
+
+ return v;
+
+// return addVertex(m_vertexArray.count(), pos);
+}
+
+/*Vertex * Mesh::addVertex(uint id, const Vector3 & pos)
+{
+ nvDebugCheck(isFinite(pos));
+
+ Vertex * v = new Vertex(id);
+ v->pos = pos;
+ m_vertexArray.append(v);
+
+ return v;
+}*/
+
+/*void Mesh::addVertices(const Mesh * mesh)
+{
+nvCheck(mesh != NULL);
+
+// Add mesh vertices
+for (uint v = 0; v < vertexCount; v++)
+{
+const Vertex * vertex = mesh->vertexAt(v);
+nvDebugCheck(vertex != NULL);
+
+Vertex * v = addVertex(vertex->pos());
+nvDebugCheck(v != NULL);
+
+v->setNor(vertex->nor());
+v->setTex(vertex->tex());
+}
+}*/
+
+
+/// Link colocal vertices based on geometric location only.
+void Mesh::linkColocals()
+{
+ nvDebug("--- Linking colocals:\n");
+
+ const uint vertexCount = this->vertexCount();
+ HashMap<Vector3, Vertex *> vertexMap(vertexCount);
+
+ for (uint v = 0; v < vertexCount; v++)
+ {
+ Vertex * vertex = vertexAt(v);
+
+ Vertex * colocal;
+ if (vertexMap.get(vertex->pos, &colocal))
+ {
+ colocal->linkColocal(vertex);
+ }
+ else
+ {
+ vertexMap.add(vertex->pos, vertex);
+ }
+ }
+
+ m_colocalVertexCount = vertexMap.count();
+
+ nvDebug("--- %d vertex positions.\n", m_colocalVertexCount);
+
+ // @@ Remove duplicated vertices? or just leave them as colocals?
+}
+
+void Mesh::linkColocalsWithCanonicalMap(const Array<uint> & canonicalMap)
+{
+ nvDebug("--- Linking colocals:\n");
+
+ uint vertexMapSize = 0;
+ foreach(i, canonicalMap) {
+ vertexMapSize = max(vertexMapSize, canonicalMap[i] + 1);
+ }
+
+ Array<Vertex *> vertexMap;
+ vertexMap.resize(vertexMapSize, NULL);
+
+ m_colocalVertexCount = 0;
+
+ const uint vertexCount = this->vertexCount();
+ for (uint v = 0; v < vertexCount; v++)
+ {
+ Vertex * vertex = vertexAt(v);
+
+ Vertex * colocal = vertexMap[canonicalMap[v]];
+ if (colocal != NULL)
+ {
+ nvDebugCheck(vertex->pos == colocal->pos);
+ colocal->linkColocal(vertex);
+ }
+ else
+ {
+ vertexMap[canonicalMap[v]] = vertex;
+ m_colocalVertexCount++;
+ }
+ }
+
+ nvDebug("--- %d vertex positions.\n", m_colocalVertexCount);
+}
+
+
+Face * Mesh::addFace()
+{
+ Face * f = new Face(m_faceArray.count());
+ m_faceArray.append(f);
+ return f;
+}
+
+Face * Mesh::addFace(uint v0, uint v1, uint v2)
+{
+ Array<uint> indexArray(3);
+ indexArray << v0 << v1 << v2;
+ return addFace(indexArray, 0, 3);
+}
+
+Face * Mesh::addFace(uint v0, uint v1, uint v2, uint v3)
+{
+ Array<uint> indexArray(4);
+ indexArray << v0 << v1 << v2 << v3;
+ return addFace(indexArray, 0, 4);
+}
+
+Face * Mesh::addFace(const Array<uint> & indexArray)
+{
+ return addFace(indexArray, 0, indexArray.count());
+}
+
+
+Face * Mesh::addFace(const Array<uint> & indexArray, uint first, uint num)
+{
+ nvDebugCheck(first < indexArray.count());
+ nvDebugCheck(num <= indexArray.count()-first);
+ nvDebugCheck(num > 2);
+
+ if (!canAddFace(indexArray, first, num)) {
+ errorCount++;
+ return NULL;
+ }
+
+ Face * f = new Face(m_faceArray.count());
+
+ Edge * firstEdge = NULL;
+ Edge * last = NULL;
+ Edge * current = NULL;
+
+ for(uint i = 0; i < num-1; i++)
+ {
+ current = addEdge(indexArray[first+i], indexArray[first+i+1]);
+ nvCheck(current != NULL && current->face == NULL);
+
+ current->face = f;
+
+ if (last != NULL) last->setNext(current);
+ else firstEdge = current;
+
+ last = current;
+ }
+
+ current = addEdge(indexArray[first+num-1], indexArray[first]);
+ nvCheck(current != NULL && current->face == NULL);
+
+ current->face = f;
+
+ last->setNext(current);
+ current->setNext(firstEdge);
+
+ f->edge = firstEdge;
+ m_faceArray.append(f);
+
+ return f;
+}
+
+/*void Mesh::addFaces(const Mesh * mesh)
+{
+nvCheck(mesh != NULL);
+
+Array indexArray;
+// Add faces
+
+}*/
+
+
+// Return true if the face can be added to the manifold mesh.
+bool Mesh::canAddFace(const Array<uint> & indexArray, uint first, uint num) const
+{
+ for (uint j = num - 1, i = 0; i < num; j = i++) {
+ if (!canAddEdge(indexArray[first+j], indexArray[first+i])) {
+ errorIndex0 = indexArray[first+j];
+ errorIndex1 = indexArray[first+i];
+ return false;
+ }
+ }
+
+ // We also have to make sure the face does not have any duplicate edge!
+ for (uint i = 0; i < num; i++) {
+
+ int i0 = indexArray[first + i + 0];
+ int i1 = indexArray[first + (i + 1)%num];
+
+ for (uint j = i + 1; j < num; j++) {
+ int j0 = indexArray[first + j + 0];
+ int j1 = indexArray[first + (j + 1)%num];
+
+ if (i0 == j0 && i1 == j1) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+// Return true if the edge doesn't exist or doesn't have any adjacent face.
+bool Mesh::canAddEdge(uint i, uint j) const
+{
+ if (i == j) {
+ // Skip degenerate edges.
+ return false;
+ }
+
+ // Same check, but taking into account colocal vertices.
+ const Vertex * v0 = vertexAt(i);
+ const Vertex * v1 = vertexAt(j);
+
+ for(Vertex::ConstVertexIterator it(v0->colocals()); !it.isDone(); it.advance())
+ {
+ if (it.current() == v1)
+ {
+ // Skip degenerate edges.
+ return false;
+ }
+ }
+
+ // Make sure edge has not been added yet.
+ Edge * edge = findEdge(i, j);
+
+ return edge == NULL || edge->face == NULL; // We ignore edges that don't have an adjacent face yet, since this face could become the edge's face.
+}
+
+Edge * Mesh::addEdge(uint i, uint j)
+{
+ nvCheck(i != j);
+
+ Edge * edge = findEdge(i, j);
+
+ if (edge != NULL) {
+ // Edge may already exist, but its face must not be set.
+ nvDebugCheck(edge->face == NULL);
+
+ // Nothing else to do!
+
+ }
+ else {
+ // Add new edge.
+
+ // Lookup pair.
+ Edge * pair = findEdge(j, i);
+
+ if (pair != NULL)
+ {
+ // Create edge with same id.
+ edge = new Edge(pair->id + 1);
+
+ // Link edge pairs.
+ edge->pair = pair;
+ pair->pair = edge;
+
+ // @@ I'm not sure this is necessary!
+ pair->vertex->setEdge(pair);
+ }
+ else
+ {
+ // Create edge.
+ edge = new Edge(2*m_edgeArray.count());
+
+ // Add only unpaired edges.
+ m_edgeArray.append(edge);
+ }
+
+ edge->vertex = m_vertexArray[i];
+ m_edgeMap.add(Key(i,j), edge);
+ }
+
+ // Face and Next are set by addFace.
+
+ return edge;
+}
+
+
+/// Find edge, test all colocals.
+Edge * Mesh::findEdge(uint i, uint j) const
+{
+ Edge * edge = NULL;
+
+ const Vertex * v0 = vertexAt(i);
+ const Vertex * v1 = vertexAt(j);
+
+ // Test all colocal pairs.
+ for(Vertex::ConstVertexIterator it0(v0->colocals()); !it0.isDone(); it0.advance())
+ {
+ for(Vertex::ConstVertexIterator it1(v1->colocals()); !it1.isDone(); it1.advance())
+ {
+ Key key(it0.current()->id, it1.current()->id);
+
+ if (edge == NULL) {
+ m_edgeMap.get(key, &edge);
+#if !defined(_DEBUG)
+ if (edge != NULL) return edge;
+#endif
+ }
+ else {
+ // Make sure that only one edge is found.
+ nvDebugCheck(!m_edgeMap.get(key));
+ }
+ }
+ }
+
+ return edge;
+}
+
+/// Link boundary edges once the mesh has been created.
+void Mesh::linkBoundary()
+{
+ nvDebug("--- Linking boundaries:\n");
+
+ int num = 0;
+
+ // Create boundary edges.
+ uint edgeCount = this->edgeCount();
+ for(uint e = 0; e < edgeCount; e++)
+ {
+ Edge * edge = edgeAt(e);
+ if (edge != NULL && edge->pair == NULL) {
+ Edge * pair = new Edge(edge->id + 1);
+
+ uint i = edge->from()->id;
+ uint j = edge->next->from()->id;
+
+ Key key(j,i);
+ nvCheck(!m_edgeMap.get(key));
+
+ pair->vertex = m_vertexArray[j];
+ m_edgeMap.add(key, pair);
+
+ edge->pair = pair;
+ pair->pair = edge;
+
+ num++;
+ }
+ }
+
+ // Link boundary edges.
+ for (uint e = 0; e < edgeCount; e++) {
+ Edge * edge = edgeAt(e);
+ if (edge != NULL && edge->pair->face == NULL) {
+ linkBoundaryEdge(edge->pair);
+ }
+ }
+
+ nvDebug("--- %d boundary edges.\n", num);
+}
+
+/// Link this boundary edge.
+void Mesh::linkBoundaryEdge(Edge * edge)
+{
+ nvCheck(edge->face == NULL);
+
+ // Make sure next pointer has not been set. @@ We want to be able to relink boundary edges after mesh changes.
+ //nvCheck(edge->next() == NULL);
+
+ Edge * next = edge;
+ while(next->pair->face != NULL) {
+ // Get pair prev
+ Edge * e = next->pair->next;
+ while (e->next != next->pair) {
+ e = e->next;
+ }
+ next = e;
+ }
+ edge->setNext(next->pair);
+
+ // Adjust vertex edge, so that it's the boundary edge. (required for isBoundary())
+ if (edge->vertex->edge != edge)
+ {
+ // Multiple boundaries in the same edge.
+ //nvCheck( edge->vertex()->edge() == NULL || edge->vertex()->edge()->face() != NULL );
+ edge->vertex->edge = edge;
+ }
+}
+
+
+/// Convert to tri mesh.
+TriMesh * Mesh::toTriMesh() const
+{
+ uint triangleCount = 0;
+
+ // Count triangle faces.
+ const uint faceCount = this->faceCount();
+ for(uint f = 0; f < faceCount; f++)
+ {
+ const Face * face = faceAt(f);
+ triangleCount += face->edgeCount() - 2;
+ }
+
+ TriMesh * triMesh = new TriMesh(triangleCount, vertexCount());
+
+ // Add vertices.
+ Array<TriMesh::Vertex> & vertices = triMesh->vertices();
+
+ const uint vertexCount = this->vertexCount();
+ for(uint v = 0; v < vertexCount; v++)
+ {
+ const Vertex * vertex = vertexAt(v);
+
+ TriMesh::Vertex triVertex;
+ triVertex.id = vertices.count();
+ triVertex.pos = vertex->pos;
+ triVertex.nor = vertex->nor;
+ triVertex.tex = vertex->tex;
+
+ vertices.append(triVertex);
+ }
+
+ // Add triangles.
+ Array<TriMesh::Face> & triangles = triMesh->faces();
+
+ for(uint f = 0; f < faceCount; f++)
+ {
+ const Face * face = faceAt(f);
+
+ // @@ Triangulate arbitrary polygons correctly.
+ const uint v0 = face->edge->vertex->id;
+ uint v1 = face->edge->next->vertex->id;
+
+ for(Face::ConstEdgeIterator it(face->edges()); !it.isDone(); it.advance())
+ {
+ uint v2 = it.current()->vertex->id;
+
+ // Skip the first two vertices.
+ if (v2 == v0 || v2 == v1) continue;
+
+ TriMesh::Face triangle;
+ triangle.id = triangles.count();
+ triangle.v[0] = v0;
+ triangle.v[1] = v1;
+ triangle.v[2] = v2;
+
+ v1 = v2;
+
+ triangles.append(triangle);
+ }
+ }
+
+ return triMesh;
+}
+
+QuadTriMesh * Mesh::toQuadTriMesh() const
+{
+ MeshBuilder builder;
+
+ const uint vertexCount = this->vertexCount();
+ builder.hintVertexCount(vertexCount);
+
+ for(uint v = 0; v < vertexCount; v++)
+ {
+ const Vertex * vertex = vertexAt(v);
+
+ builder.addPosition(vertex->pos);
+ builder.addNormal(vertex->nor);
+ builder.addTexCoord(vertex->tex);
+ }
+
+ const uint faceCount = this->faceCount();
+ builder.hintTriangleCount(faceCount);
+
+ for(uint f = 0; f < faceCount; f++)
+ {
+ const Face * face = faceAt(f);
+
+ builder.beginPolygon();
+
+ for(Face::ConstEdgeIterator it(face->edges()); !it.isDone(); it.advance())
+ {
+ uint v = it.current()->vertex->id;
+ builder.addVertex(v, v, v);
+ }
+
+ builder.endPolygon();
+ }
+
+ builder.done();
+
+ return builder.buildQuadTriMesh();
+}
+
+
+// Triangulate in place.
+void Mesh::triangulate() {
+
+ bool all_triangles = true;
+
+ const uint faceCount = m_faceArray.count();
+ for (uint f = 0; f < faceCount; f++) {
+ Face * face = m_faceArray[f];
+ if (face->edgeCount() != 3) {
+ all_triangles = false;
+ break;
+ }
+ }
+
+ if (all_triangles) {
+ return;
+ }
+
+
+ // Do not touch vertices, but rebuild edges and faces.
+ Array<Edge *> edgeArray;
+ Array<Face *> faceArray;
+
+ swap(edgeArray, m_edgeArray);
+ swap(faceArray, m_faceArray);
+ m_edgeMap.clear();
+
+ for (uint f = 0; f < faceCount; f++) {
+ Face * face = faceArray[f];
+
+ // Trivial fan-like triangulation.
+ const uint v0 = face->edge->vertex->id;
+ uint v2, v1 = -1;
+
+ for (Face::EdgeIterator it(face->edges()); !it.isDone(); it.advance()) {
+ Edge * edge = it.current();
+ v2 = edge->to()->id;
+ if (v2 == v0) break;
+ if (v1 != -1) addFace(v0, v1, v2);
+ v1 = v2;
+ }
+ }
+
+ nvDebugCheck(m_faceArray.count() > faceCount); // triangle count > face count
+
+ linkBoundary();
+
+ deleteAll(edgeArray);
+ deleteAll(faceArray);
+}
+
+
+/*
+Fixing T-junctions.
+
+- Find T-junctions. Find vertices that are on an edge.
+ - This test is approximate.
+ - Insert edges on a spatial index to speedup queries.
+ - Consider only open edges, that is edges that have no pairs.
+ - Consider only vertices on boundaries.
+- Close T-junction.
+ - Split edge.
+
+*/
+bool Mesh::splitBoundaryEdges() {
+
+ Array<Vertex *> boundaryVertices;
+
+ foreach(i, m_vertexArray) {
+ Vertex * v = m_vertexArray[i];
+ if (v->isBoundary()) {
+ boundaryVertices.append(v);
+ }
+ }
+
+ nvDebug("Fixing T-junctions:\n");
+
+ int splitCount = 0;
+
+ foreach(v, boundaryVertices) {
+ Vertex * vertex = boundaryVertices[v];
+
+ Vector3 x0 = vertex->pos;
+
+ // Find edges that this vertex overlaps with.
+ foreach(e, m_edgeArray) {
+ //for (uint e = 0; e < m_edgeArray.count(); e++) {
+ Edge * edge = m_edgeArray[e];
+ if (edge != NULL && edge->isBoundary()) {
+
+ if (edge->from() == vertex || edge->to() == vertex) {
+ continue;
+ }
+
+ Vector3 x1 = edge->from()->pos;
+ Vector3 x2 = edge->to()->pos;
+
+ Vector3 v01 = x0 - x1;
+ Vector3 v21 = x2 - x1;
+
+ float l = length(v21);
+ float d = length(cross(v01, v21)) / l;
+
+ if (isZero(d)) {
+ float t = dot(v01, v21) / (l * l);
+
+ // @@ Snap x0 to x1 or x2, if too close? No, do vertex snapping elsewhere.
+ /*if (equal(t, 0.0f, 0.01f)) {
+ //vertex->setPos(x1);
+ }
+ else if (equal(t, 1.0f, 0.01f)) {
+ //vertex->setPos(x2);
+ }
+ else*/
+ if (t > 0.0f + NV_EPSILON && t < 1.0f - NV_EPSILON) {
+ nvDebugCheck(equal(lerp(x1, x2, t), x0));
+
+ Vertex * splitVertex = splitBoundaryEdge(edge, t, x0);
+ vertex->linkColocal(splitVertex); // @@ Should we do this here?
+ splitCount++;
+ }
+ }
+ }
+ }
+ }
+
+ nvDebug(" - %d edges split.\n", splitCount);
+
+ nvDebugCheck(isValid());
+
+ return splitCount != 0;
+}
+
+
+// For this to be effective, we have to fix the boundary junctions first.
+Edge * Mesh::sewBoundary(Edge * startEdge) {
+ nvDebugCheck(startEdge->face == NULL);
+
+ // @@ We may want to be more conservative linking colocals in order to preserve the input topology. One way of doing that is by linking colocals only
+ // if the vertices next to them are linked as well. That is, by sewing boundaries after detecting them. If any pair of consecutive edges have their first
+ // and last vertex in the same position, then it can be linked.
+
+ Edge * lastBoundarySeen = startEdge;
+
+ nvDebug("Sewing Boundary:\n");
+
+ int count = 0;
+ int sewnCount = 0;
+
+ Edge * edge = startEdge;
+ do {
+ nvDebugCheck(edge->face == NULL);
+
+ Edge * edge_a = edge;
+ Edge * edge_b = edge->prev;
+
+ Edge * pair_a = edge_a->pair;
+ Edge * pair_b = edge_b->pair;
+
+ Vertex * v0a = edge_a->to();
+ Vertex * v0b = edge_b->from();
+ Vertex * v1a = edge_a->from();
+ Vertex * v1b = edge_b->to();
+
+ nvDebugCheck(v1a->isColocal(v1b));
+
+ /*
+ v0b + _+ v0a
+ \ /
+ b \ / a
+ \|/
+ v1b + v1a
+ */
+
+ // @@ This should not happen while sewing, but it may be produced somewhere else.
+ nvDebugCheck(edge_a != edge_b);
+
+ if (v0a->pos == v0b->pos) {
+
+ // Link vertices.
+ v0a->linkColocal(v0b);
+
+ // Remove edges to be collapsed.
+ disconnect(edge_a);
+ disconnect(edge_b);
+ disconnect(pair_a);
+ disconnect(pair_b);
+
+ // Link new boundary edges.
+ Edge * prevBoundary = edge_b->prev;
+ Edge * nextBoundary = edge_a->next;
+ if (nextBoundary != NULL) {
+ nvDebugCheck(nextBoundary->face == NULL);
+ nvDebugCheck(prevBoundary->face == NULL);
+ nextBoundary->setPrev(prevBoundary);
+
+ // Make sure boundary vertex points to boundary edge.
+ v0a->setEdge(nextBoundary); // This updates all colocals.
+ }
+ lastBoundarySeen = prevBoundary;
+
+ // Creat new edge.
+ Edge * newEdge_a = addEdge(v0a->id, v1a->id); // pair_a->from()->id, pair_a->to()->id
+ Edge * newEdge_b = addEdge(v1b->id, v0b->id);
+
+ newEdge_a->pair = newEdge_b;
+ newEdge_b->pair = newEdge_a;
+
+ newEdge_a->face = pair_a->face;
+ newEdge_b->face = pair_b->face;
+
+ newEdge_a->setNext(pair_a->next);
+ newEdge_a->setPrev(pair_a->prev);
+
+ newEdge_b->setNext(pair_b->next);
+ newEdge_b->setPrev(pair_b->prev);
+
+ delete edge_a;
+ delete edge_b;
+ delete pair_a;
+ delete pair_b;
+
+ edge = nextBoundary; // If nextBoundary is NULL we have closed the loop.
+ sewnCount++;
+ }
+ else {
+ edge = edge->next;
+ }
+
+ count++;
+ } while(edge != NULL && edge != lastBoundarySeen);
+
+ nvDebug(" - Sewn %d out of %d.\n", sewnCount, count);
+
+ if (lastBoundarySeen != NULL) {
+ nvDebugCheck(lastBoundarySeen->face == NULL);
+ }
+
+ return lastBoundarySeen;
+}
+
+
+// @@ We must always disconnect edge pairs simultaneously.
+void Mesh::disconnect(Edge * edge) {
+ nvDebugCheck(edge != NULL);
+
+ // Remove from edge list.
+ if ((edge->id & 1) == 0) {
+ nvDebugCheck(m_edgeArray[edge->id / 2] == edge);
+ m_edgeArray[edge->id / 2] = NULL;
+ }
+
+ // Remove edge from map. @@ Store map key inside edge?
+ nvDebugCheck(edge->from() != NULL && edge->to() != NULL);
+ bool removed = m_edgeMap.remove(Key(edge->from()->id, edge->to()->id));
+ nvDebugCheck(removed == true);
+
+ // Disconnect from vertex.
+ if (edge->vertex != NULL) {
+ if (edge->vertex->edge == edge) {
+ if (edge->prev && edge->prev->pair) {
+ edge->vertex->edge = edge->prev->pair;
+ }
+ else if (edge->pair && edge->pair->next) {
+ edge->vertex->edge = edge->pair->next;
+ }
+ else {
+ edge->vertex->edge = NULL;
+ // @@ Remove disconnected vertex?
+ }
+ }
+ //edge->setVertex(NULL);
+ }
+
+ // Disconnect from face.
+ if (edge->face != NULL) {
+ if (edge->face->edge == edge) {
+ if (edge->next != NULL && edge->next != edge) {
+ edge->face->edge = edge->next;
+ }
+ else if (edge->prev != NULL && edge->prev != edge) {
+ edge->face->edge = edge->prev;
+ }
+ else {
+ edge->face->edge = NULL;
+ // @@ Remove disconnected face?
+ }
+ }
+ //edge->setFace(NULL);
+ }
+
+ // @@ Hack, we don't disconnect from pair, because pair needs us to remove itself from the map.
+ // Disconect from pair.
+ /*if (edge->pair != NULL) {
+ if (edge->pair->pair == edge) {
+ edge->pair->setPair(NULL);
+ }
+ //edge->setPair(NULL);
+ }*/
+
+ // Disconnect from previous.
+ if (edge->prev) {
+ if (edge->prev->next == edge) {
+ edge->prev->setNext(NULL);
+ }
+ //edge->setPrev(NULL);
+ }
+
+ // Disconnect from next.
+ if (edge->next) {
+ if (edge->next->prev == edge) {
+ edge->next->setPrev(NULL);
+ }
+ //edge->setNext(NULL);
+ }
+}
+
+
+void Mesh::remove(Edge * edge) {
+ nvDebugCheck(edge != NULL);
+
+ disconnect(edge);
+
+ delete edge;
+}
+
+void Mesh::remove(Vertex * vertex) {
+ nvDebugCheck(vertex != NULL);
+
+ // Remove from vertex list.
+ m_vertexArray[vertex->id] = NULL;
+
+ // Disconnect from colocals.
+ vertex->unlinkColocal();
+
+ // Disconnect from edges.
+ if (vertex->edge != NULL) {
+ // @@ Removing a connected vertex is asking for trouble...
+ if (vertex->edge->vertex == vertex) {
+ // @@ Connect edge to a colocal?
+ vertex->edge->vertex = NULL;
+ }
+
+ vertex->setEdge(NULL);
+ }
+
+ delete vertex;
+}
+
+void Mesh::remove(Face * face) {
+ nvDebugCheck(face != NULL);
+
+ // Remove from face list.
+ m_faceArray[face->id] = NULL;
+
+ // Disconnect from edges.
+ if (face->edge != NULL) {
+ nvDebugCheck(face->edge->face == face);
+
+ face->edge->face = NULL;
+
+ face->edge = NULL;
+ }
+
+ delete face;
+}
+
+
+void Mesh::compactEdges() {
+ const uint edgeCount = m_edgeArray.count();
+
+ uint c = 0;
+ for (uint i = 0; i < edgeCount; i++) {
+ if (m_edgeArray[i] != NULL) {
+ if (i != c) {
+ m_edgeArray[c] = m_edgeArray[i];
+ m_edgeArray[c]->id = 2 * c;
+ if (m_edgeArray[c]->pair != NULL) {
+ m_edgeArray[c]->pair->id = 2 * c + 1;
+ }
+ }
+ c++;
+ }
+ }
+
+ m_edgeArray.resize(c);
+}
+
+
+void Mesh::compactVertices() {
+ const uint vertexCount = m_vertexArray.count();
+
+ uint c = 0;
+ for (uint i = 0; i < vertexCount; i++) {
+ if (m_vertexArray[i] != NULL) {
+ if (i != c) {
+ m_vertexArray[c] = m_vertexArray[i];
+ m_vertexArray[c]->id = c;
+ }
+ c++;
+ }
+ }
+
+ m_vertexArray.resize(c);
+
+ // @@ Generate xref array for external attributes.
+}
+
+
+void Mesh::compactFaces() {
+ const uint faceCount = m_faceArray.count();
+
+ uint c = 0;
+ for (uint i = 0; i < faceCount; i++) {
+ if (m_faceArray[i] != NULL) {
+ if (i != c) {
+ m_faceArray[c] = m_faceArray[i];
+ m_faceArray[c]->id = c;
+ }
+ c++;
+ }
+ }
+
+ m_faceArray.resize(c);
+}
+
+
+Vertex * Mesh::splitBoundaryEdge(Edge * edge, float t, const Vector3 & pos) {
+
+ /*
+ We want to go from this configuration:
+
+ + +
+ | ^
+ edge |<->| pair
+ v |
+ + +
+
+ To this one:
+
+ + +
+ | ^
+ e0 |<->| p0
+ v |
+ vertex + +
+ | ^
+ e1 |<->| p1
+ v |
+ + +
+
+ */
+
+
+ Edge * pair = edge->pair;
+
+ // Make sure boundaries are linked.
+ nvDebugCheck(pair != NULL);
+
+ // Make sure edge is a boundary edge.
+ nvDebugCheck(pair->face == NULL);
+
+ // Add new vertex.
+ Vertex * vertex = addVertex(pos);
+ vertex->nor = lerp(edge->from()->nor, edge->to()->nor, t);
+ vertex->tex = lerp(edge->from()->tex, edge->to()->tex, t);
+ vertex->col = lerp(edge->from()->col, edge->to()->col, t);
+
+ disconnect(edge);
+ disconnect(pair);
+
+ // Add edges.
+ Edge * e0 = addEdge(edge->from()->id, vertex->id);
+ Edge * p0 = addEdge(vertex->id, pair->to()->id);
+
+ Edge * e1 = addEdge(vertex->id, edge->to()->id);
+ Edge * p1 = addEdge(pair->from()->id, vertex->id);
+
+ // Link edges.
+ e0->setNext(e1);
+ p1->setNext(p0);
+
+ e0->setPrev(edge->prev);
+ e1->setNext(edge->next);
+
+ p1->setPrev(pair->prev);
+ p0->setNext(pair->next);
+
+ nvDebugCheck(e0->next == e1);
+ nvDebugCheck(e1->prev == e0);
+
+ nvDebugCheck(p1->next == p0);
+ nvDebugCheck(p0->prev == p1);
+
+ nvDebugCheck(p0->pair == e0);
+ nvDebugCheck(e0->pair == p0);
+
+ nvDebugCheck(p1->pair == e1);
+ nvDebugCheck(e1->pair == p1);
+
+ // Link faces.
+ e0->face = edge->face;
+ e1->face = edge->face;
+
+ // Link vertices.
+ edge->from()->setEdge(e0);
+ vertex->setEdge(e1);
+
+ delete edge;
+ delete pair;
+
+ return vertex;
+}
+
+#if 0
+// Without introducing new vertices.
+void Mesh::splitBoundaryEdge(Edge * edge, Vertex * vertex) {
+
+ /*
+ We want to go from this configuration:
+
+ | | pn
+ + +
+ | ^
+ | |
+ edge |<->| pair
+ | |
+ v |
+ + +
+ | | pp
+
+ To this one:
+ \ /
+ \ /
+ + +
+ | ^
+ e0 |<->| p0
+ v |
+ vertex + +
+ | ^
+ e1 |<->| p1
+ v |
+ + +
+ / \
+ / \
+ */
+
+
+ Edge * pair = edge->pair;
+ Edge * pn = pair->next();
+ Edge * pp = pair->prev();
+
+ // Make sure boundaries are linked.
+ nvDebugCheck(pair != NULL);
+
+ // Make sure edge is a boundary edge.
+ nvDebugCheck(pair->face() == NULL);
+
+ nvDebugCheck(edge->isValid());
+ nvDebugCheck(pair->isValid());
+
+ disconnect(edge);
+ disconnect(pair);
+
+ // Add edges.
+ Edge * e0 = addEdge(edge->from()->id(), vertex->id());
+ Edge * e1 = addEdge(vertex->id(), edge->to()->id());
+
+ // Link faces.
+ e0->setFace(edge->face());
+ e1->setFace(edge->face());
+
+ // Link pairs.
+ Edge * p0 = findEdge(vertex->id(), pair->to()->id());
+ if (p0 == NULL) {
+ p0 = addEdge(vertex->id(), pair->to()->id());
+ pn->setPrev(p0);
+ }
+ else {
+ nvDebugCheck(p0->face() != NULL);
+ if (e0->prev() != NULL) {
+ pn->setPrev(e0->prev());
+ }
+ else {
+ nvDebugCheck(pn == e0);
+ }
+ }
+
+ Edge * p1 = findEdge(pair->from()->id(), vertex->id());
+ if (p1 == NULL) {
+ p1 = addEdge(pair->from()->id(), vertex->id());
+ pp->setNext(p1);
+ }
+ else {
+ nvDebugCheck(p1->face() != NULL);
+ if (e1->next() != NULL) {
+ pp->setPrev(e1->next());
+ }
+ else {
+ nvDebugCheck(pp == e1);
+ }
+ }
+
+ // Link edges.
+ e0->setNext(e1); // e1->setPrev(e0)
+
+ if (p0->face() == p1->face()) { // can be null
+ p1->setNext(p0); // p0->setPrev(p1)
+ }
+ else {
+ //if (p1->face() == NULL) p1->setNext(
+ }
+
+
+ e0->setPrev(edge->prev());
+ e1->setNext(edge->next());
+
+ nvDebugCheck(e0->pair == p0);
+ nvDebugCheck(e1->pair == p1);
+ nvDebugCheck(p0->pair == e0);
+ nvDebugCheck(p1->pair == e1);
+
+ nvDebugCheck(e0->isValid());
+ nvDebugCheck(e1->isValid());
+ nvDebugCheck(pp->isValid());
+ nvDebugCheck(pn->isValid());
+
+ nvDebugCheck(e0->pair->isValid());
+ nvDebugCheck(e1->pair->isValid());
+ nvDebugCheck(pp->pair->isValid());
+ nvDebugCheck(pn->pair->isValid());
+
+ nvDebugCheck(edge->face->isValid());
+
+ if (pn->pair->face != NULL) {
+ nvDebugCheck(pn->pair->face->isValid());
+ }
+
+ if (pp->pair->face() != NULL) {
+ nvDebugCheck(pn->pair->face->isValid());
+ }
+
+ if (p0->face != NULL) {
+ nvDebugCheck(p0->face->isValid());
+ }
+
+ if (p1->face() != NULL) {
+ nvDebugCheck(p1->face()->isValid());
+ }
+
+ nvDebugCheck(isValid()); // Only for extreme debugging.
+
+ // Link vertices.
+ edge->from()->setEdge(e0);
+ vertex->setEdge(p0);
+
+ delete edge;
+ delete pair;
+}
+#endif
+
+bool Mesh::isValid() const
+{
+ // Make sure all edges are valid.
+ const uint edgeCount = m_edgeArray.count();
+ for (uint e = 0; e < edgeCount; e++) {
+ Edge * edge = m_edgeArray[e];
+ if (edge != NULL) {
+ if (edge->id != 2*e) {
+ return false;
+ }
+ if (!edge->isValid()) {
+ return false;
+ }
+
+ if (edge->pair->id != 2*e+1) {
+ return false;
+ }
+ if (!edge->pair->isValid()) {
+ return false;
+ }
+ }
+ }
+
+ // @@ Make sure all faces are valid.
+
+ // @@ Make sure all vertices are valid.
+
+ return true;
+}
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.h b/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.h
new file mode 100644
index 0000000000..c202c2ef9a
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.h
@@ -0,0 +1,274 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#pragma once
+#ifndef NV_MESH_HALFEDGE_MESH_H
+#define NV_MESH_HALFEDGE_MESH_H
+
+#include "nvmesh/nvmesh.h"
+#include "nvcore/Array.h"
+#include "nvcore/HashMap.h"
+
+/*
+If I were to redo this again, there are a number of things that I would do differently.
+- Edge map is only useful when importing a mesh to guarantee the result is two-manifold. However, when manipulating the mesh
+ it's a pain to maintain the map up to date.
+- Edge array only points to the even vertices. There's no good reason for that. The map becomes required to traverse all edges
+ or you have to make sure edges are properly paired.
+- Linked boundaries. It's cleaner to assume a NULL pair means a boundary edge. Makes easier to seal boundaries. The only reason
+ why we link boundaries is to simplify traversal, but that could be done with two helper functions (nextBoundary, prevBoundary).
+- Minimize the amount of state that needs to be set in a certain way:
+ - boundary vertices point to boundary edge.
+- Remove parenthesis! Make some members public.
+- Remove member functions with side effects:
+ - e->setNext(n) modifies e->next and n->prev, instead use "link(e, n)", or "e->next = n, n->prev = e"
+*/
+
+
+namespace nv
+{
+ class Vector3;
+ class TriMesh;
+ class QuadTriMesh;
+ //template <typename T> struct Hash<Mesh::Key>;
+
+ namespace HalfEdge
+ {
+ class Edge;
+ class Face;
+ class Vertex;
+
+ /// Simple half edge mesh designed for dynamic mesh manipulation.
+ class Mesh
+ {
+ public:
+
+ Mesh();
+ Mesh(const Mesh * mesh);
+ ~Mesh();
+
+ void clear();
+
+ Vertex * addVertex(const Vector3 & pos);
+ //Vertex * addVertex(uint id, const Vector3 & pos);
+ //void addVertices(const Mesh * mesh);
+
+ void linkColocals();
+ void linkColocalsWithCanonicalMap(const Array<uint> & canonicalMap);
+ void resetColocalLinks();
+
+ Face * addFace();
+ Face * addFace(uint v0, uint v1, uint v2);
+ Face * addFace(uint v0, uint v1, uint v2, uint v3);
+ Face * addFace(const Array<uint> & indexArray);
+ Face * addFace(const Array<uint> & indexArray, uint first, uint num);
+ //void addFaces(const Mesh * mesh);
+
+ // These functions disconnect the given element from the mesh and delete it.
+ void disconnect(Edge * edge);
+ void disconnectPair(Edge * edge);
+ void disconnect(Vertex * vertex);
+ void disconnect(Face * face);
+
+ void remove(Edge * edge);
+ void remove(Vertex * vertex);
+ void remove(Face * face);
+
+ // Remove holes from arrays and reassign indices.
+ void compactEdges();
+ void compactVertices();
+ void compactFaces();
+
+ void triangulate();
+
+ void linkBoundary();
+
+ bool splitBoundaryEdges(); // Returns true if any split was made.
+
+ // Sew the boundary that starts at the given edge, returns one edge that still belongs to boundary, or NULL if boundary closed.
+ HalfEdge::Edge * sewBoundary(Edge * startEdge);
+
+
+ // Vertices
+ uint vertexCount() const { return m_vertexArray.count(); }
+ const Vertex * vertexAt(int i) const { return m_vertexArray[i]; }
+ Vertex * vertexAt(int i) { return m_vertexArray[i]; }
+
+ uint colocalVertexCount() const { return m_colocalVertexCount; }
+
+ // Faces
+ uint faceCount() const { return m_faceArray.count(); }
+ const Face * faceAt(int i) const { return m_faceArray[i]; }
+ Face * faceAt(int i) { return m_faceArray[i]; }
+
+ // Edges
+ uint edgeCount() const { return m_edgeArray.count(); }
+ const Edge * edgeAt(int i) const { return m_edgeArray[i]; }
+ Edge * edgeAt(int i) { return m_edgeArray[i]; }
+
+ class ConstVertexIterator;
+
+ class VertexIterator
+ {
+ friend class ConstVertexIterator;
+ public:
+ VertexIterator(Mesh * mesh) : m_mesh(mesh), m_current(0) { }
+
+ virtual void advance() { m_current++; }
+ virtual bool isDone() const { return m_current == m_mesh->vertexCount(); }
+ virtual Vertex * current() const { return m_mesh->vertexAt(m_current); }
+
+ private:
+ HalfEdge::Mesh * m_mesh;
+ uint m_current;
+ };
+ VertexIterator vertices() { return VertexIterator(this); }
+
+ class ConstVertexIterator
+ {
+ public:
+ ConstVertexIterator(const Mesh * mesh) : m_mesh(mesh), m_current(0) { }
+ ConstVertexIterator(class VertexIterator & it) : m_mesh(it.m_mesh), m_current(it.m_current) { }
+
+ virtual void advance() { m_current++; }
+ virtual bool isDone() const { return m_current == m_mesh->vertexCount(); }
+ virtual const Vertex * current() const { return m_mesh->vertexAt(m_current); }
+
+ private:
+ const HalfEdge::Mesh * m_mesh;
+ uint m_current;
+ };
+ ConstVertexIterator vertices() const { return ConstVertexIterator(this); }
+
+ class ConstFaceIterator;
+
+ class FaceIterator
+ {
+ friend class ConstFaceIterator;
+ public:
+ FaceIterator(Mesh * mesh) : m_mesh(mesh), m_current(0) { }
+
+ virtual void advance() { m_current++; }
+ virtual bool isDone() const { return m_current == m_mesh->faceCount(); }
+ virtual Face * current() const { return m_mesh->faceAt(m_current); }
+
+ private:
+ HalfEdge::Mesh * m_mesh;
+ uint m_current;
+ };
+ FaceIterator faces() { return FaceIterator(this); }
+
+ class ConstFaceIterator
+ {
+ public:
+ ConstFaceIterator(const Mesh * mesh) : m_mesh(mesh), m_current(0) { }
+ ConstFaceIterator(const FaceIterator & it) : m_mesh(it.m_mesh), m_current(it.m_current) { }
+
+ virtual void advance() { m_current++; }
+ virtual bool isDone() const { return m_current == m_mesh->faceCount(); }
+ virtual const Face * current() const { return m_mesh->faceAt(m_current); }
+
+ private:
+ const HalfEdge::Mesh * m_mesh;
+ uint m_current;
+ };
+ ConstFaceIterator faces() const { return ConstFaceIterator(this); }
+
+ class ConstEdgeIterator;
+
+ class EdgeIterator
+ {
+ friend class ConstEdgeIterator;
+ public:
+ EdgeIterator(Mesh * mesh) : m_mesh(mesh), m_current(0) { }
+
+ virtual void advance() { m_current++; }
+ virtual bool isDone() const { return m_current == m_mesh->edgeCount(); }
+ virtual Edge * current() const { return m_mesh->edgeAt(m_current); }
+
+ private:
+ HalfEdge::Mesh * m_mesh;
+ uint m_current;
+ };
+ EdgeIterator edges() { return EdgeIterator(this); }
+
+ class ConstEdgeIterator
+ {
+ public:
+ ConstEdgeIterator(const Mesh * mesh) : m_mesh(mesh), m_current(0) { }
+ ConstEdgeIterator(const EdgeIterator & it) : m_mesh(it.m_mesh), m_current(it.m_current) { }
+
+ virtual void advance() { m_current++; }
+ virtual bool isDone() const { return m_current == m_mesh->edgeCount(); }
+ virtual const Edge * current() const { return m_mesh->edgeAt(m_current); }
+
+ private:
+ const HalfEdge::Mesh * m_mesh;
+ uint m_current;
+ };
+ ConstEdgeIterator edges() const { return ConstEdgeIterator(this); }
+
+ // @@ Add half-edge iterator.
+
+
+
+ // Convert to tri mesh.
+ TriMesh * toTriMesh() const;
+ QuadTriMesh * toQuadTriMesh() const;
+
+ bool isValid() const;
+
+ public:
+
+ // Error status:
+ mutable uint errorCount;
+ mutable uint errorIndex0;
+ mutable uint errorIndex1;
+
+ private:
+
+ bool canAddFace(const Array<uint> & indexArray, uint first, uint num) const;
+ bool canAddEdge(uint i, uint j) const;
+ Edge * addEdge(uint i, uint j);
+
+ Edge * findEdge(uint i, uint j) const;
+
+ void linkBoundaryEdge(Edge * edge);
+ Vertex * splitBoundaryEdge(Edge * edge, float t, const Vector3 & pos);
+ void splitBoundaryEdge(Edge * edge, Vertex * vertex);
+
+ private:
+
+ Array<Vertex *> m_vertexArray;
+ Array<Edge *> m_edgeArray;
+ Array<Face *> m_faceArray;
+
+ struct Key {
+ Key() {}
+ Key(const Key & k) : p0(k.p0), p1(k.p1) {}
+ Key(uint v0, uint v1) : p0(v0), p1(v1) {}
+ void operator=(const Key & k) { p0 = k.p0; p1 = k.p1; }
+ bool operator==(const Key & k) const { return p0 == k.p0 && p1 == k.p1; }
+
+ uint p0;
+ uint p1;
+ };
+ friend struct Hash<Mesh::Key>;
+
+ HashMap<Key, Edge *> m_edgeMap;
+
+ uint m_colocalVertexCount;
+
+ };
+ /*
+ // This is a much better hash than the default and greatly improves performance!
+ template <> struct hash<Mesh::Key>
+ {
+ uint operator()(const Mesh::Key & k) const { return k.p0 + k.p1; }
+ };
+ */
+
+ } // HalfEdge namespace
+
+} // nv namespace
+
+#endif // NV_MESH_HALFEDGE_MESH_H
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.cpp b/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.cpp
new file mode 100644
index 0000000000..66dad69f8a
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.cpp
@@ -0,0 +1,94 @@
+// This code is in the public domain -- castano@gmail.com
+
+#include "nvmesh.h" // pch
+
+#include "Vertex.h"
+
+#include "nvmath/Vector.inl"
+
+using namespace nv;
+using namespace HalfEdge;
+
+
+// Set first edge of all colocals.
+void Vertex::setEdge(Edge * e)
+{
+ for (VertexIterator it(colocals()); !it.isDone(); it.advance()) {
+ it.current()->edge = e;
+ }
+}
+
+// Update position of all colocals.
+void Vertex::setPos(const Vector3 & p)
+{
+ for (VertexIterator it(colocals()); !it.isDone(); it.advance()) {
+ it.current()->pos = p;
+ }
+}
+
+
+uint HalfEdge::Vertex::colocalCount() const
+{
+ uint count = 0;
+ for (ConstVertexIterator it(colocals()); !it.isDone(); it.advance()) { ++count; }
+ return count;
+}
+
+uint HalfEdge::Vertex::valence() const
+{
+ uint count = 0;
+ for (ConstEdgeIterator it(edges()); !it.isDone(); it.advance()) { ++count; }
+ return count;
+}
+
+const HalfEdge::Vertex * HalfEdge::Vertex::firstColocal() const
+{
+ uint firstId = id;
+ const Vertex * vertex = this;
+
+ for (ConstVertexIterator it(colocals()); !it.isDone(); it.advance())
+ {
+ if (it.current()->id < firstId) {
+ firstId = vertex->id;
+ vertex = it.current();
+ }
+ }
+
+ return vertex;
+}
+
+HalfEdge::Vertex * HalfEdge::Vertex::firstColocal()
+{
+ Vertex * vertex = this;
+ uint firstId = id;
+
+ for (VertexIterator it(colocals()); !it.isDone(); it.advance())
+ {
+ if (it.current()->id < firstId) {
+ firstId = vertex->id;
+ vertex = it.current();
+ }
+ }
+
+ return vertex;
+}
+
+bool HalfEdge::Vertex::isFirstColocal() const
+{
+ return firstColocal() == this;
+}
+
+bool HalfEdge::Vertex::isColocal(const Vertex * v) const {
+ if (this == v) return true;
+ if (pos != v->pos) return false;
+
+ for (ConstVertexIterator it(colocals()); !it.isDone(); it.advance())
+ {
+ if (v == it.current()) {
+ return true;
+ }
+ }
+
+ return false;
+}
+
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.h b/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.h
new file mode 100644
index 0000000000..1c5c8d7141
--- /dev/null
+++ b/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.h
@@ -0,0 +1,221 @@
+// This code is in the public domain -- castanyo@yahoo.es
+
+#pragma once
+#ifndef NV_MESH_HALFEDGE_VERTEX_H
+#define NV_MESH_HALFEDGE_VERTEX_H
+
+#include "nvmesh/halfedge/Edge.h"
+
+namespace nv
+{
+ namespace HalfEdge { class Vertex; class Face; class Edge; }
+
+ // Half edge vertex.
+ class HalfEdge::Vertex
+ {
+ NV_FORBID_COPY(Vertex);
+ public:
+
+ uint id;
+
+ Edge * edge;
+ Vertex * next;
+ Vertex * prev;
+
+ Vector3 pos;
+ Vector3 nor;
+ Vector2 tex;
+ Vector4 col;
+
+
+ Vertex(uint id) : id(id), edge(NULL), pos(0.0f), nor(0.0f), tex(0.0f), col(0.0f) {
+ next = this;
+ prev = this;
+ }
+
+
+ void setEdge(Edge * e);
+ void setPos(const Vector3 & p);
+
+ uint colocalCount() const;
+ uint valence() const;
+ bool isFirstColocal() const;
+ const Vertex * firstColocal() const;
+ Vertex * firstColocal();
+
+ bool isColocal(const Vertex * v) const;
+
+
+ void linkColocal(Vertex * v) {
+ next->prev = v;
+ v->next = next;
+ next = v;
+ v->prev = this;
+ }
+ void unlinkColocal() {
+ next->prev = prev;
+ prev->next = next;
+ next = this;
+ prev = this;
+ }
+
+
+ // @@ Note: This only works if linkBoundary has been called.
+ bool isBoundary() const {
+ return (edge && !edge->face);
+ }
+
+
+ // for(EdgeIterator it(iterator()); !it.isDone(); it.advance()) { ... }
+ //
+ // EdgeIterator it(iterator());
+ // while(!it.isDone()) {
+ // ...
+ // id.advance();
+ // }
+
+ // Iterator that visits the edges around this vertex in counterclockwise order.
+ class EdgeIterator //: public Iterator<Edge *>
+ {
+ public:
+ EdgeIterator(Edge * e) : m_end(NULL), m_current(e) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->pair->next;
+ //m_current = m_current->prev->pair;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual Edge * current() const { return m_current; }
+ Vertex * vertex() const { return m_current->vertex; }
+
+ private:
+ Edge * m_end;
+ Edge * m_current;
+ };
+
+ EdgeIterator edges() { return EdgeIterator(edge); }
+ EdgeIterator edges(Edge * e) { return EdgeIterator(e); }
+
+ // Iterator that visits the edges around this vertex in counterclockwise order.
+ class ConstEdgeIterator //: public Iterator<Edge *>
+ {
+ public:
+ ConstEdgeIterator(const Edge * e) : m_end(NULL), m_current(e) { }
+ ConstEdgeIterator(EdgeIterator it) : m_end(NULL), m_current(it.current()) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->pair->next;
+ //m_current = m_current->prev->pair;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual const Edge * current() const { return m_current; }
+ const Vertex * vertex() const { return m_current->to(); }
+
+ private:
+ const Edge * m_end;
+ const Edge * m_current;
+ };
+
+ ConstEdgeIterator edges() const { return ConstEdgeIterator(edge); }
+ ConstEdgeIterator edges(const Edge * e) const { return ConstEdgeIterator(e); }
+
+
+ // Iterator that visits the edges around this vertex in counterclockwise order.
+ class ReverseEdgeIterator //: public Iterator<Edge *>
+ {
+ public:
+ ReverseEdgeIterator(Edge * e) : m_end(NULL), m_current(e) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->prev->pair;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual Edge * current() const { return m_current; }
+ Vertex * vertex() const { return m_current->vertex; }
+
+ private:
+ Edge * m_end;
+ Edge * m_current;
+ };
+
+ // Iterator that visits the edges around this vertex in counterclockwise order.
+ class ReverseConstEdgeIterator //: public Iterator<Edge *>
+ {
+ public:
+ ReverseConstEdgeIterator(const Edge * e) : m_end(NULL), m_current(e) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->prev->pair;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual const Edge * current() const { return m_current; }
+ const Vertex * vertex() const { return m_current->to(); }
+
+ private:
+ const Edge * m_end;
+ const Edge * m_current;
+ };
+
+
+
+ // Iterator that visits all the colocal vertices.
+ class VertexIterator //: public Iterator<Edge *>
+ {
+ public:
+ VertexIterator(Vertex * v) : m_end(NULL), m_current(v) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->next;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual Vertex * current() const { return m_current; }
+
+ private:
+ Vertex * m_end;
+ Vertex * m_current;
+ };
+
+ VertexIterator colocals() { return VertexIterator(this); }
+
+ // Iterator that visits all the colocal vertices.
+ class ConstVertexIterator //: public Iterator<Edge *>
+ {
+ public:
+ ConstVertexIterator(const Vertex * v) : m_end(NULL), m_current(v) { }
+
+ virtual void advance()
+ {
+ if (m_end == NULL) m_end = m_current;
+ m_current = m_current->next;
+ }
+
+ virtual bool isDone() const { return m_end == m_current; }
+ virtual const Vertex * current() const { return m_current; }
+
+ private:
+ const Vertex * m_end;
+ const Vertex * m_current;
+ };
+
+ ConstVertexIterator colocals() const { return ConstVertexIterator(this); }
+
+ };
+
+} // nv namespace
+
+#endif // NV_MESH_HALFEDGE_VERTEX_H
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 05:18:02 +0000