Mesh.hh 40.7 KB
Newer Older
Philip Trettner's avatar
Philip Trettner committed
1
2
#pragma once

Philip Trettner's avatar
Philip Trettner committed
3
#include <cstddef>
4
#include <memory>
Philip Trettner's avatar
Philip Trettner committed
5
6
#include <vector>

7
#include "cursors.hh"
8
#include "attributes.hh"
9
#include "ranges.hh"
Philip Trettner's avatar
Philip Trettner committed
10

Philip Trettner's avatar
Philip Trettner committed
11
12
namespace polymesh
{
13
14
using SharedMesh = std::shared_ptr<Mesh>;

Philip Trettner's avatar
Philip Trettner committed
15
/**
Philip Trettner's avatar
Philip Trettner committed
16
 * @brief Half-edge Mesh Data Structure
17
 *
Philip Trettner's avatar
Philip Trettner committed
18
19
 *  * Primitives are accessed via the smart collections mesh.<primitive>()
 *    (where <primitive> can be vertices, edges, faces, or halfedges)
20
 *
Philip Trettner's avatar
Philip Trettner committed
21
22
 *  * Primitives can be added via <primitive>().add()
 *    (added primitives are at the end of the collection)
Philip Trettner's avatar
Philip Trettner committed
23
 *
Philip Trettner's avatar
Philip Trettner committed
24
25
 *  * Primitives can be deleted via <primitive>().delete(...)
 *    (deleted primitives are invalidated (flagged for removal). call compactify() to remove them)
26
 *
Philip Trettner's avatar
Philip Trettner committed
27
28
29
30
31
32
 *  * `for (auto h : <primitive>())` iterates over _all_ primitives, including invalid ones
 *    (`for (auto h : valid_<primitive>())` skips over invalid ones)
 *
 * For more concept documents see:
 *  * http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm
 *  * https://www.openmesh.org/media/Documentations/OpenMesh-Doc-Latest/a03930.html
Philip Trettner's avatar
Philip Trettner committed
33
 */
Philip Trettner's avatar
Philip Trettner committed
34
class Mesh
Philip Trettner's avatar
Philip Trettner committed
35
{
Philip Trettner's avatar
Philip Trettner committed
36
37
    // accessors and iterators
public:
38
39
    /// smart collections for primitives INCLUDING deleted ones
    /// Also primary interfaces for querying size and adding primitives
Philip Trettner's avatar
Philip Trettner committed
40
41
42
    ///
    /// CAUTION: includes deleted ones!
    ///   use compactify() to ensure that no deleted ones exist
43
    ///   use valid_<primitive>() to skip deleted ones during iteration (slower)
Philip Trettner's avatar
Philip Trettner committed
44
    ///
45
    /// NOTE: adding primitives does NOT invalidate ranges. (newly added ones are NOT processed though)
Philip Trettner's avatar
Philip Trettner committed
46
    ///       deleting primitives does NOT invalidate ranges.
47
48
49
50
    vertex_collection vertices() { return {this}; }
    face_collection faces() { return {this}; }
    edge_collection edges() { return {this}; }
    halfedge_collection halfedges() { return {this}; }
51
52
53
54
55
    // const versions:
    const_vertex_collection vertices() const { return {this}; }
    const_face_collection faces() const { return {this}; }
    const_edge_collection edges() const { return {this}; }
    const_halfedge_collection halfedges() const { return {this}; }
Philip Trettner's avatar
Philip Trettner committed
56

57
58
59
60
61
62
63
64
65
66
    /// smart collections for VALID primitives (EXCLUDING deleted ones)
    ///
    /// NOTE: if mesh.is_compact() is guaranteed, <primitive>() is faster than valid_<primitive>()
    ///
    /// NOTE: adding primitives does NOT invalidate ranges. (newly added ones are NOT processed though)
    ///       deleting primitives does NOT invalidate ranges. (they will be skipped)
    valid_vertex_collection valid_vertices() const { return {this}; }
    valid_face_collection valid_faces() const { return {this}; }
    valid_edge_collection valid_edges() const { return {this}; }
    valid_halfedge_collection valid_halfedges() const { return {this}; }
Philip Trettner's avatar
Philip Trettner committed
67

Philip Trettner's avatar
Philip Trettner committed
68
69
70
71
72
73
74
75
76
77
78
79
    /// get handle from index
    face_handle handle_of(face_index idx) const { return {this, idx}; }
    edge_handle handle_of(edge_index idx) const { return {this, idx}; }
    vertex_handle handle_of(vertex_index idx) const { return {this, idx}; }
    halfedge_handle handle_of(halfedge_index idx) const { return {this, idx}; }

    /// get handle from index, subscript version
    face_handle operator[](face_index idx) const { return handle_of(idx); }
    edge_handle operator[](edge_index idx) const { return handle_of(idx); }
    vertex_handle operator[](vertex_index idx) const { return handle_of(idx); }
    halfedge_handle operator[](halfedge_index idx) const { return handle_of(idx); }

Philip Trettner's avatar
Philip Trettner committed
80
81
82
83
84
85
86
87
88
89
90
    // helper
public:
    /// Returns true if the mesh is guaranteed compact, otherwise call compactify() to be sure
    bool is_compact() const { return mCompact; }
    /// Removes all invalid/deleted primitives
    /// NOTE: cheap no-op if already compact
    void compactify();

    /// Asserts that mesh invariants hold, e.g. that the half-edge stored in a face actually bounds that face
    void assert_consistency() const;

91
92
93
94
    // ctor
public:
    Mesh() = default;

95
    /// Meshes can be neither moved nor copied because attributes depend on the Mesh address
96
97
98
99
100
101
102
103
104
105
    Mesh(Mesh const &) = delete;
    Mesh(Mesh &&) = delete;
    Mesh &operator=(Mesh const &) = delete;
    Mesh &operator=(Mesh &&) = delete;

    /// Creates a new mesh and returns a shared_ptr to it
    static SharedMesh create() { return std::make_shared<Mesh>(); }

    // internal helper
private:
Philip Trettner's avatar
Philip Trettner committed
106
107
108
    // reserves a certain number of primitives
    void reserve_faces(size_t capacity) { mFaces.reserve(capacity); }
    void reserve_vertices(size_t capacity) { mVertices.reserve(capacity); }
109
    void reserve_edges(size_t capacity) { mHalfedges.reserve(capacity * 2); }
Philip Trettner's avatar
Philip Trettner committed
110
111
    void reserve_halfedges(size_t capacity) { mHalfedges.reserve(capacity); }

112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
    int size_faces() const { return mFaces.size(); }
    int size_vertices() const { return mVertices.size(); }
    int size_edges() const { return mHalfedges.size() >> 1; }
    int size_halfedges() const { return mHalfedges.size(); }

    int size_valid_faces() const { return mFaces.size() - mDeletedFaces; }
    int size_valid_vertices() const { return mVertices.size() - mDeletedVertices; }
    int size_valid_edges() const { return (mHalfedges.size() - mDeletedHalfedges) >> 1; }
    int size_valid_halfedges() const { return mHalfedges.size() - mDeletedHalfedges; }

    // returns the next valid idx (returns the given one if valid)
    // NOTE: the result can be invalid if no valid one was found
    vertex_index next_valid_idx_from(vertex_index idx) const;
    edge_index next_valid_idx_from(edge_index idx) const;
    face_index next_valid_idx_from(face_index idx) const;
    halfedge_index next_valid_idx_from(halfedge_index idx) const;
    // returns the next valid idx (returns the given one if valid) counting DOWNWARDS
    vertex_index prev_valid_idx_from(vertex_index idx) const;
    edge_index prev_valid_idx_from(edge_index idx) const;
    face_index prev_valid_idx_from(face_index idx) const;
    halfedge_index prev_valid_idx_from(halfedge_index idx) const;

    // Iterators
    vertex_iterator vertices_begin() const { return {{this, vertex_index(0)}}; }
    vertex_iterator vertices_end() const { return {{this, vertex_index(mVertices.size())}}; }
    valid_vertex_iterator valid_vertices_begin() const { return {{this, vertex_index(0)}}; }
    valid_vertex_iterator valid_vertices_end() const { return {{this, vertex_index(mVertices.size())}}; }

    face_iterator faces_begin() const { return {{this, face_index(0)}}; }
    face_iterator faces_end() const { return {{this, face_index(mFaces.size())}}; }
    valid_face_iterator valid_faces_begin() const { return {{this, face_index(0)}}; }
    valid_face_iterator valid_faces_end() const { return {{this, face_index(mFaces.size())}}; }

    edge_iterator edges_begin() const { return {{this, edge_index(0)}}; }
    edge_iterator edges_end() const { return {{this, edge_index(mHalfedges.size() >> 1)}}; }
    valid_edge_iterator valid_edges_begin() const { return {{this, edge_index(0)}}; }
    valid_edge_iterator valid_edges_end() const { return {{this, edge_index(mHalfedges.size() >> 1)}}; }

    halfedge_iterator halfedges_begin() const { return {{this, halfedge_index(0)}}; }
    halfedge_iterator halfedges_end() const { return {{this, halfedge_index(mHalfedges.size())}}; }
    valid_halfedge_iterator valid_halfedges_begin() const { return {{this, halfedge_index(0)}}; }
    valid_halfedge_iterator valid_halfedges_end() const { return {{this, halfedge_index(mHalfedges.size())}}; }
Philip Trettner's avatar
Philip Trettner committed
154

Philip Trettner's avatar
Philip Trettner committed
155
156
157
158
159
160
161
    /// Adds a single non-connected vertex
    /// Does NOT invalidate iterators!
    vertex_index add_vertex();

    /// Adds a face consisting of N vertices
    /// The vertices must already be sorted in CCW order
    /// (note: trying to add already existing halfedges triggers assertions)
Philip Trettner's avatar
Philip Trettner committed
162
163
164
165
    face_index add_face(vertex_handle const *v_handles, size_t vcnt);
    face_index add_face(vertex_index const *v_indices, size_t vcnt);
    face_index add_face(halfedge_handle const *half_loop, size_t vcnt);
    face_index add_face(halfedge_index const *half_loop, size_t vcnt);
Philip Trettner's avatar
Philip Trettner committed
166
167
168
169
170
171
172
173

    /// Adds an edge between two existing, distinct vertices
    /// if edge already exists, returns it
    edge_index add_or_get_edge(vertex_index v_from, vertex_index v_to);

    /// same as add_or_get_edge but returns the appropriate half-edge
    halfedge_index add_or_get_halfedge(vertex_index v_from, vertex_index v_to);

174
    // attributes
Philip Trettner's avatar
Philip Trettner committed
175
176
177
178
179
180
181
182
183
184
185
186
187
    bool is_boundary(vertex_index idx) const;
    bool is_boundary(halfedge_index idx) const;

    /// Returns the opposite of a given valid half-edge
    halfedge_index opposite(halfedge_index he) const;

    /// Makes two half-edges adjacent
    /// Ensures:
    ///     * he_in->next == he_out
    ///     * he_out->prev == he_in
    /// Requires:
    ///     * he_in->is_free()
    ///     * he_out->is_free()
Philip Trettner's avatar
Philip Trettner committed
188
189
    /// Only works if a free incident half-edge is available
    void make_adjacent(halfedge_index he_in, halfedge_index he_out);
Philip Trettner's avatar
Philip Trettner committed
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

    /// finds the next free incoming half-edge around a certain vertex
    /// starting from in_begin, EXCLUDING in_end (if in_begin == in_end, the whole vertex is searched)
    /// returns invalid index if no edge is found
    halfedge_index find_free_incident(halfedge_index in_begin, halfedge_index in_end) const;
    /// finds a free incident incoming half-edge around a given vertex
    halfedge_index find_free_incident(vertex_index v) const;

    /// returns half-edge going from `from`, point to `to`
    /// returns invalid index if not exists
    halfedge_index find_halfedge(vertex_index from, vertex_index to) const;

    /// returns edge index belonging to a half-edge
    edge_index edge_of(halfedge_index idx) const { return edge_index(idx.value >> 1); }
    /// returns a half-edge belonging to an edge
Philip Trettner's avatar
Philip Trettner committed
205
206
207
    halfedge_index halfedge_of(edge_index idx, int i) const { return halfedge_index((idx.value << 1) + i); }

    /// returns the vertex that this half-edge is pointing to
208
    vertex_index to_vertex_of(halfedge_index idx) const { return halfedge(idx).to_vertex; }
Philip Trettner's avatar
Philip Trettner committed
209
    /// returns the vertex that this half-edge is leaving from
210
    vertex_index from_vertex_of(halfedge_index idx) const { return halfedge(opposite(idx)).to_vertex; }
Philip Trettner's avatar
Philip Trettner committed
211

Philip Trettner's avatar
Philip Trettner committed
212
    // internal datastructures
Philip Trettner's avatar
Philip Trettner committed
213
private:
Philip Trettner's avatar
Philip Trettner committed
214
    // 4 byte per face
215
    struct face_info
Philip Trettner's avatar
Philip Trettner committed
216
    {
217
        halfedge_index halfedge; ///< one half-edge bounding this face
Philip Trettner's avatar
Philip Trettner committed
218
219

        bool is_valid() const { return halfedge.is_valid(); }
220
        void set_deleted() { halfedge = halfedge_index::invalid(); }
Philip Trettner's avatar
Philip Trettner committed
221
222
    };

Philip Trettner's avatar
Philip Trettner committed
223
    // 4 byte per vertex
224
    struct vertex_info
Philip Trettner's avatar
Philip Trettner committed
225
    {
226
        halfedge_index outgoing_halfedge;
Philip Trettner's avatar
Philip Trettner committed
227
228
229

        /// a vertex can be valid even without outgoing halfedge
        bool is_valid() const { return outgoing_halfedge.value >= -1; }
Philip Trettner's avatar
Philip Trettner committed
230
        bool is_isolated() const { return !outgoing_halfedge.is_valid(); }
231
        void set_deleted() { outgoing_halfedge = halfedge_index(-2); }
Philip Trettner's avatar
Philip Trettner committed
232
        // is_boundary: check if outgoing_halfedge is boundary
Philip Trettner's avatar
Philip Trettner committed
233
    };
Philip Trettner's avatar
Philip Trettner committed
234

Philip Trettner's avatar
Philip Trettner committed
235
    // 32 byte per edge
236
    struct halfedge_info
Philip Trettner's avatar
Philip Trettner committed
237
    {
Philip Trettner's avatar
Philip Trettner committed
238
        vertex_index to_vertex;       ///< half-edge points towards this vertex
239
240
241
        face_index face;              ///< might be invalid if boundary
        halfedge_index next_halfedge; ///< CCW
        halfedge_index prev_halfedge; ///< CW
Philip Trettner's avatar
Philip Trettner committed
242
243
244
        // opposite half-edge idx is "idx ^ 1"
        // edge idx is "idx >> 1"

Philip Trettner's avatar
Philip Trettner committed
245
246
247
248
249
250
251
        bool is_valid() const { return to_vertex.is_valid(); }

        /// a half-edge is free if it is a boundary, aka has no associated face
        bool is_free() const { return !face.is_valid(); }

        // CAUTION: delete both HE belonging to an edge
        void set_deleted() { to_vertex = vertex_index::invalid(); }
Philip Trettner's avatar
Philip Trettner committed
252
253
254
255
    };

    // internal primitives
private:
256
257
258
259
260
261
262
263
264
265
266
267
    std::vector<face_info> mFaces;
    std::vector<vertex_info> mVertices;
    std::vector<halfedge_info> mHalfedges;

    struct face_info &face(face_index i) { return mFaces[i.value]; }
    struct face_info const &face(face_index i) const { return mFaces[i.value]; }
    struct vertex_info &vertex(vertex_index i) { return mVertices[i.value]; }
    struct vertex_info const &vertex(vertex_index i) const { return mVertices[i.value]; }
    struct halfedge_info &halfedge(halfedge_index i) { return mHalfedges[i.value]; }
    struct halfedge_info const &halfedge(halfedge_index i) const { return mHalfedges[i.value]; }
    struct halfedge_info &halfedge(edge_index i, int h) { return mHalfedges[(i.value >> 1) + h]; }
    struct halfedge_info const &halfedge(edge_index i, int h) const { return mHalfedges[(i.value >> 1) + h]; }
Philip Trettner's avatar
Philip Trettner committed
268
269
270
271

    // internal state
private:
    bool mCompact = true;
272
273
274
275
    int mDeletedFaces = 0;
    int mDeletedVertices = 0;
    int mDeletedHalfedges = 0;

Philip Trettner's avatar
Philip Trettner committed
276
277
    std::vector<halfedge_index> mFaceInsertCache;

278
    // attributes
Philip Trettner's avatar
Philip Trettner committed
279
private:
280
281
282
283
284
285
286
287
288
289
290
291
292
293
    // linked lists of all attributes
    mutable vertex_attribute_base *mVertexProps = nullptr;
    mutable face_attribute_base *mFaceProps = nullptr;
    mutable edge_attribute_base *mEdgeProps = nullptr;
    mutable halfedge_attribute_base *mHalfedgeProps = nullptr;

    void register_prop(vertex_attribute_base *prop) const;
    void deregister_prop(vertex_attribute_base *prop) const;
    void register_prop(face_attribute_base *prop) const;
    void deregister_prop(face_attribute_base *prop) const;
    void register_prop(edge_attribute_base *prop) const;
    void deregister_prop(edge_attribute_base *prop) const;
    void register_prop(halfedge_attribute_base *prop) const;
    void deregister_prop(halfedge_attribute_base *prop) const;
Philip Trettner's avatar
Philip Trettner committed
294

295
296
297
298
299
300
301
    // friends
private:
    friend struct vertex_handle;
    friend struct vertex_collection;
    friend struct vertex_iterator;
    friend struct valid_vertex_iterator;
    friend struct valid_vertex_collection;
302
    friend struct const_vertex_collection;
303
    friend struct vertex_attribute_base;
304
305
306
307
308
309

    friend struct face_handle;
    friend struct face_collection;
    friend struct face_iterator;
    friend struct valid_face_iterator;
    friend struct valid_face_collection;
310
    friend struct const_face_collection;
311
    friend struct face_attribute_base;
312
313
314
315
316
317

    friend struct edge_handle;
    friend struct edge_collection;
    friend struct edge_iterator;
    friend struct valid_edge_iterator;
    friend struct valid_edge_collection;
318
    friend struct const_edge_collection;
319
    friend struct edge_attribute_base;
320
321
322
323
324
325

    friend struct halfedge_handle;
    friend struct halfedge_collection;
    friend struct halfedge_iterator;
    friend struct valid_halfedge_iterator;
    friend struct valid_halfedge_collection;
326
    friend struct const_halfedge_collection;
327
    friend struct halfedge_attribute_base;
Philip Trettner's avatar
Philip Trettner committed
328
};
Philip Trettner's avatar
Philip Trettner committed
329
330
331

/// ======== IMPLEMENTATION ========

332
inline vertex_index Mesh::add_vertex()
Philip Trettner's avatar
Philip Trettner committed
333
{
Philip Trettner's avatar
Philip Trettner committed
334
    auto idx = vertex_index((int)mVertices.size());
335
    mVertices.push_back(vertex_info());
Philip Trettner's avatar
Philip Trettner committed
336

337
    // notify attributes
Philip Trettner's avatar
Philip Trettner committed
338
    auto vCnt = mVertices.size();
339
    for (auto p = mVertexProps; p; p = p->mNextAttribute)
Philip Trettner's avatar
Philip Trettner committed
340
341
        p->resize(vCnt);

Philip Trettner's avatar
Philip Trettner committed
342
    return idx;
Philip Trettner's avatar
Philip Trettner committed
343
344
}

345
inline face_index Mesh::add_face(const vertex_handle *v_handles, size_t vcnt)
Philip Trettner's avatar
Philip Trettner committed
346
{
Philip Trettner's avatar
Philip Trettner committed
347
348
349
350
351
352
    mFaceInsertCache.resize(vcnt);
    for (auto i = 0u; i < vcnt; ++i)
        mFaceInsertCache[i] = find_halfedge(v_handles[i].idx, v_handles[(i + 1) % vcnt].idx);
    return add_face(mFaceInsertCache.data(), vcnt);
}

353
inline face_index Mesh::add_face(const vertex_index *v_indices, size_t vcnt)
Philip Trettner's avatar
Philip Trettner committed
354
355
356
357
358
359
360
{
    mFaceInsertCache.resize(vcnt);
    for (auto i = 0u; i < vcnt; ++i)
        mFaceInsertCache[i] = find_halfedge(v_indices[i], v_indices[(i + 1) % vcnt]);
    return add_face(mFaceInsertCache.data(), vcnt);
}

361
inline face_index Mesh::add_face(const halfedge_handle *half_loop, size_t vcnt)
Philip Trettner's avatar
Philip Trettner committed
362
363
364
365
366
367
368
{
    mFaceInsertCache.resize(vcnt);
    for (auto i = 0u; i < vcnt; ++i)
        mFaceInsertCache[i] = half_loop[i].idx;
    return add_face(mFaceInsertCache.data(), vcnt);
}

369
inline face_index Mesh::add_face(const halfedge_index *half_loop, size_t vcnt)
Philip Trettner's avatar
Philip Trettner committed
370
371
{
    assert(vcnt >= 3 && "no support for less-than-triangular faces");
372
    /// TODO: attributes
Philip Trettner's avatar
Philip Trettner committed
373
374
375

    auto fidx = face_index((int)mFaces.size());

Philip Trettner's avatar
Philip Trettner committed
376
    // ensure that half-edges are adjacent at each vertex
Philip Trettner's avatar
Philip Trettner committed
377
    for (auto i = 0u; i < vcnt; ++i)
Philip Trettner's avatar
Philip Trettner committed
378
    {
Philip Trettner's avatar
Philip Trettner committed
379
380
381
382
383
384
        auto h0 = half_loop[i];
        auto h1 = half_loop[(i + 1) % vcnt];

        // half-edge must form a chain
        assert(to_vertex_of(h0) == from_vertex_of(h1));
        // half-edge must be free, i.e. allow a new polygon
385
        assert(halfedge(h0).is_free());
Philip Trettner's avatar
Philip Trettner committed
386
387
388
389
390

        // make them adjacent
        make_adjacent(h0, h1);

        // link face
391
        halfedge(h0).face = fidx;
Philip Trettner's avatar
Philip Trettner committed
392
393
    }

Philip Trettner's avatar
Philip Trettner committed
394
    // set up face data
395
    face_info f;
Philip Trettner's avatar
Philip Trettner committed
396
    f.halfedge = half_loop[0];
Philip Trettner's avatar
Philip Trettner committed
397
    mFaces.push_back(f);
Philip Trettner's avatar
Philip Trettner committed
398

399
    // notify attributes
Philip Trettner's avatar
Philip Trettner committed
400
    auto fCnt = mFaces.size();
401
    for (auto p = mFaceProps; p; p = p->mNextAttribute)
Philip Trettner's avatar
Philip Trettner committed
402
403
        p->resize(fCnt);

Philip Trettner's avatar
Philip Trettner committed
404
    return fidx;
Philip Trettner's avatar
Philip Trettner committed
405
406
}

407
inline edge_index Mesh::add_or_get_edge(vertex_index v_from, vertex_index v_to)
Philip Trettner's avatar
Philip Trettner committed
408
409
410
411
412
413
414
415
{
    assert(v_from != v_to);

    // already exists?
    auto he = find_halfedge(v_from, v_to);
    if (he.is_valid())
        return edge_of(he);

416
417
    auto &vd_from = vertex(v_from);
    auto &vd_to = vertex(v_to);
Philip Trettner's avatar
Philip Trettner committed
418
419
420
421
422
423

    // allocate new
    auto he_size = (int)mHalfedges.size();
    auto h_from_to_idx = halfedge_index(he_size + 0);
    auto h_to_from_idx = halfedge_index(he_size + 1);
    auto eidx = edge_index(he_size >> 1);
424
425
    halfedge_info h_from_to;
    halfedge_info h_to_from;
Philip Trettner's avatar
Philip Trettner committed
426
427
428
429
430
431
432
433
434
435
436
437
438
439

    // setup data (self-connected edge)
    h_from_to.to_vertex = v_to;
    h_to_from.to_vertex = v_from;
    h_from_to.next_halfedge = h_to_from_idx;
    h_to_from.next_halfedge = h_from_to_idx;

    // link from vertex
    if (vd_from.is_isolated())
        vd_from.outgoing_halfedge = h_from_to_idx;
    else
    {
        auto from_in_idx = find_free_incident(v_from);
        assert(from_in_idx.is_valid() && "vertex is already fully connected");
440
        auto &from_in = halfedge(from_in_idx);
Philip Trettner's avatar
Philip Trettner committed
441
        auto from_out_idx = from_in.next_halfedge;
442
        auto &from_out = halfedge(from_out_idx);
Philip Trettner's avatar
Philip Trettner committed
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457

        from_in.next_halfedge = h_from_to_idx;
        h_from_to.prev_halfedge = from_in_idx;

        h_to_from.next_halfedge = from_out_idx;
        from_out.prev_halfedge = h_to_from_idx;
    }

    // link to vertex
    if (vd_to.is_isolated())
        vd_to.outgoing_halfedge = h_from_to_idx;
    else
    {
        auto to_in_idx = find_free_incident(v_to);
        assert(to_in_idx.is_valid() && "vertex is already fully connected");
458
        auto &to_in = halfedge(to_in_idx);
Philip Trettner's avatar
Philip Trettner committed
459
        auto to_out_idx = to_in.next_halfedge;
460
        auto &to_out = halfedge(to_out_idx);
Philip Trettner's avatar
Philip Trettner committed
461
462
463
464
465
466
467
468
469
470
471

        to_in.next_halfedge = h_to_from_idx;
        h_to_from.prev_halfedge = to_in_idx;

        h_from_to.next_halfedge = to_out_idx;
        to_out.prev_halfedge = h_from_to_idx;
    }

    // finalize
    mHalfedges.push_back(h_from_to);
    mHalfedges.push_back(h_to_from);
Philip Trettner's avatar
Philip Trettner committed
472

473
    // notify attributes
Philip Trettner's avatar
Philip Trettner committed
474
475
    auto hCnt = mHalfedges.size();
    auto eCnt = hCnt >> 1;
476
    for (auto p = mHalfedgeProps; p; p = p->mNextAttribute)
Philip Trettner's avatar
Philip Trettner committed
477
        p->resize(hCnt);
478
    for (auto p = mEdgeProps; p; p = p->mNextAttribute)
Philip Trettner's avatar
Philip Trettner committed
479
480
        p->resize(eCnt);

Philip Trettner's avatar
Philip Trettner committed
481
482
483
    return eidx;
}

484
inline halfedge_index Mesh::add_or_get_halfedge(vertex_index v_from, vertex_index v_to)
Philip Trettner's avatar
Philip Trettner committed
485
486
487
488
{
    auto e = add_or_get_edge(v_from, v_to);
    auto h0 = halfedge_of(e, 0);
    auto h1 = halfedge_of(e, 1);
489
    return halfedge(h0).to_vertex == v_to ? h0 : h1;
Philip Trettner's avatar
Philip Trettner committed
490
491
}

492
inline void Mesh::make_adjacent(halfedge_index he_in, halfedge_index he_out)
Philip Trettner's avatar
Philip Trettner committed
493
494
{
    // see http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm ::makeAdjacent
495
496
    auto &in = halfedge(he_in);
    auto &out = halfedge(he_out);
Philip Trettner's avatar
Philip Trettner committed
497
498
499
500
501
502

    auto he_b = in.next_halfedge;
    auto he_d = out.prev_halfedge;

    // already correct
    if (he_b == he_out)
Philip Trettner's avatar
Philip Trettner committed
503
        return;
Philip Trettner's avatar
Philip Trettner committed
504
505
506

    // find free half-edge after `out` but before `in`
    auto he_g = find_free_incident(opposite(he_out), he_in);
Philip Trettner's avatar
Philip Trettner committed
507
    assert(he_g.is_valid()); // unable to make adjacent
Philip Trettner's avatar
Philip Trettner committed
508

509
510
511
    auto &b = halfedge(he_b);
    auto &d = halfedge(he_d);
    auto &g = halfedge(he_g);
Philip Trettner's avatar
Philip Trettner committed
512
513

    auto he_h = g.next_halfedge;
514
    auto &h = halfedge(he_d);
Philip Trettner's avatar
Philip Trettner committed
515
516
517
518
519
520
521
522
523
524
525
526

    // properly rewire
    in.next_halfedge = he_out;
    out.prev_halfedge = he_in;

    g.next_halfedge = he_b;
    b.prev_halfedge = he_g;

    d.next_halfedge = he_h;
    h.prev_halfedge = he_d;
}

527
inline halfedge_index Mesh::find_free_incident(halfedge_index in_begin, halfedge_index in_end) const
Philip Trettner's avatar
Philip Trettner committed
528
{
529
    assert(halfedge(in_begin).to_vertex == halfedge(in_end).to_vertex);
Philip Trettner's avatar
Philip Trettner committed
530
531
532
533

    auto he = in_begin;
    do
    {
534
535
        auto const &h = halfedge(he);
        assert(h.to_vertex == halfedge(in_end).to_vertex);
Philip Trettner's avatar
Philip Trettner committed
536
537
538
539
540
541
542
543
544
545
546
547

        // free? found one!
        if (h.is_free())
            return he;

        // next half-edge of vertex
        he = opposite(h.next_halfedge);
    } while (he != in_end);

    return halfedge_index::invalid();
}

548
inline halfedge_index Mesh::find_free_incident(vertex_index v) const
Philip Trettner's avatar
Philip Trettner committed
549
{
550
    auto in_begin = opposite(vertex(v).outgoing_halfedge);
Philip Trettner's avatar
Philip Trettner committed
551
552
553
    return find_free_incident(in_begin, in_begin);
}

554
inline halfedge_index Mesh::find_halfedge(vertex_index from, vertex_index to) const
Philip Trettner's avatar
Philip Trettner committed
555
{
556
    auto he_begin = vertex(from).outgoing_halfedge;
Philip Trettner's avatar
Philip Trettner committed
557
558
559
    if (!he_begin.is_valid())
        return halfedge_index::invalid(); // isolated vertex

Philip Trettner's avatar
Philip Trettner committed
560
561
562
    auto he = he_begin;
    do
    {
563
        auto const &h = halfedge(he);
Philip Trettner's avatar
Philip Trettner committed
564
565
566
567
568
569
570
571
572
573
574
575
576

        // found?
        if (h.to_vertex == to)
            return he;

        // advance
        he = opposite(h.next_halfedge);

    } while (he != he_begin);

    return halfedge_index::invalid(); // not found
}

577
inline bool Mesh::is_boundary(vertex_index idx) const
Philip Trettner's avatar
Philip Trettner committed
578
{
579
    auto const &v = vertex(idx);
Philip Trettner's avatar
Philip Trettner committed
580
581
582
    return v.outgoing_halfedge.is_valid() && is_boundary(v.outgoing_halfedge);
}

583
inline bool Mesh::is_boundary(halfedge_index idx) const
Philip Trettner's avatar
Philip Trettner committed
584
{
585
    return halfedge(idx).is_free();
Philip Trettner's avatar
Philip Trettner committed
586
587
}

588
inline halfedge_index Mesh::opposite(halfedge_index he) const
Philip Trettner's avatar
Philip Trettner committed
589
590
{
    return halfedge_index(he.value ^ 1);
Philip Trettner's avatar
Philip Trettner committed
591
592
}

593
inline vertex_index Mesh::next_valid_idx_from(vertex_index idx) const
Philip Trettner's avatar
Philip Trettner committed
594
{
595
    for (auto i = idx.value; i < (int)mVertices.size(); ++i)
Philip Trettner's avatar
Philip Trettner committed
596
        if (mVertices[i].is_valid())
597
598
            return vertex_index(i);
    return vertex_index(mVertices.size()); // end index
Philip Trettner's avatar
Philip Trettner committed
599
600
}

601
inline vertex_index Mesh::prev_valid_idx_from(vertex_index idx) const
Philip Trettner's avatar
Philip Trettner committed
602
{
603
    for (auto i = idx.value; i >= 0; --i)
Philip Trettner's avatar
Philip Trettner committed
604
        if (mVertices[i].is_valid())
605
            return vertex_index(i);
Philip Trettner's avatar
Philip Trettner committed
606
607
608
    return {}; // invalid
}

609
inline edge_index Mesh::next_valid_idx_from(edge_index idx) const
Philip Trettner's avatar
Philip Trettner committed
610
{
611
    for (auto i = idx.value << 1; i < (int)mHalfedges.size(); i += 2)
Philip Trettner's avatar
Philip Trettner committed
612
        if (mHalfedges[i].is_valid())
613
614
            return edge_index(i >> 1);
    return edge_index(mHalfedges.size() >> 1); // end index
Philip Trettner's avatar
Philip Trettner committed
615
616
}

617
inline edge_index Mesh::prev_valid_idx_from(edge_index idx) const
Philip Trettner's avatar
Philip Trettner committed
618
{
619
    for (auto i = idx.value << 1; i >= 0; i -= 2)
Philip Trettner's avatar
Philip Trettner committed
620
        if (mHalfedges[i].is_valid())
621
            return edge_index(i >> 1);
Philip Trettner's avatar
Philip Trettner committed
622
623
624
    return {}; // invalid
}

625
inline face_index Mesh::next_valid_idx_from(face_index idx) const
Philip Trettner's avatar
Philip Trettner committed
626
{
627
    for (auto i = idx.value; i < (int)mFaces.size(); ++i)
Philip Trettner's avatar
Philip Trettner committed
628
        if (mFaces[i].is_valid())
629
630
            return face_index(i);
    return face_index(mFaces.size()); // end index
Philip Trettner's avatar
Philip Trettner committed
631
632
}

633
inline face_index Mesh::prev_valid_idx_from(face_index idx) const
Philip Trettner's avatar
Philip Trettner committed
634
{
635
    for (auto i = idx.value; i >= 0; --i)
Philip Trettner's avatar
Philip Trettner committed
636
        if (mFaces[i].is_valid())
637
            return face_index(i);
Philip Trettner's avatar
Philip Trettner committed
638
639
640
    return {}; // invalid
}

641
inline halfedge_index Mesh::next_valid_idx_from(halfedge_index idx) const
Philip Trettner's avatar
Philip Trettner committed
642
{
643
    for (auto i = idx.value; i < (int)mHalfedges.size(); ++i)
Philip Trettner's avatar
Philip Trettner committed
644
        if (mHalfedges[i].is_valid())
645
646
            return halfedge_index(i);
    return halfedge_index(mHalfedges.size()); // end index
Philip Trettner's avatar
Philip Trettner committed
647
648
}

649
inline halfedge_index Mesh::prev_valid_idx_from(halfedge_index idx) const
Philip Trettner's avatar
Philip Trettner committed
650
{
651
    for (auto i = idx.value; i >= 0; --i)
Philip Trettner's avatar
Philip Trettner committed
652
        if (mHalfedges[i].is_valid())
653
            return halfedge_index(i);
Philip Trettner's avatar
Philip Trettner committed
654
655
656
657
658
    return {}; // invalid
}

/// ======== ITERATOR IMPLEMENTATION ========

659
inline valid_vertex_iterator &valid_vertex_iterator::operator++()
Philip Trettner's avatar
Philip Trettner committed
660
{
661
662
    handle.idx.value++;
    handle.idx = handle.mesh->next_valid_idx_from(handle.idx);
Philip Trettner's avatar
Philip Trettner committed
663
664
    return *this;
}
665
inline vertex_iterator &vertex_iterator::operator++()
Philip Trettner's avatar
Philip Trettner committed
666
667
668
669
{
    handle.idx.value++;
    return *this;
}
670

671
inline valid_face_iterator &valid_face_iterator::operator++()
672
673
674
675
676
{
    handle.idx.value++;
    handle.idx = handle.mesh->next_valid_idx_from(handle.idx);
    return *this;
}
677
inline face_iterator &face_iterator::operator++()
678
679
680
681
682
{
    handle.idx.value++;
    return *this;
}

683
inline valid_edge_iterator &valid_edge_iterator::operator++()
684
685
686
687
688
{
    handle.idx.value++;
    handle.idx = handle.mesh->next_valid_idx_from(handle.idx);
    return *this;
}
689
inline edge_iterator &edge_iterator::operator++()
690
691
692
693
694
{
    handle.idx.value++;
    return *this;
}

695
inline valid_halfedge_iterator &valid_halfedge_iterator::operator++()
696
697
698
699
700
{
    handle.idx.value++;
    handle.idx = handle.mesh->next_valid_idx_from(handle.idx);
    return *this;
}
701
inline halfedge_iterator &halfedge_iterator::operator++()
702
703
704
705
706
707
708
709
710
{
    handle.idx.value++;
    return *this;
}

/// ======== RANGES IMPLEMENTATION ========

// - Vertices -

711
inline int vertex_collection::size() const
712
713
714
715
{
    return mesh->size_vertices();
}

716
inline void vertex_collection::reserve(int capacity) const
717
718
719
720
{
    mesh->reserve_vertices(capacity);
}

721
inline vertex_handle vertex_collection::add() const
722
{
Philip Trettner's avatar
Philip Trettner committed
723
    return mesh->handle_of(mesh->add_vertex());
724
725
}

726
inline vertex_iterator vertex_collection::begin() const
727
728
729
730
{
    return mesh->vertices_begin();
}

731
inline vertex_iterator vertex_collection::end() const
732
733
734
735
{
    return mesh->vertices_end();
}

736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
inline int const_vertex_collection::size() const
{
    return mesh->size_vertices();
}

inline vertex_iterator const_vertex_collection::begin() const
{
    return mesh->vertices_begin();
}

inline vertex_iterator const_vertex_collection::end() const
{
    return mesh->vertices_end();
}

751
inline int valid_vertex_collection::size() const
752
753
754
755
{
    return mesh->size_valid_vertices();
}

756
inline valid_vertex_iterator valid_vertex_collection::begin() const
757
758
759
760
{
    return mesh->valid_vertices_begin();
}

761
inline valid_vertex_iterator valid_vertex_collection::end() const
762
763
764
765
766
767
{
    return mesh->valid_vertices_end();
}

// - Faces -

768
inline int face_collection::size() const
769
770
771
772
{
    return mesh->size_faces();
}

773
inline void face_collection::reserve(int capacity) const
774
775
776
777
{
    mesh->reserve_faces(capacity);
}

778
inline face_handle face_collection::add(const vertex_handle *v_handles, size_t vcnt) const
Philip Trettner's avatar
Philip Trettner committed
779
780
781
782
{
    return mesh->handle_of(mesh->add_face(v_handles, vcnt));
}

783
inline face_handle face_collection::add(const halfedge_handle *half_loop, size_t vcnt) const
Philip Trettner's avatar
Philip Trettner committed
784
785
786
787
{
    return mesh->handle_of(mesh->add_face(half_loop, vcnt));
}

788
inline face_handle face_collection::add(std::vector<vertex_handle> const &v_handles) const
Philip Trettner's avatar
Philip Trettner committed
789
{
Philip Trettner's avatar
Philip Trettner committed
790
    return add(v_handles.data(), v_handles.size());
Philip Trettner's avatar
Philip Trettner committed
791
792
}

793
inline face_handle face_collection::add(std::vector<halfedge_handle> const &half_loop) const
794
{
Philip Trettner's avatar
Philip Trettner committed
795
    return add(half_loop.data(), half_loop.size());
796
797
}

798
inline face_handle face_collection::add(vertex_handle v0, vertex_handle v1, vertex_handle v2) const
799
{
Philip Trettner's avatar
Philip Trettner committed
800
    halfedge_index hs[3] = {
Philip Trettner's avatar
Philip Trettner committed
801
802
803
        mesh->add_or_get_halfedge(v0.idx, v1.idx), //
        mesh->add_or_get_halfedge(v1.idx, v2.idx), //
        mesh->add_or_get_halfedge(v2.idx, v0.idx), //
Philip Trettner's avatar
Philip Trettner committed
804
805
    };
    return mesh->handle_of(mesh->add_face(hs, 3));
806
807
}

808
inline face_handle face_collection::add(vertex_handle v0, vertex_handle v1, vertex_handle v2, vertex_handle v3) const
809
{
Philip Trettner's avatar
Philip Trettner committed
810
    halfedge_index hs[4] = {
Philip Trettner's avatar
Philip Trettner committed
811
812
813
814
        mesh->add_or_get_halfedge(v0.idx, v1.idx), //
        mesh->add_or_get_halfedge(v1.idx, v2.idx), //
        mesh->add_or_get_halfedge(v2.idx, v3.idx), //
        mesh->add_or_get_halfedge(v3.idx, v0.idx), //
Philip Trettner's avatar
Philip Trettner committed
815
816
817
818
    };
    return mesh->handle_of(mesh->add_face(hs, 4));
}

819
inline face_handle face_collection::add(halfedge_handle h0, halfedge_handle h1, halfedge_handle h2) const
Philip Trettner's avatar
Philip Trettner committed
820
821
822
{
    halfedge_index hs[3] = {h0.idx, h1.idx, h2.idx};
    return mesh->handle_of(mesh->add_face(hs, 3));
823
824
}

825
inline face_handle face_collection::add(halfedge_handle h0, halfedge_handle h1, halfedge_handle h2, halfedge_handle h3) const
Philip Trettner's avatar
Philip Trettner committed
826
827
828
829
830
831
{
    halfedge_index hs[4] = {h0.idx, h1.idx, h2.idx, h3.idx};
    return mesh->handle_of(mesh->add_face(hs, 4));
}

template <size_t N>
832
inline face_handle face_collection::add(const vertex_handle (&v_handles)[N]) const
833
{
Philip Trettner's avatar
Philip Trettner committed
834
835
836
837
    halfedge_index hs[N];
    for (auto i = 0u; i < N; ++i)
        hs[i] = mesh->find_halfedge(v_handles[i].idx, v_handles[(i + 1) % N].idx);
    return mesh->handle_of(mesh->add_face(hs, N));
838
839
840
}

template <size_t N>
841
inline face_handle face_collection::add(const halfedge_handle (&half_loop)[N]) const
842
{
Philip Trettner's avatar
Philip Trettner committed
843
844
845
846
    halfedge_index hs[N];
    for (auto i = 0u; i < N; ++i)
        hs[i] = half_loop[i].idx;
    return mesh->handle_of(mesh->add_face(hs, N));
847
848
}

849
inline face_iterator face_collection::begin() const
850
851
852
853
{
    return mesh->faces_begin();
}

854
inline face_iterator face_collection::end() const
855
856
857
858
{
    return mesh->faces_end();
}

859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
inline int const_face_collection::size() const
{
    return mesh->size_faces();
}

inline face_iterator const_face_collection::begin() const
{
    return mesh->faces_begin();
}

inline face_iterator const_face_collection::end() const
{
    return mesh->faces_end();
}

874
inline int valid_face_collection::size() const
875
876
877
878
{
    return mesh->size_valid_faces();
}

879
inline valid_face_iterator valid_face_collection::begin() const
880
881
882
883
{
    return mesh->valid_faces_begin();
}

884
inline valid_face_iterator valid_face_collection::end() const
885
886
887
888
889
890
{
    return mesh->valid_faces_end();
}

// - Edges -

891
inline int edge_collection::size() const
892
893
894
895
{
    return mesh->size_edges();
}

896
inline void edge_collection::reserve(int capacity) const
897
898
899
900
{
    mesh->reserve_edges(capacity);
}

901
inline edge_handle edge_collection::add_or_get(vertex_handle v_from, vertex_handle v_to)
Philip Trettner's avatar
Philip Trettner committed
902
903
904
905
{
    return mesh->handle_of(mesh->add_or_get_edge(v_from.idx, v_to.idx));
}

906
inline edge_iterator edge_collection::begin() const
907
908
909
910
{
    return mesh->edges_begin();
}

911
inline edge_iterator edge_collection::end() const
912
913
914
915
{
    return mesh->edges_end();
}

916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
inline int const_edge_collection::size() const
{
    return mesh->size_edges();
}

inline edge_iterator const_edge_collection::begin() const
{
    return mesh->edges_begin();
}

inline edge_iterator const_edge_collection::end() const
{
    return mesh->edges_end();
}

931
inline int valid_edge_collection::size() const
932
933
934
935
{
    return mesh->size_valid_edges();
}

936
inline valid_edge_iterator valid_edge_collection::begin() const
937
938
939
940
{
    return mesh->valid_edges_begin();
}

941
inline valid_edge_iterator valid_edge_collection::end() const
942
943
944
945
946
947
{
    return mesh->valid_edges_end();
}

// - Halfedges -

948
inline int halfedge_collection::size() const
949
950
951
952
{
    return mesh->size_halfedges();
}

953
inline void halfedge_collection::reserve(int capacity) const
954
955
956
957
{
    mesh->reserve_halfedges(capacity);
}

958
inline halfedge_handle halfedge_collection::add_or_get(vertex_handle v_from, vertex_handle v_to)
Philip Trettner's avatar
Philip Trettner committed
959
960
961
962
{
    return mesh->handle_of(mesh->add_or_get_halfedge(v_from.idx, v_to.idx));
}

963
inline halfedge_iterator halfedge_collection::begin() const
964
965
966
967
{
    return mesh->halfedges_begin();
}

968
inline halfedge_iterator halfedge_collection::end() const
969
970
971
972
{
    return mesh->halfedges_end();
}

973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
inline int const_halfedge_collection::size() const
{
    return mesh->size_halfedges();
}

inline halfedge_iterator const_halfedge_collection::begin() const
{
    return mesh->halfedges_begin();
}

inline halfedge_iterator const_halfedge_collection::end() const
{
    return mesh->halfedges_end();
}

988
inline int valid_halfedge_collection::size() const
989
990
991
992
{
    return mesh->size_valid_halfedges();
}

993
inline valid_halfedge_iterator valid_halfedge_collection::begin() const
994
995
996
997
{
    return mesh->valid_halfedges_begin();
}

998
inline valid_halfedge_iterator valid_halfedge_collection::end() const
999
1000
{
    return mesh->valid_halfedges_end();