Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.4

0.9.4 / 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)