Mesh.h 8.27 KB
Newer Older
1
2
3
4
5
6
#ifndef OERSTED_MESH_H
#define OERSTED_MESH_H

#include <algorithm>
#include <fstream>
#include <numeric>
7
#include <set>
8

9
10
11
12
13
14
#include "Sketch.hpp"

#include "Point.h"
#include "Edge.h"
#include "InsertionQueuer.h"

15
16
17
18
19
20
21
22
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
};

23
24
25
26
27
28
29
30
31
32
/* 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
33
    std::shared_ptr<Curve const> ConstraintCurve;
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

    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
64
65
};

66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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
}
*/

85
86
class Mesh {
public:
87
88
89
    Mesh(Sketch &s);

    friend class CircumcenterQueuer;
90

91
92
    friend class MidpointQueuer;

93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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
    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; };

139
    size_t size_dart_constraints() const {return DartConstraints.size(); };
140
141
142

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

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

145
146
147
148
149
150
151
152
    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;

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

155
    std::shared_ptr<Curve const> constraint_curve(size_t ei) const { return DartConstraints[Edges[ei].Constraint].constraint_curve(); };
156
157
158

    Point circumcenter(size_t ei) const;

159
160
    DartConstraint const dart_constraint(size_t i) { return DartConstraints[i]; };

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

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

165
    Point const point(size_t i) const { return Points[i]; };
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

    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);
    };

190
191
192
193
194
    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); };
195
196
197
198
199
200
201
202

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;
203
204
205
    std::vector<DartConstraint> DartConstraints;

    std::vector<std::shared_ptr<BoundaryConstraint>> BoundaryConstraints;
206
207
208

    std::vector<size_t> Triangles;

209
    std::vector<std::unique_ptr<InsertionQueuer>> Queue;
210

211
212
213
214
215
216
217
218
219
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) {
220
            Edges.emplace_back(Edges.size());
221
222
223
224
225
            Edges.back().Constraint = 0;
        }
        return Edges.size();
    }

226
227
228
229
230
    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) {
231
        bc->add_dart_constraint(DartConstraints.size());
232
233
234
235
        DartConstraints.emplace_back(s0, s1, bc, DartConstraints.size());
        return DartConstraints.back();
    }

236
    Edge &new_edge(size_t p, size_t c, bool dir) {
237
        Edges.emplace_back(p, Edges.size(), c, dir);
238
239
240
241
242
243
244
245
246
        return Edges.back();
    }

    void create_boundary_polygon();

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

    void get_triangles();

247
248
    void insert_from_queue();

249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
    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();

265
    std::vector<size_t> get_encroached_edges(Point const p, size_t edge);
266
267
268
269
270
271
272

    InsertPointResult insert_point(Point const p, size_t ei);

    InsertPointResult insert_midpoint(size_t ei);
};

#endif //OERSTED_MESH_H