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