Merged from trunk with revision range 36835-37865,
[blender.git] / intern / decimation / intern / LOD_QuadricEditor.cpp
1 /*
2  * $Id$
3  * ***** BEGIN GPL 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.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): none yet.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file decimation/intern/LOD_QuadricEditor.cpp
30  *  \ingroup decimation
31  */
32
33
34 #include "LOD_QuadricEditor.h"
35 #include "LOD_ExternNormalEditor.h"
36
37 // Creation
38 ///////////
39
40 using namespace std;
41
42
43 LOD_QuadricEditor::
44 LOD_QuadricEditor(
45         LOD_ManMesh2 &mesh
46 ) :
47         m_quadrics(NULL),
48         m_mesh(mesh)
49 {
50 };
51
52         LOD_QuadricEditor *
53 LOD_QuadricEditor::
54 New(
55         LOD_ManMesh2 &mesh
56 ){
57         //same number of quadrics as vertices in the mesh
58
59         MEM_SmartPtr<LOD_QuadricEditor> output(new LOD_QuadricEditor(mesh));
60
61         if (output == NULL) {
62                 return NULL;
63         }
64         return output.Release();
65 }
66
67
68 // Property editor interface
69 ////////////////////////////
70
71         void
72 LOD_QuadricEditor::
73 Remove(
74         std::vector<LOD_VertexInd> &sorted_vertices
75 ){
76         vector<LOD_Quadric> & quadrics = *m_quadrics;
77
78         vector<LOD_VertexInd>::const_iterator it_start = sorted_vertices.begin();
79         vector<LOD_VertexInd>::const_iterator it_end = sorted_vertices.end();
80
81         for (; it_start != it_end; ++it_start) {
82
83                 if (quadrics.size() > 0) {
84                         LOD_Quadric temp = quadrics[*it_start];
85                 
86                         quadrics[*it_start] = quadrics.back();
87                         quadrics.back() = temp;
88
89                         quadrics.pop_back();
90                 }
91         }
92 };
93
94
95 // Editor specific methods
96 //////////////////////////
97
98         bool
99 LOD_QuadricEditor::
100 BuildQuadrics(
101         LOD_ExternNormalEditor& normal_editor,
102         bool preserve_boundaries
103 ){
104         if (m_quadrics != NULL) delete(m_quadrics);             
105
106         m_quadrics =new vector<LOD_Quadric> (m_mesh.VertexSet().size());
107         if (m_quadrics == NULL) return false;
108
109         // iterate through the face set of the mesh
110         // compute a quadric based upon that face and 
111         // add it to each of it's vertices quadrics.
112
113         const vector<LOD_TriFace> &faces = m_mesh.FaceSet();
114         const vector<LOD_Vertex> &verts = m_mesh.VertexSet();
115         vector<LOD_Edge> &edges = m_mesh.EdgeSet();     
116
117         const vector<MT_Vector3> &normals = normal_editor.Normals();
118         vector<MT_Vector3>::const_iterator normal_it = normals.begin();
119         
120         vector<LOD_TriFace>::const_iterator face_it = faces.begin();
121         vector<LOD_TriFace>::const_iterator face_end = faces.end();
122
123         vector<LOD_Quadric> & quadrics = *m_quadrics;
124
125
126         for (; face_it != face_end; ++face_it, ++normal_it) {
127                                 
128                 MT_Vector3 normal = *normal_it;
129                 MT_Scalar offset = -normal.dot(verts[face_it->m_verts[0]].pos); 
130
131                 LOD_Quadric q(normal,offset);
132
133                 quadrics[face_it->m_verts[0]] += q;
134                 quadrics[face_it->m_verts[1]] += q;
135                 quadrics[face_it->m_verts[2]] += q;
136         }
137
138         if (preserve_boundaries) {
139
140                 // iterate through the edge set and add a boundary quadric to 
141                 // each of the boundary edges vertices.
142         
143                 vector<LOD_Edge>::const_iterator edge_it = edges.begin();
144                 vector<LOD_Edge>::const_iterator edge_end = edges.end();        
145
146                 for (; edge_it != edge_end; ++edge_it) {
147                         if (edge_it->BoundaryEdge()) {
148
149                                 // compute a plane perpendicular to the edge and the normal
150                                 // of the edges single polygon.
151                                 const MT_Vector3 & v0 = verts[edge_it->m_verts[0]].pos;
152                                 const MT_Vector3 & v1 = verts[edge_it->m_verts[1]].pos;
153         
154                                 MT_Vector3 edge_vector = v1 - v0;
155
156                                 LOD_FaceInd edge_face = edge_it->OpFace(LOD_EdgeInd::Empty());
157                                 edge_vector = edge_vector.cross(normals[edge_face]);
158
159                                 if (!edge_vector.fuzzyZero()) {
160                                         edge_vector.normalize();
161                                 
162                                         LOD_Quadric boundary_q(edge_vector, - edge_vector.dot(v0));     
163                                         boundary_q *= 100;                              
164
165                                         quadrics[edge_it->m_verts[0]] += boundary_q;
166                                         quadrics[edge_it->m_verts[1]] += boundary_q;
167                                 }
168                         }
169                 }
170         }
171
172
173         // initiate the heap keys of the edges by computing the edge costs.
174
175         vector<LOD_Edge>::iterator edge_it = edges.begin();
176         vector<LOD_Edge>::const_iterator edge_end = edges.end();
177
178         for (; edge_it != edge_end; ++edge_it)  {
179                 
180                 MT_Vector3 target = TargetVertex(*edge_it);
181
182                 LOD_Edge &e = *edge_it;
183                 LOD_Quadric q0 = quadrics[e.m_verts[0]];
184                 const LOD_Quadric &q1 = quadrics[e.m_verts[1]];
185                 
186                 e.HeapKey() = -float(q0.Evaluate(target) + q1.Evaluate(target));
187         }
188
189         return true;
190
191 };
192
193         MT_Vector3 
194 LOD_QuadricEditor::
195 TargetVertex(
196         LOD_Edge & e
197 ){
198
199         // compute an edge contration target for edge ei
200         // this is computed by summing it's vertices quadrics and 
201         // optimizing the result.
202         vector<LOD_Vertex> &verts = m_mesh.VertexSet();
203
204         vector<LOD_Quadric> &quadrics = *m_quadrics;
205
206         LOD_VertexInd v0 = e.m_verts[0];
207         LOD_VertexInd v1 = e.m_verts[1];
208
209         LOD_Quadric q0 = quadrics[v0];
210         q0 += quadrics[v1];
211
212         MT_Vector3 result;
213
214         if (q0.Optimize(result)) {
215                 return result;
216         } else {
217                 // the quadric was degenerate -> just take the average of 
218                 // v0 and v1
219
220                 return ((verts[v0].pos + verts[v1].pos) * 0.5);
221         }
222 };
223
224         void
225 LOD_QuadricEditor::
226 ComputeEdgeCosts(
227         vector<LOD_EdgeInd> &edges
228 ){      
229         
230         // for each we compute the target vertex and then compute
231         // the quadric error e = Q1(v') + Q2(v')
232         vector<LOD_Edge> &edge_set = m_mesh.EdgeSet();
233
234         vector<LOD_Quadric> &quadrics = *m_quadrics;
235
236         vector<LOD_EdgeInd>::const_iterator edge_it = edges.begin();
237         vector<LOD_EdgeInd>::const_iterator edge_end = edges.end();
238
239         for (; edge_it != edge_end; ++edge_it)  {
240                 
241                 MT_Vector3 target = TargetVertex(edge_set[*edge_it]);
242
243                 LOD_Edge &e = edge_set[*edge_it];
244                 LOD_Quadric q0 = quadrics[e.m_verts[0]];
245                 const LOD_Quadric &q1 = quadrics[e.m_verts[1]];
246                 
247                 e.HeapKey() = -float(q0.Evaluate(target) + q1.Evaluate(target));
248         }
249 };
250         
251                 
252
253
254                 
255
256
257
258
259
260         
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280