Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / verbs / decimate.lucb

## PolyReduce (Decimate): fewer faces for the group, after Blender's
## Decimate and Houdini's PolyReduce. Collapse merges edges, cheapest first,
## until the group's triangles are Ratio of what they were: the
## Garland–Heckbert quadric of each point (the planes of its triangles,
## weighted by area, and on the outline planes square to the faces there,
## weighted heavily so the outline keeps its shape) prices moving it; an
## edge collapses to the place its two quadrics price lowest, unless that
## turns a triangle over or would join the surface where it should not
## (the two ends sharing more neighbors than the triangles on the edge).
## Lock boundary keeps the outline's points (and every point a face outside
## the group uses) where they are. The result is triangles. Un-subdivide
## undoes subdivision on the group's quads (unsubdivide.lucb); Planar is
## Limited Dissolve's join by angle. The new faces are the output
## selection.

let reduce_parms: ParmSpec[5] = [
    ParmSpec("Mode", ParmKind.menu, 0.0, 0.0, 2.0, 1, "Collapse|Un-subdivide|Planar", "Collapse edges to a share of the triangles, undo subdivision, or join faces flatter than the angle."),
    ParmSpec("Ratio", ParmKind.number, 0.5, 0.0, 1.0, 1, "", "Collapse: the share of the group's triangles kept."),
    ParmSpec("Iterations", ParmKind.integer, 1.0, 1.0, 16.0, 1, "", "Un-subdivide: how many subdivisions to undo."),
    ParmSpec("Angle", ParmKind.number, 5.0, 0.0, 180.0, 1, "", "Planar: faces meeting flatter than this many degrees join.", 30.0),
    ParmSpec("Lock boundary", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Collapse: keep the outline's points where they are.")]

func reduce_verb() -> Verb:
    return Verb("PolyReduce", "Modeling", "Fewer faces: collapse edges to a share of the triangles, undo subdivision, or join flat faces", Domain.face, true, reduce_parms, true, cook_reduce, label = "Decimate", section = "Modify", family = "Delete", icon = "clean-mesh", picks = pick_pieces, whole = true, drag = 1, drag_mode = "amount")

func cook_reduce(input: const VerbInput*, output: VerbOutput*) -> !:
    let mode = (usize)math.max(0.0, math.min(2.0, input.parms.at(0)))
    if mode == 1: return try unsubdivide(input, output, (usize)math.max(1.0, math.min(16.0, input.parms.at(2))))
    if mode == 2:
        let numbers: f64[6] = [input.parms.at(3), 0.0, 0.0, 0.0, 0.0, 0.0]
        let planar = VerbInput(input.mesh, input.group, Parms(numbers[..<6]), input.symmetry, input.domain)
        return try cook_limited_dissolve(&planar, output)
    let ratio = input.parms.at(1)
    if not (ratio >= 0.0 and ratio <= 1.0): error(errors.invalid, "Decimate's ratio must be in 0..1")
    try collapse_edges(input, output, ratio, input.parms.at(4) != 0.0)

## A symmetric 4×4 quadric (plane equations squared): its ten numbers.
struct Quadric:
    var a: f64[10]

    func plus(other: Quadric) -> Quadric:
        var sum = Quadric([0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])
        for k in 0..<(usize)10: sum.a[k] = self.a[k] + other.a[k]
        return sum

    ## Its price at `p`.
    func at(p: Vector3) -> f64:
        let q = self.a
        return q[0] * p.x * p.x + 2.0 * q[1] * p.x * p.y + 2.0 * q[2] * p.x * p.z + 2.0 * q[3] * p.x + q[4] * p.y * p.y + 2.0 * q[5] * p.y * p.z + 2.0 * q[6] * p.y + q[7] * p.z * p.z + 2.0 * q[8] * p.z + q[9]

## The quadric of the plane through `p` with unit normal `n`, times `weight`.
func plane_quadric(n: Vector3, p: Vector3, weight: f64) -> Quadric:
    let d = -n.dot(p)
    return Quadric([n.x * n.x * weight, n.x * n.y * weight, n.x * n.z * weight, n.x * d * weight, n.y * n.y * weight, n.y * n.z * weight, n.y * d * weight, n.z * n.z * weight, n.z * d * weight, d * d * weight])

## Where quadric `q` prices lowest (its 3×3 system solved), else the best
## of `a`, `b` and their middle.
func cheapest(q: Quadric, a: Vector3, b: Vector3) -> Vector3:
    let m = q.a
    let det = m[0] * (m[4] * m[7] - m[5] * m[5]) - m[1] * (m[1] * m[7] - m[5] * m[2]) + m[2] * (m[1] * m[5] - m[4] * m[2])
    let scale = math.max(math.abs(m[0]) + math.abs(m[4]) + math.abs(m[7]), 0.000000000001)
    if math.abs(det) > 0.000001 * scale * scale * scale:
        let bx = -m[3]
        let by = -m[6]
        let bz = -m[8]
        let x = (bx * (m[4] * m[7] - m[5] * m[5]) - m[1] * (by * m[7] - m[5] * bz) + m[2] * (by * m[5] - m[4] * bz)) / det
        let y = (m[0] * (by * m[7] - bz * m[5]) - bx * (m[1] * m[7] - m[5] * m[2]) + m[2] * (m[1] * bz - by * m[2])) / det
        let z = (m[0] * (m[4] * bz - m[5] * by) - m[1] * (m[1] * bz - by * m[2]) + bx * (m[1] * m[5] - m[4] * m[2])) / det
        let solved = Vector3(x, y, z)
        if solved.is_finite(): return solved
    let middle = a.add(b).multiply_scalar(0.5)
    var best = a
    if q.at(b) < q.at(best): best = b
    if q.at(middle) < q.at(best): best = middle
    return best

## A candidate collapse in the heap: its price, its ends, and the versions
## of its ends it was priced at.
struct Candidate:
    var cost: f64
    var u: i32
    var v: i32
    var stamp_u: u32
    var stamp_v: u32

## The collapse's state, over the points of the group's triangles only
## (numbered apart: `globals` gives each its mesh point): the triangles
## (their corners always the points they are at now), each point's live
## triangles (a slice of `pool`; a merge writes the joined list as a new
## slice), places, quadrics, locks and versions.
struct Collapse:
    var globals: Growing[i32]
    var corners: Growing[i32]
    var sources: Growing[i32]
    var alive: Growing[u8]
    var places: Growing[Vector3]
    var quadrics: Growing[Quadric]
    var locked: Growing[u8]
    var merged_into: Growing[i32]
    var stamps: Growing[u32]
    var list_start: Growing[i32]
    var list_count: Growing[i32]
    var pool: Growing[i32]
    var heap: Growing[Candidate]
    var live_triangles: usize
    ## Scratch marks for neighbor sets.
    var marks: Growing[u32]
    var mark: u32

    func init():
        self.globals = Growing[i32]()
        self.corners = Growing[i32]()
        self.sources = Growing[i32]()
        self.alive = Growing[u8]()
        self.places = Growing[Vector3]()
        self.quadrics = Growing[Quadric]()
        self.locked = Growing[u8]()
        self.merged_into = Growing[i32]()
        self.stamps = Growing[u32]()
        self.list_start = Growing[i32]()
        self.list_count = Growing[i32]()
        self.pool = Growing[i32]()
        self.heap = Growing[Candidate]()
        self.live_triangles = 0
        self.marks = Growing[u32]()
        self.mark = 0

    func close():
        self.globals.close()
        self.corners.close()
        self.sources.close()
        self.alive.close()
        self.places.close()
        self.quadrics.close()
        self.locked.close()
        self.merged_into.close()
        self.stamps.close()
        self.list_start.close()
        self.list_count.close()
        self.pool.close()
        self.heap.close()
        self.marks.close()

    ## Point `point`'s triangles (some may have died since).
    func triangles_of(point: i32) -> const i32[]:
        let start = (usize)self.list_start.items[(usize)point]
        return self.pool.items[start..<start + (usize)self.list_count.items[(usize)point]]

    ## Whether live triangle `t` has point `point`.
    func has(t: usize, point: i32) -> bool:
        return self.corners.items[t * 3] == point or self.corners.items[t * 3 + 1] == point or self.corners.items[t * 3 + 2] == point

func collapse_edges(input: const VerbInput*, output: VerbOutput*, ratio: f64, lock_boundary: bool) -> !:
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    var state = Collapse()
    defer state.close()
    try collapse_setup(mesh, &topology, input.group, lock_boundary, &state)
    if state.live_triangles == 0:
        output.warning = "No faces in the group to decimate; the input passes through"
        return
    let target = (usize)math.round((f64)state.live_triangles * ratio)
    while state.live_triangles > target and state.heap.count > 0:
        let next = heap_pop(&state.heap)
        if next.stamp_u != state.stamps.items[(usize)next.u] or next.stamp_v != state.stamps.items[(usize)next.v]: continue
        if state.merged_into.items[(usize)next.u] >= 0 or state.merged_into.items[(usize)next.v] >= 0: continue
        try collapse_one(&state, next.u, next.v)
    try collapse_output(mesh, &topology, input.group, &state, output)

## The triangles of the group's faces, each point's quadric, the locked
## points and every edge's first price.
func collapse_setup(mesh: const Mesh*, topology: const Topology*, group: Bits, lock_boundary: bool, state: Collapse*) -> !:
    let triangles = mesh.triangle_span()
    let offsets = topology.offsets
    # The group's triangles over their own numbering of points.
    let local = try new i32[topology.points] --- in memory.heap
    defer free(local) in memory.heap
    for at in 0..<topology.points: local[at] = -1
    for face in 0..<topology.faces():
        if not group.get(face): continue
        let start = (usize)offsets[face]
        let size = (usize)offsets[face + 1] - start
        let first = (start - face * 2) * 3
        for k in 0..<(size - 2) * 3:
            let corner = (usize)triangles[first + k]
            let point = (usize)topology.corners[corner]
            if local[point] < 0:
                local[point] = (i32)state.globals.count
                try state.globals.push((i32)point)
            try state.corners.push(local[point])
            try state.sources.push((i32)corner)
        for _ in 0..<size - 2: try state.alive.push(1)
    state.live_triangles = state.alive.count
    let points = state.globals.count
    try state.places.reserve(points)
    for at in 0..<points: try state.places.push(point_of(mesh, state.globals.items[at]))
    try state.quadrics.fill(points, Quadric([0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]))
    try state.locked.fill(points, 0)
    try state.merged_into.fill(points, -1)
    try state.stamps.fill(points, 0)
    try state.marks.fill(points, 0)
    # Each point's triangles: its slice of the pool.
    try state.list_count.fill(points, 0)
    for point in state.corners.view(): state.list_count.items[(usize)point] += 1
    try state.list_start.fill(points, 0)
    var total: i32 = 0
    for at in 0..<points:
        state.list_start.items[at] = total
        total += state.list_count.items[at]
    try state.pool.fill((usize)total, 0)
    var fill = Growing[i32]()
    defer fill.close()
    try fill.assign(state.list_start.view())
    for at in 0..<state.corners.count:
        let point = (usize)state.corners.items[at]
        state.pool.items[(usize)fill.items[point]] = (i32)(at // 3)
        fill.items[point] += 1
    # Quadrics: the triangles' planes by area; the outline's (edges with one
    # triangle) square planes, heavily.
    let triangle_count = state.alive.count
    for t in 0..<triangle_count:
        let a = state.places.items[(usize)state.corners.items[t * 3]]
        let b = state.places.items[(usize)state.corners.items[t * 3 + 1]]
        let c = state.places.items[(usize)state.corners.items[t * 3 + 2]]
        let normal = b.subtract(a).cross(c.subtract(a))
        let doubled = normal.length()
        if doubled <= 0.0: continue
        let plane = plane_quadric(normal.multiply_scalar(1.0 / doubled), a, doubled * 0.5)
        for k in 0..<(usize)3:
            let point = (usize)state.corners.items[t * 3 + k]
            state.quadrics.items[point] = state.quadrics.items[point].plus(plane)
        for k in 0..<(usize)3:
            let p = state.corners.items[t * 3 + k]
            let q = state.corners.items[t * 3 + (k + 1) % 3]
            if triangles_on(state, p, q) != 1: continue
            let pp = state.places.items[(usize)p]
            let along = state.places.items[(usize)q].subtract(pp)
            let side = along.cross(normal)
            let length = side.length()
            if length <= 0.0: continue
            let wall = plane_quadric(side.multiply_scalar(1.0 / length), pp, 1000.0 * along.dot(along))
            state.quadrics.items[(usize)p] = state.quadrics.items[(usize)p].plus(wall)
            state.quadrics.items[(usize)q] = state.quadrics.items[(usize)q].plus(wall)
            if lock_boundary:
                state.locked.items[(usize)p] = 1
                state.locked.items[(usize)q] = 1
    # Points a face outside the group uses stay.
    for face in 0..<topology.faces():
        if group.get(face): continue
        for corner in (usize)offsets[face]..<(usize)offsets[face + 1]:
            let at = local[(usize)topology.corners[corner]]
            if at >= 0: state.locked.items[(usize)at] = 1
    for t in 0..<triangle_count:
        for k in 0..<(usize)3:
            let p = state.corners.items[t * 3 + k]
            let q = state.corners.items[t * 3 + (k + 1) % 3]
            if p < q or triangles_on(state, p, q) == 1: try price(state, p, q)

## How many live triangles have both `p` and `q`.
func triangles_on(state: const Collapse*, p: i32, q: i32) -> usize:
    var count: usize = 0
    for t in state.triangles_of(p):
        if state.alive.items[(usize)t] != 0 and state.has((usize)t, q): count += 1
    return count

## Push edge `p`–`q`'s collapse at its price (none when both are locked).
func price(state: Collapse*, p: i32, q: i32) -> !:
    let lock_p = state.locked.items[(usize)p] != 0
    let lock_q = state.locked.items[(usize)q] != 0
    if lock_p and lock_q: return
    let quadric = state.quadrics.items[(usize)p].plus(state.quadrics.items[(usize)q])
    let place = target_place(state, p, q, quadric)
    # Ties (a flat region prices every collapse 0) go to the shortest edge,
    # so the collapses spread evenly instead of piling on one point.
    let span = state.places.items[(usize)q].subtract(state.places.items[(usize)p])
    let length = span.dot(span)
    try heap_push(&state.heap, Candidate(quadric.at(place) + 0.000001 * length * length, p, q, state.stamps.items[(usize)p], state.stamps.items[(usize)q]))

## Where `p` and `q` meet: a locked end's place, else the quadric's best.
func target_place(state: const Collapse*, p: i32, q: i32, quadric: Quadric) -> Vector3:
    if state.locked.items[(usize)p] != 0: return state.places.items[(usize)p]
    if state.locked.items[(usize)q] != 0: return state.places.items[(usize)q]
    return cheapest(quadric, state.places.items[(usize)p], state.places.items[(usize)q])

## Collapse edge `u`–`v` if it is still valid: `v` merges into `u`, which
## moves to the pair's best place; the edges round `u` are priced again.
func collapse_one(state: Collapse*, u_in: i32, v_in: i32) -> !:
    # The locked end survives.
    var u = u_in
    var v = v_in
    if state.locked.items[(usize)v] != 0:
        u = v_in
        v = u_in
    let shared = triangles_on(state, u, v)
    if shared == 0: return
    let quadric = state.quadrics.items[(usize)u].plus(state.quadrics.items[(usize)v])
    let place = target_place(state, u, v, quadric)
    # The link condition: common neighbors only the triangles' third points.
    state.mark += 2
    mark_neighbors(state, u)
    var common: usize = 0
    for t in state.triangles_of(v):
        if state.alive.items[(usize)t] == 0: continue
        for k in 0..<(usize)3:
            let corner = state.corners.items[(usize)t * 3 + k]
            if corner == u or corner == v or state.marks.items[(usize)corner] != state.mark: continue
            state.marks.items[(usize)corner] = state.mark + 1
            common += 1
    if common != shared: return
    # No triangle round either end may turn over.
    if flips(state, u, v, place) or flips(state, v, u, place): return
    # Merge: the joined list as a new slice; the triangles on the edge die,
    # v's others now name u.
    state.merged_into.items[(usize)v] = u
    state.places.items[(usize)u] = place
    state.quadrics.items[(usize)u] = quadric
    state.stamps.items[(usize)u] += 1
    let start = state.pool.count
    let ends: i32[2] = [u, v]
    for end in ends:
        let first = (usize)state.list_start.items[(usize)end]
        let count = (usize)state.list_count.items[(usize)end]
        for slot in first..<first + count:
            let t = (usize)state.pool.items[slot]
            if state.alive.items[t] == 0: continue
            if state.has(t, u) and state.has(t, v):
                state.alive.items[t] = 0
                state.live_triangles -= 1
                continue
            for k in 0..<(usize)3:
                if state.corners.items[t * 3 + k] == v: state.corners.items[t * 3 + k] = u
            try state.pool.push((i32)t)
    state.list_start.items[(usize)u] = (i32)start
    state.list_count.items[(usize)u] = (i32)(state.pool.count - start)
    state.list_count.items[(usize)v] = 0
    # Price the edges round u again (u's new version voids its old prices;
    # its neighbors' other edges stand).
    state.mark += 2
    mark_neighbors(state, u)
    for t in state.triangles_of(u):
        for k in 0..<(usize)3:
            let corner = state.corners.items[(usize)t * 3 + k]
            if corner == u or state.marks.items[(usize)corner] != state.mark: continue
            state.marks.items[(usize)corner] = state.mark + 1
            try price(state, u, corner)

## Mark the points sharing a live triangle with `point` with the current
## mark.
func mark_neighbors(state: Collapse*, point: i32):
    for t in state.triangles_of(point):
        if state.alive.items[(usize)t] == 0: continue
        for k in 0..<(usize)3:
            let corner = state.corners.items[(usize)t * 3 + k]
            if corner != point: state.marks.items[(usize)corner] = state.mark

## Whether moving `moving` to `place` turns over (or flattens) a live
## triangle of it that does not have `other`.
func flips(state: const Collapse*, moving: i32, other: i32, place: Vector3) -> bool:
    for t in state.triangles_of(moving):
        let at = (usize)t
        if state.alive.items[at] == 0 or state.has(at, other): continue
        var ids: i32[3] = [state.corners.items[at * 3], state.corners.items[at * 3 + 1], state.corners.items[at * 3 + 2]]
        let a = state.places.items[(usize)ids[0]]
        let b = state.places.items[(usize)ids[1]]
        let c = state.places.items[(usize)ids[2]]
        let before = b.subtract(a).cross(c.subtract(a))
        var moved: Vector3[3] = [a, b, c]
        for k in 0..<(usize)3:
            if ids[k] == moving: moved[k] = place
        let after = moved[1].subtract(moved[0]).cross(moved[2].subtract(moved[0]))
        if after.length() <= 0.0 or after.dot(before) <= 0.2 * before.length() * after.length(): return true
    return false

## The decimated mesh: faces outside the group as they were, then the live
## triangles; points at their merged places, unused ones gone.
func collapse_output(mesh: const Mesh*, topology: const Topology*, group: Bits, state: const Collapse*, output: VerbOutput*) -> !:
    var builder = &output.builder
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    output.built = true
    for point in 0..<state.globals.count:
        if state.merged_into.items[point] < 0 and state.stamps.items[point] > 0: builder.move_point(state.globals.items[point], state.places.items[point])
    var run: usize = 0
    for face in 0..<topology.faces():
        if not group.get(face): continue
        try builder.copy_faces(mesh, run, face)
        run = face + 1
    try builder.copy_faces(mesh, run, topology.faces())
    let first = builder.face_count()
    for t in 0..<state.alive.count:
        if state.alive.items[t] == 0: continue
        try builder.face(topology.corner_faces[(usize)state.sources.items[t * 3]])
        for k in 0..<(usize)3: try builder.corner(state.globals.items[(usize)state.corners.items[t * 3 + k]], state.sources.items[t * 3 + k])
        try builder.end_face()
    try builder.drop_unused_points()
    output.selection = try BitsBuilder.zeros(builder.face_count())
    output.selection.set_range(first, builder.face_count())
    output.selection_domain = Domain.face

## A binary min-heap of candidates by cost.
func heap_push(heap: Growing[Candidate]*, item: Candidate) -> !:
    try heap.push(item)
    var at = heap.count - 1
    while at > 0:
        let parent = (at - 1) // 2
        if heap.items[parent].cost <= heap.items[at].cost: break
        let swap = heap.items[parent]
        heap.items[parent] = heap.items[at]
        heap.items[at] = swap
        at = parent

func heap_pop(heap: Growing[Candidate]*) -> Candidate:
    let top = heap.items[0]
    heap.count -= 1
    if heap.count == 0: return top
    heap.items[0] = heap.items[heap.count]
    var at: usize = 0
    while true:
        let left = at * 2 + 1
        let right = left + 1
        var smallest = at
        if left < heap.count and heap.items[left].cost < heap.items[smallest].cost: smallest = left
        if right < heap.count and heap.items[right].cost < heap.items[smallest].cost: smallest = right
        if smallest == at: break
        let swap = heap.items[smallest]
        heap.items[smallest] = heap.items[at]
        heap.items[at] = swap
        at = smallest
    return top