Reverting change to decimation to fix compatibility with
[blender.git] / intern / decimation / intern / LOD_ManMesh2.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_ManMesh2.h"
37
38 #include "MT_assert.h"
39 #include <algorithm>
40 #include "LOD_MeshException.h"
41 #include "CTR_TaggedSetOps.h"
42 #include "CTR_UHeap.h"
43 #include "LOD_ExternBufferEditor.h"
44
45
46 using namespace std;
47
48 LOD_ManMesh2::
49 LOD_ManMesh2(
50 ) :
51         m_bbox_min(0,0,0),
52         m_bbox_max(0,0,0)
53 {
54 }
55         
56
57         LOD_ManMesh2 *
58 LOD_ManMesh2::
59 New(
60 ){
61         MEM_SmartPtr<LOD_ManMesh2> output(new LOD_ManMesh2());
62         if (output == NULL) return NULL;
63
64         // build the vertex, edge and face sets.
65
66         MEM_SmartPtr<vector<LOD_Vertex> > verts(new vector<LOD_Vertex>);
67         MEM_SmartPtr<vector<LOD_TriFace> > faces(new vector<LOD_TriFace>);
68         MEM_SmartPtr<vector<LOD_Edge> > edges(new vector<LOD_Edge>);
69         
70         if ((faces == NULL) || (edges == NULL) || (verts == NULL)) {
71                 return NULL;
72         }
73         
74         output->m_verts = verts.Release();
75         output->m_faces = faces.Release();
76         output->m_edges = edges.Release();
77
78         return output.Release();
79 }       
80
81 // take ownership of the vertices.
82
83         bool    
84 LOD_ManMesh2::
85 SetVertices(
86         MEM_SmartPtr<vector<LOD_Vertex> > verts
87 ){
88
89
90         // take ownership of vertices
91         m_verts = verts;
92
93         // create a polygon and edge buffer of half the size 
94         // and just use the automatic resizing feature of vector<>
95         // to worry about the dynamic array resizing
96         
97         m_faces->clear();
98         m_edges->clear();
99
100         m_faces->reserve(m_verts->size()/2);
101         m_edges->reserve(m_verts->size()/2);
102
103         return true;    
104
105 }
106
107         
108 // add a triangle to the mesh
109
110         void
111 LOD_ManMesh2::
112 AddTriangle(
113         int verts[3]
114 ) {
115
116         MT_assert(verts[0] < int(m_verts->size()));
117         MT_assert(verts[1] < int(m_verts->size()));
118         MT_assert(verts[2] < int(m_verts->size()));
119
120         LOD_TriFace face;
121         face.m_verts[0] = verts[0];
122         face.m_verts[1] = verts[1];
123         face.m_verts[2] = verts[2];
124
125         LOD_FaceInd face_index = m_faces->size();
126
127         m_faces->push_back(face);       
128
129         // now work out if any of the directed edges or their
130         // companion edges exist already.
131         // We go through the edges associated with each of the given vertices 
132
133         // the safest thing to do is iterate through each of the edge sets
134         // check against each of the 2 other triangle edges to see if they are there
135         
136         vector<LOD_EdgeInd> new_edges;
137         new_edges.reserve(3);
138
139         InsertEdge(verts[0],verts[1],face_index,new_edges);
140         InsertEdge(verts[1],verts[2],face_index,new_edges);
141         InsertEdge(verts[2],verts[0],face_index,new_edges);
142
143 }
144         
145 // Adds the index of any created edges to new_edges
146
147         bool
148 LOD_ManMesh2::
149 InsertEdge(
150         const LOD_VertexInd v1,
151         const LOD_VertexInd v2,
152         const LOD_FaceInd f,
153         vector<LOD_EdgeInd> &new_edges
154 ){
155         
156         MT_assert(!v1.IsEmpty());
157         MT_assert(!v2.IsEmpty());
158         MT_assert(!f.IsEmpty());
159
160         vector<LOD_Vertex> &verts = VertexSet();
161         vector<LOD_Edge> &edges = EdgeSet();
162         
163         LOD_EdgeInd e;
164
165         e = FindEdge(v1,v2);
166
167         if (e.IsEmpty()) {
168                 // This edge does not exist -- make a new one 
169
170                 LOD_Edge temp_e;
171                 temp_e.m_verts[0] = v1;
172                 temp_e.m_verts[1] = v2;
173
174                 e = m_edges->size();
175
176                 // set the face ptr for this half-edge
177                 temp_e.m_faces[0] = f;
178
179                 m_edges->push_back(temp_e);
180
181                 // add the edge index to it's vertices 
182
183                 verts[v1].AddEdge(e);
184                 verts[v2].AddEdge(e);
185
186                 new_edges.push_back(e);
187
188         } else {
189
190                 // edge already exists
191                 // insure that there is no polygon already
192                 // attached to the other side of this edge
193
194                 // swap the empty face pointer in edge with f
195
196                 LOD_Edge &edge = edges[e];
197
198                 edge.SwapFace(LOD_FaceInd::Empty(),f);
199         }
200                 
201
202         return true;
203
204 }
205
206         void
207 LOD_ManMesh2::
208 ConnectTriangle(
209         LOD_FaceInd fi,
210         std::vector<LOD_EdgeInd> & new_edges
211 ){
212
213         vector<LOD_TriFace> &faces = FaceSet();
214
215         MT_assert(!faces[fi].Degenerate());
216
217         LOD_TriFace & face = faces[fi];
218
219         InsertEdge(face.m_verts[0],face.m_verts[1],fi,new_edges);
220         InsertEdge(face.m_verts[1],face.m_verts[2],fi,new_edges);
221         InsertEdge(face.m_verts[2],face.m_verts[0],fi,new_edges);
222 };
223
224
225
226
227 // geometry access
228 //////////////////
229
230         vector<LOD_Vertex> &
231 LOD_ManMesh2::
232 VertexSet(
233 ) const {
234         return m_verts.Ref();
235 }               
236
237         vector<LOD_TriFace> &
238 LOD_ManMesh2::
239 FaceSet(
240 ) const {
241         return m_faces.Ref();
242 }
243
244         vector<LOD_Edge> &
245 LOD_ManMesh2::
246 EdgeSet(
247 ) const {
248         return m_edges.Ref();
249 };
250
251 LOD_ManMesh2::
252 ~LOD_ManMesh2(
253 ){
254         //auto ptr takes care of vertex arrays etc.
255 }
256
257         LOD_EdgeInd
258 LOD_ManMesh2::
259 FindEdge(
260         const LOD_VertexInd v1,
261         const LOD_VertexInd v2
262 ) {
263
264         vector<LOD_Vertex> &verts = VertexSet();
265         vector<LOD_Edge> &edges = EdgeSet();
266
267         LOD_Edge e;
268         e.m_verts[0] = v1;
269         e.m_verts[1] = v2;
270         
271         vector<LOD_EdgeInd> &v1_edges = verts[v1].m_edges;
272         vector<LOD_EdgeInd>::const_iterator v1_end = v1_edges.end();
273         vector<LOD_EdgeInd>::iterator v1_begin = v1_edges.begin();
274
275         for (; v1_begin != v1_end; ++v1_begin) {
276                 if (edges[*v1_begin] == e) return *v1_begin;
277         }
278         
279         return LOD_EdgeInd::Empty();
280 }
281
282 // face queries
283 ///////////////
284
285         void
286 LOD_ManMesh2::
287 FaceVertices(
288         LOD_FaceInd fi,
289         vector<LOD_VertexInd> &output
290 ){      
291         const vector<LOD_TriFace> &faces = FaceSet();
292         const LOD_TriFace & f = faces[fi];
293
294         output.push_back(f.m_verts[0]);
295         output.push_back(f.m_verts[1]);
296         output.push_back(f.m_verts[2]);
297 }
298         
299         void
300 LOD_ManMesh2::
301 FaceEdges(
302         LOD_FaceInd fi,
303         vector<LOD_EdgeInd> &output
304 ){
305         const vector<LOD_TriFace> &faces = FaceSet();
306         vector<LOD_Edge> &edges = EdgeSet();
307         vector<LOD_Vertex> &verts = VertexSet();        
308
309         const LOD_TriFace & f = faces[fi];
310         // intersect vertex edges
311
312         vector<LOD_EdgeInd> & v0_edges = verts[f.m_verts[0]].m_edges;
313         vector<LOD_EdgeInd> & v1_edges = verts[f.m_verts[1]].m_edges;
314         vector<LOD_EdgeInd> & v2_edges = verts[f.m_verts[2]].m_edges;
315
316         CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v0_edges,v1_edges,edges,output);
317         CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v1_edges,v2_edges,edges,output);
318         CTR_TaggedSetOps<LOD_EdgeInd,LOD_Edge>::IntersectPair(v2_edges,v0_edges,edges,output);
319
320         MT_assert(output.size() == 3);
321         if (output.size() != 3) {
322                 LOD_MeshException e(LOD_MeshException::e_non_manifold);
323                 throw(e);       
324         }
325 }
326         
327
328 // edge queries
329 ///////////////
330
331         void
332 LOD_ManMesh2::
333 EdgeVertices(
334         LOD_EdgeInd ei,
335         vector<LOD_VertexInd> &output
336 ){
337         const vector<LOD_Edge> &edges = EdgeSet();
338         const LOD_Edge & e = edges[ei];
339
340         output.push_back(e.m_verts[0]);
341         output.push_back(e.m_verts[1]);
342 }
343
344         void
345 LOD_ManMesh2::
346 EdgeFaces(
347         LOD_EdgeInd ei,
348         vector<LOD_FaceInd> &output
349 ){
350         const vector<LOD_Edge> &edges = EdgeSet();
351         const LOD_Edge & e = edges[ei];
352
353         if (!e.m_faces[0].IsEmpty()) {
354                 output.push_back(e.m_faces[0]);
355         }
356         if (!e.m_faces[1].IsEmpty()) {
357                 output.push_back(e.m_faces[1]);
358         }
359 }       
360
361 // vertex queries
362 /////////////////
363
364         void
365 LOD_ManMesh2::
366 VertexEdges(
367         LOD_VertexInd vi,
368         vector<LOD_EdgeInd> &output
369 ){
370         // iterate through the edges of v and push them onto the 
371         // output
372         
373         vector<LOD_Vertex> &verts = VertexSet();
374
375         vector<LOD_EdgeInd> & v_edges = verts[vi].m_edges;
376         vector<LOD_EdgeInd>::iterator v_it = v_edges.begin();
377
378         for (; v_it != v_edges.end(); ++v_it) {
379                 output.push_back(*v_it);
380         }       
381 }
382
383         void
384 LOD_ManMesh2::
385 VertexFaces(
386         LOD_VertexInd vi,
387         vector<LOD_FaceInd> &output
388 ){
389         const vector<LOD_Vertex> &verts = VertexSet();
390         vector<LOD_Edge> &edges = EdgeSet();
391         vector<LOD_TriFace> &faces = FaceSet();
392
393         const vector<LOD_EdgeInd> &v_edges = verts[vi].m_edges;
394         vector<LOD_EdgeInd>::const_iterator e_it = v_edges.begin();
395
396         for (; e_it != v_edges.end(); ++e_it) {
397
398                 LOD_Edge &e = edges[*e_it]; 
399
400                 if ((!e.m_faces[0].IsEmpty()) && (!faces[e.m_faces[0]].SelectTag())) {
401                         output.push_back(e.m_faces[0]);
402                         faces[e.m_faces[0]].SetSelectTag(true);
403                 }
404
405                 if ((!e.m_faces[1].IsEmpty()) && (!faces[e.m_faces[1]].SelectTag())) {
406                         output.push_back(e.m_faces[1]);
407                         faces[e.m_faces[1]].SetSelectTag(true);
408                 }
409         }
410
411         vector<LOD_FaceInd>::iterator f_it = output.begin();
412
413         for (; f_it != output.end(); ++f_it) {
414                 faces[*f_it].SetSelectTag(false);
415         }
416 };
417                 
418         void
419 LOD_ManMesh2::
420 SetBBox(
421         MT_Vector3 bbox_min,
422         MT_Vector3 bbox_max
423 ){
424         m_bbox_min = bbox_min;
425         m_bbox_max = bbox_max;
426 };
427
428         void
429 LOD_ManMesh2::
430 SC_TriFace(
431         LOD_FaceInd f
432 ){
433         LOD_TriFace face = (*m_faces)[f];
434         
435         // check for unique vertices
436
437         if (
438                 (face.m_verts[0] == face.m_verts[1]) ||
439                 (face.m_verts[1] == face.m_verts[2]) ||
440                 (face.m_verts[2] == face.m_verts[0])
441         ) {
442                 MT_assert(false);
443         }       
444
445 }
446
447
448         void
449 LOD_ManMesh2::
450 SC_EdgeList(
451         LOD_VertexInd v
452 ){
453         vector<LOD_Edge> &edges = EdgeSet();
454         vector<LOD_Vertex> &verts = VertexSet();
455
456         vector<LOD_EdgeInd>::iterator e_it = verts[v].m_edges.begin();
457
458         for (;e_it != verts[v].m_edges.end(); ++e_it) {
459                 MT_assert( (edges[*e_it].m_verts[0] == v) || (edges[*e_it].m_verts[1] == v));
460         }                               
461
462 };
463         
464         void
465 LOD_ManMesh2::
466 DeleteVertex(
467         LOD_ExternBufferEditor & extern_editor,
468         LOD_VertexInd v
469 ){
470
471         vector<LOD_Edge> &edges = EdgeSet();
472         vector<LOD_Vertex> &verts = VertexSet();
473         vector<LOD_TriFace> &faces = FaceSet();
474
475         // need to update all the edge and polygons pointing to 
476         // the last vertex in m_verts
477
478         if (verts.size() == 1) {
479                 verts.clear();
480                 return;
481         }
482
483         LOD_VertexInd last = LOD_VertexInd(verts.end() - verts.begin() - 1);
484
485         if (!(last == v)) {
486
487                 // we asume that v is already disconnected
488
489                 vector<LOD_FaceInd> v_faces;
490                 vector<LOD_EdgeInd> v_edges;
491
492                 v_faces.reserve(64);
493                 v_edges.reserve(64);
494
495                 VertexFaces(last,v_faces);
496                 VertexEdges(last,v_edges);
497
498                 // map the faces and edges to look at v 
499
500                 vector<LOD_FaceInd>::iterator face_it = v_faces.begin();
501
502                 for(; face_it != v_faces.end(); ++face_it) {
503                         faces[*face_it].SwapVertex(last,v);
504                 }
505                 vector<LOD_EdgeInd>::iterator edge_it = v_edges.begin();
506
507                 for (; edge_it != v_edges.end(); ++edge_it) {
508                         edges[*edge_it].SwapVertex(last,v);
509                 }
510
511                 // copy the last vertex onto v and pop off the back.
512
513                 verts[v] = verts[last];
514
515                 // tidy external buffer
516                 extern_editor.CopyModifiedFaces(*this,v_faces);
517         }
518
519         verts.pop_back();       
520         extern_editor.CopyBackVertex(v);
521
522
523 };              
524
525         void
526 LOD_ManMesh2::
527 DeleteEdge(
528         LOD_EdgeInd e,
529         CTR_UHeap<LOD_Edge> * heap
530 ){
531         vector<LOD_Edge> &edges = EdgeSet();
532         vector<LOD_Vertex> &verts = VertexSet();
533
534         if (edges.size() == 1) {
535                 edges.clear();
536                 return;
537         }
538
539         LOD_EdgeInd last = LOD_EdgeInd(edges.end() - edges.begin() - 1);
540
541         if (!(last == e)) {
542                 vector<LOD_EdgeInd> e_verts;
543                 e_verts.reserve(2);
544                 EdgeVertices(last,e_verts);
545                 // something is wrong if there arent two!
546
547                 verts[e_verts[0]].SwapEdge(last,e);
548                 verts[e_verts[1]].SwapEdge(last,e);
549
550                 // edges[e] should already have been removed from the heap
551
552                 MT_assert(edges[e].HeapPos() == 0xffffffff);
553
554                 edges[e] = edges[last];
555                 // also have to swap there heap positions.!!!!!
556
557                 heap->HeapVector()[edges[e].HeapPos()] = e;
558
559
560         }
561         edges.pop_back();
562 };
563         
564         void
565 LOD_ManMesh2::
566 DeleteFace(
567         LOD_ExternBufferEditor & extern_editor,
568         LOD_FaceInd f
569 ){
570
571         vector<LOD_Edge> &edges = EdgeSet();
572         vector<LOD_TriFace> &faces = FaceSet();
573
574         if (faces.size() == 1) {
575                 faces.clear();
576                 return;
577         }
578
579         LOD_FaceInd last = LOD_FaceInd(faces.end() - faces.begin() - 1);
580
581         if (!(last == f)) {
582                 
583                 // we have to update the edges which point to the last 
584                 // face 
585
586                 vector<LOD_EdgeInd> f_edges;
587                 f_edges.reserve(3);
588
589                 FaceEdges(last,f_edges);
590
591                 vector<LOD_EdgeInd>::iterator edge_it = f_edges.begin();
592                 vector<LOD_EdgeInd>::const_iterator edge_end = f_edges.end();
593         
594                 for (; edge_it != edge_end; ++edge_it) {
595                         edges[*edge_it].SwapFace(last,f);
596                 }
597
598                 faces[f] = faces[last];
599
600         }
601         faces.pop_back();
602
603         // tidy external buffers
604         extern_editor.CopyBackFace(f);
605 };      
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621