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