dymokomi/luce-cad
Source of release 0.9.4
0.9.4 / src / tessellation / trim_layout.lucb
## Cross-patch station planning and canonical CAD-edge/grid intersections.
## Regular UV directions continue through irregular trims when compatible;
## non-isoparametric trims cut cells without bending every interior row.
## Initialize and reconcile layouts before shared vertices are allocated.
## Invalid/over-budget layouts fall back; their already registered edge cuts are
## still shared by both incident faces. No tolerance welding is performed.
pub func plan_layouts(vertices: const Vector3[], edges: const Curve[], surfaces: const Surface[], faces: const BrepFace[], sides: const PatchSides[], cuts: Stations[], metrics: const ArcMetric[], plans: GridLayout[], divisions: i64, tolerance: f64, edge_size: f64) -> !:
let settled = try new Settled[faces.length] --- in memory.heap
defer free(settled) in memory.heap
for at in 0..<settled.length: settled[at] = Settled()
try balance(faces, edges, sides, cuts, metrics, plans, tolerance, settled)
# Seeding reads shared cuts and writes only its own face's plan: faces run
# on the pool, and errors are raised in face order as the serial loop did.
var errors = try FaceErrors(faces.length)
defer errors.close()
var seeding = Seeding(vertices = vertices, edges = edges, surfaces = surfaces, faces = faces, sides = sides, cuts = cuts, plans = plans, divisions = divisions, tolerance = tolerance, edge_size = edge_size, errors = &errors)
try parallel.for_each(faces.length, (void*)&seeding, seed_item)
try errors.raise()
# Crossing roots and inversions are remembered per face for the whole
# plan: later passes re-intersect unchanged segments, and each serial pass
# first gets a parallel speculative fill (see trim_memo).
let memos = try new TrimMemo[faces.length] --- in memory.heap
for at in 0..<memos.length: memos[at] = TrimMemo()
defer close_memos(memos)
for pass in 0..<8:
var changed = false
try speculate(vertices, edges, surfaces, faces, cuts, plans, memos, tolerance)
for at in 0..<faces.length:
if not plans[at].valid: continue
let grew = reconcile(&plans[at], faces[at], surfaces[(usize)faces[at].surface], vertices, edges, cuts, tolerance, pass < 7, &memos[at]) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
plans[at].valid = false
recover false
changed = changed or grew
if not changed: break
# Mapped neighbors can publish new opposite-side rows while absorbing clip
# intersections. Reconcile both representations together before freezing;
# one final balance alone leaves stale grid rows on the clipped side.
for pass in 0..<12:
var before: usize = 0
for cut in cuts: before += cut.count
try balance(faces, edges, sides, cuts, metrics, plans, tolerance, settled)
try speculate(vertices, edges, surfaces, faces, cuts, plans, memos, tolerance)
for at in 0..<faces.length:
if not plans[at].valid: continue
_ = reconcile(&plans[at], faces[at], surfaces[(usize)faces[at].surface], vertices, edges, cuts, tolerance, true, &memos[at]) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
plans[at].valid = false
recover false
var after: usize = 0
for cut in cuts: after += cut.count
if after == before: break
# Freeze the final boundary chains after the last shared-edge insertion.
try redistribute(faces, edges, metrics, cuts, plans)
try regularize_extrusions(faces, surfaces, edges, sides, metrics, cuts, plans, tolerance)
for at in 0..<faces.length:
if not plans[at].valid: continue
for use in 0..<faces[at].uses.length:
let index = edge_index(faces[at].uses[use])
_ = try cached(&plans[at].chains[use], surfaces[(usize)faces[at].surface], vertices, edges[index], cuts[index], tolerance)
struct Seeding:
let vertices: const Vector3[]
let edges: const Curve[]
let surfaces: const Surface[]
let faces: const BrepFace[]
let sides: const PatchSides[]
let cuts: const Stations[]
let plans: GridLayout[]
let divisions: i64
let tolerance: f64
let edge_size: f64
let errors: FaceErrors*
func seed_item(raw: void*, at: usize, worker: usize):
let job = (Seeding*)raw
seed_face(job, at) catch failure:
job.errors.record(at, failure.code, failure.message)
## Choose a face's chart strategy and seed its clipped-grid layout.
func seed_face(job: Seeding*, at: usize) -> !:
let faces = job.faces
let edges = job.edges
let vertices = job.vertices
let sides = job.sides
let plans = job.plans
let divisions = job.divisions
let tolerance = job.tolerance
let s = job.surfaces[(usize)faces[at].surface]
# Cylinders/cones have regular analytic charts too. An oblique end trim
# must be allowed to cut those rows instead of forcing the entire fillet
# through the constrained triangle path (constrained_face).
if s.kind != surface_plane and s.kind != surface_cylinder and s.kind != surface_cone and s.kind != surface_spline: return
# Most four-sided domains retain their transfinite layout. A stopped
# oblique trim instead cuts a support grid;
# the number of CAD coedges alone cannot make that mapping compatible.
if sides[at].valid:
let preferred = prefers_clipping(faces[at], s, edges, plans[at].flow, tolerance) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
recover false
plans[at].cut_first = plans[at].cut_first or preferred
if not plans[at].cut_first and s.kind == surface_plane:
plans[at].cut_first = not (try can_map_plane(vertices, edges, faces[at], s, plans[at].rows, tolerance, divisions))
# A closed NURBS band can fail the single-seed mapped inverse at
# its duplicated seam. Prepare its branch-aware cut chart while
# shared cuts are still mutable, even if mapped quads get first
# refusal. The constrained fallback has no seam chart identity.
var periodic_fallback = false
if s.kind == surface_spline:
for use in 0..<faces[at].uses.length:
for before in 0..<use:
periodic_fallback = periodic_fallback or edge_index(faces[at].uses[use]) == edge_index(faces[at].uses[before])
if periodic_fallback:
periodic_fallback = not (try can_map(vertices, edges, faces[at], s, plans[at].rows, tolerance, divisions))
if not plans[at].cut_first and not periodic_fallback: return
else:
# Without four logical sides the mapped mesher cannot succeed.
# Own the cut chart from the start, including its stopped-end and
# physical-pitch policies, rather than only retrying it at dispatch.
plans[at].cut_first = true
seed_layout(&plans[at], faces[at], s, vertices, edges, job.cuts, divisions, tolerance, job.edge_size) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
plans[at].valid = false
recover ()
func seed_layout(plan: GridLayout*, face: BrepFace, s: Surface, vertices: const Vector3[], edges: const Curve[], cuts: const Stations[], divisions: i64, tolerance: f64, edge_size: f64) -> !:
# A face may have any number of coedges and boundary samples: the chart
# and the cut grid size their scratch by the face.
try plan.u.open(axis_stations)
try plan.v.open(axis_stations)
plan.applied = try new bool[1] --- in memory.heap
plan.applied[0] = false
plan.normals = try new NormalCache[1] --- in memory.heap
plan.normals[0] = NormalCache()
plan.chains = try new UVChain[face.uses.length] --- in memory.heap
for at in 0..<plan.chains.length: plan.chains[at] = UVChain()
try chain_face(plan.chains, face, s, vertices, edges, cuts, tolerance)
var low = Vector3(1e100, 1e100, 0.0)
var high = Vector3(-1e100, -1e100, 0.0)
for use in 0..<face.uses.length:
let index = edge_index(face.uses[use])
let chain = try cached(&plan.chains[use], s, vertices, edges[index], cuts[index], tolerance)
for seed in chain:
low = Vector3(math.min(low.x, seed.x), math.min(low.y, seed.y), 0.0)
high = Vector3(math.max(high.x, seed.x), math.max(high.y, seed.y), 0.0)
try include_conics(s, face, edges, &low, &high)
if high.x - low.x < 1e-9 or high.y - low.y < 1e-9: error(invalid, "singular trim layout")
let trim_low = low
let trim_high = high
plan.trim_low = trim_low
plan.trim_high = trim_high
# The sampled trim polygon bounds are not the curve bounds. Subsequent exact
# edge/grid intersections can lie outside that polygon (e.g. a circle near
# its extremum). Guard cells cover that envelope and are clipped away.
let margin = high.subtract(low).multiply_scalar(0.01)
low = low.subtract(margin)
high = high.add(margin)
if s.kind == surface_spline:
low = Vector3(math.max(0.0, low.x), math.max(0.0, low.y), 0.0)
high = Vector3(math.min(1.0, high.x), math.min(1.0, high.y), 0.0)
plan.epsilon = math.max(high.x - low.x, high.y - low.y) * 1e-7
_ = try plan.u.insert(low.x, plan.epsilon)
_ = try plan.u.insert(high.x, plan.epsilon)
_ = try plan.v.insert(low.y, plan.epsilon)
_ = try plan.v.insert(high.y, plan.epsilon)
# Actual rectangular trim limits remain mandatory. An affine extrusion can
# let a stopped oblique end cut its grid: that end's envelope extrema are
# not additional interior rows. Curved axes retain their existing support.
let rails = (try trim_rails(s, plan.chains, trim_low, trim_high, plan.epsilon, tolerance)) if s.kind == surface_spline and plan.cut_first else [true, true, true, true]
if rails[0]: _ = try plan.u.insert(trim_low.x, plan.epsilon)
if rails[1]: _ = try plan.u.insert(trim_high.x, plan.epsilon)
if rails[2]: _ = try plan.v.insert(trim_low.y, plan.epsilon)
if rails[3]: _ = try plan.v.insert(trim_high.y, plan.epsilon)
# Nearby competing row phases must not create microscopic sliver columns.
# This bounds optional flow propagation, never the shared CAD edge samples.
plan.u.separation = (high.x - low.x) / math.max(32.0, (f64)divisions * 4.0) * 0.9
plan.v.separation = (high.y - low.y) / math.max(32.0, (f64)divisions * 4.0) * 0.9
var dominant_u = plan.chains.length
var dominant_v = plan.chains.length
var count_u: usize = 0
var count_v: usize = 0
var span_u: f64 = 0.0
var span_v: f64 = 0.0
for at in 0..<plan.chains.length:
if not plan.flow[at]: continue
let uv = plan.chains[at].points
let direction = try rail_axis(s, uv, plan.epsilon, tolerance)
let span = uv[uv.length - 1].subtract(uv[0])
if direction == 0 and (math.abs(span.x) > span_u + plan.epsilon or (math.abs(math.abs(span.x) - span_u) <= plan.epsilon and uv.length > count_u)):
dominant_u = at
count_u = uv.length
span_u = math.abs(span.x)
if direction == 1 and (math.abs(span.y) > span_v + plan.epsilon or (math.abs(math.abs(span.y) - span_v) <= plan.epsilon and uv.length > count_v)):
dominant_v = at
count_v = uv.length
span_v = math.abs(span.y)
for at in 0..<plan.chains.length:
if not plan.flow[at]: continue
# A dominant boundary rail can comprise several STEP coedges. Seed its
# entire station family before curvature refinement, not just its
# longest segment. Otherwise the uncovered remainder acquires a second
# independent phase which gets unioned with its real seam stations later.
if (try same_rail(s, plan.chains, at, dominant_u, 0, plan.epsilon, tolerance)) or (try same_rail(s, plan.chains, at, dominant_v, 1, plan.epsilon, tolerance)):
_ = try inherit(plan, s, face, at, tolerance)
var planar_support: usize = 1
if s.kind == surface_plane:
var samples: usize = 0
for use in face.uses: samples += cuts[edge_index(use)].count - 1
if samples > 8: planar_support = (usize)math.min(math.max(32.0, (f64)divisions), math.max((f64)divisions, (f64)samples / 4.0))
if s.kind == surface_plane: plan.independent_phase = try fill_plane(&plan.u, &plan.v, trim_low, trim_high, planar_support, plan.epsilon)
else:
try fill(&plan.u, planar_support, plan.epsilon)
try fill(&plan.v, planar_support, plan.epsilon)
try refine_axis(&plan.u, s, low, high, 0, divisions, tolerance, edge_size, plan.epsilon)
try refine_axis(&plan.v, s, low, high, 1, divisions, tolerance, edge_size, plan.epsilon)
if s.kind != surface_plane:
try snap_lines(&plan.u, plan.chains, 0, 0.3)
try snap_lines(&plan.v, plan.chains, 1, 0.3)
if plan.cut_first: plan.pitch_axes = try refine_pitch(&plan.u, &plan.v, s, plan.epsilon)
try check_grid_size(plan.u.count, plan.v.count)
try refine_cells(&plan.u, &plan.v, s, divisions, tolerance, plan.epsilon)
plan.valid = true
func same_rail(s: Surface, chains: const UVChain[], at: usize, dominant: usize, axis: i64, epsilon: f64, tolerance: f64) -> bool!:
if dominant == chains.length: return false
if at == dominant: return true
let candidate = chains[at].points
if try rail_axis(s, candidate, epsilon, tolerance) != axis: return false
let a = bounds(candidate, false)
let b = bounds(candidate, true)
let c = bounds(chains[dominant].points, false)
let d = bounds(chains[dominant].points, true)
return math.max(a.y, c.y) <= math.min(b.y, d.y) + epsilon if axis == 0 else math.max(a.x, c.x) <= math.min(b.x, d.x) + epsilon
func inherit(plan: GridLayout*, s: Surface, face: BrepFace, use: usize, tolerance: f64) -> bool!:
let chain = plan.chains[use]
let axis = try rail_axis(s, chain.points, plan.epsilon, tolerance)
if axis < 0: return false
let can_stop = plan.cut_first and extrusion_axis(s, axis)
# Curvature-resolved rows also own their physical phase. On a proven
# extrusion, a late curved-rail station must not spoil adjacent cells.
let protect_curve = plan.valid and affine_axis(s, 1 - axis)
let start_row = not can_stop or (try row_endpoint(s, face, plan.chains, plan.flow, use, axis, true, plan.epsilon, tolerance))
let end_row = not can_stop or (try row_endpoint(s, face, plan.chains, plan.flow, use, axis, false, plan.epsilon, tolerance))
let original_u = plan.u.separation
let original_v = plan.v.separation
# Smooth compatibility permits flow, but does not make every trim vertex
# an interior row. Curvature-seeded charts keep their own stations; reject
# late competing phases that would turn a usable cell into a severe sliver.
# The canonical edge cut remains shared and becomes a cut-polygon corner.
plan.u.separation = 0.0
plan.v.separation = 0.0
defer:
plan.u.separation = original_u
plan.v.separation = original_v
var changed = false
for at in 0..<chain.points.length:
if (at == 0 and not start_row) or (at + 1 == chain.points.length and not end_row): continue
let p = chain.points[at]
if protect_curve and not (try accept_extruded_row(*plan, s, axis, p.x if axis == 0 else p.y)): continue
if axis == 0:
if plan.valid and plan.pitch_axes[0] and not accept_pitch_row(plan.u, p.x, plan.epsilon): continue
if plan.independent_phase and plan.valid and not accept_plane_row(plan.u, plan.v, p.x, plan.trim_low.x, plan.trim_high.x, plan.trim_low.y, plan.trim_high.y, plan.epsilon): continue
let added = try plan.u.insert(math.clamp(p.x, plan.u.values[0], plan.u.values[plan.u.count - 1]), plan.epsilon)
changed = changed or added
if axis == 1:
if plan.valid and plan.pitch_axes[1] and not accept_pitch_row(plan.v, p.y, plan.epsilon): continue
if plan.independent_phase and plan.valid and not accept_plane_row(plan.v, plan.u, p.y, plan.trim_low.y, plan.trim_high.y, plan.trim_low.x, plan.trim_high.x, plan.epsilon): continue
let added = try plan.v.insert(math.clamp(p.y, plan.v.values[0], plan.v.values[plan.v.count - 1]), plan.epsilon)
changed = changed or added
try check_grid_size(plan.u.count, plan.v.count)
return changed
## Register exact boundary/grid crossings before either adjacent face is meshed.
pub func reconcile(plan: GridLayout*, face: BrepFace, s: Surface, vertices: const Vector3[], edges: const Curve[], cuts: Stations[], tolerance: f64, propagate: bool, memo: TrimMemo*? = none) -> bool!:
var revision: usize = 0
for use in face.uses: revision += cuts[edge_index(use)].count
if revision == plan.seen: return false
plan.seen = revision
var changed = false
if propagate:
for use in 0..<face.uses.length:
if not plan.flow[use]: continue
let index = edge_index(face.uses[use])
_ = try cached(&plan.chains[use], s, vertices, edges[index], cuts[index], tolerance, memo = memo)
let grew = try inherit(plan, s, face, use, tolerance)
changed = changed or grew
for use in 0..<face.uses.length:
let index = edge_index(face.uses[use])
let edge = edges[index]
var seam = false
for other in 0..<face.uses.length:
seam = seam or (other != use and edge_index(face.uses[other]) == index)
# Freeze this edge's old chain while collecting new intersection roots.
let uv = try cached(&plan.chains[use], s, vertices, edge, cuts[index], tolerance, memo = memo)
let times = try new f64[uv.length] --- in memory.heap
defer free(times) in memory.heap
for at in 0..<times.length: times[at] = cuts[index].values[at]
for axis in 0..<(usize)2:
let lines = plan.u if axis == 0 else plan.v
# Row deduplication tolerance is not geometric incidence.
# A shallow crossing near a tangent is still a crossing;
# skipping it sends an unsplit chord through the grid side
# and can turn an otherwise valid cut cell inside out.
let incidence = math.max(1e-13, plan.epsilon * 1e-5)
let last = lines.count - 1
for segment in 0..<uv.length - 1:
let a = uv[segment].x if axis == 0 else uv[segment].y
let b = uv[segment + 1].x if axis == 0 else uv[segment + 1].y
let low = math.min(a, b) + incidence
let high = math.max(a, b) - incidence
# Sorted lines: those strictly inside (low, high) are one run.
var line = first_above(lines, low, last)
while line < last:
let value = lines.values[line]
line += 1
if value >= high: break
if try grazes(s, edge, uv, times, segment, axis, value, tolerance): continue
let t = intersection(s, edge, times[segment], times[segment + 1], uv[segment], uv[segment + 1], axis, value, tolerance, plan.epsilon, memo, index) catch failure:
if failure.code != invalid: error(failure.code, failure.message)
recover times[segment]
let preserve = try separates_crossings(uv, times, segment, axis, value, incidence, edge, t, tolerance)
# A crossing a hair from a sample moves the sample onto
# the line in this chart instead of becoming a station.
if not preserve and (try absorb_crossing(&plan.chains[use], edge, times, segment, axis, value, t, lines, seam, incidence)): continue
let added = (try cuts[index].insert(t, cuts[index].epsilon)) if preserve else (try insert_cut(&cuts[index], edge, t, tolerance))
changed = changed or added
return changed
## A nearby sample can represent one crossing on a monotone run, but cannot
## replace both crossings around an extremum. This also covers a tolerant CAD
## endpoint that returns behind the last analytic curve sample. Keep the exact
## roots and the intervening vertex; neither topology nor the turn may collapse.
func separates_crossings(uv: const Vector3[], times: const f64[], segment: usize, axis: usize, value: f64, incidence: f64, edge: Curve, t: f64, tolerance: f64) -> bool!:
for at in [segment, segment + 1]:
if at == 0 or at + 1 == uv.length: continue
let a = uv[at - 1].x if axis == 0 else uv[at - 1].y
let p = uv[at].x if axis == 0 else uv[at].y
let b = uv[at + 1].x if axis == 0 else uv[at + 1].y
if math.abs(p - value) <= incidence: continue
if value > math.min(a, b) + incidence and value < math.max(a, b) - incidence: continue
if (try edge.at(t)).subtract(try edge.at(times[at])).length() < math.max(1e-8, tolerance * 0.01): return true
return false
func insert_cut(cuts: Stations*, edge: Curve, t: f64, tolerance: f64) -> bool!:
var low: usize = 0
var high = cuts.count
while low < high:
let mid = (low + high) // 2
if cuts.values[mid] < t: low = mid + 1
else: high = mid
let p = try edge.at(t)
let separation = math.max(1e-8, tolerance * 0.01)
if low < cuts.count and p.subtract(try edge.at(cuts.values[low])).length() < separation: return false
if low > 0 and p.subtract(try edge.at(cuts.values[low - 1])).length() < separation: return false
return try cuts.insert(t, cuts.epsilon)
func close_memos(memos: TrimMemo[]):
for at in 0..<memos.length: memos[at].close()
free(memos) in memory.heap