Сетка и ядро CSG

Что такое ядро сетки

Ядро сетки работает с сетками замкнутых треугольников: оно строит их из параметрических примитивов (meshOf), измеряет их (meshVolume, meshBounds, meshTopology) и объединяет их с логическими значениями (booleanMesh, booleanAll). Это то, что показывает окно просмотра, что делает генератор CAM и что пишет экспорт STL.

Это не точное представление границ. Разрезанный цилиндр остается граненым цилиндром, и у него нет топологии грани, по которой можно было бы выполнить сопряжение или измерение. Для точных граней, скруглений, массовых свойств и STEP Ядро B-rep это отдельный фрагмент кода.

Тип сетки и примитивы

export interface Mesh {
  readonly positions: Float32Array   // x, y, z per vertex
  readonly indices: Uint32Array      // three per triangle, counter-clockwise seen from outside
}
export const meshOf: (solid: Solid, tolerance?: number /* 0.1 mm */) => Mesh
export const meshVolume: (mesh: Mesh) => number     // signed; positive when outward-facing
export const meshBounds: (mesh: Mesh) => SolidBounds

Цилиндр Ø6 с segments: 24 при допуске 0.05 получилось с треугольниками 96 (стороны 24, две вершины 24-угольника); Ø20 с 128, поскольку для большего радиуса требовалось, чтобы сегменты 32 оставались в пределах 0.05 мм.

Логические значения путем разделения двоичного пространства

Каждый операнд становится классификатором. Общая сетка получает дерево BSP; Выпуклая сетка (замкнутая, связная, каждый край выпуклый) представляет собой просто отдельные плоскости ее граней, поэтому ящик состоит из шести плоскостей, а сфера из десяти тысяч треугольников классифицируется без построения квадратичной цепи, в которую вырождается BSP выпуклого твердого тела. Полигоны классифицируются как списки, и полигон, выходящий за рамки ограничивающего прямоугольника другого операнда, сохраняется или удаляется без каких-либо перемещений.

1. If either mesh is empty, or the bounding boxes do not meet (within tolerance), answer directly: union = merge, subtract = a, intersect = empty.
2. Постройте классификаторы A и B (выпуклые плоскости или BSP).
3. Объединение: оставьте A снаружи B, B снаружи A и отбросьте грани B, совпадающие с гранями A, указывающими в том же направлении, чтобы общее лицо сохранялось один раз.
4. Subtract and intersect follow the classic a.clipTo(b), b.clipTo(a), b.invert() sequence on polygon lists, without copying trees.
5. Очистите полигональный суп: точки сварки в пределах max(10·eps, 1e-9·size), закройте Т-образные соединения, закройте зазоры размером до 1e-4·между полосками, объедините копланарные фрагменты и повторите триангуляцию.

export type BooleanOp = "union" | "subtract" | "intersect"
export interface CsgOptions {
  /** Distance below which a point counts as on a plane, mm. Default 1e-7 × the larger extent. */
  readonly tolerance?: number
  /** Merge coplanar fragments and re-triangulate (default true). */
  readonly mergeCoplanar?: boolean
}
export const booleanMesh: (a: Mesh, b: Mesh, op: BooleanOp, options?: CsgOptions) => Mesh
/** Union reduced as a balanced tree; subtract and intersect fold left to right. */
export const booleanAll: (meshes: ReadonlyArray<Mesh>, op: BooleanOp, options?: CsgOptions) => Mesh
export const translateMesh: (mesh: Mesh, dx: number, dy: number, dz: number) => Mesh
export const rotateMesh: (mesh: Mesh, axis: V3, radians: number, origin?: V3) => Mesh
export const mergeMeshes: (meshes: ReadonlyArray<Mesh>) => Mesh

Число треугольников растет вместе с объектами, а не с количеством логических значений: шаг слияния возвращает копланарные фрагменты обратно в целые грани. На пластине выше коробка имела треугольники 12, после четырёх отверстий 412, после бобышки 540, после отверстия 640; вся цепочка выполнялась за 96 мс.

Объединение, вычитание, пересечение на изогнутом входе

A 20 mm cube at the origin against a sphere of radius 12 centred on its far corner (20, 20, 20), meshed at tolerance 0.2 (624 triangles). Real volumes:

Проверьте: 8 000 + 7 063.84 – 882.98 = 14 180.86 и 8 000 – 882.98 = 7 117.02, чтобы эти три результата согласовывались друг с другом с точки зрения сотый. Сама сетка сферы составляет 2.4 % под точной сферой, что является гранью грубого допуска, а не логической ошибки.

Проверка топологии

{"vertices":312,"triangles":640,"edges":960,"boundaryEdges":0,"nonManifoldEdges":0,
 "misorientedEdges":0,"degenerateTriangles":0,"shells":1,"eulerCharacteristic":-8,"genus":5,
 "closed":true,"solid":true,"volume":23981.43509870267,"area":8238.640705862534}
// describeTopology → "closed solid, 1 shell, genus 5, 640 triangles, V 23981.4 mm³, A 8238.6 mm²"

V − E + F = 312 − 960 + 640 = −8 = 2 − 2g, so g = 5: the four drilled holes plus the bore, which runs through the boss and the plate.

Триангуляция многоугольника

triangulatePolygon(
  [{x:0,y:0},{x:4,y:0},{x:4,y:4},{x:0,y:4}],
  [[{x:1,y:1},{x:1,y:3},{x:3,y:3},{x:3,y:1}]])
// [[0,4,5],[7,4,0],[3,0,5],[7,0,1],[2,3,5],[6,7,1],[2,5,6],[6,1,2]]

Поиск неисправностей