dymokomi/luce-cad
Source of release 0.9.5
0.9.5 / src / modeling / split.lucb
## Splitting a face: its boundary's edge pieces (each the way the face uses
## it) and the new edges across it (both ways) traced into the regions they
## enclose. From each half-edge the trace turns, at its end, to the first
## edge clockwise from where it came (in the tangent plane, about the face's
## outward normal), so the region on its left is followed. A cycle turning
## positively in the surface's chart bounds a region; one turning negatively
## is a hole, put in the smallest region around it.
## The fraction along an edge a half-edge's direction is taken by default:
## a short chord, so curves leaving along one tangent order by their bend.
let half_chord_fraction: f64 = 0.001
## The fraction a half-chord's search starts doubling from.
let half_chord_start: f64 = 1e-6
## The shares of the reach two half-edges are compared at, until they part.
let clockwise_fractions: f64[4] = [0.01, 0.05, 0.2, 0.5]
## Turns closer than this (radians) do not order two half-edges; a turn at
## most this is a whole turn.
let clockwise_tie: f64 = 1e-9
let least_clockwise: f64 = 1e-12
## Each way on from a vertex is measured this share of the shortest one's
## reach from it; turns closer than this (radians) tie there.
let way_on_share: f64 = 1e-3
let way_on_tie: f64 = 1e-6
## How far left of a hole's first segment (in its chart, as a share of the
## segment) the point finding its region lies.
let hole_probe_share: f64 = 0.001
## A directed use of an edge in a face being split.
pub struct HalfEdge:
pub var edge: i64
pub var forward: bool
## The regions of a split face: piece p's loops are cycles
## pieces[piece_starts[p]..<piece_starts[p + 1]], each cycle's uses
## uses[cycle_starts[c]..<cycle_starts[c + 1]] (signed), the outer first.
pub struct Pieces:
pub var uses: Growing[i64]
pub var cycle_starts: Growing[usize]
pub var pieces: Growing[usize]
pub var piece_starts: Growing[usize]
pub func close():
self.uses.close()
self.cycle_starts.close()
self.pieces.close()
self.piece_starts.close()
pub func piece_count() -> usize:
return self.piece_starts.count - 1
pub func cycle(c: usize) -> const i64[]:
return self.uses.view()[self.cycle_starts.items[c]..<self.cycle_starts.items[c + 1]]
pub func piece_cycles(p: usize) -> const usize[]:
return self.pieces.view()[self.piece_starts.items[p]..<self.piece_starts.items[p + 1]]
pub func new_pieces() -> Pieces!:
var made = Pieces(Growing[i64](), Growing[usize](), Growing[usize](), Growing[usize]())
try made.cycle_starts.push(0)
try made.piece_starts.push(0)
return made
func start_of(w: const Shape*, h: HalfEdge) -> i64:
let edge = w.edges.items[(usize)h.edge]
return edge.start if h.forward else edge.end
func end_of(w: const Shape*, h: HalfEdge) -> i64:
let edge = w.edges.items[(usize)h.edge]
return edge.end if h.forward else edge.start
## The direction `h` leaves (`leaving`) or arrives back from (not leaving)
## the vertex at its start or end: a short chord, so curves leaving along
## one tangent still order by how they bend.
func half_direction(w: const Shape*, h: HalfEdge, at_start: bool, fraction: f64 = half_chord_fraction) -> Vector3!:
let e = (usize)h.edge
# The edge's own end the half-edge is at.
let own_start = at_start == h.forward
let here = try w.edge_at(e, 0.0 if own_start else 1.0)
let near = try w.edge_at(e, fraction if own_start else 1.0 - fraction)
let chord = near.subtract(here)
if chord.length() > nonzero: return chord
return try w.leaving(e, 0 if own_start else 1)
## The chord from where half-edge `h` starts to its point `distance` from
## there (its far end when it never gets that far): curves leaving one
## vertex are compared at equal distances, not at equal fractions of
## edges whose lengths may differ a thousandfold (a fillet's section
## against the long arc of the face it touches).
func half_chord(w: const Shape*, h: HalfEdge, distance: f64) -> Vector3!:
let e = (usize)h.edge
let here = try w.edge_at(e, 0.0 if h.forward else 1.0)
# The fraction reaching `distance`: doubled from a small one, then
# halved between.
var low = 0.0
var high = half_chord_start
while high < 1.0 and (try w.edge_at(e, high if h.forward else 1.0 - high)).subtract(here).length() < distance:
low = high
high = math.min(1.0, high * 2.0)
for _ in 0..<60:
let middle = (low + high) * 0.5
if (try w.edge_at(e, middle if h.forward else 1.0 - middle)).subtract(here).length() < distance: low = middle
else: high = middle
let chord = (try w.edge_at(e, high if h.forward else 1.0 - high)).subtract(here)
if chord.length() > nonzero: return chord
return try w.leaving(e, 0 if h.forward else 1)
## How far half-edge `h` reaches from where it starts (to its middle or
## its far end, whichever is further: a closed edge comes back).
func half_reach(w: const Shape*, h: HalfEdge) -> f64!:
let e = (usize)h.edge
let here = try w.edge_at(e, 0.0 if h.forward else 1.0)
return math.max((try w.edge_at(e, 0.5)).subtract(here).length(), (try w.edge_at(e, 1.0 if h.forward else 0.0)).subtract(here).length())
## Whether half-edge `a` turns clockwise from `back` before `b` does, both
## leaving along one tangent: compared on chords of equal length further
## along each until they part.
func first_clockwise(w: const Shape*, back: Vector3, a: HalfEdge, b: HalfEdge, n: Vector3) -> bool!:
let fractions: f64[4] = clockwise_fractions
let reach = math.min(try half_reach(w, a), try half_reach(w, b))
for f in fractions:
let ta = clockwise(back, try half_chord(w, a, reach * f), n)
let tb = clockwise(back, try half_chord(w, b, reach * f), n)
if math.abs(ta - tb) > clockwise_tie: return ta < tb
return false
## The clockwise turn from `back` to `to` about `n`, in (0, 2 pi].
func clockwise(back: Vector3, to: Vector3, n: Vector3) -> f64:
let a = back.subtract(n.multiply_scalar(back.dot(n)))
let b = to.subtract(n.multiply_scalar(to.dot(n)))
let counter = math.atan2(n.dot(a.cross(b)), a.dot(b))
var turn = -counter
if turn <= least_clockwise: turn += 2.0 * math.pi
return turn
## Face `f` of `w` split along `halves` (its boundary pieces and the new
## edges, both ways) into `out`.
## `pole` is the face's (face_pole).
pub func split_face(w: const Shape*, f: usize, halves: const HalfEdge[], pole: f64, out: Pieces*) -> !:
var used = Growing[bool]()
defer used.close()
for _ in halves: try used.push(false)
var cycle = Growing[i64]()
defer cycle.close()
let first_cycle = out.cycle_starts.count - 1
for first in 0..<halves.length:
if used.items[first]: continue
cycle.clear()
var at = first
var steps: usize = 0
while not used.items[at]:
used.items[at] = true
let h = halves[at]
try cycle.push((h.edge + 1) * (1 if h.forward else -1))
let vertex = end_of(w, h)
# A lone way on (a cone's apex, where the seam turns back: no
# normal there) needs no turning.
var leaving: i64 = -1
var ways = 0
for k in 0..<halves.length:
if start_of(w, halves[k]) != vertex: continue
leaving = (i64)k
ways += 1
if ways == 1:
at = (usize)leaving
steps += 1
if steps > halves.length: error(invalid, "a face being split does not close")
continue
let point = w.points.items[(usize)vertex]
let n = try w.face_normal(f, point)
let back = try half_direction(w, h, false)
# Each way on is measured a thousandth of the shortest one's
# reach from the vertex.
var near = 1.0e300
for k in 0..<halves.length:
if start_of(w, halves[k]) == vertex: near = math.min(near, try half_reach(w, halves[k]))
near *= way_on_share
var best: i64 = -1
var best_turn = 1.0e300
for k in 0..<halves.length:
if start_of(w, halves[k]) != vertex: continue
# Its own reverse comes last.
var turn = clockwise(back, try half_chord(w, halves[k], near), n)
if halves[k].edge == h.edge and halves[k].forward != h.forward: turn = 2.0 * math.pi + 1.0
if best >= 0 and math.abs(turn - best_turn) < way_on_tie:
# Leaving along one tangent (a curve touching a line, as
# a G2 blend's edge does its face's): the one that bends
# first clockwise, seen further along both.
if try first_clockwise(w, back, halves[k], halves[(usize)best], n): best = (i64)k
continue
if turn < best_turn:
best_turn = turn
best = (i64)k
if best < 0: error(invalid, "a face being split has a loose edge end")
at = (usize)best
steps += 1
if steps > halves.length: error(invalid, "a face being split does not close")
if at != first:
error(invalid, "a face being split traced into another loop")
for use in cycle.view(): try out.uses.push(use)
try out.cycle_starts.push(out.uses.count)
try group_cycles(w, f, out, first_cycle, pole)
## Turn the cycles just traced (those after the last piece) into pieces:
## positive ones bound pieces, negative ones are holes in the smallest
## piece around them.
func group_cycles(w: const Shape*, f: usize, out: Pieces*, first_cycle: usize, pole: f64) -> !:
let face = w.faces.items[f]
let cycle_count = out.cycle_starts.count - 1
# The cycles of this face are those not yet in a piece.
var areas = Growing[f64]()
defer areas.close()
var charts = Growing[Vector3]()
defer charts.close()
var chart_starts = Growing[usize]()
defer chart_starts.close()
var mine = Growing[usize]()
defer mine.close()
# Each cycle's turning sense from a coarse chart; only the positive
# ones (outlines) are charted finely, to wind round, and of each hole
# only its first two points, for the probe beside it (a plate's top
# with a hundred holes charts its outline, not every hole, each time).
var coarse = Growing[Vector3]()
defer coarse.close()
for c in first_cycle..<cycle_count:
try mine.push(c)
coarse.clear()
try loop_chart(w, face.surface, pole, out.cycle(c), &coarse, true)
let area = signed_area(coarse.view())
let signed = area if face.sense else -area
try areas.push(signed)
try chart_starts.push(charts.count)
let uses = out.cycle(c)
try loop_chart(w, face.surface, pole, uses, &charts, false, 0 if signed > 0.0 else 2)
try chart_starts.push(charts.count)
var owner = Growing[i64]()
defer owner.close()
for k in 0..<mine.count:
var best: i64 = -1
if areas.items[k] < 0.0:
# The smallest positive cycle holding a point just left of the
# hole's first segment (the side its region is on: the twin
# cycle of the same edges, running the other way, is right of it).
let a = charts.items[chart_starts.items[k]]
let next = charts.items[chart_starts.items[k] + 1] if chart_starts.items[k + 1] - chart_starts.items[k] > 1 else a
let along = next.subtract(a)
let left = Vector3(-along.y, along.x, 0.0).multiply_scalar(hole_probe_share * (1.0 if face.sense else -1.0))
let probe = a.add(along.multiply_scalar(0.5)).add(left)
var best_area = 1.0e300
for j in 0..<mine.count:
if areas.items[j] <= 0.0: continue
let loop: usize[2] = [chart_starts.items[j], chart_starts.items[j + 1]]
let support = &w.surfaces.items[(usize)face.surface]
let hit = chart_winding(charts.view(), loop[..<2], probe.x, probe.y, periodic(support), support.kind == surface_torus) != 0
if hit and areas.items[j] < best_area:
best_area = areas.items[j]
best = (i64)j
try owner.push(best)
for k in 0..<mine.count:
if areas.items[k] <= 0.0: continue
try out.pieces.push(mine.items[k])
for j in 0..<mine.count:
if owner.items[j] == (i64)k: try out.pieces.push(mine.items[j])
try out.piece_starts.push(out.pieces.count)