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, 0 insertions, 2374 deletions
diff --git a/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp b/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp
deleted file mode 100644
index 671650296c..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.cpp
+++ /dev/null
@@ -1,57 +0,0 @@
-// 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
deleted file mode 100644
index 25c47f4860..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Edge.h
+++ /dev/null
@@ -1,70 +0,0 @@
-// 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
deleted file mode 100644
index 9f6987154e..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Face.cpp
+++ /dev/null
@@ -1,268 +0,0 @@
-// 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
deleted file mode 100644
index 677f8666f0..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Face.h
+++ /dev/null
@@ -1,106 +0,0 @@
-// 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
deleted file mode 100644
index 0012513bce..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.cpp
+++ /dev/null
@@ -1,1284 +0,0 @@
-// 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
deleted file mode 100644
index c202c2ef9a..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Mesh.h
+++ /dev/null
@@ -1,274 +0,0 @@
-// 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
deleted file mode 100644
index 66dad69f8a..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.cpp
+++ /dev/null
@@ -1,94 +0,0 @@
-// 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
deleted file mode 100644
index 1c5c8d7141..0000000000
--- a/thirdparty/thekla_atlas/nvmesh/halfedge/Vertex.h
+++ /dev/null
@@ -1,221 +0,0 @@
-// 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-12-16 14:47:13 +0000