Reverting change to decimation to fix compatibility with
[blender.git] / intern / decimation / intern / LOD_QSDecimator.cpp
1 /**
2  * $Id$
3  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30  */
31
32 #ifdef HAVE_CONFIG_H
33 #include <config.h>
34 #endif
35
36 #include "LOD_QSDecimator.h"
37
38 #include "LOD_ExternBufferEditor.h"
39
40 using namespace std;
41
42         LOD_QSDecimator *
43 LOD_QSDecimator::
44 New(
45         LOD_ManMesh2 &mesh,
46         LOD_ExternNormalEditor &face_editor,
47         LOD_ExternBufferEditor &extern_editor
48 ){
49
50         MEM_SmartPtr<LOD_QSDecimator> output 
51                 = new LOD_QSDecimator(mesh,face_editor,extern_editor);
52
53         MEM_SmartPtr<LOD_EdgeCollapser > collapser(LOD_EdgeCollapser::New());
54         MEM_SmartPtr<LOD_QuadricEditor> q_editor(LOD_QuadricEditor::New(mesh));
55
56         if (
57                 output == NULL ||
58                 collapser == NULL ||
59                 q_editor == NULL 
60         ) {
61                 return NULL;
62         }
63         output->m_collapser = collapser.Release();
64         output->m_quadric_editor = q_editor.Release();
65         return output.Release();
66 }       
67
68
69
70         bool
71 LOD_QSDecimator::
72 Arm(
73 ){
74         MT_assert(!m_is_armed);
75         bool heap_result = BuildHeap();
76         if (!heap_result) {
77                 return false;
78         }
79         m_is_armed = true;
80         return true;
81 }
82         
83         bool
84 LOD_QSDecimator::
85 Step(
86 ){
87         return CollapseEdge();
88 }
89
90
91 LOD_QSDecimator::
92 LOD_QSDecimator(
93         LOD_ManMesh2 &mesh,
94         LOD_ExternNormalEditor &face_editor,
95         LOD_ExternBufferEditor &extern_editor
96 ) :
97         m_mesh(mesh),
98         m_face_editor(face_editor),
99         m_extern_editor(extern_editor),
100         m_is_armed (false)
101 {       
102         m_deg_edges.reserve(32);
103         m_deg_faces.reserve(32);
104         m_deg_vertices.reserve(32);
105         m_update_faces.reserve(32);
106         m_new_edges.reserve(32);
107         m_update_vertices.reserve(32);
108 };
109
110         bool
111 LOD_QSDecimator::
112 CollapseEdge(
113 ){
114         
115         // find an edge to collapse
116         
117         // FIXME force an edge collapse
118         // or return false
119
120         std::vector<LOD_Edge> & edges = m_mesh.EdgeSet();
121         std::vector<LOD_Vertex> & verts = m_mesh.VertexSet();
122         std::vector<LOD_Quadric> & quadrics = m_quadric_editor->Quadrics();
123         int size = edges.size();
124
125         if (size == 0) return false;
126
127         const int heap_top = m_heap->Top();
128
129         if (heap_top == -1 || edges[heap_top].HeapKey() <= -MT_INFINITY) {
130                 return false;
131         }
132         
133         // compute the target position
134         MT_Vector3 new_vertex = m_quadric_editor->TargetVertex(edges[heap_top]);
135         LOD_Quadric & q0 = quadrics[edges[heap_top].m_verts[0]];
136         LOD_Quadric & q1 = quadrics[edges[heap_top].m_verts[1]];
137
138         LOD_Vertex &v0 = verts[edges[heap_top].m_verts[0]];
139         LOD_Vertex &v1 = verts[edges[heap_top].m_verts[1]];
140
141         LOD_Quadric sum = q0;
142         sum += q1;
143
144
145         if (m_collapser->CollapseEdge(
146                         heap_top,
147                         m_mesh,
148                         m_deg_edges,
149                         m_deg_faces,
150                         m_deg_vertices,
151                         m_new_edges,
152                         m_update_faces,
153                         m_update_vertices
154         )) {
155
156                 // assign new vertex position
157
158                  v0.pos = new_vertex;
159                  v1.pos = new_vertex;
160
161                 // sum the quadrics of v0 and v1
162                 q0 = sum;
163                 q1 = sum;
164
165                 // ok update the primitive properties
166
167                 m_face_editor.Update(m_update_faces);   
168                 m_face_editor.UpdateVertexNormals(m_update_vertices);
169
170                 // update the external vertex buffer 
171                 m_extern_editor.CopyModifiedVerts(m_mesh,m_update_vertices);
172
173                 // update the external face buffer
174                 m_extern_editor.CopyModifiedFaces(m_mesh,m_update_faces);
175
176                 // update the edge heap
177                 UpdateHeap(m_deg_edges,m_new_edges);
178
179                 m_quadric_editor->Remove(m_deg_vertices);
180                 m_face_editor.Remove(m_deg_faces);
181                 m_face_editor.RemoveVertexNormals(m_deg_vertices);              
182                                 
183                 // delete the primitives
184
185                 DeletePrimitives(m_deg_edges,m_deg_faces,m_deg_vertices);
186
187         } else {
188                 // the edge could not be collapsed at the moment - so
189                 // we adjust it's priority and add it back to the heap.
190                 m_heap->Remove(&edges[0],0);
191                 edges[heap_top].HeapKey() = - MT_INFINITY;
192                 m_heap->Insert(&edges[0],heap_top);
193         }
194
195         //clear all the temporary buffers
196
197         m_deg_faces.clear();
198         m_deg_edges.clear();
199         m_deg_vertices.clear();
200         
201         m_update_faces.clear();
202         m_update_vertices.clear();
203         m_new_edges.clear();
204
205         return true;
206
207 }       
208
209         void
210 LOD_QSDecimator::
211 DeletePrimitives(
212         const vector<LOD_EdgeInd> & degenerate_edges,
213         const vector<LOD_FaceInd> & degenerate_faces,
214         const vector<LOD_VertexInd> & degenerate_vertices
215 ) {
216
217         // assumes that the 3 vectors are sorted in descending order.
218
219         // Delete Degnerate primitives
220         //////////////////////////////
221
222
223         // delete the old edges - we have to be very careful here
224         // mesh.delete() swaps edges to be deleted with the last edge in 
225         // the edge buffer. However the next edge to be deleted may have
226         // been the last edge in the buffer!
227
228         // One way to solve this is to sort degenerate_edges in descending order.
229         // And then delete them in that order.
230         
231         // it is also vital that degenerate_edges contains no duplicates
232
233         vector<LOD_EdgeInd>::const_iterator edge_it = degenerate_edges.begin();
234         vector<LOD_EdgeInd>::const_iterator edge_end = degenerate_edges.end();
235
236         for (; edge_it != edge_end; ++edge_it) {
237                 m_mesh.DeleteEdge(*edge_it,m_heap);
238         }
239
240
241
242         vector<LOD_FaceInd>::const_iterator face_it = degenerate_faces.begin();
243         vector<LOD_FaceInd>::const_iterator face_end = degenerate_faces.end();
244         
245         for (;face_it != face_end; ++face_it) {
246                 m_mesh.DeleteFace(m_extern_editor,*face_it);
247         }
248
249         vector<LOD_VertexInd>::const_iterator vertex_it = degenerate_vertices.begin();
250         vector<LOD_VertexInd>::const_iterator vertex_end = degenerate_vertices.end();
251         
252         for (;vertex_it != vertex_end; ++vertex_it) {
253                 m_mesh.DeleteVertex(m_extern_editor,*vertex_it);
254         }
255 }
256
257
258         bool
259 LOD_QSDecimator::
260 BuildHeap(
261 ){
262         // build the quadrics 
263
264         if (m_quadric_editor->BuildQuadrics(m_face_editor,true) == false) return false;
265
266
267         m_heap = CTR_UHeap<LOD_Edge>::New();
268         // load in edge pointers to the heap
269
270         std::vector<LOD_Edge> & edge_set= m_mesh.EdgeSet();
271         std::vector<LOD_Edge>::const_iterator edge_end = edge_set.end();
272         std::vector<LOD_Edge>::iterator edge_start = edge_set.begin();
273
274         std::vector<int> & heap_vector = m_heap->HeapVector();
275
276         for (int i = 0; i < edge_set.size(); ++i) {
277                 edge_set[i].HeapPos() = i;
278                 heap_vector.push_back(i);
279         }
280         
281         m_heap->MakeHeap(&edge_set[0]);
282
283         return true;
284 }
285
286         void
287 LOD_QSDecimator::
288 UpdateHeap(
289         std::vector<LOD_EdgeInd> &deg_edges,
290         std::vector<LOD_EdgeInd> &new_edges
291 ){
292         // first of all compute values for the new edges 
293         // and bung them on the heap.
294
295         std::vector<LOD_Edge>  & edge_set= m_mesh.EdgeSet();
296
297         std::vector<LOD_EdgeInd>::const_iterator edge_it = new_edges.begin();
298         std::vector<LOD_EdgeInd>::const_iterator end_it = new_edges.end();
299
300
301         // insert all the new edges             
302         ///////////////////////////
303
304         // compute edge costs ffor the new edges
305
306         m_quadric_editor->ComputeEdgeCosts(new_edges);
307
308         // inser the new elements into the heap
309
310         for (; edge_it != end_it; ++edge_it) {          
311                 m_heap->Insert(&edge_set[0],*edge_it);
312         }
313
314
315         // remove all the old values from the heap
316
317         edge_it = deg_edges.begin();
318         end_it = deg_edges.end();
319
320         for (; edge_it != end_it; ++edge_it) {
321                 LOD_Edge &e = edge_set[*edge_it];
322                 m_heap->Remove(&edge_set[0],e.HeapPos());
323
324                 e.HeapPos() = 0xffffffff;
325
326         }
327 }
328