Reverting change to decimation to fix compatibility with
[blender.git] / intern / decimation / intern / LOD_QuadricEditor.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_QuadricEditor.h"
37 #include "LOD_ExternNormalEditor.h"
38
39 // Creation
40 ///////////
41
42 using namespace std;
43
44
45 LOD_QuadricEditor::
46 LOD_QuadricEditor(
47         LOD_ManMesh2 &mesh
48 ) :
49         m_quadrics(NULL),
50         m_mesh(mesh)
51 {
52 };
53
54         LOD_QuadricEditor *
55 LOD_QuadricEditor::
56 New(
57         LOD_ManMesh2 &mesh
58 ){
59         //same number of quadrics as vertices in the mesh
60
61         MEM_SmartPtr<LOD_QuadricEditor> output(new LOD_QuadricEditor(mesh));
62
63         if (output == NULL) {
64                 return NULL;
65         }
66         return output.Release();
67 }
68
69
70 // Property editor interface
71 ////////////////////////////
72
73         void
74 LOD_QuadricEditor::
75 Remove(
76         std::vector<LOD_VertexInd> &sorted_vertices
77 ){
78         vector<LOD_Quadric> & quadrics = *m_quadrics;
79
80         vector<LOD_VertexInd>::const_iterator it_start = sorted_vertices.begin();
81         vector<LOD_VertexInd>::const_iterator it_end = sorted_vertices.end();
82
83         for (; it_start != it_end; ++it_start) {
84
85                 if (quadrics.size() > 0) {
86                         LOD_Quadric temp = quadrics[*it_start];
87                 
88                         quadrics[*it_start] = quadrics.back();
89                         quadrics.back() = temp;
90
91                         quadrics.pop_back();
92                 }
93         }
94 };
95
96
97 // Editor specific methods
98 //////////////////////////
99
100         bool
101 LOD_QuadricEditor::
102 BuildQuadrics(
103         LOD_ExternNormalEditor& normal_editor,
104         bool preserve_boundaries
105 ){
106         if (m_quadrics != NULL) delete(m_quadrics);             
107
108         m_quadrics =new vector<LOD_Quadric> (m_mesh.VertexSet().size());
109         if (m_quadrics == NULL) return false;
110
111         // iterate through the face set of the mesh
112         // compute a quadric based upon that face and 
113         // add it to each of it's vertices quadrics.
114
115         const vector<LOD_TriFace> &faces = m_mesh.FaceSet();
116         const vector<LOD_Vertex> &verts = m_mesh.VertexSet();
117         vector<LOD_Edge> &edges = m_mesh.EdgeSet();     
118
119         const vector<MT_Vector3> &normals = normal_editor.Normals();
120         vector<MT_Vector3>::const_iterator normal_it = normals.begin();
121         
122         vector<LOD_TriFace>::const_iterator face_it = faces.begin();
123         vector<LOD_TriFace>::const_iterator face_end = faces.end();
124
125         vector<LOD_Quadric> & quadrics = *m_quadrics;
126
127
128         for (; face_it != face_end; ++face_it, ++normal_it) {
129                                 
130                 MT_Vector3 normal = *normal_it;
131                 MT_Scalar offset = -normal.dot(verts[face_it->m_verts[0]].pos); 
132
133                 LOD_Quadric q(normal,offset);
134
135                 quadrics[face_it->m_verts[0]] += q;
136                 quadrics[face_it->m_verts[1]] += q;
137                 quadrics[face_it->m_verts[2]] += q;
138         }
139
140         if (preserve_boundaries) {
141
142                 // iterate through the edge set and add a boundary quadric to 
143                 // each of the boundary edges vertices.
144         
145                 vector<LOD_Edge>::const_iterator edge_it = edges.begin();
146                 vector<LOD_Edge>::const_iterator edge_end = edges.end();        
147
148                 for (; edge_it != edge_end; ++edge_it) {
149                         if (edge_it->BoundaryEdge()) {
150
151                                 // compute a plane perpendicular to the edge and the normal
152                                 // of the edges single polygon.
153                                 const MT_Vector3 & v0 = verts[edge_it->m_verts[0]].pos;
154                                 const MT_Vector3 & v1 = verts[edge_it->m_verts[1]].pos;
155         
156                                 MT_Vector3 edge_vector = v1 - v0;
157
158                                 LOD_FaceInd edge_face = edge_it->OpFace(LOD_EdgeInd::Empty());
159                                 edge_vector = edge_vector.cross(normals[edge_face]);
160
161                                 if (!edge_vector.fuzzyZero()) {
162                                         edge_vector.normalize();
163                                 
164                                         LOD_Quadric boundary_q(edge_vector, - edge_vector.dot(v0));     
165                                         boundary_q *= 100;                              
166
167                                         quadrics[edge_it->m_verts[0]] += boundary_q;
168                                         quadrics[edge_it->m_verts[1]] += boundary_q;
169                                 }
170                         }
171                 }
172         }
173
174
175         // initiate the heap keys of the edges by computing the edge costs.
176
177         vector<LOD_Edge>::iterator edge_it = edges.begin();
178         vector<LOD_Edge>::const_iterator edge_end = edges.end();
179
180         for (; edge_it != edge_end; ++edge_it)  {
181                 
182                 MT_Vector3 target = TargetVertex(*edge_it);
183
184                 LOD_Edge &e = *edge_it;
185                 LOD_Quadric q0 = quadrics[e.m_verts[0]];
186                 const LOD_Quadric &q1 = quadrics[e.m_verts[1]];
187                 
188                 e.HeapKey() = -float(q0.Evaluate(target) + q1.Evaluate(target));
189         }
190
191         return true;
192
193 };
194
195         MT_Vector3 
196 LOD_QuadricEditor::
197 TargetVertex(
198         LOD_Edge & e
199 ){
200
201         // compute an edge contration target for edge ei
202         // this is computed by summing it's vertices quadrics and 
203         // optimizing the result.
204         vector<LOD_Vertex> &verts = m_mesh.VertexSet();
205
206         vector<LOD_Quadric> &quadrics = *m_quadrics;
207
208         LOD_VertexInd v0 = e.m_verts[0];
209         LOD_VertexInd v1 = e.m_verts[1];
210
211         LOD_Quadric q0 = quadrics[v0];
212         q0 += quadrics[v1];
213
214         MT_Vector3 result;
215
216         if (q0.Optimize(result)) {
217                 return result;
218         } else {
219                 // the quadric was degenerate -> just take the average of 
220                 // v0 and v1
221
222                 return ((verts[v0].pos + verts[v1].pos) * 0.5);
223         }
224 };
225
226         void
227 LOD_QuadricEditor::
228 ComputeEdgeCosts(
229         vector<LOD_EdgeInd> &edges
230 ){      
231         
232         // for each we compute the target vertex and then compute
233         // the quadric error e = Q1(v') + Q2(v')
234         vector<LOD_Edge> &edge_set = m_mesh.EdgeSet();
235
236         vector<LOD_Quadric> &quadrics = *m_quadrics;
237
238         vector<LOD_EdgeInd>::const_iterator edge_it = edges.begin();
239         vector<LOD_EdgeInd>::const_iterator edge_end = edges.end();
240
241         for (; edge_it != edge_end; ++edge_it)  {
242                 
243                 MT_Vector3 target = TargetVertex(edge_set[*edge_it]);
244
245                 LOD_Edge &e = edge_set[*edge_it];
246                 LOD_Quadric q0 = quadrics[e.m_verts[0]];
247                 const LOD_Quadric &q1 = quadrics[e.m_verts[1]];
248                 
249                 e.HeapKey() = -float(q0.Evaluate(target) + q1.Evaluate(target));
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
281
282