1474 (!opt.coarseningTargetSize || !(opt.coarseningReferenceSize > 0) ||
1475 !std::isfinite(opt.coarseningReferenceSize) || !(opt.normalVerticalToXY > 0) ||
1476 !std::isfinite(opt.normalVerticalToXY))) ||
1477 (opt.terrainToleranceForFootprint &&
1478 (!(opt.terrainTolerance > 0) || !opt.terrainError || !opt.terrainElevationAt))) {
1482 auto triangleBox = [&](
const Triangle &cell) {
1483 double x0 = m_pts[cell.v[0]].x(), x1 = x0, y0 = m_pts[cell.v[0]].y(), y1 = y0;
1484 for (
int k = 1; k < 3; ++k) {
1485 const auto p = m_pts[cell.v[k]];
1486 x0 = std::min(x0, p.x());
1487 x1 = std::max(x1, p.x());
1488 y0 = std::min(y0, p.y());
1489 y1 = std::max(y1, p.y());
1493 auto toleranceFor = [&](
const Triangle &cell) {
1494 const double value = opt.terrainToleranceForFootprint
1495 ? opt.terrainToleranceForFootprint(triangleBox(cell))
1496 : opt.terrainTolerance;
1497 if (value > 0 && std::isfinite(value))
1499 if (opt.terrainToleranceForFootprint)
1501 return std::numeric_limits<double>::quiet_NaN();
1503 const double theta = std::clamp(opt.minAngleDeg, 0.0, 60.0) * M_PI / 180.0;
1504 const double sinMin = std::sin(theta);
1508 theta > 0.0 ? 0.475 * std::sqrt((1.0 + std::cos(theta)) / (1.0 - std::cos(theta))) : 0.0;
1510 const double minEdge2 = opt.minEdge > 0.0 ? opt.minEdge * opt.minEdge : 0.0;
1511 auto tooShortToSplit = [&](
int a,
int b) {
1512 return minEdge2 > 0.0 &&
dist2(m_pts[a], m_pts[b]) < 4.0 * minEdge2;
1514 const bool terrain = opt.terrainError && opt.terrainElevationAt && opt.terrainTolerance > 0;
1517 const double terrainSpacing = std::max(opt.terrainMinSpacing, opt.minEdge);
1519 auto terrainKey = [&](
const Point &p) {
1520 return std::make_pair(std::int64_t(std::floor(p.x() / terrainSpacing)),
1521 std::int64_t(std::floor(p.y() / terrainSpacing)));
1523 auto indexTerrainVertex = [&](
int v) {
1525 terrainGrid[terrainKey(m_pts[v])].append(v);
1527 auto rebuildTerrainGrid = [&] {
1528 terrainGrid.clear();
1529 for (
int v = 0; v < m_pts.size(); ++v)
1530 indexTerrainVertex(v);
1532 auto terrainClear = [&](
const Point &p) {
1533 if (!(terrainSpacing > 0))
1535 const auto key = terrainKey(p);
1536 for (
int dy = -1; dy <= 1; ++dy)
1537 for (
int dx = -1; dx <= 1; ++dx) {
1539 terrainGrid.constFind(std::make_pair(key.first + dx, key.second + dy));
1540 if (it != terrainGrid.cend())
1542 if (
dist2(p, m_pts[v]) < terrainSpacing * terrainSpacing * (1.0 - 1e-12))
1548 rebuildTerrainGrid();
1549 m_terrainElevations.clear();
1550 auto &heights = m_terrainElevations;
1551 auto terrainError = [&](
int t,
Point *p) {
1552 const auto &T = m_tris[t];
1553 while (heights.size() < m_pts.size())
1554 heights.append(std::numeric_limits<double>::infinity());
1557 for (
int k = 0; k < 3; ++k) {
1558 const int v = T.v[k];
1560 if (std::isinf(heights[v])) {
1561 const double h = opt.terrainElevationAt(xy[k].x(), xy[k].y());
1562 heights[v] = std::isfinite(h) ? h : std::numeric_limits<double>::quiet_NaN();
1566 return opt.terrainError(xy, z, p);
1572 int v[3] = {-1, -1, -1};
1576 auto measure = [&](
int t,
Point *p) {
1577 const double e = terrainError(t, p);
1578 if (std::isfinite(e)) {
1579 if (measured.size() <= t)
1580 measured.resize(std::max<std::ptrdiff_t>(t + 1, measured.size() * 3 / 2));
1581 Measured &m = measured[t];
1582 for (
int k = 0; k < 3; ++k)
1583 m.v[k] = m_tris[t].v[k];
1589 bool repairing =
false;
1590 int repairBegin = 0;
1591 auto footprintCap = [&](
const Triangle &t) {
1592 if (!opt.maximumAreaForTriangle)
1594 const Point xy[3] = {m_pts[t.v[0]], m_pts[t.v[1]], m_pts[t.v[2]]};
1595 return opt.maximumAreaForTriangle(xy);
1599 auto badPoint = [&](
int t,
Point *out) {
1604 const Point &A = m_pts[T.
v[0]], &B = m_pts[T.
v[1]], &C = m_pts[T.
v[2]];
1605 const double cross = (B.x() - A.x()) * (C.y() - A.y()) - (B.y() - A.y()) * (C.x() - A.x());
1609 const int s = (l[0] <= l[1] && l[0] <= l[2]) ? 0 : (l[1] <= l[2] ? 1 : 2);
1612 const Point g = (A + B + C) / 3.0;
1613 const double h = opt.hAt(g.x(), g.y());
1619 if (!bad && opt.maximumAreaForTriangle) {
1620 const double cap = footprintCap(T);
1621 if (cap > 0 && .5 * cross > cap * (1 + 1e-10)) {
1626 if (!bad && repairing && opt.maximumAdjacentRatio >= 1) {
1627 for (
int neighbour : T.
adj) {
1628 if (neighbour < 0 || !m_tris[neighbour].alive)
1630 const auto &other = m_tris[neighbour];
1634 const double otherArea =
1635 std::abs(
orientPts(m_pts[other.v[0]], m_pts[other.v[1]], m_pts[other.v[2]])) *
1637 if (std::sqrt(.5 * cross / otherArea) > opt.maximumAdjacentRatio * (1 + 1e-10)) {
1643 if (!bad && opt.fixedNeighbourSize)
1644 for (
int k = 0; k < 3; ++k) {
1645 const double neighbour =
1646 opt.fixedNeighbourSize(T.
v[(k + 1) % 3], T.
v[(k + 2) % 3]);
1647 if (neighbour > 0 && std::sqrt(.5 * cross /
kEquilateralArea) / neighbour >
1648 opt.maximumAdjacentRatio * (1 + 1e-10)) {
1655 if (!bad && sinMin > 0.0 && l[s] >= minEdge2) {
1658 std::sqrt(l[(s + 1) % 3] * l[(s + 2) % 3]);
1659 if (sinA < sinMin && !exemptShortestEdge(T.
v[(s + 1) % 3], T.
v[(s + 2) % 3])) {
1664 if (!bad && terrain && (!opt.terrainWorstFirst || repairing)) {
1665 const double e = measure(t, out);
1666 if (std::isfinite(e) && e > toleranceFor(T)) {
1667 const double clearance = std::max(opt.terrainMinSpacing, opt.minEdge);
1671 clearance * clearance)
1680 const Point &P = m_pts[T.
v[(s + 1) % 3]], &Q = m_pts[T.
v[(s + 2) % 3]], &R = m_pts[T.
v[s]];
1681 const double bx = Q.x() - P.x(), by = Q.y() - P.y(), cx = R.x() - P.x(), cy = R.y() - P.y();
1682 const double d = 2.0 * (bx * cy - by * cx);
1685 const double b2 = bx * bx + by * by, c2 = cx * cx + cy * cy;
1686 double ux = (cy * b2 - by * c2) / d, uy = (bx * c2 - cx * b2) / d;
1688 const double mx = 0.5 * bx, my = 0.5 * by;
1689 const double ox = mx - offK * by, oy = my + offK * bx;
1690 if ((ox - mx) * (ox - mx) + (oy - my) * (oy - my) <
1691 (ux - mx) * (ux - mx) + (uy - my) * (uy - my)) {
1696 *out =
Point(P.x() + ux, P.y() + uy);
1697 return std::isfinite(out->x()) && std::isfinite(out->y());
1703 auto walkTo = [&](
int t,
const Point &p,
int *blockT,
int *blockE) {
1704 *blockT = *blockE = -1;
1706 const Point g = (m_pts[T0.
v[0]] + m_pts[T0.
v[1]] + m_pts[T0.
v[2]]) / 3.0;
1707 const int cap = 4 * m_tris.size() + 16;
1708 for (
int step = 0; step < cap; ++step) {
1711 for (
int i = 0; i < 3; ++i)
1712 o[i] = orient(T.
v[(i + 1) % 3], T.
v[(i + 2) % 3], p);
1713 if (o[0] >= 0.0 && o[1] >= 0.0 && o[2] >= 0.0)
1716 for (
int i = 0; i < 3 && exit < 0; ++i) {
1719 const double s1 =
orientPts(g, p, m_pts[T.
v[(i + 1) % 3]]);
1720 const double s2 =
orientPts(g, p, m_pts[T.
v[(i + 2) % 3]]);
1721 if ((s1 <= 0.0 && s2 >= 0.0) || (s1 >= 0.0 && s2 <= 0.0))
1725 for (
int i = 0; i < 3 && exit < 0; ++i)
1733 const int n = T.
adj[exit];
1734 if (n < 0 || !m_tris[n].alive)
1745 const double pd[2] = {p.x(), p.y()};
1747 while (!stack.isEmpty()) {
1748 const int t = stack.takeLast();
1750 for (
int k = 0; k < 3; ++k) {
1751 const int a = T.
v[(k + 1) % 3], b = T.
v[(k + 2) % 3];
1753 const Point &A = m_pts[a], &B = m_pts[b];
1754 if ((A.x() - p.x()) * (B.x() - p.x()) + (A.y() - p.y()) * (B.y() - p.y()) < 0.0)
1758 const int n = T.
adj[k];
1759 if (n < 0 || !m_tris[n].alive || seen.contains(n))
1764 const double pa[2] = {m_pts[N.
v[0]].x(), m_pts[N.
v[0]].y()};
1765 const double pb[2] = {m_pts[N.
v[1]].x(), m_pts[N.
v[1]].y()};
1766 const double pc[2] = {m_pts[N.
v[2]].x(), m_pts[N.
v[2]].y()};
1767 if (!(incircle(pa, pb, pc, pd) > 0.0))
1778 std::array<int, 32> heads, tails;
1782 auto enqueue = [&](
int t) {
1783 while (next.size() < m_tris.size())
1785 const auto &T = m_tris[t];
1786 if (!T.alive || next[t] != -2)
1789 if (opt.prioritizeQuality && sinMin > 0) {
1790 const auto &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
1791 const double cross =
1792 std::abs((b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()));
1794 const double denom = std::sqrt(std::max({l0 * l1, l1 * l2, l2 * l0}));
1796 bucket = std::clamp(
int(31 * cross / (denom * sinMin)), 0, 31);
1799 if (tails[bucket] >= 0)
1800 next[tails[bucket]] = t;
1805 auto dequeue = [&]() {
1806 for (
int k = 0; k < 32; ++k)
1807 if (heads[k] >= 0) {
1808 const int t = heads[k];
1817 m_triangleChanged = enqueue;
1821 auto publishProgress = [&] {
1822 if (opt.onProgress) {
1824 state.
stage = progressStage;
1825 state.
workingVertices = std::max<std::ptrdiff_t>(0, m_pts.size() - 3);
1829 opt.onProgress(state);
1834 auto queueEncroachedOf = [&](
int t) {
1836 for (
int k = 0; k < 3; ++k) {
1839 const int a = T.
v[(k + 1) % 3], b = T.
v[(k + 2) % 3];
1842 if (subsegmentEncroached(a, b))
1846 auto afterInsert = [&](
int v) {
1847 indexTerrainVertex(v);
1850 trianglesAround(v, &star);
1851 for (
int t : std::as_const(star))
1852 if (m_tris[t].alive) {
1854 queueEncroachedOf(t);
1860 if (repairing && rep.
inserted - repairBegin >= opt.maximumSizingRepairInsertions)
1864 if (opt.cancelled && opt.cancelled()) {
1870 auto drainSegments = [&]() {
1872 const std::uint64_t k = segQueue.takeLast();
1874 if (isFixedSub(a, b) || tooShortToSplit(a, b) || !
isConstrained(a, b) ||
1875 !subsegmentEncroached(a, b))
1877 const int v = splitSubsegment(a, b);
1885 for (
int i = 0; i < m_tris.size(); ++i)
1886 if (m_tris[i].alive) {
1888 queueEncroachedOf(i);
1899 auto tryInsert = [&](
int t,
Point p) {
1900 if (reason == 3 && !terrainClear(p))
1903 int blockT = -1, blockE = -1;
1904 int c = walkTo(t, p, &blockT, &blockE);
1909 edgeKey64(m_tris[blockT].v[(blockE + 1) % 3], m_tris[blockT].v[(blockE + 2) % 3]));
1911 cavityEncroached(c, p, &enc);
1912 if (!enc.isEmpty()) {
1916 for (std::uint64_t k : std::as_const(enc)) {
1918 if (stop || isFixedSub(a, b) || tooShortToSplit(a, b) || !
isConstrained(a, b))
1920 if (reason == 3 && !terrainClear((m_pts[a] + m_pts[b]) * 0.5))
1922 const int v = splitSubsegment(a, b);
1934 if (!repairing || reason != 1 || !opt.maximumAreaForTriangle)
1936 const auto &cell = m_tris[t];
1937 const auto a = m_pts[cell.v[0]], b = m_pts[cell.v[1]], cxy = m_pts[cell.v[2]];
1938 const double cap = footprintCap(cell);
1939 if (!(cap > 0) ||
orientPts(a, b, cxy) * .5 <= cap * (1 + 1e-10))
1941 const Point center = a + ((b - a) + (cxy - a)) / 3.;
1942 if (!std::isfinite(center.x()) || !std::isfinite(center.y()) ||
1943 std::min({dist2(center, a), dist2(center, b), dist2(center, cxy)}) < minEdge2 ||
1948 cavityEncroached(t, center, &enc);
1949 for (std::uint64_t key : enc)
1961 const int before = m_pts.size();
1963 if (v < 0 || v < before)
1968 else if (reason == 2)
1970 else if (reason == 3)
1977 auto drainQueue = [&]() {
1979 const int t = dequeue();
1982 if ((++examined & 4095) == 0) {
1984 if (opt.cancelled && opt.cancelled()) {
1990 if (!badPoint(t, &p))
1999 if (opt.smoothingPasses > 0 && (!terrain || opt.terrainWorstFirst) && !stop && !rep.
cancelled) {
2002 auto minAngleOf = [&](
int t) {
2003 const auto &T = m_tris[t];
2004 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2006 const double cross =
2007 std::abs((b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()));
2009 const int s = (l[0] <= l[1] && l[0] <= l[2]) ? 0 : (l[1] <= l[2] ? 1 : 2);
2010 return cross / std::sqrt(l[(s + 1) % 3] * l[(s + 2) % 3]);
2012 auto positive = [&](
int t) {
2013 const auto &T = m_tris[t];
2014 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2015 return (b.x() - a.x()) * (c.y() - a.y()) - (b.y() - a.y()) * (c.x() - a.x()) > 0.0;
2017 const int firstFree = m_superBase + 3;
2019 for (
int pass = 0; pass < opt.smoothingPasses; ++pass) {
2020 for (
int v = firstFree; v < m_pts.size(); ++v) {
2022 trianglesAround(v, &star);
2023 if (star.size() < 3)
2026 double wsum = 0, cx = 0, cy = 0, before = 1e300;
2027 for (
int t : std::as_const(star)) {
2028 const auto &T = m_tris[t];
2029 const int i = edgeIndex(t, v);
2032 T.constrained[(i + 2) % 3] || T.adj[(i + 1) % 3] < 0 ||
2033 T.adj[(i + 2) % 3] < 0) {
2037 const Point &a = m_pts[T.v[0]], &b = m_pts[T.v[1]], &c = m_pts[T.v[2]];
2038 const double area = 0.5 * std::abs((b.x() - a.x()) * (c.y() - a.y()) -
2039 (b.y() - a.y()) * (c.x() - a.x()));
2040 cx += area * (a.x() + b.x() + c.x()) / 3.0;
2041 cy += area * (a.y() + b.y() + c.y()) / 3.0;
2043 before = std::min(before, minAngleOf(t));
2045 if (fixed || !(wsum > 0.0))
2047 const Point old = m_pts[v];
2048 m_pts[v] =
Point(cx / wsum, cy / wsum);
2049 double after = 1e300;
2051 for (
int t : std::as_const(star)) {
2056 after = std::min(after, minAngleOf(t));
2058 if (!valid || !(after > before * (1.0 + 1e-9))) {
2062 for (
int t : std::as_const(star))
2063 if (m_tris[t].alive) {
2064 const int i = edgeIndex(t, v);
2076 if (terrain && opt.terrainWorstFirst && !stop && !rep.
cancelled) {
2080 rebuildTerrainGrid();
2087 auto worse = [](
const Candidate &a,
const Candidate &b) {
return a.e < b.e; };
2088 std::priority_queue<Candidate, std::vector<Candidate>,
decltype(worse)> heap(worse);
2089 auto consider = [&](
int t) {
2093 const Point &A = m_pts[T.
v[0]], &B = m_pts[T.
v[1]], &C = m_pts[T.
v[2]];
2094 if (!((B.x() - A.x()) * (C.y() - A.y()) - (B.y() - A.y()) * (C.x() - A.x()) > 0.0))
2097 const double e = measure(t, &p);
2098 const double localTolerance = toleranceFor(T);
2099 if (!std::isfinite(e) || !std::isfinite(localTolerance) || e <= localTolerance)
2101 const double clearance = std::max(opt.terrainMinSpacing, opt.minEdge);
2102 if (std::min({
dist2(p, A),
dist2(p, B),
dist2(p, C)}) <= clearance * clearance)
2104 heap.push({opt.terrainToleranceForFootprint ? e / localTolerance : e,
2106 {T.
v[0], T.
v[1], T.
v[2]},
2109 for (
int t = 0; t < m_tris.size(); ++t)
2112 m_triangleChanged = [&](
int t) {
2116 while (!heap.empty() && !stop) {
2117 const Candidate c = heap.top();
2120 if (!T.
alive || T.
v[0] != c.v[0] || T.
v[1] != c.v[1] || T.
v[2] != c.v[2])
2122 if ((++examined & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2128 if (!tryInsert(c.t, c.p))
2131 for (
int t : std::as_const(changed))
2134 m_triangleChanged = enqueue;
2139 m_triangleChanged = {};
2140 if (opt.coarsenPasses > 0 && !rep.
cancelled) {
2147 const double unknown = std::numeric_limits<double>::quiet_NaN();
2151 const auto freeSlots = std::max<std::ptrdiff_t>(0, m_pts.size() - m_superBase - 3);
2152 CoarseningQueue resolutionHeap(resolutionOrder && freeSlots ? m_pts.size() : 0,
2153 resolutionOrder ? freeSlots : 0);
2156 double x0 = std::numeric_limits<double>::infinity(), y0 = x0, x1 = -x0, y1 = -x0;
2158 for (
const auto &T : m_tris)
2163 x0 = std::min(x0, m_pts[v].x());
2164 y0 = std::min(y0, m_pts[v].y());
2165 x1 = std::max(x1, m_pts[v].x());
2166 y1 = std::max(y1, m_pts[v].y());
2168 auto key = [&](
int v,
unsigned scale) {
2171 ? unsigned(std::clamp((m_pts[v].x() - x0) / (x1 - x0), 0.0, 1.0) * scale)
2175 ? unsigned(std::clamp((m_pts[v].y() - y0) / (y1 - y0), 0.0, 1.0) * scale)
2183 while (heights.size() < m_pts.size())
2184 heights.append(std::numeric_limits<double>::infinity());
2186 for (
int v = 0; v < m_pts.size(); ++v)
2187 if (used[v] && std::isinf(heights[v]))
2188 pending.append({key(v, 65535), v});
2189 std::sort(pending.begin(), pending.end());
2190 for (
int i = 0; i < pending.size(); ++i) {
2191 if ((i & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2195 const int v = pending[i].second;
2196 heights[v] = opt.terrainElevationAt(m_pts[v].x(), m_pts[v].y());
2202 unsigned version, tile;
2204 auto less = [](
const Candidate &a,
const Candidate &b) {
2205 if (a.tile != b.tile)
2206 return a.tile > b.tile;
2207 return a.score != b.score ? a.score < b.score : a.v > b.v;
2209 std::priority_queue<Candidate, std::vector<Candidate>,
decltype(less)> heap(less);
2210 auto height = [&](
int v) {
2211 while (heights.size() < m_pts.size())
2212 heights.append(std::numeric_limits<double>::infinity());
2213 if (std::isinf(heights[v]))
2214 heights[v] = opt.terrainElevationAt(m_pts[v].x(), m_pts[v].y());
2217 auto score = [&](
int v,
const Vector<int> &star) {
2220 std::array<double, 3> sum{0, 0, 0};
2222 for (
int t : star) {
2223 const auto &T = m_tris[t];
2224 const Point b = m_pts[T.v[1]] - m_pts[T.v[0]],
2225 c = m_pts[T.v[2]] - m_pts[T.v[0]];
2226 const double scale = resolutionOrder ? opt.normalVerticalToXY : 1.;
2227 const double z = height(T.v[0]), bz = (height(T.v[1]) - z) * scale,
2228 cz = (height(T.v[2]) - z) * scale;
2229 if (!std::isfinite(z) || !std::isfinite(bz) || !std::isfinite(cz))
2231 std::array<double, 3> normal{b.y() * cz - bz * c.y(), bz * c.x() - b.x() * cz,
2232 b.x() * c.y() - b.y() * c.x()};
2233 const double length = std::hypot(normal[0], normal[1], normal[2]);
2236 for (
int k = 0; k < 3; ++k) {
2237 sum[k] += normal[k];
2238 normal[k] /= length;
2240 normals.append(normal);
2242 const double length = std::hypot(sum[0], sum[1], sum[2]);
2246 for (
const auto &n : normals)
2248 std::min(result, (n[0] * sum[0] + n[1] * sum[1] + n[2] * sum[2]) / length);
2251 const int limit = std::clamp(opt.coarsenPasses, 1, 10);
2252 auto queue = [&](
int v) {
2253 if (v < m_superBase + 3 || !
isVertexActive(v) || m_vertexSeg.contains(v) ||
2254 opt.protectedVertices.contains(v) ||
2255 (opt.protectedLocation && opt.protectedLocation(m_pts[v])) ||
2256 attempts[v] >= limit)
2259 if (terrain || resolutionOrder)
2260 trianglesAround(v, &star);
2261 const double flatness = score(v, star);
2262 if (!resolutionOrder) {
2263 heap.push({float(flatness), v, ++versions[v], unsigned(key(v, 31))});
2269 double totalArea = 0;
2271 for (
int t : star) {
2272 const auto &cell = m_tris[t];
2273 const auto bound = triangleBox(cell);
2274 box = first ? bound :
box.united(bound);
2277 .5 *
orientPts(m_pts[cell.v[0]], m_pts[cell.v[1]], m_pts[cell.v[2]]);
2280 double target = opt.coarseningTargetSize(
box);
2281 if (!std::isfinite(target) || target < 0) {
2286 target = opt.coarseningReferenceSize;
2287 const double actual =
2288 star.isEmpty() ? 0 : std::sqrt(totalArea / (star.size() *
kEquilateralArea));
2289 const double density = actual / target;
2290 const double importance =
2292 : std::numeric_limits<double>::infinity();
2293 const auto compact = [](
double value) {
2294 return float(std::min(value,
double(std::numeric_limits<float>::max())));
2297 {compact(importance), compact(density), v, unsigned(key(v, 31))});
2303 if ((v & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2310 const auto &a = m_pts[T.
v[0]], &b = m_pts[T.
v[1]], &c = m_pts[T.
v[2]];
2311 const double z = height(T.
v[0]);
2312 const double cross =
orientPts(a, b, c);
2314 ((p.x() - a.x()) * (c.y() - a.y()) - (p.y() - a.y()) * (c.x() - a.x())) / cross;
2316 ((b.x() - a.x()) * (p.y() - a.y()) - (b.y() - a.y()) * (p.x() - a.x())) / cross;
2317 return z + u * (height(T.
v[1]) - z) + w * (height(T.
v[2]) - z);
2319 while (!(resolutionOrder ? resolutionHeap.
empty() : heap.empty()) && !rep.
cancelled &&
2322 if (resolutionOrder) {
2323 const auto next = resolutionHeap.
pop();
2330 if ((!resolutionOrder && c.version != versions[v]) || !
isVertexActive(v))
2334 if (opt.cancelled && opt.cancelled()) {
2342 if (!prepareRemoval(v, &r))
2344 double shortest = std::numeric_limits<double>::infinity();
2345 for (
int t : r.star)
2346 for (
int k = 0; k < 3; ++k)
2347 shortest = std::min(shortest,
dist2(m_pts[m_tris[t].v[k]],
2348 m_pts[m_tris[t].v[(k + 1) % 3]]));
2349 bool accepted =
true;
2350 for (
const auto &T : r.replacement) {
2351 const Point &a = m_pts[T.
v[0]], &b = m_pts[T.
v[1]], &c = m_pts[T.
v[2]];
2352 const double cross =
orientPts(a, b, c);
2354 const int k = l[0] <= l[1] && l[0] <= l[2] ? 0 : l[1] <= l[2] ? 1 : 2;
2355 if (l[k] < shortest * (1 - 1e-12)) {
2360 if (l[k] >= minEdge2 &&
2361 cross / std::sqrt(l[(k + 1) % 3] * l[(k + 2) % 3]) < sinMin &&
2362 !exemptShortestEdge(T.
v[(k + 1) % 3], T.
v[(k + 2) % 3])) {
2367 const Point g = (a + b + c) / 3;
2368 const double h = opt.hAt ? opt.hAt(g.x(), g.y()) : 0;
2374 if (resolutionOrder) {
2375 const double target = opt.coarseningTargetSize(triangleBox(T));
2376 if (!std::isfinite(target) || target < 0) {
2381 if (target > 0 &&
static_cast<long double>(cross) * .5 >
2383 target * (1 + 1e-10)) {
2389 const double cap = footprintCap(T);
2390 if (cap > 0 && cross * .5 > cap * (1 + 1e-10)) {
2402 for (
const auto &T : r.replacement)
2403 if (orient(T.
v[0], T.
v[1], m_pts[v]) >= 0 &&
2404 orient(T.
v[1], T.
v[2], m_pts[v]) >= 0 &&
2405 orient(T.
v[2], T.
v[0], m_pts[v]) >= 0) {
2406 const double error = std::abs(plane(T, m_pts[v]) - height(v));
2407 if (!std::isfinite(error) || !std::isfinite(toleranceFor(T)) ||
2408 error > toleranceFor(T)) {
2414 for (
const auto &T : r.replacement) {
2421 for (
int t : r.star) {
2422 if (!std::isfinite(bounds[t])) {
2426 double difference = 0;
2427 for (
int q : m_tris[t].v) {
2428 const double d = std::abs(plane(T, m_pts[q]) - height(q));
2429 if (!std::isfinite(d)) {
2430 difference = unknown;
2433 difference = std::max(difference, d);
2435 if (!std::isfinite(difference)) {
2439 bound = std::max(bound, bounds[t] + difference);
2441 if (std::isfinite(bound) && bound <= toleranceFor(T) * (1 - 1e-10))
2446 for (
int k = 0; k < 3; ++k) {
2447 xy[k] = m_pts[T.
v[k]];
2448 z[k] = height(T.
v[k]);
2450 bound = opt.terrainErrorBound(xy, z);
2453 if (!std::isfinite(bound) || bound < 0 || !std::isfinite(toleranceFor(T)) ||
2454 bound > toleranceFor(T))
2456 newBounds.append(bound);
2463 commitRemoval(v, r);
2465 for (
int i = 0; i < r.star.size(); ++i) {
2466 const int t = r.star[i];
2467 if (t < measured.size())
2468 measured[t] = Measured{};
2470 bounds[t] = i < newBounds.size() ? newBounds[i] : unknown;
2472 for (
int q : r.ring)
2481 if (opt.sizingRepairPasses > 0 && !stop && !rep.
cancelled) {
2484 if (opt.maximumSizingRepairInsertions <= 0)
2487 m_triangleChanged = [&](
int t) {
2489 for (
int n : m_tris[t].adj)
2493 for (
int pass = 0; pass < std::clamp(opt.sizingRepairPasses, 0, 3) && !stop &&
2498 next.fill(-2, m_tris.size());
2501 for (
int t = 0; t < m_tris.size(); ++t) {
2502 if ((t & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2506 if (m_tris[t].alive)
2516 m_triangleChanged = {};
2521 if (terrain && opt.terrainFinalCheck && !rep.
cancelled) {
2524 for (
int t = 0; t < m_tris.size(); ++t) {
2525 const auto &T = m_tris[t];
2528 if ((t & 4095) == 0 && opt.cancelled && opt.cancelled()) {
2533 if (t < measured.size() && measured[t].v[0] == T.v[0] && measured[t].v[1] == T.v[1] &&
2534 measured[t].v[2] == T.v[2])
2538 e = terrainError(t, &p);
2540 if (!std::isfinite(e) || !std::isfinite(toleranceFor(T)))
2544 if (e > toleranceFor(T))