dymokomi/luce-geocore
Source of release 0.7.8
0.7.8 / src / verbs / bevel_widths.lucb
## Widths after the halves are known: Clamp overlap, the even-widths pass
## along loop-slid chains, and which side a Custom profile starts from.
##
## Clamp overlap finds the widest bevel before anything collides, assuming
## every width grows in proportion with Width: the strip of an edge between
## two others collapses when the offset lines of its neighbours meet across
## it; a side sliding along an unbeveled edge runs out of edge; two points
## cut off along one edge (Affect Vertices) meet. Every width scales down to
## just short of the smallest such width.
##
## Loop slide puts a boundary point on an unbeveled edge, which leaves the
## strips either side with slightly different widths at that point. The
## even-widths pass follows the chains (or cycles) of such points along
## their strips and solves, in the least-squares sense, for widths that
## agree at both ends of each strip while staying near what was asked for.
## How far short of a collision Clamp overlap stops, as a share of the
## width.
let clamp_margin: f64 = 0.0001
## Scale every width down to where nothing collides.
func limit_widths(work: Bevel*) -> !:
let asked = work.width
if asked <= 0.0: return
# The least reach of each range of halves, ranges in parallel.
let ranges = (work.halves.count + clamp_range - 1) // clamp_range
var reaches = try new f64[ranges] --- in memory.heap
defer free(reaches) in memory.heap
var clamping = Clamping(work, reaches[..<ranges], 1.0)
try parallel.for_each_range(work.halves.count, clamp_range, (void*)&clamping, reach_range)
var limited = asked
for reach in reaches[..<ranges]: limited = math.min(limited, reach)
if limited >= asked: return
# Just short of the collision, so the faces squeezed between keep an
# area.
limited *= 1.0 - clamp_margin
clamping.factor = limited / asked
try parallel.for_each_range(work.halves.count, clamp_range, (void*)&clamping, scale_range)
work.width = limited
let clamp_range: usize = 4096
struct Clamping:
var work: Bevel*
var reaches: f64[]
var factor: f64
func reach_range(context: void*, first: usize, end: usize, worker: usize) -> !:
let clamping = (Clamping*)context
let work = clamping.work
var limited = work.width
for at in first..<end:
let reach = vertex_collision(work, (i32)at) if work.settings.vertices else strip_collision(work, (i32)at)
limited = math.min(limited, reach)
clamping.reaches[first // clamp_range] = limited
func scale_range(context: void*, first: usize, end: usize, worker: usize) -> !:
let clamping = (Clamping*)context
let halves = clamping.work.halves.items
let factor = clamping.factor
for at in first..<end:
halves[at].spec_left *= factor
halves[at].spec_right *= factor
halves[at].offset_left *= factor
halves[at].offset_right *= factor
## The width at which the strip of `half` (going from its vertex b to c, in
## the face after it, between edges a-b and c-d) collapses or runs out of
## room sliding along a neighbour.
func strip_collision(work: const Bevel*, half: i32) -> f64:
let unlimited = work.width + 1000000.0
let item = work.halves.items[(usize)half]
var kb = item.spec_left
let next_one = next_half(work, half)
let ka = work.halves.items[(usize)next_one].spec_right
let b = vertex_at(work, item.slot)
let c = input_point(work, item.other)
let a = input_point(work, work.halves.items[(usize)next_one].other)
let far = far_half(work, half)
let kind = work.settings.width_type
if kind == width_percent or kind == width_absolute:
if work.halves.items[(usize)next_one].beveled and far >= 0 and work.halves.items[(usize)previous_half(work, far)].beveled:
if kind == width_percent: return 50.0
let length = c.subtract(b).length()
return length / 2.0 if work.width > length / 2.0 else length
return unlimited
var kc = 0.0
var d = Vector3()
var c_edge: i32 = -1
if far >= 0:
let previous_far = previous_half(work, far)
kc = work.halves.items[(usize)previous_far].spec_left
d = input_point(work, work.halves.items[(usize)previous_far].other)
c_edge = work.halves.items[(usize)previous_far].edge
else:
# The point after c in the face after the strip's edge.
if item.after < 0: return unlimited
let at_c = face_corner(work, item.after, item.other)
if at_c < 0: return unlimited
d = input_point(work, work.topology.corners[work.topology.next((usize)at_c)])
if work.halves.items[(usize)next_one].edge == item.edge or c_edge == item.edge: return unlimited
let angle1 = corner_angle(a, b, c)
let angle2 = corner_angle(b, c, d)
var limit = unlimited
# The strip collapses where its neighbours' offset lines meet across it.
let projected = safe_ratio(ka + math.cos(angle1) * kb, math.sin(angle1)) + safe_ratio(kc + math.cos(angle2) * kb, math.sin(angle2))
if projected > tiny:
let reach = work.width * (c.subtract(b).length() / projected)
if reach > tiny: limit = reach
# A side sliding along an unbeveled neighbour runs out of that edge (and
# those in line with it).
if kb > 0.0000001 and (ka == 0.0 or kc == 0.0) and item.after >= 0:
kb = work.width / kb
let topology = &work.topology
let size = (usize)topology.offsets[(usize)item.after + 1] - (usize)topology.offsets[(usize)item.after]
if ka == 0.0:
let at_a = face_corner(work, item.after, work.halves.items[(usize)next_one].other)
if at_a >= 0:
var corner = (usize)at_a
var side = 0.0
var exterior = math.pi - angle1
for step in 0..<size:
if step > 0:
corner = topology.previous(corner)
exterior += math.pi - corner_angle(input_point(work, topology.corners[corner]), input_point(work, topology.corners[topology.next(corner)]), input_point(work, topology.corners[topology.next(topology.next(corner))]))
side += corner_edge_length(work, corner) * math.sin(exterior)
if exterior >= 0.0001: break
limit = math.min(side * kb, limit)
if kc == 0.0:
let at_b = face_corner(work, item.after, work.vertices.items[(usize)item.slot].point)
if at_b >= 0:
var corner = topology.next((usize)at_b)
var side = 0.0
var exterior = math.pi - angle2
for step in 0..<size:
if step > 0:
corner = topology.next(corner)
exterior += math.pi - corner_angle(input_point(work, topology.corners[topology.previous(corner)]), input_point(work, topology.corners[corner]), input_point(work, topology.corners[topology.next(corner)]))
side += corner_edge_length(work, corner) * math.sin(exterior)
if exterior >= 0.0001: break
limit = math.min(side * kb, limit)
return limit
func safe_ratio(a: f64, b: f64) -> f64:
return 0.0 if b == 0.0 else a / b
## The length of the edge leaving input corner `corner`.
func corner_edge_length(work: const Bevel*, corner: usize) -> f64:
let topology = &work.topology
return input_point(work, topology.corners[topology.next(corner)]).subtract(input_point(work, topology.corners[corner])).length()
## Affect Vertices: the width at which the points slid toward each other
## along `half`'s edge from its two ends meet.
func vertex_collision(work: const Bevel*, half: i32) -> f64:
let unlimited = work.width + 1000000.0
if work.width == 0.0: return unlimited
let ka = work.halves.items[(usize)half].spec_left / work.width
let far = far_half(work, half)
let kb = work.halves.items[(usize)far].spec_left / work.width if far >= 0 else 0.0
if ka + kb <= 0.0: return unlimited
return half_length(work, half) / (ka + kb)
## Even the widths along chains and cycles of loop-slid boundary points,
## then place the rings they changed again.
func even_widths(work: Bevel*) -> !:
var evened = false
for slot in 0..<work.vertices.count:
let vertex = work.vertices.items[slot]
for at in vertex.first_bound..<vertex.first_bound + vertex.bounds:
let anchor = (i32)at
if work.bounds.items[at].visited or work.bounds.items[at].on < 0: continue
var start = anchor
var end = anchor
var current = anchor
var cycle = false
var length = 1
# Forward: each point's first half's strip leads to the left
# point at its other end.
while work.bounds.items[(usize)current].on >= 0 and not work.bounds.items[(usize)current].visited and not cycle:
work.bounds.items[(usize)current].visited = true
let first = work.bounds.items[(usize)current].first
if first < 0: break
let across = far_half(work, first)
if across < 0: break
let following = work.halves.items[(usize)across].left
work.bounds.items[(usize)current].chain = following
end = following
length += 1
if work.bounds.items[(usize)following].visited:
if following != start: break
try even_chain(work, start, true)
evened = true
cycle = true
current = following
if cycle: continue
# Backward from the start along each point's last half.
work.bounds.items[(usize)current].chain = -1
current = start
while true:
work.bounds.items[(usize)current].visited = true
let last = work.bounds.items[(usize)current].last
if last < 0: break
let across = far_half(work, last)
if across < 0: break
let preceding = work.halves.items[(usize)across].right
work.bounds.items[(usize)preceding].chain = current
length += 1
start = preceding
current = preceding
if work.bounds.items[(usize)current].visited or work.bounds.items[(usize)current].on < 0: break
if length >= 3 and work.bounds.items[(usize)start].on < 0 and work.bounds.items[(usize)end].on < 0:
try even_chain(work, start, false)
evened = true
if not evened: return
try parallel.for_each_range(work.vertices.count, 256, (void*)work, place_range)
## Place every ring again at the evened widths, vertices in parallel.
func place_range(context: void*, first: usize, end: usize, worker: usize) -> !:
let work = (Bevel*)context
for slot in first..<end: try build_boundary(work, slot, false)
## How strongly the widths keep to what was asked, against agreeing at both
## ends of a strip.
let spec_weight: f64 = 0.2
## One chain (or cycle) from `start` along Bound.chain. Unknown i is the
## right width of point i's first half (the last point of a chain: the left
## width of its last half); point i's last half's left width is its sine
## ratio times unknown i. Rows: strip i's right width at point i equals its
## left width at point i + 1, and, weighted down, each width near its spec.
func even_chain(work: Bevel*, start: i32, cycle: bool) -> !:
var points = Growing[i32]()
defer points.close()
var current = start
while current >= 0:
try points.push(current)
current = work.bounds.items[(usize)current].chain
if current == start: break
if points.count > work.bounds.count: break
let count = points.count
if count < 2: return
var rows = Growing[i64]()
defer rows.close()
var columns = Growing[i64]()
defer columns.close()
var values = Growing[f64]()
defer values.close()
var targets = Growing[f64]()
defer targets.close()
var row: i64 = 0
let links = count if cycle else count - 1
for i in 0..<links:
let following = (i + 1) % count
let ratio = work.bounds.items[(usize)points.items[following]].sine_ratio
try add_entry_at(&rows, &columns, &values, row, (i64)i, 1.0)
let last_of_chain = not cycle and following == count - 1
try add_entry_at(&rows, &columns, &values, row, (i64)following, -1.0 if last_of_chain else -ratio)
try targets.push(0.0)
row += 1
for i in 0..<count:
let bound = work.bounds.items[(usize)points.items[i]]
if cycle or i < count - 1:
let right = work.halves.items[(usize)bound.first].offset_right
try add_entry_at(&rows, &columns, &values, row, (i64)i, spec_weight)
try targets.push(spec_weight * right)
row += 1
if (cycle or i > 0) and bound.last >= 0:
let left = work.halves.items[(usize)bound.last].offset_left
let ratio = 1.0 if (not cycle and i == count - 1) else bound.sine_ratio
try add_entry_at(&rows, &columns, &values, row, (i64)i, spec_weight * ratio)
try targets.push(spec_weight * left)
row += 1
var solution = Growing[f64]()
defer solution.close()
try least_squares(rows.view(), columns.view(), values.view(), targets.view(), count, &solution)
for i in 0..<count:
let bound = work.bounds.items[(usize)points.items[i]]
let value = solution.items[i]
if cycle or i < count - 1:
work.halves.items[(usize)bound.first].offset_right = value
if (cycle or i > 0) and bound.last >= 0: work.halves.items[(usize)bound.last].offset_left = bound.sine_ratio * value
elif bound.last >= 0:
work.halves.items[(usize)bound.last].offset_left = value
func add_entry_at(rows: Growing[i64]*, columns: Growing[i64]*, values: Growing[f64]*, row: i64, column: i64, value: f64) -> !:
try rows.push(row)
try columns.push(column)
try values.push(value)
## The least-squares solution of the sparse system (entries by row and
## column) by conjugate gradients on its normal equations (CGLS).
func least_squares(rows: const i64[], columns: const i64[], values: const f64[], targets: const f64[], count: usize, solution: Growing[f64]*) -> !:
let row_count = targets.length
try solution.fill(count, 0.0)
var residual = Growing[f64]()
defer residual.close()
try residual.assign(targets)
var gradient = Growing[f64]()
defer gradient.close()
try gradient.fill(count, 0.0)
var direction = Growing[f64]()
defer direction.close()
var product = Growing[f64]()
defer product.close()
try product.fill(row_count, 0.0)
transpose_times(rows, columns, values, residual.view(), gradient.items)
try direction.assign(gradient.view())
var gradient_norm = dot_of(gradient.view(), gradient.view())
let first_norm = gradient_norm
for _ in 0..<count * 4 + 8:
if gradient_norm <= first_norm * 0.000000000000000000000001 or gradient_norm == 0.0: break
for at in 0..<row_count: product.items[at] = 0.0
for at in 0..<rows.length: product.items[(usize)rows[at]] += values[at] * direction.items[(usize)columns[at]]
let curvature = dot_of(product.view(), product.view())
if curvature == 0.0: break
let step = gradient_norm / curvature
for at in 0..<count: solution.items[at] += step * direction.items[at]
for at in 0..<row_count: residual.items[at] -= step * product.items[at]
transpose_times(rows, columns, values, residual.view(), gradient.items)
let next_norm = dot_of(gradient.view(), gradient.view())
let beta = next_norm / gradient_norm
for at in 0..<count: direction.items[at] = gradient.items[at] + beta * direction.items[at]
gradient_norm = next_norm
func transpose_times(rows: const i64[], columns: const i64[], values: const f64[], vector: const f64[], into: f64[]):
for at in 0..<into.length: into[at] = 0.0
for at in 0..<rows.length: into[(usize)columns[at]] += values[at] * vector[(usize)rows[at]]
func dot_of(a: const f64[], b: const f64[]) -> f64:
var sum = 0.0
for at in 0..<a.length: sum += a[at] * b[at]
return sum
## Custom profile: along every chain of beveled edges the profile starts
## from one consistent side, so an asymmetric profile does not flip from
## strip to strip. Each chain starts on the side of its first strip whose
## boundary point is higher (Y).
func orient_profiles(work: Bevel*):
let topology = &work.topology
for edge in 0..<topology.edges():
if not work.beveled.view().get(edge): continue
let slot = work.slot_of.items[(usize)topology.edge_points[edge * 2]]
if slot < 0: continue
let start = half_of(work, slot, (i32)edge)
if start < 0 or work.halves.items[(usize)start].visited: continue
let left = work.halves.items[(usize)start].left
let right = work.halves.items[(usize)start].right
let right_highest = work.bounds.items[(usize)left].position.y < work.bounds.items[(usize)right].position.y
work.bounds.items[(usize)left].profile_start = right_highest
work.halves.items[(usize)start].visited = true
for pass in 0..<2:
var toward = pass == 0
var half = next_beveled(work, start, toward)
while half >= 0 and not work.halves.items[(usize)half].visited:
let flag = (toward != right_highest) if pass == 0 else ((not toward) != right_highest)
work.bounds.items[(usize)work.halves.items[(usize)half].left].profile_start = flag
toward = not toward
work.halves.items[(usize)half].visited = true
half = next_beveled(work, half, toward)
## The next beveled half along a chain: the other end of `half`'s edge, or
## (`across`) the beveled half at its vertex that continues it most
## straight, when that one is clearly the straightest.
func next_beveled(work: const Bevel*, half: i32, across: bool) -> i32:
if not across: return far_half(work, half)
let vertex = work.vertices.items[(usize)work.halves.items[(usize)half].slot]
if vertex.selected == 1: return -1
let incoming = half_direction(work, half).multiply_scalar(-1.0)
var best: i32 = -1
var best_dot = 0.0
var second_dot = 0.0
var other = next_half(work, half)
while other != half:
if work.halves.items[(usize)other].beveled:
if vertex.selected == 2: return other
let dot = half_direction(work, other).dot(incoming)
if dot > best_dot:
second_dot = best_dot
best_dot = dot
best = other
elif dot > second_dot:
second_dot = dot
other = next_half(work, other)
if best >= 0 and math.abs(best_dot - second_dot) < 0.015: return -1
return best