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