dymokomi/luce-cad
Source of release 0.9.3
0.9.3 / src / polygons / grid.lucb
## Insert a regular planar lattice without changing the constrained boundary.
## Each lattice point (a cell's center) inside the trim and not next to a
## boundary point splits the triangle holding it (grid_lattice finds both),
## or the two beside the side it lies on.
pub func insert_grid(source: interop.Reference[Mesh], normal: Vector3, spacing: f64, second_spacing: f64 = 0.0, constraints: TrimConstraints = TrimConstraints()) -> interop.Reference[Mesh]!:
if spacing == 0.0:
return source.clone()
if not math.is_finite(spacing) or spacing < 0.0:
error(invalid, "edge size must be finite and nonnegative")
let vertical = second_spacing if second_spacing > 0.0 else spacing
if not math.is_finite(vertical):
error(invalid, "second grid spacing must be finite")
let n = try normal.normalized()
let reference = Vector3(1.0, 0.0, 0.0) if math.abs(n.x) < 0.9 else Vector3(0.0, 1.0, 0.0)
let u = try reference.subtract(n.multiply_scalar(reference.dot(n))).normalized()
let v = n.cross(u)
let input = source.value()
let origin = try input.point(0)
var umin: f64 = 0.0
var umax: f64 = 0.0
var vmin: f64 = 0.0
var vmax: f64 = 0.0
var mesh = try MeshBuilder(precise = true)
defer mesh.close()
try mesh.copy_points(input)
for face in 0..<input.face_count():
try mesh.copy_face(input, face)
for index in 0..<input.point_count():
let p = (try input.point(index)).subtract(origin)
umin = math.min(umin, p.dot(u))
umax = math.max(umax, p.dot(u))
vmin = math.min(vmin, p.dot(v))
vmax = math.max(vmax, p.dot(v))
let nx = math.ceil((umax - umin) / spacing)
let ny = math.ceil((vmax - vmin) / vertical)
if nx * ny > most_cells:
error(invalid, "edge size produces more than 131072 grid cells on a face; increase it")
let epsilon = math.max(0.000000000001, spacing * vertical * 0.000000001)
var neighbors = try Neighbors.of(&mesh)
defer neighbors.close()
var cells = try lattice(&mesh, &neighbors, origin, u, v, umin, vmin, spacing, vertical, (usize)nx, (usize)ny, constraints)
defer cells.close()
var last: i64 = 0
for iy in 0..<(usize)ny:
try cells.start_row(iy)
for ix in 0..<(usize)nx:
# A point outside the trim, or next to a boundary sample (a
# near-duplicate), is left out.
if not cells.inside(ix): continue
let p = origin.add(u.multiply_scalar(umin + ((f64)ix + 0.5) * spacing)).add(v.multiply_scalar(vmin + ((f64)iy + 0.5) * vertical))
if cells.near(&mesh, ix, iy, p) or cells.beside_side(ix, iy, p): continue
var face = walk(&mesh, &neighbors, last, p, n, epsilon)
if face < 0: face = scan_triangles(&mesh, p, n, epsilon)
if face < 0: continue
last = face
let f = (usize)face
let a = mesh.corners[f * 3]
let b = mesh.corners[f * 3 + 1]
let c = mesh.corners[f * 3 + 2]
let pa = mesh.points[(usize)a]
let pb = mesh.points[(usize)b]
let pc = mesh.points[(usize)c]
# A point much nearer a boundary side than a lattice step, and
# inside its 120-degree lens, would make a flat triangle against
# it, which no flip can mend.
if lens_of_boundary(&mesh, &neighbors, f, p, math.min(spacing, vertical) * 0.25, constraints): continue
let ab = pb.subtract(pa).cross(p.subtract(pa)).dot(n)
let bc = pc.subtract(pb).cross(p.subtract(pb)).dot(n)
let ca = pa.subtract(pc).cross(p.subtract(pc)).dot(n)
if ab <= epsilon or bc <= epsilon or ca <= epsilon:
# On a side: split it and the triangle beside it, unless
# it is the boundary's (insertion never splits a boundary
# side, which a neighboring face shares) or a kept seam.
let x = a if ab <= epsilon else (b if bc <= epsilon else c)
let y = b if ab <= epsilon else (c if bc <= epsilon else a)
if constraints.contains(x,y): continue
let opposite = c if ab <= epsilon else (a if bc <= epsilon else b)
let neighbor = neighbors.across.items[f * 3 + neighbors.slot(&mesh, f, x, y)]
if neighbor < 0: continue
let other_slot = neighbors.slot(&mesh, (usize)neighbor, y, x)
if other_slot == 3: continue
let other = mesh.corners[(usize)neighbor * 3 + (other_slot + 2) % 3]
let px = mesh.points[(usize)x]
let py = mesh.points[(usize)y]
let po = mesh.points[(usize)opposite]
let pq = mesh.points[(usize)other]
# An almost-on-edge point must not create zero-area slivers
# on either side, especially in anisotropic UV lattices.
if p.subtract(px).cross(po.subtract(px)).dot(n) <= epsilon or py.subtract(p).cross(po.subtract(p)).dot(n) <= epsilon or p.subtract(py).cross(pq.subtract(py)).dot(n) <= epsilon or px.subtract(p).cross(pq.subtract(p)).dot(n) <= epsilon:
continue
let y_side = neighbors.across.items[f * 3 + neighbors.slot(&mesh, f, y, opposite)]
let o_side = neighbors.across.items[f * 3 + neighbors.slot(&mesh, f, opposite, x)]
let x_side = neighbors.across.items[(usize)neighbor * 3 + neighbors.slot(&mesh, (usize)neighbor, x, other)]
let q_side = neighbors.across.items[(usize)neighbor * 3 + neighbors.slot(&mesh, (usize)neighbor, other, y)]
let id = try mesh.point(p)
replace(&mesh, f, x, id, opposite)
let g = (i64)mesh.nf
try append(&mesh, id, y, opposite)
replace(&mesh, (usize)neighbor, y, id, other)
let h = (i64)mesh.nf
try append(&mesh, id, x, other)
try neighbors.grow()
try neighbors.grow()
neighbors.set(f, [h, g, o_side])
neighbors.set((usize)g, [neighbor, y_side, face])
neighbors.set((usize)neighbor, [g, h, q_side])
neighbors.set((usize)h, [face, x_side, neighbor])
neighbors.relink(&mesh, y_side, opposite, y, g)
neighbors.relink(&mesh, x_side, other, x, h)
else:
let first_side = neighbors.across.items[f * 3]
let second_side = neighbors.across.items[f * 3 + 1]
let third_side = neighbors.across.items[f * 3 + 2]
let id = try mesh.point(p)
replace(&mesh, f, a, b, id)
let g = (i64)mesh.nf
try append(&mesh, b, c, id)
let h = (i64)mesh.nf
try append(&mesh, c, a, id)
try neighbors.grow()
try neighbors.grow()
neighbors.set(f, [first_side, g, h])
neighbors.set((usize)g, [second_side, h, face])
neighbors.set((usize)h, [third_side, face, g])
neighbors.relink(&mesh, second_side, c, b, g)
neighbors.relink(&mesh, third_side, a, c, h)
return try mesh.finish()
## The most lattice cells on a face: twice a 64-division face's (its
## spacing leaves at most 4 x 64 cells a side).
let most_cells: f64 = 131072.0
## Whether `p` lies within `reach` of a side of triangle `face` that is on
## the boundary or a kept seam, and inside its 120-degree lens (the points
## that see it at more than 120 degrees).
func lens_of_boundary(mesh: const MeshBuilder*, neighbors: const Neighbors*, face: usize, p: Vector3, reach: f64, constraints: TrimConstraints) -> bool:
for k in 0..<(usize)3:
let a = mesh.corners[face * 3 + k]
let b = mesh.corners[face * 3 + (k + 1) % 3]
if neighbors.across.items[face * 3 + k] >= 0 and not constraints.contains(a, b): continue
let pa = mesh.points[(usize)a].subtract(p)
let pb = mesh.points[(usize)b].subtract(p)
if pa.cross(pb).length() > reach * pb.subtract(pa).length(): continue
if pa.dot(pb) < -0.5 * pa.length() * pb.length(): return true
return false
func replace(mesh: MeshBuilder*, face: usize, a: i64, b: i64, c: i64):
mesh.corners[face * 3] = a
mesh.corners[face * 3 + 1] = b
mesh.corners[face * 3 + 2] = c
func append(mesh: MeshBuilder*, a: i64, b: i64, c: i64) -> !:
try mesh.face(3)
try mesh.corner(a)
try mesh.corner(b)
try mesh.corner(c)