Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.9

0.7.9 / src / verbs / subdivide.lucb

## Subdivide: the group's faces each become n quads through their edge
## midpoints and their center; Catmull-Clark then moves the points (Linear
## keeps the shape). Like Blender's Subdivide it works on the selection
## alone: the group's faces (or with an edge group, its edges, and the faces
## all of whose edges it holds) split whole, and every other face keeps the
## mesh joined as Blender's do with their default Straight Cut: a face with
## one split edge takes its midpoint as a corner, two split edges are
## joined by a cut across it, and a quad with three is cut as Blender's
## quad_3edge pattern (three triangles and a quad). Later levels split the
## made faces again, the others only taking the midpoints. Catmull-Clark
## moves only the points every face of which splits whole, and an edge's
## point only between two such faces, so the faces around keep their shape.
## Linear's Smoothness rounds the new points out as Blender's Subdivide
## Smoothness does, onto the sphere the corners' normals describe: a new
## point at the mean of points p_i with normals n_i rises along the
## normals' mean by R (1 - |mean n_i|), R the radius the edges give (an
## edge's length over 2 sin of half the angle between its ends' normals),
## so an edge's point rises by its arc's sagitta; the old points stay.
## 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. The faces made from
## whole split faces are the output selection.

let subdivide_parms: ParmSpec[3] = [
    ParmSpec("Levels", ParmKind.integer, 1.0, 1.0, 4.0, 1, "", "Each level splits the faces into quads again."),
    ParmSpec("Method", ParmKind.menu, 1.0, 0.0, 1.0, 1, "Linear|Catmull-Clark", "Catmull-Clark smooths as it splits; Linear keeps the shape."),
    ParmSpec("Smoothness", ParmKind.number, 0.0, 0.0, 1.0, 1, "", "Linear: round the new points out along the surface's curve (1: onto the circle the normals describe).")]

## Edges split as they are (and faces of split edges whole).
let subdivide_also: Domain[1] = [Domain.edge]

let subdivide_picks: PickSpec[1] = [PickSpec("Faces or edges", "objects faces edges")]

func subdivide_verb() -> Verb:
    return Verb("Subdivide", "Modeling", "Split the group's faces into quads (or its edges), optionally with Catmull-Clark smoothing; the faces around stay joined", Domain.face, true, subdivide_parms, true, cook_subdivide, false, subdivide_also, section = "Modify", family = "Subdivide", icon = "subdivide", picks = subdivide_picks, whole = true)

## What one level splits: faces split whole, edges given a midpoint.
struct SplitRegion:
    var whole: BitsBuilder
    var split: BitsBuilder

    func init():
        self.whole = BitsBuilder(Column[u64](), 0)
        self.split = BitsBuilder(Column[u64](), 0)

    func close():
        self.whole.close()
        self.split.close()

    ## Faces all of whose edges split also split whole (Blender's grid
    ## fill of a face whose every edge is cut).
    func close_faces(topology: const Topology*) -> !:
        for face in 0..<topology.faces():
            if self.whole.view().get(face): continue
            var all = true
            for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
                if not self.split.view().get((usize)topology.corner_edges[corner]):
                    all = false
                    break
            if all: self.whole.set(face)

## What a level made that the next level reads: per output face whether it
## came from a face split whole, and per new edge point the ends of its
## edge (old points keep their numbers).
struct LevelMarks:
    var whole: Growing[u8]
    var ends: Growing[i32]
    var first_edge_point: usize

    func init():
        self.whole = Growing[u8]()
        self.ends = Growing[i32]()
        self.first_edge_point = 0

    func close():
        self.whole.close()
        self.ends.close()

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
    let smoothness = 0.0 if smooth else math.max(0.0, math.min(1.0, input.parms.at(2)))
    var region = SplitRegion()
    defer region.close()
    try first_region(input, &region)
    if region.split.view().population() == 0:
        output.warning = "No faces or edges in the group to subdivide; the input passes through"
        return
    var current = try mesh_share(input.mesh)
    var marks = LevelMarks()
    defer marks.close()
    for level in 0..<levels:
        if level > 0:
            next_region(current, &marks, &region) catch failure:
                mesh_dispose(current)
                error(failure.code, failure.message)
        var built = TopologyBuilder()
        defer built.close()
        marks.whole.clear()
        marks.ends.clear()
        subdivide_level(current, &region, level == 0, smooth, smoothness, &built, &marks) catch failure:
            mesh_dispose(current)
            error(failure.code, failure.message)
        let next = built.finish(current) catch failure:
            mesh_dispose(current)
            error(failure.code, failure.message)
        mesh_dispose(current)
        current = next
    output.mesh = current
    output.selection = try BitsBuilder.zeros((usize)current.face_count())
    for face in 0..<marks.whole.count:
        if marks.whole.items[face] != 0: output.selection.set(face)
    output.selection_domain = Domain.face

## The first level's region: the group's faces and their edges, or the
## group's edges and the faces they close.
func first_region(input: const VerbInput*, region: SplitRegion*) -> !:
    let topology = try Topology.of(input.mesh)
    region.whole = try BitsBuilder.zeros(topology.faces())
    region.split = try BitsBuilder.zeros(topology.edges())
    if input.domain == Domain.edge:
        region.split.unite(input.group)
    else:
        region.whole.unite(input.group)
        for face in 0..<topology.faces():
            if not input.group.get(face): continue
            for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]: region.split.set((usize)topology.corner_edges[corner])
    try region.close_faces(&topology)

## A later level's region on `mesh` (the last level's output): the faces
## made from whole faces, their edges, and the halves of split edges.
func next_region(mesh: const Mesh*, marks: const LevelMarks*, region: SplitRegion*) -> !:
    let topology = try Topology.of(mesh)
    region.close()
    region.whole = try BitsBuilder.zeros(topology.faces())
    region.split = try BitsBuilder.zeros(topology.edges())
    for face in 0..<topology.faces():
        if marks.whole.items[face] == 0: continue
        region.whole.set(face)
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]: region.split.set((usize)topology.corner_edges[corner])
    let first = marks.first_edge_point
    let made = marks.ends.count // 2
    for edge in 0..<topology.edges():
        let a = (usize)topology.edge_points[edge * 2]
        let b = (usize)topology.edge_points[edge * 2 + 1]
        if split_half(marks, first, made, a, b) or split_half(marks, first, made, b, a): region.split.set(edge)
    try region.close_faces(&topology)

## Whether `middle` is an edge point of the last level and `end` one of its
## edge's ends.
func split_half(marks: const LevelMarks*, first: usize, made: usize, middle: usize, end: usize) -> bool:
    if middle < first or middle >= first + made: return false
    let at = (middle - first) * 2
    return (usize)marks.ends.items[at] == end or (usize)marks.ends.items[at + 1] == end

func subdivide_level(mesh: const Mesh*, region: const SplitRegion*, patterns: bool, smooth: bool, smoothness: f64, builder: TopologyBuilder*, marks: LevelMarks*) -> !:
    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()
    let whole = region.whole.view()
    let split = region.split.view()
    if points + split.population() + whole.population() > max_points: error(errors.limit, "subdivision would exceed 8M points")
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    # Face points: centroids (of every face; whole faces take theirs).
    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 of the split edges: midpoints, or with Catmull-Clark the
    # average of the ends and the two face points of an edge between two
    # whole faces; with Smoothness risen off the middle (their rises kept
    # for the face points).
    var parents: i32[256]
    var weights: f32[256]
    let rises = try new Vector3[edges] --- in memory.heap
    defer free(rises) in memory.heap
    let radii = try new f64[edges] --- in memory.heap
    defer free(radii) in memory.heap
    let point_normals = try new Vector3[points] --- in memory.heap
    defer free(point_normals) in memory.heap
    let edge_ids = try new i32[edges] --- in memory.heap
    defer free(edge_ids) in memory.heap
    for edge in 0..<edges:
        rises[edge] = Vector3()
        radii[edge] = 0.0
        edge_ids[edge] = -1
    if smoothness > 0.0:
        try corner_normals(mesh, &topology, point_normals[..<points])
        edge_rises(mesh, &topology, smoothness, point_normals[..<points], rises[..<edges], radii[..<edges])
    marks.first_edge_point = builder.point_count()
    try marks.ends.reserve(split.population() * 2)
    try marks.whole.reserve(topology.corners.length + faces * 4)
    for edge in 0..<edges:
        if not split.get(edge): continue
        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 = (usize)topology.corner_faces[(usize)topology.edge_corners[first]]
            let f2 = (usize)topology.corner_faces[(usize)topology.edge_corners[first + 1]]
            if whole.get(f1) and whole.get(f2):
                position = builder.position(a).add(builder.position(b)).add(centers[f1]).add(centers[f2]).multiply_scalar(0.25)
        position = position.add(rises[edge])
        parents[0] = a
        parents[1] = b
        weights[0] = 0.5
        weights[1] = 0.5
        edge_ids[edge] = try builder.mixed_point(position, parents[..<2], weights[..<2])
        try marks.ends.push(a)
        try marks.ends.push(b)
    let face_ids = try new i32[faces] --- in memory.heap
    defer free(face_ids) in memory.heap
    for face in 0..<faces:
        face_ids[face] = -1
        if not whole.get(face): continue
        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)
        var normal_sum = Vector3()
        var radius = 0.0
        var curved: usize = 0
        for at in 0..<size:
            face_parents[at] = corners[start + at]
            face_weights[at] = (f32)(1.0 / (f64)size)
            normal_sum = normal_sum.add(point_normals[(usize)corners[start + at]])
            let edge_radius = radii[(usize)topology.corner_edges[start + at]]
            if edge_radius > 0.0:
                radius += edge_radius
                curved += 1
        var center = centers[face]
        let mean = normal_sum.length() / (f64)size
        if smoothness > 0.0 and curved > 0 and mean > 0.0:
            center = center.add(normal_sum.multiply_scalar(smoothness * radius / (f64)curved * (1.0 - mean) / normal_sum.length()))
        face_ids[face] = try builder.mixed_point(center, face_parents, face_weights)
    if smooth: try catmull_clark_points(&topology, whole, builder, centers)
    var ring = KeptRing()
    defer ring.close()
    for face in 0..<faces:
        if whole.get(face):
            try whole_face(&topology, face, edge_ids, face_ids[face], builder)
            for _ in 0..<(usize)offsets[face + 1] - (usize)offsets[face]: try marks.whole.push(1)
            continue
        let made = try kept_face(&topology, face, split, edge_ids, patterns, &ring, builder)
        for _ in 0..<made: try marks.whole.push(0)

## Face `face` split whole: a quad at each corner through its two edge
## points and the face point `center`.
func whole_face(topology: const Topology*, face: usize, edge_ids: const i32[], center: i32, builder: TopologyBuilder*) -> !:
    let corners = topology.corners
    let start = (usize)topology.offsets[face]
    let size = (usize)topology.offsets[face + 1] - start
    var mixed_parents: i32[256]
    var mixed_weights: f32[256]
    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 mix = 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_ids[(usize)topology.corner_edges[corner]], pair, half)
        try builder.shared_corner(center, mix)
        let back: i32[2] = [(i32)previous, (i32)corner]
        try builder.mixed_corner(edge_ids[(usize)topology.corner_edges[previous]], back, half)
        try builder.end_face()

## A face's corners with its split edges' points between them: per entry
## the point, the face corner it starts at, and whether it is an edge's
## middle (its corner mixes that corner and the next).
struct KeptRing:
    var points: Growing[i32]
    var corners: Growing[i32]
    var middles: Growing[u8]

    func init():
        self.points = Growing[i32]()
        self.corners = Growing[i32]()
        self.middles = Growing[u8]()

    func close():
        self.points.close()
        self.corners.close()
        self.middles.close()

    func clear():
        self.points.clear()
        self.corners.clear()
        self.middles.clear()

    func push(point: i32, corner: i32, middle: bool) -> !:
        try self.points.push(point)
        try self.corners.push(corner)
        try self.middles.push(1 if middle else 0)

## A face not split whole, kept joined to the split ones: its split edges'
## points become its corners, and (on the first level) two of them are
## joined across it, or a quad's three cut as Blender's quad_3edge. How
## many faces it made.
func kept_face(topology: const Topology*, face: usize, split: Bits, edge_ids: const i32[], patterns: bool, ring: KeptRing*, builder: TopologyBuilder*) -> usize!:
    let start = (usize)topology.offsets[face]
    let size = (usize)topology.offsets[face + 1] - start
    ring.clear()
    var cuts: usize = 0
    for at in 0..<size:
        let corner = start + at
        try ring.push(topology.corners[corner], (i32)corner, false)
        let edge = (usize)topology.corner_edges[corner]
        if split.get(edge):
            try ring.push(edge_ids[edge], (i32)corner, true)
            cuts += 1
    if cuts == 0:
        try builder.face((i32)face, true)
        for corner in start..<start + size: try builder.corner(topology.corners[corner], (i32)corner)
        try builder.end_face()
        return 1
    let length = ring.points.count
    if patterns and cuts == 2:
        let first = kept_middle(ring, 0)
        let second = kept_middle(ring, first + 1)
        try kept_part(topology, face, ring, first, second, builder)
        try kept_part(topology, face, ring, second, first + length, builder)
        return 2
    if patterns and cuts == 3 and size == 4:
        # The middle after the uncut edge, then the other two in order.
        var after: usize = 0
        while after < length:
            if ring.middles.items[after] != 0 and ring.middles.items[(after + length - 2) % length] == 0: break
            after += 1
        let one = after
        let two = kept_middle(ring, one + 1)
        let three = kept_middle(ring, two + 1)
        try kept_part(topology, face, ring, one, two, builder)
        try kept_part(topology, face, ring, two, three, builder)
        try kept_triangle(topology, face, ring, one, two, three, builder)
        try kept_part(topology, face, ring, three, one + length, builder)
        return 4
    try kept_part(topology, face, ring, 0, length - 1, builder)
    return 1

## The first middle at or after ring entry `start` (counting round).
func kept_middle(ring: const KeptRing*, start: usize) -> usize:
    let length = ring.points.count
    for step in 0..<length:
        if ring.middles.items[(start + step) % length] != 0: return start + step
    return start

## The face of ring entries `first` to `last`, counting round.
func kept_part(topology: const Topology*, face: usize, ring: const KeptRing*, first: usize, last: usize, builder: TopologyBuilder*) -> !:
    try builder.face((i32)face)
    for at in first..<last + 1: try kept_corner(topology, ring, at % ring.points.count, builder)
    try builder.end_face()

## A triangle of three ring entries.
func kept_triangle(topology: const Topology*, face: usize, ring: const KeptRing*, a: usize, b: usize, c: usize, builder: TopologyBuilder*) -> !:
    let length = ring.points.count
    try builder.face((i32)face)
    try kept_corner(topology, ring, a % length, builder)
    try kept_corner(topology, ring, b % length, builder)
    try kept_corner(topology, ring, c % length, builder)
    try builder.end_face()

func kept_corner(topology: const Topology*, ring: const KeptRing*, at: usize, builder: TopologyBuilder*) -> !:
    let corner = ring.corners.items[at]
    if ring.middles.items[at] == 0: return try builder.corner(ring.points.items[at], corner)
    let pair: i32[2] = [corner, (i32)topology.next((usize)corner)]
    let half: f32[2] = [0.5, 0.5]
    try builder.mixed_corner(ring.points.items[at], pair, half)

## Each point's normal: its faces', weighted by their corner angles (zero
## for a point no face uses).
func corner_normals(mesh: const Mesh*, topology: const Topology*, point_normals: Vector3[]) -> !:
    let normals = mesh.face_normal_span()
    for at in 0..<point_normals.length: point_normals[at] = Vector3()
    for corner in 0..<topology.corners.length:
        let point = topology.corners[corner]
        let here = point_of(mesh, point)
        let before = point_of(mesh, topology.corners[topology.previous(corner)]).subtract(here)
        let after = point_of(mesh, topology.corners[topology.next(corner)]).subtract(here)
        let lengths = before.length() * after.length()
        if lengths <= 0.0: continue
        let angle = math.acos(math.max(-1.0, math.min(1.0, before.dot(after) / lengths)))
        point_normals[(usize)point] = point_normals[(usize)point].add(normals[(usize)topology.corner_faces[corner]].vector().multiply_scalar(angle))
    for at in 0..<point_normals.length:
        let length = point_normals[at].length()
        if length > 0.0: point_normals[at] = point_normals[at].multiply_scalar(1.0 / length)

## Each edge's rise for Smoothness (its arc's sagitta along its ends'
## mean normal, times `smoothness`) and the radius its ends' normals give
## (0 where they agree).
func edge_rises(mesh: const Mesh*, topology: const Topology*, smoothness: f64, point_normals: const Vector3[], rises: Vector3[], radii: f64[]):
    for edge in 0..<rises.length:
        let na = point_normals[(usize)topology.edge_points[edge * 2]]
        let nb = point_normals[(usize)topology.edge_points[edge * 2 + 1]]
        let mean = na.add(nb)
        let length = mean.length()
        if length <= 0.0: continue
        let angle = math.acos(math.max(-1.0, math.min(1.0, na.dot(nb))))
        if angle < 0.000001: continue
        let chord = point_of(mesh, topology.edge_points[edge * 2 + 1]).subtract(point_of(mesh, topology.edge_points[edge * 2])).length()
        radii[edge] = chord / (2.0 * math.sin(angle * 0.5))
        rises[edge] = mean.multiply_scalar(smoothness * radii[edge] * (1.0 - length * 0.5) / length)

## 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, and so do points with a face
## that does not split whole.
func catmull_clark_points(topology: const Topology*, whole: Bits, 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
    let held = try new u8[topology.points] --- in memory.heap
    defer free(held) in memory.heap
    for at in 0..<topology.points: held[at] = 0
    for corner in 0..<topology.corners.length:
        let point = (usize)topology.corners[corner]
        let face = (usize)topology.corner_faces[corner]
        point_faces[point] = point_faces[point].add(centers[face])
        face_counts[point] += 1
        if not whole.get(face): held[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 or held[point] != 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])