properties.hh 10.9 KB
Newer Older
Philip Trettner's avatar
Philip Trettner committed
1
2
3
4
5
#pragma once

#include <glm/glm.hpp>

#include "../Mesh.hh"
6
#include "../fields.hh"
Philip Trettner's avatar
Philip Trettner committed
7
8
9
10
11
12
13
14
15
16
17

// Derived mesh properties, including:
// - valences
// - edge angles
// - face angles
// - face centroids
// - face area
// - mesh volume
// - face normal
// - vertex normal
// - curvature
Philip Trettner's avatar
Philip Trettner committed
18
// - topological properties
Philip Trettner's avatar
Philip Trettner committed
19
20
21
//
// Note: unary properties should be usable as free functions OR as index into handles
// e.g. valence(v) is the same as v[valence]
Philip Trettner's avatar
Philip Trettner committed
22
namespace polymesh
Philip Trettner's avatar
Philip Trettner committed
23
{
Philip Trettner's avatar
Philip Trettner committed
24
25
/// returns true if the vertex lies at a boundary
bool is_boundary(vertex_handle v);
Philip Trettner's avatar
Philip Trettner committed
26
bool is_vertex_boundary(vertex_handle v);
Philip Trettner's avatar
Philip Trettner committed
27
/// returns true if the face lies at a boundary
Philip Trettner's avatar
Philip Trettner committed
28
29
bool is_boundary(face_handle f);
bool is_face_boundary(face_handle f);
Philip Trettner's avatar
Philip Trettner committed
30
/// returns true if the edge lies at a boundary
Philip Trettner's avatar
Philip Trettner committed
31
32
bool is_boundary(edge_handle e);
bool is_edge_boundary(edge_handle e);
Philip Trettner's avatar
Philip Trettner committed
33
/// returns true if the half-edge lies at a boundary (NOTE: a half-edge is boundary if it has no face)
Philip Trettner's avatar
Philip Trettner committed
34
35
bool is_boundary(halfedge_handle h);
bool is_halfedge_boundary(halfedge_handle h);
Philip Trettner's avatar
Philip Trettner committed
36
37
38

/// returns true if the vertex has no neighbors
bool is_isolated(vertex_handle v);
Philip Trettner's avatar
Philip Trettner committed
39
bool is_vertex_isolated(vertex_handle v);
Philip Trettner's avatar
Philip Trettner committed
40
/// returns true if the edge has no neighboring faces
Philip Trettner's avatar
Philip Trettner committed
41
42
bool is_isolated(edge_handle e);
bool is_edge_isolated(edge_handle e);
Philip Trettner's avatar
Philip Trettner committed
43

Philip Trettner's avatar
Philip Trettner committed
44
/// returns the vertex valence (number of adjacent vertices)
Philip Trettner's avatar
Philip Trettner committed
45
int valence(vertex_handle v);
Philip Trettner's avatar
Philip Trettner committed
46

Philip Trettner's avatar
Philip Trettner committed
47
48
49
50
51
52
53
54
55
56
/// returns true iff face is a triangle
bool is_triangle(face_handle f);
/// returns true iff face is a quad
bool is_quad(face_handle f);

/// returns true iff all faces are triangles
bool is_triangle_mesh(Mesh const& m);
/// returns true iff all faces are quads
bool is_quad_mesh(Mesh const& m);

Philip Trettner's avatar
Philip Trettner committed
57
/// returns the area of the (flat) polygonal face
58
59
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar face_area(face_handle f, vertex_attribute<Vec3> const& position);
Philip Trettner's avatar
Philip Trettner committed
60
61

/// returns the center of gravity for a given (flat) polygonal face
62
63
template <class Vec3>
Vec3 face_centroid(face_handle f, vertex_attribute<Vec3> const& position);
Philip Trettner's avatar
Philip Trettner committed
64

65
/// returns the (CCW) oriented face normal (assumes planar polygon)
66
template <class Vec3>
67
68
69
70
71
Vec3 face_normal(face_handle f, vertex_attribute<Vec3> const& position);

/// returns the area of a given triangle
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar triangle_area(face_handle f, vertex_attribute<Vec3> const& position);
Philip Trettner's avatar
Philip Trettner committed
72
73

/// returns the center of gravity for a given triangle
74
75
template <class Vec3>
Vec3 triangle_centroid(face_handle f, vertex_attribute<Vec3> const& position);
Philip Trettner's avatar
Philip Trettner committed
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
105
106
107
108
109
110
111
112
113
114
115
116
/// returns the (CCW) oriented face normal
template <class Vec3>
Vec3 triangle_normal(face_handle f, vertex_attribute<Vec3> const& position);

/// returns a barycentric interpolation of a triangular face
template <class Vec3>
Vec3 bary_interpolate(face_handle f, Vec3 bary, vertex_attribute<Vec3> const& position);

/// returns the length of an edge
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar edge_length(edge_handle e, vertex_attribute<Vec3> const& position);

/// returns the length of an edge
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar edge_length(halfedge_handle h, vertex_attribute<Vec3> const& position);

/// returns the (non-normalized) vector from -> to
template <class Vec3>
Vec3 edge_vector(halfedge_handle h, vertex_attribute<Vec3> const& position);

/// returns the (normalized) vector from -> to (0 if from == to)
template <class Vec3>
Vec3 edge_dir(halfedge_handle h, vertex_attribute<Vec3> const& position);

/// calculates the angle between this half-edge and the next one
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar angle_to_next(halfedge_handle h, vertex_attribute<Vec3> const& position);

/// calculates the angle between this half-edge and the previous one
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar angle_to_prev(halfedge_handle h, vertex_attribute<Vec3> const& position);

/// sum of face angles at this vertex
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar angle_sum(vertex_handle v, vertex_attribute<Vec3> const& position);

/// difference between 2pi and the angle sum (positive means less than 2pi)
template <class Vec3, class Scalar = typename field_3d<Vec3>::Scalar>
Scalar angle_defect(vertex_handle v, vertex_attribute<Vec3> const& position);

Philip Trettner's avatar
Philip Trettner committed
117
118
/// ======== IMPLEMENTATION ========

Philip Trettner's avatar
Philip Trettner committed
119
inline bool is_boundary(vertex_handle v) { return v.is_boundary(); }
120
inline bool is_vertex_boundary(vertex_handle v) { return v.is_boundary(); }
Philip Trettner's avatar
Philip Trettner committed
121

122
123
inline bool is_boundary(face_handle f) { return f.is_boundary(); }
inline bool is_face_boundary(face_handle f) { return f.is_boundary(); }
Philip Trettner's avatar
Philip Trettner committed
124

125
126
inline bool is_boundary(edge_handle e) { return e.is_boundary(); }
inline bool is_edge_boundary(edge_handle e) { return e.is_boundary(); }
Philip Trettner's avatar
Philip Trettner committed
127

128
129
inline bool is_boundary(halfedge_handle h) { return h.is_boundary(); }
inline bool is_halfedge_boundary(halfedge_handle h) { return h.is_boundary(); }
Philip Trettner's avatar
Philip Trettner committed
130
131

inline bool is_isolated(vertex_handle v) { return v.is_isolated(); }
132
inline bool is_vertex_isolated(vertex_handle v) { return v.is_isolated(); }
Philip Trettner's avatar
Philip Trettner committed
133

134
135
inline bool is_isolated(edge_handle e) { return e.is_isolated(); }
inline bool is_edge_isolated(edge_handle e) { return e.is_isolated(); }
Philip Trettner's avatar
Philip Trettner committed
136

Philip Trettner's avatar
Philip Trettner committed
137
inline int valence(vertex_handle v) { return v.adjacent_vertices().size(); }
Philip Trettner's avatar
Philip Trettner committed
138

Philip Trettner's avatar
Philip Trettner committed
139
140
141
142
143
144
inline bool is_triangle(face_handle f) { return f.halfedges().size() == 3; }
inline bool is_quad(face_handle f) { return f.halfedges().size() == 5; }

inline bool is_triangle_mesh(Mesh const& m) { return m.faces().all(is_triangle); }
inline bool is_quad_mesh(Mesh const& m) { return m.faces().all(is_quad); }

145
146
template <class Vec3, class Scalar>
Scalar triangle_area(face_handle f, vertex_attribute<Vec3> const& position)
Philip Trettner's avatar
Philip Trettner committed
147
148
149
150
151
152
{
    auto h = f.any_halfedge();
    auto p0 = position[h.vertex_from()];
    auto p1 = position[h.vertex_to()];
    auto p2 = position[h.next().vertex_to()];

153
    return field_3d<Vec3>::length(field_3d<Vec3>::cross(p0 - p1, p0 - p2)) * field_3d<Vec3>::scalar(0.5f);
Philip Trettner's avatar
Philip Trettner committed
154
155
}

156
157
template <class Vec3>
Vec3 triangle_centroid(face_handle f, vertex_attribute<Vec3> const& position)
Philip Trettner's avatar
Philip Trettner committed
158
159
160
161
162
163
{
    auto h = f.any_halfedge();
    auto p0 = position[h.vertex_from()];
    auto p1 = position[h.vertex_to()];
    auto p2 = position[h.next().vertex_to()];

164
    return (p0 + p1 + p2) / field_3d<Vec3>::scalar(3);
Philip Trettner's avatar
Philip Trettner committed
165
166
}

167
template <class Vec3>
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
Vec3 face_normal(face_handle f, vertex_attribute<Vec3> const& position)
{
    auto c = face_centroid(f, position);
    auto e = f.any_halfedge();
    auto v0 = e.vertex_from()[position];
    auto v1 = e.vertex_to()[position];
    auto n = field_3d<Vec3>::cross(v0 - c, v1 - c);
    auto l = field_3d<Vec3>::length(n);
    return l == 0 ? field_3d<Vec3>::zero() : n / l;
}

template <class Vec3>
Vec3 triangle_normal(face_handle f, vertex_attribute<Vec3> const& position)
{
    auto e = f.any_halfedge();
    auto v0 = e.vertex_from()[position];
    auto v1 = e.vertex_to()[position];
    auto v2 = e.next().vertex_to()[position];
    auto n = field_3d<Vec3>::cross(v1 - v0, v2 - v0);
    auto l = field_3d<Vec3>::length(n);
    return l == 0 ? field_3d<Vec3>::zero() : n / l;
}

template <class Vec3, class Scalar>
Scalar face_area(face_handle f, vertex_attribute<Vec3> const& position)
Philip Trettner's avatar
Philip Trettner committed
193
{
194
    auto varea = field_3d<Vec3>::zero();
Philip Trettner's avatar
Philip Trettner committed
195

Philip Trettner's avatar
Philip Trettner committed
196
    auto h = f.any_halfedge();
Philip Trettner's avatar
Philip Trettner committed
197

Philip Trettner's avatar
Philip Trettner committed
198
199
200
201
202
203
204
    auto v0 = h.vertex_from();
    auto p0 = v0[position];

    auto p_prev = h.vertex_to()[position];
    h = h.next();

    do
Philip Trettner's avatar
Philip Trettner committed
205
    {
Philip Trettner's avatar
Philip Trettner committed
206
        auto p_curr = h.vertex_to()[position];
Philip Trettner's avatar
Philip Trettner committed
207

208
        varea += field_3d<Vec3>::cross(p_prev - p0, p_curr - p0);
Philip Trettner's avatar
Philip Trettner committed
209
210
211

        // circulate
        h = h.next();
Philip Trettner's avatar
Philip Trettner committed
212
        p_prev = p_curr;
Philip Trettner's avatar
Philip Trettner committed
213
    } while (h.vertex_to() != v0);
Philip Trettner's avatar
Philip Trettner committed
214

215
    return field_3d<Vec3>::length(varea) * 0.5f;
Philip Trettner's avatar
Philip Trettner committed
216
217
}

218
219
template <class Vec3>
Vec3 face_centroid(face_handle f, vertex_attribute<Vec3> const& position)
Philip Trettner's avatar
Philip Trettner committed
220
{
Philip Trettner's avatar
Philip Trettner committed
221
222
    // TODO: make correct for non-convex polygons!

223
224
    auto area = field_3d<Vec3>::scalar(0);
    auto centroid = field_3d<Vec3>::zero();
Philip Trettner's avatar
Philip Trettner committed
225

Philip Trettner's avatar
Philip Trettner committed
226
227
228
229
230
231
232
    auto h = f.any_halfedge();

    auto v0 = h.vertex_from();
    auto p0 = v0[position];

    auto p_prev = h.vertex_to()[position];
    h = h.next();
Philip Trettner's avatar
Philip Trettner committed
233

Philip Trettner's avatar
Philip Trettner committed
234
    do
Philip Trettner's avatar
Philip Trettner committed
235
    {
Philip Trettner's avatar
Philip Trettner committed
236
        auto p_curr = h.vertex_to()[position];
Philip Trettner's avatar
Philip Trettner committed
237

238
        auto a = field_3d<Vec3>::length(field_3d<Vec3>::cross(p_prev - p0, p_curr - p0));
Philip Trettner's avatar
Philip Trettner committed
239
240
        area += a;
        centroid += (p_prev + p_curr + p0) * a;
Philip Trettner's avatar
Philip Trettner committed
241

Philip Trettner's avatar
Philip Trettner committed
242
243
244
245
        // circulate
        h = h.next();
        p_prev = p_curr;
    } while (h.vertex_to() != v0);
Philip Trettner's avatar
Philip Trettner committed
246

Philip Trettner's avatar
Philip Trettner committed
247
    return centroid / (3.0f * area);
Philip Trettner's avatar
Philip Trettner committed
248
}
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
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
333
334
335
336
337
338
339
340
341
342

template <class Vec3, class Scalar>
Scalar edge_length(edge_handle e, vertex_attribute<Vec3> const& position)
{
    return field_3d<Vec3>::length(position[e.vertexA()] - position[e.vertexB()]);
}

template <class Vec3, class Scalar>
Scalar edge_length(halfedge_handle h, vertex_attribute<Vec3> const& position)
{
    return field_3d<Vec3>::length(position[h.vertex_from()] - position[h.vertex_to()]);
}

template <class Vec3>
Vec3 edge_vector(halfedge_handle h, vertex_attribute<Vec3> const& position)
{
    return position[h.vertex_to()] - position[h.vertex_from()];
}

template <class Vec3>
Vec3 edge_dir(halfedge_handle h, vertex_attribute<Vec3> const& position)
{
    auto d = position[h.vertex_to()] - position[h.vertex_from()];
    auto l = field_3d<Vec3>::length(d);
    if (l == 0)
        return field_3d<Vec3>::zero();
    return d / l;
}

template <class Vec3, class Scalar>
Scalar angle_to_next(halfedge_handle h, vertex_attribute<Vec3> const& position)
{
    auto v0 = h.vertex_from()[position];
    auto v1 = h.vertex_to()[position];
    auto v2 = h.next().vertex_to()[position];

    auto v01 = v0 - v1;
    auto v21 = v2 - v1;

    auto l01 = field_3d<Vec3>::length(v01);
    auto l21 = field_3d<Vec3>::length(v21);

    if (l01 == 0 || l21 == 0)
        return 0;

    auto ca = field_3d<Vec3>::dot(v01, v21) / (l01 * l21);
    return std::acos(ca);
}

template <class Vec3, class Scalar>
Scalar angle_to_prev(halfedge_handle h, vertex_attribute<Vec3> const& position)
{
    auto v0 = h.vertex_to()[position];
    auto v1 = h.vertex_from()[position];
    auto v2 = h.prev().vertex_from()[position];

    auto v01 = v0 - v1;
    auto v21 = v2 - v1;

    auto l01 = field_3d<Vec3>::length(v01);
    auto l21 = field_3d<Vec3>::length(v21);

    if (l01 == 0 || l21 == 0)
        return 0;

    auto ca = field_3d<Vec3>::dot(v01, v21) / (l01 * l21);
    return std::acos(ca);
}

template <class Vec3, class Scalar>
Scalar angle_sum(vertex_handle v, vertex_attribute<Vec3> const& position)
{
    Scalar sum = 0;
    for (auto h : v.outgoing_halfedges())
        if (!h.is_boundary())
            sum += angle_to_prev(h, position);
    return sum;
}

template <class Vec3, class Scalar>
Scalar angle_defect(vertex_handle v, vertex_attribute<Vec3> const& position)
{
    return 2 * M_PI - angle_sum(v, position);
}

template <class Vec3>
Vec3 bary_interpolate(face_handle f, Vec3 bary, vertex_attribute<Vec3> const& position)
{
    auto h = f.any_halfedge();
    auto v0 = h.vertex_to()[position];
    auto v1 = h.next().vertex_to()[position];
    auto v2 = h.next().next().vertex_to()[position];
    return v0 * bary[0] + v1 * bary[1] + v2 * bary[2];
}
Philip Trettner's avatar
Philip Trettner committed
343
}