dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / modeling / classify.lucb
## The booleans' classification (step 5): a point well inside each piece,
## and whether it lies inside the other solid, on its coincident face, or
## outside.
## A point well inside piece `p` of face `f`: across the middle of its
## chart, the middle of the widest stretch inside it, on the surface.
func piece_point(work: Work*, traced: const Shape*, f: usize, pieces: const Pieces*, p: usize) -> Vector3!:
let face = work.w.faces.items[f]
var chart = Growing[Vector3]()
defer chart.close()
var starts = Growing[usize]()
defer starts.close()
for c in pieces.piece_cycles(p):
try starts.push(chart.count)
try loop_chart(traced, face.surface, try face_pole(&work.w, f), pieces.cycle(c), &chart)
try starts.push(chart.count)
var low = Vector3(1.0e300, 1.0e300, 0.0)
var high = Vector3(-1.0e300, -1.0e300, 0.0)
for q in chart.view():
low = Vector3(math.min(low.x, q.x), math.min(low.y, q.y), 0.0)
high = Vector3(math.max(high.x, q.x), math.max(high.y, q.y), 0.0)
# Angles count by the radius, so clearances compare like lengths.
let s = &work.w.surfaces.items[(usize)face.surface]
let wraps = periodic(s)
let scale = 1.0 if s.kind == surface_plane or s.kind == surface_spline else math.max(s.radius, 1e-300)
# The chart with angles scaled, for clearances.
var scaled = Growing[Vector3]()
defer scaled.close()
for q in chart.view(): try scaled.push(Vector3(q.x * scale, q.y, 0.0))
var best_u = 0.0
var best_v = 0.0
var best = -1.0
# First a few candidates: a point a quarter of the piece's narrower
# extent from every boundary segment is well inside already (a disk
# cut from a face by a hole is found at once).
let enough = 0.25 * math.min((high.x - low.x) * scale, high.y - low.y)
for row in 0..<3:
for column in 0..<5:
let u = low.x + (high.x - low.x) * ((f64)column + 0.5 + 0.0098765432) / 5.0
let v = low.y + (high.y - low.y) * ((f64)row + 0.5 + 0.0123456789) / 3.0
if chart_winding(chart.view(), starts.view(), u, v, wraps, s.kind == surface_torus) == 0: continue
let clearance = nearest_segment(scaled.view(), starts.view(), u * scale, v, best)
if clearance > best:
best = clearance
best_u = u
best_v = v
if enough > 0.0 and best >= enough: return try surface_point(work.w.surfaces.items[(usize)face.surface], Vector3(best_u, best_v, 0.0))
best = -1.0
# A coarse grid of candidates off the vertices (an irrational step); of
# those inside, the one farthest from every boundary segment; then
# finer grids about the best so far.
var cell_u = (high.x - low.x) / 24.0
var cell_v = (high.y - low.y) / 12.0
var from_u = low.x + cell_u * (0.5 + 0.0098765432)
var from_v = low.y + cell_v * (0.5 + 0.0123456789)
var columns = 24
var rows = 12
for round in 0..<4:
for row in 0..<rows:
let v = from_v + cell_v * (f64)row
for column in 0..<columns:
let u = from_u + cell_u * (f64)column
if chart_winding(chart.view(), starts.view(), u, v, wraps, s.kind == surface_torus) == 0: continue
let clearance = nearest_segment(scaled.view(), starts.view(), u * scale, v, best)
if clearance > best:
best = clearance
best_u = u
best_v = v
if best < 0.0 and round == 0:
# A piece thinner than the grid's cells (a thin wall's ring
# round a hole): beside the middle of each boundary segment,
# stepping in, on whichever side is inside.
let (u, v, clearance) = beside_boundary(chart.view(), scaled.view(), starts.view(), scale, wraps, s.kind == surface_torus)
if clearance > 0.0:
best = clearance
best_u = u
best_v = v
cell_u = clearance / math.max(scale, 1e-300) * 3.5
cell_v = clearance * 3.5
if best < 0.0: break
# Next: a 7 x 7 grid over the cells about the best.
cell_u = cell_u * 2.0 / 7.0
cell_v = cell_v * 2.0 / 7.0
from_u = best_u - cell_u * 3.0
from_v = best_v - cell_v * 3.0
columns = 7
rows = 7
_ = round
if best < 0.0: error(invalid, "a face piece has no inside to classify")
return try surface_point(work.w.surfaces.items[(usize)face.surface], Vector3(best_u, best_v, 0.0))
## A point inside the loops of `chart` (from `starts`; `scaled`, the same
## with u times `scale`) beside the middle of a boundary segment, stepped
## in from it by a fraction of the segment, the one farthest from every
## segment: its u, v and that clearance (-1: none found).
func beside_boundary(chart: const Vector3[], scaled: const Vector3[], starts: const usize[], scale: f64, wraps: bool, torus: bool) -> (f64, f64, f64):
var best = -1.0
var best_u = 0.0
var best_v = 0.0
for loop in 0..<starts.length - 1:
let first = starts[loop]
let last = starts[loop + 1]
for k in first..<last:
let a = scaled[k]
let b = scaled[first if k + 1 == last else k + 1]
let dx = b.x - a.x
let dy = b.y - a.y
let length = math.sqrt(dx * dx + dy * dy)
if length <= 0.0: continue
for fraction in [0.25, 0.05, 0.01, 0.001]:
for side in [-1.0, 1.0]:
let step = length * fraction * side
let u = ((a.x + b.x) * 0.5 - dy / length * step) / scale
let v = (a.y + b.y) * 0.5 + dx / length * step
if chart_winding(chart, starts, u, v, wraps, torus) == 0: continue
let clearance = nearest_segment(scaled, starts, u * scale, v, best)
if clearance > best:
best = clearance
best_u = u
best_v = v
return (best_u, best_v, best)
## The distance from (`u`, `v`) to the nearest segment of the loops of
## `points` (from `starts`), or a smaller one as soon as it is below
## `enough` (the candidate cannot win).
func nearest_segment(points: const Vector3[], starts: const usize[], u: f64, v: f64, enough: f64) -> f64:
var nearest = 1.0e300
let floor = enough * enough if enough > 0.0 else -1.0
for loop in 0..<starts.length - 1:
let first = starts[loop]
let last = starts[loop + 1]
for k in first..<last:
let a = points[k]
let b = points[first if k + 1 == last else k + 1]
let dx = b.x - a.x
let dy = b.y - a.y
let length = dx * dx + dy * dy
var t = 0.0
if length > 0.0: t = math.clamp(((u - a.x) * dx + (v - a.y) * dy) / length, 0.0, 1.0)
let ex = a.x + dx * t - u
let ey = a.y + dy * t - v
let d = ex * ex + ey * ey
if d < nearest:
nearest = d
if nearest <= floor: return math.sqrt(nearest)
return math.sqrt(nearest)
## What pieces are classified against: both solids' faces (their charts,
## for exact rays, and boxes), B-spline surfaces' Bezier patches, and
## each block's class once a ray found it.
struct Others:
var charts: Charts
var nets: Nets
## Where a ray's hit lies against an analytic face (face_lookup.lucb).
var lookup: Lookup
var lows: Growing[Vector3]
var highs: Growing[Vector3]
## Each solid's box: [0] the first's, [1] the second's.
var solid_low: Vector3[2]
var solid_high: Vector3[2]
## Each piece's block, and each block's class (-1 not yet known).
var block: Growing[usize]
var block_class: Growing[i64]
func close():
self.charts.close()
self.nets.close()
self.lookup.close()
self.lows.close()
self.highs.close()
self.block.close()
self.block_class.close()
func new_others(work: const Work*) -> Others!:
let w = &work.w
var made = Others(try new_charts(w.faces.count), try new_nets(w.surfaces.count), try new_lookup(w), Growing[Vector3](), Growing[Vector3](),
[Vector3(1.0e300, 1.0e300, 1.0e300), Vector3(1.0e300, 1.0e300, 1.0e300)],
[Vector3(-1.0e300, -1.0e300, -1.0e300), Vector3(-1.0e300, -1.0e300, -1.0e300)], Growing[usize](), Growing[i64]())
errdefer made.close()
for f in 0..<w.faces.count:
let (l, h) = try face_box(w, f)
try made.lows.push(l)
try made.highs.push(h)
let k: usize = 0 if work.is_a(f) else 1
let sl = made.solid_low[k]
let sh = made.solid_high[k]
made.solid_low[k] = Vector3(math.min(sl.x, l.x), math.min(sl.y, l.y), math.min(sl.z, l.z))
made.solid_high[k] = Vector3(math.max(sh.x, h.x), math.max(sh.y, h.y), math.max(sh.z, h.z))
return made
## Pieces in blocks: pieces of one solid sharing an edge that keeps clear of
## the other solid's surfaces are on the same side of it, so one ray serves
## the block (OpenCASCADE's connexity blocks).
func find_blocks(work: const Work*, traced: const Shape*, pieces: const Pieces*, piece_face: const usize[], others: Others*) -> !:
let count = pieces.piece_count()
others.block.clear()
others.block_class.clear()
for p in 0..<count:
try others.block.push(p)
try others.block_class.push(-1)
# The first piece found using each final edge, per solid.
let edges = traced.edges.count
var seen = Growing[i64]()
defer seen.close()
for _ in 0..<edges * 2: try seen.push(-1)
var clear = Growing[i64]()
defer clear.close()
for _ in 0..<edges: try clear.push(-1)
for p in 0..<count:
let solid: usize = 0 if work.is_a(piece_face[p]) else 1
for c in pieces.piece_cycles(p):
for use in pieces.cycle(c):
let e = edge_index(use)
if clear.items[e] < 0: clear.items[e] = 1 if try keeps_clear(work, traced, e, solid) else 0
if clear.items[e] == 0: continue
let other = seen.items[e * 2 + solid]
if other < 0:
seen.items[e * 2 + solid] = (i64)p
continue
let ra = union_root(others.block.items, p)
let rb = union_root(others.block.items, (usize)other)
if ra < rb: others.block.items[rb] = ra
elif rb < ra: others.block.items[ra] = rb
## Whether final edge `e`'s middle is well clear of every surface of the
## solid other than `solid` (B-spline surfaces: never assumed).
func keeps_clear(work: const Work*, traced: const Shape*, e: usize, solid: usize) -> bool!:
let edge = traced.edges.items[e]
let middle = try traced.at(edge.carrier, (edge.t0 + edge.t1) * 0.5)
let w = &work.w
let first = work.faces_a if solid == 0 else 0
let last = w.faces.count if solid == 0 else work.faces_a
for f in first..<last:
let s = &w.surfaces.items[(usize)w.faces.items[f].surface]
if s.kind == surface_spline: return false
if surface_distance(s, middle) <= work.tol * 1000.0: return false
return true
## Piece `p` of face `f` against the other solid.
func classify(work: Work*, traced: const Shape*, f: usize, pieces: const Pieces*, p: usize, others: Others*) -> i64!:
# A face whose box misses the other solid's lies outside it.
let other: usize = 1 if work.is_a(f) else 0
let pad = work.tol * 10.0
let l = others.lows.items[f]
let h = others.highs.items[f]
let ol = others.solid_low[other]
let oh = others.solid_high[other]
# Its block's, once known, unless its face lies on one of the other's
# (then the piece itself decides). A point inside a piece of a face
# with many holes is the costliest step here: found only when needed.
let block = union_root(others.block.items, p)
if l.x > oh.x + pad or l.y > oh.y + pad or l.z > oh.z + pad or ol.x > h.x + pad or ol.y > h.y + pad or ol.z > h.z + pad:
# So is its block (pieces of a block lie on one side).
others.block_class.items[block] = class_out
return class_out
var paired = false
for pair in work.coincident.view(): paired = paired or pair.fa == f or pair.fb == f
if not paired and others.block_class.items[block] >= 0: return others.block_class.items[block]
let point = try piece_point(work, traced, f, pieces, p)
for pair in work.coincident.view():
let partner = pair.fb if pair.fa == f else (pair.fa if pair.fb == f else f)
if partner == f: continue
if try face_contains(&work.w, partner, point, work.tol) != outside:
return class_same if pair.same else class_opposite
if others.block_class.items[block] >= 0: return others.block_class.items[block]
let class = try ray_class(work, f, point, others)
others.block_class.items[block] = class
return class
## Inside or outside the other solid at `point` (on face `f`), by rays.
func ray_class(work: Work*, f: usize, point: Vector3, others: Others*) -> i64!:
# The other solid's faces.
let first = work.faces_a if work.is_a(f) else 0
let last = work.w.faces.count if work.is_a(f) else work.faces_a
return class_in if try inside_faces(&work.w, &others.charts, &others.nets, first, last, point, work.size, &others.lookup) else class_out