Blender V2.61 - r43446

LOD_QSDecimator.cpp

Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN GPL LICENSE BLOCK *****
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License
00006  * as published by the Free Software Foundation; either version 2
00007  * of the License, or (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software Foundation,
00016  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00017  *
00018  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
00019  * All rights reserved.
00020  *
00021  * The Original Code is: all of this file.
00022  *
00023  * Contributor(s): none yet.
00024  *
00025  * ***** END GPL LICENSE BLOCK *****
00026  */
00027 
00033 #include "LOD_QSDecimator.h"
00034 
00035 #include "LOD_ExternBufferEditor.h"
00036 
00037 using namespace std;
00038 
00039     LOD_QSDecimator *
00040 LOD_QSDecimator::
00041 New(
00042     LOD_ManMesh2 &mesh,
00043     LOD_ExternNormalEditor &face_editor,
00044     LOD_ExternBufferEditor &extern_editor
00045 ){
00046 
00047     MEM_SmartPtr<LOD_QSDecimator> output 
00048         = new LOD_QSDecimator(mesh,face_editor,extern_editor);
00049 
00050     MEM_SmartPtr<LOD_EdgeCollapser > collapser(LOD_EdgeCollapser::New());
00051     MEM_SmartPtr<LOD_QuadricEditor> q_editor(LOD_QuadricEditor::New(mesh));
00052 
00053     if (
00054         output == NULL ||
00055         collapser == NULL ||
00056         q_editor == NULL 
00057     ) {
00058         return NULL;
00059     }
00060     output->m_collapser = collapser.Release();
00061     output->m_quadric_editor = q_editor.Release();
00062     return output.Release();
00063 }   
00064 
00065 
00066 
00067     bool
00068 LOD_QSDecimator::
00069 Arm(
00070 ){
00071     MT_assert(!m_is_armed);
00072     bool heap_result = BuildHeap();
00073     if (!heap_result) {
00074         return false;
00075     }
00076     m_is_armed = true;
00077     return true;
00078 }
00079     
00080     bool
00081 LOD_QSDecimator::
00082 Step(
00083 ){
00084     return CollapseEdge();
00085 }
00086 
00087 
00088 LOD_QSDecimator::
00089 LOD_QSDecimator(
00090     LOD_ManMesh2 &mesh,
00091     LOD_ExternNormalEditor &face_editor,
00092     LOD_ExternBufferEditor &extern_editor
00093 ) :
00094     m_is_armed (false),
00095     m_mesh(mesh),
00096     m_face_editor(face_editor),
00097     m_extern_editor(extern_editor)
00098 {   
00099     m_deg_edges.reserve(32);
00100     m_deg_faces.reserve(32);
00101     m_deg_vertices.reserve(32);
00102     m_update_faces.reserve(32);
00103     m_new_edges.reserve(32);
00104     m_update_vertices.reserve(32);
00105 };
00106 
00107     bool
00108 LOD_QSDecimator::
00109 CollapseEdge(
00110 ){
00111     
00112     // find an edge to collapse
00113     
00114     // FIXME force an edge collapse
00115     // or return false
00116 
00117     std::vector<LOD_Edge> & edges = m_mesh.EdgeSet();
00118     std::vector<LOD_Vertex> & verts = m_mesh.VertexSet();
00119     std::vector<LOD_Quadric> & quadrics = m_quadric_editor->Quadrics();
00120     int size = edges.size();
00121 
00122     if (size == 0) return false;
00123 
00124     const int heap_top = m_heap->Top();
00125 
00126     if (heap_top == -1 || edges[heap_top].HeapKey() <= -MT_INFINITY) {
00127         return false;
00128     }
00129     
00130     // compute the target position
00131     MT_Vector3 new_vertex = m_quadric_editor->TargetVertex(edges[heap_top]);
00132     LOD_Quadric & q0 = quadrics[edges[heap_top].m_verts[0]];
00133     LOD_Quadric & q1 = quadrics[edges[heap_top].m_verts[1]];
00134 
00135     LOD_Vertex &v0 = verts[edges[heap_top].m_verts[0]];
00136     LOD_Vertex &v1 = verts[edges[heap_top].m_verts[1]];
00137 
00138     LOD_Quadric sum = q0;
00139     sum += q1;
00140 
00141 
00142     if (m_collapser->CollapseEdge(
00143             heap_top,
00144             m_mesh,
00145             m_deg_edges,
00146             m_deg_faces,
00147             m_deg_vertices,
00148             m_new_edges,
00149             m_update_faces,
00150             m_update_vertices
00151     )) {
00152 
00153         // assign new vertex position
00154 
00155         v0.pos = new_vertex;
00156         v1.pos = new_vertex;
00157 
00158         // sum the quadrics of v0 and v1
00159         q0 = sum;
00160         q1 = sum;
00161 
00162         // ok update the primitive properties
00163 
00164         m_face_editor.Update(m_update_faces);   
00165         m_face_editor.UpdateVertexNormals(m_update_vertices);
00166 
00167         // update the external vertex buffer 
00168         m_extern_editor.CopyModifiedVerts(m_mesh,m_update_vertices);
00169 
00170         // update the external face buffer
00171         m_extern_editor.CopyModifiedFaces(m_mesh,m_update_faces);
00172 
00173         // update the edge heap
00174         UpdateHeap(m_deg_edges,m_new_edges);
00175 
00176         m_quadric_editor->Remove(m_deg_vertices);
00177         m_face_editor.Remove(m_deg_faces);
00178         m_face_editor.RemoveVertexNormals(m_deg_vertices);      
00179                 
00180         // delete the primitives
00181 
00182         DeletePrimitives(m_deg_edges,m_deg_faces,m_deg_vertices);
00183 
00184     } else {
00185         // the edge could not be collapsed at the moment - so
00186         // we adjust it's priority and add it back to the heap.
00187         m_heap->Remove(&edges[0],0);
00188         edges[heap_top].HeapKey() = - MT_INFINITY;
00189         m_heap->Insert(&edges[0],heap_top);
00190     }
00191 
00192     //clear all the temporary buffers
00193 
00194     m_deg_faces.clear();
00195     m_deg_edges.clear();
00196     m_deg_vertices.clear();
00197     
00198     m_update_faces.clear();
00199     m_update_vertices.clear();
00200     m_new_edges.clear();
00201 
00202     return true;
00203 
00204 }   
00205 
00206     void
00207 LOD_QSDecimator::
00208 DeletePrimitives(
00209     const vector<LOD_EdgeInd> & degenerate_edges,
00210     const vector<LOD_FaceInd> & degenerate_faces,
00211     const vector<LOD_VertexInd> & degenerate_vertices
00212 ) {
00213 
00214     // assumes that the 3 vectors are sorted in descending order.
00215 
00216     // Delete Degnerate primitives
00218 
00219 
00220     // delete the old edges - we have to be very careful here
00221     // mesh.delete() swaps edges to be deleted with the last edge in 
00222     // the edge buffer. However the next edge to be deleted may have
00223     // been the last edge in the buffer!
00224 
00225     // One way to solve this is to sort degenerate_edges in descending order.
00226     // And then delete them in that order.
00227     
00228     // it is also vital that degenerate_edges contains no duplicates
00229 
00230     vector<LOD_EdgeInd>::const_iterator edge_it = degenerate_edges.begin();
00231     vector<LOD_EdgeInd>::const_iterator edge_end = degenerate_edges.end();
00232 
00233     for (; edge_it != edge_end; ++edge_it) {
00234         m_mesh.DeleteEdge(*edge_it,m_heap);
00235     }
00236 
00237 
00238 
00239     vector<LOD_FaceInd>::const_iterator face_it = degenerate_faces.begin();
00240     vector<LOD_FaceInd>::const_iterator face_end = degenerate_faces.end();
00241     
00242     for (;face_it != face_end; ++face_it) {
00243         m_mesh.DeleteFace(m_extern_editor,*face_it);
00244     }
00245 
00246     vector<LOD_VertexInd>::const_iterator vertex_it = degenerate_vertices.begin();
00247     vector<LOD_VertexInd>::const_iterator vertex_end = degenerate_vertices.end();
00248     
00249     for (;vertex_it != vertex_end; ++vertex_it) {
00250         m_mesh.DeleteVertex(m_extern_editor,*vertex_it);
00251     }
00252 }
00253 
00254 
00255     bool
00256 LOD_QSDecimator::
00257 BuildHeap(
00258 ){
00259     // build the quadrics 
00260 
00261     if (m_quadric_editor->BuildQuadrics(m_face_editor,true) == false) return false;
00262 
00263 
00264     m_heap = CTR_UHeap<LOD_Edge>::New();
00265     // load in edge pointers to the heap
00266 
00267     std::vector<LOD_Edge> & edge_set= m_mesh.EdgeSet();
00268     std::vector<LOD_Edge>::const_iterator edge_end = edge_set.end();
00269     std::vector<LOD_Edge>::iterator edge_start = edge_set.begin();
00270 
00271     std::vector<int> & heap_vector = m_heap->HeapVector();
00272 
00273     for (unsigned int i = 0; i < edge_set.size(); ++i) {
00274         edge_set[i].HeapPos() = i;
00275         heap_vector.push_back(i);
00276     }
00277     
00278     m_heap->MakeHeap(&edge_set[0]);
00279 
00280     return true;
00281 }
00282 
00283     void
00284 LOD_QSDecimator::
00285 UpdateHeap(
00286     std::vector<LOD_EdgeInd> &deg_edges,
00287     std::vector<LOD_EdgeInd> &new_edges
00288 ){
00289     // first of all compute values for the new edges 
00290     // and bung them on the heap.
00291 
00292     std::vector<LOD_Edge>  & edge_set= m_mesh.EdgeSet();
00293 
00294     std::vector<LOD_EdgeInd>::const_iterator edge_it = new_edges.begin();
00295     std::vector<LOD_EdgeInd>::const_iterator end_it = new_edges.end();
00296 
00297 
00298     // insert all the new edges     
00300 
00301     // compute edge costs ffor the new edges
00302 
00303     m_quadric_editor->ComputeEdgeCosts(new_edges);
00304 
00305     // inser the new elements into the heap
00306 
00307     for (; edge_it != end_it; ++edge_it) {      
00308         m_heap->Insert(&edge_set[0],*edge_it);
00309     }
00310 
00311 
00312     // remove all the old values from the heap
00313 
00314     edge_it = deg_edges.begin();
00315     end_it = deg_edges.end();
00316 
00317     for (; edge_it != end_it; ++edge_it) {
00318         LOD_Edge &e = edge_set[*edge_it];
00319         m_heap->Remove(&edge_set[0],e.HeapPos());
00320 
00321         e.HeapPos() = -1;
00322 
00323     }
00324 }
00325