Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.3

0.7.3 / src / verbs / subdivide.lucb

## Subdivide: every face of n corners becomes n quads through its edge
## midpoints and its center; Catmull-Clark then moves the points (Linear
## keeps the shape). Edge and face points mix their parents' attributes, and
## each new corner mixes the corners it lies between, so UVs interpolate
## within faces. Edges used by more than two faces act as creases.

let subdivide_parms: ParmSpec[2] = [
    ParmSpec("Levels", ParmKind.integer, 1.0, 1.0, 4.0, 1, "", "Each level splits every face into quads."),
    ParmSpec("Method", ParmKind.menu, 1.0, 0.0, 1.0, 1, "Linear|Catmull-Clark", "Catmull-Clark smooths as it splits; Linear keeps the shape.")]

func subdivide_verb() -> Verb:
    return Verb("Subdivide", "Modeling", "Split faces into quads, optionally with Catmull-Clark smoothing", Domain.face, true, subdivide_parms, true, cook_subdivide)

func cook_subdivide(input: const VerbInput*, output: VerbOutput*) -> !:
    let levels = (usize)math.max(1.0, math.min(4.0, input.parms.at(0)))
    let smooth = input.parms.at(1) != 0.0
    if input.group.population() != input.group.count:
        output.warning = "Subdivide works on the whole mesh; the group is ignored"
    var current = try mesh_share(input.mesh)
    for _ in 0..<levels:
        var level = TopologyBuilder()
        defer level.close()
        subdivide_level(current, smooth, &level) catch failure:
            mesh_dispose(current)
            error(failure.code, failure.message)
        let next = level.finish(current) catch failure:
            mesh_dispose(current)
            error(failure.code, failure.message)
        mesh_dispose(current)
        current = next
    output.mesh = current
    output.selection = try BitsBuilder.ones((usize)current.face_count())
    output.selection_domain = Domain.face

func subdivide_level(mesh: const Mesh*, smooth: bool, builder: TopologyBuilder*) -> !:
    let topology = try Topology.of(mesh)
    let offsets = topology.offsets
    let corners = topology.corners
    let points = topology.points
    let edges = topology.edges()
    let faces = topology.faces()
    if points + edges + faces > max_points: error(errors.limit, "subdivision would exceed 8M points")
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    # Face points: centroids.
    let centers = try new Vector3[faces] --- in memory.heap
    defer free(centers) in memory.heap
    for face in 0..<faces:
        var sum = Vector3()
        let start = (usize)offsets[face]
        let size = (usize)offsets[face + 1] - start
        for at in 0..<size: sum = sum.add(builder.position(corners[start + at]))
        centers[face] = sum.multiply_scalar(1.0 / (f64)size)
    # Edge points: midpoints, or with Catmull-Clark the average of the ends
    # and the two face points of an interior edge.
    var parents: i32[256]
    var weights: f32[256]
    for edge in 0..<edges:
        let a = topology.edge_points[edge * 2]
        let b = topology.edge_points[edge * 2 + 1]
        var position = builder.position(a).add(builder.position(b)).multiply_scalar(0.5)
        let first = (usize)topology.edge_corner_offsets[edge]
        let end = (usize)topology.edge_corner_offsets[edge + 1]
        if smooth and end - first == 2:
            let f1 = centers[(usize)topology.corner_faces[(usize)topology.edge_corners[first]]]
            let f2 = centers[(usize)topology.corner_faces[(usize)topology.edge_corners[first + 1]]]
            position = builder.position(a).add(builder.position(b)).add(f1).add(f2).multiply_scalar(0.25)
        parents[0] = a
        parents[1] = b
        weights[0] = 0.5
        weights[1] = 0.5
        _ = try builder.mixed_point(position, parents[..<2], weights[..<2])
    for face in 0..<faces:
        let start = (usize)offsets[face]
        let size = (usize)offsets[face + 1] - start
        # Small faces mix on the stack, larger ones in heap scratch.
        let face_parents = try face_scratch.take[i32](parents, size, size)
        defer face_scratch.release[i32](parents, face_parents)
        let face_weights = try face_scratch.take[f32](weights, size, size)
        defer face_scratch.release[f32](weights, face_weights)
        for at in 0..<size:
            face_parents[at] = corners[start + at]
            face_weights[at] = (f32)(1.0 / (f64)size)
        _ = try builder.mixed_point(centers[face], face_parents, face_weights)
    if smooth: try catmull_clark_points(&topology, builder, centers)
    # n quads per face.
    let edge_base = (i32)points
    let face_base = (i32)(points + edges)
    var mixed_parents: i32[256]
    var mixed_weights: f32[256]
    for face in 0..<faces:
        let start = (usize)offsets[face]
        let size = (usize)offsets[face + 1] - start
        let center_parents = try face_scratch.take[i32](mixed_parents, size, size)
        defer face_scratch.release[i32](mixed_parents, center_parents)
        let center_weights = try face_scratch.take[f32](mixed_weights, size, size)
        defer face_scratch.release[f32](mixed_weights, center_weights)
        for at in 0..<size:
            center_parents[at] = (i32)(start + at)
            center_weights[at] = (f32)(1.0 / (f64)size)
        # Every quad's center corner shares one mix of the face's corners.
        let center = try builder.shared_mix(center_parents, center_weights)
        for at in 0..<size:
            let corner = start + at
            let next = start + (at + 1) % size
            let previous = start + (at + size - 1) % size
            try builder.face((i32)face)
            try builder.corner(corners[corner], (i32)corner)
            let pair: i32[2] = [(i32)corner, (i32)next]
            let half: f32[2] = [0.5, 0.5]
            try builder.mixed_corner(edge_base + topology.corner_edges[corner], pair, half)
            try builder.shared_corner(face_base + (i32)face, center)
            let back: i32[2] = [(i32)previous, (i32)corner]
            try builder.mixed_corner(edge_base + topology.corner_edges[previous], back, half)
            try builder.end_face()

## Catmull-Clark positions of the original points: interior (F + 2R + (n-3)P)/n
## over n faces, boundary 3/4 P + 1/8 each boundary neighbor; points on
## creases or other irregular boundaries stay.
func catmull_clark_points(topology: const Topology*, builder: TopologyBuilder*, centers: const Vector3[]) -> !:
    let point_faces = try new Vector3[topology.points] --- in memory.heap
    defer free(point_faces) in memory.heap
    let face_counts = try new u32[topology.points] --- in memory.heap
    defer free(face_counts) in memory.heap
    for at in 0..<topology.points:
        point_faces[at] = Vector3()
        face_counts[at] = 0
    for corner in 0..<topology.corners.length:
        let point = (usize)topology.corners[corner]
        point_faces[point] = point_faces[point].add(centers[(usize)topology.corner_faces[corner]])
        face_counts[point] += 1
    let moved = try new Vector3[topology.points] --- in memory.heap
    defer free(moved) in memory.heap
    for point in 0..<topology.points:
        let p = builder.position((i32)point)
        moved[point] = p
        let first = (usize)topology.point_edge_offsets[point]
        let end = (usize)topology.point_edge_offsets[point + 1]
        var mids = Vector3()
        var boundary = Vector3()
        var boundary_count = 0
        var irregular = false
        for slot in first..<end:
            let edge = (usize)topology.point_edges[slot]
            let a = topology.edge_points[edge * 2]
            let other = topology.edge_points[edge * 2 + 1] if (usize)a == point else a
            let q = builder.position(other)
            mids = mids.add(p.add(q).multiply_scalar(0.5))
            let uses = topology.edge_corner_offsets[edge + 1] - topology.edge_corner_offsets[edge]
            if uses == 1:
                boundary = boundary.add(q)
                boundary_count += 1
            elif uses > 2:
                irregular = true
        let n = (f64)(end - first)
        if irregular or n == 0.0: continue
        if boundary_count == 2:
            moved[point] = p.multiply_scalar(0.75).add(boundary.multiply_scalar(0.125))
        elif boundary_count == 0 and face_counts[point] > 0:
            let faces = point_faces[point].multiply_scalar(1.0 / (f64)face_counts[point])
            let edges = mids.multiply_scalar(1.0 / n)
            moved[point] = faces.add(edges.multiply_scalar(2.0)).add(p.multiply_scalar(n - 3.0)).multiply_scalar(1.0 / n)
    for point in 0..<topology.points: builder.move_point((i32)point, moved[point])