Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.9

0.7.9 / src / geometries / topology / topology_cache.lucb

## What connectivity alone determines, computed on first use and shared by
## every mesh with the same face offsets and corner points: snapshots, worker
## transfers and position edits. Each item is published once under the lock
## and immutable after, so readers on any thread need no lock once it is
## ready. A mesh that never asks for edges never pays for them.
import memory
import sync
from luce_std import parallel
from core.shared import Column
from geometries.topology.topology_hash import topology_hash

pub struct TopologyCache:
    pub var users: @usize = 1
    var lock: sync.Mutex
    var faces_ready: @u32
    var corner_faces: Column[i32]
    var edges_ready: @u32
    var edge_points: Column[i32]
    var corner_edges: Column[i32]
    var incidence_ready: @u32
    var point_face_offsets: Column[i32]
    var point_faces: Column[i32]
    var hash_ready: @u32
    var hash: u64
    ## Each edge's corners (one or two on a manifold), and each point's edges,
    ## as offsets into one array: selection conversion, loops and rings.
    var edge_corners_ready: @u32
    var edge_corner_offsets: Column[i32]
    var edge_corner_list: Column[i32]
    var point_edges_ready: @u32
    var point_edge_offsets: Column[i32]
    var point_edge_list: Column[i32]
    ## Every face's part (the faces joined to it through shared points),
    ## parts numbered by their lowest faces, and each part's face count:
    ## Boolean's and Separate's pieces when a pick holds whole parts.
    var parts_ready: @u32
    var face_parts: Column[i32]
    var part_sizes: Column[i32]
    ## What another module derives from this connectivity (subdivision's
    ## plans and display meshes), made by it on first use under its own
    ## lock and disposed with the cache.
    var extension_lock: sync.Mutex
    var extension: void*? = none
    var extension_dispose: func(void*) -> unit = ignore_extension

    ## The face of every corner.
    pub func faces(offsets: const i32[], corners: usize) -> const i32[]!:
        if self.faces_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.faces_ready.load(.acquire) == 0:
                var column = try Column[i32].allocate(corners)
                var work = FaceWork(offsets, column.span())
                try parallel.for_each_range(offsets.length - 1, 4096, (void*)&work, fill_faces)
                self.corner_faces = column
                self.faces_ready.store(1, .release)
        return self.corner_faces.view()

    ## Two points per edge, and the edge of every corner (its edge to the next
    ## corner). Edges are numbered by their first corner, so ids depend on
    ## connectivity alone.
    pub func edges(offsets: const i32[], corners: const i32[], points: usize) -> (const i32[], const i32[])!:
        if self.edges_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.edges_ready.load(.acquire) == 0:
                try self.build_edges(offsets, corners, points)
                self.edges_ready.store(1, .release)
        return (self.edge_points.view(), self.corner_edges.view())

    ## For every point, the faces using it (a face once per corner at it), as
    ## offsets into one array.
    pub func incidence(offsets: const i32[], corners: const i32[], points: usize) -> (const i32[], const i32[])!:
        if self.incidence_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.incidence_ready.load(.acquire) == 0:
                try self.build_incidence(offsets, corners, points)
                self.incidence_ready.store(1, .release)
        return (self.point_face_offsets.view(), self.point_faces.view())

    ## For every edge, the corners whose outgoing edge it is. Needs `edges`.
    pub func edge_corners(corner_edges: const i32[], edges: usize) -> (const i32[], const i32[])!:
        if self.edge_corners_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.edge_corners_ready.load(.acquire) == 0:
                try bucketed(corner_edges, edges, &self.edge_corner_offsets, &self.edge_corner_list, 1)
                self.edge_corners_ready.store(1, .release)
        return (self.edge_corner_offsets.view(), self.edge_corner_list.view())

    ## For every point, the edges ending at it. Needs `edges`.
    pub func point_edges(edge_points: const i32[], points: usize) -> (const i32[], const i32[])!:
        if self.point_edges_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.point_edges_ready.load(.acquire) == 0:
                try bucketed(edge_points, points, &self.point_edge_offsets, &self.point_edge_list, 2)
                self.point_edges_ready.store(1, .release)
        return (self.point_edge_offsets.view(), self.point_edge_list.view())

    ## Each face's part and each part's face count (see `face_parts`).
    pub func parts(offsets: const i32[], corners: const i32[], points: usize) -> (const i32[], const i32[])!:
        if self.parts_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.parts_ready.load(.acquire) == 0:
                try self.build_parts(offsets, corners, points)
                self.parts_ready.store(1, .release)
        return (self.face_parts.view(), self.part_sizes.view())

    pub func connectivity_hash(offsets: const i32[], corners: const i32[], points: usize) -> u64:
        if self.hash_ready.load(.acquire) == 0:
            self.lock.lock()
            defer self.lock.unlock()
            if self.hash_ready.load(.acquire) == 0:
                self.hash = topology_hash(points, offsets, corners)
                self.hash_ready.store(1, .release)
        return self.hash

    ## Group each corner's edge by its low point (a counting sort in corner
    ## order), find each group's first corner per high point in parallel, and
    ## number the first corners in corner order.
    func build_edges(offsets: const i32[], corners: const i32[], points: usize) -> !:
        let count = corners.length
        let high = try new i32[count] --- in memory.heap
        defer free(high) in memory.heap
        let low = try new i32[count] --- in memory.heap
        defer free(low) in memory.heap
        var ends = EndWork(offsets, corners, low, high)
        try parallel.for_each_range(offsets.length - 1, 4096, (void*)&ends, fill_ends)
        let starts = try new i32[points + 1] --- in memory.heap
        defer free(starts) in memory.heap
        for at in 0..<starts.length: starts[at] = 0
        for corner in 0..<count: starts[(usize)low[corner] + 1] += 1
        for point in 0..<points: starts[point + 1] += starts[point]
        let bucket = try new i32[count] --- in memory.heap
        defer free(bucket) in memory.heap
        let cursor = try new i32[points] --- in memory.heap
        defer free(cursor) in memory.heap
        memory.copy(cursor, starts[..<points], points)
        for corner in 0..<count:
            let point = (usize)low[corner]
            bucket[(usize)cursor[point]] = (i32)corner
            cursor[point] += 1
        # Reuse `low` for each corner's first corner of its edge.
        var groups = GroupWork(starts, bucket, high, low)
        try parallel.for_each_range(points, 4096, (void*)&groups, first_corners)
        let ids = try new i32[count] --- in memory.heap
        defer free(ids) in memory.heap
        var next: i32 = 0
        for corner in 0..<count:
            if low[corner] == (i32)corner:
                ids[corner] = next
                next += 1
        var edge_points = try Column[i32].allocate((usize)next * 2)
        errdefer edge_points.release()
        var corner_edges = try Column[i32].allocate(count)
        var fill = EdgeWork(offsets, corners, low, ids, edge_points.span(), corner_edges.span())
        try parallel.for_each_range(offsets.length - 1, 4096, (void*)&fill, fill_edges)
        self.edge_points = edge_points
        self.corner_edges = corner_edges

    func build_incidence(offsets: const i32[], corners: const i32[], points: usize) -> !:
        var starts = try Column[i32].allocate(points + 1)
        errdefer starts.release()
        let first = starts.span()
        for at in 0..<first.length: first[at] = 0
        for corner in corners: first[(usize)corner + 1] += 1
        for point in 0..<points: first[point + 1] += first[point]
        var faces = try Column[i32].allocate(corners.length)
        errdefer faces.release()
        let cursor = try new i32[points] --- in memory.heap
        defer free(cursor) in memory.heap
        memory.copy(cursor, first[..<points], points)
        let output = faces.span()
        for face in 0..<offsets.length - 1:
            for corner in (usize)offsets[face]..<(usize)offsets[face + 1]:
                let point = (usize)corners[corner]
                output[(usize)cursor[point]] = (i32)face
                cursor[point] += 1
        self.point_face_offsets = starts
        self.point_faces = faces

    ## Union the faces at each point (union by lowest face, paths halved),
    ## then number the roots in face order.
    func build_parts(offsets: const i32[], corners: const i32[], points: usize) -> !:
        let faces = offsets.length - 1
        var parts = try Column[i32].allocate(faces)
        errdefer parts.release()
        let parent = parts.span()
        for face in 0..<faces: parent[face] = (i32)face
        let first = try new i32[points] --- in memory.heap
        defer free(first) in memory.heap
        for at in 0..<points: first[at] = -1
        for face in 0..<faces:
            for corner in (usize)offsets[face]..<(usize)offsets[face + 1]:
                let point = (usize)corners[corner]
                if first[point] < 0:
                    first[point] = (i32)face
                    continue
                let a = part_root(parent, first[point])
                let b = part_root(parent, (i32)face)
                if a != b: parent[(usize)(a if a > b else b)] = a if a < b else b
        # A face's parent is a lower face (a root is its own), so one pass in
        # face order numbers each root and gives every other face its parent's
        # number, already written; numbers are stored as -1 - number until
        # the pass ends so they cannot be taken for face indices.
        var count: i32 = 0
        for face in 0..<faces:
            let up = parent[face]
            if up == (i32)face:
                parent[face] = -1 - count
                count += 1
            else:
                parent[face] = parent[(usize)up]
        var sizes = try Column[i32].allocate((usize)count)
        let size = sizes.span()
        for at in 0..<size.length: size[at] = 0
        for face in 0..<faces:
            parent[face] = -1 - parent[face]
            size[(usize)parent[face]] += 1
        self.face_parts = parts
        self.part_sizes = sizes

    ## The extension, made by `make` on first use; `dispose` frees it with
    ## the cache. One module owns the slot.
    pub func extension_of(dispose: func(void*) -> unit, make: func() -> void*!) -> void*!:
        self.extension_lock.lock()
        defer self.extension_lock.unlock()
        if let made = self.extension: return made
        let made = try make()
        self.extension = made
        self.extension_dispose = dispose
        return made

    ## Called by the last owner, after every reader.
    pub func close():
        if let made = self.extension:
            let dispose = self.extension_dispose
            dispose(made)
            self.extension = none
        self.corner_faces.release()
        self.edge_points.release()
        self.corner_edges.release()
        self.point_face_offsets.release()
        self.point_faces.release()
        self.edge_corner_offsets.release()
        self.edge_corner_list.release()
        self.point_edge_offsets.release()
        self.point_edge_list.release()
        self.face_parts.release()
        self.part_sizes.release()

## The root of `face` (halving the path on the way).
func part_root(parent: i32[], face: i32) -> i32:
    var at = face
    while parent[(usize)at] != at:
        let up = parent[(usize)parent[(usize)at]]
        parent[(usize)at] = up
        at = up
    return at

func ignore_extension(context: void*):
    _ = context

## A counting sort: element i of `keys` goes to bucket keys[i], and the
## bucket lists `i / per` (so with per = 2, edge endpoints list their edge).
func bucketed(keys: const i32[], buckets: usize, offsets: Column[i32]*, list: Column[i32]*, per: usize) -> !:
    var starts = try Column[i32].allocate(buckets + 1)
    errdefer starts.release()
    let first = starts.span()
    for at in 0..<first.length: first[at] = 0
    for key in keys: first[(usize)key + 1] += 1
    for at in 0..<buckets: first[at + 1] += first[at]
    var items = try Column[i32].allocate(keys.length)
    errdefer items.release()
    let cursor = try new i32[buckets] --- in memory.heap
    defer free(cursor) in memory.heap
    memory.copy(cursor, first[..<buckets], buckets)
    let output = items.span()
    for at in 0..<keys.length:
        let key = (usize)keys[at]
        output[(usize)cursor[key]] = (i32)(at // per)
        cursor[key] += 1
    *offsets = starts
    *list = items

struct FaceWork:
    let offsets: const i32[]
    let faces: i32[]

func fill_faces(context: void*, first: usize, end: usize, worker: usize):
    let work = (FaceWork*)context
    for face in first..<end:
        for corner in (usize)work.offsets[face]..<(usize)work.offsets[face + 1]:
            work.faces[corner] = (i32)face

struct EndWork:
    let offsets: const i32[]
    let corners: const i32[]
    let low: i32[]
    let high: i32[]

func fill_ends(context: void*, first: usize, end: usize, worker: usize):
    let work = (EndWork*)context
    for face in first..<end:
        let start = (usize)work.offsets[face]
        let stop = (usize)work.offsets[face + 1]
        for corner in start..<stop:
            let a = work.corners[corner]
            let b = work.corners[corner + 1 if corner + 1 < stop else start]
            work.low[corner] = a if a < b else b
            work.high[corner] = b if a < b else a

struct GroupWork:
    let starts: const i32[]
    let bucket: const i32[]
    let high: const i32[]
    let first: i32[]

## Within one low point's corners (in corner order), a corner's edge starts
## at the earliest corner with the same high point.
func first_corners(context: void*, first: usize, end: usize, worker: usize):
    let work = (GroupWork*)context
    for point in first..<end:
        let start = (usize)work.starts[point]
        let stop = (usize)work.starts[point + 1]
        for at in start..<stop:
            let corner = (usize)work.bucket[at]
            var owner = corner
            for earlier in start..<at:
                let other = (usize)work.bucket[earlier]
                if work.high[other] == work.high[corner]:
                    owner = other
                    break
            work.first[corner] = (i32)owner

struct EdgeWork:
    let offsets: const i32[]
    let corners: const i32[]
    let first: const i32[]
    let ids: const i32[]
    let edge_points: i32[]
    let corner_edges: i32[]

func fill_edges(context: void*, first: usize, end: usize, worker: usize):
    let work = (EdgeWork*)context
    for face in first..<end:
        let start = (usize)work.offsets[face]
        let stop = (usize)work.offsets[face + 1]
        for corner in start..<stop:
            let owner = (usize)work.first[corner]
            let edge = work.ids[owner]
            work.corner_edges[corner] = edge
            if owner == corner:
                let a = work.corners[corner]
                let b = work.corners[corner + 1 if corner + 1 < stop else start]
                work.edge_points[(usize)edge * 2] = a if a < b else b
                work.edge_points[(usize)edge * 2 + 1] = b if a < b else a