dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / modeling / shell_cells.lucb
## The inner body of a shell by the cells of the body's planes (the SMLib
## study's item 11: an offset body from a soup of faces, its cells kept by
## winding), for bodies of flat faces and rounds between them that are not
## convex and whose rounds Delete cannot heal together (an L rounded on
## every edge, G1 or G2), or where the wall swallows a flat face (an L with
## one edge chamfered, shelled thicker than the chamfer).
##
## The flat faces' planes cut space into convex cells (a tree of splits
## over the body's box). A cell is the body's when a point inside it lies
## inside the body (three rays): the rounds lie within their radii of the
## sharp edges, where no plane cuts a cell of their own, so the kept cells
## are the sharp body, chamfers and all. Each kept cell, its planes moved
## in by the wall (an opened face's out past the outer body), is the same
## cell of the inner body: their union is the sharp body's inner parallel
## body as Fusion makes it, its edges mitered (Fusion's shells keep an
## inside edge sharp: an L shelled 2 is 3504, the plain L's planes moved
## in), a face the others' moved planes pass (a small chamfer) gone. The
## rounds are then made again on it as one fillet of edge sets, between
## the same faces' moved planes: a convex round of r at r - wall (gone when
## the wall passes it), a concave one at r + wall (a cylinder's offset
## about its axis; a G2 strip's at G2, r + wall); their corners are the
## fillet's own.
## Corners: three corners span a plane when their cross product is longer
## than this share of the size squared, and a fourth off that plane by more
## than this share of the size makes a solid.
let corners_span_share: f64 = 1e-12
let corners_solid_share: f64 = 1e-7
## A plane of the body's flat faces: its outward normal and offset, the
## first face on it (its name), whether that face is opened, and its offset
## moved for the inner body.
struct CellPlane:
var normal: Vector3
var offset: f64
var face: usize
var opened: bool
var moved: f64
## A round to make again: its walls' faces, its new size and, a G2 or G3
## strip's, how far its section is offset (BlendShape.offset: the strip's
## offset surface; 0 a cylinder's, whose offset is a cylinder).
struct CellRound:
var a: usize
var b: usize
var size: f64
var offset: f64
## The most planes the cells take.
let most_cell_planes: usize = 24
## The inner body of `model` (`removed` faces opened) for a wall of
## `wall_in` inside (`wall_out` outside: the opened faces' planes go that
## much further out), by the cells of its planes (above); none when a face
## is neither flat nor a round between flat walls, a plane carries faces
## facing both ways, or a step fails.
func cells_inner(model: interop.Reference[CadModel], removed: const bool[], wall_in: f64, wall_out: f64) -> interop.Reference[CadModel]?!:
if not (wall_in > 0.0): return none
var w = try shape_of(model.value())
defer w.close()
var planes = Growing[CellPlane]()
defer planes.close()
var rounds = Growing[CellRound]()
defer rounds.close()
var continuity: i64 = 0
var low = Vector3(1.0e300, 1.0e300, 1.0e300)
var high = Vector3(-1.0e300, -1.0e300, -1.0e300)
for f in 0..<w.faces.count:
let (l, h) = try face_box(&w, f)
low = lower(low, l)
high = upper(high, h)
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
if s.kind == surface_plane:
if not try add_cell_plane(&w, f, removed[f], wall_in, wall_out, &planes): return none
continue
if removed[f]: return none
# A round beside an opened face is tangent_opening's (the hollow
# opens square to the face there).
for use in w.face_uses(f):
let e = edge_index(use)
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
if (fa >= 0 and removed[(usize)fa]) or (fb >= 0 and removed[(usize)fb]): return none
# A round between two flat walls: its size on the inner body.
let (round, kind) = try cell_round(&w, f, wall_in)
if kind < 0: return none
if kind == 0: continue
if continuity != 0 and continuity != kind: return none
continuity = kind
if round.size > w.tolerance * 100.0: try rounds.push(round)
if planes.count < 4 or planes.count > most_cell_planes: return none
let size = high.subtract(low).length()
# The cells of the body's planes, kept where the body is.
var signs = Growing[i8]()
defer signs.close()
try kept_cells(&w, planes.view(), low, high, size, &signs)
if signs.count == 0: return none
# Each kept cell from the moved planes; their union, its faces named
# and its rounds made again.
let united = try moved_cells(w.tolerances, planes.view(), signs.view(), low, high, size)
if let cells = united:
defer cells.release()
return try cells_remade(&w, planes.view(), rounds.view(), continuity, cells)
return none
## The cells' union `united` with every face named after the face of `w`
## whose plane (of `planes`, moved) it lies on, and `rounds` made again on
## it at `continuity` as one fillet of edge sets by size; none when a face
## lies on no plane or the fillet refuses.
func cells_remade(w: const Shape*, planes: const CellPlane[], rounds: const CellRound[], continuity: i64, united: interop.Reference[CadModel]) -> interop.Reference[CadModel]?!:
# Every face named after the face whose plane it lies on.
var v = try shape_of(united.value())
defer v.close()
for f in 0..<v.faces.count:
let s = &v.surfaces.items[(usize)v.faces.items[f].surface]
if s.kind != surface_plane: return none
let normal = face_outward(&v, f)
let offset = normal.dot(s.origin)
var named = false
for plane in planes:
if plane.normal.dot(normal) > 1.0 - parallel_slack and math.abs(plane.moved - offset) <= w.tolerance * 100.0:
v.faces.items[f].name = try v.add_name(w.face_name(plane.face))
named = true
if not named: return none
let b = try brep_of(&v)
defer b.release()
let inner = try CadModel.of_brep(b)
if rounds.length == 0: return inner
defer inner.release()
# The rounds again, as edge sets by size, between their walls' faces.
var o = try shape_of(inner.value())
defer o.close()
var radii = Growing[f64]()
defer radii.close()
for round in rounds:
var known = false
for r in radii.view(): known = known or math.abs(r - round.size) <= w.tolerance
if not known: try radii.push(round.size)
var sets = Growing[u8]()
defer sets.close()
var edges = Growing[i64]()
defer edges.close()
var text = Growing[u8]()
defer text.close()
for at in 0..<radii.count:
edges.clear()
for round in rounds:
if math.abs(round.size - radii.items[at]) > w.tolerance: continue
# Its walls' planes' faces (a wall's first face on its plane).
let fa = planes[(usize)try plane_of(w, planes, round.a)].face
let fb = planes[(usize)try plane_of(w, planes, round.b)].face
edges_between(&o, w.face_name(fa), w.face_name(fb), &edges) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
return none
text.clear()
try references_of(&o, edges.view(), &text)
if at > 0: try sets.push(124)
for byte in text.view(): try sets.push(byte)
# G2 and G3 rounds are their strips' offsets (one offset for the
# feature: rounds grown and shrunk together take the plain section).
var shape = plain_blend
shape.offset = rounds[0].offset
for round in rounds:
if round.offset != shape.offset: shape.offset = 0.0
let made = filleted_sets(inner.value(), (str)sets.view(), radii.view(), "r", continuity, false, shape) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
return none
return made
## Flat face `f`'s plane onto `planes` (once: a face of a plane already
## there joins it); false when a plane carries faces facing both ways.
func add_cell_plane(w: const Shape*, f: usize, opened: bool, wall_in: f64, wall_out: f64, planes: Growing[CellPlane]*) -> bool!:
let normal = face_outward(w, f)
let offset = normal.dot(w.surfaces.items[(usize)w.faces.items[f].surface].origin)
for plane in planes.view():
if math.abs(plane.normal.dot(normal)) < 1.0 - parallel_slack: continue
if math.abs(plane.offset - offset * plane.normal.dot(normal)) > w.tolerance * 100.0: continue
if plane.normal.dot(normal) < 0.0 or plane.opened != opened: return false
return true
try planes.push(CellPlane(normal, offset, f, opened, offset + (wall_in + wall_out if opened else -wall_in)))
return true
## The place in `planes` of flat face `f`'s plane.
func plane_of(w: const Shape*, planes: const CellPlane[], f: usize) -> i64!:
let normal = face_outward(w, f)
let offset = normal.dot(w.surfaces.items[(usize)w.faces.items[f].surface].origin)
for k in 0..<planes.length:
if planes[k].normal.dot(normal) > 1.0 - parallel_slack and math.abs(planes[k].offset - offset) <= w.tolerance * 100.0: return (i64)k
error(invalid, "a round's wall has no plane")
## Curved face `f` of `w` as cells_inner takes it: a round strip between
## two flat walls (a cylinder: 1; a G2 or G3 B-spline strip: 2) with its
## size on the inner body for a wall of `wall` (its walls, r - wall turned
## outward, r + wall inward); a corner (a sphere, a torus, a B-spline patch
## meeting strips) to be made again with them (0); or neither (-1).
func cell_round(w: const Shape*, f: usize, wall: f64) -> (CellRound, i64)!:
let none_round = CellRound(0, 0, 0.0, 0.0)
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
if s.kind == surface_sphere or s.kind == surface_torus: return (none_round, 0)
if s.kind == surface_cylinder:
let (fa, fb) = strip_walls(w, f) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
return (none_round, -1)
if w.surfaces.items[(usize)w.faces.items[fa].surface].kind != surface_plane or w.surfaces.items[(usize)w.faces.items[fb].surface].kind != surface_plane: return (none_round, -1)
let size = s.radius - wall if try outward_round(w, f) else s.radius + wall
return (CellRound(fa, fb, size, 0.0), 1)
if s.kind != surface_spline: return (none_round, -1)
let (round, found) = try spline_strip(w, f, wall)
if found: return (round, 2)
# A corner patch: it meets some strip (a spline face beside flat walls).
for use in w.face_uses(f):
let e = edge_index(use)
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
if fa < 0 or fb < 0: continue
let other = (usize)(fb if (usize)fa == f else fa)
if other == f or w.surfaces.items[(usize)w.faces.items[other].surface].kind != surface_spline: continue
let (_, strip) = try spline_strip(w, other, wall)
if strip: return (none_round, 0)
return (none_round, -1)
## Whether B-spline face `f` is a G2 or G3 fillet's strip between two flat
## walls it meets tangentially along straight edges, and its round: its
## radius the contacts' distance from the walls' meeting line over
## tan(φ/2) (φ their turn), r - `wall` round a convex edge, r + `wall` in a
## concave one.
func spline_strip(w: const Shape*, f: usize, wall: f64) -> (CellRound, bool)!:
let none_round = CellRound(0, 0, 0.0, 0.0)
var walls = Growing[usize]()
defer walls.close()
var contacts = Growing[Vector3]()
defer contacts.close()
for use in w.face_uses(f):
let e = edge_index(use)
let fa = w.sides.items[e * 2]
let fb = w.sides.items[e * 2 + 1]
if fa < 0 or fb < 0: continue
let other = (usize)(fb if (usize)fa == f else fa)
if w.surfaces.items[(usize)w.faces.items[other].surface].kind != surface_plane: continue
if w.carriers.items[(usize)w.edges.items[e].carrier].kind != curve_line: continue
if not try tangent_edge(w, e): continue
var known = false
for k in walls.view(): known = known or k == other
if known: continue
try walls.push(other)
try contacts.push(try w.edge_at(e, 0.5))
if walls.count != 2: return (none_round, false)
let na = face_outward(w, walls.items[0])
let nb = face_outward(w, walls.items[1])
let turn = math.acos(math.clamp(na.dot(nb), -1.0, 1.0))
if turn < least_wall_turn or turn > math.pi - least_wall_turn: return (none_round, false)
let line = try na.cross(nb).normalized()
let ca = contacts.items[0]
let hb = nb.dot(w.surfaces.items[(usize)w.faces.items[walls.items[1]].surface].origin)
let into_a = line.cross(na)
let apex = ca.add(into_a.multiply_scalar((hb - nb.dot(ca)) / nb.dot(into_a)))
let radius = apex.subtract(ca).length() / math.tan(turn * 0.5)
let middle = try point_on_face(w, f)
let outward = (try w.face_normal(f, middle)).dot(apex.subtract(middle)) > 0.0
return (CellRound(walls.items[0], walls.items[1], radius - wall if outward else radius + wall, -wall if outward else wall), true)
## The six planes of the box about `low` to `high`, a tenth of `size` out
## (every cell's outer bounds), onto `normals` and `offsets`.
func box_planes(low: Vector3, high: Vector3, size: f64, normals: Growing[Vector3]*, offsets: Growing[f64]*) -> !:
let margin = size * 0.1
let axes: Vector3[3] = [Vector3(1.0, 0.0, 0.0), Vector3(0.0, 1.0, 0.0), Vector3(0.0, 0.0, 1.0)]
for axis in axes:
try normals.push(axis)
try offsets.push(axis.dot(high) + margin)
try normals.push(axis.multiply_scalar(-1.0))
try offsets.push(-axis.dot(low) + margin)
## The corners of the cell n . x <= h over `normals` and `offsets` onto
## `corners` (cleared first): each three planes' meeting point inside all.
func cell_corners(normals: const Vector3[], offsets: const f64[], size: f64, corners: Growing[Vector3]*) -> !:
corners.clear()
let eps = size * relative_zero
for i in 0..<normals.length:
for j in i + 1..<normals.length:
for k in j + 1..<normals.length:
if math.abs(normals[i].dot(normals[j].cross(normals[k]))) < planes_meet_floor: continue
let three: Vector3[3] = [normals[i], normals[j], normals[k]]
let at: f64[3] = [offsets[i], offsets[j], offsets[k]]
let p = try least_squares_point(three[..<3], at[..<3])
var within = true
for m in 0..<normals.length:
if normals[m].dot(p) > offsets[m] + eps: within = false
if not within: continue
var known = false
for q in corners.view(): known = known or q.subtract(p).length() <= eps * 10.0
if not known: try corners.push(p)
## Whether `corners` span a solid (not all on one plane), of more than a
## billionth of `size` across.
func solid_corners(corners: const Vector3[], size: f64) -> bool:
if corners.length < 4: return false
let a = corners[0]
var far = 0
for k in 1..<corners.length:
if corners[k].subtract(a).length() > corners[far].subtract(a).length(): far = (i64)k
let b = corners[(usize)far]
var best = 0.0
var c = a
for q in corners:
let lift = q.subtract(a).cross(b.subtract(a)).length()
if lift > best:
best = lift
c = q
let n = b.subtract(a).cross(c.subtract(a))
if n.length() <= size * size * corners_span_share: return false
let across_unit = n.multiply_scalar(1.0 / n.length())
for q in corners:
if math.abs(q.subtract(a).dot(across_unit)) > size * corners_solid_share: return true
return false
## The cells of `planes` over the box about `low` to `high` inside the
## body `w` (a point inside the cell, its corners' middle, inside the body
## by three rays): each cell's signs (1: behind the plane, -1 in front)
## onto `signs`, n per cell. The cells come from splitting the box by one
## plane after another, keeping the solid halves.
func kept_cells(w: const Shape*, planes: const CellPlane[], low: Vector3, high: Vector3, size: f64, signs: Growing[i8]*) -> !:
let n = planes.length
# The live cells' signs (0: not cut by that plane yet).
var cells = Growing[i8]()
defer cells.close()
try cells.fill(n, 0)
var next = Growing[i8]()
defer next.close()
var normals = Growing[Vector3]()
defer normals.close()
var offsets = Growing[f64]()
defer offsets.close()
var corners = Growing[Vector3]()
defer corners.close()
for i in 0..<n:
next.clear()
for cell in 0..<cells.count // n:
for sign in [1, -1]:
normals.clear()
offsets.clear()
for j in 0..<n:
let s = (i8)sign if j == i else cells.items[cell * n + j]
if s == 0: continue
try normals.push(planes[j].normal.multiply_scalar((f64)s))
try offsets.push(planes[j].offset * (f64)s)
try box_planes(low, high, size, &normals, &offsets)
try cell_corners(normals.view(), offsets.view(), size, &corners)
if not solid_corners(corners.view(), size): continue
for j in 0..<n: try next.push((i8)sign if j == i else cells.items[cell * n + j])
try cells.assign(next.view())
var rays = try shape_rays(w)
defer rays.close()
for cell in 0..<cells.count // n:
normals.clear()
offsets.clear()
for j in 0..<n:
let s = (f64)cells.items[cell * n + j]
try normals.push(planes[j].normal.multiply_scalar(s))
try offsets.push(planes[j].offset * s)
try box_planes(low, high, size, &normals, &offsets)
try cell_corners(normals.view(), offsets.view(), size, &corners)
var middle = Vector3()
for q in corners.view(): middle = middle.add(q)
middle = middle.multiply_scalar(1.0 / (f64)corners.count)
if not try rays.inside(w, middle, size): continue
for j in 0..<n: try signs.push(cells.items[cell * n + j])
## The union of the kept cells (`signs`, one per plane per cell) each made
## of `planes` moved (their `moved` offsets) and the box about `low` to
## `high`; none when no cell stays solid or the booleans refuse.
func moved_cells(tolerances: CadTolerances, planes: const CellPlane[], signs: const i8[], low: Vector3, high: Vector3, size: f64) -> interop.Reference[CadModel]?!:
let n = planes.length
var normals = Growing[Vector3]()
defer normals.close()
var offsets = Growing[f64]()
defer offsets.close()
var corners = Growing[Vector3]()
defer corners.close()
var joined_cells: interop.Reference[CadModel]? = none
for cell in 0..<signs.length // n:
normals.clear()
offsets.clear()
for i in 0..<n:
let sign = (f64)signs[cell * n + i]
try normals.push(planes[i].normal.multiply_scalar(sign))
try offsets.push(planes[i].moved * sign)
try box_planes(low, high, size, &normals, &offsets)
try cell_corners(normals.view(), offsets.view(), size, &corners)
if not solid_corners(corners.view(), size): continue
let piece = try convex_cell(tolerances, normals.view(), offsets.view(), size)
if let so_far = joined_cells:
let joined = combine(so_far.value(), piece.value(), op_union) catch failure:
so_far.release()
piece.release()
if failure.code != invalid: error(failure.code, failure.message)
return none
so_far.release()
piece.release()
joined_cells = joined
else:
joined_cells = piece
return joined_cells