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