Finds straight walls and door openings in a plan slice of a room scan and proposes them, with the rooms they close, for a person to accept.
How the precision is kept
A wall is a peak in a histogram of the slice's points with 20 mm cells, placed at the mean of the points in a 60 mm window; its ends are the first and last point of a run. The method's cell size and the scan's own noise set the accuracy. A cloud's slice is taken from the loader's 32-bit offsets, and the survey foot factor used for a cloud is rounded. Proposals are rounded to 0.1 mm.
Open item. Slice the cloud from 64-bit coordinates, and replace the survey foot factor 304.8006 with 1200 ÷ 3937 × 1000.
Calculations under this policy
11 calculations in 2 source files. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
Turns the slice's points by the walls' angle so that every wall runs along one of two axes.
u = x cos(−α) − y sin(−α); v = x sin(−α) + y cos(−α)
One rotation per point with Math.cos and Math.sin of the angle in radians, stored in Float64Arrays. Results are turned back with the opposite rotation.
scan-walls.js
lines 17 to 22
BimCraft 0.8.1
const c = Math.cos((-angle * Math.PI) / 180), s = Math.sin((-angle * Math.PI) / 180);
const u = new Float64Array(n), v = new Float64Array(n);
let u0 = Infinity, u1 = -Infinity, v0 = Infinity, v1 = -Infinity;
for (let i = 0; i < n; i++) {
const x = xy[2 * i], y = xy[2 * i + 1];
u[i] = x * c - y * s; v[i] = x * s + y * c;
Wall line from a histogram peak
64-bit
Finds where a wall lies across its direction: a peak in the histogram of the points, then the mean of the points in that peak.
peak: h_b ≥ h_b₋₁, h_b > h_b₊₁, three-cell sum ≥ 2 × minimum points; position = mean of the points in the three cells
The wall's position is the mean of the across coordinates of the points in a 60 mm window, added in point order. Peaks within 3 cells of a stronger one are taken as the same wall.
scan-walls.js
lines 29 to 47
BimCraft 0.8.1
const nb = Math.max(1, Math.ceil((p1 - p0) / cell) + 1), h = new Float64Array(nb);
const idx = (x) => Math.min(nb - 1, Math.max(0, Math.floor((x - p0) / cell)));
for (let i = 0; i < n; i++) h[idx(P[i])]++;
const peaks = [];
for (let b = 1; b < nb - 1; b++) { // a peak: a local maximum over a 3-cell window that holds enough points
const w = h[b - 1] + h[b] + h[b + 1];
if (h[b] >= h[b - 1] && h[b] > h[b + 1] && w >= minPoints * 2) peaks.push({ b, w });
}
peaks.sort((a, b2) => b2.w - a.w);
const used = [];
for (const pk of peaks) {
if (used.some((q) => Math.abs(q - pk.b) <= 3)) continue; // one wall per 8 cm: a thick wall's second face is the same wall
used.push(pk.b);
const lo = p0 + (pk.b - 1) * cell, hi = p0 + (pk.b + 2) * cell;
const own = [];
let sum = 0, k = 0;
for (let i = 0; i < n; i++) if (P[i] >= lo && P[i] < hi) { own.push(Q[i]); sum += P[i]; k++; }
if (k < minPoints) continue;
const mid = sum / k;
Wall runs and their ends
64-bit
Splits the points on a wall line into runs and keeps the runs that are long, thin and denser than what lies beside them.
split at gaps > 450 mm; keep when length ≥ 800 mm, min(side counts) ≤ 0.25 × count, core density ≥ 3 × side density
A run's ends are the along-wall coordinates of its first and last point, so a wall's length is as fine as the scan's point spacing at its ends. The tests compare point counts in bands 4 to 10 cells to each side.
scan-walls.js
lines 50 to 63
BimCraft 0.8.1
let start = own[0], prev = own[0], count = 1;
const flush = (end) => {
if (end - start < minLen || count < minPoints) return;
// thin: a wall has an empty side (outside the building); a table or a sofa has points on both. Count the points in the bands 4–10 cells to each side along the run.
let left = 0, right = 0;
for (let i = 0; i < n; i++) {
if (Q[i] < start || Q[i] > end) continue;
if (P[i] >= lo - 10 * cell && P[i] < lo - 3 * cell) left++; else if (P[i] >= hi + 3 * cell && P[i] < hi + 10 * cell) right++;
}
if (Math.min(left, right) > 0.25 * count) return;
// and denser than what is beside it: the edge of a filled blob (a table, a sofa) is a histogram peak too, but its dense side is as dense as the edge
const core = count / (3 * cell), side = Math.max(left, right) / (7 * cell);
if (core < 3 * side) return;
walls.push({ across: mid, from: start, to: end, points: count, dir });
Door gaps
64-bit
Finds a door where two wall runs on one line are a door's width apart.
gap = second.from − first.to; door when 600 ≤ gap ≤ 1300; width = Math.round(gap)
The door's width is rounded to a whole millimeter. Two runs count as one line when their positions differ by at most 4 cells (80 mm), and the door sits at the average of the two.
scan-walls.js
lines 80 to 83
BimCraft 0.8.1
const first = A.from < B.from ? A : B, second = first === A ? B : A, gap = second.from - first.to;
if (gap >= doorMin && gap <= doorMax) {
const mid = (first.to + second.from) / 2, across = (A.across + B.across) / 2;
doors.push({ wall: i, at: A.dir === 'y' ? back(across, mid) : back(mid, across), width: Math.round(gap) });
scan-propose.jsBimCraft 0.8.1 32-bit in part7 calculationsReviewed
Tests tools/bimcraft-test/scan-propose-test.mjs
Plan slice of a scanned mesh
64-bit
Finds where a horizontal plane cuts each triangle of a mesh and samples points along the cut.
f = (z_cut − z_a) ÷ (z_b − z_a); samples every 20 mm along each cut segment
Cut points are linear interpolations along triangle edges, computed in 64-bit from the mesh's positions as they are given, and stored in a Float64Array. The samples are the input of the wall finder, which works with 20 mm cells.
scan-propose.js
lines 29 to 52
BimCraft 0.8.1
export function meshSlice(solids, { cutZ = 1200, step = 20 } = {}) {
const pts = [];
for (const s of solids || []) {
const P = s.positions, I = s.indices;
for (let t = 0; t + 2 < I.length; t += 3) {
const z = [P[3 * I[t] + 2], P[3 * I[t + 1] + 2], P[3 * I[t + 2] + 2]];
if ((z[0] > cutZ && z[1] > cutZ && z[2] > cutZ) || (z[0] < cutZ && z[1] < cutZ && z[2] < cutZ)) continue;
const hit = [];
for (let e = 0; e < 3; e++) {
const i = I[t + e], j = I[t + (e + 1) % 3], za = P[3 * i + 2], zb = P[3 * j + 2];
if ((za - cutZ) * (zb - cutZ) < 0 || (za === cutZ) !== (zb === cutZ) && (za === cutZ || zb === cutZ)) {
const f = zb === za ? 0 : (cutZ - za) / (zb - za);
if (f >= 0 && f <= 1) hit.push([P[3 * i] + f * (P[3 * j] - P[3 * i]), P[3 * i + 1] + f * (P[3 * j + 1] - P[3 * i + 1])]);
}
}
if (hit.length < 2) continue;
const [a, b] = hit, L = Math.hypot(b[0] - a[0], b[1] - a[1]), k = Math.max(1, Math.ceil(L / step));
for (let m = 0; m <= k; m++) pts.push(a[0] + (b[0] - a[0]) * m / k, a[1] + (b[1] - a[1]) * m / k);
if (pts.length > 4_000_000) break;
}
}
const n = pts.length / 2;
return { xy: Float64Array.from(pts), n };
}
Plan slice of a point cloud
32-bit in part
Takes the cloud's points in a band above the floor as the plan slice, in millimeters from the cloud's origin.
k = 304.8 for feet, 304.8006 for US survey feet, 1000 otherwise
The positions passed on are cloud.pos, the Float32Array of offsets that pointcloud.js keeps. The US survey foot factor is written as 304.8006; the defining value is 1200 ÷ 3937 × 1000 = 304.800609601… mm.
scan-propose.js
lines 54 to 60
BimCraft 0.8.1
export function cloudSlice(cloud, { above = 1200, thick = 100, max = 200000 } = {}) {
const k = cloud.unit === 'ft' ? 304.8 : cloud.unit === 'ftUS' ? 304.8006 : 1000;
const M = [k, 0, 0, 0, 0, k, 0, 0, 0, 0, k, 0, 0, 0, 0, 1]; // positions are relative to the cloud's own origin, in its unit → mm
const floor = floorZ(cloud.pos, cloud.n, M);
const s = slicePoints(cloud.pos, cloud.n, M, { cutZ: (floor ?? 0) + above, thick, max });
return { xy: s.xy, n: s.n, floor: floor ?? 0, total: s.total };
}
Runs joined across doors and outside walls moved to their middle
64-bit
Joins two runs on one line with a door between them into one wall, and moves a wall that has points on one side only half its thickness outward.
c = (c₁ + c₂) ÷ 2; outside when the emptier side has < 15% of the other's points; c ← c ± thickness ÷ 2
The scan shows a wall's face, so the half-thickness move depends on the thickness given (150 mm unless set), not on a measured one. Points between 60 and 1500 mm from the line are counted on each side.
scan-propose.js
lines 87 to 101
BimCraft 0.8.1
const prev = walls.find((w) => w.dir === r.dir && Math.abs(w.c - r.c) < 100 && doors.some((d) => d.dir === r.dir && Math.abs(d.c - w.c) < 100 && d.along - d.width / 2 >= w.hi - 40 && d.along + d.width / 2 <= r.lo + 40));
if (prev) { prev.hi = r.hi; prev.points += r.points; prev.c = (prev.c + r.c) / 2; } else walls.push({ ...r });
}
// the scan shows a wall's visible face: move an outside wall (one side empty) half its thickness outward, to its middle
for (const w of walls) {
let a = 0, b = 0;
const P = w.dir === 'x' ? V : U, Q = w.dir === 'x' ? U : V;
for (let i = 0; i < n; i++) {
if (Q[i] < w.lo || Q[i] > w.hi) continue;
const d = P[i] - w.c;
if (d > 60 && d < 1500) a++; else if (d < -60 && d > -1500) b++;
}
const lo = Math.min(a, b), hi = Math.max(a, b);
w.shift = hi > 20 && lo < 0.15 * hi ? (a < b ? 1 : -1) : 0; // + toward the side with fewer points (the outside)
w.c += w.shift * thickness / 2;
Wall ends snapped to corners
64-bit
Moves a wall's end onto the line of a perpendicular wall when it is within the snap distance.
end ← c_other when |c_other − end| ≤ 350 mm
The end takes the other wall's position exactly, so the corner is closed with no gap. The nearest wall within the snap distance wins.
scan-propose.js
lines 107 to 114
BimCraft 0.8.1
const e = end ? w.hi : w.lo;
let best = null;
for (const q of walls) {
if (q.dir === w.dir) continue;
const d = Math.abs(q.c - e);
if (d <= snap && w.c >= q.lo - snap && w.c <= q.hi + snap && (!best || d < best.d)) best = { d, c: q.c };
}
if (best) { if (end) w.hi = best.c; else w.lo = best.c; w.ends[end] = true; }
Proposed wall coordinates
64-bit
Turns each wall back into the slice's own axes and writes its two ends.
a, b = round(coordinate × 10) ÷ 10
The ends are rotated back by the walls' angle and rounded to 0.1 mm. A run shorter than the wall thickness is not proposed.
Rotate the slice square, histogram the points across each of the two wall directions, take peaks as walls and split each into runs at gaps over 450 mm; a gap of 600 to 1300 mm between two runs on one line is a door. Outside walls move half a thickness outward; ends within 350 mm of a perpendicular wall snap to it.
Number types
Slice points: Float64Array in millimeters. A cloud's positions: Float32Array of offsets from its origin (pointcloud.js). Histograms: Float64Array of counts.
Tolerances
cell 20 mm; minimum wall length 800 mm and 25 points; gap 450 mm; door 600 to 1300 mm; runs on one line when within 100 mm; corner snap 350 mm; wall thickness 150 mm unless given.
Limits
Only walls parallel to two perpendicular directions are found. The file's header says it has been run on generated scans and not on a real phone scan.
Approach: 32-bit step, flagged
One step stores or exchanges 32-bit values that reach a number a person reads. It is listed here with its open item, and the step is either moved to 64-bit or the app will warn where the number is read.