dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / modeling / arrangement.lucb
## A sketch's curves as Fusion 360 reads them for profiles: every piece
## split where it meets another (crossing, touching, or a curve's end on
## it), the pieces joined at shared points into a planar graph, dangling
## pieces dropped, and the graph's faces traced: each bounded face is a
## profile. Which faces a feature takes (`chosen`, by key) or, given none,
## islands alternating from the outside in (a plate's hole stays empty,
## overlapping shapes join), and their outline traced together, so faces
## next to each other become one region. Loops leave as profile.lucb's:
## outer loops counterclockwise about the plane's normal, holes clockwise.
##
## A face's key names it by what bounds it: the sorted sketch curves of its
## loops, each with the side it runs (+ along the curve, - against), so it
## stays the same face when dimensions move things (two crescents of
## overlapping circles differ by which circle each runs along).
## Arrange `pieces` (on `result`'s plane) and write the regions of the faces
## `chosen` names (keys apart by `;`; empty: alternating islands) into
## `result`'s loops and regions.
func arrange(result: Profiles*, pieces: const Growing[ProfileEdge]*, chosen: str, tolerance: f64) -> !:
var a = try arranged(result, pieces, tolerance)
defer a.close()
let count = a.areas.count
var take = Growing[bool]()
defer take.close()
try take.fill(count, false)
if trimmed(chosen) == "":
try alternate_islands(&a, &take)
else:
for f in 0..<count:
if a.areas.items[f] <= 0.0: continue
var key = Growing[u8]()
defer key.close()
try face_key(&a.subs, &a.halves, a.loop(f), &key)
take.items[f] = key_listed(chosen, (str)key.view())
# A piece's outside (a clockwise face) belongs to the face around it:
# the smallest bounded face holding a point just outside it.
for f in 0..<count:
if a.areas.items[f] > 0.0: continue
let owner = a.holding(a.left_point(f), (i64)f)
take.items[f] = owner >= 0 and take.items[(usize)owner]
try chosen_regions(result, &a.subs, &a.halves, a.vertex_count, &take, tolerance)
## A sketch's arrangement: its sub-edges, half-edges and faces, each face's
## signed area (positive: bounded) and outline in plane coordinates.
struct Arranged:
var subs: Growing[ProfileEdge]
var halves: Growing[SketchHalf]
var vertex_count: usize
var faces: Growing[usize]
var face_offsets: Growing[usize]
var areas: Growing[f64]
var outlines: Growing[Vector3]
var outline_offsets: Growing[usize]
## Per face: the connected piece of the graph it belongs to (faces of
## one piece never hold each other).
var pieces_of: Growing[usize]
func close():
self.subs.close()
self.halves.close()
self.faces.close()
self.face_offsets.close()
self.areas.close()
self.outlines.close()
self.outline_offsets.close()
self.pieces_of.close()
## Face `f`'s half-edges, in order round it.
func loop(f: usize) -> const usize[]:
return self.faces.view()[self.face_offsets.items[f]..<self.face_offsets.items[f + 1]]
func outline_of(f: usize) -> const Vector3[]:
return self.outlines.view()[self.outline_offsets.items[f]..<self.outline_offsets.items[f + 1]]
## A point just left of face `f`'s first edge (inside a bounded face,
## outside a piece's outer face).
func left_point(f: usize) -> Vector3:
return left_of_start(self.outline_of(f))
## The smallest bounded face holding plane point `p`, or -1; with
## `apart`, only faces of other pieces than face `apart`'s.
func holding(p: Vector3, apart: i64 = -1) -> i64:
var owner: i64 = -1
for other in 0..<self.areas.count:
if apart >= 0 and self.pieces_of.items[other] == self.pieces_of.items[(usize)apart]: continue
if self.areas.items[other] <= 0.0 or not inside(self.outline_of(other), p): continue
if owner < 0 or self.areas.items[other] < self.areas.items[(usize)owner]: owner = (i64)other
return owner
## The arrangement of `pieces` on `result`'s plane.
func arranged(result: Profiles*, pieces: const Growing[ProfileEdge]*, tolerance: f64) -> Arranged!:
var a = Arranged(Growing[ProfileEdge](), Growing[SketchHalf](), 0, Growing[usize](), Growing[usize](), Growing[f64](), Growing[Vector3](), Growing[usize](), Growing[usize]())
errdefer a.close()
try split_pieces(result, pieces, tolerance, &a.subs)
var vertices = Growing[Vector3]()
defer vertices.close()
try build_graph(result, &a.subs, tolerance, &vertices, &a.halves)
a.vertex_count = vertices.count
try trace_faces(&a.halves, vertices.count, &a.faces, &a.face_offsets)
var outline = Growing[Vector3]()
defer outline.close()
try a.outline_offsets.push(0)
for f in 0..<a.face_offsets.count - 1:
try face_outline(result, &a.subs, &a.halves, a.loop(f), &outline)
try a.areas.push(signed_area(outline.view()))
for p in outline.view(): try a.outlines.push(p)
try a.outline_offsets.push(a.outlines.count)
# Pieces: vertices joined by live edges.
var parent = Growing[usize]()
defer parent.close()
for v in 0..<vertices.count: try parent.push(v)
for h in a.halves.view():
if not h.alive: continue
let x = union_root(parent.items, h.tail)
let y = union_root(parent.items, h.head)
if x != y: parent.items[x] = y
for f in 0..<a.face_offsets.count - 1:
try a.pieces_of.push(union_root(parent.items, a.halves.items[a.loop(f)[0]].tail))
return a
## The outlines of `set`'s faces named by `keys` (apart by `;`), as closed
## polylines on the sketch plane (arcs and splines sampled): what a viewport
## draws to show chosen or hovered profiles.
func face_outlines(set: const GeometrySet*, tolerance: f64, keys: str, out: CurvesBuilder*) -> !:
var result = try empty_profiles(set)
defer result.close()
var pieces = Growing[ProfileEdge]()
defer pieces.close()
try read_pieces(set, &result, &pieces, tolerance)
var a = try arranged(&result, &pieces, tolerance)
defer a.close()
for f in 0..<a.areas.count:
if a.areas.items[f] <= 0.0: continue
var key = Growing[u8]()
defer key.close()
try face_key(&a.subs, &a.halves, a.loop(f), &key)
if not key_listed(keys, (str)key.view()): continue
try out.begin(CurveType.poly, true)
for p in a.outline_of(f):
try out.point(result.origin.add(result.u.multiply_scalar(p.x)).add(result.v.multiply_scalar(p.y)))
## The keys of `set`'s profiles (its arrangement's bounded faces) apart by
## `;` onto `out`; with `probe`, only the face holding plane point `at`.
func face_keys(set: const GeometrySet*, tolerance: f64, probe: bool, at: Vector3, out: Growing[u8]*) -> !:
var result = try empty_profiles(set)
defer result.close()
var pieces = Growing[ProfileEdge]()
defer pieces.close()
try read_pieces(set, &result, &pieces, tolerance)
var a = try arranged(&result, &pieces, tolerance)
defer a.close()
let (x, y) = result.planar(at)
let target = a.holding(Vector3(x, y, 0.0)) if probe else -1
for f in 0..<a.areas.count:
if a.areas.items[f] <= 0.0 or (probe and (i64)f != target): continue
if out.count > 0: try out.push(59)
try face_key(&a.subs, &a.halves, a.loop(f), out)
## The faces taken by default: bounded faces of islands alternating from
## the outside in (a face's depth: how many bounded faces of other pieces
## hold it).
func alternate_islands(a: const Arranged*, take: Growing[bool]*) -> !:
let count = a.areas.count
for f in 0..<count:
if a.areas.items[f] <= 0.0: continue
let probe = a.left_point(f)
var depth = 0
for other in 0..<count:
if a.areas.items[other] <= 0.0 or a.pieces_of.items[other] == a.pieces_of.items[f]: continue
if inside(a.outline_of(other), probe): depth += 1
take.items[f] = depth % 2 == 0
## A point just left of an outline's first segment's middle: inside a
## counterclockwise outline, outside a clockwise one.
func left_of_start(points: const Vector3[]) -> Vector3:
let a = points[0]
let b = points[1 % points.length]
let dx = b.x - a.x
let dy = b.y - a.y
let l = math.max(math.hypot(dx, dy), 1e-300)
let reach = l * 1e-3
return Vector3((a.x + b.x) * 0.5 - dy / l * reach, (a.y + b.y) * 0.5 + dx / l * reach, 0.0)
## Face key: its half-edges' sketch curves and the way each is run.
func face_key(subs: Growing[ProfileEdge]*, halves: Growing[SketchHalf]*, loop: const usize[], out: Growing[u8]*) -> !:
var parts = Growing[i64]()
defer parts.close()
for at in loop:
let h = halves.items[at]
let e = subs.items[h.edge]
let code = e.curve * 2 + (1 if h.backward else 0)
var seen = false
for p in parts.view():
if p == code: seen = true
if not seen: try parts.push(code)
sort.sort(parts.items[..<parts.count])
for index in 0..<parts.count:
if index > 0: try out.push(44)
try push_decimal(out, parts.items[index] // 2)
try out.push(45 if parts.items[index] % 2 == 1 else 43)
## Whether `key` is one of `keys` (apart by `;`).
func key_listed(keys: str, key: str) -> bool:
var start: usize = 0
let bytes = keys.bytes
while start <= bytes.length:
var end = start
while end < bytes.length and bytes[end] != 59: end += 1
if trimmed((str)bytes[start..<end]) == key: return true
start = end + 1
return false
## The outline of the taken faces together: the half-edges with a taken
## face on their left and none on their right, traced into loops (around
## each vertex, the next such edge clockwise), then nested into regions
## (counterclockwise loops outer, clockwise ones holes of the smallest
## outer loop holding them).
func chosen_regions(result: Profiles*, subs: Growing[ProfileEdge]*, halves: Growing[SketchHalf]*, vertex_count: usize, take: const Growing[bool]*, tolerance: f64) -> !:
# Boundary half-edges stay alive; the rest leave the tracing (decided
# for all before any face is cleared).
var boundary = Growing[bool]()
defer boundary.close()
for at in 0..<halves.count:
let h = halves.items[at]
let twin = halves.items[twin_of(at)]
let left = h.alive and h.face >= 0 and take.items[(usize)h.face]
let right = twin.alive and twin.face >= 0 and take.items[(usize)twin.face]
try boundary.push(left and not right)
for at in 0..<halves.count:
halves.items[at].alive = boundary.items[at]
halves.items[at].face = -1
try result.loop_offsets.push(0)
for start in 0..<halves.count:
if not halves.items[start].alive or halves.items[start].face >= 0: continue
var at = start
var guard: usize = 0
while halves.items[at].face < 0:
halves.items[at].face = 0
let h = halves.items[at]
var e = subs.items[h.edge]
try result.edges.push(e)
if h.backward: try result.reverse_edge(result.edges.count - 1)
at = next_boundary(halves, at)
guard += 1
if guard > halves.count: error(invalid, "a sketch's profile could not be traced")
let first = result.loop_offsets.items[result.loop_offsets.count - 1]
try join_parts(result, first, tolerance)
# Ends that met within tolerance meet exactly.
let last = result.edges.count - 1
for index in first..<last:
result.edges.items[index + 1].start = result.edges.items[index].end
result.edges.items[first].start = result.edges.items[last].end
try result.loop_offsets.push(result.edges.count)
_ = vertex_count
_ = tolerance
try nest_oriented(result)
## Loop edges from `first` on: neighbors that are parts of one sketch curve
## going on the same way (a line straight on, an arc round the same circle)
## joined into one, the loop's last and first included.
func join_parts(result: Profiles*, first: usize, tolerance: f64) -> !:
var at = first
while at + 1 < result.edges.count:
if continues(&result.edges.items[at], &result.edges.items[at + 1], tolerance):
result.edges.items[at].end = result.edges.items[at + 1].end
result.edges.items[at].sweep += result.edges.items[at + 1].sweep
for move in at + 1..<result.edges.count - 1:
result.edges.items[move] = result.edges.items[move + 1]
result.edges.count -= 1
else:
at += 1
# Round the loop's seam: the last edge going on into the first.
let last = result.edges.count - 1
if last > first and continues(&result.edges.items[last], &result.edges.items[first], tolerance):
var joined = result.edges.items[last]
joined.end = result.edges.items[first].end
joined.sweep += result.edges.items[first].sweep
result.edges.items[first] = joined
result.edges.count -= 1
## Whether `b` goes on from `a` as one curve: the same sketch curve, both
## lines in line, or both arcs of one circle turning one way.
func continues(a: const ProfileEdge*, b: const ProfileEdge*, tolerance: f64) -> bool:
if a.curve < 0 or a.curve != b.curve or a.kind != b.kind or a.kind == profile_spline: return false
if a.kind == profile_line:
let d1 = a.end.subtract(a.start)
let d2 = b.end.subtract(b.start)
return d1.cross(d2).length() <= tolerance * math.max(d1.length(), d2.length()) and d1.dot(d2) > 0.0
return a.center.subtract(b.center).length() <= tolerance and math.abs(a.radius - b.radius) <= tolerance and (a.sweep > 0.0) == (b.sweep > 0.0)
## The next boundary half-edge after `at`: at its head, the alive one
## leaving most clockwise from the way back.
func next_boundary(halves: Growing[SketchHalf]*, at: usize) -> usize:
let h = halves.items[at]
let back = halves.items[twin_of(at)]
var best: usize = at
var best_turn = 10.0
for index in 0..<halves.count:
let o = halves.items[index]
if not o.alive or o.tail != h.head or o.face >= 0: continue
let turn = clockwise_turn(&back, &o)
if turn < best_turn:
best_turn = turn
best = index
return best
## Loops already oriented (outer counterclockwise, holes clockwise) into
## regions: each hole in the smallest outer loop holding it.
func nest_oriented(result: Profiles*) -> !:
let count = result.loop_count()
var outlines = Growing[Vector3]()
defer outlines.close()
var offsets = Growing[usize]()
defer offsets.close()
var scratch = Growing[Vector3]()
defer scratch.close()
var areas = Growing[f64]()
defer areas.close()
try offsets.push(0)
for loop in 0..<count:
try result.outline(loop, &scratch)
try areas.push(signed_area(scratch.view()))
for p in scratch.view(): try outlines.push(p)
try offsets.push(outlines.count)
try result.region_offsets.push(0)
for loop in 0..<count:
if areas.items[loop] <= 0.0: continue
try result.region_loops.push(loop)
for hole in 0..<count:
if areas.items[hole] >= 0.0: continue
let probe = outlines.items[offsets.items[hole]]
if not inside(outlines.view()[offsets.items[loop]..<offsets.items[loop + 1]], probe): continue
# The smallest outer loop holding it.
var smallest = true
for other in 0..<count:
if other == loop or areas.items[other] <= 0.0 or areas.items[other] >= areas.items[loop]: continue
if inside(outlines.view()[offsets.items[other]..<offsets.items[other + 1]], probe): smallest = false
if smallest: try result.region_loops.push(hole)
try result.region_offsets.push(result.region_loops.count)