From bc2821adb11a30244fc4663f4fafb756877d9508 Mon Sep 17 00:00:00 2001 From: Yasutake Yohei <61961825+yasutakeyohei@users.noreply.github.com> Date: Wed, 7 Oct 2026 23:09:40 +0900 Subject: bluebey-studio: public/ の外へ移動し非公開化 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- bluebey-studio/src/trace.js | 410 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 410 insertions(+) create mode 100644 bluebey-studio/src/trace.js (limited to 'bluebey-studio/src/trace.js') diff --git a/bluebey-studio/src/trace.js b/bluebey-studio/src/trace.js new file mode 100644 index 0000000..9b61d6d --- /dev/null +++ b/bluebey-studio/src/trace.js @@ -0,0 +1,410 @@ +/** + * Zero-dependency marching-squares contour tracer. + * + * Runs unchanged in the browser and in Node: the module has no imports at all, + * never touches the DOM and never writes to the console. + * + * Coordinate system + * ----------------- + * Pixel (x, y) is the unit square whose top-left corner sits at (x, y), so the + * centre of pixel (x, y) is at (x + 0.5, y + 0.5) and y grows downwards + * (row 0 is the top row of the input). + * + * Contours + * -------- + * Every returned contour is a *closed* polyline of sub-pixel points; the first + * point is not repeated at the end. Contours are oriented so that the inside of + * the shape (the region where the sample is at or above the threshold) lies to + * the left of the direction of travel. See `contourArea` for the sign this + * implies. + */ + +const EDGE_TOP = 0; +const EDGE_RIGHT = 1; +const EDGE_BOTTOM = 2; +const EDGE_LEFT = 3; + +/** + * Directed segments emitted by each unambiguous marching-squares case. + * + * The case index is built from the cell corners as + * `tl | tr << 1 | br << 2 | bl << 3`. Entries are flat `[from, to, from, to]` + * pairs of edge ids; the direction keeps the inside region on the left. + */ +const CELL_SEGMENTS = [ + null, // 0 - nothing inside + [EDGE_LEFT, EDGE_TOP, -1, -1], // 1 - top-left only + [EDGE_TOP, EDGE_RIGHT, -1, -1], // 2 - top-right only + [EDGE_LEFT, EDGE_RIGHT, -1, -1], // 3 - top row + [EDGE_RIGHT, EDGE_BOTTOM, -1, -1], // 4 - bottom-right only + null, // 5 - saddle (top-left + bottom-right) + [EDGE_TOP, EDGE_BOTTOM, -1, -1], // 6 - right column + [EDGE_LEFT, EDGE_BOTTOM, -1, -1], // 7 - everything but bottom-left + [EDGE_BOTTOM, EDGE_LEFT, -1, -1], // 8 - bottom-left only + [EDGE_BOTTOM, EDGE_TOP, -1, -1], // 9 - left column + null, // 10 - saddle (top-right + bottom-left) + [EDGE_BOTTOM, EDGE_RIGHT, -1, -1], // 11 - everything but bottom-right + [EDGE_RIGHT, EDGE_LEFT, -1, -1], // 12 - bottom row + [EDGE_RIGHT, EDGE_TOP, -1, -1], // 13 - everything but top-right + [EDGE_TOP, EDGE_LEFT, -1, -1], // 14 - everything but top-left + null, // 15 - everything inside +]; + +// Case 5 (top-left + bottom-right inside). When the centre of the cell is +// inside, the two inside corners are joined through the middle and the two +// outside corners are separated; otherwise the inside corners are separated. +const SADDLE_5_CONNECTED = [EDGE_LEFT, EDGE_BOTTOM, EDGE_RIGHT, EDGE_TOP]; +const SADDLE_5_SPLIT = [EDGE_LEFT, EDGE_TOP, EDGE_RIGHT, EDGE_BOTTOM]; + +// Case 10 (top-right + bottom-left inside): the mirror image of case 5. +const SADDLE_10_CONNECTED = [EDGE_TOP, EDGE_LEFT, EDGE_BOTTOM, EDGE_RIGHT]; +const SADDLE_10_SPLIT = [EDGE_TOP, EDGE_RIGHT, EDGE_BOTTOM, EDGE_LEFT]; + +const DUPLICATE_EPS = 1e-9; + +/** + * Signed area of a closed polyline, via the shoelace formula. The polyline is + * implicitly closed (the last point is joined back to the first), so an open + * ring is fine. + * + * Sign convention: this is the plain shoelace sum `Σ (x_i·y_{i+1} − x_{i+1}·y_i) / 2` + * evaluated in the tracer's y-down pixel coordinates. A ring that runs + * clockwise *as seen on screen* is therefore positive, and a counter-clockwise + * one is negative. Because `traceAlphaContours` keeps the inside on the left, + * the outer boundary of a filled region comes out negative and a hole in it + * comes out positive. + * + * @param {Array<{x: number, y: number}>} points + * @returns {number} signed area in square pixels + */ +export function contourArea(points) { + const n = points.length; + if (!points || n < 3) return 0; + let sum = 0; + for (let i = 0; i < n; i++) { + const a = points[i]; + const b = i + 1 === n ? points[0] : points[i + 1]; + sum += a.x * b.y - b.x * a.y; + } + return sum / 2; +} + +/** + * Build an SVG path `d` attribute with one closed subpath per contour. + * + * `mapPoint(x, y)` returns the `[X, Y]` pair written to the output, which is + * what makes it possible to flip the y axis or apply a scale without touching + * the tracer. Coordinates are rounded to `decimals` places. + * + * @param {Array>} contours + * @param {(x: number, y: number) => [number, number]} mapPoint + * @param {number} [decimals] + * @returns {string} + */ +export function contoursToPathData(contours, mapPoint, decimals = 2) { + const places = Math.max(0, Math.floor(decimals)); + const factor = Math.pow(10, places); + const parts = []; + for (let c = 0; c < contours.length; c++) { + const points = contours[c]; + if (!points || points.length < 2) continue; + for (let i = 0; i < points.length; i++) { + const mapped = mapPoint(points[i].x, points[i].y); + // Rounding before formatting keeps `-0.00` out of the output. + const rx = Math.round(mapped[0] * factor) / factor; + const ry = Math.round(mapped[1] * factor) / factor; + parts.push((i === 0 ? 'M' : 'L') + rx.toFixed(places) + ' ' + ry.toFixed(places)); + } + parts.push('Z'); + } + return parts.join(' '); +} + +// --- closed-ring simplification helpers ------------------------------------ + +/** Drop points that repeat their predecessor (including across the wrap). */ +function removeConsecutiveDuplicates(points) { + const out = []; + for (let i = 0; i < points.length; i++) { + const p = points[i]; + const last = out[out.length - 1]; + if (last && Math.abs(last.x - p.x) <= DUPLICATE_EPS && Math.abs(last.y - p.y) <= DUPLICATE_EPS) { + continue; + } + out.push(p); + } + while (out.length > 1) { + const first = out[0]; + const last = out[out.length - 1]; + if (Math.abs(first.x - last.x) <= DUPLICATE_EPS && Math.abs(first.y - last.y) <= DUPLICATE_EPS) { + out.pop(); + } else { + break; + } + } + return out; +} + +/** Drop points that sit on the straight segment between their two neighbours. */ +function removeCollinear(points) { + let list = points; + let changed = true; + while (changed && list.length > 3) { + changed = false; + const n = list.length; + const out = []; + for (let i = 0; i < n; i++) { + const a = list[i === 0 ? n - 1 : i - 1]; + const b = list[i]; + const c = list[i + 1 === n ? 0 : i + 1]; + const abx = b.x - a.x; + const aby = b.y - a.y; + const bcx = c.x - b.x; + const bcy = c.y - b.y; + const cross = abx * bcy - aby * bcx; + // |cross| / (|ab| * |bc|) is sin(turn angle); a small value means a + // straight-through point, which carries no shape information. + const scale = Math.sqrt((abx * abx + aby * aby) * (bcx * bcx + bcy * bcy)); + const straight = scale <= DUPLICATE_EPS || Math.abs(cross) <= 1e-9 * scale; + if (straight && abx * bcx + aby * bcy >= 0) { + changed = true; + } else { + out.push(b); + } + } + list = out; + } + return list; +} + +/** + * Iterative Douglas–Peucker for an *open* polyline. The two end points are + * always kept; the recursion uses an explicit stack so long contours cannot + * overflow the call stack. + */ +function douglasPeucker(points, tolerance) { + const n = points.length; + if (n <= 2) return points.slice(); + const keep = new Uint8Array(n); + keep[0] = 1; + keep[n - 1] = 1; + const stack = [0, n - 1]; + while (stack.length > 0) { + const i1 = stack.pop(); + const i0 = stack.pop(); + if (i1 <= i0 + 1) continue; + const a = points[i0]; + const b = points[i1]; + const dx = b.x - a.x; + const dy = b.y - a.y; + const len = Math.sqrt(dx * dx + dy * dy); + let maxDistance = -1; + let maxIndex = -1; + if (len <= DUPLICATE_EPS) { + // Degenerate segment: fall back to the distance from the anchor point. + for (let i = i0 + 1; i < i1; i++) { + const px = points[i].x - a.x; + const py = points[i].y - a.y; + const d = Math.sqrt(px * px + py * py); + if (d > maxDistance) { + maxDistance = d; + maxIndex = i; + } + } + } else { + for (let i = i0 + 1; i < i1; i++) { + const p = points[i]; + const d = Math.abs(dy * (p.x - a.x) - dx * (p.y - a.y)) / len; + if (d > maxDistance) { + maxDistance = d; + maxIndex = i; + } + } + } + if (maxDistance > tolerance && maxIndex > i0) { + keep[maxIndex] = 1; + stack.push(i0, maxIndex, maxIndex, i1); + } + } + const out = []; + for (let i = 0; i < n; i++) { + if (keep[i]) out.push(points[i]); + } + return out; +} + +/** + * Simplify a closed ring, wrap-around segment included. + * + * The ring is cut at the point farthest from `points[0]`, which gives two open + * polylines that together cover every segment of the loop exactly once; each + * half is then simplified with Douglas–Peucker and the halves are stitched + * back together (without duplicating the shared anchors). + */ +function simplifyClosedRing(points, tolerance) { + const n = points.length; + if (n <= 3) return points.slice(); + let far = 0; + let farDistance = -1; + const first = points[0]; + for (let i = 1; i < n; i++) { + const dx = points[i].x - first.x; + const dy = points[i].y - first.y; + const d = dx * dx + dy * dy; + if (d > farDistance) { + farDistance = d; + far = i; + } + } + // A ring whose points all coincide carries no shape; leave it to minArea. + if (far <= 0 || farDistance <= DUPLICATE_EPS) return points.slice(); + + const head = douglasPeucker(points.slice(0, far + 1), tolerance); + const tail = douglasPeucker(points.slice(far).concat([first]), tolerance); + + // `head` ends and `tail` starts on the same anchor, and both end on + // `points[0]`; drop the duplicated join so every point appears once. + return head.slice(0, -1).concat(tail.slice(0, -1)); +} + +/** + * Trace the iso-contour of a scalar field at `options.threshold`. + * + * @param {ArrayLike} alpha width*height samples, row-major, row 0 on top + * @param {number} width + * @param {number} height + * @param {object} [options] + * @param {number} [options.threshold=0.5] inside when `alpha/255 >= threshold` + * @param {number} [options.simplifyTolerance=0.35] Douglas-Peucker tolerance, px + * @param {number} [options.minArea=2] drop rings smaller than this, px² + * @returns {Array>} + */ +export function traceAlphaContours(alpha, width, height, options = {}) { + const threshold = options.threshold ?? 0.5; + const tolerance = options.simplifyTolerance ?? 0.35; + const minArea = options.minArea ?? 2; + + const w = Math.floor(width); + const h = Math.floor(height); + if (!alpha || w < 1 || h < 1 || alpha.length < w * h) return []; + if (w < 2 && h < 2) return []; + + // Work on a signed field, padded with a 1px outside border: `s >= 0` is + // inside. The padding guarantees every crossing is strictly interior, so the + // marching always yields closed rings and never touches the array edges. + // The border holds the same value a fully transparent pixel maps to, which + // makes shapes that run off the image close exactly on the image edge. + const pw = w + 2; + const ph = h + 2; + const s = new Float32Array(pw * ph); + s.fill(-threshold); + for (let y = 0; y < h; y++) { + const src = y * w; + const dst = (y + 1) * pw + 1; + for (let x = 0; x < w; x++) s[dst + x] = alpha[src + x] / 255 - threshold; + } + const sample = (x, y) => s[y * pw + x]; + + // Crossing points, keyed by the grid edge they sit on. Both cells sharing an + // edge call these with the same sample pair in the same order (top→bottom, + // left→right), so the coordinates come out bit-identical and can be matched + // by key alone. + const points = new Map(); + function crossing(key, a, b, x0, y0, dx, dy) { + let p = points.get(key); + if (p === undefined) { + const t = a / (a - b); + p = { x: x0 + dx * t, y: y0 + dy * t }; + points.set(key, p); + } + return p; + } + // Horizontal edge of the padded grid at row `py`, spanning columns px..px+1. + const hKey = (px, py) => `h:${px}:${py}`; + const hPoint = (px, py) => crossing(hKey(px, py), sample(px, py), sample(px + 1, py), px - 0.5, py - 0.5, 1, 0); + // Vertical edge of the padded grid at column `px`, spanning rows py..py+1. + const vKey = (px, py) => `v:${px}:${py}`; + const vPoint = (px, py) => crossing(vKey(px, py), sample(px, py), sample(px, py + 1), px - 0.5, py - 0.5, 0, 1); + + const edgeKey = [ + (px, py) => hKey(px, py), // EDGE_TOP + (px, py) => vKey(px + 1, py), // EDGE_RIGHT + (px, py) => hKey(px, py + 1), // EDGE_BOTTOM + (px, py) => vKey(px, py), // EDGE_LEFT + ]; + const edgePoint = [ + (px, py) => hPoint(px, py), // EDGE_TOP + (px, py) => vPoint(px + 1, py), // EDGE_RIGHT + (px, py) => hPoint(px, py + 1), // EDGE_BOTTOM + (px, py) => vPoint(px, py), // EDGE_LEFT + ]; + + // Directed segments: `from` -> `to`, inside region on the left of travel. + const fromKeys = []; + const toKeys = []; + const fromPoints = []; + + for (let py = 0; py < ph - 1; py++) { + for (let px = 0; px < pw - 1; px++) { + const tl = sample(px, py); + const tr = sample(px + 1, py); + const br = sample(px + 1, py + 1); + const bl = sample(px, py + 1); + const inside = (v) => (v >= 0 ? 1 : 0); + const code = inside(tl) | (inside(tr) << 1) | (inside(br) << 2) | (inside(bl) << 3); + let segments = CELL_SEGMENTS[code]; + if (code === 5) { + // With the cell centre inside, the two inside corners join through the + // middle; otherwise each is cut off on its own. + segments = (tl + tr + br + bl) / 4 >= 0 ? SADDLE_5_CONNECTED : SADDLE_5_SPLIT; + } else if (code === 10) { + segments = (tl + tr + br + bl) / 4 >= 0 ? SADDLE_10_CONNECTED : SADDLE_10_SPLIT; + } + if (!segments) continue; + for (let i = 0; i < segments.length; i += 2) { + const a = segments[i]; + const b = segments[i + 1]; + if (a < 0 || b < 0) continue; // padding of the single-segment cases + fromKeys.push(edgeKey[a](px, py)); + fromPoints.push(edgePoint[a](px, py)); + toKeys.push(edgeKey[b](px, py)); + edgePoint[b](px, py); // make sure the shared crossing exists + } + } + } + + // Every crossing has exactly one incoming and one outgoing segment, so the + // segments can be walked into closed rings without any ambiguity. + const outgoing = new Map(); + for (let i = 0; i < fromKeys.length; i++) outgoing.set(fromKeys[i], i); + + const segmentCount = fromKeys.length; + const used = new Uint8Array(segmentCount); + const contours = []; + + for (let start = 0; start < segmentCount; start++) { + if (used[start]) continue; + const ring = []; + let current = start; + for (let guard = 0; guard <= segmentCount; guard++) { + used[current] = 1; + ring.push(fromPoints[current]); + const next = outgoing.get(toKeys[current]); + if (next === undefined || next === start) break; + if (used[next]) break; + current = next; + } + if (ring.length >= 3) contours.push(ring); + } + + const result = []; + for (let i = 0; i < contours.length; i++) { + let ring = removeConsecutiveDuplicates(contours[i]); + ring = simplifyClosedRing(ring, tolerance); + ring = removeCollinear(ring); + if (ring.length < 3) continue; + if (Math.abs(contourArea(ring)) < minArea) continue; + result.push(ring); + } + return result; +} \ No newline at end of file -- cgit v1.3.1