Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / verbs / knife.lucb

## Knife: cut the group's faces along a stroke of several segments, after
## Blender's Knife and Cinema 4D's Knife (Line mode). The stroke is points
## (its corners, as the editor placed them: on the surface, snapped to
## points or edge middles, with angles held) and the direction it was
## drawn along (the view's); each segment cuts with the ribbon its two
## points sweep along that direction. With Cut through every face the
## ribbon crosses is cut; else only those facing the view that nothing
## hides (Blender's default). A face splits along each path the cuts make
## across it from boundary to boundary, through the stroke's corners
## inside it; a path that ends inside a face (the stroke's first or last
## point) is trimmed back to where it last crossed an edge. Faces beside a
## cut edge take its new point into their boundaries, so the surface stays
## closed. New points and corners blend their face's values (mean value
## coordinates inside a face, along the edge on one). The cut edges are
## the output selection. knife_faces.lucb splits the faces.
##
## Its numbers: Cut through, the direction (x, y, z), how many points, then
## the points (x, y, z each) after the parameters. A stroke whose last
## point is its first closes.

let knife_parms: ParmSpec[3] = [
    ParmSpec("Cut through", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Cut every face the stroke passes over, hidden ones too."),
    ParmSpec("Direction", ParmKind.vector, 0.0, -1.0, 1.0, 3, "", "The direction the stroke was drawn along (the view's).", bar = false),
    ParmSpec("Points", ParmKind.integer, 0.0, 0.0, 100000.0, 1, "", "How many stroke points follow the parameters.", bar = false)]

func knife_verb() -> Verb:
    return Verb("Knife", "Modeling", "Cut the group's faces along a stroke of segments, through or on the visible surface", Domain.face, true, knife_parms, true, cook_knife, trailing = true, section = "Modify", family = "Cut", icon = "knife", gesture = "knife", whole = true)

## A point the cut passes through: on a point, on an edge (at `t` from its
## first end), or inside a face (stroke corner `stroke` there).
struct KnifePoint:
    var kind: u8
    var element: i32
    var t: f64
    var stroke: i32
    var segment: i32
    var position: Vector3
    ## The builder's point (-1 until numbered) and the next on its element.
    var id: i32
    var next: i32

let knife_on_point: u8 = 0
let knife_on_edge: u8 = 1
let knife_in_face: u8 = 2

## One segment's cut across one face, between two knife points.
struct Chord:
    var face: i32
    var a: i32
    var b: i32
    var live: bool

## The stroke and what it cuts.
struct Knife:
    var stroke: Growing[Vector3]
    var direction: Vector3
    var through: bool
    ## Whether its last segment runs back to its first point.
    var closed: bool
    var points: Growing[KnifePoint]
    var chords: Growing[Chord]
    ## Per point, edge and face: its first knife point (a linked list).
    var on_points: Growing[i32]
    var on_edges: Growing[i32]
    var in_faces: Growing[i32]
    ## Lengths below which things meet.
    var near: f64

    func init():
        self.stroke = Growing[Vector3]()
        self.direction = Vector3()
        self.through = false
        self.closed = false
        self.points = Growing[KnifePoint]()
        self.chords = Growing[Chord]()
        self.on_points = Growing[i32]()
        self.on_edges = Growing[i32]()
        self.in_faces = Growing[i32]()
        self.near = 0.0

    func close():
        self.stroke.close()
        self.points.close()
        self.chords.close()
        self.on_points.close()
        self.on_edges.close()
        self.in_faces.close()

    ## The knife point on point `point`, made the first time.
    func at_point(point: i32, position: Vector3) -> i32!:
        if self.on_points.items[(usize)point] >= 0: return self.on_points.items[(usize)point]
        try self.points.push(KnifePoint(knife_on_point, point, 0.0, -1, -1, position, -1, -1))
        self.on_points.items[(usize)point] = (i32)(self.points.count - 1)
        return (i32)(self.points.count - 1)

    ## The knife point segment `segment` makes on edge `edge` at `t`.
    func at_edge(edge: i32, t: f64, segment: i32, position: Vector3) -> i32!:
        var at = self.on_edges.items[(usize)edge]
        while at >= 0:
            let known = self.points.items[(usize)at]
            if known.segment == segment and math.abs(known.t - t) <= 0.000000001: return at
            at = known.next
        try self.points.push(KnifePoint(knife_on_edge, edge, t, -1, segment, position, -1, self.on_edges.items[(usize)edge]))
        self.on_edges.items[(usize)edge] = (i32)(self.points.count - 1)
        return (i32)(self.points.count - 1)

    ## The knife point of stroke corner `stroke` inside face `face`.
    func in_face(face: i32, stroke: i32, position: Vector3) -> i32!:
        var at = self.in_faces.items[(usize)face]
        while at >= 0:
            let known = self.points.items[(usize)at]
            if known.stroke == stroke: return at
            at = known.next
        try self.points.push(KnifePoint(knife_in_face, face, 0.0, stroke, -1, position, -1, self.in_faces.items[(usize)face]))
        self.in_faces.items[(usize)face] = (i32)(self.points.count - 1)
        return (i32)(self.points.count - 1)

## Where a segment's ribbon crosses a face's boundary: its knife point and
## how far along the segment (0 at its start, 1 at its end).
struct Crossing:
    var point: i32
    var along: f64

func crossing_before(a: Crossing, b: Crossing) -> bool:
    return a.along < b.along

func cook_knife(input: const VerbInput*, output: VerbOutput*) -> !:
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    var knife = Knife()
    defer knife.close()
    try read_stroke(input, &knife)
    if knife.stroke.count < 2:
        output.warning = "Draw the knife's stroke in the viewport: it needs two points or more; the input passes through"
        return
    let box = mesh.bounds()
    knife.near = math.max(0.000000001, box.maximum.subtract(box.minimum).length() * 0.000000001)
    try knife.on_points.fill(topology.points, -1)
    try knife.on_edges.fill(topology.edges(), -1)
    try knife.in_faces.fill(topology.faces(), -1)
    let segments = knife.stroke.count if knife.closed else knife.stroke.count - 1
    for segment in 0..<segments:
        try cut_segment(mesh, &topology, input.group, &knife, segment)
    if not knife.through: try keep_visible(mesh, &topology, &knife)
    try trim_dangling(&knife)
    var live: usize = 0
    for chord in knife.chords.view():
        if chord.live: live += 1
    if live == 0:
        output.warning = "The stroke cuts across no face of the group from edge to edge; the input passes through"
        return
    try split_faces(mesh, &topology, &knife, output)

## The stroke from the numbers: the direction (unit) and the points.
func read_stroke(input: const VerbInput*, knife: Knife*) -> !:
    knife.through = input.parms.at(0) != 0.0
    let given = Vector3(input.parms.at(1), input.parms.at(2), input.parms.at(3))
    if not given.is_finite(): error(errors.invalid, "The knife's direction must be finite")
    # No direction is no stroke drawn yet (a node dropped in): nothing cuts.
    if given.length() == 0.0: return
    knife.direction = given.multiply_scalar(1.0 / given.length())
    let count = (usize)math.max(0.0, input.parms.at(4))
    let numbers = input.parms.numbers
    if numbers.length < 5 + count * 3: error(errors.invalid, "The knife's stroke has fewer points than it says")
    for at in 0..<count:
        let point = Vector3(numbers[5 + at * 3], numbers[6 + at * 3], numbers[7 + at * 3])
        if not point.is_finite(): error(errors.invalid, "A knife stroke point is not finite")
        # Points placed twice in a row count once.
        if knife.stroke.count > 0 and knife.stroke.items[knife.stroke.count - 1].subtract(point).length() == 0.0: continue
        try knife.stroke.push(point)
    # Back at its first point: a closed stroke.
    if knife.stroke.count >= 4 and knife.stroke.items[knife.stroke.count - 1].subtract(knife.stroke.items[0]).length() == 0.0:
        knife.stroke.count -= 1
        knife.closed = true

## Segment `segment`'s chords: in every face of the group its ribbon
## crosses, the crossings paired along the segment and clipped to it (an
## end inside the face is the stroke's corner there).
func cut_segment(mesh: const Mesh*, topology: const Topology*, group: Bits, knife: Knife*, segment: usize) -> !:
    let end_corner = (segment + 1) % knife.stroke.count
    let start = knife.stroke.items[segment]
    let end = knife.stroke.items[end_corner]
    let across = end.subtract(start)
    # The part of the segment square to the direction, and the ribbon's
    # normal.
    let flat = across.subtract(knife.direction.multiply_scalar(across.dot(knife.direction)))
    let length = flat.length()
    if length <= knife.near: return
    let along = flat.multiply_scalar(1.0 / (length * length))
    let normal_raw = across.cross(knife.direction)
    let normal = normal_raw.multiply_scalar(1.0 / normal_raw.length())
    let level = normal.dot(start)
    var crossings = Growing[Crossing]()
    defer crossings.close()
    let normals = mesh.face_normal_span()
    for face in 0..<topology.faces():
        if not group.get(face): continue
        crossings.clear()
        let first = (usize)topology.offsets[face]
        let size = (usize)topology.offsets[face + 1] - first
        for at in 0..<size:
            let corner = first + at
            let next = first + (at + 1) % size
            let previous = first + (at + size - 1) % size
            let p = point_of(mesh, topology.corners[corner])
            let q = point_of(mesh, topology.corners[next])
            let dp = normal.dot(p) - level
            let dq = normal.dot(q) - level
            if math.abs(dp) <= knife.near:
                # The ribbon through a point: a crossing where the faces
                # either side of it lie on opposite sides, not where it
                # only touches.
                let dr = normal.dot(point_of(mesh, topology.corners[previous])) - level
                if (dr > knife.near and dq > knife.near) or (dr < -knife.near and dq < -knife.near): continue
                let made = try knife.at_point(topology.corners[corner], p)
                try crossings.push(Crossing(made, p.subtract(start).dot(along)))
                continue
            if math.abs(dq) <= knife.near or (dp > 0.0) == (dq > 0.0): continue
            let edge = (usize)topology.corner_edges[corner]
            # t from the edge's first end, the same from either face.
            let forward = topology.edge_points[edge * 2] == topology.corners[corner]
            let da = dp if forward else dq
            let db = dq if forward else dp
            let t = da / (da - db)
            let a = point_of(mesh, topology.edge_points[edge * 2])
            let b = point_of(mesh, topology.edge_points[edge * 2 + 1])
            let place = a.add(b.subtract(a).multiply_scalar(t))
            let made = try knife.at_edge((i32)edge, t, (i32)segment, place)
            try crossings.push(Crossing(made, place.subtract(start).dot(along)))
        if crossings.count < 2: continue
        sort.by[Crossing](crossings.items[..<crossings.count], crossing_before)
        let facing = normals[face].vector()
        var pair: usize = 0
        while pair + 1 < crossings.count:
            let low = crossings.items[pair]
            let high = crossings.items[pair + 1]
            pair += 2
            let slack = knife.near / length
            if high.along < -slack or low.along > 1.0 + slack: continue
            var a = low.point
            var b = high.point
            if low.along < -slack:
                a = try stroke_in_face(mesh, topology, knife, face, segment, start, facing)
            if high.along > 1.0 + slack:
                b = try stroke_in_face(mesh, topology, knife, face, end_corner, end, facing)
            if a < 0 or b < 0 or a == b: continue
            # Along an existing edge: nothing to cut.
            if same_edge(topology, knife, a, b): continue
            try knife.chords.push(Chord((i32)face, a, b, true))

## Stroke corner `stroke` (at `place`) inside face `face`: moved onto the
## face's plane along the direction (-1 when the face lies edge on).
func stroke_in_face(mesh: const Mesh*, topology: const Topology*, knife: Knife*, face: usize, stroke: usize, place: Vector3, facing: Vector3) -> i32!:
    let across = facing.dot(knife.direction)
    if math.abs(across) <= 0.000001: return -1
    let anchor = point_of(mesh, topology.corners[(usize)topology.offsets[face]])
    let travel = facing.dot(anchor.subtract(place)) / across
    return try knife.in_face((i32)face, (i32)stroke, place.add(knife.direction.multiply_scalar(travel)))

## Whether knife points `a` and `b` are the two ends of one edge.
func same_edge(topology: const Topology*, knife: const Knife*, a: i32, b: i32) -> bool:
    let x = knife.points.items[(usize)a]
    let y = knife.points.items[(usize)b]
    if x.kind != knife_on_point or y.kind != knife_on_point: return false
    let p = (usize)x.element
    for slot in (usize)topology.point_edge_offsets[p]..<(usize)topology.point_edge_offsets[p + 1]:
        let edge = (usize)topology.point_edges[slot]
        if topology.edge_points[edge * 2] == y.element or topology.edge_points[edge * 2 + 1] == y.element: return true
    return false

## Without Cut through: only chords on faces facing the view whose middle
## nothing hides (a ray back toward the view hits no face).
func keep_visible(mesh: const Mesh*, topology: const Topology*, knife: Knife*) -> !:
    let normals = mesh.face_normal_span()
    let back = knife.direction.multiply_scalar(-1.0)
    let box = mesh.bounds()
    let lift = math.max(0.0000001, box.maximum.subtract(box.minimum).length() * 0.000001)
    for at in 0..<knife.chords.count:
        let chord = knife.chords.items[at]
        if normals[(usize)chord.face].vector().dot(knife.direction) >= 0.0:
            knife.chords.items[at].live = false
            continue
        let middle = knife.points.items[(usize)chord.a].position.add(knife.points.items[(usize)chord.b].position).multiply_scalar(0.5)
        let hit = try mesh.ray_face(middle.add(back.multiply_scalar(lift)), back)
        if hit >= 0: knife.chords.items[at].live = false