diff options
Diffstat (limited to 'intern/decimation')
25 files changed, 4949 insertions, 0 deletions
diff --git a/intern/decimation/Makefile b/intern/decimation/Makefile new file mode 100644 index 00000000000..f0d9567a618 --- /dev/null +++ b/intern/decimation/Makefile @@ -0,0 +1,52 @@ +# +# $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 ***** +# decimation main makefile. +# + +include nan_definitions.mk + +LIBNAME = decimation +SOURCEDIR = intern/$(LIBNAME) +DIR = $(OCGDIR)/$(SOURCEDIR) +DIRS = intern +TESTDIRS = test + +include nan_subdirs.mk + +install: all debug + @[ -d $(NAN_DECIMATION) ] || mkdir $(NAN_DECIMATION) + @[ -d $(NAN_DECIMATION)/include ] || mkdir $(NAN_DECIMATION)/include + @[ -d $(NAN_DECIMATION)/lib ] || mkdir $(NAN_DECIMATION)/lib + @[ -d $(NAN_DECIMATION)/lib/debug ] || mkdir $(NAN_DECIMATION)/lib/debug + cp -f $(DIR)/libdecimation.a $(NAN_DECIMATION)/lib/ + cp -f $(DIR)/debug/libdecimation.a $(NAN_DECIMATION)/lib/debug/ + cp -f extern/*.h $(NAN_DECIMATION)/include/ + diff --git a/intern/decimation/extern/LOD_decimation.h b/intern/decimation/extern/LOD_decimation.h new file mode 100644 index 00000000000..7a74dde165a --- /dev/null +++ b/intern/decimation/extern/LOD_decimation.h @@ -0,0 +1,119 @@ +/** + * $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 ***** + */ + +/** + + * @author Laurence Bourn + * @date 6/7/2001 + * + * This is the external interface for the decimation module. + */ + +#ifndef NAN_INCLUDED_LOD_decimation_h +#define NAN_INCLUDED_LOD_decimation_h + + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * External decimation structure + */ + +typedef struct LOD_Decimation_Info { + float * vertex_buffer; + float * vertex_normal_buffer; + int * triangle_index_buffer; + int vertex_num; + int face_num; + void * intern; +} LOD_Decimation_Info; + +typedef LOD_Decimation_Info* LOD_Decimation_InfoPtr; + +/** + * Create internal mesh representation from + * LOD_Decimation_Info structure. + * @return 1 on successful loading + * @return 0 on failure + * @warning This should be changed to return an enumeration + * detailing the error encountered + */ + +extern int LOD_LoadMesh(LOD_Decimation_InfoPtr info); + +/** + * Allocate and Compute internal data strucures required for + * decimation. + * @return 1 on successful computation of data + * @return 0 on failure + * @warning This should be changed to return an enumeration + * detailing the error encountered + */ + +extern int LOD_PreprocessMesh(LOD_Decimation_InfoPtr info); + +/** + * Once both the stages above have been completed + * this function collapses a single edge in the mesh. + * The LOD_Decimation_Info structure is updated + * to represent the new mesh. + * @return 1 if an edge was collapsed. + * @return 0 if no suitable edge was found to be collapsable + * You should stop calling this method in this case + * @warning Do not expect that the order of polygons, vertices or + * vertex normals will be preserved by this operation. This function + * returns a packed array of polygons and vertices and so necessarily + * the order will be different. This means you should not expect to + * find the same polygon in the same place in the polygon array after + * this function has been called. + */ + +extern int LOD_CollapseEdge(LOD_Decimation_InfoPtr info); + +/** + * Free any memory the decimation process used + * during the decimation process + * @return 1 if internal data successfully freed + * @return 0 if no data was freed + */ + +extern int LOD_FreeDecimationData(LOD_Decimation_InfoPtr); + +#ifdef __cplusplus +} +#endif + +#endif // NAN_INCLUDED_LOD_decimation_h + + + diff --git a/intern/decimation/intern/LOD_DecimationClass.h b/intern/decimation/intern/LOD_DecimationClass.h new file mode 100644 index 00000000000..7df294daaee --- /dev/null +++ b/intern/decimation/intern/LOD_DecimationClass.h @@ -0,0 +1,118 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_LOD_DecimationClass_h + +#define NAN_INCLUDED_LOD_DecimationClass_h + +#include "MEM_SmartPtr.h" +#include "MEM_NonCopyable.h" + +#include "LOD_ManMesh2.h" +#include "LOD_QSDecimator.h" +#include "LOD_ExternNormalEditor.h" +#include "../extern/LOD_decimation.h" +#include "LOD_ExternBufferEditor.h" + + +class LOD_DecimationClass : public MEM_NonCopyable +{ +public : + + enum { + e_not_loaded, + e_loaded, + e_preprocessed + } m_e_decimation_state; + + + static + LOD_DecimationClass * + New( + LOD_Decimation_InfoPtr extern_info + ) { + // create everything + + MEM_SmartPtr<LOD_DecimationClass> output(new LOD_DecimationClass()); + MEM_SmartPtr<LOD_ManMesh2> mesh(LOD_ManMesh2::New()); + MEM_SmartPtr<LOD_ExternBufferEditor> extern_editor(LOD_ExternBufferEditor::New(extern_info)); + + if (mesh == NULL || extern_editor == NULL) return NULL; + MEM_SmartPtr<LOD_ExternNormalEditor> normals(LOD_ExternNormalEditor::New(extern_info,mesh.Ref())); + + if (normals == NULL) return NULL; + MEM_SmartPtr<LOD_QSDecimator> decimator(LOD_QSDecimator::New( + mesh.Ref(), + normals.Ref(), + extern_editor.Ref() + )); + if (decimator == NULL || output == NULL) return NULL; + + output->m_mesh = mesh.Release(); + output->m_decimator = decimator.Release(); + output->m_normals = normals.Release(); + output->m_extern_editor = extern_editor.Release(); + + return output.Release(); + } + + LOD_ManMesh2 & + Mesh( + ){ + return m_mesh.Ref(); + } + + LOD_QSDecimator & + Decimator( + ) { + return m_decimator.Ref(); + } + + LOD_ExternNormalEditor & + FaceEditor( + ){ + return m_normals.Ref(); + } + +private : + + LOD_DecimationClass( + ) : m_e_decimation_state(e_not_loaded) { + }; + + MEM_SmartPtr<LOD_ManMesh2> m_mesh; + MEM_SmartPtr<LOD_QSDecimator> m_decimator; + MEM_SmartPtr<LOD_ExternNormalEditor> m_normals; + MEM_SmartPtr<LOD_ExternBufferEditor> m_extern_editor; +}; + + +#endif diff --git a/intern/decimation/intern/LOD_EdgeCollapser.cpp b/intern/decimation/intern/LOD_EdgeCollapser.cpp new file mode 100644 index 00000000000..4168a2ae371 --- /dev/null +++ b/intern/decimation/intern/LOD_EdgeCollapser.cpp @@ -0,0 +1,408 @@ +/** + * $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_EdgeCollapser.h" + +#include "LOD_ManMesh2.h" +#include "CTR_TaggedSetOps.h" +#include <algorithm> +#include <functional> + + +using namespace std; + + + LOD_EdgeCollapser * +LOD_EdgeCollapser:: +New( +){ + return new LOD_EdgeCollapser(); +} + + + bool +LOD_EdgeCollapser:: +TJunctionTest( + LOD_ManMesh2 &mesh, + vector<LOD_EdgeInd> &e_v0v1, + LOD_EdgeInd collapse_edge +){ + + // we need to copy the egdes in e_v0v1 from the mesh + // into a new buffer -> we are going to modify them + + int original_size = e_v0v1.size(); + if (original_size == 0) return true; + + vector<LOD_Edge> &edge_set = mesh.EdgeSet(); + + LOD_VertexInd c_v0 = edge_set[collapse_edge].m_verts[0]; + LOD_VertexInd c_v1 = edge_set[collapse_edge].m_verts[1]; + + vector<LOD_Edge> temp_edges; + temp_edges.reserve(e_v0v1.size()); + + vector<LOD_EdgeInd>::iterator edge_it = e_v0v1.begin(); + vector<LOD_EdgeInd>::const_iterator edge_end = e_v0v1.end(); + + for (;edge_it != edge_end; ++edge_it) { + temp_edges.push_back(edge_set[*edge_it]); + } + + // in the copied edges replace all instances of c_v0 with c_v1 + + vector<LOD_Edge>::iterator e_it = temp_edges.begin(); + vector<LOD_Edge>::const_iterator e_it_end = temp_edges.end(); + + for (; e_it != e_it_end; ++e_it) { + + if (e_it->m_verts[0] == c_v0) { + e_it->m_verts[0] = c_v1; + } + if (e_it->m_verts[1] == c_v0) { + e_it->m_verts[1] = c_v1; + } + + // normalize the edge + if (int(e_it->m_verts[0]) > int(e_it->m_verts[1])) { + LOD_EdgeInd temp = e_it->m_verts[0]; + e_it->m_verts[0] = e_it->m_verts[1]; + e_it->m_verts[1] = temp; + } + } + + // sort the edges using the edge less functional + + sort(temp_edges.begin(),temp_edges.end(),LOD_EdgeCollapser::less()); + // count the unique edges. + + e_it = temp_edges.begin(); + e_it_end = temp_edges.end(); + + int coincedent_edges = 0; + + vector<LOD_Edge>::const_iterator last_edge = e_it; + ++e_it; + + for (; e_it != e_it_end; ++e_it) { + + if ((e_it->m_verts[0] == last_edge->m_verts[0]) && + (e_it->m_verts[1] == last_edge->m_verts[1]) + ) { + ++coincedent_edges; + } + last_edge = e_it; + } + + // now if the collapse edge is a boundary edges + // then we are alloved at most one coincedent edge + + // otherwise at most 2 coincedent edges + + if (edge_set[collapse_edge].BoundaryEdge()) { + return (coincedent_edges > 1); + } else { + return (coincedent_edges > 2); + } + + +} + + + + bool +LOD_EdgeCollapser:: +CollapseEdge( + LOD_EdgeInd ei, + LOD_ManMesh2 &mesh, + vector<LOD_EdgeInd> & degenerate_edges, + vector<LOD_FaceInd> & degenerate_faces, + vector<LOD_VertexInd> & degenerate_vertices, + vector<LOD_EdgeInd> & new_edges, + vector<LOD_FaceInd> & update_faces, + vector<LOD_VertexInd> & update_vertices +){ + + vector<LOD_Vertex> &verts = mesh.VertexSet(); + vector<LOD_Edge> &edges = mesh.EdgeSet(); + vector<LOD_TriFace> &faces = mesh.FaceSet(); + + // shouldn't do this (use mesh interface instead!) + LOD_VertexInd v0_ind = edges[ei].m_verts[0]; + LOD_VertexInd v1_ind = edges[ei].m_verts[1]; +#if 0 + LOD_Vertex &v0 = verts[v0_ind]; + LOD_Vertex &v1 = verts[v1_ind]; +#endif + vector<vector<LOD_EdgeInd> > e_v01(2); + e_v01[0].reserve(32); + e_v01[1].reserve(32); + + mesh.VertexEdges(v0_ind,e_v01[0]); + mesh.VertexEdges(v1_ind,e_v01[1]); + + + // compute the union of e_v0 and e_v1 -> this is the degenerate edges of the collapse + // we remove old edges and replace edges inside the collapse zone with new ones + + CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::Union(e_v01,edges,degenerate_edges); + + vector< vector<LOD_FaceInd> > p_v01(2); + p_v01[0].reserve(32); + p_v01[1].reserve(32); + + mesh.VertexFaces(v0_ind,p_v01[0]); + mesh.VertexFaces(v1_ind,p_v01[1]); + + // compute the union of p_v0 anf p_v1 + vector<LOD_FaceInd> p_v0v1; + p_v0v1.reserve(32); + + CTR_TaggedSetOps<LOD_FaceInd,LOD_TriFace>::Union(p_v01,faces,p_v0v1); + + // compute the union of all the edges in p_v0v1 this is the collapse zone + + vector<vector<LOD_EdgeInd> > e_input_vectors(p_v0v1.size()); + + vector<LOD_FaceInd>::iterator p_v0v1_end = p_v0v1.end(); + vector<LOD_FaceInd>::iterator p_v0v1_start = p_v0v1.begin(); + + vector<vector<LOD_FaceInd> >::iterator vector_insert_it = e_input_vectors.begin(); + + for (;p_v0v1_start != p_v0v1_end; ++p_v0v1_start , ++vector_insert_it) { + mesh.FaceEdges(*p_v0v1_start,*vector_insert_it); + } + + vector<LOD_EdgeInd> collapse_zone; + collapse_zone.reserve(32); + + CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::Union(e_input_vectors,edges,collapse_zone); + + // compute the ring edges = collpase_zone - e_v0v1 + + vector<LOD_EdgeInd> edge_ring; + edge_ring.reserve(32); + + CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::Difference(collapse_zone,degenerate_edges,edges,edge_ring); + + // T Junction test + ////////////////// + // At this point we check to see if any of the polygons + // in p_v0v1 are coninceddent - this leads + // to errors later on if we try and insert a polygon + // into the mesh to an edge which already has 2 polygons. + + // not that t junctions occur naturally from edge collapses + // and are not just the result of coincedent polygons + // for example consider collapsing an edge that forms part + // of a triangular bottle neck. + + // Really we need to make sure that we don't create t-junctions. + + // I think that a sufficient test is to check the number of + // coincedent edge pairs after a collapse. If it is more than 2 + // then collapsing the edge may result in an undeleted edge + // sharing more than 2 polygons. This test probably is too + // restictive though. + + // To perform this test we need to make a copy of the edges + // in e_v0v1. We then apply the contraction to these edge + // copies. Sort them using a function that places coincedent + // edges next to each other. And then count the number + // of coincedent pairs. + + // Of course we have to do this test before we change any of the + // mesh -> so we can back out safely. + + if (TJunctionTest(mesh,degenerate_edges,ei)) return false; + + // Compute the set of possibly degenerate vertices + // this is the union of all the vertices of polygons + // of v0 and v1 + + vector<LOD_FaceInd>::iterator face_it = p_v0v1.begin(); + vector<LOD_FaceInd>::const_iterator face_end = p_v0v1.end(); + + + vector<vector<LOD_VertexInd> > p_v0v1_vertices(p_v0v1.size()); + + for (int i = 0; face_it != face_end; ++face_it, ++i) { + mesh.FaceVertices(*face_it,p_v0v1_vertices[i]); + } + + vector<LOD_VertexInd> vertex_ring; + vertex_ring.reserve(32); + + CTR_TaggedSetOps<LOD_VertexInd,LOD_Vertex>::Union(p_v0v1_vertices,verts,vertex_ring); + + // remove all the internal edges e_v0v1 from the mesh. + // for each edge remove the egde from it's vertices edge lists. + + vector<LOD_EdgeInd>::iterator edge_it = degenerate_edges.begin(); + vector<LOD_EdgeInd>::const_iterator edge_end = degenerate_edges.end(); + + for (; edge_it != edge_end; ++edge_it) { + + LOD_Edge & edge = edges[*edge_it]; + + verts[edge.m_verts[0]].RemoveEdge(*edge_it); + verts[edge.m_verts[1]].RemoveEdge(*edge_it); + } + + // we postpone deletion of the internal edges untill the end + // this is because deleting edges invalidates all of the + // EdgeInd vectors above. + + + // now untie all the polygons in p_v0v1 from the edge ring + + // select all polygons in p_v0v1 + + face_it = p_v0v1.begin(); + face_end = p_v0v1.end(); + + for (;face_it != face_end; ++face_it) { + faces[*face_it].SetSelectTag(true); + } + + edge_it = edge_ring.begin(); + edge_end = edge_ring.end(); + + for (;edge_it != edge_end; ++edge_it) { + LOD_Edge & edge = edges[*edge_it]; + + // presumably all edges in edge_ring point to at least + // one polygon from p_v0v1 + + if (!edge.m_faces[0].IsEmpty() && faces[edge.m_faces[0]].SelectTag()) { + edge.m_faces[0].Invalidate(); + } + + if (!edge.m_faces[1].IsEmpty() && faces[edge.m_faces[1]].SelectTag()) { + edge.m_faces[1].Invalidate(); + } + } + + // deselect the faces + + face_it = p_v0v1.begin(); + face_end = p_v0v1.end(); + + for (;face_it != face_end; ++face_it) { + faces[*face_it].SetSelectTag(false); + } + + // perform the edge collapse + //////////////////////////// + + // iterate through the polygons of p_v0 and replace the vertex + // index v0 with v1 + + face_it = p_v01[0].begin(); + face_end = p_v01[0].end(); + + for (;face_it != face_end; ++face_it) { + faces[*face_it].SwapVertex(v0_ind,v1_ind); + } + + face_it = p_v0v1.begin(); + face_end = p_v0v1.end(); + + for (;face_it != face_end; ++face_it) { + if (faces[*face_it].Degenerate()) { + degenerate_faces.push_back(*face_it); + } else { + update_faces.push_back(*face_it); + } + } + + // Add all the non-degenerate faces back into the + // mesh. Get a record of the new edges created in + // this process. + + face_it = update_faces.begin(); + face_end = update_faces.end(); + + for (;face_it != face_end; ++face_it) { + mesh.ConnectTriangle(*face_it,new_edges); + } + + // degenerate ring primitives + ///////////////////////////// + + // we now need to examine each of the edges on the ring + // and work out if they are degenerate - if so we attempt + // to delete them -> add them to the other edges to delete + // in e_v0v1 + + edge_it = edge_ring.begin(); + edge_end = edge_ring.end(); + + for (;edge_it != edge_end; ++edge_it) { + if (edges[*edge_it].Degenerate()) { + degenerate_edges.push_back(*edge_it); + } + } + + // do the same for the ring vertices. + + vector<LOD_VertexInd>::iterator vertex_it = vertex_ring.begin(); + vector<LOD_VertexInd>::const_iterator vertex_end = vertex_ring.end(); + + for (;vertex_it != vertex_end; ++vertex_it) { + if (verts[*vertex_it].Degenerate()) { + degenerate_vertices.push_back(*vertex_it); + } else { + update_vertices.push_back(*vertex_it); + } + } + + // we now know all the degenerate primitives + // and the new primitives we have inserted into the mesh + + // We now delete the mesh primitives, mesh.DeleteXXXXXX() methods + // assume that the index vectors are sorted into descending order. + // we do that now. + + sort(degenerate_edges.begin(),degenerate_edges.end(),LOD_EdgeInd::greater()); + sort(degenerate_faces.begin(),degenerate_faces.end(),LOD_FaceInd::greater()); + sort(degenerate_vertices.begin(),degenerate_vertices.end(),LOD_VertexInd::greater()); + + + return true; + +} + +LOD_EdgeCollapser:: +LOD_EdgeCollapser( +){ + // nothing to do +} diff --git a/intern/decimation/intern/LOD_EdgeCollapser.h b/intern/decimation/intern/LOD_EdgeCollapser.h new file mode 100644 index 00000000000..d500c45e1ba --- /dev/null +++ b/intern/decimation/intern/LOD_EdgeCollapser.h @@ -0,0 +1,118 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLDUED_EgdeCollapser_h + +#define NAN_INCLDUED_EgdeCollapser_h + +// This is a helper class that collapses edges of a 2 - manifold mesh. + +#include "LOD_MeshPrimitives.h" +#include "MEM_NonCopyable.h" +#include <vector> +#include <functional> + +class LOD_ManMesh2; + +class LOD_EdgeCollapser +: public MEM_NonCopyable +{ + +public : + + static + LOD_EdgeCollapser * + New( + ); + + // returns via arguments the set of modified + // verts,edges and faces. + + bool + CollapseEdge( + LOD_EdgeInd ei, + LOD_ManMesh2 &mesh, + std::vector<LOD_EdgeInd> & degenerate_edges, + std::vector<LOD_FaceInd> & degenerate_faces, + std::vector<LOD_VertexInd> & degenerate_vertices, + std::vector<LOD_EdgeInd> & new_edges, + std::vector<LOD_FaceInd> & update_faces, + std::vector<LOD_VertexInd> & update_vertices + ); + +private : + + LOD_EdgeCollapser( + ); + + // Test to see if the result of collapsing the + // edge produces 2 junctions in the mesh i.e. where + // an edge is shared by more than 2 polygons + + // We count the number of coincedent edge pairs that + // result from the collapse of collapse_edge. + + // If collapse edge is a boundary edge then the number of + // coincedent pairs should be 1 + // else it should be 2. + + bool + TJunctionTest( + LOD_ManMesh2 &mesh, + std::vector<LOD_EdgeInd> &e_v0v1, + LOD_EdgeInd collapse_edge + ); + + // here's the definition of the sort function + // we use to determine coincedent edges + + // assumes the edges are normalized i.e. m_verts[0] <= m_verts[1] + + struct less : std::binary_function<LOD_Edge, LOD_Edge, bool> { + bool + operator()( + const LOD_Edge& a, + const LOD_Edge& b + ) const { + + if (int(a.m_verts[0]) == int(b.m_verts[0])) { + return (int(a.m_verts[1]) < int(b.m_verts[1])); + } else { + return (int(a.m_verts[0]) < int(b.m_verts[0])); + } + } + }; + +}; + + +#endif + diff --git a/intern/decimation/intern/LOD_ExternBufferEditor.h b/intern/decimation/intern/LOD_ExternBufferEditor.h new file mode 100644 index 00000000000..9f628c4455b --- /dev/null +++ b/intern/decimation/intern/LOD_ExternBufferEditor.h @@ -0,0 +1,164 @@ +/** + * $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 ***** + */ + +/** + + * $Id$ + * Copyright (C) 2001 NaN Technologies B.V. + */ + +#ifndef NAN_INCLUDED_LOD_ExternBufferEditor_h +#define NAN_INCLUDED_LOD_ExternBufferEditor_h + +#include "LOD_MeshPrimitives.h" +#include <vector> +#include "LOD_ManMesh2.h" +#include "../extern/LOD_decimation.h" + + +// This class syncs external vertex/face buffers +// with the internal mesh representation during +// decimation. + +class LOD_ExternBufferEditor +{ + +public : + + static + LOD_ExternBufferEditor * + New( + LOD_Decimation_InfoPtr extern_info + ){ + if (extern_info == NULL) return NULL; + return new LOD_ExternBufferEditor(extern_info); + } + + // update the external vertex buffer with vertices + // from the mesh + + void + CopyModifiedVerts( + LOD_ManMesh2 & mesh, + const std::vector<LOD_VertexInd> & mod_vertices + ){ + + std::vector<LOD_VertexInd>::const_iterator v_start = mod_vertices.begin(); + std::vector<LOD_VertexInd>::const_iterator v_end = mod_vertices.end(); + + std::vector<LOD_Vertex> & mesh_verts = mesh.VertexSet(); + + float * const extern_vertex_ptr = m_extern_info->vertex_buffer; + + for (; v_start != v_end; ++v_start) { + float * mod_vert = extern_vertex_ptr + int(*v_start)*3; + mesh_verts[*v_start].CopyPosition(mod_vert); + } + } + + // update the external face buffer with faces from the mesh + + void + CopyModifiedFaces( + LOD_ManMesh2 & mesh, + const std::vector<LOD_FaceInd> & mod_faces + ){ + + std::vector<LOD_FaceInd>::const_iterator f_start = mod_faces.begin(); + std::vector<LOD_FaceInd>::const_iterator f_end = mod_faces.end(); + + std::vector<LOD_TriFace> &mesh_faces = mesh.FaceSet(); + + int * const extern_face_ptr = m_extern_info->triangle_index_buffer; + + for (; f_start != f_end; ++f_start) { + int *mod_face = extern_face_ptr + 3*int(*f_start); + mesh_faces[*f_start].CopyVerts(mod_face); + } + } + + + // Copy the last vertex over the vertex specified by + // vi. Decrement the size of the vertex array + + void + CopyBackVertex( + LOD_VertexInd vi + ){ + + float * const extern_vertex_ptr = m_extern_info->vertex_buffer; + int * extern_vertex_num = &(m_extern_info->vertex_num); + + float * last_external_vert = extern_vertex_ptr + 3*((*extern_vertex_num) - 1); + float * external_vert = extern_vertex_ptr + 3*int(vi); + + external_vert[0] = last_external_vert[0]; + external_vert[1] = last_external_vert[1]; + external_vert[2] = last_external_vert[2]; + + *extern_vertex_num -=1; + } + + // Copy the last face over the face specified by fi + // Decrement the size of the face array + + void + CopyBackFace( + LOD_FaceInd fi + ) { + int * const extern_face_ptr = m_extern_info->triangle_index_buffer; + int * extern_face_num = &(m_extern_info->face_num); + + int * last_external_face = extern_face_ptr + 3*((*extern_face_num) -1); + int * external_face = extern_face_ptr + 3*int(fi); + external_face[0] = last_external_face[0]; + external_face[1] = last_external_face[1]; + external_face[2] = last_external_face[2]; + + *extern_face_num -=1; + } + + +private : + + LOD_ExternBufferEditor( + LOD_Decimation_InfoPtr extern_info + ) : + m_extern_info (extern_info) + { + } + + LOD_Decimation_InfoPtr const m_extern_info; + +}; + +#endif + diff --git a/intern/decimation/intern/LOD_ExternNormalEditor.cpp b/intern/decimation/intern/LOD_ExternNormalEditor.cpp new file mode 100644 index 00000000000..357aaf56006 --- /dev/null +++ b/intern/decimation/intern/LOD_ExternNormalEditor.cpp @@ -0,0 +1,264 @@ +/** + * $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_ExternNormalEditor.h" + +#include <vector> + +using namespace std; + + +LOD_ExternNormalEditor:: +LOD_ExternNormalEditor( + LOD_Decimation_InfoPtr extern_info, + LOD_ManMesh2 &mesh +) : + m_extern_info (extern_info), + m_mesh(mesh) +{ +} + + LOD_ExternNormalEditor * +LOD_ExternNormalEditor:: +New( + LOD_Decimation_InfoPtr extern_info, + LOD_ManMesh2 &mesh +){ + if (extern_info == NULL) return NULL; + + MEM_SmartPtr<LOD_ExternNormalEditor> output(new LOD_ExternNormalEditor(extern_info,mesh)); + + int face_num = mesh.FaceSet().size(); + + MEM_SmartPtr<vector<MT_Vector3> > normals(new vector<MT_Vector3>); + + if (output == NULL || + normals == NULL + ) { + return NULL; + } + + normals->reserve(face_num); + output->m_normals = normals.Release(); + + return output.Release(); +}; + + + void +LOD_ExternNormalEditor:: +Remove( + std::vector<LOD_FaceInd> &sorted_faces +){ + // assumes a collection of faces sorted in descending order . + + vector<MT_Vector3> & normals = m_normals.Ref(); + + vector<LOD_FaceInd>::const_iterator it_start = sorted_faces.begin(); + vector<LOD_FaceInd>::const_iterator it_end = sorted_faces.end(); + + for (; it_start != it_end; ++it_start) { + + if (normals.size() > 0) { + MT_Vector3 temp = normals[*it_start]; + + normals[*it_start] = normals.back(); + normals.back() = temp; + + normals.pop_back(); + } + + // FIXME - throw exception + } +} + + + void +LOD_ExternNormalEditor:: +Add( +){ + MT_Vector3 zero(0.0f,0.0f,0.0f); + m_normals->push_back(zero); +}; + + void +LOD_ExternNormalEditor:: +Update( + std::vector<LOD_FaceInd> &sorted_faces +){ + vector<MT_Vector3> & normals = m_normals.Ref(); + + vector<LOD_FaceInd>::const_iterator it_start = sorted_faces.begin(); + vector<LOD_FaceInd>::const_iterator it_end = sorted_faces.end(); + + const vector<LOD_TriFace> &faces = m_mesh.FaceSet(); + + for (; it_start != it_end; ++it_start) { + normals[*it_start] = ComputeNormal(faces[*it_start]); + } +}; + + + + +// vertex normals +///////////////// + + void +LOD_ExternNormalEditor:: +RemoveVertexNormals( + std::vector<LOD_VertexInd> &sorted_verts +){ + + float * vertex_normals = m_extern_info->vertex_normal_buffer; + + // assumption here that the vertexs normal number corresponds with + // the number of vertices ! + + int vertex_normal_num = m_extern_info->vertex_num; + + vector<LOD_VertexInd>::const_iterator it_start = sorted_verts.begin(); + vector<LOD_VertexInd>::const_iterator it_end = sorted_verts.end(); + + for (; it_start != it_end; ++it_start) { + + if (vertex_normal_num > 0) { + float * vertex_normal = vertex_normals + int(*it_start)*3; + float * last_vertex = vertex_normals + ((vertex_normal_num-1)*3); + + MT_Vector3 last_v(last_vertex); + last_v.getValue(vertex_normal); + vertex_normal_num--; + } + + // FIXME - through exception + } +}; + + + + void +LOD_ExternNormalEditor:: +UpdateVertexNormals( + std::vector<LOD_VertexInd> &sorted_verts +){ + float * vertex_normals = m_extern_info->vertex_normal_buffer; + + vector<LOD_VertexInd>::const_iterator it_start = sorted_verts.begin(); + vector<LOD_VertexInd>::const_iterator it_end = sorted_verts.end(); + + for (; it_start != it_end; ++it_start) { + MT_Vector3 temp = ComputeVertexNormal(*it_start); + float * vertex_normal = vertex_normals + int(*it_start)*3; + temp.getValue(vertex_normal); + } +} + +// Editor specific methods +////////////////////////// + + void +LOD_ExternNormalEditor:: +BuildNormals( +) { + const vector<LOD_TriFace> &faces = m_mesh.FaceSet(); + vector<MT_Vector3> & normals = m_normals.Ref(); + + int face_num = faces.size(); + int cur_face = 0; + + for (; cur_face < face_num; ++cur_face) { + + MT_Vector3 new_normal = ComputeNormal(faces[cur_face]); + normals.push_back(new_normal); + } +} + +const + MT_Vector3 +LOD_ExternNormalEditor:: +ComputeNormal( + const LOD_TriFace &face +) const { + + const vector<LOD_Vertex> &verts = m_mesh.VertexSet(); + + MT_Vector3 vec1 = + verts[face.m_verts[1]].pos - + verts[face.m_verts[0]].pos; + + MT_Vector3 vec2 = + verts[face.m_verts[2]].pos - + verts[face.m_verts[1]].pos; + + vec1 = vec1.cross(vec2); + + if (!vec1.fuzzyZero()) { + vec1.normalize(); + return (vec1); + } else { + return (MT_Vector3(1.0,0,0)); + } +} + +const + MT_Vector3 +LOD_ExternNormalEditor:: +ComputeVertexNormal( + const LOD_VertexInd v +) const { + + // average the face normals surrounding this + // vertex and normalize + vector<LOD_Vertex> &verts = m_mesh.VertexSet(); + const vector<MT_Vector3> & face_normals = m_normals.Ref(); + + vector<LOD_FaceInd> vertex_faces; + vertex_faces.reserve(32); + + m_mesh.VertexFaces(v,vertex_faces); + + MT_Vector3 normal(0,0,0); + + vector<LOD_FaceInd>::const_iterator face_it = vertex_faces.begin(); + vector<LOD_FaceInd>::const_iterator face_end = vertex_faces.end(); + + for (; face_it != face_end; ++face_it) { + normal += face_normals[*face_it]; + } + + if (!normal.fuzzyZero()) { + normal.normalize(); + return (normal); + } else { + return (MT_Vector3(1.0,0,0)); + } +} diff --git a/intern/decimation/intern/LOD_ExternNormalEditor.h b/intern/decimation/intern/LOD_ExternNormalEditor.h new file mode 100644 index 00000000000..c32b3d5a0b3 --- /dev/null +++ b/intern/decimation/intern/LOD_ExternNormalEditor.h @@ -0,0 +1,134 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_ExternNormalEditor_h + +#define NAN_INCLUDED_ExternNormalEditor_h + +#include "MEM_NonCopyable.h" +#include "LOD_ManMesh2.h" +#include "MT_Vector3.h" +#include "../extern/LOD_decimation.h" + +class LOD_ExternNormalEditor : public MEM_NonCopyable +{ + +public : + + // Creation + /////////// + + static + LOD_ExternNormalEditor * + New( + LOD_Decimation_InfoPtr, + LOD_ManMesh2 &mesh + ); + + // Property editor interface + //////////////////////////// + + + // Faces + //////// + void + Remove( + std::vector<LOD_FaceInd> &sorted_faces + ); + + void + Add( + ); + + void + Update( + std::vector<LOD_FaceInd> &sorted_faces + ); + + const + std::vector<MT_Vector3> & + Normals( + ) const { + return m_normals.Ref(); + }; + + + // vertex normals + ///////////////// + + void + RemoveVertexNormals( + std::vector<LOD_VertexInd> &sorted_verts + ); + + + void + UpdateVertexNormals( + std::vector<LOD_VertexInd> &sorted_verts + ); + + // Editor specific methods + ////////////////////////// + + void + BuildNormals( + ); + + +private : + + MEM_SmartPtr<std::vector<MT_Vector3> > m_normals; + + LOD_ManMesh2 &m_mesh; + LOD_Decimation_InfoPtr m_extern_info; + +private : + + + LOD_ExternNormalEditor( + LOD_Decimation_InfoPtr extern_info, + LOD_ManMesh2 &mesh + ); + + const + MT_Vector3 + ComputeNormal( + const LOD_TriFace &face + ) const ; + + const + MT_Vector3 + ComputeVertexNormal ( + const LOD_VertexInd vi + ) const; +}; + +#endif diff --git a/intern/decimation/intern/LOD_FaceNormalEditor.cpp b/intern/decimation/intern/LOD_FaceNormalEditor.cpp new file mode 100644 index 00000000000..ef6bc0d252e --- /dev/null +++ b/intern/decimation/intern/LOD_FaceNormalEditor.cpp @@ -0,0 +1,291 @@ +/** + * $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 ***** + */ + +// implementation of LOD_FaceNormalEditor.h + +/////////////////////////////////////// + +#include "LOD_FaceNormalEditor.h" + +using namespace std; + +LOD_FaceNormalEditor:: +LOD_FaceNormalEditor( + LOD_ManMesh2 & mesh +) : m_mesh(mesh) { +}; + + LOD_FaceNormalEditor * +LOD_FaceNormalEditor:: +New( + LOD_ManMesh2 &mesh +){ + // build a set of normals of the same size + // as the number of polys in the mesh + + MEM_SmartPtr<LOD_FaceNormalEditor> output(new LOD_FaceNormalEditor(mesh)); + + int face_num = mesh.FaceSet().size(); + + MEM_SmartPtr<vector<MT_Vector3> > normals(new vector<MT_Vector3>); + MEM_SmartPtr<vector<MT_Vector3> > vertex_normals(new vector<MT_Vector3>); + + if (output == NULL || + normals == NULL + ) { + return NULL; + } + + normals->reserve(face_num); + vertex_normals->reserve(mesh.VertexSet().size()); + output->m_normals = normals.Release(); + output->m_vertex_normals = vertex_normals.Release(); + + return output.Release(); +}; + + +// Property editor interface +//////////////////////////// + + void +LOD_FaceNormalEditor:: +Remove( + std::vector<LOD_FaceInd> &sorted_faces +){ + + // assumes a collection of faces sorted in descending order . + + vector<MT_Vector3> & normals = m_normals.Ref(); + + vector<LOD_FaceInd>::const_iterator it_start = sorted_faces.begin(); + vector<LOD_FaceInd>::const_iterator it_end = sorted_faces.end(); + + for (; it_start != it_end; ++it_start) { + + if (normals.size() > 0) { + MT_Vector3 temp = normals[*it_start]; + + normals[*it_start] = normals.back(); + normals.back() = temp; + + normals.pop_back(); + } + + // FIXME - through exception + } +} + + + void +LOD_FaceNormalEditor:: +Add( +){ + MT_Vector3 zero(0.0f,0.0f,0.0f); + m_normals->push_back(zero); +} + + void +LOD_FaceNormalEditor:: +Update( + std::vector<LOD_FaceInd> &sorted_faces +){ + + vector<MT_Vector3> & normals = m_normals.Ref(); + + vector<LOD_FaceInd>::const_iterator it_start = sorted_faces.begin(); + vector<LOD_FaceInd>::const_iterator it_end = sorted_faces.end(); + + const vector<LOD_TriFace> &faces = m_mesh.FaceSet(); + + for (; it_start != it_end; ++it_start) { + normals[*it_start] = ComputeNormal(faces[*it_start]); + } +}; + +// vertex normals +///////////////// + + + void +LOD_FaceNormalEditor:: +RemoveVertexNormals( + vector<LOD_VertexInd> &sorted_verts +){ + vector<MT_Vector3> & vertex_normals = m_vertex_normals.Ref(); + + vector<LOD_VertexInd>::const_iterator it_start = sorted_verts.begin(); + vector<LOD_VertexInd>::const_iterator it_end = sorted_verts.end(); + + for (; it_start != it_end; ++it_start) { + + if (vertex_normals.size() > 0) { + MT_Vector3 temp = vertex_normals[*it_start]; + + vertex_normals[*it_start] = vertex_normals.back(); + vertex_normals.back() = temp; + + vertex_normals.pop_back(); + } + + // FIXME - through exception + } +}; + + void +LOD_FaceNormalEditor:: +UpdateVertexNormals( + vector<LOD_VertexInd> &sorted_verts +){ + vector<MT_Vector3> & vertex_normals = m_vertex_normals.Ref(); + + vector<LOD_VertexInd>::const_iterator it_start = sorted_verts.begin(); + vector<LOD_VertexInd>::const_iterator it_end = sorted_verts.end(); + + for (; it_start != it_end; ++it_start) { + vertex_normals[*it_start] = ComputeVertexNormal(*it_start); + } +} + + + +// Editor specific methods +////////////////////////// + + void +LOD_FaceNormalEditor:: +BuildNormals( +){ + + const vector<LOD_TriFace> &faces = m_mesh.FaceSet(); + vector<MT_Vector3> & normals = m_normals.Ref(); + + int face_num = faces.size(); + int cur_face = 0; + + for (; cur_face < face_num; ++cur_face) { + + MT_Vector3 new_normal = ComputeNormal(faces[cur_face]); + normals.push_back(new_normal); + } + // now build the vertex normals + + vector<MT_Vector3> & vertex_normals = m_vertex_normals.Ref(); + const vector<LOD_Vertex> &verts = m_mesh.VertexSet(); + + int vertex_num = verts.size(); + int cur_vertex = 0; + + for (; cur_vertex < vertex_num; ++cur_vertex) { + MT_Vector3 new_normal = ComputeVertexNormal(cur_vertex); + vertex_normals.push_back(new_normal); + } +} + +const + MT_Vector3 +LOD_FaceNormalEditor:: +ComputeNormal( + const LOD_TriFace &face +) const { + + const vector<LOD_Vertex> &verts = m_mesh.VertexSet(); + + MT_Vector3 vec1 = + verts[face.m_verts[1]].pos - + verts[face.m_verts[0]].pos; + + MT_Vector3 vec2 = + verts[face.m_verts[2]].pos - + verts[face.m_verts[1]].pos; + + vec1 = vec1.cross(vec2); + + if (!vec1.fuzzyZero()) { + vec1.normalize(); + return (vec1); + } else { + return (MT_Vector3(1.0,0,0)); + } +} + +const + MT_Vector3 +LOD_FaceNormalEditor:: +ComputeVertexNormal( + const LOD_VertexInd v +) const { + + // average the face normals surrounding this + // vertex and normalize + const vector<MT_Vector3> & face_normals = m_normals.Ref(); + + vector<LOD_FaceInd> vertex_faces; + vertex_faces.reserve(32); + + m_mesh.VertexFaces(v,vertex_faces); + + MT_Vector3 normal(0,0,0); + + vector<LOD_FaceInd>::const_iterator face_it = vertex_faces.begin(); + vector<LOD_FaceInd>::const_iterator face_end = vertex_faces.end(); + + for (; face_it != face_end; ++face_it) { + normal += face_normals[*face_it]; + } + + if (!normal.fuzzyZero()) { + normal.normalize(); + return (normal); + } else { + return (MT_Vector3(1.0,0,0)); + } +} + + + + + + + + + + + + + + + + + + + + diff --git a/intern/decimation/intern/LOD_FaceNormalEditor.h b/intern/decimation/intern/LOD_FaceNormalEditor.h new file mode 100644 index 00000000000..345dc4f8246 --- /dev/null +++ b/intern/decimation/intern/LOD_FaceNormalEditor.h @@ -0,0 +1,143 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_FaceNormalEditor_h + +#define NAN_INCLUDED_FaceNormalEditor_h + +#include "MEM_NonCopyable.h" +#include "LOD_ManMesh2.h" +#include "MT_Vector3.h" + + +class LOD_FaceNormalEditor : public MEM_NonCopyable +{ + +public : + + // Creation + /////////// + + static + LOD_FaceNormalEditor * + New( + LOD_ManMesh2 &mesh + ); + + // Property editor interface + //////////////////////////// + + + // Faces + //////// + void + Remove( + std::vector<LOD_FaceInd> &sorted_faces + ); + + void + Add( + ); + + void + Update( + std::vector<LOD_FaceInd> &sorted_faces + ); + + + // vertex normals + ///////////////// + + void + RemoveVertexNormals( + std::vector<LOD_VertexInd> &sorted_verts + ); + + + void + UpdateVertexNormals( + std::vector<LOD_VertexInd> &sorted_verts + ); + + + + const + std::vector<MT_Vector3> & + Normals( + ) const { + return m_normals.Ref(); + }; + + + const + std::vector<MT_Vector3> & + VertexNormals( + ) const { + return m_vertex_normals.Ref(); + }; + + // Editor specific methods + ////////////////////////// + + void + BuildNormals( + ); + + +private : + + MEM_SmartPtr<std::vector<MT_Vector3> > m_normals; + MEM_SmartPtr<std::vector<MT_Vector3> > m_vertex_normals; + + LOD_ManMesh2 &m_mesh; + +private : + + + LOD_FaceNormalEditor(LOD_ManMesh2 &mesh); + + const + MT_Vector3 + ComputeNormal( + const LOD_TriFace &face + ) const ; + + const + MT_Vector3 + ComputeVertexNormal ( + const LOD_VertexInd vi + ) const; + + + +}; + +#endif 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); +}; + + + + + + + + + + + + + + + + diff --git a/intern/decimation/intern/LOD_ManMesh2.h b/intern/decimation/intern/LOD_ManMesh2.h new file mode 100644 index 00000000000..e208155c1f0 --- /dev/null +++ b/intern/decimation/intern/LOD_ManMesh2.h @@ -0,0 +1,264 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_ManMesh2_h + +#define NAN_INCLUDED_ManMesh2_h + +#include "LOD_MeshPrimitives.h" +#include "MEM_SmartPtr.h" +#include <vector> + +template <class HeapType> class CTR_UHeap; + +class LOD_ExternBufferEditor; + +class LOD_ManMesh2 // Manifold 2 dimensional mesh +{ + +public: + + static + LOD_ManMesh2 * + New( + ); + + // take ownership of the vertices. + + bool + SetVertices( + MEM_SmartPtr<std::vector<LOD_Vertex> > verts + ); + + // Add a triangle to the mesh + + void + AddTriangle( + int verts[3] + ); + + void + ConnectTriangle( + LOD_FaceInd fi, + std::vector<LOD_EdgeInd> & new_edges + ); + + // geometry access + ////////////////// + + std::vector<LOD_Vertex> & + VertexSet( + ) const ; + + std::vector<LOD_TriFace> & + FaceSet( + ) const ; + + std::vector<LOD_Edge> & + EdgeSet( + ) const; + + ~LOD_ManMesh2( + ); + + // local geometry queries + ///////////////////////// + + // face queries + /////////////// + + void + FaceVertices( + LOD_FaceInd f, + std::vector<LOD_VertexInd> &output + ); + + void + FaceEdges( + LOD_FaceInd f, + std::vector<LOD_EdgeInd> &output + ); + + // edge queries + /////////////// + + void + EdgeVertices( + LOD_EdgeInd e, + std::vector<LOD_VertexInd> &output + ); + + void + EdgeFaces( + LOD_EdgeInd e, + std::vector<LOD_FaceInd> &output + ); + + // vertex queries + ///////////////// + + void + VertexEdges( + LOD_VertexInd v, + std::vector<LOD_EdgeInd> &output + ); + + void + VertexFaces( + LOD_VertexInd v, + std::vector<LOD_FaceInd> &output + ); + + void + SetBBox( + MT_Vector3 bbox_min, + MT_Vector3 bbox_max + ); + + MT_Vector3 + BBoxMin( + ) const { + return m_bbox_min; + }; + + MT_Vector3 + BBoxMax( + ) const { + return m_bbox_max; + }; + + // Remove a primitive from the mesh + /////////////////////////////////// + + // These methods assume you have correctly + // tidied up the index pointers in other primitives, + // so that nothing refers to this object any more + + // These methods exchange the primitive with the + // last primitive in the vector. It modifies everything + // pointing to the last primitive correctly. + + // FIXME refactor extern editor out of primitive deletion + // insead return a vector of primitives that need to be + // modified and do this externally + + void + DeleteVertex( + LOD_ExternBufferEditor & extern_editor, + LOD_VertexInd v + ); + + void + DeleteEdge( + LOD_EdgeInd e, + CTR_UHeap<LOD_Edge> *heap + ); + + void + DeleteFace( + LOD_ExternBufferEditor & extern_editor, + LOD_FaceInd f + ); + + // Sanity Check routines + //////////////////////// + + // Make sure the edge sets and the vertex sets are + // consistent + + void + SC_TriFace( + LOD_FaceInd f + ); + + // basic sanity checking of an edge list bails out if there are more than 1024 + // edges + + void + SC_EdgeList( + LOD_EdgeInd e + ); + + + // Check to see that the edges of v1 and v2 are unique. + + bool + SC_UniqueEdge( + LOD_EdgeInd e + ); + + +private : + + + // Returns the edge index of the edge from v1 to v2. + // Does this by searching the edge sets of v1 - but not v2. + // If you are paranoid you should check both and make sure the + // indices are the same. If the edge doe not exist edgeInd is empty. + + LOD_EdgeInd + FindEdge( + const LOD_VertexInd v1, + const LOD_VertexInd v2 + ); + + // Insert an edge into the mesh + // Tie up the ptrs and create space for the edge + // returns manifold errors - need to sort out memory edges + + bool + InsertEdge( + const LOD_VertexInd v1, + const LOD_VertexInd v2, + const LOD_FaceInd f, + std::vector<LOD_EdgeInd> &new_edges + ); + + +private : + + LOD_ManMesh2( + ); + + MEM_SmartPtr< std::vector<LOD_Vertex> > m_verts; + MEM_SmartPtr< std::vector<LOD_TriFace> > m_faces; + MEM_SmartPtr< std::vector<LOD_Edge> > m_edges; + + // not sure of these descrtiptions of the mesh should + // reside in this class coz may lead to very bloated interface. + + MT_Vector3 m_bbox_min; + MT_Vector3 m_bbox_max; + + +}; + +#endif
\ No newline at end of file diff --git a/intern/decimation/intern/LOD_MeshBounds.h b/intern/decimation/intern/LOD_MeshBounds.h new file mode 100644 index 00000000000..bb74bdb3945 --- /dev/null +++ b/intern/decimation/intern/LOD_MeshBounds.h @@ -0,0 +1,134 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_MeshBounds_h + +#define NAN_INCLUDED_MeshBounds_h + + +#include "MEM_SmartPtr.h" +#include "LOD_MeshPrimitives.h" +#include "LOD_ManMesh2.h" +#include "MT_assert.h" + +// simple class to compute the mesh bounds of a manifold mesh, + +class LOD_MeshBounds { + +public : + static + LOD_MeshBounds * + New( + ){ + + MEM_SmartPtr<LOD_MeshBounds> output(new LOD_MeshBounds()); + return output.Release(); + } + + void + ComputeBounds( + const LOD_ManMesh2 * mesh + ){ + MT_assert(mesh!=NULL); + MT_assert(mesh->VertexSet().size() > 0); + + const std::vector<LOD_Vertex> &verts = mesh->VertexSet(); + + m_min = verts[0].pos; + m_max = verts[0].pos; + + // iterate through the verts + + int t; + const int size = verts.size(); + + for (t=1; t< size ; ++t) { + + UpdateBounds(verts[t].pos,m_min,m_max); + } + } + + MT_Vector3 + Min( + ) const { + return m_min; + } + + MT_Vector3 + Max( + ) const { + return m_max; + } + +private : + + void + UpdateBounds( + MT_Vector3 vertex, + MT_Vector3& min, + MT_Vector3& max + ) { + if (vertex.x() < min.x()) { + min.x() = vertex.x(); + } else + if (vertex.x() > max.x()) { + max.x()= vertex.x(); + } + + if (vertex.y() < min.y()) { + min.y() = vertex.y(); + } else + if (vertex.y() > max.y()) { + max.y()= vertex.y(); + } + + if (vertex.z() < min.z()) { + min.z() = vertex.z(); + } else + if (vertex.z() > max.z()) { + max.z()= vertex.z(); + } + } + + LOD_MeshBounds( + ) : + m_min(0,0,0), + m_max(0,0,0) + { + }; + + MT_Vector3 m_min; + MT_Vector3 m_max; + +}; + + +#endif diff --git a/intern/decimation/intern/LOD_MeshException.h b/intern/decimation/intern/LOD_MeshException.h new file mode 100644 index 00000000000..4f0b8f99c38 --- /dev/null +++ b/intern/decimation/intern/LOD_MeshException.h @@ -0,0 +1,55 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_MeshExceptions_h + +#define NAN_INCLUDED_MeshExceptions_h + + +class LOD_MeshException { + +public : + + // stick in more error types as you think of them + + enum ExceptionType{ + e_non_manifold, + e_search_error + } m_e_type; + + LOD_MeshException ( + ExceptionType type + ) : m_e_type (type) + { + } +}; + +#endif diff --git a/intern/decimation/intern/LOD_MeshPrimitives.cpp b/intern/decimation/intern/LOD_MeshPrimitives.cpp new file mode 100644 index 00000000000..147e107cb4b --- /dev/null +++ b/intern/decimation/intern/LOD_MeshPrimitives.cpp @@ -0,0 +1,407 @@ +/** + * $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_MeshPrimitives.h" + +#include "MT_assert.h" +#include "LOD_MeshException.h" +#include <algorithm> + +using namespace std; + +// Vertex Methods +///////////////// + +LOD_Vertex:: +LOD_Vertex( +) : + pos (MT_Vector3()), + m_select_tag(false) +{ +}; + + bool +LOD_Vertex:: +RemoveEdge( + LOD_EdgeInd e +){ + + vector<LOD_EdgeInd>::iterator result = find(m_edges.begin(),m_edges.end(),e); + if (result == m_edges.end()) { + return false; + } + LOD_EdgeInd last = m_edges.back(); + m_edges.pop_back(); + if (m_edges.empty()) return true; + + *result = last; + return true; +}; + + void +LOD_Vertex:: +AddEdge( + LOD_EdgeInd e +){ + m_edges.push_back(e); +}; + + void +LOD_Vertex:: +SwapEdge( + LOD_EdgeInd e_old, + LOD_EdgeInd e_new +){ + + vector<LOD_EdgeInd>::iterator result = + find(m_edges.begin(),m_edges.end(),e_old); + if (result == m_edges.end()) { + MT_assert(false); + LOD_MeshException e(LOD_MeshException::e_search_error); + throw(e); + } + + *result = e_new; +}; + + bool +LOD_Vertex:: +SelectTag( +) const { + return m_select_tag; +}; + + void +LOD_Vertex:: +SetSelectTag( + bool tag +){ + m_select_tag = tag; +}; + + bool +LOD_Vertex:: +Degenerate( +){ + return m_edges.empty(); +} + + void +LOD_Vertex:: +CopyPosition( + float *float_ptr +){ + pos.getValue(float_ptr); +} + + + +// Edge Methods +/////////////// + +LOD_Edge:: +LOD_Edge ( +) { + m_verts[0] = m_verts[1] = LOD_VertexInd::Empty(); + m_faces[0] = m_faces[1] = LOD_FaceInd::Empty(); +} + + bool +LOD_Edge:: +operator == ( + LOD_Edge & rhs +) { + // edges are the same if their vertex indices are the + // same!!! Other properties are not checked + + int matches = 0; + + if (this->m_verts[0] == rhs.m_verts[0]) { + ++matches; + } + if (this->m_verts[1] == rhs.m_verts[0]) { + ++matches; + } + if (this->m_verts[0] == rhs.m_verts[1]) { + ++matches; + } + if (this->m_verts[1] == rhs.m_verts[1]) { + ++matches; + } + + if (matches >= 2) { + return true; + } + return false; +} + +// Elementary helper methods +//////////////////////////// + + LOD_FaceInd +LOD_Edge:: +OpFace( + LOD_FaceInd f +) const { + if (f == m_faces[0]) { + return m_faces[1]; + } else + if (f == m_faces[1]) { + return m_faces[0]; + } else { + MT_assert(false); + LOD_MeshException e(LOD_MeshException::e_search_error); + throw(e); + + return LOD_FaceInd::Empty(); + } +} + + void +LOD_Edge:: +SwapFace( + LOD_FaceInd old_f, + LOD_FaceInd new_f +) { + if (old_f == m_faces[0]) { + m_faces[0] = new_f; + } else + if (old_f == m_faces[1]) { + m_faces[1] = new_f; + } else { + MT_assert(false); + + LOD_MeshException e(LOD_MeshException::e_search_error); + throw(e); + } +} + + +// return the half edge face - the half edge is defined +// by the {vertex,edge} tuple. + + LOD_FaceInd +LOD_Edge:: +HalfEdgeFace( + LOD_VertexInd vi +){ + if (vi == m_verts[0]) return m_faces[0]; + if (vi == m_verts[1]) return m_faces[1]; + MT_assert(false); + + LOD_MeshException e(LOD_MeshException::e_search_error); + throw(e); + + return LOD_FaceInd::Empty(); +} + + + LOD_VertexInd +LOD_Edge:: +OpVertex( + LOD_VertexInd vi +) { + if (vi == m_verts[0]) return m_verts[1]; + if (vi == m_verts[1]) return m_verts[0]; + MT_assert(false); + + LOD_MeshException e(LOD_MeshException::e_search_error); + throw(e); + + return LOD_VertexInd::Empty(); +} + +// replace the vertex v_old with vertex v_new +// error if v_old is not one of the original vertices + + void +LOD_Edge:: +SwapVertex( + LOD_VertexInd v_old, + LOD_VertexInd v_new +) { + if (v_old == m_verts[0]) { + m_verts[0] = v_new; + } else + if (v_old == m_verts[1]) { + m_verts[1] = v_new; + } else { + + MT_assert(false); + + LOD_MeshException e(LOD_MeshException::e_search_error); + throw(e); + } + if(m_verts[0] == m_verts[1]) { + MT_assert(false); + + LOD_MeshException e(LOD_MeshException::e_non_manifold); + throw(e); + } + +} + + bool +LOD_Edge:: +SelectTag( +) const { + return bool(m_verts[1].Tag() & 0x1); +}; + + void +LOD_Edge:: +SetSelectTag( + bool tag +) { + m_verts[1].SetTag(int(tag)); +}; + + int +LOD_Edge:: +OpenTag( +) const { + return m_faces[0].Tag(); +} + + void +LOD_Edge:: +SetOpenTag( + int tag +) { + m_faces[0].SetTag(tag); +} + + bool +LOD_Edge:: +Degenerate( +) const { + return ( + (m_faces[0].IsEmpty() && m_faces[1].IsEmpty()) || + (m_verts[0] == m_verts[1]) + ); +}; + +// TriFace Methods +////////////////// + +LOD_TriFace:: +LOD_TriFace( +) { + m_verts[0] = m_verts[1] = m_verts[2] = LOD_VertexInd::Empty(); +} + +// Elementary helper methods +//////////////////////////// + + void +LOD_TriFace:: +SwapVertex( + LOD_VertexInd old_v, + LOD_VertexInd new_v +) { + // could save branching here... + + if (m_verts[0] == old_v) { + m_verts[0] = new_v; + } else + if (m_verts[1] == old_v) { + m_verts[1] = new_v; + } else + if (m_verts[2] == old_v) { + m_verts[2] = new_v; + } else { + MT_assert(false); + + LOD_MeshException excep(LOD_MeshException::e_search_error); + throw(excep); + } +} + + bool +LOD_TriFace:: +SelectTag( +) const { + return bool(m_verts[1].Tag() & 0x1); +}; + + void +LOD_TriFace:: +SetSelectTag( + bool tag +) { + m_verts[1].SetTag(int(tag)); +}; + + int +LOD_TriFace:: +OpenTag( +) { + return m_verts[2].Tag(); +} + + void +LOD_TriFace:: +SetOpenTag( + int tag +) { + m_verts[2].SetTag(tag); +} + + bool +LOD_TriFace:: +Degenerate( +) { + + return ( + (m_verts[0] == m_verts[1]) || + (m_verts[1] == m_verts[2]) || + (m_verts[2] == m_verts[0]) + ); +} + + void +LOD_TriFace:: +CopyVerts( + int * index_ptr +){ + index_ptr[0] = m_verts[0]; + index_ptr[1] = m_verts[1]; + index_ptr[2] = m_verts[2]; +}; + + + + + + + + + diff --git a/intern/decimation/intern/LOD_MeshPrimitives.h b/intern/decimation/intern/LOD_MeshPrimitives.h new file mode 100644 index 00000000000..12214c7528d --- /dev/null +++ b/intern/decimation/intern/LOD_MeshPrimitives.h @@ -0,0 +1,221 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_MeshPrimitives_h + +#define NAN_INCLUDED_MeshPrimitives_h + +#include "MT_Vector3.h" +#include "CTR_TaggedIndex.h" +#include "CTR_UHeap.h" +#include <vector> + +typedef CTR_TaggedIndex<24,0x00ffffff> LOD_VertexInd; +typedef CTR_TaggedIndex<24,0x00ffffff> LOD_EdgeInd; +typedef CTR_TaggedIndex<24,0x00ffffff> LOD_FaceInd; +typedef CTR_TaggedIndex<24,0x00ffffff> LOD_HeapInd; + +class LOD_Vertex { +public : + MT_Vector3 pos; + std::vector<LOD_EdgeInd> m_edges; + bool m_select_tag; + + LOD_Vertex( + ) ; + + bool + RemoveEdge( + LOD_EdgeInd e + ); + + void + AddEdge( + LOD_EdgeInd e + ); + + void + SwapEdge( + LOD_EdgeInd e_old, + LOD_EdgeInd e_new + ); + + bool + SelectTag( + ) const; + + void + SetSelectTag( + bool tag + ); + + bool + Degenerate( + ); + + void + CopyPosition( + float *float_ptr + ); + +private : + + +}; + +class LOD_Edge : public CTR_UHeapable { +public : + LOD_VertexInd m_verts[2]; + LOD_FaceInd m_faces[2]; + + LOD_Edge ( + ); + + bool operator == ( + LOD_Edge & rhs + ); + + // Elementary helper methods + //////////////////////////// + + LOD_FaceInd + OpFace( + LOD_FaceInd f + ) const ; + + void + SwapFace( + LOD_FaceInd old_f, + LOD_FaceInd new_f + ) ; + + + // return the half edge face - the half edge is defined + // by the {vertex,edge} tuple. + + LOD_FaceInd + HalfEdgeFace( + LOD_VertexInd vi + ); + + + LOD_VertexInd + OpVertex( + LOD_VertexInd vi + ); + + // replace the vertex v_old with vertex v_new + // error if v_old is not one of the original vertices + + void + SwapVertex( + LOD_VertexInd v_old, + LOD_VertexInd v_new + ) ; + + bool + SelectTag( + ) const ; + + void + SetSelectTag( + bool tag + ); + + int + OpenTag( + ) const; + + void + SetOpenTag( + int tag + ) ; + + bool + Degenerate( + ) const; + + bool + BoundaryEdge( + ) const { + return (m_faces[0].IsEmpty() || m_faces[1].IsEmpty()); + }; + + +}; + +class LOD_TriFace { +public: + + LOD_VertexInd m_verts[3]; + + LOD_TriFace( + ); + + // Elementary helper methods + //////////////////////////// + + void + SwapVertex( + LOD_VertexInd old_v, + LOD_VertexInd new_v + ); + + bool + SelectTag( + ) const; + + void + SetSelectTag( + bool tag + ); + + int + OpenTag( + ); + void + SetOpenTag( + int tag + ); + + bool + Degenerate( + ); + + void + CopyVerts( + int * index_ptr + ); + +}; + +#endif + diff --git a/intern/decimation/intern/LOD_QSDecimator.cpp b/intern/decimation/intern/LOD_QSDecimator.cpp new file mode 100644 index 00000000000..6620fa15ad3 --- /dev/null +++ b/intern/decimation/intern/LOD_QSDecimator.cpp @@ -0,0 +1,324 @@ +/** + * $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_QSDecimator.h" + +#include "LOD_ExternBufferEditor.h" + +using namespace std; + + LOD_QSDecimator * +LOD_QSDecimator:: +New( + LOD_ManMesh2 &mesh, + LOD_ExternNormalEditor &face_editor, + LOD_ExternBufferEditor &extern_editor +){ + + MEM_SmartPtr<LOD_QSDecimator> output + = new LOD_QSDecimator(mesh,face_editor,extern_editor); + + MEM_SmartPtr<LOD_EdgeCollapser > collapser(LOD_EdgeCollapser::New()); + MEM_SmartPtr<LOD_QuadricEditor> q_editor(LOD_QuadricEditor::New(mesh)); + + if ( + output == NULL || + collapser == NULL || + q_editor == NULL + ) { + return NULL; + } + output->m_collapser = collapser.Release(); + output->m_quadric_editor = q_editor.Release(); + return output.Release(); +} + + + + bool +LOD_QSDecimator:: +Arm( +){ + MT_assert(!m_is_armed); + bool heap_result = BuildHeap(); + if (!heap_result) { + return false; + } + m_is_armed = true; + return true; +} + + bool +LOD_QSDecimator:: +Step( +){ + return CollapseEdge(); +} + + +LOD_QSDecimator:: +LOD_QSDecimator( + LOD_ManMesh2 &mesh, + LOD_ExternNormalEditor &face_editor, + LOD_ExternBufferEditor &extern_editor +) : + m_mesh(mesh), + m_face_editor(face_editor), + m_extern_editor(extern_editor), + m_is_armed (false) +{ + m_deg_edges.reserve(32); + m_deg_faces.reserve(32); + m_deg_vertices.reserve(32); + m_update_faces.reserve(32); + m_new_edges.reserve(32); + m_update_vertices.reserve(32); +}; + + bool +LOD_QSDecimator:: +CollapseEdge( +){ + + // find an edge to collapse + + // FIXME force an edge collapse + // or return false + + std::vector<LOD_Edge> & edges = m_mesh.EdgeSet(); + std::vector<LOD_Vertex> & verts = m_mesh.VertexSet(); + std::vector<LOD_Quadric> & quadrics = m_quadric_editor->Quadrics(); + int size = edges.size(); + + if (size == 0) return false; + + const int heap_top = m_heap->Top(); + + if (heap_top == -1 || edges[heap_top].HeapKey() <= -MT_INFINITY) { + return false; + } + + // compute the target position + MT_Vector3 new_vertex = m_quadric_editor->TargetVertex(edges[heap_top]); + LOD_Quadric & q0 = quadrics[edges[heap_top].m_verts[0]]; + LOD_Quadric & q1 = quadrics[edges[heap_top].m_verts[1]]; + + LOD_Vertex &v0 = verts[edges[heap_top].m_verts[0]]; + LOD_Vertex &v1 = verts[edges[heap_top].m_verts[1]]; + + LOD_Quadric sum = q0; + sum += q1; + + + if (m_collapser->CollapseEdge( + heap_top, + m_mesh, + m_deg_edges, + m_deg_faces, + m_deg_vertices, + m_new_edges, + m_update_faces, + m_update_vertices + )) { + + // assign new vertex position + + v0.pos = new_vertex; + v1.pos = new_vertex; + + // sum the quadrics of v0 and v1 + q0 = sum; + q1 = sum; + + // ok update the primitive properties + + m_face_editor.Update(m_update_faces); + m_face_editor.UpdateVertexNormals(m_update_vertices); + + // update the external vertex buffer + m_extern_editor.CopyModifiedVerts(m_mesh,m_update_vertices); + + // update the external face buffer + m_extern_editor.CopyModifiedFaces(m_mesh,m_update_faces); + + // update the edge heap + UpdateHeap(m_deg_edges,m_new_edges); + + m_quadric_editor->Remove(m_deg_vertices); + m_face_editor.Remove(m_deg_faces); + m_face_editor.RemoveVertexNormals(m_deg_vertices); + + // delete the primitives + + DeletePrimitives(m_deg_edges,m_deg_faces,m_deg_vertices); + + } else { + // the edge could not be collapsed at the moment - so + // we adjust it's priority and add it back to the heap. + m_heap->Remove(edges.begin(),0); + edges[heap_top].HeapKey() = - MT_INFINITY; + m_heap->Insert(edges.begin(),heap_top); + } + + //clear all the temporary buffers + + m_deg_faces.clear(); + m_deg_edges.clear(); + m_deg_vertices.clear(); + + m_update_faces.clear(); + m_update_vertices.clear(); + m_new_edges.clear(); + + return true; + +} + + void +LOD_QSDecimator:: +DeletePrimitives( + const vector<LOD_EdgeInd> & degenerate_edges, + const vector<LOD_FaceInd> & degenerate_faces, + const vector<LOD_VertexInd> & degenerate_vertices +) { + + // assumes that the 3 vectors are sorted in descending order. + + // Delete Degnerate primitives + ////////////////////////////// + + + // delete the old edges - we have to be very careful here + // mesh.delete() swaps edges to be deleted with the last edge in + // the edge buffer. However the next edge to be deleted may have + // been the last edge in the buffer! + + // One way to solve this is to sort degenerate_edges in descending order. + // And then delete them in that order. + + // it is also vital that degenerate_edges contains no duplicates + + vector<LOD_EdgeInd>::const_iterator edge_it = degenerate_edges.begin(); + vector<LOD_EdgeInd>::const_iterator edge_end = degenerate_edges.end(); + + for (; edge_it != edge_end; ++edge_it) { + m_mesh.DeleteEdge(*edge_it,m_heap); + } + + + + vector<LOD_FaceInd>::const_iterator face_it = degenerate_faces.begin(); + vector<LOD_FaceInd>::const_iterator face_end = degenerate_faces.end(); + + for (;face_it != face_end; ++face_it) { + m_mesh.DeleteFace(m_extern_editor,*face_it); + } + + vector<LOD_VertexInd>::const_iterator vertex_it = degenerate_vertices.begin(); + vector<LOD_VertexInd>::const_iterator vertex_end = degenerate_vertices.end(); + + for (;vertex_it != vertex_end; ++vertex_it) { + m_mesh.DeleteVertex(m_extern_editor,*vertex_it); + } +} + + + bool +LOD_QSDecimator:: +BuildHeap( +){ + // build the quadrics + + if (m_quadric_editor->BuildQuadrics(m_face_editor,true) == false) return false; + + + m_heap = CTR_UHeap<LOD_Edge>::New(); + // load in edge pointers to the heap + + std::vector<LOD_Edge> & edge_set= m_mesh.EdgeSet(); + std::vector<LOD_Edge>::const_iterator edge_end = edge_set.end(); + std::vector<LOD_Edge>::iterator edge_start = edge_set.begin(); + + std::vector<int> & heap_vector = m_heap->HeapVector(); + + for (int i = 0; i < edge_set.size(); ++i) { + edge_set[i].HeapPos() = i; + heap_vector.push_back(i); + } + + m_heap->MakeHeap(edge_set.begin()); + + return true; +} + + void +LOD_QSDecimator:: +UpdateHeap( + std::vector<LOD_EdgeInd> °_edges, + std::vector<LOD_EdgeInd> &new_edges +){ + // first of all compute values for the new edges + // and bung them on the heap. + + std::vector<LOD_Edge> & edge_set= m_mesh.EdgeSet(); + + std::vector<LOD_EdgeInd>::const_iterator edge_it = new_edges.begin(); + std::vector<LOD_EdgeInd>::const_iterator end_it = new_edges.end(); + + + // insert all the new edges + /////////////////////////// + + // compute edge costs ffor the new edges + + m_quadric_editor->ComputeEdgeCosts(new_edges); + + // inser the new elements into the heap + + for (; edge_it != end_it; ++edge_it) { + m_heap->Insert(edge_set.begin(),*edge_it); + } + + + // remove all the old values from the heap + + edge_it = deg_edges.begin(); + end_it = deg_edges.end(); + + for (; edge_it != end_it; ++edge_it) { + LOD_Edge &e = edge_set[*edge_it]; + m_heap->Remove(edge_set.begin(),e.HeapPos()); + + e.HeapPos() = 0xffffffff; + + } +} + diff --git a/intern/decimation/intern/LOD_QSDecimator.h b/intern/decimation/intern/LOD_QSDecimator.h new file mode 100644 index 00000000000..c5ae915db29 --- /dev/null +++ b/intern/decimation/intern/LOD_QSDecimator.h @@ -0,0 +1,128 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_LOD_QSDecimator_H + +#define NAN_INCLUDED_LOD_QSDecimator_H + +#include "MEM_NonCopyable.h" +#include "LOD_ManMesh2.h" +#include "LOD_ExternNormalEditor.h" +#include "LOD_EdgeCollapser.h" +#include "LOD_QuadricEditor.h" + +class LOD_ExternBufferEditor; + +class LOD_QSDecimator : public MEM_NonCopyable { + +public : + + static + LOD_QSDecimator * + New( + LOD_ManMesh2 &mesh, + LOD_ExternNormalEditor &face_editor, + LOD_ExternBufferEditor &extern_editor + ); + + + bool + Arm( + ); + + + bool + Step( + ); + +private : + + LOD_QSDecimator( + LOD_ManMesh2 &mesh, + LOD_ExternNormalEditor &face_editor, + LOD_ExternBufferEditor &extern_editor + ); + + bool + CollapseEdge( + ); + + bool + BuildHeap( + ); + + void + UpdateHeap( + std::vector<LOD_EdgeInd> °_edges, + std::vector<LOD_EdgeInd> &new_edges + ); + + void + DeletePrimitives( + const std::vector<LOD_EdgeInd> & degenerate_edges, + const std::vector<LOD_FaceInd> & degenerate_faces, + const std::vector<LOD_VertexInd> & degenerate_vertices + ); + + +private : + + // owned by this class + ////////////////////// + + MEM_SmartPtr<LOD_EdgeCollapser> m_collapser; + MEM_SmartPtr<CTR_UHeap<LOD_Edge> > m_heap; + MEM_SmartPtr<LOD_QuadricEditor> m_quadric_editor; + + bool m_is_armed; + + // arguments to New(...) + //////////////////////// + + LOD_ManMesh2 & m_mesh; + LOD_ExternNormalEditor &m_face_editor; + LOD_ExternBufferEditor & m_extern_editor; + + // temporary buffers + //////////////////// + + std::vector<LOD_FaceInd> m_deg_faces; + std::vector<LOD_EdgeInd> m_deg_edges; + std::vector<LOD_VertexInd> m_deg_vertices; + + std::vector<LOD_FaceInd> m_update_faces; + std::vector<LOD_EdgeInd> m_new_edges; + std::vector<LOD_VertexInd> m_update_vertices; + + +}; +#endif + diff --git a/intern/decimation/intern/LOD_Quadric.h b/intern/decimation/intern/LOD_Quadric.h new file mode 100644 index 00000000000..16e7dec17e9 --- /dev/null +++ b/intern/decimation/intern/LOD_Quadric.h @@ -0,0 +1,168 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_LOD_Quadric_h + +#define NAN_INCLUDED_LOD_Quadric_h + +#include "MT_Vector3.h" +#include "MT_Matrix3x3.h" + + +class LOD_Quadric { + +private: + MT_Scalar a2, ab, ac, ad; + MT_Scalar b2, bc, bd; + MT_Scalar c2, cd; + MT_Scalar d2; + + void init(MT_Scalar a, MT_Scalar b, MT_Scalar c, MT_Scalar d); + +public: + + LOD_Quadric( + ) { + Clear(); + }; + + LOD_Quadric( + const MT_Vector3 & vec, + const MT_Scalar & offset + ) { + a2 = vec[0] *vec[0]; + b2 = vec[1] *vec[1]; + c2 = vec[2] *vec[2]; + + ab = vec[0]*vec[1]; + ac = vec[0]*vec[2]; + bc = vec[1]*vec[2]; + + MT_Vector3 temp = vec*offset; + ad = temp[0]; + bd = temp[1]; + cd = temp[2]; + + d2 = offset*offset; + }; + + MT_Matrix3x3 + Tensor( + ) const { + // return a symmetric matrix + + return MT_Matrix3x3( + a2,ab,ac, + ab,b2,bc, + ac,bc,c2 + ); + }; + + + MT_Vector3 + Vector( + ) const { + return MT_Vector3(ad, bd, cd); + }; + + void + Clear( + MT_Scalar val=0.0 + ) { + a2=ab=ac=ad=b2=bc=bd=c2=cd=d2=val; + }; + + LOD_Quadric & + operator=( + const LOD_Quadric& Q + ) { + + a2 = Q.a2; ab = Q.ab; ac = Q.ac; ad = Q.ad; + b2 = Q.b2; bc = Q.bc; bd = Q.bd; + c2 = Q.c2; cd = Q.cd; + d2 = Q.d2; + return *this; + }; + + LOD_Quadric& + operator+=( + const LOD_Quadric& Q + ) { + a2 += Q.a2; ab += Q.ab; ac += Q.ac; ad += Q.ad; + b2 += Q.b2; bc += Q.bc; bd += Q.bd; + c2 += Q.c2; cd += Q.cd; + d2 += Q.d2; + return *this; + }; + + LOD_Quadric& + operator*=( + const MT_Scalar & s + ) { + a2 *= s; ab *= s; ac *= s; ad *= s; + b2 *= s; bc *= s; bd *= s; + c2 *= s; cd *= s; + d2 *= s; + return *this; + }; + + + MT_Scalar + Evaluate( + const MT_Vector3 &v + ) const { + // compute the LOD_Quadric error + + return v[0]*v[0]*a2 + 2*v[0]*v[1]*ab + 2*v[0]*v[2]*ac + 2*v[0]*ad + +v[1]*v[1]*b2 + 2*v[1]*v[2]*bc + 2*v[1]*bd + +v[2]*v[2]*c2 + 2*v[2]*cd + + d2; + }; + + bool + Optimize( + MT_Vector3& v + ) const { + + MT_Scalar det = Tensor().determinant(); + if (MT_fuzzyZero(det)) { + return false; + } + + v = -((Tensor().inverse()) * Vector()); + return true; + }; + +}; + + +#endif + diff --git a/intern/decimation/intern/LOD_QuadricEditor.cpp b/intern/decimation/intern/LOD_QuadricEditor.cpp new file mode 100644 index 00000000000..751f5d1e7e0 --- /dev/null +++ b/intern/decimation/intern/LOD_QuadricEditor.cpp @@ -0,0 +1,279 @@ +/** + * $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_QuadricEditor.h" + +#include "LOD_ExternNormalEditor.h" + +// Creation +/////////// + +using namespace std; + + +LOD_QuadricEditor:: +LOD_QuadricEditor( + LOD_ManMesh2 &mesh +) : + m_quadrics(NULL), + m_mesh(mesh) +{ +}; + + LOD_QuadricEditor * +LOD_QuadricEditor:: +New( + LOD_ManMesh2 &mesh +){ + //same number of quadrics as vertices in the mesh + + MEM_SmartPtr<LOD_QuadricEditor> output(new LOD_QuadricEditor(mesh)); + + if (output == NULL) { + return NULL; + } + return output.Release(); +} + + +// Property editor interface +//////////////////////////// + + void +LOD_QuadricEditor:: +Remove( + std::vector<LOD_VertexInd> &sorted_vertices +){ + vector<LOD_Quadric> & quadrics = *m_quadrics; + + vector<LOD_VertexInd>::const_iterator it_start = sorted_vertices.begin(); + vector<LOD_VertexInd>::const_iterator it_end = sorted_vertices.end(); + + for (; it_start != it_end; ++it_start) { + + if (quadrics.size() > 0) { + LOD_Quadric temp = quadrics[*it_start]; + + quadrics[*it_start] = quadrics.back(); + quadrics.back() = temp; + + quadrics.pop_back(); + } + } +}; + + +// Editor specific methods +////////////////////////// + + bool +LOD_QuadricEditor:: +BuildQuadrics( + LOD_ExternNormalEditor& normal_editor, + bool preserve_boundaries +){ + if (m_quadrics != NULL) delete(m_quadrics); + + m_quadrics =new vector<LOD_Quadric> (m_mesh.VertexSet().size()); + if (m_quadrics == NULL) return false; + + // iterate through the face set of the mesh + // compute a quadric based upon that face and + // add it to each of it's vertices quadrics. + + const vector<LOD_TriFace> &faces = m_mesh.FaceSet(); + const vector<LOD_Vertex> &verts = m_mesh.VertexSet(); + vector<LOD_Edge> &edges = m_mesh.EdgeSet(); + + const vector<MT_Vector3> &normals = normal_editor.Normals(); + vector<MT_Vector3>::const_iterator normal_it = normals.begin(); + + vector<LOD_TriFace>::const_iterator face_it = faces.begin(); + vector<LOD_TriFace>::const_iterator face_end = faces.end(); + + vector<LOD_Quadric> & quadrics = *m_quadrics; + + + for (; face_it != face_end; ++face_it, ++normal_it) { + + MT_Vector3 normal = *normal_it; + MT_Scalar offset = -normal.dot(verts[face_it->m_verts[0]].pos); + + LOD_Quadric q(normal,offset); + + quadrics[face_it->m_verts[0]] += q; + quadrics[face_it->m_verts[1]] += q; + quadrics[face_it->m_verts[2]] += q; + } + + if (preserve_boundaries) { + + // iterate through the edge set and add a boundary quadric to + // each of the boundary edges vertices. + + vector<LOD_Edge>::const_iterator edge_it = edges.begin(); + vector<LOD_Edge>::const_iterator edge_end = edges.end(); + + for (; edge_it != edge_end; ++edge_it) { + if (edge_it->BoundaryEdge()) { + + // compute a plane perpendicular to the edge and the normal + // of the edges single polygon. + const MT_Vector3 & v0 = verts[edge_it->m_verts[0]].pos; + const MT_Vector3 & v1 = verts[edge_it->m_verts[1]].pos; + + MT_Vector3 edge_vector = v1 - v0; + + LOD_FaceInd edge_face = edge_it->OpFace(LOD_EdgeInd::Empty()); + edge_vector = edge_vector.cross(normals[edge_face]); + + if (!edge_vector.fuzzyZero()) { + edge_vector.normalize(); + + LOD_Quadric boundary_q(edge_vector, - edge_vector.dot(v0)); + boundary_q *= 100; + + quadrics[edge_it->m_verts[0]] += boundary_q; + quadrics[edge_it->m_verts[1]] += boundary_q; + } + } + } + } + + + // initiate the heap keys of the edges by computing the edge costs. + + vector<LOD_Edge>::iterator edge_it = edges.begin(); + vector<LOD_Edge>::const_iterator edge_end = edges.end(); + + for (; edge_it != edge_end; ++edge_it) { + + MT_Vector3 target = TargetVertex(*edge_it); + + LOD_Edge &e = *edge_it; + LOD_Quadric q0 = quadrics[e.m_verts[0]]; + const LOD_Quadric &q1 = quadrics[e.m_verts[1]]; + + e.HeapKey() = -float(q0.Evaluate(target) + q1.Evaluate(target)); + } + + return true; + +}; + + MT_Vector3 +LOD_QuadricEditor:: +TargetVertex( + LOD_Edge & e +){ + + // compute an edge contration target for edge ei + // this is computed by summing it's vertices quadrics and + // optimizing the result. + vector<LOD_Vertex> &verts = m_mesh.VertexSet(); + + vector<LOD_Quadric> &quadrics = *m_quadrics; + + LOD_VertexInd v0 = e.m_verts[0]; + LOD_VertexInd v1 = e.m_verts[1]; + + LOD_Quadric q0 = quadrics[v0]; + q0 += quadrics[v1]; + + MT_Vector3 result; + + if (q0.Optimize(result)) { + return result; + } else { + // the quadric was degenerate -> just take the average of + // v0 and v1 + + return ((verts[v0].pos + verts[v1].pos) * 0.5); + } +}; + + void +LOD_QuadricEditor:: +ComputeEdgeCosts( + vector<LOD_EdgeInd> &edges +){ + + // for each we compute the target vertex and then compute + // the quadric error e = Q1(v') + Q2(v') + vector<LOD_Edge> &edge_set = m_mesh.EdgeSet(); + + vector<LOD_Quadric> &quadrics = *m_quadrics; + + vector<LOD_EdgeInd>::const_iterator edge_it = edges.begin(); + vector<LOD_EdgeInd>::const_iterator edge_end = edges.end(); + + for (; edge_it != edge_end; ++edge_it) { + + MT_Vector3 target = TargetVertex(edge_set[*edge_it]); + + LOD_Edge &e = edge_set[*edge_it]; + LOD_Quadric q0 = quadrics[e.m_verts[0]]; + const LOD_Quadric &q1 = quadrics[e.m_verts[1]]; + + e.HeapKey() = -float(q0.Evaluate(target) + q1.Evaluate(target)); + } +}; + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/intern/decimation/intern/LOD_QuadricEditor.h b/intern/decimation/intern/LOD_QuadricEditor.h new file mode 100644 index 00000000000..bb3a5e957b9 --- /dev/null +++ b/intern/decimation/intern/LOD_QuadricEditor.h @@ -0,0 +1,119 @@ +/** + * $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 ***** + */ + +#ifndef NAN_INCLUDED_LOD_QuadricEditor_h + +#define NAN_INCLUDED_LOD_QuadricEditor_h + +#include "MEM_NonCopyable.h" +#include "LOD_ManMesh2.h" +#include "MT_Vector3.h" +#include "LOD_Quadric.h" + +class LOD_ExternNormalEditor; + + +class LOD_QuadricEditor : public MEM_NonCopyable +{ + +public : + + // Creation + /////////// + + static + LOD_QuadricEditor * + New( + LOD_ManMesh2 &mesh + ); + + // Property editor interface + //////////////////////////// + + void + Remove( + std::vector<LOD_VertexInd> &sorted_vertices + ); + + void + Update( + std::vector<LOD_FaceInd> &sorted_vertices + ); + + + std::vector<LOD_Quadric> & + Quadrics( + ) const { + return *m_quadrics; + }; + + + // Editor specific methods + ////////////////////////// + + bool + BuildQuadrics( + LOD_ExternNormalEditor& normal_editor, + bool preserve_boundaries + ); + + + void + ComputeEdgeCosts( + std::vector<LOD_EdgeInd> &edges + ); + + MT_Vector3 + TargetVertex( + LOD_Edge &e + ); + + ~LOD_QuadricEditor( + ){ + delete(m_quadrics); + }; + + +private : + + std::vector<LOD_Quadric> * m_quadrics; + + LOD_ManMesh2 &m_mesh; + +private : + + LOD_QuadricEditor(LOD_ManMesh2 &mesh); + + + +}; + +#endif diff --git a/intern/decimation/intern/LOD_decimation.cpp b/intern/decimation/intern/LOD_decimation.cpp new file mode 100644 index 00000000000..7bbc0945424 --- /dev/null +++ b/intern/decimation/intern/LOD_decimation.cpp @@ -0,0 +1,156 @@ +/** + * $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 ***** + */ + +// implementation of external c api + + +#include "../extern/LOD_decimation.h" +#include "LOD_DecimationClass.h" + +using namespace std; + + int +LOD_LoadMesh( + LOD_Decimation_InfoPtr info +) { + if (info == NULL) return 0; + if ( + info->vertex_buffer == NULL || + info->vertex_normal_buffer == NULL || + info->triangle_index_buffer == NULL + ) { + return 0; + } + + + // create the intern object to hold all + // the decimation classes + + MEM_SmartPtr<LOD_DecimationClass> intern(LOD_DecimationClass::New(info)); + + if (intern == NULL) return 0; + + MEM_SmartPtr<vector<LOD_Vertex> > intern_vertex_buffer(new vector<LOD_Vertex>(info->vertex_num)); + if (intern_vertex_buffer == NULL) return 0; + + vector<LOD_Vertex>::iterator intern_vertex_it(intern_vertex_buffer->begin()); + + // now load in the vertices to the mesh + + const int vertex_stride = 3; + + float * vertex_ptr = info->vertex_buffer; + const float * vertex_end = vertex_ptr + info->vertex_num*vertex_stride; + + LOD_ManMesh2 &mesh = intern->Mesh(); + + for (;vertex_ptr < vertex_end; vertex_ptr += vertex_stride,++intern_vertex_it) { + intern_vertex_it->pos = MT_Vector3(vertex_ptr); + } + + mesh.SetVertices(intern_vertex_buffer); + + // load in the triangles + + const int triangle_stride = 3; + + int * triangle_ptr = info->triangle_index_buffer; + const int * triangle_end = triangle_ptr + info->face_num*triangle_stride; + + try { + + for (;triangle_ptr < triangle_end; triangle_ptr += triangle_stride) { + mesh.AddTriangle(triangle_ptr); + } + } + + catch (...) { + return 0; + } + + // ok we have built the mesh + + intern->m_e_decimation_state = LOD_DecimationClass::e_loaded; + + info->intern = (void *) (intern.Release()); + + return 1; +} + + int +LOD_PreprocessMesh( + LOD_Decimation_InfoPtr info +) { + if (info == NULL) return 0; + if (info->intern == NULL) return 0; + + LOD_DecimationClass *intern = (LOD_DecimationClass *) info->intern; + if (intern->m_e_decimation_state != LOD_DecimationClass::e_loaded) return 0; + + // arm the various internal classes so that we are ready to step + // through decimation + + intern->FaceEditor().BuildNormals(); + if (intern->Decimator().Arm() == false) return 0; + + // ok preprocessing done + intern->m_e_decimation_state = LOD_DecimationClass::e_preprocessed; + + return 1; +} + + int +LOD_CollapseEdge( + LOD_Decimation_InfoPtr info +){ + if (info == NULL) return 0; + if (info->intern == NULL) return 0; + LOD_DecimationClass *intern = (LOD_DecimationClass *) info->intern; + if (intern->m_e_decimation_state != LOD_DecimationClass::e_preprocessed) return 0; + + bool step_result = intern->Decimator().Step(); + + return step_result == true ? 1 : 0; +} + + + int +LOD_FreeDecimationData( + LOD_Decimation_InfoPtr info +){ + if (info == NULL) return 0; + if (info->intern == NULL) return 0; + LOD_DecimationClass *intern = (LOD_DecimationClass *) info->intern; + delete(intern); + info->intern = NULL; + return 1; +} + diff --git a/intern/decimation/intern/Makefile b/intern/decimation/intern/Makefile new file mode 100644 index 00000000000..d7c9d89d9c7 --- /dev/null +++ b/intern/decimation/intern/Makefile @@ -0,0 +1,45 @@ +# +# $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 ***** +# decimation intern Makefile +# + +LIBNAME = decimation +DIR = $(OCGDIR)/intern/$(LIBNAME) + +include nan_compile.mk + +CCFLAGS += $(NAN_LEVEL_2_CPP_WARNINGS) + +CPPFLAGS += -I$(NAN_MOTO)/include +CPPFLAGS += -I$(NAN_MEMUTIL)/include +CPPFLAGS += -I$(NAN_CONTAINER)/include + + diff --git a/intern/decimation/make/msvc_6_0/decimation.dsp b/intern/decimation/make/msvc_6_0/decimation.dsp new file mode 100644 index 00000000000..32d6928c61a --- /dev/null +++ b/intern/decimation/make/msvc_6_0/decimation.dsp @@ -0,0 +1,188 @@ +# Microsoft Developer Studio Project File - Name="decimation" - Package Owner=<4> +# Microsoft Developer Studio Generated Build File, Format Version 6.00 +# ** DO NOT EDIT ** + +# TARGTYPE "Win32 (x86) Static Library" 0x0104 + +CFG=decimation - Win32 Debug +!MESSAGE This is not a valid makefile. To build this project using NMAKE, +!MESSAGE use the Export Makefile command and run +!MESSAGE +!MESSAGE NMAKE /f "decimation.mak". +!MESSAGE +!MESSAGE You can specify a configuration when running NMAKE +!MESSAGE by defining the macro CFG on the command line. For example: +!MESSAGE +!MESSAGE NMAKE /f "decimation.mak" CFG="decimation - Win32 Debug" +!MESSAGE +!MESSAGE Possible choices for configuration are: +!MESSAGE +!MESSAGE "decimation - Win32 Release" (based on "Win32 (x86) Static Library") +!MESSAGE "decimation - Win32 Debug" (based on "Win32 (x86) Static Library") +!MESSAGE + +# Begin Project +# PROP AllowPerConfigDependencies 0 +# PROP Scc_ProjName "" +# PROP Scc_LocalPath "" +CPP=cl.exe +RSC=rc.exe + +!IF "$(CFG)" == "decimation - Win32 Release" + +# PROP BASE Use_MFC 0 +# PROP BASE Use_Debug_Libraries 0 +# PROP BASE Output_Dir "Release" +# PROP BASE Intermediate_Dir "Release" +# PROP BASE Target_Dir "" +# PROP Use_MFC 0 +# PROP Use_Debug_Libraries 0 +# PROP Output_Dir "Release" +# PROP Intermediate_Dir "Release" +# PROP Target_Dir "" +LINK32=link.exe -lib +# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_MBCS" /D "_LIB" /YX /FD /c +# ADD CPP /nologo /W3 /GX /O2 /Ob2 /I "..\..\..\..\lib\windows\container\include\\" /I "..\..\..\..\lib\windows\memutil\include\\" /I "..\..\..\..\lib\windows\moto\include\\" /D "WIN32" /D "NDEBUG" /D "_MBCS" /D "_LIB" /FD /c +# SUBTRACT CPP /YX +# ADD BASE RSC /l 0x413 /d "NDEBUG" +# ADD RSC /l 0x413 /d "NDEBUG" +BSC32=bscmake.exe +# ADD BASE BSC32 /nologo +# ADD BSC32 /nologo +LIB32=link.exe -lib +# ADD BASE LIB32 /nologo +# ADD LIB32 /nologo /out:"Release\libdecimation.lib" +# Begin Special Build Tool +SOURCE="$(InputPath)" +PostBuild_Cmds=ECHO Copying header files COPY "..\..\extern\*.h" "..\..\..\..\lib\windows\decimation\include" ECHO Copying lib COPY "Release\libdecimation.lib" "..\..\..\..\lib\windows\decimation\lib\libdecimation.a" ECHO Done +# End Special Build Tool + +!ELSEIF "$(CFG)" == "decimation - Win32 Debug" + +# PROP BASE Use_MFC 0 +# PROP BASE Use_Debug_Libraries 1 +# PROP BASE Output_Dir "Debug" +# PROP BASE Intermediate_Dir "Debug" +# PROP BASE Target_Dir "" +# PROP Use_MFC 0 +# PROP Use_Debug_Libraries 1 +# PROP Output_Dir "Debug" +# PROP Intermediate_Dir "Debug" +# PROP Target_Dir "" +LINK32=link.exe -lib +# ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_MBCS" /D "_LIB" /YX /FD /GZ /c +# ADD CPP /nologo /W4 /Gm /GX /ZI /Od /I "..\..\..\..\lib\windows\container\include\\" /I "..\..\..\..\lib\windows\memutil\include\\" /I "..\..\..\..\lib\windows\moto\include\\" /D "WIN32" /D "_DEBUG" /D "_MBCS" /D "_LIB" /FD /GZ /c +# SUBTRACT CPP /YX +# ADD BASE RSC /l 0x413 /d "_DEBUG" +# ADD RSC /l 0x413 /d "_DEBUG" +BSC32=bscmake.exe +# ADD BASE BSC32 /nologo +# ADD BSC32 /nologo +LIB32=link.exe -lib +# ADD BASE LIB32 /nologo +# ADD LIB32 /nologo /out:"Debug\libdecimation.lib" +# Begin Special Build Tool +SOURCE="$(InputPath)" +PostBuild_Cmds=ECHO Copying header files COPY "..\..\extern\*.h" "..\..\..\..\lib\windows\decimation\include" ECHO Copying lib COPY "Debug\libdecimation.lib" "..\..\..\..\lib\windows\decimation\lib\debug\libdecimation.a" ECHO Copying Debug info. COPY "Debug\vc60.*" "..\..\..\..\lib\windows\decimation\lib\debug\" ECHO Done +# End Special Build Tool + +!ENDIF + +# Begin Target + +# Name "decimation - Win32 Release" +# Name "decimation - Win32 Debug" +# Begin Group "intern" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=..\..\intern\LOD_decimation.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_DecimationClass.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_EdgeCollapser.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_EdgeCollapser.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_ExternBufferEditor.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_ExternNormalEditor.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_ExternNormalEditor.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_FaceNormalEditor.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_FaceNormalEditor.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_ManMesh2.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_ManMesh2.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_MeshBounds.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_MeshException.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_MeshPrimitives.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_MeshPrimitives.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_QSDecimator.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_QSDecimator.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_Quadric.h +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_QuadricEditor.cpp +# End Source File +# Begin Source File + +SOURCE=..\..\intern\LOD_QuadricEditor.h +# End Source File +# End Group +# Begin Group "extern" + +# PROP Default_Filter "" +# Begin Source File + +SOURCE=..\..\extern\LOD_decimation.h +# End Source File +# End Group +# End Target +# End Project diff --git a/intern/decimation/make/msvc_6_0/decimation.dsw b/intern/decimation/make/msvc_6_0/decimation.dsw new file mode 100644 index 00000000000..f874b324725 --- /dev/null +++ b/intern/decimation/make/msvc_6_0/decimation.dsw @@ -0,0 +1,33 @@ +Microsoft Developer Studio Workspace File, Format Version 6.00 +# WARNING: DO NOT EDIT OR DELETE THIS WORKSPACE FILE! + +############################################################################### + +Project: "decimation"=.\decimation.dsp - Package Owner=<4> + +Package=<5> +{{{ +}}} + +Package=<4> +{{{ +}}} + +############################################################################### + +Global: + +Package=<5> +{{{ +}}} + +Package=<3> +{{{ +}}} + +############################################################################### + + + + + |