Polygon mesh: normals, areas, triangles and volume
The normal, area, center and flatness of a mesh face, the triangles the mesh is cut into, and the area and volume reported for a mesh.
How the precision is kept
Mesh vertex positions are a Float64Array, three numbers per vertex in meters, and every measure here reads them directly in 64-bit. Face normals are Newell sums about the origin; the mesh's area is summed from triangle edge vectors and its volume from signed tetrahedra about the origin.
Calculations under this policy
7 calculations in 1 source file. 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.
Read from the Float64Array and summed corner by corner in three 64-bit accumulators. Each term multiplies a coordinate difference by a coordinate sum, so far from the origin the terms are much larger than the result.
m3d/mesh.js
lines 495 to 508
CadCraft 0.8.2
/** Newell normal of face f (not unit: its length is twice the area) into out. */
faceNormalRaw(f, out = [0, 0, 0]) {
const P = this.P, hV = this.hV, nx = this.hNx, h0 = this.fHe[f];
let x = 0, y = 0, z = 0, h = h0, g = 0;
do {
const a = hV[h] * 3, b = hV[nx[h]] * 3;
x += (P[a + 1] - P[b + 1]) * (P[a + 2] + P[b + 2]);
y += (P[a + 2] - P[b + 2]) * (P[a] + P[b]);
z += (P[a] - P[b]) * (P[a + 1] + P[b + 1]);
h = nx[h];
} while (h !== h0 && ++g < LIMITS.faceCorners);
out[0] = x; out[1] = y; out[2] = z;
return out;
}
Unit normal of a mesh face
64-bit
The direction a mesh face points.
n = N ÷ |N|
Divides by Math.hypot of the Newell vector; a zero vector is returned as zero, not divided.
Half the length of the Newell vector. For a flat face this is its area; for a face that is not flat it is the area of the face's shadow on the plane square to that vector, which is no larger than the sum of its triangles used in the mesh totals.
The plain mean of the corners, added in order and divided once. For a triangle this is the area centroid; for other faces it need not be.
m3d/mesh.js
lines 511 to 517
CadCraft 0.8.2
faceCenter(f, out = [0, 0, 0]) {
const P = this.P, hV = this.hV, nx = this.hNx, h0 = this.fHe[f];
let x = 0, y = 0, z = 0, n = 0, h = h0;
do { const a = hV[h] * 3; x += P[a]; y += P[a + 1]; z += P[a + 2]; n++; h = nx[h]; } while (h !== h0 && n < LIMITS.faceCorners);
out[0] = x / n; out[1] = y / n; out[2] = z / n;
return out;
}
Is a mesh face flat
64-bit
Whether every corner of a face lies in one plane, which decides if it stays one face or becomes triangles.
|(p − c) · n| ≤ tol, tol = 1e-6 m by default
Each corner's distance from the plane through the corner mean with the unit Newell normal is compared with an absolute tolerance, the same for a face of any size.
m3d/mesh.js
lines 518 to 524
CadCraft 0.8.2
/** Is face f flat within tol (metres)? */
facePlanar(f, tol = 1e-6) {
const n = this.faceNormal(f), c = this.faceCenter(f), P = this.P, hV = this.hV, nx = this.hNx, h0 = this.fHe[f];
let h = h0, g = 0;
do { const a = hV[h] * 3; if (Math.abs((P[a] - c[0]) * n[0] + (P[a + 1] - c[1]) * n[1] + (P[a + 2] - c[2]) * n[2]) > tol) return false; h = nx[h]; } while (h !== h0 && ++g < LIMITS.faceCorners);
return true;
}
Triangles of a mesh
64-bit
The triangles every face is cut into for area, volume, ray tests and drawing.
Triangles pass through; a quad is split along the diagonal for which both halves face the Newell normal, tested against zero with no tolerance. Larger faces are projected onto two axes in their plane (dot products with full coordinates) and ear clipped, and each triangle's winding is fixed with the same sign test. A face with a zero Newell vector is fanned from its first corner.
m3d/mesh.js
lines 525 to 572
CadCraft 0.8.2
/**
* Triangles of every face that shows (not dead; hidden ones too when `hidden`): {tri: Int32Array of corners (3 per
* triangle), face: Int32Array (the face of each triangle), n}. Triangles and quads directly (a concave quad split
* through its dent), bigger faces by ear clipping in their plane.
*/
triangulate({ hidden = false } = {}) {
let est = 0;
for (let f = 0; f < this.nf; f++) { const fl = this.fFl[f]; if (fl & FL_DEAD || (!hidden && fl & FL_HIDE)) continue; est += this.faceSize(f) - 2; }
const tri = new Int32Array(est * 3), face = new Int32Array(est);
const P = this.P, hV = this.hV, nx = this.hNx, nrm = [0, 0, 0], cs = [];
let k = 0;
const up = (a, b, c) => {
const A = hV[a] * 3, B = hV[b] * 3, C = hV[c] * 3;
const ux = P[B] - P[A], uy = P[B + 1] - P[A + 1], uz = P[B + 2] - P[A + 2], vx = P[C] - P[A], vy = P[C + 1] - P[A + 1], vz = P[C + 2] - P[A + 2];
return (uy * vz - uz * vy) * nrm[0] + (uz * vx - ux * vz) * nrm[1] + (ux * vy - uy * vx) * nrm[2] > 0;
};
const put = (f, a, b, c) => { tri[k * 3] = a; tri[k * 3 + 1] = b; tri[k * 3 + 2] = c; face[k++] = f; };
for (let f = 0; f < this.nf; f++) {
const fl = this.fFl[f];
if (fl & FL_DEAD || (!hidden && fl & FL_HIDE)) continue;
const h0 = this.fHe[f], h1 = nx[h0], h2 = nx[h1], h3 = nx[h2];
if (h3 === h0) { put(f, h0, h1, h2); continue; }
this.faceNormalRaw(f, nrm);
if (nx[h3] === h0) {
if (up(h0, h1, h2) && up(h0, h2, h3)) { put(f, h0, h1, h2); put(f, h0, h2, h3); continue; }
if (up(h1, h2, h3) && up(h1, h3, h0)) { put(f, h1, h2, h3); put(f, h1, h3, h0); continue; }
}
this.faceCorners(f, cs);
const l = Math.hypot(nrm[0], nrm[1], nrm[2]);
if (!(l > 0)) { for (let i = 1; i + 1 < cs.length; i++) put(f, cs[0], cs[i], cs[i + 1]); continue; }
// a frame in the face's plane
const n = [nrm[0] / l, nrm[1] / l, nrm[2] / l];
const ax = Math.abs(n[0]) < 0.9 ? [1, 0, 0] : [0, 1, 0];
let ux = n[1] * ax[2] - n[2] * ax[1], uy = n[2] * ax[0] - n[0] * ax[2], uz = n[0] * ax[1] - n[1] * ax[0];
const ul = Math.hypot(ux, uy, uz); ux /= ul; uy /= ul; uz /= ul;
const vx = n[1] * uz - n[2] * uy, vy = n[2] * ux - n[0] * uz, vz = n[0] * uy - n[1] * ux;
const flat = new Array(cs.length * 2);
for (let i = 0; i < cs.length; i++) { const a = hV[cs[i]] * 3; flat[i * 2] = P[a] * ux + P[a + 1] * uy + P[a + 2] * uz; flat[i * 2 + 1] = P[a] * vx + P[a + 1] * vy + P[a + 2] * vz; }
const ts = earcut(flat);
let made = 0;
for (let i = 0; i + 2 < ts.length && made < cs.length - 2; i += 3, made++) {
const a = cs[ts[i]], b = cs[ts[i + 1]], c = cs[ts[i + 2]];
if (up(a, b, c)) put(f, a, b, c); else put(f, a, c, b);
}
for (; made < cs.length - 2; made++) put(f, cs[0], cs[0], cs[0]); // a degenerate face: keep the count, draw nothing
}
return { tri, face, n: k };
}
Area and volume of a mesh
64-bit
The surface area of a mesh and, when it is closed, the volume it encloses.
A = Σ |u × v| ÷ 2; V = Σ a · (b × c) ÷ 6
Area uses each triangle's two edge vectors, so it does not depend on the distance from the origin. Volume multiplies full coordinates (signed tetrahedra from the origin) and is added in triangle order, so for a mesh far from the origin the terms cancel. Volume is returned only when no edge is open.
m3d/mesh.js
lines 628 to 644
CadCraft 0.8.2
/** {verts, faces, edges, boundary (edges with one face), loose (vertices with none), closed, area, volume (closed only), tris}. */
info() {
let boundary = 0, area = 0, vol = 0;
for (let h = 0; h < this.nh; h++) if (!this.heDead(h) && this.hTw[h] < 0) boundary++;
let loose = 0;
for (let v = 0; v < this.nv; v++) if (!this.vertDead(v) && this.vHe[v] < 0) loose++;
const T = this.triangulate({ hidden: true }), P = this.P, hV = this.hV;
for (let i = 0; i < T.n; i++) {
const a = hV[T.tri[i * 3]] * 3, b = hV[T.tri[i * 3 + 1]] * 3, c = hV[T.tri[i * 3 + 2]] * 3;
const ux = P[b] - P[a], uy = P[b + 1] - P[a + 1], uz = P[b + 2] - P[a + 2], vx = P[c] - P[a], vy = P[c + 1] - P[a + 1], vz = P[c + 2] - P[a + 2];
area += Math.hypot(uy * vz - uz * vy, uz * vx - ux * vz, ux * vy - uy * vx) / 2;
vol += (P[a] * (P[b + 1] * P[c + 2] - P[b + 2] * P[c + 1]) - P[a + 1] * (P[b] * P[c + 2] - P[b + 2] * P[c]) + P[a + 2] * (P[b] * P[c + 1] - P[b + 1] * P[c])) / 6;
}
const faces = this.faceCount;
const closed = faces > 0 && boundary === 0;
return { verts: this.vertexCount, faces, edges: this.edgeCount, boundary, loose, closed, area, volume: closed ? vol : null, tris: T.n };
}
In detail
Method
Newell's method for face normals; direct split of triangles and quads, ear clipping (earcut.js) of larger faces in their own plane; triangle cross products for area; signed tetrahedron sum for volume.
Number types
Float64Array for positions; Int32Array for connectivity; 64-bit arithmetic.
Tolerances
Flatness: 1e-6 m by default, absolute. Quad split and triangle winding: sign tests against zero.
Limits
Newell and volume sums are taken about the origin and lose digits for a small mesh far from it. A single face's area (faceArea) is half the length of its Newell vector, which for a face that is not flat is no larger than the sum of its triangles.
Approach: 64-bit, direct
Every value is a 64-bit number from input to result. Formulas are closed form or a direct solve, and every comparison uses a stated tolerance.