← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty

« back to all changes in this revision

Viewing changes to intern/decimation/intern/LOD_QSDecimator.cpp

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

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