00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #ifndef OPENMESH_ARRAY_KERNEL_HH
00040 #define OPENMESH_ARRAY_KERNEL_HH
00041
00042
00043
00044
00045
00046 #include <OpenMesh/Core/System/config.h>
00047 #include <OpenMesh/Core/Mesh/Kernels/Common/AttribKernelT.hh>
00048 #include <OpenMesh/Core/Utils/GenProg.hh>
00049 #include <vector>
00050
00051
00052
00053
00054
00055
00056 namespace OpenMesh {
00057
00058
00059
00060
00061
00078 template <class AttribKernel, class FinalMeshItems>
00079 class ArrayKernelT : public AttribKernel
00080 {
00081 public:
00082
00083 typedef ArrayKernelT<AttribKernel, FinalMeshItems> This;
00084 typedef AttribKernel Base;
00085
00086
00087 typedef typename Base::HasPrevHalfedge HasPrevHalfedge;
00088
00089
00090 typedef typename FinalMeshItems::Vertex Vertex;
00091 typedef typename FinalMeshItems::Halfedge Halfedge;
00092 typedef typename FinalMeshItems::Edge Edge;
00093 typedef typename FinalMeshItems::Face Face;
00094 typedef typename FinalMeshItems::Point Point;
00095 typedef typename FinalMeshItems::Scalar Scalar;
00096
00097
00098 typedef OpenMesh::VertexHandle VertexHandle;
00099 typedef OpenMesh::HalfedgeHandle HalfedgeHandle;
00100 typedef OpenMesh::EdgeHandle EdgeHandle;
00101 typedef OpenMesh::FaceHandle FaceHandle;
00102
00103
00104
00105
00106
00107
00108 ArrayKernelT() {}
00109 ~ArrayKernelT() { clear(); }
00110
00111
00112
00113
00114
00115 VertexHandle handle(const Vertex& _v) const {
00116 return VertexHandle(&_v - &vertices_.front());
00117 }
00118
00119 HalfedgeHandle handle(const Halfedge& _he) const {
00120 unsigned int eh(((char*)&edges_.front() - (char*)&_he) % sizeof(Edge));
00121 assert((&_he == &edges_[eh].halfedges_[0]) ||
00122 (&_he == &edges_[eh].halfedges_[1]));
00123 return ((&_he == &edges_[eh].halfedges_[0]) ?
00124 HalfedgeHandle(eh<<1) :
00125 HalfedgeHandle((eh<<1)+1));
00126 }
00127
00128 EdgeHandle handle(const Edge& _e) const {
00129 return EdgeHandle(&_e - &edges_.front());
00130 }
00131
00132 FaceHandle handle(const Face& _f) const {
00133 return FaceHandle(&_f - &faces_.front());
00134 }
00135
00136
00137
00138 #define SIGNED(x) signed( (x) )
00139
00140
00141
00142
00143 const Vertex& vertex(VertexHandle _vh) const {
00144 assert(_vh.idx() >= 0 && _vh.idx() < SIGNED(n_vertices()));
00145 return vertices_[_vh.idx()];
00146 }
00147
00148 Vertex& vertex(VertexHandle _vh) {
00149 assert(_vh.idx() >= 0 && _vh.idx() < SIGNED(n_vertices()));
00150 return vertices_[_vh.idx()];
00151 }
00152
00153
00154 const Halfedge& halfedge(HalfedgeHandle _heh) const {
00155 assert(_heh.idx() >= 0 && _heh.idx() < SIGNED(n_edges()*2));
00156 return edges_[_heh.idx() >> 1].halfedges_[_heh.idx() & 1];
00157 }
00158
00159 Halfedge& halfedge(HalfedgeHandle _heh) {
00160 assert(_heh.idx() >= 0 && _heh.idx() < SIGNED(n_edges())*2);
00161 return edges_[_heh.idx() >> 1].halfedges_[_heh.idx() & 1];
00162 }
00163
00164
00165 const Edge& edge(EdgeHandle _eh) const {
00166 assert(_eh.idx() >= 0 && _eh.idx() < SIGNED(n_edges()));
00167 return edges_[_eh.idx()];
00168 }
00169
00170 Edge& edge(EdgeHandle _eh) {
00171 assert(_eh.idx() >= 0 && _eh.idx() < SIGNED(n_edges()));
00172 return edges_[_eh.idx()];
00173 }
00174
00175
00176 const Face& face(FaceHandle _fh) const {
00177 assert(_fh.idx() >= 0 && _fh.idx() < SIGNED(n_faces()));
00178 return faces_[_fh.idx()];
00179 }
00180
00181 Face& face(FaceHandle _fh) {
00182 assert(_fh.idx() >= 0 && _fh.idx() < SIGNED(n_faces()));
00183 return faces_[_fh.idx()];
00184 }
00185
00186 #undef SIGNED
00187
00188
00189
00190
00191
00192 VertexHandle vertex_handle(unsigned int _i) const {
00193 return (_i < n_vertices()) ? handle( vertices_[_i] ) : VertexHandle();
00194 }
00195
00196 HalfedgeHandle halfedge_handle(unsigned int _i) const {
00197 return (_i < n_halfedges()) ? halfedge_handle(edge_handle(_i/2), _i%2) : HalfedgeHandle();
00198 }
00199
00200 EdgeHandle edge_handle(unsigned int _i) const {
00201 return (_i < n_edges()) ? handle(edges_[_i]) : EdgeHandle();
00202 }
00203
00204 FaceHandle face_handle(unsigned int _i) const {
00205 return (_i < n_faces()) ? handle(faces_[_i]) : FaceHandle();
00206 }
00207
00208
00209
00210
00211 void reserve( unsigned int _n_vertices,
00212 unsigned int _n_edges,
00213 unsigned int _n_faces ) {
00214 vertices_.reserve(_n_vertices);
00215 edges_.reserve(_n_edges);
00216 faces_.reserve(_n_faces);
00217
00218 vprops_reserve(_n_vertices);
00219 hprops_reserve(_n_edges*2);
00220 eprops_reserve(_n_edges);
00221 fprops_reserve(_n_faces);
00222 }
00223
00224
00225 public:
00226
00227 VertexHandle new_vertex() {
00228 vertices_.push_back(Vertex());
00229 vprops_resize(n_vertices());
00230
00231 return handle(vertices_.back());
00232 }
00233
00234
00235 VertexHandle new_vertex(const Point& _p) {
00236 vertices_.push_back(Vertex());
00237 vprops_resize(n_vertices());
00238
00239 VertexHandle vh(handle(vertices_.back()));
00240 set_point(vh, _p);
00241 return vh;
00242 }
00243
00244
00245 HalfedgeHandle new_edge(VertexHandle _start_vertex_handle,
00246 VertexHandle _end_vertex_handle)
00247 {
00248 edges_.push_back(Edge());
00249 eprops_resize(n_edges());
00250 hprops_resize(n_halfedges());
00251
00252 EdgeHandle eh(handle(edges_.back()));
00253 HalfedgeHandle heh0(halfedge_handle(eh, 0));
00254 HalfedgeHandle heh1(halfedge_handle(eh, 1));
00255 set_vertex_handle(heh0, _end_vertex_handle);
00256 set_vertex_handle(heh1, _start_vertex_handle);
00257 return heh0;
00258 }
00259
00260
00261 FaceHandle new_face() {
00262 faces_.push_back(Face());
00263 fprops_resize(n_faces());
00264 return handle(faces_.back());
00265 }
00266
00267 FaceHandle new_face(const Face& _f) {
00268 faces_.push_back(_f);
00269 fprops_resize(n_faces());
00270 return handle(faces_.back());
00271 }
00272
00273 public:
00274
00275
00276
00277
00278
00279 void garbage_collection(bool _v=true, bool _e=true, bool _f=true);
00280
00281 void clear() {
00282 vertices_.clear();
00283 edges_.clear();
00284 faces_.clear();
00285
00286 vprops_resize(0);
00287 eprops_resize(0);
00288 hprops_resize(0);
00289 fprops_resize(0);
00290 }
00291
00292 void resize( unsigned int _n_vertices,
00293 unsigned int _n_edges,
00294 unsigned int _n_faces )
00295 {
00296 vertices_.resize(_n_vertices);
00297 edges_.resize(_n_edges);
00298 faces_.resize(_n_faces);
00299
00300 vprops_resize(n_vertices());
00301 hprops_resize(n_halfedges());
00302 eprops_resize(n_edges());
00303 fprops_resize(n_faces());
00304 }
00305
00306
00307
00308
00309
00310
00311 unsigned int n_vertices() const { return vertices_.size(); }
00312 unsigned int n_halfedges() const { return 2*edges_.size(); }
00313 unsigned int n_edges() const { return edges_.size(); }
00314 unsigned int n_faces() const { return faces_.size(); }
00315
00316 bool vertices_empty() const { return vertices_.empty(); }
00317 bool halfedges_empty() const { return edges_.empty(); }
00318 bool edges_empty() const { return edges_.empty(); }
00319 bool faces_empty() const { return faces_.empty(); }
00320
00321
00322
00323
00324
00325
00326
00327 HalfedgeHandle halfedge_handle(VertexHandle _vh) const {
00328 return vertex(_vh).halfedge_handle_;
00329 }
00330
00331 void set_halfedge_handle(VertexHandle _vh, HalfedgeHandle _heh) {
00332 vertex(_vh).halfedge_handle_ = _heh;
00333 }
00334
00335
00336
00337
00338
00339
00340 VertexHandle to_vertex_handle(HalfedgeHandle _heh) const {
00341 return halfedge(_heh).vertex_handle_;
00342 }
00343
00344 VertexHandle from_vertex_handle(HalfedgeHandle _heh) const {
00345 return to_vertex_handle(opposite_halfedge_handle(_heh));
00346 }
00347
00348 void set_vertex_handle(HalfedgeHandle _heh, VertexHandle _vh) {
00349 halfedge(_heh).vertex_handle_ = _vh;
00350 }
00351
00352
00353
00354 FaceHandle face_handle(HalfedgeHandle _heh) const {
00355 return halfedge(_heh).face_handle_;
00356 }
00357
00358 void set_face_handle(HalfedgeHandle _heh, FaceHandle _fh) {
00359 halfedge(_heh).face_handle_ = _fh;
00360 }
00361
00362
00363 HalfedgeHandle next_halfedge_handle(HalfedgeHandle _heh) const {
00364 return halfedge(_heh).next_halfedge_handle_;
00365 }
00366
00367 void set_next_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _nheh) {
00368 halfedge(_heh).next_halfedge_handle_ = _nheh;
00369 set_prev_halfedge_handle(_nheh, _heh);
00370 }
00371
00372
00373 void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh) {
00374 set_prev_halfedge_handle(_heh, _pheh, HasPrevHalfedge());
00375 }
00376
00377 void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
00378 GenProg::True) {
00379 halfedge(_heh).prev_halfedge_handle_ = _pheh;
00380 }
00381 void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
00382 GenProg::False) {}
00383
00384
00385 HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh) const {
00386 return prev_halfedge_handle(_heh, HasPrevHalfedge() );
00387 }
00388
00389 HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh,
00390 GenProg::True) const {
00391 return halfedge(_heh).prev_halfedge_handle_;
00392 }
00393
00394 HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh,
00395 GenProg::False) const {
00396 HalfedgeHandle heh(_heh);
00397 HalfedgeHandle next_heh(next_halfedge_handle(heh));
00398 while (next_heh != _heh) {
00399 heh = next_heh;
00400 next_heh = next_halfedge_handle(next_heh);
00401 }
00402 return heh;
00403 }
00404
00405
00406 HalfedgeHandle opposite_halfedge_handle(HalfedgeHandle _heh) const {
00407 return HalfedgeHandle((_heh.idx() & 1) ? _heh.idx()-1 : _heh.idx()+1);
00408 }
00409
00410
00411 HalfedgeHandle ccw_rotated_halfedge_handle(HalfedgeHandle _heh) const {
00412 return opposite_halfedge_handle(prev_halfedge_handle(_heh));
00413 }
00414
00415
00416 HalfedgeHandle cw_rotated_halfedge_handle(HalfedgeHandle _heh) const {
00417 return next_halfedge_handle(opposite_halfedge_handle(_heh));
00418 }
00419
00420
00421
00422
00423
00424
00425 HalfedgeHandle halfedge_handle(EdgeHandle _eh, unsigned int _i) const {
00426 assert(_i<=1);
00427 return HalfedgeHandle((_eh.idx() << 1) + _i);
00428 }
00429
00430
00431 EdgeHandle edge_handle(HalfedgeHandle _heh) const {
00432 return EdgeHandle(_heh.idx() >> 1);
00433 }
00434
00435
00436
00437
00438
00439
00440 HalfedgeHandle halfedge_handle(FaceHandle _fh) const {
00441 return face(_fh).halfedge_handle_;
00442 }
00443
00444 void set_halfedge_handle(FaceHandle _fh, HalfedgeHandle _heh) {
00445 face(_fh).halfedge_handle_ = _heh;
00446 }
00447
00448
00449
00450 private:
00451
00452
00453 typedef std::vector<Vertex> VertexContainer;
00454 typedef std::vector<Edge> EdgeContainer;
00455 typedef std::vector<Face> FaceContainer;
00456 typedef typename VertexContainer::iterator KernelVertexIter;
00457 typedef typename VertexContainer::const_iterator KernelConstVertexIter;
00458 typedef typename EdgeContainer::iterator KernelEdgeIter;
00459 typedef typename EdgeContainer::const_iterator KernelConstEdgeIter;
00460 typedef typename FaceContainer::iterator KernelFaceIter;
00461 typedef typename FaceContainer::const_iterator KernelConstFaceIter;
00462
00463
00464 KernelVertexIter vertices_begin() { return vertices_.begin(); }
00465 KernelConstVertexIter vertices_begin() const { return vertices_.begin(); }
00466 KernelVertexIter vertices_end() { return vertices_.end(); }
00467 KernelConstVertexIter vertices_end() const { return vertices_.end(); }
00468
00469 KernelEdgeIter edges_begin() { return edges_.begin(); }
00470 KernelConstEdgeIter edges_begin() const { return edges_.begin(); }
00471 KernelEdgeIter edges_end() { return edges_.end(); }
00472 KernelConstEdgeIter edges_end() const { return edges_.end(); }
00473
00474 KernelFaceIter faces_begin() { return faces_.begin(); }
00475 KernelConstFaceIter faces_begin() const { return faces_.begin(); }
00476 KernelFaceIter faces_end() { return faces_.end(); }
00477 KernelConstFaceIter faces_end() const { return faces_.end(); }
00478
00479
00480 private:
00481
00482 VertexContainer vertices_;
00483 EdgeContainer edges_;
00484 FaceContainer faces_;
00485 };
00486
00487
00488
00489
00490
00491 template <class AttribKernel, class FinalMeshItems>
00492 void
00493 ArrayKernelT<AttribKernel, FinalMeshItems>::
00494 garbage_collection(bool _v, bool _e, bool _f)
00495 {
00496 int i, i0, i1,
00497 nV(n_vertices()),
00498 nE(n_edges()),
00499 nH(2*n_edges()),
00500 nF(n_faces());
00501
00502 std::vector<VertexHandle> vh_map;
00503 std::vector<HalfedgeHandle> hh_map;
00504 std::vector<FaceHandle> fh_map;
00505
00506
00507
00508
00509 vh_map.reserve(nV+1);
00510 for (i=-1; i<nV; ++i) vh_map.push_back(VertexHandle(i));
00511
00512 hh_map.reserve(nH+1);
00513 for (i=-1; i<nH; ++i) hh_map.push_back(HalfedgeHandle(i));
00514
00515 fh_map.reserve(nF+1);
00516 for (i=-1; i<nF; ++i) fh_map.push_back(FaceHandle(i));
00517
00518
00519
00520
00521 if (_v && n_vertices() > 0)
00522 {
00523 i0=0; i1=nV-1;
00524
00525 while (1)
00526 {
00527
00528 while (!status(VertexHandle(i0)).deleted() && i0 < i1) ++i0;
00529 while ( status(VertexHandle(i1)).deleted() && i0 < i1) --i1;
00530 if (i0 >= i1) break;
00531
00532
00533 std::swap(vertices_[i0], vertices_[i1]);
00534 std::swap(vh_map[i0+1], vh_map[i1+1]);
00535 vprops_swap(i0, i1);
00536 };
00537
00538 vertices_.resize(status(VertexHandle(i0)).deleted() ? i0 : i0+1);
00539 vprops_resize(n_vertices());
00540 }
00541
00542
00543
00544 if (_e && n_edges() > 0)
00545 {
00546 i0=0; i1=nE-1;
00547
00548 while (1)
00549 {
00550
00551 while (!status(EdgeHandle(i0)).deleted() && i0 < i1) ++i0;
00552 while ( status(EdgeHandle(i1)).deleted() && i0 < i1) --i1;
00553 if (i0 >= i1) break;
00554
00555
00556 std::swap(edges_[i0], edges_[i1]);
00557 std::swap(hh_map[2*i0+1], hh_map[2*i1+1]);
00558 std::swap(hh_map[2*i0+2], hh_map[2*i1+2]);
00559 eprops_swap(i0, i1);
00560 hprops_swap(2*i0, 2*i1);
00561 hprops_swap(2*i0+1, 2*i1+1);
00562 };
00563
00564 edges_.resize(status(EdgeHandle(i0)).deleted() ? i0 : i0+1);
00565 eprops_resize(n_edges());
00566 hprops_resize(n_halfedges());
00567 }
00568
00569
00570
00571 if (_f && n_faces() > 0)
00572 {
00573 i0=0; i1=nF-1;
00574
00575 while (1)
00576 {
00577
00578 while (!status(FaceHandle(i0)).deleted() && i0 < i1) ++i0;
00579 while ( status(FaceHandle(i1)).deleted() && i0 < i1) --i1;
00580 if (i0 >= i1) break;
00581
00582
00583 std::swap(faces_[i0], faces_[i1]);
00584 std::swap(fh_map[i0+1], fh_map[i1+1]);
00585 fprops_swap(i0, i1);
00586 };
00587
00588 faces_.resize(status(FaceHandle(i0)).deleted() ? i0 : i0+1);
00589 fprops_resize(n_faces());
00590 }
00591
00592
00593
00594 if (_e)
00595 {
00596 KernelVertexIter v_it(vertices_begin()), v_end(vertices_end());
00597 VertexHandle vh;
00598
00599 for (; v_it!=v_end; ++v_it)
00600 {
00601 vh = handle(*v_it);
00602 set_halfedge_handle(vh, hh_map[halfedge_handle(vh).idx()+1]);
00603 }
00604 }
00605
00606
00607
00608 KernelEdgeIter e_it(edges_begin()), e_end(edges_end());
00609 HalfedgeHandle hh;
00610
00611 for (; e_it!=e_end; ++e_it)
00612 {
00613 hh = halfedge_handle(handle(*e_it), 0);
00614 set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()+1]);
00615 set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()+1]);
00616 set_face_handle(hh, fh_map[face_handle(hh).idx()+1]);
00617
00618 hh = halfedge_handle(handle(*e_it), 1);
00619 set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()+1]);
00620 set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()+1]);
00621 set_face_handle(hh, fh_map[face_handle(hh).idx()+1]);
00622 }
00623
00624
00625
00626 if (_e)
00627 {
00628 KernelFaceIter f_it(faces_begin()), f_end(faces_end());
00629 FaceHandle fh;
00630
00631 for (; f_it!=f_end; ++f_it)
00632 {
00633 fh = handle(*f_it);
00634 set_halfedge_handle(fh, hh_map[halfedge_handle(fh).idx()+1]);
00635 }
00636 }
00637
00638 }
00639
00640
00641
00642 }
00643
00644 #endif // OPENMESH_ARRAY_KERNEL_HH defined
00645