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