Picks the tile level for the screen and cuts a map picture into pieces that are each drawn with one affine transform.
How the precision is kept
This code only draws the background map on the screen. A picture is split into cells until one affine transform per cell is within a tolerance in screen pixels (0.25 unless the caller passes another) of the exact mapping at six test points, to a depth of 6. The tile level is the coarsest whose pixels are no larger than 1.5 screen pixels.
Calculations under this policy
3 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
The affine transform that carries three source points onto three destination points.
det = (u₁ − u₀)(v₂ − v₀) − (u₂ − u₀)(v₁ − v₀); a = ((x₁ − x₀)(v₂ − v₀) − (x₂ − x₀)(v₁ − v₀)) ÷ det
Cramer's rule on coordinate differences from the first point, in 64-bit. A determinant under 1e-18 in size (absolute) returns null. The result feeds the canvas transform.
basemap.js
lines 420 to 429
CadCraft 0.8.2
/** The affine (canvas order a b c d e f: x' = a·u + c·v + e, y' = b·u + d·v + f) mapping three source points onto three
* destination points. */
export function affineFrom3(s, d) {
const [[u0, v0], [u1, v1], [u2, v2]] = s, [[x0, y0], [x1, y1], [x2, y2]] = d;
const det = (u1 - u0) * (v2 - v0) - (u2 - u0) * (v1 - v0);
if (Math.abs(det) < 1e-18) return null;
const a = ((x1 - x0) * (v2 - v0) - (x2 - x0) * (v1 - v0)) / det, c = ((x2 - x0) * (u1 - u0) - (x1 - x0) * (u2 - u0)) / det;
const b = ((y1 - y0) * (v2 - v0) - (y2 - y0) * (v1 - v0)) / det, dd = ((y2 - y0) * (u1 - u0) - (y1 - y0) * (u2 - u0)) / det;
return [a, b, c, dd, x0 - a * u0 - c * v0, y0 - b * u0 - dd * v0];
}
Cells of a warped picture
32-bit, display only
The cells a picture is cut into so that each can be drawn with one affine transform.
split while max |affine(p) − exact(p)| > tol over the fourth corner, the middle and the four edge midpoints
The error is measured with Math.hypot in screen pixels at six points of the cell. Splitting stops at the depth limit or when a cell is 1 source pixel or less on a side, so the tolerance is a target and not a guarantee. A cell with a corner that cannot be mapped is left out.
basemap.js
lines 431 to 465
CadCraft 0.8.2
/** Splits a picture (w × h px; pixToScreen(u, v) → [x, y] or null exact) into cells, each drawn by one affine, until each
* affine is within `tol` screen px of the exact mapping at the cell's middle and edge midpoints. A cell whose corners
* cannot be mapped is left out. → [{ src: 4 corners [u, v], dst: 4 corners [x, y], m: affine }] */
export function planWarp(pixToScreen, w, h, { tol = 0.25, maxDepth = 6, minCells = 0 } = {}) {
const out = [];
const cache = new Map();
const P = (u, v) => { const k = u + ',' + v; let r = cache.get(k); if (r === undefined) { r = pixToScreen(u, v); r = r && Number.isFinite(r[0]) && Number.isFinite(r[1]) ? r : null; cache.set(k, r); } return r; };
const cell = (u0, v0, u1, v1, depth) => {
const c = [P(u0, v0), P(u1, v0), P(u1, v1), P(u0, v1)];
if (c.some((p) => !p)) { if (depth < maxDepth) split(u0, v0, u1, v1, depth); return; }
// the affine through three corners; its error at the fourth corner, the middle and the edge midpoints
const m = affineFrom3([[u0, v0], [u1, v0], [u0, v1]], [c[0], c[1], c[3]]);
let err = Infinity;
if (m) {
const um = (u0 + u1) / 2, vm = (v0 + v1) / 2;
err = 0;
for (const [u, v] of [[u1, v1], [um, vm], [um, v0], [u1, vm], [um, v1], [u0, vm]]) {
const e = P(u, v); if (!e) { err = Infinity; break; }
const a = applyAffine(m, u, v); err = Math.max(err, Math.hypot(a[0] - e[0], a[1] - e[1]));
}
}
if ((err > tol || depth < minCells) && depth < maxDepth && u1 - u0 > 1 && v1 - v0 > 1) { split(u0, v0, u1, v1, depth); return; }
if (!m) return;
// the fourth corner exact; the affine is the average of the two triangles' (the cell is drawn clipped to its quad)
const m2 = affineFrom3([[u1, v1], [u0, v1], [u1, v0]], [c[2], c[3], c[1]]);
const avg = m2 ? m.map((x, i) => (x + m2[i]) / 2) : m;
out.push({ src: [[u0, v0], [u1, v0], [u1, v1], [u0, v1]], dst: c, m: avg, err });
};
const split = (u0, v0, u1, v1, depth) => {
const um = (u0 + u1) / 2, vm = (v0 + v1) / 2;
cell(u0, v0, um, vm, depth + 1); cell(um, v0, u1, vm, depth + 1); cell(u0, vm, um, v1, depth + 1); cell(um, vm, u1, v1, depth + 1);
};
cell(0, 0, w, h, 0);
return out;
}
Tile level for the screen
32-bit, display only
Which level of a tile grid is drawn at the current zoom.
the coarsest level with res ≤ 1.5 × screen resolution
Levels are sorted from coarse to fine and the first whose resolution is at most 1.5 times the screen's is taken; if none is, the finest is used. It decides picture sharpness only.
basemap.js
lines 62 to 69
CadCraft 0.8.2
/** The matrix to use for a screen resolution `res` (system units per screen px): the coarsest whose pixels are no larger
* than 1.5 screen px — sharp enough, and never a flood of tiles. */
export function pickMatrix(grid, res) {
const ms = [...grid.matrices].sort((a, b) => b.res - a.res);
let pick = ms[0];
for (const m of ms) { pick = m; if (m.res <= res * 1.5) break; }
return pick;
}
In detail
Method
Recursive four-way split of the picture; each cell's affine comes from three of its corners and is averaged with the affine of the opposite triangle.
Number types
64-bit numbers; the results are handed to the canvas.
Tolerances
0.25 screen pixels by default for the affine error. A source triangle with |determinant| under 1e-18 gives no affine. Cells are not split below 1 source pixel or past the depth limit.
Approach: Display only
Computed to draw the screen, often in 32-bit on the graphics processor. No number a person reads, saves or exports comes from it.