Compare commits

..
Author SHA1 Message Date
Mazeyar Moeini FeizabadiandClaude Fable 5.2 6521fd2316 docs(changelog): add the #1705 fragment
Co-Authored-By: Claude Fable 5.2 <[email protected]>
2026-11-13 16:05:53 +01:00
Mazeyar Moeini FeizabadiandClaude Fable 5.2 346a08a42e perf(traffic): stop clipping and re-parsing the whole road set in one task
After the detail tiles arrived, every coarse road was clipped against every
detail tile for four regions, the composed set was parsed again although
each tile had been parsed as it streamed, and every coordinate asked the
ground floor service for its cell. A road wholly inside one region is now
answered from its extent, records already parsed in a pass are reused, and
the floor is read once per cell within a parse (when floors are per cell).

Co-Authored-By: Claude Fable 5.2 <[email protected]>
2026-11-13 16:03:19 +01:00
17 changed files with 645 additions and 653 deletions

No files matched your search

+4
View File
@@ -0,0 +1,4 @@
- Cut the stutter while zooming and panning with Street Traffic on in dense
cities. Coarse roads are no longer clipped against every detail tile in one
task, roads already parsed in a load are not parsed again, and ground floors
are read once per cell (mazy1998, #1705).
@@ -1,4 +0,0 @@
- Make a whole-globe view of Live Flights about three times faster on a slow
CPU. Aircraft at cruise altitude no longer ask for the ground under them on
every pass, and a ground floor read no longer formats numbers into text
(mazy1998, #1708).
+1 -7
View File
@@ -2949,13 +2949,7 @@ visits to one place share a key but does not bound how many distinct places a
session visits, and the cache previously had no eviction, so a long session
retained every coordinate it ever resolved. Eviction is least-recently-used:
a consumer read, including a warm hit in a batch lookup, promotes its entry, so
the cell being watched is not dropped for having been resolved early. A
synchronous read (`cachedEllipsoidalGround`, `cachedRealEllipsoidalGround`)
promotes its entry only once half the bound's worth of stores and promotions
have passed since the entry was last newest, so an entry read at least that
often is still never evicted while the per-frame floor reads no longer rewrite
the cache; those reads find entries through a numeric key and format no
strings. The bound sits far above a city-scale session, so
the cell being watched is not dropped for having been resolved early. The bound sits far above a city-scale session, so
normal use never evicts and issues no additional proxy requests. A batch's
results are assembled from what that call resolved or found warm, so eviction
during a large batch cannot report one of its points as unresolved. Re:Earth and
-34
View File
@@ -311,10 +311,6 @@ export const COAST_FLOOR_LIFT_M = 1.5;
*/
export function floorCoastedPosition(position, cachedGroundFloor) {
if (typeof cachedGroundFloor !== 'function') return position;
// Most coasting contacts are at cruise, and this runs for each of them on
// every fleet pass. One above COAST_FLOOR_CEILING_M cannot be lifted by any
// ground, so it needs neither the geodetic conversion nor the floor read.
if (clearOfAllGround(position)) return position;
const carto = Cesium.Cartographic.fromCartesian(
position,
Cesium.Ellipsoid.WGS84,
@@ -338,36 +334,6 @@ export function floorCoastedPosition(position, cachedGroundFloor) {
const _coastCarto = new Cesium.Cartographic();
/**
* @constant {number} No ground reaches this height above the ellipsoid:
* Everest's summit is about 8,821 m (8,849 m above a geoid that sits 28 m
* below the ellipsoid there).
*/
export const COAST_FLOOR_CEILING_M = 9000;
const _oneOverRadiiSq = Cesium.Ellipsoid.WGS84.oneOverRadiiSquared;
const COAST_CLEAR_SCALED_SQ =
(1 + COAST_FLOOR_CEILING_M / Cesium.Ellipsoid.WGS84.minimumRadius) ** 2;
/**
* Whether a position is certainly more than COAST_FLOOR_CEILING_M above the
* ellipsoid, from three multiplications. Scale the axes so the ellipsoid is
* the unit sphere: a point h metres up its surface normal is then at most
* 1 + h / (polar radius) from the centre, so one further out than
* 1 + ceiling / (polar radius) is above the ceiling. At the equator this
* answers yes from about 30 m above the ceiling; at the poles, from the
* ceiling itself.
* @param {Cesium.Cartesian3} position
* @returns {boolean}
*/
function clearOfAllGround(position) {
return (
position.x * position.x * _oneOverRadiiSq.x +
position.y * position.y * _oneOverRadiiSq.y +
position.z * position.z * _oneOverRadiiSq.z >
COAST_CLEAR_SCALED_SQ
);
}
/**
* Seconds to coast past the last report: the elapsed time, bounded by the
* source's coast limit and STALE_COAST_MAX_SEC; none for a contact that
-77
View File
@@ -10,7 +10,6 @@ import {
liftRepeatedGroundFix, synthesizeForwardKinematicsFix,
projectGroundArcLatLon, corridorPathLatLon,
COURSE_TRACK_ONLY_MPS, COURSE_CHORD_ONLY_MPS, COURSE_MIN_DPS, TURN_MIN_SPEED_MPS,
floorCoastedPosition, COAST_FLOOR_CEILING_M, COAST_FLOOR_LIFT_M,
} from './motionModel.js';
const AUSTIN = { lat: 30.2672, lon: -97.7431, alt: 9000 };
@@ -342,79 +341,3 @@ test('corridorPathLatLon returns nothing without a display position', () => {
extrapolating: true, displayLat: NaN, displayLon: -97.66, courseDeg: 0, speedMps: 10, lookaheadSec: 60,
}), []);
});
/** floorCoastedPosition as it was before the cruise skip: always converts and reads. */
function floorCoastedReference(position, groundAt) {
const carto = Cesium.Cartographic.fromCartesian(position);
if (!carto) return position;
const ground = groundAt(
Cesium.Math.toDegrees(carto.latitude),
Cesium.Math.toDegrees(carto.longitude),
);
if (!Number.isFinite(ground) || carto.height >= ground + COAST_FLOOR_LIFT_M)
return position;
return Cesium.Cartesian3.fromRadians(carto.longitude, carto.latitude, ground + COAST_FLOOR_LIFT_M);
}
test('a coasting contact above any terrain is not looked up against the ground', () => {
let reads = 0;
const ground = () => {
reads += 1;
return 8821; // Everest's summit, the highest floor there is
};
// Just over the ceiling and at cruise, from pole to equator.
for (let lat = -90; lat <= 90; lat += 7.5) {
for (const lon of [0, 86.925, -78.8, 179.9]) {
for (const height of [COAST_FLOOR_CEILING_M + 35, 10_000, 12_500, 40_000]) {
const position = Cesium.Cartesian3.fromDegrees(lon, lat, height);
const before = Cesium.Cartesian3.clone(position);
assert.equal(floorCoastedPosition(position, ground), position);
assert.ok(Cesium.Cartesian3.equals(position, before));
}
}
}
assert.equal(reads, 0);
});
test('below the ceiling a coast is floored exactly as before', () => {
// Terrain that rises under the coast, known in some places and not others.
const ground = (lat, lon) => (Math.floor(lat * 10 + lon) % 3 === 0 ? null : 1500 + ((lat * 7 + lon * 3) % 900));
let lifted = 0;
let checked = 0;
for (let lat = -89; lat <= 89; lat += 5.5) {
for (let lon = -180; lon < 180; lon += 17) {
for (const height of [-40, 0, 800, 1499, 1501.4, 2399, 2402, 5000, 8990, 9000, 9010, 11_000, 30_000]) {
const position = Cesium.Cartesian3.fromDegrees(lon, lat, height);
const expected = floorCoastedReference(Cesium.Cartesian3.clone(position), ground);
const actual = floorCoastedPosition(position, ground);
assert.ok(
Cesium.Cartesian3.equals(actual, expected),
`coast at ${lat}, ${lon}, ${height} m`,
);
checked += 1;
if (!Cesium.Cartesian3.equals(expected, Cesium.Cartesian3.fromDegrees(lon, lat, height))) lifted += 1;
}
}
}
assert.ok(lifted > 500, `${lifted} of ${checked} coasts were lifted onto the ground`);
});
test('nothing at or below the ceiling skips the ground', () => {
let reads = 0;
const ground = () => {
reads += 1;
return null;
};
let asked = 0;
for (let lat = -90; lat <= 90; lat += 2.5) {
for (const height of [-400, 0, 4000, 8821, COAST_FLOOR_CEILING_M - 1, COAST_FLOOR_CEILING_M]) {
floorCoastedPosition(Cesium.Cartesian3.fromDegrees(33, lat, height), ground);
asked += 1;
}
}
assert.equal(reads, asked);
});
test('the ceiling clears the highest ground with room to spare', () => {
assert.ok(COAST_FLOOR_CEILING_M > 8849 + 100);
});
+3 -1
View File
@@ -1,6 +1,7 @@
import { roadIdentity } from './retention.js';
import * as Cesium from 'cesium';
import {
floorCellReader,
prepareRoadSurfaces,
roadHeightStations,
trafficSurfaceReady,
@@ -301,6 +302,7 @@ export function createFlow({ state: layerState, services, parts, source }) {
}
}
if (depthHeight !== undefined) layerState._viewHeightEstimate = depthHeight;
const floorAt = floorCellReader(services.ground);
for (const road of roads) {
road.key ||= roadIdentity(road);
const prepared = !refining && preparedRoads.get(road.key);
@@ -319,7 +321,7 @@ export function createFlow({ state: layerState, services, parts, source }) {
);
for (let i = 0; i < road.coords.length; i++) {
const [lon, lat] = road.coords[i];
const floor = services.ground?.cachedGroundFloor?.(lat, lon);
const floor = floorAt(lat, lon);
const height =
Number.isFinite(floor) && Math.abs(floor) <= 9000
? Math.max(floor, layerState._viewHeightEstimate)
+3 -3
View File
@@ -39,10 +39,10 @@ export function createTrafficLayer({ services, source }) {
parts.controls = createControls(context);
parts.lifecycle = createLifecycle(context);
state._parseRoads = TRAFFIC_TIMING_ENABLED
? (data, trace) =>
? (data, trace, parsedBySource) =>
trace
? parts.timing.parseRoadsTimed(data, trace)
: parts.model.parseRoads(data)
? parts.timing.parseRoadsTimed(data, trace, parsedBySource)
: parts.model.parseRoads(data, trace, parsedBySource)
: parts.model.parseRoads;
state._loadRoadsForBounds = TRAFFIC_TIMING_ENABLED
+7 -1
View File
@@ -348,11 +348,16 @@ export function createIngestion({
layerState._retainedPreview = false;
layerState._detailRoadsReady = false;
let paintRevision = 0;
// The snapshot that ends a pass replaces the streamed roads with the
// composed set, which is mostly the tile records already parsed and
// drawn. Remembering those per pass means only the records new to that
// snapshot (the clipped coarse roads) are parsed, not the whole set again.
let parsedBySource = new WeakMap();
const onTile = (data, passSignal, preview) => {
if (generation !== layerState._loadGeneration || passSignal.aborted)
return;
const start = performance.now();
const parsed = layerState._parseRoads(data, trace);
const parsed = layerState._parseRoads(data, trace, parsedBySource);
phaseTiming('parse', start, { roads: parsed.length, incremental: true });
if (data.replace) streamed = parsed;
else streamed.push(...parsed);
@@ -531,6 +536,7 @@ export function createIngestion({
if (altitude > FAST_FETCH_ALTITUDE) return;
streamed = [];
parsedBySource = new WeakMap();
majorPass = false;
// Detailed pass: fetch the full road graph (tertiary, residential, etc.)
console.log(`[Data:Traffic] Full fetch local roads [${cacheKey}]`);
+18 -4
View File
@@ -1,5 +1,5 @@
import * as Cesium from 'cesium';
import { roadSurfaceChunks } from './surface.js';
import { floorCellReader, roadSurfaceChunks } from './surface.js';
import { t, translateKnown } from '../../i18n/index.js';
import {
flowDensityMult,
@@ -13,22 +13,35 @@ import {
} from './policy.js';
export function createModel({ state: layerState, services, parts, source }) {
/** Build scene waypoints from source records; thinning and terrain remain rendering policy. */
function parseRoads(roadData) {
/**
* Build scene waypoints from source records; thinning and terrain remain rendering policy.
*
* `parsedBySource` (source record → its parsed roads) is filled as records
* are parsed, and a record already in it is answered from it.
*/
function parseRoads(roadData, _trace, parsedBySource) {
if (!roadData || !roadData.roads) {
return [];
}
const roads = [];
const floorAt = floorCellReader(services.ground);
for (const road of roadData.roads) {
if (!road.coordinates || road.coordinates.length < 2) continue;
// A replacing snapshot repeats records this load already parsed.
const known = parsedBySource?.get(road);
if (known) {
for (const parsed of known) roads.push(parsed);
continue;
}
const first = roads.length;
for (const coords of roadSurfaceChunks(road.coordinates)) {
const type = road.type;
const oneway = road.oneway;
// Pre-compute Cartesian3 waypoints (lon, lat, height) for fast lerp animation
const waypoints = coords.map(([lng, lat]) => {
const floor = services.ground?.cachedGroundFloor?.(lat, lng);
const floor = floorAt(lat, lng);
const h =
(Number.isFinite(floor) && Math.abs(floor) <= 9000
? floor
@@ -60,6 +73,7 @@ export function createModel({ state: layerState, services, parts, source }) {
flow: road.flow || null,
});
}
parsedBySource?.set(road, roads.slice(first));
}
return roads;
+444
View File
@@ -0,0 +1,444 @@
import test from 'node:test';
import assert from 'node:assert/strict';
import * as Cesium from 'cesium';
import { createTrafficSource, outsideDetailTiles } from './source.js';
import { createIngestion } from './ingestion.js';
import { createModel } from './model.js';
import { floorCellReader, roadSurfaceChunks } from './surface.js';
import { DOT_HEIGHT_OFFSET } from './policy.js';
import { clipTileLine } from '../../sources/openFreeMap.js';
import { tileToBBox } from '../../data/tomtomTiles.js';
// The clip as it was before the extent shortcut: every road against the four
// regions around every tile. The shortcut must return exactly this.
function clipEveryRoadAgainstEveryTile(roads, tiles) {
return roads.flatMap((road) => {
let lines = [road.coordinates];
for (const tile of tiles) {
const box = tileToBBox(tile.z, tile.x, tile.y);
const regions = [
{ west: -180, east: box.west, south: -85, north: 85 },
{ west: box.east, east: 180, south: -85, north: 85 },
{ west: box.west, east: box.east, south: -85, north: box.south },
{ west: box.west, east: box.east, south: box.north, north: 85 },
];
lines = lines.flatMap((line) =>
regions.flatMap((region) => clipTileLine(line, region)),
);
}
return lines.map((coordinates) => ({ ...road, coordinates }));
});
}
function seeded(seed) {
let state = seed >>> 0;
return () => {
state = (Math.imul(state, 1664525) + 1013904223) >>> 0;
return state / 2 ** 32;
};
}
function tileBlock(x, y, size = 4) {
const tiles = [];
for (let dx = 0; dx < size; dx++)
for (let dy = 0; dy < size; dy++)
tiles.push({ z: 14, x: x + dx, y: y + dy });
return tiles;
}
/** Roads in and around a tile block: wandering, straight, tiny, and on tile edges. */
function roadsAround(tiles, random, count = 400) {
const boxes = tiles.map((tile) => tileToBBox(tile.z, tile.x, tile.y));
const west = Math.min(...boxes.map((box) => box.west)),
east = Math.max(...boxes.map((box) => box.east)),
south = Math.min(...boxes.map((box) => box.south)),
north = Math.max(...boxes.map((box) => box.north));
const width = east - west,
height = north - south;
const roads = [];
for (let i = 0; i < count; i++) {
const step = i % 7 === 0 ? 0.00002 : i % 3 === 0 ? 0.01 : 0.002;
let lon = west - width / 2 + random() * width * 2,
lat = south - height / 2 + random() * height * 2;
const coordinates = [[lon, lat]];
const points = 1 + Math.floor(random() * 12);
for (let j = 0; j < points; j++) {
lon += (random() - 0.5) * step;
lat += (random() - 0.5) * step;
coordinates.push([lon, lat]);
}
roads.push({ type: 'primary', oneway: i % 2, id: i, coordinates });
}
const box = boxes[5];
const midLat = (box.south + box.north) / 2,
midLon = (box.west + box.east) / 2;
roads.push(
// Along a tile edge, ending on a corner, and touching an edge from outside.
{
id: 'edge',
coordinates: [
[box.west, box.south - 0.01],
[box.west, box.north + 0.01],
],
},
{
id: 'corner',
coordinates: [
[box.west - 0.01, box.south - 0.01],
[box.west, box.south],
[box.east, box.north],
],
},
{
id: 'touch',
coordinates: [
[box.west - 0.01, midLat],
[box.west, midLat],
],
},
// Across the whole block, and a repeated vertex.
{
id: 'across',
coordinates: [
[west - 0.01, midLat],
[east + 0.01, midLat + 0.0003],
],
},
{
id: 'repeat',
coordinates: [
[midLon, midLat],
[midLon, midLat],
[midLon + 0.001, midLat],
],
},
// Records the clip drops or leaves alone.
{ id: 'single', coordinates: [[west - 0.02, midLat]] },
{ id: 'empty', coordinates: [] },
{
id: 'negative-zero',
coordinates: [
[-0, south - 0.02],
[0.001, south - 0.02],
],
},
{
id: 'polar',
coordinates: [
[west - 0.02, 86],
[west - 0.02, 86.01],
],
},
);
return roads;
}
for (const [place, x, y] of [
['Manhattan', 4823, 6158],
['London, across longitude 0', 8190, 5446],
['longitude 0 and latitude 0', 8190, 8190],
['the southern and eastern hemispheres', 15070, 9826],
])
test(`coarse roads clipped around detail tiles match the every-tile clip: ${place}`, () => {
const tiles = tileBlock(x, y);
const roads = roadsAround(tiles, seeded(x * 31 + y));
for (const loaded of [tiles, tiles.slice(0, 5), tiles.slice(3, 4), []]) {
const expected = clipEveryRoadAgainstEveryTile(roads, loaded);
assert.ok(loaded.length === 0 || expected.length !== roads.length);
// deepStrictEqual separates -0 from 0 and compares every vertex exactly.
assert.deepStrictEqual(outsideDetailTiles(roads, loaded), expected);
}
});
test('only a road that reaches a detail tile is clipped against it', () => {
const tiles = tileBlock(4823, 6158);
const block = tiles.map((tile) => tileToBBox(tile.z, tile.x, tile.y));
const west = Math.min(...block.map((box) => box.west)),
north = Math.max(...block.map((box) => box.north));
// 300 roads beside the block and between its tile edges, none touching one.
const clear = [];
for (let i = 0; i < 300; i++) {
const box = block[i % block.length];
const lon = i % 2 ? west - 0.02 - i * 1e-5 : box.west + 0.004;
const lat = i % 2 ? box.south + 0.004 : north + 0.01 + i * 1e-5;
clear.push({
coordinates: [
[lon, lat],
[lon + 0.002, lat + 0.0005],
[lon + 0.003, lat + 0.001],
],
});
}
const first = block[0];
const crossing = {
coordinates: [
[first.west + 0.004, north + 0.01],
[first.west + 0.004, (first.south + first.north) / 2],
],
};
let clips = 0;
const counted = (line, region) => {
clips++;
return clipTileLine(line, region);
};
const roads = outsideDetailTiles([...clear, crossing], tiles, counted);
assert.deepStrictEqual(
roads,
clipEveryRoadAgainstEveryTile([...clear, crossing], tiles),
);
assert.equal(roads.length, 301);
// Four regions for each tile the crossing road reaches, never the 19,264
// clips of every road against every tile.
assert.ok(clips >= 4, `expected the crossing road to be clipped: ${clips}`);
assert.ok(clips <= 4 * tiles.length, `clipped ${clips} times`);
});
/** A DEM-regime ground service: one floor per toFixed(3) cell, counting reads. */
function cellGround({ mesh = false, warm = () => true } = {}) {
const ground = {
reads: 0,
meshFloorPreferred: () => mesh,
cachedGroundFloor(lat, lon) {
ground.reads++;
if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
// Number() as the shared cache does it: "-0.000" and "0.000" are one cell.
const cell = `${Number(lat.toFixed(3))},${Number(lon.toFixed(3))}`;
if (!warm(cell)) return null;
let hash = 0;
for (const character of cell)
hash = (Math.imul(hash, 31) + character.charCodeAt(0)) | 0;
// The mesh regime answers per point, not per cell.
return (hash % 4000) / 10 + (mesh ? lat - Math.floor(lat * 1000) / 1000 : 0);
},
};
return ground;
}
test('floor reads are shared per cell and equal the per-coordinate reads', () => {
const random = seeded(7);
const points = [];
for (let i = 0; i < 4000; i++)
points.push([40.75 + random() * 0.01, -73.99 + random() * 0.01]);
// Cell edges, where toFixed(3) and Math.round can disagree, in each sign.
for (const lat of [40.7505, -40.7505, 0.0005, -0.0005, 1.0005, 8.5745])
for (const lon of [-73.9905, 73.9905, 0.0005, -0.0005, 1.0005, 2.3515])
points.push([lat, lon], [lat + 1e-9, lon - 1e-9], [lat - 1e-9, lon]);
points.push([Number.NaN, 0], [0, Infinity], [0, 0], [-0, -0]);
const direct = cellGround();
const expected = points.map(([lat, lon]) =>
direct.cachedGroundFloor(lat, lon),
);
const ground = cellGround();
const floorAt = floorCellReader(ground);
assert.deepStrictEqual(
points.map(([lat, lon]) => floorAt(lat, lon)),
expected,
);
// 4000 points in a 0.01 degree square share about 121 cells.
assert.ok(ground.reads < 600, `read the shared cache ${ground.reads} times`);
// A cold cell is remembered as cold for the pass, not asked again.
const cold = cellGround({ warm: () => false });
const coldAt = floorCellReader(cold);
assert.equal(coldAt(40.7512, -73.9812), null);
assert.equal(coldAt(40.7513, -73.9813), null);
assert.equal(cold.reads, 1);
});
test('mesh floors and unknown ground services are read per coordinate', () => {
const mesh = cellGround({ mesh: true });
const meshAt = floorCellReader(mesh);
const a = meshAt(40.7512, -73.9812),
b = meshAt(40.75121, -73.9812);
assert.equal(mesh.reads, 2);
assert.notEqual(a, b);
// No regime to ask: nothing says a floor is the same across a cell.
let reads = 0;
const bareAt = floorCellReader({ cachedGroundFloor: () => ++reads });
bareAt(40.7512, -73.9812);
bareAt(40.7512, -73.9812);
assert.equal(reads, 2);
assert.equal(floorCellReader(undefined)(1, 2), undefined);
assert.equal(floorCellReader({})(1, 2), undefined);
});
function road(lon, lat, points = 40) {
const coordinates = [];
for (let i = 0; i < points; i++)
coordinates.push([lon + i * 0.00004, lat + i * 0.00003]);
return { type: 'residential', oneway: 1, coordinates };
}
test('parsing reads each floor cell once and builds the same waypoints', () => {
const ground = cellGround({ warm: (cell) => !cell.endsWith('3') });
const state = { _viewHeightEstimate: 12 };
const model = createModel({
state,
services: { ground },
parts: {},
source: {},
});
const records = [road(-73.99, 40.75), road(-73.9899, 40.7501)];
const parsed = model.parseRoads({ roads: records });
const coordinates = records.reduce(
(count, record) => count + record.coordinates.length,
0,
);
assert.ok(
ground.reads < coordinates / 3,
`${ground.reads} floor reads for ${coordinates} coordinates`,
);
const direct = cellGround({ warm: (cell) => !cell.endsWith('3') });
const expected = records.flatMap((record) =>
roadSurfaceChunks(record.coordinates).map((coords) =>
coords.map(([lon, lat]) => {
const floor = direct.cachedGroundFloor(lat, lon);
return Cesium.Cartesian3.fromDegrees(
lon,
lat,
(floor ?? state._viewHeightEstimate) + DOT_HEIGHT_OFFSET,
);
}),
),
);
assert.ok(direct.reads >= coordinates);
assert.deepStrictEqual(
parsed.map((entry) => entry.waypoints),
expected,
);
});
test('a record parsed earlier in the pass is not parsed again', () => {
const ground = cellGround();
const model = createModel({
state: {},
services: { ground },
parts: {},
source: {},
});
const first = { ...road(-73.99, 40.75), oneway: 0 },
second = road(-73.98, 40.76),
short = { type: 'primary', coordinates: [[-73.97, 40.77]] };
const parsedBySource = new WeakMap();
const tile = model.parseRoads({ roads: [first] }, null, parsedBySource);
assert.equal(tile.length, 2, 'a two-way record parses to both directions');
const reads = ground.reads;
const replaced = model.parseRoads(
{ roads: [second, short, first], replace: true },
null,
parsedBySource,
);
assert.equal(replaced.length, 3);
// The same parsed roads, in the snapshot's order: dots stay attached.
assert.equal(replaced[1], tile[0]);
assert.equal(replaced[2], tile[1]);
const fresh = cellGround();
createModel({
state: {},
services: { ground: fresh },
parts: {},
source: {},
}).parseRoads({ roads: [second] });
assert.equal(ground.reads - reads, fresh.reads, 'only the new record read');
// Without the map every call parses, as before.
const again = model.parseRoads({ roads: [first] });
assert.notEqual(again[0], tile[0]);
assert.deepStrictEqual(again, tile);
});
test('the snapshot that ends a pass parses only the records it adds', async () => {
const detail = { z: 14, x: 3743, y: 6745 };
const core = tileToBBox(detail.z, detail.x, detail.y);
const local = {
type: 'residential',
oneway: 1,
coordinates: [
[core.west + 0.002, core.south + 0.002],
[core.west + 0.004, core.south + 0.004],
],
};
const distant = {
type: 'primary',
oneway: 1,
coordinates: [
[core.east + 0.01, core.south],
[core.east + 0.02, core.south],
],
};
const bounds = {
...core,
east: core.east + 0.03,
coverage: {
detail: [detail],
coarse: [{ z: 12, x: 935, y: 1686 }],
key: 'test',
},
};
const source = createTrafficSource({
mapTiles: {
async fetchBounds(box, { zoom, onTile }) {
const tile = { roads: zoom === 14 ? [local] : [distant] };
onTile?.(tile);
return {
tiles: [tile],
loadedTiles: zoom === 14 ? [detail] : bounds.coverage.coarse,
partial: false,
};
},
},
});
const parsedRecords = [];
const painted = [];
const state = {
_enabled: true,
_loadGeneration: 0,
_tileCache: new Map(),
_roadMode: null,
_liveMode: false,
// The model's contract: fill the map, answer known records from it.
_parseRoads: (data, trace, parsedBySource) =>
data.roads.flatMap((record) => {
const known = parsedBySource?.get(record);
if (known) return known;
parsedRecords.push(record);
const parsed = [{ record }];
parsedBySource?.set(record, parsed);
return parsed;
}),
};
const ingestion = createIngestion({
state,
source,
services: {},
parts: {
viewport: {
clampBounds: (b) => b,
getBoundsCenter: () => ({ lat: 30.26, lon: -97.74 }),
},
flow: {
warmFlow: () => Promise.resolve([]),
applyFlowThenRender: async (roads, box, generation, altitude, label) => {
if (label === 'Loaded full') painted.push(roads);
return true;
},
},
},
});
await ingestion.loadRoadsForBounds(bounds, 350);
assert.equal(
parsedRecords.filter((record) => record === local).length,
1,
'the detail tile record is parsed when its tile streams, not again',
);
// The full graph is still the detail record plus the coarse road outside it.
assert.equal(painted.at(-1).length, 2);
assert.equal(painted.at(-1)[0].record, local);
assert.deepStrictEqual(
painted.at(-1)[1].record.coordinates,
distant.coordinates,
);
});
+100 -15
View File
@@ -33,23 +33,108 @@ export function trafficDetailBounds(box) {
return detail;
}
/** Keep coarse roads only outside the detailed tile cores. */
export function outsideDetailTiles(roads, tiles) {
/** Longitude/latitude extent of one line; NaN coordinates leave it unusable. */
function lineExtent(coordinates) {
let west = Infinity,
east = -Infinity,
south = Infinity,
north = -Infinity;
for (const [lon, lat] of coordinates) {
if (!(lon >= west)) west = lon;
if (!(lon <= east)) east = lon;
if (!(lat >= south)) south = lat;
if (!(lat <= north)) north = lat;
}
return { coordinates, west, east, south, north, settled: false };
}
/**
* What `clipTileLine` returns for a line lying wholly inside the clip region:
* the same line with each vertex recomputed from the one before it. Returns
* null for a line under the 12 m floor `clipTileLine` drops.
*/
function unclippedLine(coordinates) {
if (coordinates.length < 2) return null;
const out = [];
let metres = 0;
for (let i = 1; i < coordinates.length; i++) {
const a = coordinates[i - 1],
b = coordinates[i];
const dx = b[0] - a[0],
dy = b[1] - a[1];
if (i === 1) out.push([a[0] + 0 * dx, a[1] + 0 * dy]);
out.push([a[0] + dx, a[1] + dy]);
metres +=
Math.hypot(
(out[i][0] - out[i - 1][0]) * Math.cos((out[i][1] * Math.PI) / 180),
out[i][1] - out[i - 1][1],
) * 111320;
}
return metres >= 12 ? out : null;
}
const sameLine = (a, b) =>
a.every(
(point, i) => Object.is(point[0], b[i][0]) && Object.is(point[1], b[i][1]),
);
/**
* Keep coarse roads only outside the detailed tile cores.
*
* Each tile splits a line into the four regions around its core. Nearly every
* coarse road lies wholly inside one of those regions for nearly every tile,
* where the clip hands the line back unchanged, so that case is answered from
* the line's extent and only a line that reaches a tile's core or edge is
* clipped. Clipping every road against every tile froze the page for hundreds
* of milliseconds per road load at street level.
*
* `clip` is injectable for tests.
*/
export function outsideDetailTiles(roads, tiles, clip = clipTileLine) {
const boxes = tiles.map((tile) => tileToBBox(tile.z, tile.x, tile.y));
return roads.flatMap((road) => {
let lines = [road.coordinates];
for (const tile of tiles) {
const box = tileToBBox(tile.z, tile.x, tile.y);
const regions = [
{ west: -180, east: box.west, south: -85, north: 85 },
{ west: box.east, east: 180, south: -85, north: 85 },
{ west: box.west, east: box.east, south: -85, north: box.south },
{ west: box.west, east: box.east, south: box.north, north: 85 },
];
lines = lines.flatMap((line) =>
regions.flatMap((region) => clipTileLine(line, region)),
);
let lines = [lineExtent(road.coordinates)];
for (const box of boxes) {
const next = [];
for (const line of lines) {
// Strictly inside one region, and inside the bounds every region
// shares: the other three regions return nothing.
const clear =
line.west > -180 &&
line.east < 180 &&
line.south > -85 &&
line.north < 85 &&
(line.east < box.west ||
line.west > box.east ||
(line.west > box.west &&
line.east < box.east &&
(line.north < box.south || line.south > box.north)));
if (!clear) {
const regions = [
{ west: -180, east: box.west, south: -85, north: 85 },
{ west: box.east, east: 180, south: -85, north: 85 },
{ west: box.west, east: box.east, south: -85, north: box.south },
{ west: box.west, east: box.east, south: box.north, north: 85 },
];
for (const region of regions)
for (const coordinates of clip(line.coordinates, region))
next.push(lineExtent(coordinates));
} else if (line.settled) {
next.push(line);
} else {
// The first unclipped pass can still move a vertex by a rounding
// step (a road crossing longitude or latitude 0); once a pass
// changes nothing, no later one will.
const coordinates = unclippedLine(line.coordinates);
if (!coordinates) continue;
const kept = lineExtent(coordinates);
kept.settled = sameLine(coordinates, line.coordinates);
next.push(kept);
}
}
lines = next;
}
return lines.map((coordinates) => ({ ...road, coordinates }));
return lines.map(({ coordinates }) => ({ ...road, coordinates }));
});
}
+39
View File
@@ -69,6 +69,45 @@ export function trafficSurfaceReady(scene) {
return currentRenderedFrame(scene)?.ready === true;
}
/**
* Ground-floor reads for one synchronous pass over road coordinates, asking
* the shared cache once per floor cell instead of once per coordinate.
*
* A road tile puts thousands of coordinates into a few hundred ~111 m cells,
* and each shared read formats and looks up two string keys, which added up
* to seconds per street-level load. Mesh floors answer per point (the nearest
* reading in the cell), so they are read through unchanged; only the DEM
* regime is one value per cell. Build a reader per pass: cells warm up
* between passes.
*/
export function floorCellReader(ground) {
const read = ground?.cachedGroundFloor;
if (!read) return () => undefined;
if (ground.meshFloorPreferred?.() !== false)
return (lat, lon) => read(lat, lon);
const cells = new Map();
return (lat, lon) => {
const y = lat * 1000,
x = lon * 1000;
const row = Math.round(y),
column = Math.round(x);
// The shared cache rounds with toFixed(3). At a cell edge that and
// Math.round can pick different cells, so an edge point asks directly.
if (!(
Math.abs(Math.abs(y - row) - 0.5) > 1e-6 &&
Math.abs(Math.abs(x - column) - 0.5) > 1e-6
))
return read(lat, lon);
const key = row * 1e6 + column;
let floor = cells.get(key);
if (floor === undefined) {
floor = read(lat, lon) ?? null;
cells.set(key, floor);
}
return floor;
};
}
/** Preserve bends and insert height samples at most 150 m apart, splitting long roads. */
export function roadSurfaceChunks(coordinates) {
const chunks = [];
+12 -3
View File
@@ -1,5 +1,5 @@
import * as Cesium from 'cesium';
import { roadSurfaceChunks } from './surface.js';
import { floorCellReader, roadSurfaceChunks } from './surface.js';
import { TRAFFIC_TIMING_ENABLED, DOT_HEIGHT_OFFSET } from './policy.js';
export function createTiming({ state: layerState, services, parts, source }) {
@@ -190,7 +190,7 @@ export function createTiming({ state: layerState, services, parts, source }) {
* waypoint-materialization time independently.
*/
function parseRoadsTimed(roadData, trace) {
function parseRoadsTimed(roadData, trace, parsedBySource) {
/* TRACE_ONLY_BEGIN */
const _trafficTimingState = trafficTimingPass(
trace,
@@ -231,11 +231,19 @@ export function createTiming({ state: layerState, services, parts, source }) {
}
const roads = [];
const floorAt = floorCellReader(services.ground);
/* TRACE_ONLY_BEGIN */
let _trafficTimingWaypointMaterializationMs = 0;
/* TRACE_ONLY_END */
for (const road of roadData.roads) {
if (!road.coordinates || road.coordinates.length < 2) continue;
// A replacing snapshot repeats records this load already parsed.
const known = parsedBySource?.get(road);
if (known) {
for (const parsed of known) roads.push(parsed);
continue;
}
const first = roads.length;
for (const coords of roadSurfaceChunks(road.coordinates)) {
const type = road.type;
@@ -245,7 +253,7 @@ export function createTiming({ state: layerState, services, parts, source }) {
const _trafficTimingMaterializeStart = performance.now();
/* TRACE_ONLY_END */
const waypoints = coords.map(([lng, lat]) => {
const floor = services.ground?.cachedGroundFloor?.(lat, lng);
const floor = floorAt(lat, lng);
const h =
(Number.isFinite(floor) && Math.abs(floor) <= 9000
? floor
@@ -279,6 +287,7 @@ export function createTiming({ state: layerState, services, parts, source }) {
flow: road.flow || null,
});
}
parsedBySource?.set(road, roads.slice(first));
}
/* TRACE_ONLY_BEGIN */
const _trafficTimingMetrics = {
+11 -55
View File
@@ -45,39 +45,6 @@ export function createGroundFloor({ terrain, signal }) {
return { lat: Number(lat.toFixed(3)), lon: Number(lon.toFixed(3)) };
}
/**
* One coordinate's coarse cell as an integer: `Number(deg.toFixed(3))` in
* thousandths of a degree, without the trip through a string. The floor is
* read for every aircraft on every fleet pass, and `coarseFloorCoord`'s two
* `toFixed` calls and the string keys built from them were most of the cost.
* `toFixed` rounds the exact decimal value; `deg * 1000` is within 1e-10 of
* it for |deg| < 1000, so the two can only round differently right at a
* half, and there the string decides.
* @param {number} deg
* @returns {number}
*/
function coarseCellIndex(deg) {
const scaled = deg * 1000;
if (
!(Math.abs(deg) < 1000) ||
Math.abs(scaled - Math.floor(scaled) - 0.5) < 1e-6
)
return Math.round(Number(deg.toFixed(3)) * 1000);
return Math.round(scaled);
}
/**
* Key of a coarse cell in `_meshCells`: the two indices packed into one
* number, or the text form for a longitude too far out of range to pack.
* @param {number} latIndex @param {number} lonIndex
* @returns {number|string}
*/
function meshCellKey(latIndex, lonIndex) {
return Math.abs(lonIndex) < 500_000 && Math.abs(latIndex) < 1e9
? latIndex * 1_000_000 + lonIndex
: `${latIndex},${lonIndex}`;
}
/**
* Pure floor clamp.
* - finite alt + finite ground → max(alt, ground + lift)
@@ -457,8 +424,8 @@ export function createGroundFloor({ terrain, signal }) {
// reported here by meshFloorSampler.js. Design principle (owner): NEVER
// below the visible surface; slightly above is always fine. The DEM stays
// the instant global prior/fallback and the sanity gate for samples.
/** @type {Map<number|string, Array<{lat: number, lon: number, h: number}>>}
* coarse cell key (`meshCellKey`) -> rendered-surface readings (m, ellipsoidal), each kept
/** @type {Map<string, Array<{lat: number, lon: number, h: number}>>}
* coarse cell key -> rendered-surface readings (m, ellipsoidal), each kept
* at the point it was probed. A read answers from the reading nearest the
* asked point, so a viaduct and the street beside it in one cell keep their
* own heights. */
@@ -501,7 +468,8 @@ export function createGroundFloor({ terrain, signal }) {
!Number.isFinite(heightM)
)
return;
const key = meshCellKey(coarseCellIndex(lat), coarseCellIndex(lon));
const c = coarseFloorCoord(lat, lon);
const key = `${c.lat},${c.lon}`;
if (!_meshCells.has(key)) _meshCells.set(key, [{ lat, lon, h: heightM }]);
}
@@ -529,7 +497,7 @@ export function createGroundFloor({ terrain, signal }) {
const cell = coarseFloorCoord(lat, lon);
const prior = cachedRealEllipsoidalGround(cell.lat, cell.lon);
if (!meshFloorSampleWithinPrior(heightM, prior)) return false;
const key = meshCellKey(coarseCellIndex(lat), coarseCellIndex(lon));
const key = `${cell.lat},${cell.lon}`;
const readings = _meshCells.get(key);
if (!readings) {
_meshCells.set(key, [{ lat, lon, h: heightM }]);
@@ -570,16 +538,8 @@ export function createGroundFloor({ terrain, signal }) {
function cachedMeshFloor(lat, lon) {
if (!_meshPreferred) return null;
if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
return meshFloorInCell(
lat,
lon,
meshCellKey(coarseCellIndex(lat), coarseCellIndex(lon)),
);
}
/** `cachedMeshFloor` for a caller that already has the point's cell key. */
function meshFloorInCell(lat, lon, key) {
const readings = _meshCells.get(key);
const c = coarseFloorCoord(lat, lon);
const readings = _meshCells.get(`${c.lat},${c.lon}`);
if (!readings) return null;
if (readings.length === 1) return readings[0].h;
const k = Math.cos((lat * Math.PI) / 180) ** 2;
@@ -612,14 +572,10 @@ export function createGroundFloor({ terrain, signal }) {
*/
function cachedGroundFloor(lat, lon) {
if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
// The cell is worked out once, as integers, for both reads.
const latIndex = coarseCellIndex(lat);
const lonIndex = coarseCellIndex(lon);
if (_meshPreferred) {
const mesh = meshFloorInCell(lat, lon, meshCellKey(latIndex, lonIndex));
if (mesh != null) return mesh;
}
return cachedRealEllipsoidalGround(latIndex / 1000, lonIndex / 1000);
const mesh = cachedMeshFloor(lat, lon);
if (mesh != null) return mesh;
const c = coarseFloorCoord(lat, lon);
return cachedRealEllipsoidalGround(c.lat, c.lon);
}
/**
-176
View File
@@ -1,176 +0,0 @@
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { createGroundFloor } from './groundFloor.js';
import { createTerrainHeights } from './terrainHeights.js';
/** Counts Number.prototype.toFixed calls made while `run` executes. */
function countToFixed(run) {
const original = Number.prototype.toFixed;
let calls = 0;
Number.prototype.toFixed = function (...args) {
calls += 1;
return original.apply(this, args);
};
try {
run();
} finally {
Number.prototype.toFixed = original;
}
return calls;
}
/**
* The floor read as it was before the cell became an integer: the coarse cell
* through `toFixed(3)`, mesh cells and DEM cells under string keys.
*/
function referenceFloor() {
const mesh = new Map();
const dem = new Map();
const coarse = (lat, lon) => ({
lat: Number(lat.toFixed(3)),
lon: Number(lon.toFixed(3)),
});
const demKey = (lat, lon) => `${lat.toFixed(5)},${lon.toFixed(5)}`;
return {
reportMesh(lat, lon, h) {
const c = coarse(lat, lon);
const key = `${c.lat},${c.lon}`;
if (!mesh.has(key)) mesh.set(key, [{ lat, lon, h }]);
},
storeDem(lat, lon, h) {
dem.set(demKey(lat, lon), h);
},
read(lat, lon, meshPreferred = true) {
if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
const c = coarse(lat, lon);
const readings = meshPreferred ? mesh.get(`${c.lat},${c.lon}`) : null;
if (readings) return readings[0].h;
return dem.get(demKey(c.lat, c.lon)) ?? null;
},
};
}
/** A real terrain cache whose every resolved point takes the height asked for. */
async function warmTerrain(points) {
const heights = new Map(points.map((p) => [`${p.lat},${p.lon}`, p.h]));
const terrain = createTerrainHeights({
source: {
async getHeights(chunk) {
return chunk.map((item) => ({
ellipsoid: heights.get(`${item.lat},${item.lon}`),
}));
},
},
});
await terrain.resolveEllipsoidalGround(
points.map(({ lat, lon }) => ({ lat, lon })),
);
return terrain;
}
/** Deterministic pseudo-random numbers in [0, 1). */
function random(seed) {
let state = seed;
return () => {
state = (state * 1664525 + 1013904223) % 4294967296;
return state / 4294967296;
};
}
/** Coordinates that land on, and just either side of, a coarse-cell edge. */
function edgeCoordinates() {
const out = [];
for (const base of [0, 0.0005, -0.0005, 12.3455, -12.3455, 89.9995, 179.9995])
for (const nudge of [0, 1e-13, -1e-13, 1e-9, -1e-9, 1e-7, -1e-7, 4e-4])
out.push(base + nudge);
// Thousandths whose doubles sit a hair either side of the half.
for (let k = -40; k <= 40; k += 1) out.push((k + 0.5) / 1000);
out.push(-0, 1.0005, 1.0015, 2.5, -2.5, 1e-7, -1e-7);
return out;
}
test('the floor read answers exactly as the string-keyed read did', async () => {
const next = random(20261113);
const cells = [];
for (let i = 0; i < 400; i += 1) {
cells.push({
lat: Number((next() * 170 - 85).toFixed(3)),
lon: Number((next() * 360 - 180).toFixed(3)),
h: Math.round(next() * 4000),
});
}
// Cells along the equator and the prime meridian, where a cell index is 0.
for (const edge of edgeCoordinates()) {
const lat = Number(edge.toFixed(3));
cells.push({ lat: Math.max(-89, Math.min(89, lat)), lon: 10, h: 77 });
cells.push({ lat: 10, lon: lat, h: 88 });
}
const reference = referenceFloor();
for (const c of cells) reference.storeDem(c.lat, c.lon, c.h);
const terrain = await warmTerrain(cells);
const groundFloor = createGroundFloor({ terrain });
// A rendered-surface reading in every seventh cell, taken off its centre.
cells.forEach((c, i) => {
if (i % 7) return;
const lat = c.lat + 0.0002;
const lon = c.lon - 0.0003;
reference.reportMesh(lat, lon, c.h + 3);
groundFloor.reportMeshFloorCell(lat, lon, c.h + 3);
});
const probes = [];
for (const c of cells) {
probes.push([c.lat, c.lon]);
probes.push([c.lat + (next() - 0.5) * 0.002, c.lon + (next() - 0.5) * 0.002]);
}
for (const a of edgeCoordinates())
for (const b of [10, 10.0004, -0, 0.0005, -0.0005]) {
probes.push([a, b]);
probes.push([b, a]);
}
probes.push([NaN, 1], [1, Infinity], [95, 400], [10, 720.1234]);
for (const meshPreferred of [true, false]) {
groundFloor.setMeshFloorPreferred(meshPreferred);
let hits = 0;
for (const [lat, lon] of probes) {
const expected = reference.read(lat, lon, meshPreferred);
assert.equal(
groundFloor.cachedGroundFloor(lat, lon),
expected,
`floor at ${lat}, ${lon} (mesh ${meshPreferred})`,
);
if (expected !== null) hits += 1;
}
assert.ok(hits > 400, `${hits} probes found a floor`);
}
});
test('reading a floor formats no numbers, hit or miss', async () => {
const cell = { lat: 51.47, lon: -0.454, h: 25 };
const terrain = await warmTerrain([cell]);
const groundFloor = createGroundFloor({ terrain });
groundFloor.reportMeshFloorCell(48.3537, 11.7861, 453);
const calls = countToFixed(() => {
// The DEM cell, a rendered-surface cell, and open ocean with neither.
assert.equal(groundFloor.cachedGroundFloor(51.4702, -0.4541), 25);
assert.equal(groundFloor.cachedGroundFloor(48.3538, 11.7862), 453);
for (let i = 0; i < 1000; i += 1)
assert.equal(groundFloor.cachedGroundFloor(30 + i * 0.011, -40.2), null);
});
// Before, each read made six toFixed calls (the cell twice, the DEM key).
assert.equal(calls, 0);
});
test('a reading reported at a point is found from anywhere in its cell', async () => {
const terrain = await warmTerrain([{ lat: 41.5, lon: -97.66, h: 120 }]);
const groundFloor = createGroundFloor({ terrain });
assert.equal(groundFloor.reportValidatedMeshFloorCell(41.5003, -97.6602, 129), true);
assert.equal(groundFloor.cachedMeshFloor(41.4996, -97.6598), 129);
assert.equal(groundFloor.cachedGroundFloor(41.4996, -97.6598), 129);
// The next cell over has no reading and no DEM entry.
assert.equal(groundFloor.cachedMeshFloor(41.5006, -97.6602), null);
assert.equal(groundFloor.cachedGroundFloor(41.5006, -97.6602), null);
});
+3 -125
View File
@@ -86,89 +86,6 @@ export function createTerrainHeights({
*/
const cache = new Map();
/**
* The same entries under a numeric key, for the synchronous reads. Those run
* for every aircraft on every fleet pass (about 94,000 a second with 7,500
* aircraft in view), nearly all of them misses, and building the string key
* (two `toFixed` calls and a concatenation) was most of what a read cost.
* Kept in step with `cache` by `cacheStore`, eviction and the abort handler.
* `at` is the value of `moves` when the entry last became the newest.
* @type {Map<number, {key: string, entry: object, at: number}>}
*/
const cells = new Map();
/** Counts every move to the newest end of `cache`: stores and promotions. */
let moves = 0;
/**
* A read promotes its entry only once this many moves have passed since it
* was last the newest. An entry cannot reach the cold end in fewer than
* CACHE_MAX_ENTRIES - 1 moves, so one read at least this often is never
* evicted, without rewriting the Map on every read.
*/
const PROMOTE_AFTER_MOVES = Math.floor(CACHE_MAX_ENTRIES / 2);
/**
* `value.toFixed(5)` as an integer count of 1e-5 steps, or null when the
* fast arithmetic cannot be trusted to match it. `toFixed` rounds the exact
* decimal value; `value * 1e5` is within 2e-8 of it for |value| < 1000, so
* the two can only round differently this close to a half. A negative value
* that rounds to zero is left to the string too: it formats as "-0.00000",
* a different key from "0.00000".
* @param {number} value
* @returns {number|null}
*/
function fixed5Index(value) {
if (!(Math.abs(value) < 1000)) return null;
const scaled = value * 1e5;
if (Math.abs(scaled - Math.floor(scaled) - 0.5) < 1e-6) return null;
const index = Math.round(scaled);
return Object.is(index, -0) ? null : index;
}
/** Indices at or past this (500 degrees) do not pack into one integer. */
const CELL_INDEX_LIMIT = 5e7;
/**
* The numeric key for a coordinate: its two 5-decimal indices packed into
* one integer (below 2^53), or null when the coordinate has to go through
* its string key instead.
* @param {number} lat
* @param {number} lon
* @returns {number|null}
*/
function cellKey(lat, lon) {
const latIndex = fixed5Index(lat);
const lonIndex = fixed5Index(lon);
if (
latIndex === null ||
lonIndex === null ||
Math.abs(latIndex) >= CELL_INDEX_LIMIT ||
Math.abs(lonIndex) >= CELL_INDEX_LIMIT
)
return null;
return latIndex * 1e8 + lonIndex;
}
/**
* The numeric key of a stored string key. The text is the rounded
* coordinate itself, so this is exact. Null for a key `cellKey` never
* produces; such a key is only ever read through its string.
* @param {string} key
* @returns {number|null}
*/
function cellKeyOf(key) {
const comma = key.indexOf(',');
const latIndex = Math.round(Number(key.slice(0, comma)) * 1e5);
const lonIndex = Math.round(Number(key.slice(comma + 1)) * 1e5);
if (
!(Math.abs(latIndex) < CELL_INDEX_LIMIT) ||
!(Math.abs(lonIndex) < CELL_INDEX_LIMIT) ||
Object.is(latIndex, -0) ||
Object.is(lonIndex, -0)
)
return null;
return latIndex * 1e8 + lonIndex;
}
/**
* Store an entry and drop the coldest ones once past the cap. `Map` iterates
* in insertion order, so deleting the first key evicts the least recently
@@ -184,15 +101,10 @@ export function createTerrainHeights({
function cacheStore(key, entry) {
cache.delete(key);
cache.set(key, entry);
moves += 1;
const cell = cellKeyOf(key);
if (cell !== null) cells.set(cell, { key, entry, at: moves });
while (cache.size > CACHE_MAX_ENTRIES) {
const coldest = cache.keys().next().value;
if (coldest === undefined) break;
cache.delete(coldest);
const coldestCell = cellKeyOf(coldest);
if (coldestCell !== null) cells.delete(coldestCell);
}
}
@@ -207,36 +119,9 @@ export function createTerrainHeights({
if (entry === undefined) return undefined;
cache.delete(key);
cache.set(key, entry);
moves += 1;
const cell = cellKeyOf(key);
const held = cell === null ? undefined : cells.get(cell);
if (held) held.at = moves;
return entry;
}
/**
* The synchronous read: the entry for a coordinate, or undefined on a miss.
* Same answer as `cacheTouch(cacheKey(lat, lon))`, without building the
* string, and promoting only an entry that has drifted towards the cold end
* (see PROMOTE_AFTER_MOVES).
* @param {number} lat
* @param {number} lon
* @returns {{ellipsoid: number, source: 'reearth'|'geoid-fallback', retryAt?: number}|undefined}
*/
function cacheRead(lat, lon) {
const cell = cellKey(lat, lon);
if (cell === null) return cacheTouch(cacheKey(lat, lon));
const held = cells.get(cell);
if (held === undefined) return undefined;
if (moves - held.at > PROMOTE_AFTER_MOVES) {
cache.delete(held.key);
cache.set(held.key, held.entry);
moves += 1;
held.at = moves;
}
return held.entry;
}
/**
* Builds the rounded cache key shared between the in-memory cache and the
* `points` string sent to the proxy (see file header, point 2).
@@ -257,7 +142,7 @@ export function createTerrainHeights({
* @returns {number|null}
*/
function cachedEllipsoidalGround(lat, lon) {
const entry = cacheRead(lat, lon);
const entry = cacheTouch(cacheKey(lat, lon));
return entry ? entry.ellipsoid : null;
}
@@ -274,7 +159,7 @@ export function createTerrainHeights({
* @returns {number|null}
*/
function cachedRealEllipsoidalGround(lat, lon) {
const entry = cacheRead(lat, lon);
const entry = cacheTouch(cacheKey(lat, lon));
return entry && entry.source === 'reearth' ? entry.ellipsoid : null;
}
@@ -485,14 +370,7 @@ export function createTerrainHeights({
});
}
signal?.addEventListener(
'abort',
() => {
cache.clear();
cells.clear();
},
{ once: true },
);
signal?.addEventListener('abort', () => cache.clear(), { once: true });
return {
cachedEllipsoidalGround,
cachedRealEllipsoidalGround,
-148
View File
@@ -169,151 +169,3 @@ test('an out-of-range cache bound falls back to the default instead of disabling
);
}
});
/** Counts Number.prototype.toFixed calls made while `run` executes. */
function countToFixed(run) {
const original = Number.prototype.toFixed;
let calls = 0;
Number.prototype.toFixed = function (...args) {
calls += 1;
return original.apply(this, args);
};
try {
run();
} finally {
Number.prototype.toFixed = original;
}
return calls;
}
test('a synchronous read finds exactly the entry its 5-decimal key names', async () => {
// Stored coordinates, and for each the reads that must and must not reach it.
// The expectation is the string key the cache has always used.
const stored = [
[0, 0.001],
[51.47, -0.454],
[-33.94611, 151.17722],
[0.00001, 0.00002],
[-0.00001, 0.00003],
[89.99999, 179.99999],
[-89.99999, -179.99999],
[12.345675, 98.765435],
[1e-7, 5],
[-1e-7, 6],
[7, -1e-7],
[200.5, 361.25],
[10, 500],
[10, 499.999999],
];
const key = (lat, lon) => `${lat.toFixed(5)},${lon.toFixed(5)}`;
const heights = new Map(
stored.map(([lat, lon], i) => [key(lat, lon), 100 + i]),
);
const terrain = createTerrainHeights({
source: {
async getHeights(chunk) {
return chunk.map((item) => ({ ellipsoid: heights.get(item.key) }));
},
},
});
await terrain.resolveEllipsoidalGround(
stored.map(([lat, lon]) => ({ lat, lon })),
);
const probes = [];
const nudges = [
0, 1e-13, -1e-13, 1e-9, -1e-9, 4e-6, -4e-6, 4.9999e-6, 5e-6, -5e-6,
5.0001e-6, 1e-5, -1e-5,
];
for (const [lat, lon] of stored)
for (const a of nudges)
for (const b of [0, 4e-6, -5e-6])
probes.push([lat + a, lon + b], [lat + b, lon + a]);
probes.push([0, 0], [-0, 0.001], [0, -0], [NaN, 1], [1, Infinity], [1e21, 2]);
let hits = 0;
for (const [lat, lon] of probes) {
const expected = heights.get(key(lat, lon)) ?? null;
assert.equal(
terrain.cachedEllipsoidalGround(lat, lon),
expected,
`plain read at ${lat}, ${lon}`,
);
assert.equal(
terrain.cachedRealEllipsoidalGround(lat, lon),
expected,
`real read at ${lat}, ${lon}`,
);
if (expected !== null) hits += 1;
}
assert.ok(
hits > 100 && hits < probes.length,
`${hits} of ${probes.length} reads hit`,
);
});
test('a synchronous read of an ordinary coordinate formats no numbers', async () => {
const terrain = createTerrainHeights({ source: stubSource() });
await terrain.resolveEllipsoidalGround([pointAt(1), pointAt(2)]);
const calls = countToFixed(() => {
assert.equal(
terrain.cachedRealEllipsoidalGround(0, lonAt(1)),
heightAt(lonAt(1)),
);
assert.equal(
terrain.cachedEllipsoidalGround(0, lonAt(2)),
heightAt(lonAt(2)),
);
// Misses are the common case: an aircraft over a cell nobody resolved.
for (let i = 10; i < 1010; i += 1)
assert.equal(terrain.cachedRealEllipsoidalGround(45.123, lonAt(i)), null);
});
// Before, every read built its key with two toFixed calls.
assert.equal(calls, 0);
});
test('an entry read again and again is not rewritten on each read, and still outlives the rest', async () => {
const terrain = createTerrainHeights({
source: stubSource(),
maxCacheEntries: 8,
});
for (let i = 0; i < 8; i += 1)
await terrain.resolveEllipsoidalGround([pointAt(i)]);
// Coordinate 0 is the coldest. Read it between stores, as a parked contact
// would; the seven newer ones are never read.
for (let i = 8; i < 15; i += 1) {
for (let read = 0; read < 50; read += 1)
assert.equal(
terrain.cachedEllipsoidalGround(0, lonAt(0)),
heightAt(lonAt(0)),
);
await terrain.resolveEllipsoidalGround([pointAt(i)]);
}
assert.equal(
terrain.cachedEllipsoidalGround(0, lonAt(0)),
heightAt(lonAt(0)),
);
for (let i = 1; i < 8; i += 1)
assert.equal(
terrain.cachedEllipsoidalGround(0, lonAt(i)),
null,
`unread coordinate ${i} was evicted`,
);
});
test('an evicted coordinate is gone from the synchronous read too', async () => {
const terrain = createTerrainHeights({
source: stubSource(),
maxCacheEntries: 2,
});
for (let i = 0; i < 5; i += 1)
await terrain.resolveEllipsoidalGround([pointAt(i)]);
for (let i = 0; i < 3; i += 1)
assert.equal(terrain.cachedRealEllipsoidalGround(0, lonAt(i)), null);
for (let i = 3; i < 5; i += 1)
assert.equal(
terrain.cachedRealEllipsoidalGround(0, lonAt(i)),
heightAt(lonAt(i)),
);
});