ArrayKernel.hh 30.7 KB
Newer Older
Jan Möbius's avatar
Jan Möbius committed
1
/* ========================================================================= *
2 3
 *                                                                           *
 *                               OpenMesh                                    *
Jan Möbius's avatar
Jan Möbius committed
4
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
Jan Möbius's avatar
Typo  
Jan Möbius committed
5
 *           Department of Computer Graphics and Multimedia                  *
Jan Möbius's avatar
Jan Möbius committed
6 7
 *                          All rights reserved.                             *
 *                            www.openmesh.org                               *
8
 *                                                                           *
9
 *---------------------------------------------------------------------------*
Jan Möbius's avatar
Jan Möbius committed
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
 * This file is part of OpenMesh.                                            *
 *---------------------------------------------------------------------------*
 *                                                                           *
 * Redistribution and use in source and binary forms, with or without        *
 * modification, are permitted provided that the following conditions        *
 * are met:                                                                  *
 *                                                                           *
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
 *                                                                           *
 * 2. Redistributions in binary form must reproduce the above copyright      *
 *    notice, this list of conditions and the following disclaimer in the    *
 *    documentation and/or other materials provided with the distribution.   *
 *                                                                           *
 * 3. Neither the name of the copyright holder nor the names of its          *
 *    contributors may be used to endorse or promote products derived from   *
 *    this software without specific prior written permission.               *
 *                                                                           *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
Jan Möbius's avatar
Jan Möbius committed
39 40
 *                                                                           *
 * ========================================================================= */
41

42

Jan Möbius's avatar
Jan Möbius committed
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86


//=============================================================================
//
//  CLASS ArrayKernel
//
//=============================================================================


#ifndef OPENMESH_ARRAY_KERNEL_HH
#define OPENMESH_ARRAY_KERNEL_HH


//== INCLUDES =================================================================
#include <vector>

#include <OpenMesh/Core/System/config.h>
#include <OpenMesh/Core/Utils/GenProg.hh>

#include <OpenMesh/Core/Mesh/ArrayItems.hh>
#include <OpenMesh/Core/Mesh/BaseKernel.hh>
#include <OpenMesh/Core/Mesh/Status.hh>

//== NAMESPACES ===============================================================
namespace OpenMesh {


//== CLASS DEFINITION =========================================================
/** \ingroup mesh_kernels_group

    Mesh kernel using arrays for mesh item storage.

    This mesh kernel uses the std::vector as container to store the
    mesh items. Therefore all handle types are internally represented
    by integers. To get the index from a handle use the handle's \c
    idx() method.

    \note For a description of the minimal kernel interface see
    OpenMesh::Mesh::BaseKernel.
    \note You do not have to use this class directly, use the predefined
    mesh-kernel combinations in \ref mesh_types_group.
    \see OpenMesh::Concepts::KernelT, \ref mesh_type
*/

Mike Kremer's avatar
Mike Kremer committed
87
class OPENMESHDLLEXPORT ArrayKernel : public BaseKernel, public ArrayItems
Jan Möbius's avatar
Jan Möbius committed
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
{
public:

  // handles
  typedef OpenMesh::VertexHandle            VertexHandle;
  typedef OpenMesh::HalfedgeHandle          HalfedgeHandle;
  typedef OpenMesh::EdgeHandle              EdgeHandle;
  typedef OpenMesh::FaceHandle              FaceHandle;
  typedef Attributes::StatusInfo            StatusInfo;
  typedef VPropHandleT<StatusInfo>          VertexStatusPropertyHandle;
  typedef HPropHandleT<StatusInfo>          HalfedgeStatusPropertyHandle;
  typedef EPropHandleT<StatusInfo>          EdgeStatusPropertyHandle;
  typedef FPropHandleT<StatusInfo>          FaceStatusPropertyHandle;

public:

  // --- constructor/destructor ---
  ArrayKernel();
  virtual ~ArrayKernel();

108
  /** ArrayKernel uses the default copy constructor and assignment operator, which means
Jan Möbius's avatar
Jan Möbius committed
109
      that the connectivity and all properties are copied, including reference
110
      counters, allocated bit status masks, etc.. In contrast assign_connectivity
Jan Möbius's avatar
Jan Möbius committed
111
      copies only the connectivity, i.e. vertices, edges, faces and their status fields.
112
      NOTE: The geometry (the points property) is NOT copied. Poly/TriConnectivity
Jan Möbius's avatar
Jan Möbius committed
113
      override(and hide) that function to provide connectivity consistence.*/
114
  void assign_connectivity(const ArrayKernel& _other);
115

Jan Möbius's avatar
Jan Möbius committed
116
  // --- handle -> item ---
117 118 119 120 121 122 123
  VertexHandle handle(const Vertex& _v) const;

  HalfedgeHandle handle(const Halfedge& _he) const;

  EdgeHandle handle(const Edge& _e) const;

  FaceHandle handle(const Face& _f) const;
Jan Möbius's avatar
Jan Möbius committed
124 125


126 127
  ///checks handle validity - useful for debugging
  bool is_valid_handle(VertexHandle _vh) const;
Jan Möbius's avatar
Jan Möbius committed
128

129 130 131 132 133 134 135 136
  ///checks handle validity - useful for debugging
  bool is_valid_handle(HalfedgeHandle _heh) const;

  ///checks handle validity - useful for debugging
  bool is_valid_handle(EdgeHandle _eh) const;

  ///checks handle validity - useful for debugging
  bool is_valid_handle(FaceHandle _fh) const;
Jan Möbius's avatar
Jan Möbius committed
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189


  // --- item -> handle ---
  const Vertex& vertex(VertexHandle _vh) const
  {
    assert(is_valid_handle(_vh));
    return vertices_[_vh.idx()];
  }

  Vertex& vertex(VertexHandle _vh)
  {
    assert(is_valid_handle(_vh));
    return vertices_[_vh.idx()];
  }

  const Halfedge& halfedge(HalfedgeHandle _heh) const
  {
    assert(is_valid_handle(_heh));
    return edges_[_heh.idx() >> 1].halfedges_[_heh.idx() & 1];
  }

  Halfedge& halfedge(HalfedgeHandle _heh)
  {
    assert(is_valid_handle(_heh));
    return edges_[_heh.idx() >> 1].halfedges_[_heh.idx() & 1];
  }

  const Edge& edge(EdgeHandle _eh) const
  {
    assert(is_valid_handle(_eh));
    return edges_[_eh.idx()];
  }

  Edge& edge(EdgeHandle _eh)
  {
    assert(is_valid_handle(_eh));
    return edges_[_eh.idx()];
  }

  const Face& face(FaceHandle _fh) const
  {
    assert(is_valid_handle(_fh));
    return faces_[_fh.idx()];
  }

  Face& face(FaceHandle _fh)
  {
    assert(is_valid_handle(_fh));
    return faces_[_fh.idx()];
  }

  // --- get i'th items ---

190
  VertexHandle vertex_handle(unsigned int _i) const
Jan Möbius's avatar
Jan Möbius committed
191 192
  { return (_i < n_vertices()) ? handle( vertices_[_i] ) : VertexHandle(); }

193
  HalfedgeHandle halfedge_handle(unsigned int _i) const
Jan Möbius's avatar
Jan Möbius committed
194 195 196 197 198
  {
    return (_i < n_halfedges()) ?
      halfedge_handle(edge_handle(_i/2), _i%2) : HalfedgeHandle();
  }

199
  EdgeHandle edge_handle(unsigned int _i) const
Jan Möbius's avatar
Jan Möbius committed
200 201
  { return (_i < n_edges()) ? handle(edges_[_i]) : EdgeHandle(); }

202
  FaceHandle face_handle(unsigned int _i) const
Jan Möbius's avatar
Jan Möbius committed
203 204 205 206
  { return (_i < n_faces()) ? handle(faces_[_i]) : FaceHandle(); }

public:

207 208 209 210 211 212 213 214 215
  /**
   * \brief Add a new vertex.
   *
   * If you are rebuilding a mesh that you previously erased using clean() or
   * clean_keep_reservation() you probably want to use new_vertex_dirty()
   * instead.
   *
   * \sa new_vertex_dirty()
   */
Jan Möbius's avatar
Jan Möbius committed
216 217 218 219 220 221 222 223
  inline VertexHandle new_vertex()
  {
    vertices_.push_back(Vertex());
    vprops_resize(n_vertices());//TODO:should it be push_back()?

    return handle(vertices_.back());
  }

224 225 226 227 228 229 230 231 232 233
  /**
   * Same as new_vertex() but uses PropertyContainer::resize_if_smaller() to
   * resize the vertex property container.
   *
   * If you are rebuilding a mesh that you erased with clean() or
   * clean_keep_reservation() using this method instead of new_vertex() saves
   * reallocation and reinitialization of property memory.
   *
   * \sa new_vertex()
   */
234 235 236 237 238 239 240 241
  inline VertexHandle new_vertex_dirty()
  {
    vertices_.push_back(Vertex());
    vprops_resize_if_smaller(n_vertices());//TODO:should it be push_back()?

    return handle(vertices_.back());
  }

Jan Möbius's avatar
Jan Möbius committed
242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
  inline HalfedgeHandle new_edge(VertexHandle _start_vh, VertexHandle _end_vh)
  {
//     assert(_start_vh != _end_vh);
    edges_.push_back(Edge());
    eprops_resize(n_edges());//TODO:should it be push_back()?
    hprops_resize(n_halfedges());//TODO:should it be push_back()?

    EdgeHandle eh(handle(edges_.back()));
    HalfedgeHandle heh0(halfedge_handle(eh, 0));
    HalfedgeHandle heh1(halfedge_handle(eh, 1));
    set_vertex_handle(heh0, _end_vh);
    set_vertex_handle(heh1, _start_vh);
    return heh0;
  }

  inline FaceHandle new_face()
  {
    faces_.push_back(Face());
    fprops_resize(n_faces());
    return handle(faces_.back());
  }

  inline FaceHandle new_face(const Face& _f)
  {
    faces_.push_back(_f);
    fprops_resize(n_faces());
    return handle(faces_.back());
  }

public:
  // --- resize/reserve ---
Jan Möbius's avatar
Jan Möbius committed
273 274
  void resize( size_t _n_vertices, size_t _n_edges, size_t _n_faces );
  void reserve(size_t _n_vertices, size_t _n_edges, size_t _n_faces );
Jan Möbius's avatar
Jan Möbius committed
275 276

  // --- deletion ---
277 278 279 280 281
  /** \brief garbage collection
   *
   * Usually if you delete primitives in OpenMesh, they are only flagged as deleted.
   * Only when you call garbage collection, they will be actually removed.
   *
Jan Möbius's avatar
Jan Möbius committed
282 283 284
   * \note Garbage collection invalidates all handles. If you need to keep track of
   *       a set of handles, you can pass them to the second garbage collection
   *       function, which will update a vector of handles.
285
   *       See also \ref deletedElements.
286 287 288 289
   *
   * @param _v Remove deleted vertices?
   * @param _e Remove deleted edges?
   * @param _f Remove deleted faces?
290
   *
291
   */
Jan Möbius's avatar
Jan Möbius committed
292
  void garbage_collection(bool _v=true, bool _e=true, bool _f=true);
293

Jan Möbius's avatar
Jan Möbius committed
294
  /** \brief garbage collection with handle tracking
295 296 297 298 299
   *
   * Usually if you delete primitives in OpenMesh, they are only flagged as deleted.
   * Only when you call garbage collection, they will be actually removed.
   *
   * \note Garbage collection invalidates all handles. If you need to keep track of
300 301
   *       a set of handles, you can pass them to this function. The handles that the
   *       given pointers point to are updated in place.
302
   *       See also \ref deletedElements.
303
   *
304 305 306
   * @param vh_to_update Pointers to vertex handles that should get updated
   * @param hh_to_update Pointers to halfedge handles that should get updated
   * @param fh_to_update Pointers to face handles that should get updated
307 308 309 310 311 312 313
   * @param _v Remove deleted vertices?
   * @param _e Remove deleted edges?
   * @param _f Remove deleted faces?
   */
  template<typename std_API_Container_VHandlePointer,
           typename std_API_Container_HHandlePointer,
           typename std_API_Container_FHandlePointer>
Jan Möbius's avatar
Jan Möbius committed
314 315 316 317
  void garbage_collection(std_API_Container_VHandlePointer& vh_to_update,
                          std_API_Container_HHandlePointer& hh_to_update,
                          std_API_Container_FHandlePointer& fh_to_update,
                          bool _v=true, bool _e=true, bool _f=true);
318

319
  /// \brief Does the same as clean() and in addition erases all properties.
Jan Möbius's avatar
Jan Möbius committed
320 321
  void clear();

322
  /** \brief Remove all vertices, edges and faces and deallocates their memory.
323
   *
324 325 326 327 328 329
   * In contrast to clear() this method does neither erases the properties
   * nor clears the property vectors. Depending on how you add any new entities
   * to the mesh after calling this method, your properties will be initialized
   * with old values.
   *
   * \sa clean_keep_reservation()
330 331 332
   */
  void clean();

333
  /** \brief Remove all vertices, edges and faces but keep memory allocated.
334
   *
335 336 337 338
   * This method behaves like clean() (also regarding the properties) but
   * leaves the memory used for vertex, edge and face storage allocated. This
   * leads to no reduction in memory consumption but allows for faster
   * performance when rebuilding the mesh.
339 340 341
   */
  void clean_keep_reservation();

Jan Möbius's avatar
Jan Möbius committed
342
  // --- number of items ---
343 344 345 346
  size_t n_vertices()  const { return vertices_.size(); }
  size_t n_halfedges() const { return 2*edges_.size(); }
  size_t n_edges()     const { return edges_.size(); }
  size_t n_faces()     const { return faces_.size(); }
Jan Möbius's avatar
Jan Möbius committed
347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369

  bool vertices_empty()  const { return vertices_.empty(); }
  bool halfedges_empty() const { return edges_.empty(); }
  bool edges_empty()     const { return edges_.empty(); }
  bool faces_empty()     const { return faces_.empty(); }

  // --- vertex connectivity ---

  HalfedgeHandle halfedge_handle(VertexHandle _vh) const
  { return vertex(_vh).halfedge_handle_; }

  void set_halfedge_handle(VertexHandle _vh, HalfedgeHandle _heh)
  {
//     assert(is_valid_handle(_heh));
    vertex(_vh).halfedge_handle_ = _heh;
  }

  bool is_isolated(VertexHandle _vh) const
  { return !halfedge_handle(_vh).is_valid(); }

  void set_isolated(VertexHandle _vh)
  { vertex(_vh).halfedge_handle_.invalidate(); }

370
  unsigned int delete_isolated_vertices();
Jan Möbius's avatar
Jan Möbius committed
371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419

  // --- halfedge connectivity ---
  VertexHandle to_vertex_handle(HalfedgeHandle _heh) const
  { return halfedge(_heh).vertex_handle_; }

  VertexHandle from_vertex_handle(HalfedgeHandle _heh) const
  { return to_vertex_handle(opposite_halfedge_handle(_heh)); }

  void set_vertex_handle(HalfedgeHandle _heh, VertexHandle _vh)
  {
//     assert(is_valid_handle(_vh));
    halfedge(_heh).vertex_handle_ = _vh;
  }

  FaceHandle face_handle(HalfedgeHandle _heh) const
  { return halfedge(_heh).face_handle_; }

  void set_face_handle(HalfedgeHandle _heh, FaceHandle _fh)
  {
//     assert(is_valid_handle(_fh));
    halfedge(_heh).face_handle_ = _fh;
  }

  void set_boundary(HalfedgeHandle _heh)
  { halfedge(_heh).face_handle_.invalidate(); }

  /// Is halfedge _heh a boundary halfedge (is its face handle invalid) ?
  bool is_boundary(HalfedgeHandle _heh) const
  { return !face_handle(_heh).is_valid(); }

  HalfedgeHandle next_halfedge_handle(HalfedgeHandle _heh) const
  { return halfedge(_heh).next_halfedge_handle_; }

  void set_next_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _nheh)
  {
    assert(is_valid_handle(_nheh));
//     assert(to_vertex_handle(_heh) == from_vertex_handle(_nheh));
    halfedge(_heh).next_halfedge_handle_ = _nheh;
    set_prev_halfedge_handle(_nheh, _heh);
  }


  void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh)
  {
    assert(is_valid_handle(_pheh));
    set_prev_halfedge_handle(_heh, _pheh, HasPrevHalfedge());
  }

  void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
420
                                GenProg::TrueType)
Jan Möbius's avatar
Jan Möbius committed
421 422 423
  { halfedge(_heh).prev_halfedge_handle_ = _pheh; }

  void set_prev_halfedge_handle(HalfedgeHandle /* _heh */, HalfedgeHandle /* _pheh */,
424
                                GenProg::FalseType)
Jan Möbius's avatar
Jan Möbius committed
425 426 427 428 429
  {}

  HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh) const
  { return prev_halfedge_handle(_heh, HasPrevHalfedge() ); }

430
  HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh, GenProg::TrueType) const
Jan Möbius's avatar
Jan Möbius committed
431 432
  { return halfedge(_heh).prev_halfedge_handle_; }

433
  HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh, GenProg::FalseType) const
Jan Möbius's avatar
Jan Möbius committed
434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
  {
    if (is_boundary(_heh))
    {//iterating around the vertex should be faster than iterating the boundary
      HalfedgeHandle curr_heh(opposite_halfedge_handle(_heh));
      HalfedgeHandle next_heh(next_halfedge_handle(curr_heh));
      do
      {
        curr_heh = opposite_halfedge_handle(next_heh);
        next_heh = next_halfedge_handle(curr_heh);
      }
      while (next_heh != _heh);
      return curr_heh;
    }
    else
    {
      HalfedgeHandle  heh(_heh);
      HalfedgeHandle  next_heh(next_halfedge_handle(heh));
      while (next_heh != _heh) {
        heh = next_heh;
        next_heh = next_halfedge_handle(next_heh);
      }
      return heh;
    }
  }


  HalfedgeHandle opposite_halfedge_handle(HalfedgeHandle _heh) const
461
  { return HalfedgeHandle(_heh.idx() ^ 1); }
Jan Möbius's avatar
Jan Möbius committed
462 463 464 465 466 467 468 469 470 471


  HalfedgeHandle ccw_rotated_halfedge_handle(HalfedgeHandle _heh) const
  { return opposite_halfedge_handle(prev_halfedge_handle(_heh)); }


  HalfedgeHandle cw_rotated_halfedge_handle(HalfedgeHandle _heh) const
  { return next_halfedge_handle(opposite_halfedge_handle(_heh)); }

  // --- edge connectivity ---
472
  static HalfedgeHandle s_halfedge_handle(EdgeHandle _eh, unsigned int _i)
Jan Möbius's avatar
Jan Möbius committed
473 474 475 476 477
  {
    assert(_i<=1);
    return HalfedgeHandle((_eh.idx() << 1) + _i);
  }

478
  static EdgeHandle s_edge_handle(HalfedgeHandle _heh)
Jan Möbius's avatar
Jan Möbius committed
479 480
  { return EdgeHandle(_heh.idx() >> 1); }

481 482 483 484 485 486 487 488
  HalfedgeHandle halfedge_handle(EdgeHandle _eh, unsigned int _i) const
  {
      return s_halfedge_handle(_eh, _i);
  }

  EdgeHandle edge_handle(HalfedgeHandle _heh) const
  { return s_edge_handle(_heh); }

Jan Möbius's avatar
Jan Möbius committed
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
  // --- face connectivity ---
  HalfedgeHandle halfedge_handle(FaceHandle _fh) const
  { return face(_fh).halfedge_handle_; }

  void set_halfedge_handle(FaceHandle _fh, HalfedgeHandle _heh)
  {
//     assert(is_valid_handle(_heh));
    face(_fh).halfedge_handle_ = _heh;
  }

  /// Status Query API
  //------------------------------------------------------------ vertex status
  const StatusInfo&                         status(VertexHandle _vh) const
  { return property(vertex_status_, _vh); }

  StatusInfo&                               status(VertexHandle _vh)
  { return property(vertex_status_, _vh); }

507 508 509 510
  /**
   * Reinitializes the status of all vertices using the StatusInfo default
   * constructor, i.e. all flags will be set to false.
   */
511 512 513 514 515 516
  void reset_status() {
      PropertyT<StatusInfo> &status_prop = property(vertex_status_);
      PropertyT<StatusInfo>::vector_type &sprop_v = status_prop.data_vector();
      std::fill(sprop_v.begin(), sprop_v.begin() + n_vertices(), StatusInfo());
  }

Jan Möbius's avatar
Jan Möbius committed
517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624
  //----------------------------------------------------------- halfedge status
  const StatusInfo&                         status(HalfedgeHandle _hh) const
  { return property(halfedge_status_, _hh);  }

  StatusInfo&                               status(HalfedgeHandle _hh)
  { return property(halfedge_status_, _hh); }

  //--------------------------------------------------------------- edge status
  const StatusInfo&                         status(EdgeHandle _eh) const
  { return property(edge_status_, _eh); }

  StatusInfo&                               status(EdgeHandle _eh)
  { return property(edge_status_, _eh); }

  //--------------------------------------------------------------- face status
  const StatusInfo&                         status(FaceHandle _fh) const
  { return property(face_status_, _fh); }

  StatusInfo&                               status(FaceHandle _fh)
  { return property(face_status_, _fh); }

  inline bool                               has_vertex_status() const
  { return vertex_status_.is_valid();    }

  inline bool                               has_halfedge_status() const
  { return halfedge_status_.is_valid();  }

  inline bool                               has_edge_status() const
  { return edge_status_.is_valid(); }

  inline bool                               has_face_status() const
  { return face_status_.is_valid(); }

  inline VertexStatusPropertyHandle         vertex_status_pph() const
  { return vertex_status_;  }

  inline HalfedgeStatusPropertyHandle       halfedge_status_pph() const
  { return halfedge_status_; }

  inline EdgeStatusPropertyHandle           edge_status_pph() const
  { return edge_status_;  }

  inline FaceStatusPropertyHandle           face_status_pph() const
  { return face_status_; }

  /// status property by handle
  inline VertexStatusPropertyHandle         status_pph(VertexHandle /*_hnd*/) const
  { return vertex_status_pph(); }

  inline HalfedgeStatusPropertyHandle       status_pph(HalfedgeHandle /*_hnd*/) const
  { return halfedge_status_pph(); }

  inline EdgeStatusPropertyHandle           status_pph(EdgeHandle /*_hnd*/) const
  { return edge_status_pph();  }

  inline FaceStatusPropertyHandle           status_pph(FaceHandle /*_hnd*/) const
  { return face_status_pph();  }

  /// Status Request API
  void request_vertex_status()
  {
    if (!refcount_vstatus_++)
      add_property( vertex_status_, "v:status" );
  }

  void request_halfedge_status()
  {
    if (!refcount_hstatus_++)
      add_property( halfedge_status_, "h:status" );
  }

  void request_edge_status()
  {
    if (!refcount_estatus_++)
      add_property( edge_status_, "e:status" );
  }

  void request_face_status()
  {
    if (!refcount_fstatus_++)
      add_property( face_status_, "f:status" );
  }

  /// Status Release API
  void release_vertex_status()
  {
    if ((refcount_vstatus_ > 0) && (! --refcount_vstatus_))
      remove_property(vertex_status_);
  }

  void release_halfedge_status()
  {
    if ((refcount_hstatus_ > 0) && (! --refcount_hstatus_))
      remove_property(halfedge_status_);
  }

  void release_edge_status()
  {
    if ((refcount_estatus_ > 0) && (! --refcount_estatus_))
      remove_property(edge_status_);
  }

  void release_face_status()
  {
    if ((refcount_fstatus_ > 0) && (! --refcount_fstatus_))
      remove_property(face_status_);
  }

625 626
  /// --- StatusSet API ---

627 628 629 630
  /*! 
  Implements a set of connectivity entities (vertex, edge, face, halfedge) 
  using the available bits in the corresponding mesh status field. 

631
  Status-based sets are much faster than std::set<> and equivalent 
632 633 634
  in performance to std::vector<bool>, but much more convenient. 
  */
  template <class HandleT>
635 636
  class StatusSetT
  {
637 638 639
  public: 
    typedef HandleT Handle;

640
  protected:
641
    ArrayKernel& kernel_;
642 643

  public:
644
    const unsigned int bit_mask_;
645 646

  public:
647
    StatusSetT(ArrayKernel& _kernel, const unsigned int _bit_mask)
648 649 650 651 652 653
    : kernel_(_kernel), bit_mask_(_bit_mask)
    {}

    ~StatusSetT()
    {}

654
    inline bool is_in(Handle _hnd) const
655 656
    { return kernel_.status(_hnd).is_bit_set(bit_mask_); }

657
    inline void insert(Handle _hnd)
658 659
    { kernel_.status(_hnd).set_bit(bit_mask_); }

660
    inline void erase(Handle _hnd)
661 662
    { kernel_.status(_hnd).unset_bit(bit_mask_); }

663 664
    //! Note: 0(n) complexity
    size_t size() const
665
    {
666 667 668 669 670 671
      const int n = kernel_.status_pph(Handle()).is_valid() ?
       (int)kernel_.property(kernel_.status_pph(Handle())).n_elements() : 0;
 
      size_t sz = 0;
      for (int i = 0; i < n; ++i)
        sz += (size_t)is_in(Handle(i));
672 673 674
      return sz;
    }

675 676
    //! Note: O(n) complexity
    void clear()
677
    {
678 679 680 681
      const int n = kernel_.status_pph(Handle()).is_valid() ?
       (int)kernel_.property(kernel_.status_pph(Handle())).n_elements() : 0;

      for (int i = 0; i < n; ++i)
682 683 684 685 686 687 688 689 690
        erase(Handle(i));
    }
  };

  friend class StatusSetT<VertexHandle>;
  friend class StatusSetT<EdgeHandle>;
  friend class StatusSetT<FaceHandle>;
  friend class StatusSetT<HalfedgeHandle>;

691
  //! AutoStatusSetT: A status set that automatically picks a status bit 
692 693
  template <class HandleT>
  class AutoStatusSetT : public StatusSetT<HandleT>
694 695
  {
  private:
696
    typedef HandleT Handle;
Jan Möbius's avatar
Jan Möbius committed
697
    typedef StatusSetT<Handle> Base;
698

699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720
  public:
    AutoStatusSetT(ArrayKernel& _kernel)
    : StatusSetT<Handle>(_kernel, _kernel.pop_bit_mask(Handle()))
    { /*assert(size() == 0);*/ } //the set should be empty on creation

    ~AutoStatusSetT()
    {
      //assert(size() == 0);//the set should be empty on leave?
      Base::kernel_.push_bit_mask(Handle(), Base::bit_mask_);
    }
  };

  friend class AutoStatusSetT<VertexHandle>;
  friend class AutoStatusSetT<EdgeHandle>;
  friend class AutoStatusSetT<FaceHandle>;
  friend class AutoStatusSetT<HalfedgeHandle>;

  typedef AutoStatusSetT<VertexHandle>      VertexStatusSet;
  typedef AutoStatusSetT<EdgeHandle>        EdgeStatusSet;
  typedef AutoStatusSetT<FaceHandle>        FaceStatusSet;
  typedef AutoStatusSetT<HalfedgeHandle>    HalfedgeStatusSet;

721 722 723
  //! ExtStatusSet: A status set augmented with an array
  template <class HandleT>
  class ExtStatusSetT : public AutoStatusSetT<HandleT>
724 725
  {
  public:
726 727
    typedef HandleT Handle;
    typedef AutoStatusSetT<Handle> Base;
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746

  protected:
    typedef std::vector<Handle>             HandleContainer;
    HandleContainer                         handles_;

  public:
    typedef typename HandleContainer::iterator
                                            iterator;
    typedef typename HandleContainer::const_iterator
                                            const_iterator;
  public:
    ExtStatusSetT(ArrayKernel& _kernel, size_t _capacity_hint = 0)
    : Base(_kernel)
    { handles_.reserve(_capacity_hint); }

    ~ExtStatusSetT()
    { clear(); }

    // Complexity: O(1)
747
    inline void insert(Handle _hnd)
748 749 750 751 752 753 754 755
    {
      if (!is_in(_hnd))
      {
        Base::insert(_hnd);
        handles_.push_back(_hnd);
      }
    }

756 757
    //! Complexity: O(k), (k - number of the elements in the set)
    inline void erase(Handle _hnd)
758 759 760 761 762 763 764 765
    {
      if (is_in(_hnd))
      {
        iterator it = std::find(begin(), end(), _hnd);
        erase(it);
      }
    }

766 767
    //! Complexity: O(1)
    inline void erase(iterator _it)
768 769
    {
      assert(_it != end() && is_in(*_it));
770
      Base::erase(*_it);
771 772 773 774
      *_it = handles_.back();
      _it.pop_back();
    }

775
    inline void clear()
776 777 778 779 780 781 782 783 784 785
    {
      for (iterator it = begin(); it != end(); ++it)
      {
        assert(is_in(*it));
        Base::erase(*it);
      }
      handles_.clear();
    }

    /// Complexity: 0(1)
786
    inline unsigned int size() const
787
    { return handles_.size(); }
788
    inline bool empty() const
789 790 791
    { return handles_.empty(); }

    //Vector API
792
    inline iterator begin()
793
    { return handles_.begin(); }
794
    inline const_iterator begin() const
795 796
    { return handles_.begin(); }

797
    inline iterator end()
798
    { return handles_.end(); }
799
    inline const_iterator end() const
800 801
    { return handles_.end(); }

802
    inline Handle& front()
803
    { return handles_.front(); }
804
    inline const Handle& front() const
805 806
    { return handles_.front(); }

807
    inline Handle& back()
808
    { return handles_.back(); }
809
    inline const Handle& back() const
810 811 812 813 814 815 816 817
    { return handles_.back(); }
  };

  typedef ExtStatusSetT<FaceHandle>         ExtFaceStatusSet;
  typedef ExtStatusSetT<VertexHandle>       ExtVertexStatusSet;
  typedef ExtStatusSetT<EdgeHandle>         ExtEdgeStatusSet;
  typedef ExtStatusSetT<HalfedgeHandle>     ExtHalfedgeStatusSet;

Jan Möbius's avatar
Jan Möbius committed
818 819 820 821 822 823 824 825 826 827 828
private:
  // iterators
  typedef std::vector<Vertex>                VertexContainer;
  typedef std::vector<Edge>                  EdgeContainer;
  typedef std::vector<Face>                  FaceContainer;
  typedef VertexContainer::iterator          KernelVertexIter;
  typedef VertexContainer::const_iterator    KernelConstVertexIter;
  typedef EdgeContainer::iterator            KernelEdgeIter;
  typedef EdgeContainer::const_iterator      KernelConstEdgeIter;
  typedef FaceContainer::iterator            KernelFaceIter;
  typedef FaceContainer::const_iterator      KernelConstFaceIter;
829
  typedef std::vector<unsigned int>          BitMaskContainer;
Jan Möbius's avatar
Jan Möbius committed
830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857


  KernelVertexIter      vertices_begin()        { return vertices_.begin(); }
  KernelConstVertexIter vertices_begin() const  { return vertices_.begin(); }
  KernelVertexIter      vertices_end()          { return vertices_.end(); }
  KernelConstVertexIter vertices_end() const    { return vertices_.end(); }

  KernelEdgeIter        edges_begin()           { return edges_.begin(); }
  KernelConstEdgeIter   edges_begin() const     { return edges_.begin(); }
  KernelEdgeIter        edges_end()             { return edges_.end(); }
  KernelConstEdgeIter   edges_end() const       { return edges_.end(); }

  KernelFaceIter        faces_begin()           { return faces_.begin(); }
  KernelConstFaceIter   faces_begin() const     { return faces_.begin(); }
  KernelFaceIter        faces_end()             { return faces_.end(); }
  KernelConstFaceIter   faces_end() const       { return faces_.end(); }

  /// bit mask container by handle
  inline BitMaskContainer&                  bit_masks(VertexHandle /*_dummy_hnd*/)
  { return vertex_bit_masks_; }
  inline BitMaskContainer&                  bit_masks(EdgeHandle /*_dummy_hnd*/)
  { return edge_bit_masks_; }
  inline BitMaskContainer&                  bit_masks(FaceHandle /*_dummy_hnd*/)
  { return face_bit_masks_; }
  inline BitMaskContainer&                  bit_masks(HalfedgeHandle /*_dummy_hnd*/)
  { return halfedge_bit_masks_; }

  template <class Handle>
858
  unsigned int                              pop_bit_mask(Handle _hnd)
Jan Möbius's avatar
Jan Möbius committed
859 860
  {
    assert(!bit_masks(_hnd).empty());//check if the client request too many status sets
861
    unsigned int bit_mask = bit_masks(_hnd).back();
Jan Möbius's avatar
Jan Möbius committed
862 863 864 865 866
    bit_masks(_hnd).pop_back();
    return bit_mask;
  }

  template <class Handle>
867
  void                                      push_bit_mask(Handle _hnd, unsigned int _bit_mask)
Jan Möbius's avatar
Jan Möbius committed
868 869 870 871 872 873 874 875
  {
    assert(std::find(bit_masks(_hnd).begin(), bit_masks(_hnd).end(), _bit_mask) ==
           bit_masks(_hnd).end());//this mask should be not already used
    bit_masks(_hnd).push_back(_bit_mask);
  }

  void                                      init_bit_masks(BitMaskContainer& _bmc);
  void                                      init_bit_masks();
876

877
protected:
Jan Möbius's avatar
Jan Möbius committed
878 879 880 881 882 883

  VertexStatusPropertyHandle                vertex_status_;
  HalfedgeStatusPropertyHandle              halfedge_status_;
  EdgeStatusPropertyHandle                  edge_status_;
  FaceStatusPropertyHandle                  face_status_;

884 885 886 887
  unsigned int                              refcount_vstatus_;
  unsigned int                              refcount_hstatus_;
  unsigned int                              refcount_estatus_;
  unsigned int                              refcount_fstatus_;
Jan Möbius's avatar
Jan Möbius committed
888

889 890 891 892 893
private:
  VertexContainer                           vertices_;
  EdgeContainer                             edges_;
  FaceContainer                             faces_;

Jan Möbius's avatar
Jan Möbius committed
894 895 896 897 898 899
  BitMaskContainer                          halfedge_bit_masks_;
  BitMaskContainer                          edge_bit_masks_;
  BitMaskContainer                          vertex_bit_masks_;
  BitMaskContainer                          face_bit_masks_;
};

900

Jan Möbius's avatar
Jan Möbius committed
901 902 903
//=============================================================================
} // namespace OpenMesh
//=============================================================================
904 905
#if defined(OM_INCLUDE_TEMPLATES) && !defined(OPENMESH_ARRAY_KERNEL_C)
#  define OPENMESH_ARRAY_KERNEL_TEMPLATES
906
#  include "ArrayKernelT_impl.hh"
907 908
#endif
//=============================================================================
Jan Möbius's avatar
Jan Möbius committed
909 910
#endif // OPENMESH_ARRAY_KERNEL_HH defined
//=============================================================================