diff options
Diffstat (limited to 'intern/decimation/intern/LOD_ManMesh2.cpp')
| -rw-r--r-- | intern/decimation/intern/LOD_ManMesh2.cpp | 617 |
1 files changed, 617 insertions, 0 deletions
diff --git a/intern/decimation/intern/LOD_ManMesh2.cpp b/intern/decimation/intern/LOD_ManMesh2.cpp new file mode 100644 index 00000000000..f0bf40f577c --- /dev/null +++ b/intern/decimation/intern/LOD_ManMesh2.cpp @@ -0,0 +1,617 @@ +/** + * $Id$ + * ***** BEGIN GPL/BL DUAL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. The Blender + * Foundation also sells licenses for use in proprietary software under + * the Blender License. See http://www.blender.org/BL/ for information + * about this. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL/BL DUAL LICENSE BLOCK ***** + */ + +#include "LOD_ManMesh2.h" + +#include "MT_assert.h" +#include <algorithm> +#include "LOD_MeshException.h" +#include "CTR_TaggedSetOps.h" +#include "CTR_UHeap.h" +#include "LOD_ExternBufferEditor.h" + + +using namespace std; + +LOD_ManMesh2:: +LOD_ManMesh2( +) : + m_bbox_min(0,0,0), + m_bbox_max(0,0,0) +{ +} + + + LOD_ManMesh2 * +LOD_ManMesh2:: +New( +){ + MEM_SmartPtr<LOD_ManMesh2> output(new LOD_ManMesh2()); + if (output == NULL) return NULL; + + // build the vertex, edge and face sets. + + MEM_SmartPtr<vector<LOD_Vertex> > verts(new vector<LOD_Vertex>); + MEM_SmartPtr<vector<LOD_TriFace> > faces(new vector<LOD_TriFace>); + MEM_SmartPtr<vector<LOD_Edge> > edges(new vector<LOD_Edge>); + + if ((faces == NULL) || (edges == NULL) || (verts == NULL)) { + return NULL; + } + + output->m_verts = verts.Release(); + output->m_faces = faces.Release(); + output->m_edges = edges.Release(); + + return output.Release(); +} + +// take ownership of the vertices. + + bool +LOD_ManMesh2:: +SetVertices( + MEM_SmartPtr<vector<LOD_Vertex> > verts +){ + + + // take ownership of vertices + m_verts = verts; + + // create a polygon and edge buffer of half the size + // and just use the automatic resizing feature of vector<> + // to worry about the dynamic array resizing + + m_faces->clear(); + m_edges->clear(); + + m_faces->reserve(m_verts->size()/2); + m_edges->reserve(m_verts->size()/2); + + return true; + +} + + +// add a triangle to the mesh + + void +LOD_ManMesh2:: +AddTriangle( + int verts[3] +) { + + MT_assert(verts[0] < int(m_verts->size())); + MT_assert(verts[1] < int(m_verts->size())); + MT_assert(verts[2] < int(m_verts->size())); + + LOD_TriFace face; + face.m_verts[0] = verts[0]; + face.m_verts[1] = verts[1]; + face.m_verts[2] = verts[2]; + + LOD_FaceInd face_index = m_faces->size(); + + m_faces->push_back(face); + + // now work out if any of the directed edges or their + // companion edges exist already. + // We go through the edges associated with each of the given vertices + + // the safest thing to do is iterate through each of the edge sets + // check against each of the 2 other triangle edges to see if they are there + + vector<LOD_EdgeInd> new_edges; + new_edges.reserve(3); + + InsertEdge(verts[0],verts[1],face_index,new_edges); + InsertEdge(verts[1],verts[2],face_index,new_edges); + InsertEdge(verts[2],verts[0],face_index,new_edges); + +} + +// Adds the index of any created edges to new_edges + + bool +LOD_ManMesh2:: +InsertEdge( + const LOD_VertexInd v1, + const LOD_VertexInd v2, + const LOD_FaceInd f, + vector<LOD_EdgeInd> &new_edges +){ + + MT_assert(!v1.IsEmpty()); + MT_assert(!v2.IsEmpty()); + MT_assert(!f.IsEmpty()); + + vector<LOD_Vertex> &verts = VertexSet(); + vector<LOD_Edge> &edges = EdgeSet(); + + LOD_EdgeInd e; + + e = FindEdge(v1,v2); + + if (e.IsEmpty()) { + // This edge does not exist -- make a new one + + LOD_Edge temp_e; + temp_e.m_verts[0] = v1; + temp_e.m_verts[1] = v2; + + e = m_edges->size(); + + // set the face ptr for this half-edge + temp_e.m_faces[0] = f; + + m_edges->push_back(temp_e); + + // add the edge index to it's vertices + + verts[v1].AddEdge(e); + verts[v2].AddEdge(e); + + new_edges.push_back(e); + + } else { + + // edge already exists + // insure that there is no polygon already + // attached to the other side of this edge + + // swap the empty face pointer in edge with f + + LOD_Edge &edge = edges[e]; + + edge.SwapFace(LOD_FaceInd::Empty(),f); + } + + + return true; + +} + + void +LOD_ManMesh2:: +ConnectTriangle( + LOD_FaceInd fi, + std::vector<LOD_EdgeInd> & new_edges +){ + + vector<LOD_TriFace> &faces = FaceSet(); + + MT_assert(!faces[fi].Degenerate()); + + LOD_TriFace & face = faces[fi]; + + InsertEdge(face.m_verts[0],face.m_verts[1],fi,new_edges); + InsertEdge(face.m_verts[1],face.m_verts[2],fi,new_edges); + InsertEdge(face.m_verts[2],face.m_verts[0],fi,new_edges); +}; + + + + +// geometry access +////////////////// + + vector<LOD_Vertex> & +LOD_ManMesh2:: +VertexSet( +) const { + return m_verts.Ref(); +} + + vector<LOD_TriFace> & +LOD_ManMesh2:: +FaceSet( +) const { + return m_faces.Ref(); +} + + vector<LOD_Edge> & +LOD_ManMesh2:: +EdgeSet( +) const { + return m_edges.Ref(); +}; + +LOD_ManMesh2:: +~LOD_ManMesh2( +){ + //auto ptr takes care of vertex arrays etc. +} + + LOD_EdgeInd +LOD_ManMesh2:: +FindEdge( + const LOD_VertexInd v1, + const LOD_VertexInd v2 +) { + + vector<LOD_Vertex> &verts = VertexSet(); + vector<LOD_Edge> &edges = EdgeSet(); + + LOD_Edge e; + e.m_verts[0] = v1; + e.m_verts[1] = v2; + + vector<LOD_EdgeInd> &v1_edges = verts[v1].m_edges; + vector<LOD_EdgeInd>::const_iterator v1_end = v1_edges.end(); + vector<LOD_EdgeInd>::iterator v1_begin = v1_edges.begin(); + + for (; v1_begin != v1_end; ++v1_begin) { + if (edges[*v1_begin] == e) return *v1_begin; + } + + return LOD_EdgeInd::Empty(); +} + +// face queries +/////////////// + + void +LOD_ManMesh2:: +FaceVertices( + LOD_FaceInd fi, + vector<LOD_VertexInd> &output +){ + const vector<LOD_TriFace> &faces = FaceSet(); + const LOD_TriFace & f = faces[fi]; + + output.push_back(f.m_verts[0]); + output.push_back(f.m_verts[1]); + output.push_back(f.m_verts[2]); +} + + void +LOD_ManMesh2:: +FaceEdges( + LOD_FaceInd fi, + vector<LOD_EdgeInd> &output +){ + const vector<LOD_TriFace> &faces = FaceSet(); + vector<LOD_Edge> &edges = EdgeSet(); + vector<LOD_Vertex> &verts = VertexSet(); + + const LOD_TriFace & f = faces[fi]; + // intersect vertex edges + + vector<LOD_EdgeInd> & v0_edges = verts[f.m_verts[0]].m_edges; + vector<LOD_EdgeInd> & v1_edges = verts[f.m_verts[1]].m_edges; + vector<LOD_EdgeInd> & v2_edges = verts[f.m_verts[2]].m_edges; + + CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v0_edges,v1_edges,edges,output); + CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v1_edges,v2_edges,edges,output); + CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v2_edges,v0_edges,edges,output); + + MT_assert(output.size() == 3); + if (output.size() != 3) { + LOD_MeshException e(LOD_MeshException::e_non_manifold); + throw(e); + } +} + + +// edge queries +/////////////// + + void +LOD_ManMesh2:: +EdgeVertices( + LOD_EdgeInd ei, + vector<LOD_VertexInd> &output +){ + const vector<LOD_Edge> &edges = EdgeSet(); + const LOD_Edge & e = edges[ei]; + + output.push_back(e.m_verts[0]); + output.push_back(e.m_verts[1]); +} + + void +LOD_ManMesh2:: +EdgeFaces( + LOD_EdgeInd ei, + vector<LOD_FaceInd> &output +){ + const vector<LOD_Edge> &edges = EdgeSet(); + const LOD_Edge & e = edges[ei]; + + if (!e.m_faces[0].IsEmpty()) { + output.push_back(e.m_faces[0]); + } + if (!e.m_faces[1].IsEmpty()) { + output.push_back(e.m_faces[1]); + } +} + +// vertex queries +///////////////// + + void +LOD_ManMesh2:: +VertexEdges( + LOD_VertexInd vi, + vector<LOD_EdgeInd> &output +){ + // iterate through the edges of v and push them onto the + // output + + vector<LOD_Vertex> &verts = VertexSet(); + + vector<LOD_EdgeInd> & v_edges = verts[vi].m_edges; + vector<LOD_EdgeInd>::iterator v_it = v_edges.begin(); + + for (; v_it != v_edges.end(); ++v_it) { + output.push_back(*v_it); + } +} + + void +LOD_ManMesh2:: +VertexFaces( + LOD_VertexInd vi, + vector<LOD_FaceInd> &output +){ + const vector<LOD_Vertex> &verts = VertexSet(); + vector<LOD_Edge> &edges = EdgeSet(); + vector<LOD_TriFace> &faces = FaceSet(); + + const vector<LOD_EdgeInd> &v_edges = verts[vi].m_edges; + vector<LOD_EdgeInd>::const_iterator e_it = v_edges.begin(); + + for (; e_it != v_edges.end(); ++e_it) { + + LOD_Edge &e = edges[*e_it]; + + if ((!e.m_faces[0].IsEmpty()) && (!faces[e.m_faces[0]].SelectTag())) { + output.push_back(e.m_faces[0]); + faces[e.m_faces[0]].SetSelectTag(true); + } + + if ((!e.m_faces[1].IsEmpty()) && (!faces[e.m_faces[1]].SelectTag())) { + output.push_back(e.m_faces[1]); + faces[e.m_faces[1]].SetSelectTag(true); + } + } + + vector<LOD_FaceInd>::iterator f_it = output.begin(); + + for (; f_it != output.end(); ++f_it) { + faces[*f_it].SetSelectTag(false); + } +}; + + void +LOD_ManMesh2:: +SetBBox( + MT_Vector3 bbox_min, + MT_Vector3 bbox_max +){ + m_bbox_min = bbox_min; + m_bbox_max = bbox_max; +}; + + void +LOD_ManMesh2:: +SC_TriFace( + LOD_FaceInd f +){ + LOD_TriFace face = (*m_faces)[f]; + + // check for unique vertices + + if ( + (face.m_verts[0] == face.m_verts[1]) || + (face.m_verts[1] == face.m_verts[2]) || + (face.m_verts[2] == face.m_verts[0]) + ) { + MT_assert(false); + } + +} + + + void +LOD_ManMesh2:: +SC_EdgeList( + LOD_VertexInd v +){ + vector<LOD_Edge> &edges = EdgeSet(); + vector<LOD_Vertex> &verts = VertexSet(); + + vector<LOD_EdgeInd>::iterator e_it = verts[v].m_edges.begin(); + + for (;e_it != verts[v].m_edges.end(); ++e_it) { + MT_assert( (edges[*e_it].m_verts[0] == v) || (edges[*e_it].m_verts[1] == v)); + } + +}; + + void +LOD_ManMesh2:: +DeleteVertex( + LOD_ExternBufferEditor & extern_editor, + LOD_VertexInd v +){ + + vector<LOD_Edge> &edges = EdgeSet(); + vector<LOD_Vertex> &verts = VertexSet(); + vector<LOD_TriFace> &faces = FaceSet(); + + // need to update all the edge and polygons pointing to + // the last vertex in m_verts + + if (verts.size() == 1) { + verts.clear(); + return; + } + + LOD_VertexInd last = LOD_VertexInd(verts.end() - verts.begin() - 1); + + if (!(last == v)) { + + // we asume that v is already disconnected + + vector<LOD_FaceInd> v_faces; + vector<LOD_EdgeInd> v_edges; + + v_faces.reserve(64); + v_edges.reserve(64); + + VertexFaces(last,v_faces); + VertexEdges(last,v_edges); + + // map the faces and edges to look at v + + vector<LOD_FaceInd>::iterator face_it = v_faces.begin(); + + for(; face_it != v_faces.end(); ++face_it) { + faces[*face_it].SwapVertex(last,v); + } + vector<LOD_EdgeInd>::iterator edge_it = v_edges.begin(); + + for (; edge_it != v_edges.end(); ++edge_it) { + edges[*edge_it].SwapVertex(last,v); + } + + // copy the last vertex onto v and pop off the back. + + verts[v] = verts[last]; + + // tidy external buffer + extern_editor.CopyModifiedFaces(*this,v_faces); + } + + verts.pop_back(); + extern_editor.CopyBackVertex(v); + + +}; + + void +LOD_ManMesh2:: +DeleteEdge( + LOD_EdgeInd e, + CTR_UHeap<LOD_Edge> * heap +){ + vector<LOD_Edge> &edges = EdgeSet(); + vector<LOD_Vertex> &verts = VertexSet(); + + if (edges.size() == 1) { + edges.clear(); + return; + } + + LOD_EdgeInd last = LOD_EdgeInd(edges.end() - edges.begin() - 1); + + if (!(last == e)) { + vector<LOD_EdgeInd> e_verts; + e_verts.reserve(2); + EdgeVertices(last,e_verts); + // something is wrong if there arent two! + + verts[e_verts[0]].SwapEdge(last,e); + verts[e_verts[1]].SwapEdge(last,e); + + // edges[e] should already have been removed from the heap + + MT_assert(edges[e].HeapPos() == 0xffffffff); + + edges[e] = edges[last]; + // also have to swap there heap positions.!!!!! + + heap->HeapVector()[edges[e].HeapPos()] = e; + + + } + edges.pop_back(); +}; + + void +LOD_ManMesh2:: +DeleteFace( + LOD_ExternBufferEditor & extern_editor, + LOD_FaceInd f +){ + + vector<LOD_Edge> &edges = EdgeSet(); + vector<LOD_TriFace> &faces = FaceSet(); + + if (faces.size() == 1) { + faces.clear(); + return; + } + + LOD_FaceInd last = LOD_FaceInd(faces.end() - faces.begin() - 1); + + if (!(last == f)) { + + // we have to update the edges which point to the last + // face + + vector<LOD_EdgeInd> f_edges; + f_edges.reserve(3); + + FaceEdges(last,f_edges); + + vector<LOD_EdgeInd>::iterator edge_it = f_edges.begin(); + vector<LOD_EdgeInd>::const_iterator edge_end = f_edges.end(); + + for (; edge_it != edge_end; ++edge_it) { + edges[*edge_it].SwapFace(last,f); + } + + faces[f] = faces[last]; + + } + faces.pop_back(); + + // tidy external buffers + extern_editor.CopyBackFace(f); +}; + + + + + + + + + + + + + + + + |