1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
// tiles.js — deep-zoom tile maths (pure): the scheme shared with map/tiles.py, target zoom, visible tiles, patch meshes
import { R_KM, toVec, project } from './geo.js';
export const TILE = 256;
export const MIN_TILE_Z = 5; // below this the base texture is as sharp as the tiles
export const MAX_TILE_Z = 16;
export const MESH_SEGS = 128; // 3D patches: one vertex per server height (map/tiles.py MESH_N = 129)
export const tileSpanDeg = z => 180 / 2 ** z;
export const pxKm = z => (2 * Math.PI * R_KM) / (2 ** (z + 1) * TILE);
export const tileKey = t => `${t.z}/${t.x}/${t.y}`;
export const DETAIL_TILES = 16; // the 3D fine grain repeats every 16 tiles (columns per zoom are a multiple of 16)
export const detailOrigin = t => [(t.x % DETAIL_TILES) * TILE, (t.y % DETAIL_TILES) * TILE]; // texels, small: float32-exact
export const parentTile = t => ({ z: t.z - 1, x: t.x >> 1, y: t.y >> 1 });
export function tileOf(lat, lon, z) {
const s = tileSpanDeg(z), nx = 2 ** (z + 1), ny = 2 ** z;
const x = ((Math.floor((lon + 180) / s) % nx) + nx) % nx;
const y = Math.min(ny - 1, Math.max(0, Math.floor((90 - lat) / s)));
return { z, x, y };
}
export function tileBounds({ z, x, y }) {
const s = tileSpanDeg(z);
return { west: -180 + x * s, east: -180 + (x + 1) * s, north: 90 - y * s, south: 90 - (y + 1) * s };
}
export function targetZoom(kmPerPx) {
if (!(kmPerPx > 0)) return 0;
const z = Math.ceil(Math.log2((2 * Math.PI * R_KM) / (kmPerPx * 2 * TILE)) - 1e-12);
return Math.max(0, Math.min(MAX_TILE_Z, z));
}
function ringTiles(t, ring) { // the tile first, then its neighbours (rows clipped at the poles, columns wrapped)
const nx = 2 ** (t.z + 1), ny = 2 ** t.z, out = [t];
for (let dy = -ring; dy <= ring; dy++) {
const y = t.y + dy;
if (y < 0 || y >= ny) continue;
for (let dx = -ring; dx <= ring; dx++) if (dx || dy) out.push({ z: t.z, x: (((t.x + dx) % nx) + nx) % nx, y });
}
return out;
}
export function tilesForPoints(points, z, ring = 1) {
const out = new Map();
for (const p of points) for (const u of ringTiles(tileOf(p.lat, p.lon, z), ring)) if (!out.has(tileKey(u))) out.set(tileKey(u), u);
return [...out.values()];
}
const children = t => [0, 1, 2, 3].map(i => ({ z: t.z + 1, x: 2 * t.x + (i & 1), y: 2 * t.y + (i >> 1) }));
// A quadtree cut for per-point zooms: every point wants its tile (and ring) at its own zoom. Any tile holding a
// wanted finer tile is split into all four children, so nothing overlaps; a split tile that was itself wanted
// (on screen) has all its children drawn, so nothing it covered goes missing. Order: first wanted first.
export function lodTiles(points, zs, ring = 1) {
const want = new Map(), split = new Set();
points.forEach((p, i) => {
if (!(zs[i] >= MIN_TILE_Z)) return;
for (const u of ringTiles(tileOf(p.lat, p.lon, zs[i]), ring)) {
const k = tileKey(u);
if (!want.has(k)) want.set(k, { t: u, n: want.size });
for (let a = parentTile(u); a.z >= MIN_TILE_Z; a = parentTile(a)) split.add(tileKey(a));
}
});
const out = [], roots = new Map();
const visit = (t, cov, n) => {
const k = tileKey(t), w = want.get(k), c = cov || !!w, m = w ? w.n : n;
if (split.has(k)) for (const ch of children(t)) visit(ch, c, m);
else if (c) out.push({ t, n: w ? w.n : n + 0.5 });
};
for (const { t } of want.values()) {
let r = t;
while (r.z > MIN_TILE_Z) r = parentTile(r);
roots.set(tileKey(r), r);
}
for (const r of roots.values()) visit(r, false, Infinity);
return out.sort((a, b) => a.n - b.n).map(o => o.t);
}
function grid(t, segs) { // rows north → south, columns west → east (same winding as geo.sphereMesh)
const b = tileBounds(t), n = segs + 1;
const lat = new Float64Array(n * n), lon = new Float64Array(n * n), uvs = new Float32Array(n * n * 2);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const k = i * n + j;
lat[k] = b.north - ((b.north - b.south) * i) / segs;
lon[k] = b.west + ((b.east - b.west) * j) / segs;
uvs[2 * k] = j / segs;
uvs[2 * k + 1] = 1 - i / segs;
}
}
const indices = new Uint32Array(segs * segs * 6);
let q = 0;
for (let i = 0; i < segs; i++) {
for (let j = 0; j < segs; j++) {
const a = i * n + j, c = a + n;
indices.set([a, c, c + 1, a, c + 1, a + 1], q);
q += 6;
}
}
return { b, lat, lon, uvs, indices };
}
const R_M = R_KM * 1000;
function edgeRing(segs) { // grid indices around the border, each once, in order (N, E, S, W)
const n = segs + 1, out = [];
for (let j = 0; j < segs; j++) out.push(j);
for (let i = 0; i < segs; i++) out.push(i * n + segs);
for (let j = segs; j > 0; j--) out.push(segs * n + j);
for (let i = segs; i > 0; i--) out.push(i * n);
return out;
}
export function globePatch(t, segs = 16, heights = null, exag = 1) { // positions relative to the patch centre
const g = grid(t, segs), N = g.lat.length;
const center = toVec((g.b.north + g.b.south) / 2, (g.b.west + g.b.east) / 2);
const edge = heights ? edgeRing(segs) : [], M = N + edge.length;
const spacingM = (((g.b.north - g.b.south) * Math.PI) / 180 / segs) * R_M;
const skirt = heights ? 2 * spacingM * Math.max(1, exag) : 0; // m: hides cracks against neighbours up to 2 zooms coarser
const positions = new Float32Array(M * 3), uvs = new Float32Array(M * 2);
const skirtFlags = heights ? new Float32Array(M).fill(1, N) : undefined; // 1: skirt (the cliff shading skips it)
const put = (k, lat, lon, m) => {
const v = toVec(lat, lon), r = 1 + m / R_M;
for (let i = 0; i < 3; i++) positions[3 * k + i] = v[i] * r - center[i];
};
for (let k = 0; k < N; k++) put(k, g.lat[k], g.lon[k], heights ? heights[k] * exag : 0);
uvs.set(g.uvs);
edge.forEach((k, i) => {
put(N + i, g.lat[k], g.lon[k], heights[k] * exag - skirt);
uvs[2 * (N + i)] = g.uvs[2 * k];
uvs[2 * (N + i) + 1] = g.uvs[2 * k + 1];
});
const indices = new Uint32Array(g.indices.length + edge.length * 6);
indices.set(g.indices);
for (let i = 0, q = g.indices.length; i < edge.length; i++, q += 6) {
const a = edge[i], b = edge[(i + 1) % edge.length], a2 = N + i, b2 = N + ((i + 1) % edge.length);
indices.set([a, a2, b2, a, b2, b], q);
}
return { center, positions, uvs, indices, skirt: skirtFlags };
}
export function gridHeight(t, heights, lat, lon, segs = MESH_SEGS) { // bilinear height inside a tile's mesh
const b = tileBounds(t), n = segs + 1, s = b.east - b.west;
const fx = ((((lon - b.west) % 360) + 360) % 360 / s) * segs, fy = ((b.north - lat) / (b.north - b.south)) * segs;
const j = Math.min(segs - 1, Math.max(0, Math.floor(fx))), i = Math.min(segs - 1, Math.max(0, Math.floor(fy)));
const u = Math.min(1, Math.max(0, fx - j)), v = Math.min(1, Math.max(0, fy - i)), h = (a, c) => heights[a * n + c];
return (1 - v) * ((1 - u) * h(i, j) + u * h(i, j + 1)) + v * ((1 - u) * h(i + 1, j) + u * h(i + 1, j + 1));
}
export function flatPatch(t, kind, segs = 16, zOff = 0) {
const g = grid(t, segs), N = g.lat.length, D = Math.PI / 180;
const c = project(kind, (g.b.north + g.b.south) / 2, (g.b.west + g.b.east) / 2);
const positions = new Float32Array(N * 3), ll = new Float32Array(N * 2);
for (let k = 0; k < N; k++) {
const p = project(kind, g.lat[k], g.lon[k]);
positions[3 * k] = p.x - c.x;
positions[3 * k + 1] = p.y - c.y;
ll[2 * k] = g.lat[k] * D;
ll[2 * k + 1] = g.lon[k] * D;
}
return { center: [c.x, c.y, zOff], positions, uvs: g.uvs, indices: g.indices, ll };
}
|
