File size: 16,737 Bytes
7391956
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
// SPDX-License-Identifier: Apache-2.0
// Live sheet: stream a tifxyz segment and a zarr volume from the open data bucket and sample the volume onto the
// sheet in the browser, the same rule as Scrolls' `kit sheetview` (a volume value per grid node: the max or mean
// along the node's normal over plus or minus `depth` level-0 voxels, nearest voxel of one pyramid level).
// Pure JavaScript, no DOM. Only the rows of the tifxyz TIFFs inside the crop are fetched (HTTP Range), and only the
// zarr chunks the samples touch. Raw chunks need nothing else; blosc chunks load a decoder from jsDelivr once.

const BLOSC_URL = 'https://cdn.jsdelivr.net/npm/numcodecs@0.3.2/+esm';

// ------------------------------------------------------------------ fetching

async function getRange(url, start, end, signal) {           // bytes [start, end)
  const r = await fetch(url, { headers: { Range: `bytes=${start}-${end - 1}` }, signal });
  if (!r.ok) throw new Error(`${url}: HTTP ${r.status}`);
  const buf = new Uint8Array(await r.arrayBuffer());
  if (r.status === 200) return buf.subarray(start, end);      // a server that ignores Range sends the whole file
  return buf;
}

async function getJSON(url, signal) {
  const r = await fetch(url, { signal });
  if (!r.ok) return null;
  return r.json();
}

// ------------------------------------------------------------------ TIFF (uncompressed float32, strips)

const TYPE_SIZE = { 1: 1, 2: 1, 3: 2, 4: 4, 5: 8, 6: 1, 7: 1, 8: 2, 9: 4, 10: 8, 11: 4, 12: 8, 16: 8 };

// The layout of a one-page float32 TIFF: width, height, and the byte offset of every row.
export async function tiffLayout(url, signal) {
  let head = await getRange(url, 0, 65536, signal);
  const dv = () => new DataView(head.buffer, head.byteOffset, head.byteLength);
  const le = head[0] === 0x49;
  let d = dv();
  const magic = d.getUint16(2, le), big = magic === 43;
  if (magic !== 42 && !big) throw new Error(`${url}: not a TIFF`);
  const u64 = (o) => Number(d.getBigUint64(o, le));
  let ifd = big ? u64(8) : d.getUint32(4, le);
  if (ifd + 4096 > head.length) { head = await getRange(url, ifd, ifd + 65536, signal); d = dv(); ifd = 0; }
  const n = big ? u64(ifd) : d.getUint16(ifd, le);
  const tags = {};
  for (let i = 0; i < n; i++) {
    const e = ifd + (big ? 8 + 20 * i : 2 + 12 * i);
    const tag = d.getUint16(e, le), type = d.getUint16(e + 2, le);
    const count = big ? u64(e + 4) : d.getUint32(e + 4, le);
    const size = (TYPE_SIZE[type] || 1) * count, inline = size <= (big ? 8 : 4);
    const voff = e + (big ? 12 : 8);
    tags[tag] = { type, count, inline, at: inline ? voff : (big ? u64(voff) : d.getUint32(voff, le)) };
  }
  const read = async (t) => {                                  // the tag's values as numbers
    const size = TYPE_SIZE[t.type] || 1;
    let view, base;
    if (t.inline) { view = d; base = t.at; } else {
      const b = await getRange(url, t.at, t.at + size * t.count, signal);
      view = new DataView(b.buffer, b.byteOffset, b.byteLength); base = 0;
    }
    const out = new Array(t.count);
    for (let i = 0; i < t.count; i++) {
      const o = base + i * size;
      out[i] = size === 2 ? view.getUint16(o, le) : size === 4 ? view.getUint32(o, le) : Number(view.getBigUint64(o, le));
    }
    return out;
  };
  const one = async (tag, dflt) => (tags[tag] ? (await read(tags[tag]))[0] : dflt);
  const width = await one(256), height = await one(257);
  if ((await one(259, 1)) !== 1) throw new Error(`${url}: compressed TIFF; only uncompressed tifxyz is supported`);
  if ((await one(258, 32)) !== 32 || (await one(339, 3)) !== 3) throw new Error(`${url}: not float32`);
  if (!tags[273]) throw new Error(`${url}: tiled TIFF; only strips are supported`);
  const offsets = await read(tags[273]);
  const rps = await one(278, height);
  const rowOffset = (r) => offsets[Math.floor(r / rps)] + (r % rps) * width * 4;
  return { width, height, le, rowOffset, rps };
}

// Rows r0:r1 and columns c0:c1 of a float32 TIFF, as a Float32Array (row-major, (r1-r0) x (c1-c0)).
export async function tiffRows(url, layout, r0, r1, c0, c1, signal) {
  const { width, le, rowOffset, rps } = layout, W = c1 - c0, out = new Float32Array((r1 - r0) * W);
  for (let s = r0; s < r1;) {                                   // one request per strip span
    const e = Math.min(r1, (Math.floor(s / rps) + 1) * rps);
    const a = rowOffset(s), buf = await getRange(url, a, a + (e - s) * width * 4, signal);
    const dv = new DataView(buf.buffer, buf.byteOffset, buf.byteLength);
    for (let r = s; r < e; r++) for (let c = c0; c < c1; c++)
      out[(r - r0) * W + (c - c0)] = dv.getFloat32(((r - s) * width + c) * 4, le);
    s = e;
  }
  return out;
}

// ------------------------------------------------------------------ segment

// A tifxyz crop: { xyz (Float64Array h*w*3), valid (Uint8Array h*w), h, w, meta, voxelUM }.
export async function readSegment(base, { crop = null, stride = 1, signal } = {}) {
  base = base.replace(/\/$/, '');
  const meta = (await getJSON(`${base}/meta.json`, signal)) || {};
  const lay = await tiffLayout(`${base}/x.tif`, signal);
  const [r0, r1, c0, c1] = crop || [0, lay.height, 0, lay.width];
  if (!(0 <= r0 && r0 < r1 && r1 <= lay.height && 0 <= c0 && c0 < c1 && c1 <= lay.width))
    throw new Error(`crop ${r0} ${r1} ${c0} ${c1} is outside the grid of ${lay.height} rows and ${lay.width} columns`);
  const ch = await Promise.all(['x', 'y', 'z'].map(async (k) => {
    const l = k === 'x' ? lay : await tiffLayout(`${base}/${k}.tif`, signal);
    return tiffRows(`${base}/${k}.tif`, l, r0, r1, c0, c1, signal);
  }));
  const H0 = r1 - r0, W0 = c1 - c0, h = Math.ceil(H0 / stride), w = Math.ceil(W0 / stride);
  const xyz = new Float64Array(h * w * 3), valid = new Uint8Array(h * w);
  for (let i = 0; i < h; i++) for (let j = 0; j < w; j++) {
    const s = i * stride * W0 + j * stride, k = i * w + j;
    const x = ch[0][s], y = ch[1][s], z = ch[2][s];
    xyz[3 * k] = x; xyz[3 * k + 1] = y; xyz[3 * k + 2] = z;
    valid[k] = Number.isFinite(x + y + z) && x > -0.5 && y > -0.5 && z > -0.5 && (Math.abs(x) + Math.abs(y) + Math.abs(z)) > 0 ? 1 : 0;
  }
  const m = /-(\d+(?:\.\d+)?)um\.tifxyz$/.exec(base);
  return { xyz, valid, h, w, meta, voxelUM: m ? +m[1] : null, grid: [lay.height, lay.width], crop: [r0, r1, c0, c1] };
}

// Bilinear refinement by an integer factor; a new node is valid when its cell's 4 corners are (kit sheetview's rule).
export function upsample(seg, f) {
  if (f <= 1) return seg;
  const { xyz, valid, h, w } = seg, H = (h - 1) * f + 1, W = (w - 1) * f + 1;
  const out = new Float64Array(H * W * 3), ok = new Uint8Array(H * W);
  for (let i = 0; i < H; i++) {
    const r = i / f, i0 = Math.min(Math.floor(r), h - 2), fr = r - i0;
    for (let j = 0; j < W; j++) {
      const c = j / f, j0 = Math.min(Math.floor(c), w - 2), fc = c - j0;
      const a = i0 * w + j0, b = a + 1, cc = a + w, d = cc + 1, k = i * W + j;
      ok[k] = valid[a] & valid[b] & valid[cc] & valid[d];
      for (let t = 0; t < 3; t++) {
        const q = (n) => (valid[n] ? xyz[3 * n + t] : 0);
        out[3 * k + t] = (1 - fr) * (1 - fc) * q(a) + (1 - fr) * fc * q(b) + fr * (1 - fc) * q(cc) + fr * fc * q(d);
      }
    }
  }
  return { ...seg, xyz: out, valid: ok, h: H, w: W };
}

// Unit normals, column step cross row step (numpy.gradient: central inside, one-sided at the edges); NaN at holes.
export function normals(seg) {
  const { xyz, valid, h, w } = seg, n = new Float64Array(h * w * 3).fill(NaN);
  const P = (i, j, t) => (valid[i * w + j] ? xyz[3 * (i * w + j) + t] : NaN);
  const grad = (i, j, t, alongCols) => {
    const L = alongCols ? w : h, p = alongCols ? j : i;
    const at = (q) => (alongCols ? P(i, q, t) : P(q, j, t));
    if (L < 2) return NaN;
    if (p === 0) return at(1) - at(0);
    if (p === L - 1) return at(L - 1) - at(L - 2);
    return (at(p + 1) - at(p - 1)) / 2;
  };
  for (let i = 0; i < h; i++) for (let j = 0; j < w; j++) {
    const u = [0, 1, 2].map((t) => grad(i, j, t, true)), v = [0, 1, 2].map((t) => grad(i, j, t, false));
    const c = [u[1] * v[2] - u[2] * v[1], u[2] * v[0] - u[0] * v[2], u[0] * v[1] - u[1] * v[0]];
    const L = Math.hypot(c[0], c[1], c[2]), k = 3 * (i * w + j);
    for (let t = 0; t < 3; t++) n[k + t] = c[t] / L;
  }
  return n;
}

// ------------------------------------------------------------------ zarr v2

let bloscCodec = null;
async function blosc() {
  if (!bloscCodec) bloscCodec = import(BLOSC_URL).then((m) => new m.Blosc());
  return bloscCodec;
}

const DTYPES = { '|u1': Uint8Array, '<u1': Uint8Array, '|i1': Int8Array, '<u2': Uint16Array, '<i2': Int16Array,
  '<u4': Uint32Array, '<i4': Int32Array, '<f4': Float32Array, '<f8': Float64Array };

// One level of an OME-Zarr (v2) volume: { shape, chunks, factor [z, y, x], chunk(cz, cy, cx) -> typed array or null }.
export async function openVolume(root, level = 0, { signal } = {}) {
  root = root.replace(/\/$/, '');
  const attrs = await getJSON(`${root}/.zattrs`, signal);
  const ds = attrs?.multiscales?.[0]?.datasets;
  let path = '', factor = [1, 1, 1];
  if (ds) {
    if (!(level >= 0 && level < ds.length)) throw new Error(`${root} has levels 0 to ${ds.length - 1}`);
    const sc = (d) => (d.coordinateTransformations || []).find((t) => t.type === 'scale')?.scale;
    const s0 = sc(ds[0]), sl = sc(ds[level]);
    factor = s0 && sl ? sl.slice(-3).map((v, i) => v / s0.slice(-3)[i]) : [2 ** level, 2 ** level, 2 ** level];
    path = ds[level].path;
  } else if (level) throw new Error(`${root} is one array, not a pyramid`);
  const meta = await getJSON(`${root}/${path ? path + '/' : ''}.zarray`, signal);
  if (!meta) throw new Error(`${root}: no zarr v2 array at level ${level} (zarr v3 volumes are not supported here yet)`);
  if (meta.shape.length !== 3) throw new Error(`${root}: level ${level} has ${meta.shape.length} axes; a scan volume has 3`);
  const T = DTYPES[meta.dtype];
  if (!T) throw new Error(`${root}: dtype ${meta.dtype} is not supported`);
  if (meta.filters?.length) throw new Error(`${root}: zarr filters are not supported`);
  const cid = meta.compressor?.id || null;
  if (cid && cid !== 'blosc') throw new Error(`${root}: compressor ${cid} is not supported (raw and blosc are)`);
  const sep = meta.dimension_separator || '.', pre = `${root}/${path ? path + '/' : ''}`;
  const n = meta.chunks[0] * meta.chunks[1] * meta.chunks[2];
  const stats = { chunks: 0, bytes: 0, absent: 0 };
  const chunk = async (cz, cy, cx) => {
    const r = await fetch(pre + [cz, cy, cx].join(sep), { signal });
    if (!r.ok) { stats.absent++; return null; }               // a missing chunk is the fill value
    let buf = new Uint8Array(await r.arrayBuffer());
    stats.chunks++; stats.bytes += buf.length;
    if (cid) buf = await (await blosc()).decode(buf);
    const a = new T(buf.buffer, buf.byteOffset, buf.byteLength / T.BYTES_PER_ELEMENT);
    if (a.length !== n) throw new Error(`chunk ${cz} ${cy} ${cx}: ${a.length} values, expected ${n}`);
    return a;
  };
  return { root, level, shape: meta.shape, chunks: meta.chunks, factor, dtype: meta.dtype, fill: meta.fill_value || 0,
    chunk, stats };
}

// ------------------------------------------------------------------ sampling

const rint = (x) => {                                          // numpy.rint: halves go to the even neighbor
  const f = Math.floor(x), d = x - f;
  return d > 0.5 ? f + 1 : d < 0.5 ? f : (f % 2 === 0 ? f : f + 1);
};

// Values on the sheet: Float32Array h*w, NaN at holes and where every sample is outside the volume.
export async function sampleSheet(seg, vol, { depth = 0, reduce = 'max', onProgress, concurrency = 12 } = {}) {
  if (!(depth >= 0)) throw new Error(`depth must be 0 or more voxels (got ${depth})`);
  if (reduce !== 'max' && reduce !== 'mean') throw new Error(`reduce must be max or mean (got ${reduce})`);
  const { xyz, valid, h, w } = seg, nrm = normals(seg), N = h * w;
  const step = Math.max(Math.max(...vol.factor), 1), K = Math.floor(depth / step + 1e-9);
  const offs = []; for (let k = -K; k <= K; k++) offs.push(k * step);
  const S = offs.length, [CZ, CY, CX] = vol.chunks, [SZ, SY, SX] = vol.shape, [fz, fy, fx] = vol.factor;
  const idx = new Int32Array(N * S * 3).fill(-1), groups = new Map();
  for (let p = 0; p < N; p++) {
    if (!valid[p]) continue;
    const nx = Number.isFinite(nrm[3 * p]) ? nrm[3 * p] : 0, ny = Number.isFinite(nrm[3 * p + 1]) ? nrm[3 * p + 1] : 0;
    const nz = Number.isFinite(nrm[3 * p + 2]) ? nrm[3 * p + 2] : 0;
    for (let s = 0; s < S; s++) {
      const z = rint((xyz[3 * p + 2] + offs[s] * nz) / fz), y = rint((xyz[3 * p + 1] + offs[s] * ny) / fy);
      const x = rint((xyz[3 * p] + offs[s] * nx) / fx);
      if (z < 0 || y < 0 || x < 0 || z >= SZ || y >= SY || x >= SX) continue;
      const q = 3 * (p * S + s); idx[q] = z; idx[q + 1] = y; idx[q + 2] = x;
      const key = `${Math.floor(z / CZ)},${Math.floor(y / CY)},${Math.floor(x / CX)}`;
      let g = groups.get(key); if (!g) groups.set(key, (g = []));
      g.push(p * S + s);
    }
  }
  const vals = new Float32Array(N * S).fill(NaN), keys = [...groups.keys()];
  let done = 0, next = 0;
  const worker = async () => {
    while (next < keys.length) {
      const key = keys[next++], [cz, cy, cx] = key.split(',').map(Number);
      const a = await vol.chunk(cz, cy, cx);
      for (const t of groups.get(key)) {
        const lz = idx[3 * t] - cz * CZ, ly = idx[3 * t + 1] - cy * CY, lx = idx[3 * t + 2] - cx * CX;
        vals[t] = a ? a[(lz * CY + ly) * CX + lx] : vol.fill;
      }
      groups.delete(key);                                      // the chunk is not needed again
      onProgress?.(++done, keys.length);
    }
  };
  await Promise.all(Array.from({ length: Math.min(concurrency, keys.length) }, worker));
  const out = new Float32Array(N).fill(NaN);
  for (let p = 0; p < N; p++) {
    if (!valid[p]) continue;
    let m = reduce === 'max' ? -Infinity : 0, c = 0;
    for (let s = 0; s < S; s++) {
      const v = vals[p * S + s]; if (Number.isNaN(v)) continue;
      if (reduce === 'max') { if (v > m) m = v; } else m += v;
      c++;
    }
    if (c) out[p] = reduce === 'max' ? m : m / c;
  }
  return { values: out, chunks: keys.length, samplesPerVertex: S };
}

// ------------------------------------------------------------------ mesh

// Triangles of the valid grid (two per cell whose 4 corners are valid) and compact positions and values.
export function sheetMesh(seg, values) {
  const { xyz, valid, h, w } = seg, index = new Int32Array(h * w).fill(-1);
  let nv = 0;
  for (let p = 0; p < h * w; p++) if (valid[p]) index[p] = nv++;
  const positions = new Float32Array(nv * 3), vals = new Float32Array(nv), uv = new Float32Array(nv * 2);
  for (let p = 0; p < h * w; p++) {
    const k = index[p]; if (k < 0) continue;
    positions.set(xyz.subarray(3 * p, 3 * p + 3), 3 * k);
    vals[k] = values[p]; uv[2 * k] = (p % w) / Math.max(w - 1, 1); uv[2 * k + 1] = Math.floor(p / w) / Math.max(h - 1, 1);
  }
  const tri = [];
  for (let i = 0; i < h - 1; i++) for (let j = 0; j < w - 1; j++) {
    const a = index[i * w + j], b = index[i * w + j + 1], c = index[(i + 1) * w + j], d = index[(i + 1) * w + j + 1];
    if (a >= 0 && b >= 0 && c >= 0 && d >= 0) tri.push(a, c, b, b, c, d);
  }
  return { positions, values: vals, uv, indices: Uint32Array.from(tri), vertices: nv, triangles: tri.length / 3 };
}

// ASCII VTK polydata with one point attribute: what Neuroglancer's vtk:// source reads (as kit sheetview writes).
export function toVTK(mesh, name = 'value') {
  const L = ['# vtk DataFile Version 3.0', 'unroll live sheet', 'ASCII', 'DATASET POLYDATA', `POINTS ${mesh.vertices} float`];
  for (let k = 0; k < mesh.vertices; k++)
    L.push(`${mesh.positions[3 * k].toFixed(2)} ${mesh.positions[3 * k + 1].toFixed(2)} ${mesh.positions[3 * k + 2].toFixed(2)}`);
  L.push(`POLYGONS ${mesh.triangles} ${4 * mesh.triangles}`);
  for (let t = 0; t < mesh.triangles; t++) L.push(`3 ${mesh.indices[3 * t]} ${mesh.indices[3 * t + 1]} ${mesh.indices[3 * t + 2]}`);
  L.push(`POINT_DATA ${mesh.vertices}`, `SCALARS ${name} float 1`, 'LOOKUP_TABLE default');
  for (let k = 0; k < mesh.vertices; k++) L.push(String(Number.isFinite(mesh.values[k]) ? +mesh.values[k].toPrecision(6) : 0));
  return L.join('\n') + '\n';
}

// Percentiles of the finite values (for a default contrast).
export function percentiles(values, ps) {
  const a = Float32Array.from(values.filter(Number.isFinite)).sort();
  if (!a.length) return ps.map(() => 0);
  return ps.map((p) => {
    const x = (p / 100) * (a.length - 1), i = Math.floor(x), f = x - i;
    return i + 1 < a.length ? a[i] * (1 - f) + a[i + 1] * f : a[i];
  });
}