dymokomi/luce-geocore
Source of release 0.7.6
0.7.6 / src / verbs / bridge_rows.lucb
## A bridge's faces between one pair of chains (bridge.lucb), after
## Blender's Bridge Edge Loops and its edge-ring subdivision. The second
## chain runs reversed so both run the same way across the bridge. With as
## many edges on each side, Cuts loops of points cross between them in
## rows of quads:
##
## - Linear: each cut point on the straight line between its two ends.
## - Blend path: the loops' centers joined by a cubic Bézier leaving each
## loop square to its plane (toward the other; a straight run's way is
## square to it, toward the other run), its handles Smoothness × half
## the distance (across the normals' plane) × Blender's factor: 4/3 for
## loops side by side, down to 3/4 for loops facing. Each loop's shape
## rides along the curve, turned with it (the turn that keeps it from
## twisting), and a cut point blends where the two loops' shapes put it.
## - Blend surface: each point's own Bézier, leaving its end along the
## surface (away from the face beside the boundary).
##
## Profile swells each cut loop away from the center line (pinches below
## 0) by Profile × the shape's value, 0 at the ends and 1 halfway: the
## straight line between the centers for Linear, the Bézier otherwise. An
## open run swells along itself too, as Blender's does. A cut point's
## values blend its two ends' by where it sits. Sides of different lengths
## zip together with triangles, advancing along whichever is behind by
## length. Merge welds the second chain's points onto the first's.
## Bridge's numbers, read once.
struct BridgeSettings:
var cuts: usize
var twist: i64
var interpolation: usize
var smoothness: f64
var profile: f64
var shape: usize
var merge: bool
var factor: f64
## Pairs zipped with triangles (for the warning).
var zipped: usize
static func of(parms: Parms) -> BridgeSettings!:
let smoothness = parms.at(3)
let profile = parms.at(4)
let factor = parms.at(7)
if not math.is_finite(smoothness) or not math.is_finite(profile) or not math.is_finite(factor): error(errors.invalid, "Bridge's numbers must be finite")
return BridgeSettings((usize)math.max(0.0, math.min(64.0, parms.at(0))), (i64)math.max(-1000.0, math.min(1000.0, parms.at(1))),
(usize)math.max(0.0, math.min(2.0, parms.at(2))), math.max(0.0, smoothness), profile,
(usize)math.max(0.0, math.min(5.0, parms.at(5))), parms.at(6) != 0.0, math.max(0.0, math.min(1.0, factor)), 0)
## One side of a bridge: its points and corners in order (a closed loop
## repeats its first at the end), the distance along it to each, and the
## direction leaving the surface at each (away from the face beside it).
struct Side:
var points: Growing[i32]
var corners: Growing[i32]
var along: Growing[f64]
var outward: Growing[Vector3]
func init():
self.points = Growing[i32]()
self.corners = Growing[i32]()
self.along = Growing[f64]()
self.outward = Growing[Vector3]()
func close():
self.points.close()
self.corners.close()
self.along.close()
self.outward.close()
## Its center as Blender weighs it: each point by the lengths of the
## two edges at it, round the loop (an open run closed by its chord).
func center(mesh: const Mesh*, closed: bool) -> Vector3:
let count = self.points.count - (1 if closed else 0)
var sum = Vector3()
var mean = Vector3()
var total = 0.0
for at in 0..<count:
let here = point_of(mesh, self.points.items[at])
let before = point_of(mesh, self.points.items[(at + count - 1) % count])
let after = point_of(mesh, self.points.items[(at + 1) % count])
let weight = here.subtract(before).length() + after.subtract(here).length()
sum = sum.add(here.multiply_scalar(weight))
mean = mean.add(here)
total += weight
if total > 0.0: return sum.multiply_scalar(1.0 / total)
return mean.multiply_scalar(1.0 / (f64)count)
## Its plane's normal (Newell's over its points, round the loop). A
## straight run has none: then square to it, along `toward` (Blender's
## aligned normal). Nearly straight counts as straight, against the
## loop's size, so rounding never picks a way at random.
func normal(mesh: const Mesh*, closed: bool, toward: Vector3) -> Vector3:
let count = self.points.count - (1 if closed else 0)
var sum = Vector3()
var aligned = Vector3()
var perimeter = 0.0
for at in 0..<count:
let p = point_of(mesh, self.points.items[at])
let q = point_of(mesh, self.points.items[(at + 1) % count])
sum = sum.add(p.cross(q))
let way = q.subtract(p)
perimeter += way.length()
aligned = aligned.add(way.cross(toward.cross(way)))
if sum.length() > 0.000001 * perimeter * perimeter: return unit_of(sum)
if aligned.length() > 0.0: return unit_of(aligned)
return unit_of(toward) if toward.length() > 0.0 else Vector3(0.0, 1.0, 0.0)
## The way out of the surface across the boundary edge of corner `corner`:
## along its face, square to the edge, away from the face.
func edge_outward(mesh: const Mesh*, topology: const Topology*, corner: usize) -> Vector3:
let a = point_of(mesh, topology.corners[corner])
let b = point_of(mesh, topology.corners[topology.next(corner)])
let normal = mesh.face_normal_span()[(usize)topology.corner_faces[corner]].vector()
let out = b.subtract(a).cross(normal)
let length = out.length()
return out.multiply_scalar(1.0 / length) if length > 0.0 else Vector3()
## Chain point `index`'s way out: the mean of its chain edges'.
func chain_outward(mesh: const Mesh*, topology: const Topology*, chains: const Chains*, chain: usize, index: usize) -> Vector3:
let start = (usize)chains.starts.items[chain]
let size = chains.size(chain)
let closed = chains.closed.items[chain] != 0
var sum = Vector3()
if index < size: sum = sum.add(edge_outward(mesh, topology, (usize)chains.corners.items[start + index]))
if index > 0: sum = sum.add(edge_outward(mesh, topology, (usize)chains.corners.items[start + index - 1]))
elif closed: sum = sum.add(edge_outward(mesh, topology, (usize)chains.corners.items[start + size - 1]))
let length = sum.length()
return sum.multiply_scalar(1.0 / length) if length > 0.0 else sum
## The first chain as it runs; the second reversed (so both run the same way
## across the bridge), starting nearest the first's start for loops.
func side_of(mesh: const Mesh*, topology: const Topology*, chains: const Chains*, chain: usize, reversed: bool, align: Vector3, twist: i64, side: Side*) -> !:
let size = chains.size(chain)
let closed = chains.closed.items[chain] == 1
let total = size if closed else size + 1
var shift: usize = 0
if closed and reversed:
var nearest = -1.0
for index in 0..<total:
let (point, _) = chain_point(topology, chains, chain, total - 1 - index)
let distance = point_of(mesh, point).subtract(align).length()
if nearest < 0.0 or distance < nearest:
nearest = distance
shift = index
shift = (usize)(((i64)shift + twist % (i64)total + (i64)total) % (i64)total)
for step in 0..<total + (1 if closed else 0):
var index = (step + shift) % total
if reversed: index = total - 1 - index
let (point, corner) = chain_point(topology, chains, chain, index)
try side.points.push(point)
try side.corners.push(corner)
try side.outward.push(chain_outward(mesh, topology, chains, chain, index))
let length = 0.0 if step == 0 else side.along.items[step - 1] + point_of(mesh, point).subtract(point_of(mesh, side.points.items[step - 1])).length()
try side.along.push(length)
## Blender's Bézier handle length between `a` leaving along `out_a` and `b`
## along `out_b` (both unit, toward each other): half their distance
## across the plane of the two ways, times 4/3 for parallel ways (a
## half circle's) down to 3/4 as they come to face each other.
func handle_length(a: Vector3, out_a: Vector3, b: Vector3, out_b: Vector3) -> f64:
let facing = out_a.dot(out_b)
var factor = 4.0 / 3.0
if facing < 0.0:
let t = 1.0 + facing
factor = factor * t + 0.75 * (1.0 - t)
var gap = b.subtract(a)
let across = out_a.cross(out_b)
if across.length() > 0.0001:
let axis = unit_of(across)
gap = gap.subtract(axis.multiply_scalar(gap.dot(axis)))
return gap.length() * 0.5 * factor
## `v` turned by `angle` about unit `axis` (Rodrigues).
func axis_turned(v: Vector3, axis: Vector3, angle: f64) -> Vector3:
let c = math.cos(angle)
return v.multiply_scalar(c).add(axis.cross(v).multiply_scalar(math.sin(angle))).add(axis.multiply_scalar(axis.dot(v) * (1.0 - c)))
## A turn, as the images of the X, Y and Z axes.
struct LoopTurn:
var x: Vector3
var y: Vector3
var z: Vector3
static func identity() -> LoopTurn:
return LoopTurn(Vector3(1.0, 0.0, 0.0), Vector3(0.0, 1.0, 0.0), Vector3(0.0, 0.0, 1.0))
func apply(v: Vector3) -> Vector3:
return self.x.multiply_scalar(v.x).add(self.y.multiply_scalar(v.y)).add(self.z.multiply_scalar(v.z))
## The turn undone (a rotation's transpose).
func undo(v: Vector3) -> Vector3:
return Vector3(self.x.dot(v), self.y.dot(v), self.z.dot(v))
## This turn followed by `angle` about `axis`.
func followed(axis: Vector3, angle: f64) -> LoopTurn:
return LoopTurn(axis_turned(self.x, axis, angle), axis_turned(self.y, axis, angle), axis_turned(self.z, axis, angle))
## The cubic Bézier from `a` to `b` with handles `h` and `k`, at `t`.
func bezier(a: Vector3, h: Vector3, k: Vector3, b: Vector3, t: f64) -> Vector3:
let s = 1.0 - t
return a.multiply_scalar(s * s * s).add(h.multiply_scalar(3.0 * s * s * t)).add(k.multiply_scalar(3.0 * s * t * t)).add(b.multiply_scalar(t * t * t))
## The profile's swell at `t` (0 at the ends, 1 halfway, before Profile).
func profile_shape(shape: usize, t: f64) -> f64:
let f = 1.0 - math.abs(1.0 - 2.0 * t)
match shape:
0: return f * f * (3.0 - 2.0 * f)
1: return math.sqrt(math.max(0.0, 2.0 * f - f * f))
2: return math.sqrt(f)
3: return f * f
4: return f
_: return f * (2.0 - f)
func bridge_pair(mesh: const Mesh*, topology: const Topology*, chains: Chains*, first: usize, second: usize, settings: BridgeSettings*, builder: TopologyBuilder*) -> !:
var a = Side()
defer a.close()
var b = Side()
defer b.close()
try side_of(mesh, topology, chains, first, false, Vector3(), 0, &a)
try side_of(mesh, topology, chains, second, true, point_of(mesh, a.points.items[0]), settings.twist, &b)
let n = a.points.count - 1
let m = b.points.count - 1
let face = topology.corner_faces[(usize)a.corners.items[0]]
if n != m:
settings.zipped += 1
return try zip_sides(&a, &b, face, builder)
let closed = chains.closed.items[first] == 1
let rows = settings.cuts + 1
# The center line (for Blend path and the profile).
let center_a = a.center(mesh, closed)
let center_b = b.center(mesh, closed)
let toward = center_b.subtract(center_a)
var normal_a = a.normal(mesh, closed, toward)
var normal_b = b.normal(mesh, closed, toward)
if normal_a.dot(toward) < 0.0: normal_a = normal_a.multiply_scalar(-1.0)
if normal_b.dot(toward) > 0.0: normal_b = normal_b.multiply_scalar(-1.0)
let reach = handle_length(center_a, normal_a, center_b, normal_b) * settings.smoothness
let handle_a = center_a.add(normal_a.multiply_scalar(reach))
let handle_b = center_b.add(normal_b.multiply_scalar(reach))
# Per row: the center line's point, the profile's swell and (Blend
# path) the loop's turn there, carried along the curve from the first.
let line = try new Vector3[rows + 1] --- in memory.heap
defer free(line) in memory.heap
let swell = try new f64[rows + 1] --- in memory.heap
defer free(swell) in memory.heap
let turns = try new LoopTurn[rows + 1] --- in memory.heap
defer free(turns) in memory.heap
for row in 0..<rows + 1:
let t = (f64)row / (f64)rows
line[row] = center_a.add(toward.multiply_scalar(t)) if settings.interpolation == 0 else bezier(center_a, handle_a, handle_b, center_b, t)
swell[row] = 1.0 + settings.profile * profile_shape(settings.shape, t)
turns[row] = LoopTurn.identity()
if settings.interpolation == 1:
var before = normal_a
for row in 1..<rows + 1:
var way = normal_b.multiply_scalar(-1.0)
if row < rows: way = unit_of(unit_of(line[row].subtract(line[row - 1])).add(unit_of(line[row + 1].subtract(line[row]))))
let axis = before.cross(way)
let angle = math.atan2(axis.length(), before.dot(way))
turns[row] = turns[row - 1].followed(unit_of(axis), angle) if axis.length() > 0.000000001 else turns[row - 1]
before = way
# Rows between the sides: row 0 is the first chain, row `rows` the second.
let ids = try new i32[(n + 1) * (rows + 1)] --- in memory.heap
defer free(ids) in memory.heap
for index in 0..<n + 1:
ids[index] = a.points.items[index]
ids[rows * (n + 1) + index] = b.points.items[index]
let start = point_of(mesh, a.points.items[index])
let end = point_of(mesh, b.points.items[index])
for row in 1..<rows:
let t = (f64)row / (f64)rows
# A closed loop's last point is its first.
if index == n and closed:
ids[row * (n + 1) + index] = ids[row * (n + 1)]
continue
var placed = start.add(end.subtract(start).multiply_scalar(t))
if settings.interpolation == 1:
# Each loop's shape carried to this row, swelled; blended.
let row_turn = turns[row]
let from_a = line[row].add(row_turn.apply(start.subtract(center_a)).multiply_scalar(swell[row]))
let from_b = line[row].add(row_turn.apply(turns[rows].undo(end.subtract(center_b))).multiply_scalar(swell[row]))
placed = from_a.add(from_b.subtract(from_a).multiply_scalar(t))
else:
if settings.interpolation == 2:
let out_a = a.outward.items[index]
let out_b = b.outward.items[index]
let length = handle_length(start, out_a, end, out_b) * settings.smoothness
placed = bezier(start, start.add(out_a.multiply_scalar(length)), end.add(out_b.multiply_scalar(length)), end, t)
placed = line[row].add(placed.subtract(line[row]).multiply_scalar(swell[row]))
let parents: i32[2] = [a.points.items[index], b.points.items[index]]
let weights: f32[2] = [(f32)(1.0 - t), (f32)t]
ids[row * (n + 1) + index] = try builder.mixed_point(placed, parents[..<2], weights[..<2])
for row in 0..<rows:
for index in 0..<n:
try builder.face(face)
try bridge_corner(builder, ids[row * (n + 1) + index + 1], &a, &b, index + 1, row, rows)
try bridge_corner(builder, ids[row * (n + 1) + index], &a, &b, index, row, rows)
try bridge_corner(builder, ids[(row + 1) * (n + 1) + index], &a, &b, index, row + 1, rows)
try bridge_corner(builder, ids[(row + 1) * (n + 1) + index + 1], &a, &b, index + 1, row + 1, rows)
try builder.end_face()
## Sides of different lengths: triangles, advancing along whichever side is
## behind, by its share of its length.
func zip_sides(a: const Side*, b: const Side*, face: i32, builder: TopologyBuilder*) -> !:
let n = a.points.count - 1
let m = b.points.count - 1
let length_a = math.max(a.along.items[n], 0.000000001)
let length_b = math.max(b.along.items[m], 0.000000001)
var i: usize = 0
var j: usize = 0
while i < n or j < m:
let advance_a = j == m or (i < n and a.along.items[i + 1] / length_a <= b.along.items[j + 1] / length_b)
try builder.face(face)
if advance_a:
try builder.corner(a.points.items[i + 1], a.corners.items[i + 1])
try builder.corner(a.points.items[i], a.corners.items[i])
try builder.corner(b.points.items[j], b.corners.items[j])
i += 1
else:
try builder.corner(a.points.items[i], a.corners.items[i])
try builder.corner(b.points.items[j], b.corners.items[j])
try builder.corner(b.points.items[j + 1], b.corners.items[j + 1])
j += 1
try builder.end_face()
## A bridge corner at `index` on row `row`: the first side's corner values,
## blended toward the second side's across the rows.
func bridge_corner(builder: TopologyBuilder*, point: i32, a: const Side*, b: const Side*, index: usize, row: usize, rows: usize) -> !:
if row == 0: return try builder.corner(point, a.corners.items[index])
if row == rows: return try builder.corner(point, b.corners.items[index])
let t = (f32)row / (f32)rows
let parents: i32[2] = [a.corners.items[index], b.corners.items[index]]
let weights: f32[2] = [1.0 - t, t]
try builder.mixed_corner(point, parents[..<2], weights[..<2])
## Merge: each pair of as many edges welds, the second chain's points onto
## the first's, which move Merge factor of the way to them; the rebuilt
## mesh keeps the merged edges selected. Pairs of different lengths stay.
func merge_pairs(mesh: const Mesh*, topology: const Topology*, chains: Chains*, partner: const i32[], settings: BridgeSettings*, builder: TopologyBuilder*) -> !:
let points = topology.points
let target = try new i32[points] --- in memory.heap
defer free(target) in memory.heap
let places = try new Vector3[points] --- in memory.heap
defer free(places) in memory.heap
for at in 0..<points:
target[at] = (i32)at
places[at] = point_of(mesh, (i32)at)
var a = Side()
defer a.close()
var b = Side()
defer b.close()
var welded = Growing[i32]()
defer welded.close()
for chain in 0..<chains.count():
if partner[chain] <= (i32)chain: continue
a.points.clear()
a.corners.clear()
a.along.clear()
a.outward.clear()
b.points.clear()
b.corners.clear()
b.along.clear()
b.outward.clear()
try side_of(mesh, topology, chains, chain, false, Vector3(), 0, &a)
try side_of(mesh, topology, chains, (usize)partner[chain], true, point_of(mesh, a.points.items[0]), settings.twist, &b)
if a.points.count != b.points.count:
settings.zipped += 1
continue
for index in 0..<a.points.count:
let keep = a.points.items[index]
let other = b.points.items[index]
target[(usize)other] = keep
places[(usize)keep] = point_of(mesh, keep).add(point_of(mesh, other).subtract(point_of(mesh, keep)).multiply_scalar(settings.factor))
if index > 0:
try welded.push(a.points.items[index - 1])
try welded.push(keep)
# The faces over the welded points (cleanup.lucb's rebuild, by hand: the
# builder already holds the input's faces).
try weld_faces(mesh, topology, target[..<points], places[..<points], builder)
for at in 0..<welded.count // 2: try builder.select_edge(welded.items[at * 2], welded.items[at * 2 + 1])
try builder.drop_unused_points()
## The builder's faces (copied from the input) with every point mapped
## through `target`, the kept points at `places`.
func weld_faces(mesh: const Mesh*, topology: const Topology*, target: const i32[], places: const Vector3[], builder: TopologyBuilder*) -> !:
for point in 0..<target.length:
if target[point] != (i32)point: builder.move_point(target[point], places[(usize)target[point]])
for at in 0..<builder.corners.count: builder.corners.items[at] = target[(usize)builder.corners.items[at]]