Code/Sandbox/Plugins/LodGeneratorPlugin/Util/TopologyBuilder.cpp

   1 #include "StdAfx.h"
   2 #include "TopologyBuilder.h"
   3
   4 namespace LODGenerator
   5 {
   6         struct FacetKey
   7         {
   8                 FacetKey(CVertex* a1, CVertex* a2, CVertex* a3)
   9                 {
  10                         v1 = a1; v2 = a2; v3 = a3;
  11                 }
  12                 bool operator<(const FacetKey& rhs) const
  13                 {
  14                         if(v1 < rhs.v1) { return true; }
  15                         if(v1 > rhs.v1) { return false; }
  16                         if(v2 < rhs.v2) { return true; }
  17                         if(v2 > rhs.v2) { return false; }
  18                         return (v3 < rhs.v3);
  19                 }
  20                 CVertex* v1;
  21                 CVertex* v2;
  22                 CVertex* v3;
  23         };
  24
  25         static std::set<FacetKey>* all_facet_keys;
  26         void CTopologyBuilder::begin_surface()
  27         {
  28                 transition(eS_Initial, eS_Surface);
  29
  30                 nb_non_manifold_v_ = 0;
  31                 nb_duplicate_e_    = 0;
  32                 nb_isolated_v_     = 0;
  33                 all_facet_keys = new std::set<FacetKey>;
  34         }
  35
  36         void CTopologyBuilder::clear()
  37         {
  38                 vertex_.clear();
  39                 tex_vertex_.clear();
  40         }
  41
  42         void CTopologyBuilder::end_surface(bool remove)
  43         {
  44                 delete all_facet_keys; all_facet_keys = NULL;
  45                 transition(eS_Surface, eS_Final);
  46                 terminate_surface();
  47                 if(remove)
  48                 {
  49                         vertex_.clear();
  50                         tex_vertex_.clear();
  51                 }
  52
  53                 if(!quiet_ && (nb_non_manifold_v_ != 0))
  54                 {
  55                         CryLog("MapBuilder Encountered non-manifold vertices (fixed)");
  56                 }
  57                 if(!quiet_ && (nb_duplicate_e_ != 0))
  58                 {
  59                         CryLog("MapBuilder Encountered duplicated edges (fixed)");
  60                 }
  61                 if(!quiet_ && (nb_isolated_v_ != 0))
  62                 {
  63                         CryLog("MapBuilder Encountered isolated vertices (removed)");
  64                 }
  65         }
  66
  67         void CTopologyBuilder::reset()
  68         {
  69                 transition(eS_Final, eS_Initial);
  70         }
  71
  72         void CTopologyBuilder::add_vertex(unsigned int id, const Vec3d& p)
  73         {
  74                 transition(eS_Surface, eS_Surface);
  75                 add_vertex_internal(id, p);
  76         }
  77
  78         void CTopologyBuilder::add_vertex(const Vec3d& p)
  79         {
  80                 transition(eS_Surface, eS_Surface);
  81                 add_vertex_internal(p);
  82         }
  83
  84         void CTopologyBuilder::add_tex_vertex(const Vec2d& p)
  85         {
  86                 add_tex_vertex(tex_vertex_.size(), p);
  87         }
  88
  89         void CTopologyBuilder::add_tex_vertex(unsigned int id, const Vec2d& p)
  90         {
  91                 transition(eS_Surface, eS_Surface);
  92                 std::shared_ptr<CTexVertex>& new_tv = std::shared_ptr<CTexVertex>(target_->new_tex_vertex());
  93                 new_tv-> set_tex_coord(p);
  94                 while(tex_vertex_.size() <= id) {
  95                         tex_vertex_.push_back(NULL);
  96                 }
  97                 tex_vertex_[id] = new_tv;
  98         }
  99
 100         void CTopologyBuilder::add_vertex_internal(unsigned int id, const Vec3d& p)
 101         {
 102                 CVertex* new_v = target_->new_vertex();
 103                 new_v-> set_point(p);
 104                 while(vertex_.size() <= id) {
 105                         vertex_.push_back(NULL);
 106                 }
 107                 vertex_[id] = new_v;
 108         }
 109
 110
 111         void CTopologyBuilder::add_vertex_internal(const Vec3d& p)
 112         {
 113                 add_vertex_internal(vertex_.size(), p);
 114         }
 115
 116         void CTopologyBuilder::begin_facet() {
 117                 facet_vertex_.clear();
 118                 facet_tex_vertex_.clear();
 119         }
 120
 121         void CTopologyBuilder::end_facet()
 122         {
 123                 assert(facet_vertex_.size() == facet_tex_vertex_.size());
 124                 int nb_vertices = facet_vertex_.size();
 125
 126                 if(nb_vertices < 3)
 127                 {
 128                         if(!quiet_)
 129                         {
 130                                 CryLog("MapBuilder Facet with less than 3 vertices");
 131                         }
 132                         return;
 133                 }
 134
 135                 if(false && nb_vertices == 3)
 136                 {
 137                         std::vector<CVertex*> W = facet_vertex_;
 138                         std::sort(W.begin(), W.end());
 139                         FacetKey k(W[0], W[1],W[2]);
 140                         if(all_facet_keys->find(k) != all_facet_keys->end())
 141                         {
 142                                 //std::cerr << '.' << std::flush;
 143                                 return;
 144                         }
 145                         all_facet_keys->insert(k);
 146                 }
 147
 148
 149                 // Detect duplicated vertices
 150                 for(int i=0; i<nb_vertices; i++)
 151                 {
 152                         for(int j=i+1; j<nb_vertices; j++)
 153                         {
 154                                 if(facet_vertex_[i] == facet_vertex_[j])
 155                                 {
 156                                         if(!quiet_)
 157                                         {
 158                                                 CryLog("MapBuilder Duplicated vertex in facet, ignoring facet");
 159                                         }
 160                                         return;
 161                                 }
 162                         }
 163                 }
 164
 165                 // Detect and remove non-manifold edges by duplicating
 166                 //   the corresponding vertices.
 167                 for(int from=0; from<nb_vertices; from++)
 168                 {
 169                         int to=((from+1) % nb_vertices);
 170                         if(find_halfedge_between(facet_vertex_[from], facet_vertex_[to]) != NULL )
 171                         {
 172                                 nb_duplicate_e_++;
 173                                 facet_vertex_[from] = copy_vertex(facet_vertex_[from]);
 174                                 facet_vertex_[to] = copy_vertex(facet_vertex_[to]);
 175                         }
 176                 }
 177
 178
 179                 begin_facet_internal();
 180                 for(int i=0; i<nb_vertices; i++)
 181                 {
 182                         add_vertex_to_facet_internal(facet_vertex_[i]);
 183                         if(facet_tex_vertex_[i] != NULL)
 184                         {
 185                                 set_corner_tex_vertex_internal(facet_tex_vertex_[i]);
 186                         }
 187                 }
 188                 end_facet_internal();
 189         }
 190
 191
 192         CVertex* CTopologyBuilder::copy_vertex(CVertex* from)
 193         {
 194                 // Note: tex coords are not copied, since
 195                 //  an halfedge does not exist in the copy to
 196                 //  store the texvertex pointer.
 197
 198                 CVertex* result = target_->new_vertex();
 199                 result->set_point(from->point());
 200                 if(is_locked_[from])
 201                 {
 202                         is_locked_[result] = true;
 203                 }
 204                 return result;
 205         }
 206
 207         void CTopologyBuilder::add_vertex_to_facet(int i)
 208         {
 209                 if(i < 0 || i >= int(vertex_.size()))
 210                 {
 211                         if(!quiet_)
 212                         {
 213                                 CryLog("MapBuilder vertex index %d out of range",i);
 214                         }
 215                         return;
 216                 }
 217                 facet_vertex_.push_back(vertex_[i]);
 218                 facet_tex_vertex_.push_back(NULL);
 219         }
 220
 221         void CTopologyBuilder::set_corner_tex_vertex(int i)
 222         {
 223                 if(i < 0 || i >= int(tex_vertex_.size()))
 224                 {
 225                         if(!quiet_) {
 226                                 //                CryLog("MapBuilder") << "texvertex index "
 227                                 //                                          << i << " out of range"
 228                                 //                                          << std::endl;
 229                         }
 230                         return;
 231                 }
 232                 *(facet_tex_vertex_.rbegin()) = tex_vertex_[i];
 233         }
 234
 235         void CTopologyBuilder::lock_vertex(int i)
 236         {
 237                 if(i < 0 || i >= int(vertex_.size()))
 238                 {
 239                         if(!quiet_)
 240                         {
 241                                 CryLog("MapBuilder vertex index %d out of range",i);
 242                         }
 243                         return;
 244                 }
 245                 is_locked_[vertex(i)] = true;
 246         }
 247
 248         void CTopologyBuilder::unlock_vertex(int i)
 249         {
 250                 if(i < 0 || i >= int(vertex_.size()))
 251                 {
 252                         if(!quiet_)
 253                         {
 254                                 CryLog("MapBuilder vertex index %d out of range",i);
 255                         }
 256                         return;
 257                 }
 258                 is_locked_[vertex(i)] = false;
 259         }
 260
 261         void CTopologyBuilder::begin_facet_internal()
 262         {
 263                 transition(eS_Surface, eS_Facet);
 264                 current_facet_ = target_->new_facet();
 265                 first_vertex_in_facet_ = NULL;
 266                 current_vertex_ = NULL;
 267                 first_halfedge_in_facet_ = NULL;
 268                 current_halfedge_ = NULL;
 269                 first_tex_vertex_in_facet_ = NULL;
 270         }
 271
 272         void CTopologyBuilder::end_facet_internal()
 273         {
 274                 transition(eS_Facet, eS_Surface);
 275                 CHalfedge* h = new_halfedge_between(current_vertex_, first_vertex_in_facet_);
 276
 277                 CTopologyGraphMutator::link(current_halfedge_, h, 1);
 278                 CTopologyGraphMutator::link(h, first_halfedge_in_facet_, 1);
 279                 if(first_tex_vertex_in_facet_ != NULL)
 280                 {
 281                         CTopologyGraphMutator::set_halfedge_tex_vertex(h, std::shared_ptr<CTexVertex>(first_tex_vertex_in_facet_));
 282                 }
 283         }
 284
 285         void CTopologyBuilder::add_vertex_to_facet_internal(CVertex* v)
 286         {
 287                 transition(eS_Facet, eS_Facet);
 288
 289                 if(first_vertex_in_facet_ == NULL)
 290                 {
 291                         first_vertex_in_facet_ = v;
 292                 }
 293                 else
 294                 {
 295                         CHalfedge* new_halfedge = new_halfedge_between(current_vertex_, v);
 296
 297                         if(first_halfedge_in_facet_ == NULL)
 298                         {
 299                                 first_halfedge_in_facet_ = new_halfedge;
 300                                 CTopologyGraphMutator::make_facet_key(first_halfedge_in_facet_);
 301                         }
 302                         else
 303                         {
 304                                 CTopologyGraphMutator::link(current_halfedge_, new_halfedge, 1);
 305                         }
 306                         current_halfedge_ = new_halfedge;
 307                 }
 308                 current_vertex_ = v;
 309         }
 310
 311         void CTopologyBuilder::set_corner_tex_vertex_internal(std::shared_ptr<CTexVertex>& tv)
 312         {
 313                 transition(eS_Facet, eS_Facet);
 314                 if(current_halfedge_ == NULL)
 315                 {
 316                         first_tex_vertex_in_facet_ = tv;
 317                 }
 318                 else
 319                 {
 320                         CTopologyGraphMutator::set_halfedge_tex_vertex(current_halfedge_, tv);
 321                 }
 322         }
 323
 324
 325         CVertex* CTopologyBuilder::current_vertex()
 326         {
 327                 return vertex_[vertex_.size() - 1];
 328         }
 329
 330         CVertex* CTopologyBuilder::vertex(int i)
 331         {
 332                 return vertex_[i];
 333         }
 334
 335         std::shared_ptr<CTexVertex>& CTopologyBuilder::current_tex_vertex()
 336         {
 337                 return tex_vertex_[tex_vertex_.size() - 1];
 338         }
 339
 340         std::shared_ptr<CTexVertex>& CTopologyBuilder::tex_vertex(int i)
 341         {
 342                 return tex_vertex_[i];
 343         }
 344
 345         CFacet* CTopologyBuilder::current_facet()
 346         {
 347                 return current_facet_;
 348         }
 349
 350         CHalfedge* CTopologyBuilder::new_halfedge_between(CVertex* from, CVertex* to)
 351         {
 352                 assert(from != to);
 353
 354                 // Non-manifold edges have been removed
 355                 // by the higher level public functions.
 356                 // Let us do a sanity check anyway ...
 357                 assert(find_halfedge_between(from, to) == NULL);
 358
 359                 CHalfedge* result = target_->new_halfedge();
 360                 CTopologyGraphMutator::set_halfedge_facet(result, current_facet_);
 361                 CTopologyGraphMutator::set_halfedge_vertex(result, to);
 362
 363                 CHalfedge* opposite = find_halfedge_between(to, from);
 364                 if(opposite != NULL) {
 365                         CTopologyGraphMutator::link(result, opposite, 2);
 366                 }
 367
 368                 star_[from].push_back(result);
 369                 CTopologyGraphMutator::set_vertex_halfedge(to, result);
 370
 371                 return result;
 372         }
 373
 374         CHalfedge* CTopologyBuilder::find_halfedge_between(CVertex* from, CVertex* to)
 375         {
 376                 Star& star = star_[from];
 377                 for(Star::iterator it = star.begin(); it != star.end(); it++)
 378                 {
 379                         CHalfedge* cur = *it;
 380                         if(cur-> vertex() == to)
 381                                 return cur;
 382                 }
 383                 return NULL;
 384         }
 385
 386         bool CTopologyBuilder::vertex_is_manifold(CVertex* v)
 387         {
 388                 if(v->halfedge() == NULL)
 389                 {
 390                         // Isolated vertex, removed in subsequent steps
 391                         return true;
 392                 }
 393
 394                 // A vertex is manifold if the stored and the
 395                 // computed stars match (the number of halfedges
 396                 // are tested).
 397                 // Note: this test is valid only if the borders
 398                 // have been constructed.
 399
 400                 return (int(star_[v].size()) == v->degree());
 401         }
 402
 403         bool CTopologyBuilder::split_non_manifold_vertex(CVertex* v)
 404         {
 405                 if(vertex_is_manifold(v))
 406                 {
 407                         return false;
 408                 }
 409
 410                 std::set<CHalfedge*> star;
 411                 for(unsigned int i=0; i<star_[v].size(); i++)
 412                 {
 413                         star.insert(star_[v][i]);
 414                 }
 415
 416                 // For the first wedge, reuse the vertex
 417                 disconnect_vertex(v->halfedge()->opposite(), v, star);
 418
 419                 // There should be other wedges (else the vertex
 420                 // would have been manifold)
 421                 assert(!star.empty());
 422
 423                 {
 424                         is_locked[v] = true;
 425                         // Create the vertices for the remaining wedges.
 426                         while(!star.empty())
 427                         {
 428                                 CVertex* new_v = copy_vertex(v);
 429                                 is_locked[new_v] = true;
 430                                 CHalfedge* h = *(star.begin());
 431                                 disconnect_vertex(h, new_v, star);
 432                         }
 433                 }
 434
 435                 return true;
 436         }
 437
 438
 439         void CTopologyBuilder::disconnect_vertex(CHalfedge* start_in, CVertex* v, std::set<CHalfedge*>& star)
 440         {
 441                 CHalfedge* start = start_in;
 442
 443                 star_[v].clear();
 444
 445                 //   Important note: in this class, all the Stars correspond to the
 446                 // set of halfedges radiating FROM a vertex (i.e. h->vertex() != v
 447                 // if h belongs to Star(v) ).
 448
 449                 assert(star.find(start) != star.end());
 450
 451
 452                 //   Note: the following code needs a special handling
 453                 // of borders, since borders are not correctly connected
 454                 // in a non-manifold vertex (the standard next_around_vertex
 455                 // iteration does not traverse the whole star)
 456
 457                 while(!start->is_border())
 458                 {
 459                         start = start->prev()->opposite();
 460                         if(start == start_in)
 461                                 break;
 462                 }
 463                 CTopologyGraphMutator::set_vertex_halfedge(v,start->opposite());
 464
 465                 CHalfedge* cur = start;
 466                 CTopologyGraphMutator::set_halfedge_vertex(cur->opposite(), v);
 467                 star_[v].push_back(cur);
 468                 std::set<CHalfedge*>::iterator it = star.find(cur);
 469                 assert(it != star.end());
 470                 star.erase(it);
 471
 472                 while(!cur->opposite()->is_border())
 473                 {
 474                         cur = cur->opposite()->next();
 475                         if(cur == start)
 476                                 break;
 477                         CTopologyGraphMutator::set_halfedge_vertex(cur->opposite(), v);
 478                         std::set<CHalfedge*>::iterator it = star.find(cur);
 479                         assert(it != star.end());
 480                         star.erase(it);
 481                         star_[v].push_back(cur);
 482                 }
 483
 484                 if(start->is_border())
 485                 {
 486                         CTopologyGraphMutator::link(cur->opposite(),start,1);
 487                 }
 488         }
 489
 490
 491         void CTopologyBuilder::terminate_surface()
 492         {
 493
 494                 // Step 1 : create the border halfedges, and setup the 'opposite'
 495                 //   and 'vertex' pointers.
 496                 std::vector<CHalfedge*> halfedgelist;
 497                 FOR_EACH_HALFEDGE(CTopologyGraph, target_, it)
 498                 {
 499                         halfedgelist.push_back(*it);
 500                 }
 501                 for (std::vector<CHalfedge*>::iterator it = halfedgelist.begin();it!= halfedgelist.end();it++)
 502                 {
 503                         if((*it)-> opposite() == NULL)
 504                         {
 505                                 CHalfedge* h = target_->new_halfedge();
 506                                 CTopologyGraphMutator::link(h, *it, 2);
 507                                 CTopologyGraphMutator::set_halfedge_vertex(h, (*it)-> prev()-> vertex());
 508
 509                                 // Initialize texture coordinates
 510                                 CTopologyGraphMutator::set_halfedge_tex_vertex(h, (*it)-> prev()-> tex_vertex());
 511
 512                                 // Used later to fix non-manifold vertices.
 513                                 star_[ (*it)-> vertex() ].push_back(h);
 514                         }
 515                 }
 516
 517                 // Step 2 : setup the 'next' and 'prev' pointers of the border.
 518                 //
 519                 FOR_EACH_HALFEDGE(CTopologyGraph, target_, it)
 520                 {
 521                         if((*it)-> facet() == NULL)
 522                         {
 523
 524                                 CHalfedge* next = (*it)-> opposite();
 525                                 while(next-> facet() != NULL)
 526                                 {
 527                                         next = next-> prev()-> opposite();
 528                                 }
 529                                 CTopologyGraphMutator::set_halfedge_next(*it, next);
 530
 531                                 CHalfedge* prev = (*it)-> opposite();
 532                                 while(prev-> facet() != NULL)
 533                                 {
 534                                         prev = prev-> next()-> opposite();
 535                                 }
 536                                 CTopologyGraphMutator::set_halfedge_prev(*it, prev);
 537                         }
 538                 }
 539
 540                 // Step 3 : fix non-manifold vertices
 541
 542                 for(unsigned int i=0; i<vertex_.size(); i++)
 543                 {
 544                         if(vertex_[i] == NULL) {
 545                                 continue;
 546                         }
 547                         if(split_non_manifold_vertex(vertex_[i]))
 548                         {
 549                                 nb_non_manifold_v_++;
 550                         }
 551                 }
 552
 553
 554                 // Step 4 : create TexVertices
 555
 556                 FOR_EACH_HALFEDGE(CTopologyGraph, target_, it)
 557                 {
 558                         if((*it)->tex_vertex() == NULL)
 559                         {
 560                                 std::shared_ptr<CTexVertex>& new_tv = std::shared_ptr<CTexVertex>(target_->new_tex_vertex());
 561                                 CHalfedge* cur = *it;
 562                                 do
 563                                 {
 564                                         CTopologyGraphMutator::set_halfedge_tex_vertex(cur, new_tv);
 565                                         cur = cur-> next()-> opposite();
 566                                 }
 567                                 while(cur-> tex_vertex() == NULL);
 568                                 cur = (*it)-> opposite()-> prev();
 569                                 while((*it)-> tex_vertex() == NULL)
 570                                 {
 571                                         CTopologyGraphMutator::set_halfedge_tex_vertex(cur, new_tv);
 572                                         cur = cur-> opposite()-> prev();
 573                                 }
 574                         }
 575                 }
 576
 577                 // Step 5 : check for isolated vertices
 578                 for(unsigned int i=0; i<vertex_.size(); i++)
 579                 {
 580                         if(vertex_[i] == NULL)
 581                         {
 582                                 continue;
 583                         }
 584                         if(star_[vertex_[i]].size() == 0)
 585                         {
 586                                 nb_isolated_v_++;
 587                                 target_->delete_vertex(vertex_[i]);
 588                         }
 589                 }
 590
 591                 target_->assert_is_valid();
 592         }
 593
 594         void CTopologyBuilder::transition(EState from, EState to)
 595         {
 596                 check_state(from);
 597                 state_ = to;
 598         }
 599
 600         void CTopologyBuilder::check_state(EState s)
 601         {
 602                 if(state_ != s)
 603                 {
 604                         CryLog("MapBuilder invalid state: '%s' , expected '%s'",state_to_string(state_),state_to_string(s));
 605                         bool ok = false;
 606                         assert(ok);
 607                 }
 608         }
 609
 610         std::string CTopologyBuilder::state_to_string(EState s)
 611         {
 612                 switch(s)
 613                 {
 614                 case eS_Initial:
 615                         return "initial";
 616                 case eS_Surface:
 617                         return "surface";
 618                 case eS_Facet:
 619                         return "facet";
 620                 case eS_Final:
 621                         return "final";
 622                 default:
 623                         return "unknown";
 624                 }
 625                 return "unknown";
 626         }
 627
 628         void CTopologyBuilder::set_vertex(unsigned int v, const Vec3d& p)
 629         {
 630                 vertex(v)->set_point(p);
 631         }
 632
 633
 634         void CTopologyBuilder::create_vertices(unsigned int nb_v, bool with_colors)
 635         {
 636                 for(unsigned int i=0; i<nb_v; i++)
 637                 {
 638                         add_vertex(Vec3d(0.0, 0.0, 0.0)) ;
 639                 }
 640         }
 641 }
 642