Loading...
Searching...
No Matches
quadquality.hpp
Go to the documentation of this file.
1
21
22#ifndef MESHKIT_NATIVE_MESHQUADQUALITY_HPP
23#define MESHKIT_NATIVE_MESHQUADQUALITY_HPP
24
25#include <algorithm>
26#include <cmath>
27#include <limits>
28
29namespace meshkit::plan
30{
31
36 double minAngleDeg = 60.0;
37 double maxAngleDeg = 120.0;
38 double minScaledJacobian = 0.866;
39 double maxAspect = 2.0;
40};
41
48 double minAngleDeg = 0.0;
49 double maxAngleDeg = 0.0;
50 double scaledJacobian = 0.0;
51 double rectangularity = 0.0;
52 double aspect = 1.0;
53 double skew =
54 0.0;
55 double area = 0.0;
56 bool convex = false;
57};
58
77inline QuadQuality quadQuality(const Point2 &a, const Point2 &b, const Point2 &c, const Point2 &d)
78{
80 const Point2 p[4] = {a, b, c, d};
81 Point2 local[4];
82 double xScale = 0.0, yScale = 0.0;
83 for (int i = 0; i < 4; ++i) {
84 if (!std::isfinite(p[i].x()) || !std::isfinite(p[i].y()))
85 return {};
86 local[i] = p[i] - a;
87 if (!std::isfinite(local[i].x()) || !std::isfinite(local[i].y()))
88 return {};
89 xScale = std::max(xScale, std::abs(local[i].x()));
90 yScale = std::max(yScale, std::abs(local[i].y()));
91 }
92 if (!(xScale > 0.0) || !(yScale > 0.0))
93 return {};
94 // Local coordinates remove origin cancellation. Independent axis scales
95 // keep products finite even for representable highly anisotropic quads.
96 const auto areaCross = [&](int i, int j) {
97 return (local[i].x() / xScale) * (local[j].y() / yScale) -
98 (local[i].y() / yScale) * (local[j].x() / xScale);
99 };
100 const double area2 = areaCross(1, 2) + areaCross(2, 3);
101 if (area2 == 0.0 || !std::isfinite(area2))
102 return {};
103 const double orient = area2 > 0.0 ? 1.0 : -1.0;
104 // Rescale through exponents: neither xScale*yScale nor twice the final
105 // area needs to be representable as an intermediate value.
106 int areaExponent = 0, xExponent = 0, yExponent = 0;
107 const double areaMantissa = std::frexp(std::abs(area2), &areaExponent);
108 const double xMantissa = std::frexp(xScale, &xExponent);
109 const double yMantissa = std::frexp(yScale, &yExponent);
110 q.area =
111 std::scalbn(areaMantissa * xMantissa * yMantissa, areaExponent + xExponent + yExponent - 1);
112 if (!(q.area > 0.0) || !std::isfinite(q.area))
113 return {};
114
115 q.minAngleDeg = 360.0;
116 q.maxAngleDeg = 0.0;
117 q.scaledJacobian = 1.0;
118 q.convex = true;
119 double maxDev = 0.0;
120 double side[4];
121 for (int i = 0; i < 4; ++i) {
122 const Point2 e1 = p[(i + 3) % 4] - p[i], e2 = p[(i + 1) % 4] - p[i];
123 const double l1 = std::hypot(e1.x(), e1.y()), l2 = std::hypot(e2.x(), e2.y());
124 if (!(l1 > 0.0) || !(l2 > 0.0) || !std::isfinite(l1) || !std::isfinite(l2))
125 return {};
126 side[i] = l2;
127 const Point2 u1 = e1 / l1, u2 = e2 / l2;
128 // Normalize first; raw cross/dot products and length products may
129 // overflow or underflow even when the angular metrics are well-defined.
130 const double cross = std::clamp(u2.x() * u1.y() - u2.y() * u1.x(), -1.0, 1.0);
131 const double dot = std::clamp(u1.x() * u2.x() + u1.y() * u2.y(), -1.0, 1.0);
132 const double ang = std::atan2(std::abs(cross), dot) * 180.0 / pi;
133 const double sj = cross * orient;
134 if (sj <= 0.0)
135 q.convex = false;
136 q.scaledJacobian = std::min(q.scaledJacobian, sj);
137 q.minAngleDeg = std::min(q.minAngleDeg, ang);
138 q.maxAngleDeg = std::max(q.maxAngleDeg, ang);
139 maxDev = std::max(maxDev, std::abs(ang - 90.0));
140 }
141 q.rectangularity = std::clamp(1.0 - maxDev / 90.0, 0.0, 1.0);
142 const double s02 = 0.5 * side[0] + 0.5 * side[2];
143 const double s13 = 0.5 * side[1] + 0.5 * side[3];
144 const double lo = std::min(s02, s13), hi = std::max(s02, s13);
145 if (!(lo > 0.0))
146 return {};
147 q.aspect = hi / lo;
148 if (!std::isfinite(q.aspect))
149 return {};
150 const Point2 d1 = c - a, d2 = d - b;
151 const double ld1 = std::hypot(d1.x(), d1.y()), ld2 = std::hypot(d2.x(), d2.y());
152 if (!(ld1 > 0.0) || !(ld2 > 0.0) || !std::isfinite(ld1) || !std::isfinite(ld2))
153 return {};
154 const Point2 ud1 = d1 / ld1, ud2 = d2 / ld2;
155 q.skew = std::clamp(std::abs(ud1.x() * ud2.x() + ud1.y() * ud2.y()), 0.0, 1.0);
156 return q;
157}
158
172{
173 return quadQuality(vertices[t.v0].xy, vertices[t.v1].xy, vertices[t.v2].xy, vertices[t.v3].xy);
174}
175
176namespace quadquality_detail
177{
187inline bool validMetrics(const QuadQuality &q)
188{
189 // These checks also protect callers constructing QuadQuality manually.
190 return q.convex && std::isfinite(q.area) && q.area > 0.0 && std::isfinite(q.minAngleDeg) &&
191 std::isfinite(q.maxAngleDeg) && q.minAngleDeg > 0.0 && q.maxAngleDeg < 180.0 &&
192 q.minAngleDeg <= q.maxAngleDeg && std::isfinite(q.scaledJacobian) &&
193 q.scaledJacobian > 0.0 && q.scaledJacobian <= 1.0 && std::isfinite(q.rectangularity) &&
194 q.rectangularity >= 0.0 && q.rectangularity <= 1.0 && std::isfinite(q.aspect) &&
195 q.aspect >= 1.0 && std::isfinite(q.skew) && q.skew >= 0.0 && q.skew <= 1.0;
196}
197
205inline bool finiteBounds(const QuadQualityBounds &b)
206{
207 return std::isfinite(b.minAngleDeg) && std::isfinite(b.maxAngleDeg) &&
208 std::isfinite(b.minScaledJacobian) && std::isfinite(b.maxAspect);
209}
210} // namespace quadquality_detail
211
225inline bool quadAcceptable(const QuadQuality &q, const QuadQualityBounds &b)
226{
228 return false;
230 return false;
232 return false;
233 if (b.maxAspect > 0.0 && q.aspect > b.maxAspect)
234 return false;
235 return true;
236}
237
252inline double quadScore(const QuadQuality &q, const QuadQualityBounds &b)
253{
255 return 0.0;
256 const double aspectTerm =
257 (b.maxAspect > 0.0 && q.aspect > b.maxAspect) ? b.maxAspect / q.aspect : 1.0;
258 return std::clamp(q.scaledJacobian * q.rectangularity * aspectTerm, 0.0, 1.0);
259}
260
276inline double triangleScaledJacobian(const Point2 &a, const Point2 &b, const Point2 &c)
277{
278 const Point2 p[3] = {a, b, c};
279 double mn = 2.0;
280 double area2 = (b.x() - a.x()) * (c.y() - a.y()) - (c.x() - a.x()) * (b.y() - a.y());
281 const double orient = area2 >= 0.0 ? 1.0 : -1.0;
282 for (int i = 0; i < 3; ++i) {
283 const Point2 e1 = p[(i + 2) % 3] - p[i], e2 = p[(i + 1) % 3] - p[i];
284 const double l1 = std::hypot(e1.x(), e1.y()), l2 = std::hypot(e2.x(), e2.y());
285 if (l1 <= 0.0 || l2 <= 0.0)
286 return 0.0;
287 mn = std::min(mn, (e2.x() * e1.y() - e2.y() * e1.x()) * orient / (l1 * l2));
288 }
289 return std::min(mn, 1.0);
290}
291
303inline double cellCornerAngleDeg(const Vector<MeshVertex> &v, const MeshTriangle &t, int i)
304{
305 const int n = t.vertexCount();
306 const Point2 &prev = v[t.vertex((i + n - 1) % n)].xy;
307 const Point2 &cur = v[t.vertex(i)].xy;
308 const Point2 &next = v[t.vertex((i + 1) % n)].xy;
309 const Point2 e1 = prev - cur, e2 = next - cur;
310 return std::atan2(std::abs(e2.x() * e1.y() - e2.y() * e1.x()),
311 e1.x() * e2.x() + e1.y() * e2.y()) *
312 180.0 / pi;
313}
314
315} // namespace meshkit::plan
316
317#endif // MESHKIT_NATIVE_MESHQUADQUALITY_HPP
Point or displacement vector in the horizontal (XY) plane.
Definition geometry.hpp:21
constexpr double y() const noexcept
Y coordinate in XY plane units.
Definition geometry.hpp:36
constexpr double x() const noexcept
X coordinate in XY plane units.
Definition geometry.hpp:34
std::vector<T> with the QVector-style member names the CDT kernel and plan model use.
Definition storage.hpp:31
bool finiteBounds(const QuadQualityBounds &b)
Check every supplied quality threshold is finite.
Definition quadquality.hpp:205
bool validMetrics(const QuadQuality &q)
Check the internal finite/range/convexity invariants required before acceptance or scoring.
Definition quadquality.hpp:187
Planning algorithms on standard containers: quad patch planning and placement, size fields,...
QuadQuality quadQuality(const Point2 &a, const Point2 &b, const Point2 &c, const Point2 &d)
Measure one quadrilateral using cyclic corners and translation/scale-resistant planar arithmetic.
Definition quadquality.hpp:77
constexpr double pi
The constant pi as a double.
Definition planmodel.hpp:13
double triangleScaledJacobian(const Point2 &a, const Point2 &b, const Point2 &c)
Compute the minimum orientation-normalized corner sine of a triangle.
Definition quadquality.hpp:276
bool quadAcceptable(const QuadQuality &q, const QuadQualityBounds &b)
Apply inclusive hard angle/Jacobian/aspect limits to a valid convex metric record.
Definition quadquality.hpp:225
double cellCornerAngleDeg(const Vector< MeshVertex > &v, const MeshTriangle &t, int i)
Compute the unsigned corner angle of a triangle or quad.
Definition quadquality.hpp:303
double quadScore(const QuadQuality &q, const QuadQualityBounds &b)
Rank valid convex quads by Jacobian, rectangularity and a soft aspect penalty.
Definition quadquality.hpp:252
Mesh cell: a triangle, or a quadrilateral when v3 is nonnegative.
Definition planmodel.hpp:144
int vertex(int k) const
Corner index stored in slot k.
Definition planmodel.hpp:166
int v1
Second corner index.
Definition planmodel.hpp:154
int v2
Third corner index.
Definition planmodel.hpp:154
int v3
Fourth corner index of a quadrilateral; a negative value (default -1) marks a triangle.
Definition planmodel.hpp:154
int vertexCount() const
Return 4 for a quadrilateral and 3 for a triangle.
Definition planmodel.hpp:159
int v0
First corner index.
Definition planmodel.hpp:154
Acceptance bounds shared by pairing, cleanup, smoothing and the legacy tri-pair merge.
Definition quadquality.hpp:35
double minScaledJacobian
Smallest accepted scaled Jacobian (inclusive).
Definition quadquality.hpp:38
double maxAngleDeg
Largest accepted interior angle, degrees (inclusive).
Definition quadquality.hpp:37
double maxAspect
longest / shortest side (opposite-side means). <= 0 = unbounded.
Definition quadquality.hpp:39
double minAngleDeg
Smallest accepted interior angle, degrees (inclusive).
Definition quadquality.hpp:36
Metrics of one quadrilateral, as computed by quadQuality().
Definition quadquality.hpp:47
double aspect
mean(s0,s2) vs mean(s1,s3), >= 1.
Definition quadquality.hpp:52
bool convex
all four cross products share the sign of the total area.
Definition quadquality.hpp:56
double maxAngleDeg
Largest unsigned interior corner angle, degrees.
Definition quadquality.hpp:49
double minAngleDeg
Smallest unsigned interior corner angle, degrees.
Definition quadquality.hpp:48
double rectangularity
1 - max_i |theta_i - 90| / 90.
Definition quadquality.hpp:51
double area
positive finite area, evaluated in local coordinates.
Definition quadquality.hpp:55
double skew
|cos(angle between diagonals)|; zero for perpendicular diagonals (e.g. squares/rhombi),...
Definition quadquality.hpp:53
double scaledJacobian
min_i sin(theta_i), signed (negative = folded).
Definition quadquality.hpp:50