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