Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / verbs / rip.lucb

## Edge Split and Rip, after Blender's Edge Split and Rip (V, Alt V).
##
## Both cut the surface open along edges: around each point the faces fall
## into sectors, apart at the cut edges (and the mesh's boundary), and every
## home but the first gets a copy of the point. Edge Split cuts the
## group's edges where they make sectors: a chain's interior points split,
## its ends where they meet a boundary or another cut.
##
## Rip opens a hole as Blender's does: where a chain of the group's edges
## ends inside the surface, the cut goes on one more edge at that end (the
## one opposite at a four-edge point, the next one on the ripped side at a
## three-edge point, the second round at others), so the end point splits
## too. The ripped side (left of each chain as it runs, Flip for the other)
## moves Offset away from the cut, along its faces. A point of the group on
## no ripped edge splits its fan in two along two opposite edges (Turn picks
## which), its Flip half moving. Fill closes the opened gap with faces
## (Blender's Rip Fill). The ripped side's edges (a point rip's copy) are
## the output selection; Edge Split selects the cut edges.

let edge_split_parms: ParmSpec[1] = [ParmSpec("", ParmKind.number, 0.0, 0.0, 0.0)]

func edge_split_verb() -> Verb:
    return Verb("Edge Split", "Modeling", "Tear the surface open along the group's edges: the faces either side get their own points", Domain.edge, true, edge_split_parms[..<0], true, cook_edge_split, section = "Modify", family = "Split", icon = "split-face", picks = pick_edges)

let rip_parms: ParmSpec[4] = [
    ParmSpec("Offset", ParmKind.number, 0.1, -100000.0, 100000.0, 1, "", "How far the ripped side moves away from the cut, along its faces.", 1.0),
    ParmSpec("Fill", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Close the opened gap with faces."),
    ParmSpec("Flip", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Rip the other side (the other half of a point's fan)."),
    ParmSpec("Turn", ParmKind.integer, 0.0, -64.0, 64.0, 1, "", "A ripped point: which pair of its edges splits its fan, counted round it.", more = true)]

let rip_keys: KeySpec[2] = [KeySpec("F", 2, "toggle"), KeySpec("L", 1, "toggle")]

## Points rip as they are.
let rip_also: Domain[1] = [Domain.point]

func rip_verb() -> Verb:
    return Verb("Rip", "Modeling", "Tear the surface open along the group's edges (or at its points) and pull one side away", Domain.edge, true, rip_parms, true, cook_rip, false, rip_also, section = "Modify", family = "Split", icon = "sketch-break", picks = pick_components, drag = 0, keys = rip_keys)

## The cut: which edges split, each corner's home root, and per point
## the copies its sectors get.
struct Tear:
    var split: BitsBuilder
    var root: Growing[i32]
    ## Per corner: the output point it takes.
    var point_of: Growing[i32]

    func init():
        self.split = BitsBuilder(Column[u64](), 0)
        self.root = Growing[i32]()
        self.point_of = Growing[i32]()

    func close():
        self.split.close()
        self.root.close()
        self.point_of.close()

func cook_edge_split(input: const VerbInput*, output: VerbOutput*) -> !:
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    var cut = Tear()
    defer cut.close()
    cut.split = try manifold_edges(&topology, input.group)
    let made = try cut_open(mesh, &topology, &cut, output)
    if made == 0:
        output.warning = "No point of the group's edges splits (an edge alone inside the surface needs another cut at its ends; Rip makes one); the input passes through"
        output.built = false
        return
    try finish_faces(mesh, &topology, &cut, output)
    for edge in 0..<topology.edges():
        if not cut.split.view().get(edge): continue
        for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
            let corner = (usize)topology.edge_corners[at]
            try output.builder.select_edge(cut.point_of.items[corner], cut.point_of.items[topology.next(corner)])

## The group's edges with exactly two faces (the only ones a cut opens).
func manifold_edges(topology: const Topology*, group: Bits) -> BitsBuilder!:
    var result = try BitsBuilder.zeros(topology.edges())
    for edge in 0..<topology.edges():
        if group.get(edge) and topology.edge_corner_offsets[edge + 1] - topology.edge_corner_offsets[edge] == 2: result.set(edge)
    return result

## The sectors: corners at a point join across every manifold edge that is
## not cut; each point's first home keeps it, the others get copies. How
## many copies were made.
func cut_open(mesh: const Mesh*, topology: const Topology*, cut: Tear*, output: VerbOutput*) -> usize!:
    let corners = topology.corners.length
    try cut.root.reserve(corners)
    cut.root.count = corners
    for at in 0..<corners: cut.root.items[at] = (i32)at
    for edge in 0..<topology.edges():
        if cut.split.view().get(edge): continue
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 2: continue
        let a = (usize)topology.edge_corners[first]
        let b = (usize)topology.edge_corners[first + 1]
        # a runs p to q in its face, b q to p: p's corners are a and the
        # one after b, q's the one after a and b.
        sector_join(cut.root.items[..<corners], (i32)a, (i32)topology.next(b))
        sector_join(cut.root.items[..<corners], (i32)topology.next(a), (i32)b)
    for at in 0..<corners: cut.root.items[at] = sector_root(cut.root.items[..<corners], (i32)at)
    var builder = &output.builder
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    output.built = true
    try cut.point_of.fill(corners, -1)
    # Per point: the root of the home that keeps it (-1: none seen yet).
    let keeper = try new i32[topology.points] --- in memory.heap
    defer free(keeper) in memory.heap
    for at in 0..<topology.points: keeper[at] = -1
    var made: usize = 0
    # Roots are their sectors' lowest corners, so a root is numbered before
    # the corners joined to it.
    for corner in 0..<corners:
        let point = topology.corners[corner]
        let home = cut.root.items[corner]
        if home != (i32)corner:
            cut.point_of.items[corner] = cut.point_of.items[(usize)home]
            continue
        if keeper[(usize)point] < 0:
            keeper[(usize)point] = home
            cut.point_of.items[corner] = point
            continue
        cut.point_of.items[corner] = try builder.point(builder.position(point), point)
        made += 1
    return made

## The faces over the cut's points: faces with a moved corner rebuilt,
## the rest copied in runs.
func finish_faces(mesh: const Mesh*, topology: const Topology*, cut: const Tear*, output: VerbOutput*) -> !:
    var builder = &output.builder
    var run: usize = 0
    for face in 0..<topology.faces():
        var moved = false
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            if cut.point_of.items[corner] != topology.corners[corner]: moved = true
        if not moved: continue
        try builder.copy_faces(mesh, run, face)
        run = face + 1
        try builder.face((i32)face, true)
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]: try builder.corner(cut.point_of.items[corner], (i32)corner)
        try builder.end_face()
    try builder.copy_faces(mesh, run, topology.faces())

func sector_root(parent: i32[], at: i32) -> i32:
    var here = at
    while parent[(usize)here] != here:
        parent[(usize)here] = parent[(usize)parent[(usize)here]]
        here = parent[(usize)here]
    return here

## Join two corners' sectors; the lower corner is the root.
func sector_join(parent: i32[], a: i32, b: i32):
    let x = sector_root(parent, a)
    let y = sector_root(parent, b)
    if x == y: return
    if x < y:
        parent[(usize)y] = x
    else:
        parent[(usize)x] = y

## The corners round point `point` in fan order (from each corner across
## the edge leaving it to the next face's corner at the point), from a
## boundary when the fan is open; whether it is closed.
func fan_corners(mesh: const Mesh*, topology: const Topology*, point: usize, out: Growing[i32]*) -> bool!:
    out.clear()
    let (offsets, faces) = try mesh.point_face_span()
    let first_slot = (usize)offsets[point]
    if (usize)offsets[point + 1] == first_slot: return false
    let initial = face_corner_at(topology, (usize)faces[first_slot], point)
    # Back across arriving edges to a boundary, if there is one.
    var start = initial
    var steps: usize = 0
    while steps <= topology.corners.length:
        let back = topology.twin(topology.previous(start))
        if back < 0 or (usize)back == initial: break
        start = (usize)back
        steps += 1
    var at = start
    var closed = false
    while out.count <= topology.corners.length:
        try out.push((i32)at)
        let across = topology.twin(at)
        if across < 0: break
        at = topology.next((usize)across)
        if at == start:
            closed = true
            break
    return closed

## Face `face`'s corner at `point`.
func face_corner_at(topology: const Topology*, face: usize, point: usize) -> usize:
    for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
        if (usize)topology.corners[corner] == point: return corner
    return (usize)topology.offsets[face]

## What ripping moves: corners whose sectors move, and per corner the way.
struct Ripped:
    var corners: Growing[i32]
    var ways: Growing[Vector3]
    ## Corners of the moving side along the ripped edges (their edges are
    ## the output selection).
    var edges: Growing[i32]

    func init():
        self.corners = Growing[i32]()
        self.ways = Growing[Vector3]()
        self.edges = Growing[i32]()

    func close():
        self.corners.close()
        self.ways.close()
        self.edges.close()

func cook_rip(input: const VerbInput*, output: VerbOutput*) -> !:
    let offset = input.parms.at(0)
    if not math.is_finite(offset): error(errors.invalid, "Rip's offset must be finite")
    let fill = input.parms.at(1) != 0.0
    let flip = input.parms.at(2) != 0.0
    let turns = (i64)math.max(-64.0, math.min(64.0, input.parms.at(3)))
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    var cut = Tear()
    defer cut.close()
    var ripped = Ripped()
    defer ripped.close()
    if input.domain == Domain.point:
        cut.split = try BitsBuilder.zeros(topology.edges())
        try point_rips(mesh, &topology, input.group, flip, turns, &cut, &ripped)
    else:
        cut.split = try manifold_edges(&topology, input.group)
        try edge_rips(mesh, &topology, flip, &cut, &ripped)
    let made = try cut_open(mesh, &topology, &cut, output)
    if made == 0:
        output.warning = "Nothing to rip: the group has no edge between two faces, or no point whose fan splits; the input passes through"
        output.built = false
        return
    try finish_faces(mesh, &topology, &cut, output)
    var builder = &output.builder
    # The ripped side moves: each moving point along the mean of its ways.
    let points = builder.point_count()
    let ways = try new Vector3[points] --- in memory.heap
    defer free(ways) in memory.heap
    for at in 0..<points: ways[at] = Vector3()
    for at in 0..<ripped.corners.count:
        let point = (usize)cut.point_of.items[(usize)ripped.corners.items[at]]
        ways[point] = ways[point].add(ripped.ways.items[at])
    if offset != 0.0:
        for point in 0..<points:
            let length = ways[point].length()
            if length > 0.0: builder.move_point((i32)point, builder.position((i32)point).add(ways[point].multiply_scalar(offset / length)))
    if fill: try fill_gaps(&topology, &cut, builder)
    if input.domain == Domain.point:
        output.selection = try BitsBuilder.zeros(points)
        output.selection_domain = Domain.point
        for at in 0..<points:
            if ways[at].length() > 0.0: output.selection.set(at)
        return
    for corner in ripped.edges.view():
        try builder.select_edge(cut.point_of.items[(usize)corner], cut.point_of.items[topology.next((usize)corner)])

## Ripping the cut's edges: per chain (in the order its points run) the
## faces on its left (right with `flip`) move; a chain end inside the
## surface cuts on one more edge (Blender's rule), so it splits too.
func edge_rips(mesh: const Mesh*, topology: const Topology*, flip: bool, cut: Tear*, ripped: Ripped*) -> !:
    var chains = EdgeChains()
    defer chains.close()
    try edge_chains(topology, cut.split.view(), &chains)
    var extra = try BitsBuilder.zeros(topology.edges())
    defer extra.close()
    for index in 0..<chains.count():
        let chain = chains.chain(index)
        let closed = chains.closed.items[index] != 0
        let segments = chain.length if closed else chain.length - 1
        for at in 0..<segments:
            let p = chain[at]
            let q = chain[(at + 1) % chain.length]
            let corner = directed_corner(topology, p, q, flip)
            if corner < 0: continue
            try ripped.edges.push(corner)
            let way = rip_way(mesh, topology, (usize)corner)
            try ripped.corners.push(corner)
            try ripped.ways.push(way)
            try ripped.corners.push((i32)topology.next((usize)corner))
            try ripped.ways.push(way)
            # A chain end inside the surface: the cut goes on one edge.
            if not closed and at == 0: extend_end(topology, (usize)corner, (usize)p, &extra)
            if not closed and at == segments - 1: extend_end(topology, (usize)corner, (usize)q, &extra)
    cut.split.unite(extra.view())

## The corner of the face on the left of `p` → `q` (its edge runs p to q;
## with `flip` the one running q to p), or -1.
func directed_corner(topology: const Topology*, p: i32, q: i32, flip: bool) -> i32:
    for slot in (usize)topology.point_edge_offsets[(usize)p]..<(usize)topology.point_edge_offsets[(usize)p + 1]:
        let edge = (usize)topology.point_edges[slot]
        for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
            let corner = (usize)topology.edge_corners[at]
            let from_point = topology.corners[corner]
            let to_point = topology.corners[topology.next(corner)]
            if (not flip and from_point == p and to_point == q) or (flip and from_point == q and to_point == p): return (i32)corner
    return -1

## The way into corner `corner`'s face, square to its edge, in its plane.
func rip_way(mesh: const Mesh*, topology: const Topology*, corner: usize) -> Vector3:
    let a = point_of(mesh, topology.corners[corner])
    let b = point_of(mesh, topology.corners[topology.next(corner)])
    let normal = mesh.face_normal_span()[(usize)topology.corner_faces[corner]].vector()
    let way = normal.cross(b.subtract(a))
    let length = way.length()
    return way.multiply_scalar(1.0 / length) if length > 0.0 else Vector3()

## At chain end `point` (inside the surface), where the moving face's
## corner `corner` runs along the ripped edge: Blender's next cut. The face's other edge at the point
## is e1; at a three-edge point e1 is cut, else the edge after e1 in the
## face across it.
func extend_end(topology: const Topology*, corner: usize, point: usize, extra: BitsBuilder*):
    # Every edge at the point has two faces: the point is inside.
    var valence: usize = 0
    for slot in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
        let edge = (usize)topology.point_edges[slot]
        if topology.edge_corner_offsets[edge + 1] - topology.edge_corner_offsets[edge] != 2: return
        valence += 1
    if valence < 3: return
    let at_point = corner if (usize)topology.corners[corner] == point else topology.next(corner)
    # The ripped edge is one of this face's edges at the point; e1 the other.
    let leaving = (usize)topology.corner_edges[at_point]
    let arriving = (usize)topology.corner_edges[topology.previous(at_point)]
    let ripped_edge = (usize)topology.corner_edges[corner]
    let e1 = arriving if leaving == ripped_edge else leaving
    if valence == 3:
        extra.set(e1)
        return
    # The face across e1, and its other edge at the point.
    var across: usize = 0
    if e1 == leaving:
        let twin = topology.twin(at_point)
        if twin < 0: return
        across = topology.next((usize)twin)
    else:
        let twin = topology.twin(topology.previous(at_point))
        if twin < 0: return
        across = (usize)twin
    let out = (usize)topology.corner_edges[across]
    let back = (usize)topology.corner_edges[topology.previous(across)]
    extra.set(back if out == e1 else out)

## Ripping points: each group point's fan splits along two opposite edges
## (a boundary point's along the middle one); one half moves into itself.
func point_rips(mesh: const Mesh*, topology: const Topology*, group: Bits, flip: bool, turns: i64, cut: Tear*, ripped: Ripped*) -> !:
    var fan = Growing[i32]()
    defer fan.close()
    for point in 0..<topology.points:
        if not group.get(point): continue
        let closed = try fan_corners(mesh, topology, point, &fan)
        let n = fan.count
        var moving_first: usize = 0
        var moving_count: usize = 0
        if closed:
            if n < 2: continue
            let k = (usize)((turns % (i64)n + (i64)n) % (i64)n)
            cut.split.set((usize)topology.corner_edges[(usize)fan.items[k]])
            cut.split.set((usize)topology.corner_edges[(usize)fan.items[(k + n // 2) % n]])
            moving_first = (k + 1) % n if not flip else (k + n // 2 + 1) % n
            moving_count = n // 2 if not flip else n - n // 2
        else:
            if n < 2: continue
            let m = (usize)((((i64)(n // 2) - 1 + turns) % (i64)(n - 1) + (i64)(n - 1)) % (i64)(n - 1))
            cut.split.set((usize)topology.corner_edges[(usize)fan.items[m]])
            moving_first = m + 1 if not flip else 0
            moving_count = n - m - 1 if not flip else m + 1
        let here = point_of(mesh, (i32)point)
        var way = Vector3()
        for step in 0..<moving_count:
            let corner = (usize)fan.items[(moving_first + step) % n]
            let face = (usize)topology.corner_faces[corner]
            var middle = Vector3()
            let size = topology.offsets[face + 1] - topology.offsets[face]
            for at in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]: middle = middle.add(point_of(mesh, topology.corners[at]))
            way = way.add(middle.multiply_scalar(1.0 / (f64)size).subtract(here))
        let length = way.length()
        if length > 0.0: way = way.multiply_scalar(1.0 / length)
        for step in 0..<moving_count:
            try ripped.corners.push(fan.items[(moving_first + step) % n])
            try ripped.ways.push(way)

## Faces across the opened gap (Rip Fill): for each cut edge whose sides
## parted, the face between its two copies (a triangle where they share an
## end), winding against both sides; none where they lie together.
func fill_gaps(topology: const Topology*, cut: const Tear*, builder: TopologyBuilder*) -> !:
    for edge in 0..<topology.edges():
        if not cut.split.view().get(edge): continue
        let first = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - first != 2: continue
        let a = (usize)topology.edge_corners[first]
        let b = (usize)topology.edge_corners[first + 1]
        let ids: i32[4] = [cut.point_of.items[topology.next(b)], cut.point_of.items[b], cut.point_of.items[topology.next(a)], cut.point_of.items[a]]
        let parents: i32[4] = [(i32)topology.next(b), (i32)b, (i32)topology.next(a), (i32)a]
        var kept: i32[4]
        var kept_parents: i32[4]
        var count: usize = 0
        for at in 0..<(usize)4:
            if count > 0 and kept[count - 1] == ids[at]: continue
            if at == 3 and kept[0] == ids[at]: continue
            kept[count] = ids[at]
            kept_parents[count] = parents[at]
            count += 1
        if count < 3: continue
        # Sides that did not part (nothing moved them) leave no gap.
        var sum = Vector3()
        let base = builder.position(kept[0])
        for at in 1..<count - 1: sum = sum.add(builder.position(kept[at]).subtract(base).cross(builder.position(kept[at + 1]).subtract(base)))
        if sum.length() <= 0.000000000001: continue
        try builder.face(topology.corner_faces[a])
        for at in 0..<count: try builder.corner(kept[at], kept_parents[at])
        try builder.end_face()