Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / booleans / merge.lucb

# mark: The cut ================================================================================

## A constructed point's name and how it is built.
struct Named:
    let key: PointKey
    let recipe: Recipe

## A point on a triangle, by number.
struct OnTriangle:
    let triangle: u32
    let point: u32

## A segment on a triangle, by point numbers (the lower first), with its
## source (see SegmentRecord).
struct CutSegment:
    let triangle: u32
    let first: u32
    let second: u32
    let source: i32
    let opposite: i32

    ## The coplanar triangle whose edge this is, or -1.
    func cover() -> i32:
        return self.source if self.opposite >= 0 else -1

## The cut gathered from every pair: each cut point numbered once (input
## points keep their numbers, constructed ones follow in name order), and
## per cut triangle its points, segments and coplanar neighbors.
struct Cut:
    var named: Growing[Named]
    ## The cut triangles in order, and where each one's lists start (one
    ## more entry than triangles).
    var triangles: Growing[u32]
    var point_starts: Growing[u32]
    var points: Growing[u32]
    var segment_starts: Growing[u32]
    var segments: Growing[CutSegment]
    var cover_starts: Growing[u32]
    var covers: Growing[u32]
    ## Per operand triangle: its place in `triangles`, or -1.
    var slot: Growing[i32]
    ## The records the lists were made from, sorted.
    var on_records: Growing[OnTriangle]
    var segment_records: Growing[CutSegment]
    var cover_records: Growing[OnTriangle]

    func init():
        self.named = Growing[Named]()
        self.triangles = Growing[u32]()
        self.point_starts = Growing[u32]()
        self.points = Growing[u32]()
        self.segment_starts = Growing[u32]()
        self.segments = Growing[CutSegment]()
        self.cover_starts = Growing[u32]()
        self.covers = Growing[u32]()
        self.slot = Growing[i32]()
        self.on_records = Growing[OnTriangle]()
        self.segment_records = Growing[CutSegment]()
        self.cover_records = Growing[OnTriangle]()

    func close():
        self.named.close()
        self.triangles.close()
        self.point_starts.close()
        self.points.close()
        self.segment_starts.close()
        self.segments.close()
        self.cover_starts.close()
        self.covers.close()
        self.slot.close()
        self.on_records.close()
        self.segment_records.close()
        self.cover_records.close()

    ## How many points there are, input and constructed.
    func point_total(inputs: usize) -> usize:
        return inputs + self.named.count

    ## The number of the point named `key`.
    func id_of(key: PointKey, inputs: usize) -> u32:
        if key.kind == input_key: return (u32)key.v[0]
        var low: usize = 0
        var high = self.named.count
        while low < high:
            let middle = (low + high) // 2
            if self.named.items[middle].key.less(key): low = middle + 1
            else: high = middle
        return (u32)(inputs + low)

    ## Gather the pairs' records.
    func gather(operands: const Operands*, records: const PairOut*) -> !:
        let inputs = operands.points.count
        # Constructed points: one per name, built by the least recipe.
        for record in records.points.view():
            if record.key.kind != input_key: try self.named.push(Named(record.key, record.recipe))
        sort.by(self.named.items[..<self.named.count], named_less)
        var kept: usize = 0
        for at in 0..<self.named.count:
            if kept > 0 and self.named.items[kept - 1].key.same(self.named.items[at].key): continue
            self.named.items[kept] = self.named.items[at]
            kept += 1
        self.named.count = kept
        # Each triangle's points, segments and coplanar neighbors, sorted.
        for record in records.points.view():
            try self.on_records.push(OnTriangle((u32)record.triangle, self.id_of(record.key, inputs)))
        for record in records.segments.view():
            let first = self.id_of(record.first, inputs)
            let second = self.id_of(record.second, inputs)
            try self.segment_records.push(CutSegment((u32)record.triangle, first if first < second else second, second if first < second else first, record.source, record.opposite))
        for record in records.covers.view(): try self.cover_records.push(OnTriangle((u32)record.triangle, (u32)record.other))
        sort.by(self.on_records.items[..<self.on_records.count], on_less)
        sort.by(self.segment_records.items[..<self.segment_records.count], segment_less)
        sort.by(self.cover_records.items[..<self.cover_records.count], on_less)
        try self.slot.fill(operands.triangle_count(), -1)
        for record in self.on_records.view(): self.slot.items[(usize)record.triangle] = 0
        for record in self.segment_records.view(): self.slot.items[(usize)record.triangle] = 0
        for record in self.cover_records.view(): self.slot.items[(usize)record.triangle] = 0
        for t in 0..<operands.triangle_count():
            if self.slot.items[t] < 0: continue
            self.slot.items[t] = (i32)self.triangles.count
            try self.triangles.push((u32)t)
        try self.fill_lists()

    ## Each cut triangle's ranges of points, segments and covers, without
    ## repeats.
    func fill_lists() -> !:
        let on = self.on_records.view()
        let segments = self.segment_records.view()
        let covers = self.cover_records.view()
        self.point_starts.clear()
        self.points.clear()
        self.segment_starts.clear()
        self.segments.clear()
        self.cover_starts.clear()
        self.covers.clear()
        var p: usize = 0
        var s: usize = 0
        var c: usize = 0
        for slot in 0..<self.triangles.count:
            let t = self.triangles.items[slot]
            try self.point_starts.push((u32)self.points.count)
            while p < on.length and on[p].triangle == t:
                if self.points.count == (usize)self.point_starts.items[slot] or self.points.items[self.points.count - 1] != on[p].point: try self.points.push(on[p].point)
                p += 1
            try self.segment_starts.push((u32)self.segments.count)
            while s < segments.length and segments[s].triangle == t:
                if self.segments.count == (usize)self.segment_starts.items[slot] or not same_segment(self.segments.items[self.segments.count - 1], segments[s]): try self.segments.push(segments[s])
                s += 1
            try self.cover_starts.push((u32)self.covers.count)
            while c < covers.length and covers[c].triangle == t:
                if self.covers.count == (usize)self.cover_starts.items[slot] or self.covers.items[self.covers.count - 1] != covers[c].point: try self.covers.push(covers[c].point)
                c += 1
        try self.point_starts.push((u32)self.points.count)
        try self.segment_starts.push((u32)self.segments.count)
        try self.cover_starts.push((u32)self.covers.count)

    ## Store every point the triangulations read: the cut triangles' corners,
    ## their points, and the constructed points built from their recipes.
    func store_points(operands: const Operands*, table: PointTable*, arena: Arena*) -> !:
        let inputs = operands.points.count
        try table.size(self.point_total(inputs))
        for t in self.triangles.view():
            for k in 0..<(usize)3: try table.add_input(operands.vertex((usize)t, k))
        for id in self.points.view():
            if (usize)id < inputs: try table.add_input((usize)id)
        let points = operands.points.view()
        for at in 0..<self.named.count:
            let recipe = self.named.items[at].recipe
            let mark = arena.mark()
            defer arena.reset(mark)
            var made: Homogeneous
            if recipe.kind == three_planes_recipe:
                made = try three_planes_coordinates(arena, operands, (usize)recipe.p, (usize)recipe.q, (usize)recipe.a)
            elif recipe.kind == crossing_recipe:
                made = try crossing_coordinates(arena, points[(usize)recipe.p], points[(usize)recipe.q], points[(usize)recipe.a], points[(usize)recipe.b], points[(usize)recipe.c])
            else:
                let along = Projection.along((usize)recipe.c)
                made = try meeting_coordinates(arena, points[(usize)recipe.p], points[(usize)recipe.q], points[(usize)recipe.a], points[(usize)recipe.b], along.u, along.v)
            try table.add_constructed(inputs + at, made.x, made.y, made.z, made.w)

## Points of the cut at one place under different names (a degenerate
## meeting named one way in one triangle and another way in the next, as
## three planes meeting on an edge) become one: the lowest number. Found
## by sorting along X within the points' error bounds and comparing the
## exact coordinates. The lists are made again when any merge.
extend Cut:
    func merge_coincident(operands: const Operands*, table: const PointTable*, arena: Arena*) -> !:
        let total = self.point_total(operands.points.count)
        var ids = Growing[u32]()
        defer ids.close()
        for record in self.on_records.view(): try ids.push(record.point)
        sort.sort(ids.items[..<ids.count])
        var kept: usize = 0
        for at in 0..<ids.count:
            if kept > 0 and ids.items[kept - 1] == ids.items[at]: continue
            ids.items[kept] = ids.items[at]
            kept += 1
        ids.count = kept
        var order = Growing[PlacedId]()
        defer order.close()
        for id in ids.view(): try order.push(PlacedId(table.near_of((usize)id).x, id))
        sort.by(order.items[..<order.count], placed_less)
        var canonical = Growing[u32]()
        defer canonical.close()
        try canonical.reserve(total)
        for at in 0..<total: canonical.items[at] = (u32)at
        canonical.count = total
        var merged = false
        var stores: f64[8] = ---
        for at in 0..<order.count:
            let one = (usize)order.items[at].id
            let p = stored_or_input(table, one, stores[0..<4])
            for next in at + 1..<order.count:
                let two = (usize)order.items[next].id
                let q = stored_or_input(table, two, stores[4..<8])
                let reach = (p.slack + q.slack) * 2.0
                if q.near.x - p.near.x > reach: break
                if math.abs(q.near.y - p.near.y) > reach or math.abs(q.near.z - p.near.z) > reach: continue
                let mark = arena.mark()
                defer arena.reset(mark)
                if try compare_h(arena, &p, &q, 0) != 0 or try compare_h(arena, &p, &q, 1) != 0 or try compare_h(arena, &p, &q, 2) != 0: continue
                # One place: the higher number follows the lower.
                let x = root_of(canonical.items[..<total], one)
                let y = root_of(canonical.items[..<total], two)
                if x < y: canonical.items[y] = (u32)x
                elif y < x: canonical.items[x] = (u32)y
                merged = true
        if not merged: return
        let map = canonical.items[..<total]
        for at in 0..<self.on_records.count:
            let record = self.on_records.items[at]
            self.on_records.items[at] = OnTriangle(record.triangle, (u32)root_of(map, (usize)record.point))
        var segments: usize = 0
        for at in 0..<self.segment_records.count:
            let record = self.segment_records.items[at]
            let first = (u32)root_of(map, (usize)record.first)
            let second = (u32)root_of(map, (usize)record.second)
            if first == second: continue
            self.segment_records.items[segments] = CutSegment(record.triangle, first if first < second else second, second if first < second else first, record.source, record.opposite)
            segments += 1
        self.segment_records.count = segments
        sort.by(self.on_records.items[..<self.on_records.count], on_less)
        sort.by(self.segment_records.items[..<self.segment_records.count], segment_less)
        try self.fill_lists()

## A point number with its X, for the sweep.
struct PlacedId:
    let x: f64
    let id: u32

func placed_less(a: PlacedId, b: PlacedId) -> bool:
    if a.x != b.x: return a.x < b.x
    return a.id < b.id

## The lowest number of the points merged with `at`.
func root_of(map: u32[], at: usize) -> usize:
    var x = at
    while (usize)map[x] != x: x = (usize)map[x]
    return x

func same_segment(a: CutSegment, b: CutSegment) -> bool:
    return a.triangle == b.triangle and a.first == b.first and a.second == b.second and a.source == b.source and a.opposite == b.opposite

func named_less(a: Named, b: Named) -> bool:
    if not a.key.same(b.key): return a.key.less(b.key)
    return a.recipe.less(b.recipe)

func on_less(a: OnTriangle, b: OnTriangle) -> bool:
    if a.triangle != b.triangle: return a.triangle < b.triangle
    return a.point < b.point

func segment_less(a: CutSegment, b: CutSegment) -> bool:
    if a.triangle != b.triangle: return a.triangle < b.triangle
    if a.first != b.first: return a.first < b.first
    if a.second != b.second: return a.second < b.second
    if a.source != b.source: return a.source < b.source
    return a.opposite < b.opposite