dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / modeling / merging.lucb
## The booleans' last steps before writing: kept pieces merged back into
## whole faces, and sphere zones given a seam the tessellator needs.
## Kept pieces of one face, or of faces on one surface facing one way
## (coincident pairs), that share edges no other face uses are one region:
## each such group is traced again without those edges (a seam, one
## piece's both ways, stays), so a face cut and kept whole is one face and
## two flush faces joined are one, named by all of the faces' names.
## (Flush faces on B-spline surfaces stay two faces.)
func merge_pieces(work: Work*, traced: const Shape*, pieces: Pieces*, piece_face: Growing[usize]*, piece_name: Growing[i64]*, keep: Growing[bool]*, turn: Growing[bool]*) -> !:
let original = pieces.piece_count()
# Faces on one surface share a group (its first face), facing either
# way: a piece is merged by the way it faces once kept (a solid's face
# turned by a subtraction faces as the other's).
var group = Growing[usize]()
defer group.close()
for f in 0..<work.w.faces.count: try group.push(f)
for pair in work.coincident.view():
# Pieces on two B-spline faces stay apart: neither surface need
# reach over the other's part (an analytic surface has no edge).
if work.w.surfaces.items[(usize)work.w.faces.items[pair.fa].surface].kind == surface_spline or work.w.surfaces.items[(usize)work.w.faces.items[pair.fb].surface].kind == surface_spline: continue
let a = union_root(group.items, pair.fa)
let b = union_root(group.items, pair.fb)
if a < b: group.items[b] = a
elif b < a: group.items[a] = b
# Whether each face faces against its group's first face.
var against = Growing[bool]()
defer against.close()
for f in 0..<work.w.faces.count:
let r = union_root(group.items, f)
var differs = false
if r != f:
let use = work.w.face_uses(f)[0]
let point = try work.w.edge_at(edge_index(use), 0.5)
differs = (try work.w.face_normal(f, point)).dot(try work.w.face_normal(r, point)) < 0.0
try against.push(differs)
var halves = Growing[HalfEdge]()
defer halves.close()
var owner = Growing[usize]()
defer owner.close()
var dropped = Growing[bool]()
defer dropped.close()
var remaining = Growing[HalfEdge]()
defer remaining.close()
var names = Growing[str]()
defer names.close()
var joined = Growing[u8]()
defer joined.close()
for f in 0..<work.w.faces.count:
if union_root(group.items, f) != f: continue
for side in 0..<2:
let flip = side == 1
halves.clear()
owner.clear()
var count = 0
for p in 0..<original:
if not keep.items[p] or union_root(group.items, piece_face.items[p]) != f: continue
# Its loops in the first face's terms (reversed when its own
# face faces against it), and which way it ends up facing.
let reversed = against.items[piece_face.items[p]]
if (turn.items[p] != reversed) != flip: continue
count += 1
for c in pieces.piece_cycles(p):
for use in pieces.cycle(c):
try halves.push(HalfEdge((i64)edge_index(use), (use > 0) != reversed))
try owner.push(p)
if count < 2: continue
# Drop both ways of edges two different pieces share.
dropped.clear()
for _ in 0..<halves.count: try dropped.push(false)
var shared = false
for i in 0..<halves.count:
for j in i + 1..<halves.count:
if halves.items[i].edge == halves.items[j].edge and halves.items[i].forward != halves.items[j].forward and owner.items[i] != owner.items[j]:
dropped.items[i] = true
dropped.items[j] = true
shared = true
if not shared: continue
remaining.clear()
for i in 0..<halves.count:
if not dropped.items[i]: try remaining.push(halves.items[i])
let before = pieces.piece_count()
try split_face(traced, f, remaining.view(), try face_pole(&work.w, f), pieces)
names.clear()
for p in 0..<original:
if keep.items[p] and union_root(group.items, piece_face.items[p]) == f and (turn.items[p] != against.items[piece_face.items[p]]) == flip:
keep.items[p] = false
try names.push(work.w.name(piece_name.items[p]))
try joined_names(names.view(), &joined)
let name = try work.w.add_name((str)joined.view())
for _ in before..<pieces.piece_count():
try piece_face.push(f)
try piece_name.push(name)
try keep.push(true)
try turn.push(flip)
## Where closed curve `c` crosses the seam meridian (chart angle 0) of
## whichever of faces fa and fb lies on a sphere (0 when neither does), so
## a closed edge on a sphere has its vertex where seam_zones can join it.
func seam_parameter(work: Work*, c: i64, fa: usize, fb: usize) -> f64!:
let w = &work.w
var surface: i64 = -1
if w.surfaces.items[(usize)w.faces.items[fa].surface].kind == surface_sphere: surface = w.faces.items[fa].surface
if w.surfaces.items[(usize)w.faces.items[fb].surface].kind == surface_sphere: surface = w.faces.items[fb].surface
if surface < 0: return 0.0
let s = &w.surfaces.items[(usize)surface]
let steps = 256
var previous = (try surface_uv(s, try w.at(c, 0.0), w.tolerance)).0
for at in 1..<steps + 1:
let t = 2.0 * math.pi * (f64)at / (f64)steps
let u = (try surface_uv(s, try w.at(c, t), w.tolerance)).0
# Through angle 0, not across the far side's wrap.
if (previous <= 0.0) != (u <= 0.0) and math.abs(u - previous) < math.pi:
var low = t - 2.0 * math.pi / (f64)steps
var high = t
for _ in 0..<60:
let middle = (low + high) * 0.5
if ((try surface_uv(s, try w.at(c, middle), w.tolerance)).0 <= 0.0) == (previous <= 0.0): low = middle
else: high = middle
return (low + high) * 0.5
previous = u
return 0.0
## A kept piece on a sphere bounded by two loops each going once around (a
## zone between two latitudes, which the tessellator meshes only as a seamed
## patch) gets a seam: a meridian edge from a vertex at angle 0 on one loop
## to one on the other, both loops and the seam both ways becoming one loop.
func seam_zones(work: Work*, traced: const Shape*, pieces: Pieces*, piece_face: const usize[], keep: const bool[]) -> !:
let w = &work.w
var chart = Growing[Vector3]()
defer chart.close()
var wrapping = Growing[usize]()
defer wrapping.close()
var joined = Growing[i64]()
defer joined.close()
for p in 0..<pieces.piece_count():
if not keep[p]: continue
let face = w.faces.items[piece_face[p]]
let s = &w.surfaces.items[(usize)face.surface]
if s.kind != surface_sphere: continue
wrapping.clear()
let first = pieces.piece_starts.items[p]
let last = pieces.piece_starts.items[p + 1]
for k in first..<last:
chart.clear()
try loop_chart(traced, face.surface, 0.0, pieces.cycle(pieces.pieces.items[k]), &chart)
if math.abs(chart.items[chart.count - 1].x - chart.items[0].x) > math.pi: try wrapping.push(k)
if wrapping.count < 2: continue
if wrapping.count > 2: error(invalid, "a piece of a sphere between more than two circles is not supported yet")
let outer = pieces.pieces.items[wrapping.items[0]]
let hole = pieces.pieces.items[wrapping.items[1]]
let (outer_at, v_outer) = try seam_vertex(work, s, pieces.cycle(outer))
let (hole_at, v_hole) = try seam_vertex(work, s, pieces.cycle(hole))
# Neither circle has a vertex on the chart's seam meridian (holes
# through both poles, and others): the zone stays without a seam,
# and the tessellator meshes it in a chart of its own.
if v_outer < 0 or v_hole < 0: continue
let lat_outer = (try surface_uv(s, work.vertices.items[(usize)v_outer], work.w.tolerance)).1
let lat_hole = (try surface_uv(s, work.vertices.items[(usize)v_hole], work.w.tolerance)).1
let c = try w.add_carrier(Carrier(1, s.origin, s.x, s.z, s.radius, s.radius, -1))
let (id, forward) = try work.final_edge(ShapeEdge(c, lat_outer, lat_hole, v_outer, v_hole), 0.0)
let seam = (id + 1) * (1 if forward else -1)
joined.clear()
let outer_uses = pieces.cycle(outer)
let hole_uses = pieces.cycle(hole)
for k in 0..<outer_uses.length: try joined.push(outer_uses[(outer_at + k) % outer_uses.length])
try joined.push(seam)
for k in 0..<hole_uses.length: try joined.push(hole_uses[(hole_at + k) % hole_uses.length])
try joined.push(-seam)
for use in joined.view(): try pieces.uses.push(use)
try pieces.cycle_starts.push(pieces.uses.count)
pieces.pieces.items[wrapping.items[0]] = pieces.cycle_starts.count - 2
# The hole's place holds an empty cycle now.
try pieces.cycle_starts.push(pieces.uses.count)
pieces.pieces.items[wrapping.items[1]] = pieces.cycle_starts.count - 2
## The use of `cycle` that leaves a vertex at chart angle 0 of sphere `s`,
## and that vertex (-1 when none does).
func seam_vertex(work: Work*, s: const Surface*, cycle: const i64[]) -> (usize, i64)!:
for k in 0..<cycle.length:
let use = cycle[k]
let edge = work.finals.items[edge_index(use)]
let v = edge.start if use > 0 else edge.end
let d = work.vertices.items[(usize)v].subtract(s.origin)
if math.abs(d.dot(s.y)) <= work.tol * 10.0 and d.dot(s.x) > 0.0: return (k, v)
return (0, -1)