Reverting change to decimation to fix compatibility with
[blender.git] / intern / decimation / intern / LOD_EdgeCollapser.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_EdgeCollapser.h"
37
38 #include "LOD_ManMesh2.h"
39 #include "CTR_TaggedSetOps.h"
40 #include <algorithm>
41 #include <functional>
42
43
44 using namespace std;
45
46
47         LOD_EdgeCollapser * 
48 LOD_EdgeCollapser::
49 New(
50 ){
51         return new LOD_EdgeCollapser();
52 }
53
54
55         bool
56 LOD_EdgeCollapser::
57 TJunctionTest(
58         LOD_ManMesh2 &mesh,
59         vector<LOD_EdgeInd> &e_v0v1,
60         LOD_EdgeInd collapse_edge
61 ){
62
63         // we need to copy the egdes in e_v0v1 from the mesh
64         // into a new buffer -> we are going to modify them
65
66         int original_size = e_v0v1.size();
67         if (original_size == 0) return true;
68
69         vector<LOD_Edge> &edge_set = mesh.EdgeSet();
70
71         LOD_VertexInd c_v0 = edge_set[collapse_edge].m_verts[0];
72         LOD_VertexInd c_v1 = edge_set[collapse_edge].m_verts[1];
73
74         vector<LOD_Edge> temp_edges;
75         temp_edges.reserve(e_v0v1.size());
76
77         vector<LOD_EdgeInd>::iterator edge_it = e_v0v1.begin();
78         vector<LOD_EdgeInd>::const_iterator edge_end = e_v0v1.end();
79
80         for (;edge_it != edge_end; ++edge_it) {
81                 temp_edges.push_back(edge_set[*edge_it]);
82         }
83
84         // in the copied edges replace all instances of c_v0 with c_v1
85
86         vector<LOD_Edge>::iterator e_it = temp_edges.begin();
87         vector<LOD_Edge>::const_iterator e_it_end = temp_edges.end();
88                 
89         for (; e_it != e_it_end; ++e_it) {
90
91                 if (e_it->m_verts[0] == c_v0) {
92                         e_it->m_verts[0] = c_v1;
93                 }
94                 if (e_it->m_verts[1] == c_v0) {
95                         e_it->m_verts[1] = c_v1;
96                 }
97
98                 // normalize the edge
99                 if (int(e_it->m_verts[0]) > int(e_it->m_verts[1])) {
100                         LOD_EdgeInd temp = e_it->m_verts[0];
101                         e_it->m_verts[0] = e_it->m_verts[1];
102                         e_it->m_verts[1] = temp;
103                 }
104         }
105
106         // sort the edges using the edge less functional 
107
108         sort(temp_edges.begin(),temp_edges.end(),LOD_EdgeCollapser::less());
109         // count the unique edges.
110
111         e_it = temp_edges.begin();
112         e_it_end = temp_edges.end();
113         
114         int coincedent_edges = 0;
115
116         vector<LOD_Edge>::const_iterator last_edge = e_it;
117         ++e_it;
118                 
119         for (; e_it != e_it_end; ++e_it) {
120         
121                 if ((e_it->m_verts[0] == last_edge->m_verts[0]) &&
122                         (e_it->m_verts[1] == last_edge->m_verts[1])
123                 ) {
124                         ++coincedent_edges;
125                 }
126                 last_edge = e_it;
127         }
128
129         // now if the collapse edge is a boundary edges 
130         // then we are alloved at most one coincedent edge
131
132         // otherwise at most 2 coincedent edges
133
134         if (edge_set[collapse_edge].BoundaryEdge()) {
135                 return (coincedent_edges > 1);
136         } else {
137                 return (coincedent_edges > 2);
138         }
139
140
141 }
142
143
144         
145         bool
146 LOD_EdgeCollapser::
147 CollapseEdge(
148         LOD_EdgeInd ei,
149         LOD_ManMesh2 &mesh,
150         vector<LOD_EdgeInd> & degenerate_edges,
151         vector<LOD_FaceInd> & degenerate_faces,
152         vector<LOD_VertexInd> & degenerate_vertices,
153         vector<LOD_EdgeInd> & new_edges,
154         vector<LOD_FaceInd> & update_faces,
155         vector<LOD_VertexInd> & update_vertices
156 ){
157
158         vector<LOD_Vertex>      &verts = mesh.VertexSet();
159         vector<LOD_Edge>        &edges = mesh.EdgeSet();
160         vector<LOD_TriFace> &faces = mesh.FaceSet();
161
162         // shouldn't do this (use mesh interface instead!)
163         LOD_VertexInd v0_ind = edges[ei].m_verts[0];
164         LOD_VertexInd v1_ind = edges[ei].m_verts[1];
165 #if 0
166         LOD_Vertex &v0 = verts[v0_ind];
167         LOD_Vertex &v1 = verts[v1_ind];
168 #endif
169         vector<vector<LOD_EdgeInd> > e_v01(2);
170         e_v01[0].reserve(32);
171         e_v01[1].reserve(32);
172         
173         mesh.VertexEdges(v0_ind,e_v01[0]);
174         mesh.VertexEdges(v1_ind,e_v01[1]);
175
176
177         // compute the union of e_v0 and e_v1 -> this is the degenerate edges of the collapse
178         // we remove old edges and replace edges inside the collapse zone with new ones 
179
180         CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::Union(e_v01,edges,degenerate_edges);
181
182         vector< vector<LOD_FaceInd> > p_v01(2);
183         p_v01[0].reserve(32);
184         p_v01[1].reserve(32);
185
186         mesh.VertexFaces(v0_ind,p_v01[0]);
187         mesh.VertexFaces(v1_ind,p_v01[1]);
188
189         // compute the union of p_v0 anf p_v1
190         vector<LOD_FaceInd> p_v0v1;
191         p_v0v1.reserve(32);
192
193         CTR_TaggedSetOps<LOD_FaceInd,LOD_TriFace>::Union(p_v01,faces,p_v0v1);
194
195         // compute the union of all the edges in p_v0v1 this is the collapse zone
196
197         vector<vector<LOD_EdgeInd> > e_input_vectors(p_v0v1.size());
198
199         vector<LOD_FaceInd>::iterator p_v0v1_end = p_v0v1.end();
200         vector<LOD_FaceInd>::iterator p_v0v1_start = p_v0v1.begin();
201
202         vector<vector<LOD_FaceInd> >::iterator vector_insert_it = e_input_vectors.begin();
203         
204         for (;p_v0v1_start != p_v0v1_end; ++p_v0v1_start , ++vector_insert_it) {
205                 mesh.FaceEdges(*p_v0v1_start,*vector_insert_it);
206         }
207
208         vector<LOD_EdgeInd> collapse_zone;
209         collapse_zone.reserve(32);
210
211         CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::Union(e_input_vectors,edges,collapse_zone);
212
213         // compute the ring edges = collpase_zone - e_v0v1
214
215         vector<LOD_EdgeInd> edge_ring;
216         edge_ring.reserve(32);
217
218         CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::Difference(collapse_zone,degenerate_edges,edges,edge_ring);
219
220         // T Junction test
221         //////////////////
222         // At this point we check to see if any of the polygons
223         // in p_v0v1 are coninceddent - this leads
224         // to errors later on if we try and insert a polygon
225         // into the mesh to an edge which already has 2 polygons.
226
227         // not that t junctions occur naturally from edge collapses
228         // and are not just the result of coincedent polygons
229         // for example consider collapsing an edge that forms part
230         // of a triangular bottle neck.
231
232         // Really we need to make sure that we don't create t-junctions.
233
234         // I think that a sufficient test is to check the number of
235         // coincedent edge pairs after a collapse. If it is more than 2
236         // then collapsing the edge may result in an undeleted edge 
237         // sharing more than 2 polygons. This test probably is too 
238         // restictive though.
239         
240         // To perform this test we need to make a copy of the edges
241         // in e_v0v1. We then apply the contraction to these edge
242         // copies. Sort them using a function that places coincedent 
243         // edges next to each other. And then count the number
244         // of coincedent pairs. 
245
246         // Of course we have to do this test before we change any of the
247         // mesh -> so we can back out safely.
248
249         if (TJunctionTest(mesh,degenerate_edges,ei)) return false; 
250
251         // Compute the set of possibly degenerate vertices
252         // this is the union of all the vertices of polygons
253         // of v0 and v1
254
255         vector<LOD_FaceInd>::iterator face_it = p_v0v1.begin();
256         vector<LOD_FaceInd>::const_iterator face_end = p_v0v1.end();
257
258
259         vector<vector<LOD_VertexInd> > p_v0v1_vertices(p_v0v1.size());
260         
261         for (int i = 0; face_it != face_end; ++face_it, ++i) {
262                 mesh.FaceVertices(*face_it,p_v0v1_vertices[i]);
263         }
264         
265         vector<LOD_VertexInd> vertex_ring;
266         vertex_ring.reserve(32);
267
268         CTR_TaggedSetOps<LOD_VertexInd,LOD_Vertex>::Union(p_v0v1_vertices,verts,vertex_ring);
269
270         // remove all the internal edges e_v0v1 from the mesh.
271         // for each edge remove the egde from it's vertices edge lists.
272
273         vector<LOD_EdgeInd>::iterator edge_it = degenerate_edges.begin();
274         vector<LOD_EdgeInd>::const_iterator edge_end = degenerate_edges.end();
275
276         for (; edge_it != edge_end; ++edge_it) {
277                         
278                 LOD_Edge & edge = edges[*edge_it];
279         
280                 verts[edge.m_verts[0]].RemoveEdge(*edge_it);
281                 verts[edge.m_verts[1]].RemoveEdge(*edge_it);
282         }
283
284         // we postpone deletion of the internal edges untill the end
285         // this is because deleting edges invalidates all of the 
286         // EdgeInd vectors above.
287
288                 
289         // now untie all the polygons in p_v0v1 from the edge ring
290
291         // select all polygons in p_v0v1
292
293         face_it = p_v0v1.begin();
294         face_end = p_v0v1.end();
295
296         for (;face_it != face_end; ++face_it) {
297                 faces[*face_it].SetSelectTag(true);
298         }
299
300         edge_it = edge_ring.begin();
301         edge_end = edge_ring.end();
302
303         for (;edge_it != edge_end; ++edge_it) {
304                 LOD_Edge & edge = edges[*edge_it];
305
306                 // presumably all edges in edge_ring point to at least
307                 // one polygon from p_v0v1
308                 
309                 if (!edge.m_faces[0].IsEmpty() && faces[edge.m_faces[0]].SelectTag()) {
310                         edge.m_faces[0].Invalidate();
311                 }
312
313                 if (!edge.m_faces[1].IsEmpty() && faces[edge.m_faces[1]].SelectTag()) {
314                         edge.m_faces[1].Invalidate();
315                 }
316         }
317         
318         // deselect the faces
319
320         face_it = p_v0v1.begin();
321         face_end = p_v0v1.end();
322
323         for (;face_it != face_end; ++face_it) {
324                 faces[*face_it].SetSelectTag(false);
325         }
326
327         // perform the edge collapse
328         ////////////////////////////
329
330         // iterate through the polygons of p_v0 and replace the vertex
331         // index v0 with v1
332
333         face_it = p_v01[0].begin();
334         face_end = p_v01[0].end();
335         
336         for (;face_it != face_end; ++face_it) {
337                 faces[*face_it].SwapVertex(v0_ind,v1_ind);
338         }
339
340         face_it = p_v0v1.begin();
341         face_end = p_v0v1.end();
342         
343         for (;face_it != face_end; ++face_it) {
344                 if (faces[*face_it].Degenerate()) {
345                         degenerate_faces.push_back(*face_it);
346                 } else {
347                         update_faces.push_back(*face_it);
348                 }
349         }
350         
351         // Add all the non-degenerate faces back into the 
352         // mesh. Get a record of the new edges created in
353         // this process.
354
355         face_it = update_faces.begin();
356         face_end = update_faces.end();
357
358         for (;face_it != face_end; ++face_it) {
359                 mesh.ConnectTriangle(*face_it,new_edges);
360         }
361
362         // degenerate ring primitives
363         /////////////////////////////
364
365         // we now need to examine each of the edges on the ring
366         // and work out if they are degenerate - if so we attempt
367         // to delete them -> add them to the other edges to delete
368         // in e_v0v1
369
370         edge_it = edge_ring.begin();
371         edge_end = edge_ring.end();
372
373         for (;edge_it != edge_end; ++edge_it) {
374                 if (edges[*edge_it].Degenerate()) {
375                         degenerate_edges.push_back(*edge_it);
376                 }
377         }
378
379         // do the same for the ring vertices.
380                 
381         vector<LOD_VertexInd>::iterator vertex_it = vertex_ring.begin();
382         vector<LOD_VertexInd>::const_iterator vertex_end = vertex_ring.end();
383
384         for (;vertex_it != vertex_end; ++vertex_it) {
385                 if (verts[*vertex_it].Degenerate()) {
386                         degenerate_vertices.push_back(*vertex_it);
387                 } else {
388                         update_vertices.push_back(*vertex_it);
389                 }
390         }
391
392         // we now know all the degenerate primitives
393         // and the new primitives we have inserted into the mesh
394
395         // We now delete the mesh primitives, mesh.DeleteXXXXXX() methods
396         // assume that the index vectors are sorted into descending order.
397         // we do that now.
398
399         sort(degenerate_edges.begin(),degenerate_edges.end(),LOD_EdgeInd::greater());
400         sort(degenerate_faces.begin(),degenerate_faces.end(),LOD_FaceInd::greater());
401         sort(degenerate_vertices.begin(),degenerate_vertices.end(),LOD_VertexInd::greater());
402
403         
404         return true;
405         
406 }
407
408 LOD_EdgeCollapser::
409 LOD_EdgeCollapser(
410 ){
411         // nothing to do
412 }