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