r34526 removed a line which had an unused return value but still needed to run.
[blender-staging.git] / intern / bsp / intern / BSP_CSGMesh.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
30 #include "BSP_CSGMesh.h"
31 #include "MT_assert.h"
32 #include "CTR_TaggedSetOps.h"
33 #include "MT_Plane3.h"
34 #include "BSP_CSGException.h"
35
36 // for insert_iterator
37 #include <iterator>
38
39 // for vector reverse
40 #include <iostream>
41 #include <algorithm>
42 using namespace std;
43
44 BSP_CSGMesh::
45 BSP_CSGMesh(
46 ) :
47         MEM_RefCountable()
48 {
49         m_verts     = NULL;
50         m_faces     = NULL;
51         m_edges     = NULL;
52 }
53
54         BSP_CSGMesh *
55 BSP_CSGMesh::
56 New(
57 ){
58         return new BSP_CSGMesh();
59 }
60
61         BSP_CSGMesh *
62 BSP_CSGMesh::
63 NewCopy(
64 ) const {
65
66         BSP_CSGMesh *mesh = New();
67         if (mesh == NULL) return NULL;
68
69         mesh->m_bbox_max = m_bbox_max;
70         mesh->m_bbox_min = m_bbox_min;
71
72         if (m_edges != NULL) {
73                 mesh->m_edges = new vector<BSP_MEdge>(*m_edges);
74                 if (mesh->m_edges == NULL) {
75                         delete mesh;
76                         return NULL;
77                 }
78         }
79         if (m_verts != NULL) {
80                 mesh->m_verts = new vector<BSP_MVertex>(*m_verts);
81                 if (mesh->m_verts == NULL) {
82                         if (m_edges != NULL) free(mesh->m_edges);
83                         delete mesh;
84                         return NULL;
85                 }
86         }
87         if (m_faces != NULL) {
88                 mesh->m_faces = new vector<BSP_MFace>(*m_faces);
89                 if (mesh->m_faces == NULL) {
90                         delete mesh;
91                         return NULL;
92                 }
93         }
94
95         return mesh;
96 }
97         
98         void
99 BSP_CSGMesh::
100 Invert(
101 ){
102
103         vector<BSP_MFace> & faces = FaceSet();
104
105         vector<BSP_MFace>::const_iterator faces_end = faces.end();
106         vector<BSP_MFace>::iterator faces_it = faces.begin();
107
108         for (; faces_it != faces_end; ++faces_it) {     
109                 faces_it->Invert();
110         }
111 }
112
113         bool
114 BSP_CSGMesh::
115 SetVertices(
116         vector<BSP_MVertex> *verts
117 ){
118         if (verts == NULL) return false;
119
120         // create polygon and edge arrays and reserve some space.
121         m_faces = new vector<BSP_MFace>;
122         if (!m_faces) return false;
123
124         m_faces->reserve(verts->size()/2);
125         
126         // previous verts get deleted here.
127         m_verts = verts;
128         return true;
129 }
130
131                 void
132 BSP_CSGMesh::
133 AddPolygon(
134         const int * verts,
135         int num_verts
136 ){
137         MT_assert(verts != NULL);
138         MT_assert(num_verts >=3);
139
140         if (verts == NULL || num_verts <3) return;
141
142         // make a polyscone from these vertex indices.
143
144         const BSP_FaceInd fi = m_faces->size();
145         m_faces->push_back(BSP_MFace());                        
146         BSP_MFace & face = m_faces->back();
147
148         insert_iterator<vector<BSP_VertexInd> > insert_point(face.m_verts,face.m_verts.end()); 
149         copy (verts,verts + num_verts,insert_point);
150
151         // compute and store the plane equation for this face.
152
153         MT_Plane3 face_plane = FacePlane(fi);   
154         face.m_plane = face_plane;
155 };
156
157 // assumes that the face already has a plane equation
158         void
159 BSP_CSGMesh::
160 AddPolygon(
161         const BSP_MFace &face
162 ){
163         m_faces->push_back(face);                       
164 };
165
166
167         bool
168 BSP_CSGMesh::
169 BuildEdges(
170 ){
171
172         if (m_faces == NULL) return false;
173
174         if (m_edges != NULL) {
175                 DestroyEdges();
176         }
177
178         m_edges = new vector<BSP_MEdge>;
179
180         if (m_edges == NULL) {
181                 return false;
182         }
183                 
184
185         //iterate through the face set and add edges for all polygon
186         //edges
187         
188         vector<BSP_MFace>::const_iterator f_it_end = FaceSet().end();
189         vector<BSP_MFace>::iterator f_it_begin = FaceSet().begin();
190         vector<BSP_MFace>::iterator f_it = FaceSet().begin();
191
192         vector<BSP_EdgeInd> dummy;
193
194         for (;f_it != f_it_end; ++f_it) {
195
196                 BSP_MFace & face = *f_it;
197
198                 int vertex_num = face.m_verts.size();
199                 BSP_VertexInd prev_vi(face.m_verts[vertex_num-1]);
200
201                 for (int vert = 0; vert < vertex_num; ++vert) {
202
203                         BSP_FaceInd fi(size_t (f_it - f_it_begin));
204                         InsertEdge(prev_vi,face.m_verts[vert],fi,dummy);
205                         prev_vi = face.m_verts[vert];
206                 }
207                         
208         }
209         dummy.clear();
210         return true;
211 }       
212                 
213         void
214 BSP_CSGMesh::
215 DestroyEdges(
216 ){
217         if ( m_edges != NULL ) {
218                 delete m_edges;
219                 m_edges = NULL;
220         }       
221         
222         // Run through the vertices
223         // and clear their edge arrays.
224
225         if (m_verts){
226
227                 vector<BSP_MVertex>::const_iterator vertex_end = VertexSet().end();
228                 vector<BSP_MVertex>::iterator vertex_it = VertexSet().begin();
229
230                 for (; vertex_it != vertex_end; ++vertex_it) {
231                         vertex_it->m_edges.clear();
232                 }
233         }
234 }
235
236
237         BSP_EdgeInd
238 BSP_CSGMesh::
239 FindEdge(
240         const BSP_VertexInd & v1,
241         const BSP_VertexInd & v2
242 ) const {
243         
244         vector<BSP_MVertex> &verts = VertexSet();
245         vector<BSP_MEdge> &edges = EdgeSet();
246
247         BSP_MEdge e;
248         e.m_verts[0] = v1;
249         e.m_verts[1] = v2;
250         
251         vector<BSP_EdgeInd> &v1_edges = verts[v1].m_edges;
252         vector<BSP_EdgeInd>::const_iterator v1_end = v1_edges.end();
253         vector<BSP_EdgeInd>::const_iterator v1_begin = v1_edges.begin();
254
255         for (; v1_begin != v1_end; ++v1_begin) {
256                 if (edges[*v1_begin] == e) return *v1_begin;
257         }
258         
259         return BSP_EdgeInd::Empty();
260 }
261
262         void
263 BSP_CSGMesh::
264 InsertEdge(
265         const BSP_VertexInd & v1,
266         const BSP_VertexInd & v2,
267         const BSP_FaceInd & f,
268         vector<BSP_EdgeInd> &new_edges
269 ){
270
271         MT_assert(!v1.IsEmpty());
272         MT_assert(!v2.IsEmpty());
273         MT_assert(!f.IsEmpty());
274
275         if (v1.IsEmpty() || v2.IsEmpty() || f.IsEmpty()) {
276                 BSP_CSGException e(e_mesh_error);
277                 throw (e);
278         }
279
280         vector<BSP_MVertex> &verts = VertexSet();
281         vector<BSP_MEdge> &edges = EdgeSet();
282         
283         BSP_EdgeInd e;
284
285         e = FindEdge(v1,v2);
286         if (e.IsEmpty()) {
287                 // This edge does not exist -- make a new one 
288
289                 BSP_MEdge temp_e;
290                 temp_e.m_verts[0] = v1;
291                 temp_e.m_verts[1] = v2;
292
293                 e = m_edges->size();
294                 // set the face index from the edge back to this polygon.
295                 temp_e.m_faces.push_back(f);
296
297                 m_edges->push_back(temp_e);
298
299                 // add the edge index to it's vertices 
300                 verts[v1].AddEdge(e);
301                 verts[v2].AddEdge(e);
302
303                 new_edges.push_back(e);
304
305         } else {
306
307                 // edge already exists
308                 // insure that there is no polygon already
309                 // attached to the other side of this edge
310                 // swap the empty face pointer in edge with f
311
312                 BSP_MEdge &edge = edges[e];
313
314                 // set the face index from the edge back to this polygon.
315                 edge.m_faces.push_back(f);
316         }
317 }               
318
319
320 // geometry access
321 //////////////////
322
323         vector<BSP_MVertex> &
324 BSP_CSGMesh::
325 VertexSet(
326 ) const {
327         return *m_verts;
328 }               
329
330         vector<BSP_MFace> &
331 BSP_CSGMesh::
332 FaceSet(
333 ) const {
334         return *m_faces;
335 }
336
337         vector<BSP_MEdge> &
338 BSP_CSGMesh::
339 EdgeSet(
340 ) const {
341         return *m_edges;
342 }
343
344 BSP_CSGMesh::
345 ~BSP_CSGMesh(
346 ){
347         if ( m_verts != NULL ) delete m_verts;
348         if ( m_faces != NULL ) delete m_faces;
349         if ( m_edges != NULL ) delete m_edges;
350 }
351
352 // local geometry queries.
353 /////////////////////////
354
355 // face queries
356 ///////////////
357
358         void
359 BSP_CSGMesh::
360 FaceVertices(
361         const BSP_FaceInd & f,
362         vector<BSP_VertexInd> &output
363 ){
364         vector<BSP_MFace> & face_set = FaceSet();
365         output.insert(
366                 output.end(),
367                 face_set[f].m_verts.begin(),
368                 face_set[f].m_verts.end()
369         );
370 }
371
372
373         void
374 BSP_CSGMesh::
375 FaceEdges(
376         const BSP_FaceInd & fi,
377         vector<BSP_EdgeInd> &output
378 ){
379         // take intersection of the edges emminating from all the vertices
380         // of this polygon;
381
382         vector<BSP_MFace> &faces = FaceSet();
383         vector<BSP_MEdge> &edges = EdgeSet();
384
385         const BSP_MFace & f = faces[fi];
386
387         // collect vertex edges;
388
389         vector<BSP_VertexInd>::const_iterator face_verts_it = f.m_verts.begin();
390         vector<BSP_VertexInd>::const_iterator face_verts_end = f.m_verts.end();
391
392         vector< vector<BSP_EdgeInd> > vertex_edges(f.m_verts.size());
393                 
394         int vector_slot = 0;
395
396         for (;face_verts_it != face_verts_end; ++face_verts_it, ++vector_slot) {
397                 VertexEdges(*face_verts_it,vertex_edges[vector_slot]);
398         }       
399
400         int prev = vector_slot - 1; 
401
402         // intersect pairs of edge sets 
403
404         for (int i = 0; i < vector_slot;i++) {
405                 CTR_TaggedSetOps<BSP_EdgeInd,BSP_MEdge>::IntersectPair(vertex_edges[prev],vertex_edges[i],edges,output);        
406                 prev = i;
407         }
408         
409         // should always have 3 or more unique edges per face.
410         MT_assert(output.size() >=3);
411
412         if (output.size() < 3) {
413                 BSP_CSGException e(e_mesh_error);
414                 throw(e);
415         }
416 };
417         
418 // edge queries
419 ///////////////
420
421         void
422 BSP_CSGMesh::
423 EdgeVertices(
424         const BSP_EdgeInd & e,
425         vector<BSP_VertexInd> &output
426 ){
427         const vector<BSP_MEdge> &edges = EdgeSet();
428         output.push_back(edges[e].m_verts[0]);
429         output.push_back(edges[e].m_verts[1]);
430
431
432         void
433 BSP_CSGMesh::
434 EdgeFaces(
435         const BSP_EdgeInd & e,
436         vector<BSP_FaceInd> &output
437 ){
438
439         vector<BSP_MEdge> & edge_set = EdgeSet();
440         output.insert(
441                 output.end(),
442                 edge_set[e].m_faces.begin(),
443                 edge_set[e].m_faces.end()
444         );
445         
446 }
447
448 // vertex queries
449 /////////////////
450
451         void
452 BSP_CSGMesh::
453 VertexEdges(
454         const BSP_VertexInd &v,
455         vector<BSP_EdgeInd> &output
456 ){
457
458         vector<BSP_MVertex> & vertex_set = VertexSet();
459         output.insert(
460                 output.end(),
461                 vertex_set[v].m_edges.begin(),
462                 vertex_set[v].m_edges.end()
463         );
464 }
465
466         void
467 BSP_CSGMesh::
468 VertexFaces(
469         const BSP_VertexInd &vi,
470         vector<BSP_FaceInd> &output
471 ) {
472
473         vector<BSP_MEdge> &edges = EdgeSet();
474         vector<BSP_MFace> &faces = FaceSet();
475         vector<BSP_MVertex> &verts = VertexSet();
476
477         const vector<BSP_EdgeInd> &v_edges = verts[vi].m_edges;
478         vector<BSP_EdgeInd>::const_iterator e_it = v_edges.begin();
479
480         for (; e_it != v_edges.end(); ++e_it) {
481
482                 BSP_MEdge &e = edges[*e_it]; 
483
484                 // iterate through the faces of this edge - push unselected
485                 // edges to ouput and then select the edge
486
487                 vector<BSP_FaceInd>::const_iterator e_faces_end = e.m_faces.end();
488                 vector<BSP_FaceInd>::iterator e_faces_it = e.m_faces.begin();
489
490                 for (;e_faces_it != e_faces_end; ++e_faces_it) {
491
492                         if (!faces[*e_faces_it].SelectTag()) {
493                                 output.push_back(*e_faces_it);
494                                 faces[*e_faces_it].SetSelectTag(true);
495                         }
496                 }
497         }
498
499         // deselect selected faces.
500         vector<BSP_FaceInd>::iterator f_it = output.begin();
501
502         for (; f_it != output.end(); ++f_it) {
503                 faces[*f_it].SetSelectTag(false);
504         }
505 }
506
507         bool
508 BSP_CSGMesh::
509 SC_Face(
510         BSP_FaceInd f
511 ){
512
513
514
515 #if 0
516         {
517         // check area is greater than zero.
518
519                 vector<BSP_MVertex> & verts = VertexSet();
520
521                 vector<BSP_VertexInd> f_verts;
522                 FaceVertices(f,f_verts);
523
524                 MT_assert(f_verts.size() >= 3);
525
526                 BSP_VertexInd root = f_verts[0];
527                 
528                 MT_Scalar area = 0;
529
530                 for (int i=2; i < f_verts.size(); i++) {
531                         MT_Vector3 a = verts[root].m_pos;
532                         MT_Vector3 b = verts[f_verts[i-1]].m_pos;
533                         MT_Vector3 c = verts[f_verts[i]].m_pos;
534
535                         MT_Vector3 l1 = b-a;
536                         MT_Vector3 l2 = c-b;
537
538                         area += (l1.cross(l2)).length()/2;
539                 }
540
541                 MT_assert(!MT_fuzzyZero(area));
542         }
543 #endif
544         // Check coplanarity 
545 #if 0
546         MT_Plane3 plane = FacePlane(f);
547
548         const BSP_MFace & face = FaceSet()[f];
549         vector<BSP_VertexInd>::const_iterator f_verts_it = face.m_verts.begin();
550         vector<BSP_VertexInd>::const_iterator f_verts_end = face.m_verts.end();
551
552         for (;f_verts_it != f_verts_end; ++f_verts_it) {
553                 MT_Scalar dist = plane.signedDistance(
554                         VertexSet()[*f_verts_it].m_pos
555                 );
556
557                 MT_assert(fabs(dist) < BSP_SPLIT_EPSILON);
558         }
559 #endif
560
561
562         // Check connectivity
563
564         vector<BSP_EdgeInd> f_edges;    
565         FaceEdges(f,f_edges);
566
567         MT_assert(f_edges.size() == FaceSet()[f].m_verts.size());
568
569         unsigned int i;
570         for (i = 0; i < f_edges.size(); ++i) {
571
572                 int matches = 0;
573                 for (unsigned int j = 0; j < EdgeSet()[f_edges[i]].m_faces.size(); j++) {
574
575                         if (EdgeSet()[f_edges[i]].m_faces[j] == f) matches++;
576                 }
577
578                 MT_assert(matches == 1);
579
580         }       
581         return true;
582 }       
583
584         MT_Plane3
585 BSP_CSGMesh::
586 FacePlane(
587         const BSP_FaceInd & fi
588 ) const{
589
590         const BSP_MFace & f0 = FaceSet()[fi];   
591
592         // Have to be a bit careful here coz the poly may have 
593         // a lot of parallel edges. Should walk round the polygon
594         // and check length of cross product.
595
596         const MT_Vector3 & p1 = VertexSet()[f0.m_verts[0]].m_pos;
597         const MT_Vector3 & p2 = VertexSet()[f0.m_verts[1]].m_pos;
598
599         int face_size = f0.m_verts.size();
600         MT_Vector3 n;
601
602         for (int i = 2 ; i <face_size; i++) { 
603                 const MT_Vector3 & pi =  VertexSet()[f0.m_verts[i]].m_pos;
604                 
605                 MT_Vector3 l1 = p2-p1;
606                 MT_Vector3 l2 = pi-p2;
607                 n = l1.cross(l2);
608                 MT_Scalar length = n.length();
609
610                 if (!MT_fuzzyZero(length)) {
611                         n = n * (1/length);
612                         break;
613                 } 
614         }
615         return MT_Plane3(n,p1);
616 }
617
618         void
619 BSP_CSGMesh::
620 ComputeFacePlanes(
621 ){
622
623         int fsize = FaceSet().size();
624         int i=0;
625         for (i = 0; i < fsize; i++) {
626         
627                 FaceSet()[i].m_plane = FacePlane(i);
628         }
629 };
630
631
632         int
633 BSP_CSGMesh::
634 CountTriangles(
635 ) const {
636
637         // Each polygon of n sides can be partitioned into n-3 triangles.
638         // So we just go through and sum this function of polygon size.
639         
640         vector<BSP_MFace> & face_set = FaceSet();
641
642         vector<BSP_MFace>::const_iterator face_it = face_set.begin();
643         vector<BSP_MFace>::const_iterator face_end = face_set.end();
644
645         int sum = 0;
646
647         for (;face_it != face_end; face_it++) {
648         
649                 // Should be careful about degenerate faces here.
650                 sum += face_it->m_verts.size() - 2;
651         }
652
653         return sum;
654 }
655