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