Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / booleans / boolean.lucb

# mark: Running a boolean ======================================================================

## The operations, as the verb's menu numbers them.
pub let boolean_union: i64 = 0
pub let boolean_subtract: i64 = 1
pub let boolean_intersect: i64 = 2

## Combine faces `a` and `b` of `mesh` (disjoint; each a closed surface)
## by `operation`: what the result makes of the operands' faces, into
## `out`. Other faces are the caller's to keep.
##
## The fast way cuts the operands against each other and their own faces
## only where folds reach the cut. The kept faces are then checked to
## close up; when a fold elsewhere misled a patch they do not, and every
## crossing of each operand with itself is cut too. If even that does not
## close (an operand overlapping itself in its own plane), it is an error.
pub func combine(mesh: const Mesh*, a: Bits, b: Bits, operation: i64, out: Combined*) -> !:
    if operation < 0 or operation > 2: error(errors.invalid, "Boolean's operation is 0 (Union), 1 (Subtract) or 2 (Intersect)")
    var operands = Operands(mesh, try Topology.of(mesh))
    defer operands.close()
    try operands.gather(a, b)
    try operands.check_closed()
    var tree_a = BoxTree()
    defer tree_a.close()
    var tree_b = BoxTree()
    defer tree_b.close()
    var trees = TreeWork(&operands, &tree_a, &tree_b)
    try parallel.for_each(2, (void*)&trees, build_tree)
    let both: BoxTree[2] = [tree_a, tree_b]
    var arrangement = Arrangement()
    defer arrangement.close()
    try arrangement.build(&operands, both[..<2], operation, false)
    if not try arrangement.closes(&operands):
        arrangement.close()
        arrangement = Arrangement()
        try arrangement.build(&operands, both[..<2], operation, true)
        if not try arrangement.closes(&operands): error(errors.invalid, "Boolean: a piece overlaps itself in its own plane, so the result would not close; separate or clean it first")
    try assemble(&operands, &arrangement.cut, &arrangement.table, &arrangement.pieces, &arrangement.classes, out)

## The cut operands and what becomes of every face and piece.
struct Arrangement:
    var cut: Cut
    var table: PointTable
    var made: Growing[Pieces]
    var pieces: CutFaces
    var classes: Classes

    func init():
        self.cut = Cut()
        self.table = PointTable(no_points[..<0])
        self.made = Growing[Pieces]()
        self.pieces = CutFaces()
        self.classes = Classes()

    func close():
        self.cut.close()
        self.table.close()
        for at in 0..<self.made.count: self.made.items[at].close()
        self.made.close()
        self.pieces.close()
        self.classes.close()

    ## Cut, triangulate and classify; with `full`, every triangle is cut
    ## against its own operand, not only those the folds lead to.
    func build(operands: const Operands*, trees: const BoxTree[], operation: i64, full: bool) -> !:
        var records = PairOut()
        defer records.close()
        try cut_all_pairs(operands, &trees[1], &records)
        try flat_records(operands, &records)
        try cut_own_pairs(operands, &trees[0], &trees[1], &records, full)
        var arena = Arena()
        defer arena.close()
        self.table = PointTable(operands.points.view())
        try self.cut.gather(operands, &records)
        try self.cut.store_points(operands, &self.table, &arena)
        # Cuts crossing inside faces (an earlier cut's rounding): their
        # points join the records and the cut is gathered again.
        if try find_crossings(operands, &self.cut, &self.table, &records):
            self.cut.close()
            self.cut = Cut()
            self.table.close()
            self.table = PointTable(operands.points.view())
            try self.cut.gather(operands, &records)
            try self.cut.store_points(operands, &self.table, &arena)
        records.close()
        try self.cut.merge_coincident(operands, &self.table, &arena)
        let slots = self.cut.triangles.count
        try self.made.reserve(slots)
        for at in 0..<slots: self.made.items[at] = Pieces()
        self.made.count = slots
        try triangulate_all(operands, &self.cut, &self.table, self.made.items[..<slots])
        try self.pieces.gather(operands, &self.cut, self.made.view())
        try self.classes.run(operands, &self.table, &self.pieces, trees, operation)

    ## Whether the kept faces close up: every edge of a kept piece, and
    ## every edge of a kept whole face that a cut face or more than one
    ## other face shares, used as often one way as the other.
    func closes(operands: const Operands*) -> bool!:
        let topology = &operands.topology
        let faces = topology.faces()
        let pieces = &self.pieces
        let fate = self.classes.fate.view()
        var halves = Growing[u64]()
        defer halves.close()
        for piece in 0..<pieces.count():
            let kept = fate[faces + piece]
            if kept == unit_dropped: continue
            for k in 0..<(usize)3:
                let x = (u64)pieces.corners.items[piece * 3 + k]
                let y = (u64)pieces.corners.items[piece * 3 + (k + 1) % 3]
                try halves.push((y << 32) | x if kept == unit_reversed else (x << 32) | y)
        for face in 0..<faces:
            let kept = fate[face]
            if operands.face_operand.items[face] == outside_operands or pieces.cut_face(face) or kept == unit_dropped: continue
            let first = (usize)topology.offsets[face]
            let size = (usize)topology.offsets[face + 1] - first
            for k in 0..<size:
                let edge = (usize)topology.corner_edges[first + k]
                let from_at = (usize)topology.edge_corner_offsets[edge]
                let to_at = (usize)topology.edge_corner_offsets[edge + 1]
                var watched = to_at - from_at != 2
                for at in from_at..<to_at:
                    if pieces.cut_face((usize)topology.corner_faces[(usize)topology.edge_corners[at]]): watched = true
                if not watched: continue
                let x = (u64)operands.same.items[(usize)topology.corners[first + k]]
                let y = (u64)operands.same.items[(usize)topology.corners[first + (k + 1) % size]]
                if x == y: continue
                try halves.push((y << 32) | x if kept == unit_reversed else (x << 32) | y)
        sort.sort(halves.items[..<halves.count])
        for half in halves.view():
            let back = ((half & 0xFFFFFFFF) << 32) | (half >> 32)
            if count_of(halves.view(), half) != count_of(halves.view(), back): return false
        return true

let no_points: Vector3[1] = [Vector3()]

## How many times sorted `words` holds `word`.
func count_of(words: const u64[], word: u64) -> usize:
    var low: usize = 0
    var high = words.length
    while low < high:
        let middle = (low + high) // 2
        if words[middle] < word: low = middle + 1
        else: high = middle
    var end = low
    while end < words.length and words[end] == word: end += 1
    return end - low

## The two operands' trees, built at once.
struct TreeWork:
    let operands: const Operands*
    var a: BoxTree*
    var b: BoxTree*

func build_tree(context: void*, index: usize, worker: usize) -> !:
    let work = (TreeWork*)context
    let operands = work.operands
    if index == 0: try work.a.build(operands, 0, operands.split)
    else: try work.b.build(operands, operands.split, operands.triangle_count())