Mesh.h 9.69 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
#ifndef OERSTED_MESH_H
#define OERSTED_MESH_H

#include "Sketch.hpp"
#include "Point.h"
#include "Edge.h"

#include <algorithm>
#include <fstream>
#include <numeric>
11
#include <set>
12
13
14
15
16
17
18
19
20

enum class LocateTriangleResult {
    Interior, Exterior, Boundary, Point // TODO: Enumerate cases in function when triangle is located by a point near the boundary
};

enum class InsertPointResult {
    Success, Midpoint, Duplicate, Failure
};

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
enum class AddToQueueResult {
    Circumcenter, Midpoint, Duplicate
};

class PointQueuer {
public:
    virtual ~PointQueuer() {};

    virtual void insert(Mesh &m) const = 0;
};

class BoundaryConstraint {
public:
    BoundaryConstraint(std::shared_ptr<Curve const> cc) : ConstraintCurve(cc) {};

    void add_dart(size_t d) { Darts.push_back(d); }; // TODO: Enforce uniqueness (std::set?)

    std::shared_ptr<Curve const> curve() const { return ConstraintCurve; };

protected:
    std::vector<size_t> Darts;
    std::shared_ptr<Curve const> ConstraintCurve;
};

class CircumcenterQueuer;
class MidpointQueuer;

48
49
class DartConstraint {
public:
50
    DartConstraint(double s0, double s1, std::shared_ptr<BoundaryConstraint> bc, size_t self) : S0{s0}, S1{s1}, Constraint{bc}, Self{self} {};
51

52
53
    std::shared_ptr<BoundaryConstraint> boundary_constraint() const { return Constraint; };
    std::shared_ptr<Curve const> constraint_curve() const { return Constraint->curve(); };
54
55
56

    double S0;
    double S1;
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

    size_t Self;

protected:
    std::shared_ptr<BoundaryConstraint> Constraint;
};

/* TODO: Reverse relationship between Edge and DartConstraint
 * TODO:    Have DartConstraint point to the Edge it constrains
 * TODO:    Edge will only contain a bool IsConstrained value in order to quickly test for encroachment
 * TODO:
class BoundaryConstraint {
public:
    BoundaryConstraint() : ConstraintCurve(nullptr) {};
    BoundaryConstraint(std::shared_ptr<Curve const> cc) : ConstraintCurve(cc) {};

    std::set<size_t> DartConstraints; // TODO: Or should Darts/(Edges) be stored instead of DartConstrants? Probably not because then Darts/Edges would have to hold more data
74
    std::shared_ptr<Curve const> ConstraintCurve;
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

    std::set<size_t> RefinementQueue;

    void add_to_queue(size_t d) {
        // TODO: Add dart constraints to queue for any mapped boundaries
        if (DartConstraint.count(d) == 1) {
            if (Uniform) {
                RefinementQueue = DartConstraints;
            } else {
                RefinementQueue.insert(d);
            }
        } else { // Don't do that, give warning
            throw;
        }
    }

    bool insert(Mesh &m) {
        for(size_t d : RefinementQueue) {
            Mesh.insert_midpoint(Mesh.DartConstraints[d].DartForward);
        }
        RefinementQueue = std::set<size_t>(); // empty
    };

    // TODO: Have two seperate methods
    // TODO:    One to add darts to a refinement queue (set with unique edges)
    // TODO:    An insert method which empties the refinement queue
    // TODO:    This is necessary because there is a possibility with encroached edges and boundary mappings that too many refinements will occur

    //something like std::vector<BoundaryMapping> Map to control, e.g. periodic boundary mapping
    //bool Uniform; to control boundary discretizations which are made of evenly spaced points in the parameter space
105
106
};

107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class DartConstraint {
public:
    DartConstraint() : S0(DBL_MAX), S1(DBL_MAX), BoundaryConstraints(SIZE_MAX), DartForward(SIZE_MAX), DartReverse(SIZE_MAX) {};
    DartConstraint(double s0, double s1) : DartForward(d), S0(s0), S1(s1) {};

    void add_to_queue(Mesh &m) { m.boundary_constraint(BoundaryConstraint).add_to_queue(m, Self)}; // TODO: Have dart refinement queue in Mesh class???

    double S0;
    double S1;

    size_t Self;

    size_t BoundaryConstraint;

    size_t DartForward; // TODO: Register Edge with DartConstraint on assignment
    size_t DartReverse; // TODO: Register Edge with DartConstraint on assignment
}
*/

126
127
class Mesh {
public:
128
129
130
131
132
    Mesh(Sketch &s);

    friend class CircumcenterQueuer;
    friend class MidpointQueuer;

133
134
135
136
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
190
    double MinimumElementQuality = 0.0;
    double MinimumElementSize = 0.0;
    double MaximumElementSize = DBL_MAX;

    bool are_intersecting(size_t ei, size_t ej) const;

    bool edges_are_valid() const;

    bool in_triangle(Point const p, size_t ei) const;

    bool is_constrained(size_t ei) const { return Edges[ei].Constraint != 0; };

    bool is_encroached(Point const p, size_t ei) const;

    bool is_locally_optimal(size_t ei) const;

    bool is_protruding(size_t ei) const;

    bool is_valid(size_t ei) const;

    bool orientation(size_t ei) const { return Edges[ei].Orientation; };

    bool refine();

    bool refine_once();

    double circumradius(size_t ei) const;

    double length(size_t ei) const;

    double shortest_edge_length(size_t ei) const;

    size_t next(size_t ei) const { return Edges[ei].Next; };

    size_t node(size_t ei) const { return Edges[ei].Node; };

    size_t node(Edge const e) const { return e.Node; };

    size_t num_points() const { return Points.size(); };

    size_t num_edges() const;

    size_t num_triangles() const { return Triangles.size(); };

    size_t prev(size_t ei) const { return Edges[ei].Prev; };

    size_t size_points() const { return Points.size(); };

    size_t size_edges() const { return Edges.size(); };

    size_t size_triangles() const { return Triangles.size(); };

    size_t twin(size_t ei) const { return Edges[ei].Twin; };

    void create();

    void save_as(std::string path, std::string file_name) const;

191
    DartConstraint const constraint(size_t ei) const { return DartConstraints[Edges[ei].Constraint]; };
192

193
    std::shared_ptr<Curve const> constraint_curve(size_t ei) const { return DartConstraints[Edges[ei].Constraint].constraint_curve(); };
194
195
196
197
198
199
200

    Point circumcenter(size_t ei) const;

    Point const base(Edge const e) const { return Points[e.Node]; };

    Point const base(size_t ei) const { return Points[node(ei)]; };

201
    Point const point(size_t i) const { return Points[i]; };
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

    Point const point(Edge const e) const { return Points[e.Node]; };

    Point const tip(Edge const e) const { return Points[next(e).Node]; };

    Point const tip(size_t ei) const { return Points[node(next(ei))]; };

    Edge const edge(size_t i) const { return Edges[i]; };

    Edge const next(Edge const e) const { return Edges[e.Next]; };

    Edge const prev(Edge const e) const { return Edges[e.Prev]; };

    Edge const twin(Edge const e) const { return Edges[e.Twin]; };

    Edge const triangle(size_t i) const { return Edges[Triangles[i]]; };

    LocateTriangleResult locate_triangle(Point const p, size_t &ei) const;

    LocateTriangleResult locate_triangle(Point const p) const {
        size_t ei = Edges.size() - 1;
        return locate_triangle(p, ei);
    };

226
227
228
229
230
    AddToQueueResult add_circumcenter_to_queue(size_t dart);

    AddToQueueResult add_point_to_queue(Point const p, size_t dart);

    AddToQueueResult add_point_to_queue(Point const p) { return add_point_to_queue(p, Edges.size() - 1); };
231
232
233
234
235
236
237
238

protected:
    std::shared_ptr<Contour const> Boundary;
    std::vector<std::shared_ptr<Curve const>> Curves;
    std::vector<std::shared_ptr<Contour const>> Contours;

    std::vector<Point> Points;
    std::vector<Edge> Edges;
239
240
241
    std::vector<DartConstraint> DartConstraints;

    std::vector<std::shared_ptr<BoundaryConstraint>> BoundaryConstraints;
242
243
244

    std::vector<size_t> Triangles;

245
246
    std::vector<std::unique_ptr<PointQueuer>> Queue;

247
248
249
250
251
252
253
254
255
private:
    bool find_attached(Point const p, size_t &ei);

    bool recursive_swap(size_t ei);

    bool swap(size_t ei);

    size_t new_edges(size_t num_new) {
        for (size_t i = 0; i != num_new; ++i) {
256
            Edges.emplace_back(Edges.size());
257
258
259
260
261
            Edges.back().Constraint = 0;
        }
        return Edges.size();
    }

262
263
264
265
266
267
268
269
270
271
    DartConstraint &new_dart_constraint(DartConstraint &dc) {
        return new_dart_constraint(dc.S0, dc.S1, dc.boundary_constraint());
    }

    DartConstraint &new_dart_constraint(double s0, double s1, std::shared_ptr<BoundaryConstraint> bc) {
        bc->add_dart(DartConstraints.size());
        DartConstraints.emplace_back(s0, s1, bc, DartConstraints.size());
        return DartConstraints.back();
    }

272
    Edge &new_edge(size_t p, size_t c, bool dir) {
273
        Edges.emplace_back(p, Edges.size(), c, dir);
274
275
276
277
278
279
280
281
282
        return Edges.back();
    }

    void create_boundary_polygon();

    void element_quality(std::vector<double> &radii, std::vector<double> &quality);

    void get_triangles();

283
284
    void insert_from_queue();

285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
    void insert_internal_boundaries();

    void mark_triangles();

    void refine_once(std::vector<size_t> index, std::vector<double> circumradius, std::vector<double> quality);

    void sort_permutation_ascending(std::vector<double> &value, std::vector<size_t> &index) const;

    void sort_permutation_descending(std::vector<double> &values, std::vector<size_t> &index) const;

    void split_edge(size_t ei);

    void split_encroached_edges();

    void triangulate_boundary_polygon();

301
    std::vector<size_t> get_encroached_edges(Point const p, size_t edge);
302
303
304
305
306
307

    InsertPointResult insert_point(Point const p, size_t ei);

    InsertPointResult insert_midpoint(size_t ei);
};

308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
class MidpointQueuer : public PointQueuer {
public:
    MidpointQueuer(size_t edge_to_split) : EdgeToSplit(edge_to_split) {};

    void insert(Mesh &m) const override {
        m.insert_midpoint(EdgeToSplit);
    }

protected:
    size_t EdgeToSplit;
};

class CircumcenterQueuer : public PointQueuer {
public:
    CircumcenterQueuer(Point const cc, size_t triangle) : Circumcenter(cc), Triangle(triangle) {};

    void insert(Mesh &m) const override {
        m.insert_point(Circumcenter, Triangle);
    }

protected:
    Point const Circumcenter;
    size_t Triangle;
};

333
#endif //OERSTED_MESH_H