Mesh.h 7.4 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
#include "Sketch.hpp"

11
#include "BoundaryConstraint.h"
12 13
#include "Edge.h"
#include "InsertionQueuer.h"
14
#include "Point.h"
15
#include "DartTriangle.h"
16

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

25
class Mesh { // TODO: Namespaces. Also, need to rename a bunch of things to be more consistent and clear w.r.t. how various arrays are accessed (e.g. by edge/dart index versus plain index)
26
public:
27 28
    Mesh(Sketch &s);

29
    friend class BoundaryConstraint;
30 31 32
    friend class CircumcenterQueuer;
    friend class MidpointQueuer;

33 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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
    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; };

79
    size_t size_dart_constraints() const {return DartConstraints.size(); };
80 81 82

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

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

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

87 88
    size_t size_contours() const { return Contours.size(); };

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

91 92
    void add_to_queue(std::unique_ptr<InsertionQueuer> ic) { Queue.push_back(std::move(ic)); };

93 94 95 96
    void create();

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

97
    // TODO: rename these methods something like, dart_constraint_from_edge_index, curve_from_edge_index
98
    DartConstraint const constraint(size_t ei) const { return DartConstraints[Edges[ei].Constraint]; };
99

100
    std::shared_ptr<Curve const> constraint_curve(size_t ei) const { return DartConstraints[Edges[ei].Constraint].constraint_curve(); };
101

102 103 104
    std::shared_ptr<BoundaryConstraint> boundary_constraint(std::shared_ptr<Curve const> const &c) const;

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

106 107 108 109
    DartTriangle const &triangle(size_t i) const { return Triangles[i]; };

    Point circumcenter(size_t ei) const;

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

112
    Point const &base(size_t i) const { return Points[node(i)]; };
113

114
    Point const &point(size_t i) const { return Points[i]; };
115

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

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

120
    Point const &tip(size_t i) const { return Points[node(next(i))]; };
121

122
    Point midpoint(size_t e) { return midpoint(Edges[e]); };
123

124 125 126
    Point midpoint(Edge const e) const {
        Point const &p0 = base(e);
        Point const &p1 = tip(e);
127

128 129 130 131 132 133 134 135
        return Point((p0.X + p1.X) / 2.0, (p0.Y + p1.Y) / 2.0);
    }

    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]; };
136

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

139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
    Edge const &edge_from_triangle_index(size_t i) const { return Edges[Triangles[i].Edge]; }; // TODO: Rename to triangle_dart

    Edge const &edge_from_triangle(DartTriangle const &dt) { return Edges[dt.Edge]; };

    std::array<size_t,3> nodes_from_triangle(DartTriangle const & dt) {
        Edge const &e = edge_from_triangle(dt);

        std::array<size_t,3> n;

        n[0] = e.Node;
        n[1] = next(e).Node;
        n[2] = prev(e).Node;

        return n;
    };
154 155 156 157 158 159 160 161

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

162 163 164 165 166
    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); };
167 168

protected:
169
    // TODO: There is some amount of redundancy here (e.g. There is one Curve for each BoundaryConstraint, Countours and Boundary also contain those curves
170 171 172 173 174 175
    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;
176 177 178
    std::vector<DartConstraint> DartConstraints;

    std::vector<std::shared_ptr<BoundaryConstraint>> BoundaryConstraints;
179

180
    std::vector<DartTriangle> Triangles;
181

182
    std::vector<std::unique_ptr<InsertionQueuer>> Queue;
183

184 185 186 187 188 189 190 191 192
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) {
193
            Edges.emplace_back(Edges.size());
194 195 196 197 198
            Edges.back().Constraint = 0;
        }
        return Edges.size();
    }

199 200 201 202 203
    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) {
204
        bc->add_dart_constraint(DartConstraints.size());
205 206 207 208
        DartConstraints.emplace_back(s0, s1, bc, DartConstraints.size());
        return DartConstraints.back();
    }

209
    Edge &new_edge(size_t p, size_t c, bool dir) {
210
        Edges.emplace_back(p, Edges.size(), c, dir);
211 212 213 214 215 216 217 218 219
        return Edges.back();
    }

    void create_boundary_polygon();

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

    void get_triangles();

220 221
    void insert_from_queue();

222 223 224 225 226 227
    void insert_internal_boundaries();

    void mark_triangles();

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

228 229
    void sort_constraints();

230 231 232 233 234 235 236 237 238 239
    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();

240
    std::vector<size_t> get_encroached_edges(Point const p, size_t edge);
241 242 243 244 245 246 247

    InsertPointResult insert_point(Point const p, size_t ei);

    InsertPointResult insert_midpoint(size_t ei);
};

#endif //OERSTED_MESH_H