Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / meshing / cell_display.lucb

## How a face's cells are shown: each polygon's display triangles chosen
## for shape once its mesher is done (patch_dispatch's mesh_face), and a
## grid node a hair from a trim freed (its cells joined).

## The aspect (longest side squared over twice the area) of a needle: twice
## row_stretch, the most a cell stretches along a straight direction beside
## its narrowest step (pitch.lucb). A cell whose triangles would pass it is
## shown by shape, and a grid node standing that close to a trim side
## (that side's length over it) is freed.
pub let needle_aspect: f64 = 48.0

## The face's polygons (from `first`, corners from `first_corner`) again,
## each shown as well as its corners allow:
## - a grid node a hair from a trim side (a trim grazing a row) is freed
##   first: the cells round it joined into one (free_nodes);
## - one of more than four corners (a cell a seam conformed, a trim cut or
##   a join made), or a quad whose either diagonal leaves a needle, is shown
##   by its roundest triangulation (shaped_display), whose triangles never
##   span a straight corner;
## - else one with a straight corner (a corner off the line through its
##   neighbors by no more than the single-precision display can show: a
##   side carrying a sample another cell's row ends at) is shown by ear
##   clipping, whose ears never span a straight corner: its own display
##   triangulation could pass through it, a triangle of no area once the
##   mesh is single precision. The others keep theirs.
## A clipped face's cached corner normals follow its corners.
func straighten(mesh: MeshBuilder*, first: usize, first_corner: usize, plan: GridLayout) -> !:
    var any = false
    var corner = first_corner
    for f in first..<mesh.nf:
        let n = (usize)mesh.sizes[f]
        let ids = mesh.corners[corner..<corner + n]
        if n > 4 or (n == 4 and (straight_at(mesh, corner, n) >= 0 or quad_round(mesh, ids) * needle_aspect < 1.0)) or thin_cell(mesh, ids): any = true
        corner += n
    if not any: return
    var cells = try FaceCells(mesh, first, first_corner)
    defer cells.close()
    try cells.free_nodes(mesh)
    # A clipped face's corner normals come cached with its cells
    # (clipped_patch): written again corner by corner as the cells are.
    let cached = plan.applied.length > 0 and plan.applied[0] and plan.normals.length > 0
    var uncached: f64[]
    let previous = plan.normals[0].values if cached else uncached
    var normals = Growing[f64]()
    defer normals.close()
    mesh.nf = first
    mesh.nc = first_corner
    var scratch = Growing[i64]()
    defer scratch.close()
    for f in 0..<cells.sizes.count:
        let n = (usize)cells.sizes.items[f]
        let at = cells.offsets.items[f]
        let ids = cells.corners.items[at..<at + n]
        let sources = cells.sources.items[at..<at + n]
        let joined = cells.joined.items[f]
        # A quad whose either diagonal leaves a needle (a short side a
        # trim's close samples make) is shaped as larger cells are.
        let needle = n == 4 and quad_round(mesh, ids) * needle_aspect < 1.0
        let straight = straight_at_ids(mesh, ids) if n >= 4 else -1
        try mesh.face((i64)n, cells.parents.items[f])
        for id in ids: try mesh.corner(id)
        if cached:
            for source in sources:
                for axis in 0..<(usize)3: try normals.push(previous[source * 3 + axis])
        var shown = false
        if n > 4 or (n == 4 and (joined or needle)):
            shown = (try shaped_display(mesh, ids, &scratch)) > 0.0
            if shown: try mesh.set_last_display(scratch.view())
        if straight >= 0 and not shown:
            shown = true
            straight_display(mesh, ids, &scratch) catch failure:
                if failure.code != invalid: error(failure.code, failure.message)
                shown = false
                recover ()
            if shown: try mesh.set_last_display(scratch.view())
        let display = cells.display.items[f]
        if not shown and n >= 4 and not joined and cells.triangles.items[display] >= 0:
            scratch.clear()
            for k in 0..<(n - 2) * 3: try scratch.push(cells.triangles.items[display + k])
            try mesh.set_last_display(scratch.view())
    if cached and cells.changed:
        free(plan.normals[0].values) in memory.heap
        plan.normals[0].values = try new f64[normals.count] --- in memory.heap
        memory.copy(plan.normals[0].values, normals.view(), normals.count)

## How round quad `ids`'s better diagonal leaves its triangles: the
## greater over its two diagonals of the lesser roundness of their two.
func quad_round(mesh: const MeshBuilder*, ids: const i64[]) -> f64:
    let a = mesh.points[(usize)ids[0]]
    let b = mesh.points[(usize)ids[1]]
    let c = mesh.points[(usize)ids[2]]
    let d = mesh.points[(usize)ids[3]]
    return math.max(math.min(roundness(a, b, c), roundness(a, c, d)), math.min(roundness(a, b, d), roundness(b, c, d)))

## How far `p` lies from segment `a`-`b`.
func side_distance(p: Vector3, a: Vector3, b: Vector3) -> f64:
    let ab = b.subtract(a)
    let length = ab.dot(ab)
    let t = math.clamp(p.subtract(a).dot(ab) / length, 0.0, 1.0) if length > 0.0 else 0.0
    return p.subtract(a.add(ab.multiply_scalar(t))).length()

## Whether polygon `ids` is thin: twice its area over its longest side
## squared (a triangle's roundness) under 1 / needle_aspect.
func thin_cell(mesh: const MeshBuilder*, ids: const i64[]) -> bool:
    let n = ids.length
    let origin = mesh.points[(usize)ids[0]]
    var normal = Vector3()
    var longest: f64 = 0.0
    for at in 0..<n:
        let a = mesh.points[(usize)ids[at]].subtract(origin)
        let b = mesh.points[(usize)ids[(at + 1) % n]].subtract(origin)
        normal = normal.add(a.cross(b))
        longest = math.max(longest, b.subtract(a).length())
    return normal.length() * needle_aspect < longest * longest

## A face's cells while their display is chosen: each one's corners (point
## ids), where each corner came from (its index among the face's corners,
## for cached normals), its parent, its display triangles as the mesher
## left them (`display`: an offset into `triangles`, -1 entries none) and
## whether it was joined.
struct FaceCells:
    var sizes: Growing[i64]
    var offsets: Growing[usize]
    var corners: Growing[i64]
    var sources: Growing[usize]
    var parents: Growing[i64]
    var display: Growing[usize]
    var triangles: Growing[i64]
    var joined: Growing[bool]
    var changed: bool = false

    ## The polygons of `mesh` from `first` (corners from `first_corner`).
    func init(mesh: const MeshBuilder*, first: usize, first_corner: usize) -> !:
        self.sizes = Growing[i64]()
        self.offsets = Growing[usize]()
        self.corners = Growing[i64]()
        self.sources = Growing[usize]()
        self.parents = Growing[i64]()
        self.display = Growing[usize]()
        self.triangles = Growing[i64]()
        self.joined = Growing[bool]()
        self.changed = false
        let has_display = mesh.display.length > 0
        var corner = first_corner
        for f in first..<mesh.nf:
            let n = (usize)mesh.sizes[f]
            try self.sizes.push((i64)n)
            try self.offsets.push(self.corners.count)
            try self.parents.push(mesh.face_parents[f])
            try self.joined.push(false)
            try self.display.push(self.triangles.count)
            for k in 0..<n:
                try self.corners.push(mesh.corners[corner + k])
                try self.sources.push(corner - first_corner + k)
            # Its display triangles, as indices into its own corners.
            let slot = (corner - 2 * f) * 3
            for k in 0..<(n - 2) * 3:
                let value = mesh.display[slot + k] if has_display and slot + k < mesh.display.length else -1
                try self.triangles.push(value - (i64)corner if value >= 0 else -1)
            corner += n

    func close():
        self.sizes.close()
        self.offsets.close()
        self.corners.close()
        self.sources.close()
        self.parents.close()
        self.display.close()
        self.triangles.close()
        self.joined.close()

    ## Free each grid node standing closer to a trim side of a cell around
    ## it than that side's length over needle_aspect (a trim grazing a row
    ## passes it at a hair): every cell around the node is joined into one
    ## and the node left out, so no triangle has to stand on the trim side
    ## with the node as its apex. The trim's points all stay. Only joins
    ## into a simple polygon of at most 64 corners, each cell joined once a
    ## round; up to 8 rounds.
    func free_nodes(mesh: const MeshBuilder*) -> !:
        for round in 0..<8:
            var sides = try SideTable(&self)
            defer sides.close()
            var taken = Growing[bool]()
            defer taken.close()
            for f in 0..<self.sizes.count: try taken.push(false)
            var fan = Growing[usize]()
            defer fan.close()
            var any = false
            for f in 0..<self.sizes.count:
                if taken.items[f]: continue
                let n = (usize)self.sizes.items[f]
                let at = self.offsets.items[f]
                var done = false
                for k in 0..<n:
                    if done: break
                    let p = self.corners.items[at + k]
                    let q = self.corners.items[at + (k + 1) % n]
                    if sides.across(p, q, f) >= 0: continue
                    let a = mesh.points[(usize)p]
                    let b = mesh.points[(usize)q]
                    let length = b.subtract(a).length()
                    for j in 0..<n:
                        let v = self.corners.items[at + j]
                        if v == p or v == q: continue
                        if side_distance(mesh.points[(usize)v], a, b) * needle_aspect >= length: continue
                        if not (try self.fan_of(&sides, f, v, &fan)): continue
                        var open = true
                        for cell in fan.view(): open = open and not taken.items[cell]
                        if not open: continue
                        if not (try self.merge(fan.view(), v)): continue
                        for cell in fan.view(): taken.items[cell] = true
                        any = true
                        done = true
                        break
            if not any: return
            try self.compact()

    ## The cells round point `v` of cell `f`, in order (into `fan`); false
    ## when `v` lies on the face's boundary (a side round it has no cell
    ## across) or more than 16 cells meet there.
    func fan_of(sides: SideTable*, f: usize, v: i64, fan: Growing[usize]*) -> bool!:
        fan.clear()
        var cell = f
        for step in 0..<16:
            try fan.push(cell)
            let n = (usize)self.sizes.items[cell]
            let at = self.offsets.items[cell]
            var j: usize = 0
            while j < n and self.corners.items[at + j] != v: j += 1
            if j == n: return false
            let across = sides.across(self.corners.items[at + (j + n - 1) % n], v, cell)
            if across < 0: return false
            if (usize)across == f: return true
            cell = (usize)across
        return false

    ## Cells `fan` (round point `v`) joined into the first one's place: the
    ## sides only one of them has, chained into one loop. False, changing
    ## nothing, when they do not chain into one simple polygon of at most
    ## 64 corners or `v` is still on it.
    func merge(fan: const usize[], v: i64) -> bool!:
        var starts = Growing[i64]()
        defer starts.close()
        var ends = Growing[i64]()
        defer ends.close()
        var origins = Growing[usize]()
        defer origins.close()
        for cell in fan:
            let n = (usize)self.sizes.items[cell]
            let at = self.offsets.items[cell]
            for k in 0..<n:
                let p = self.corners.items[at + k]
                let q = self.corners.items[at + (k + 1) % n]
                # A side two of them share (its reverse in another) is inside.
                var inner = false
                for other in fan:
                    let m = (usize)self.sizes.items[other]
                    let b = self.offsets.items[other]
                    for i in 0..<m:
                        if self.corners.items[b + i] == q and self.corners.items[b + (i + 1) % m] == p: inner = true
                if inner: continue
                try starts.push(p)
                try ends.push(q)
                try origins.push(self.sources.items[at + k])
        let count = starts.count
        if count < 3 or count > 64: return false
        for k in 0..<count:
            if starts.items[k] == v: return false
            for i in k + 1..<count:
                if starts.items[i] == starts.items[k]: return false
        let offset = self.corners.count
        var side: usize = 0
        for step in 0..<count:
            try self.corners.push(starts.items[side])
            try self.sources.push(origins.items[side])
            var next = count
            for i in 0..<count:
                if starts.items[i] == ends.items[side]: next = i
            if next == count or (next == 0) != (step + 1 == count):
                self.corners.count = offset
                self.sources.count = offset
                return false
            side = next
        let first = fan[0]
        self.offsets.items[first] = offset
        self.sizes.items[first] = (i64)count
        self.joined.items[first] = true
        for k in 1..<fan.length: self.sizes.items[fan[k]] = 0
        self.changed = true
        return true

    ## Drop the cells joins emptied.
    func compact() -> !:
        var kept: usize = 0
        for f in 0..<self.sizes.count:
            if self.sizes.items[f] == 0: continue
            self.sizes.items[kept] = self.sizes.items[f]
            self.offsets.items[kept] = self.offsets.items[f]
            self.parents.items[kept] = self.parents.items[f]
            self.display.items[kept] = self.display.items[f]
            self.joined.items[kept] = self.joined.items[f]
            kept += 1
        self.sizes.count = kept
        self.offsets.count = kept
        self.parents.count = kept
        self.display.count = kept
        self.joined.count = kept

## The cells on each side of a face's cells, hashed by the side's points
## (open addressing): a side one cell uses is on the face's boundary.
struct SideTable:
    var keys: i64[]
    var cells: i64[]

    func init(cells: const FaceCells*) -> !:
        var capacity: usize = 16
        while capacity < cells.corners.count * 4: capacity *= 2
        let keys = try new i64[capacity * 2] --- in memory.heap
        errdefer free(keys) in memory.heap
        let owners = try new i64[capacity * 2] --- in memory.heap
        self.keys = keys
        self.cells = owners
        for at in 0..<self.keys.length:
            self.keys[at] = -1
            self.cells[at] = -1
        for f in 0..<cells.sizes.count:
            let n = (usize)cells.sizes.items[f]
            let at = cells.offsets.items[f]
            for k in 0..<n:
                let slot = self.slot(cells.corners.items[at + k], cells.corners.items[at + (k + 1) % n])
                self.cells[slot * 2 + (0 if self.cells[slot * 2] < 0 else 1)] = (i64)f

    func close():
        free(self.keys) in memory.heap
        free(self.cells) in memory.heap

    ## The slot of side p-q (either way), claimed when new.
    func slot(p: i64, q: i64) -> usize:
        let a = p if p < q else q
        let b = q if p < q else p
        let count = self.keys.length // 2
        var at = ((usize)a * 73856093 + (usize)b * 19349663) % count
        while self.keys[at * 2] >= 0 and (self.keys[at * 2] != a or self.keys[at * 2 + 1] != b): at = (at + 1) % count
        self.keys[at * 2] = a
        self.keys[at * 2 + 1] = b
        return at

    ## The cell across side p-q from cell `f`, or -1 on the boundary.
    func across(p: i64, q: i64, f: usize) -> i64:
        let at = self.slot(p, q)
        let first = self.cells[at * 2]
        let second = self.cells[at * 2 + 1]
        if first == (i64)f: return second
        if second == (i64)f: return first
        return -1

## The first straight corner of the polygon at `start` (`n` corners), or -1.
func straight_at(mesh: const MeshBuilder*, start: usize, n: usize) -> i64:
    return straight_at_ids(mesh, mesh.corners[start..<start + n])

## A flat polygon of more than four corners counts as straight at its
## first: any three of its corners may lie on one line (a side folding back
## past a sample), and the ear clipping that shows it never spans them. A
## curved one keeps its own triangulation unless a corner is straight as
## the polygon faces.
func straight_at_ids(mesh: const MeshBuilder*, ids: const i64[]) -> i64:
    let n = ids.length
    if n > 4 and flat(mesh, ids): return 0
    var normal = Vector3()
    for at in 0..<n: normal = normal.add(mesh.points[(usize)ids[at]].cross(mesh.points[(usize)ids[(at + 1) % n]]))
    let facing = normal.multiply_scalar(1.0 / math.max(normal.length(), nonzero))
    for at in 0..<n:
        let a = mesh.points[(usize)ids[(at + n - 1) % n]]
        let b = mesh.points[(usize)ids[at]]
        let c = mesh.points[(usize)ids[(at + 1) % n]]
        let ac = c.subtract(a)
        # Off the line through its neighbors, as the polygon faces, by no
        # more than the display's single-precision rounding: a triangle
        # through it could show flat, on edge or turned over.
        let off = math.abs(b.subtract(a).cross(ac).dot(facing)) / math.max(ac.length(), nonzero)
        if off <= display_rounding(b): return (i64)at
    return -1

## Whether polygon `ids` lies in one plane, to the display's rounding.
func flat(mesh: const MeshBuilder*, ids: const i64[]) -> bool:
    let n = ids.length
    var normal = Vector3()
    for at in 0..<n: normal = normal.add(mesh.points[(usize)ids[at]].cross(mesh.points[(usize)ids[(at + 1) % n]]))
    let length = normal.length()
    if not (length > 0.0): return false
    let axis = normal.multiply_scalar(1.0 / length)
    let origin = mesh.points[(usize)ids[0]]
    for id in ids:
        let p = mesh.points[(usize)id]
        if math.abs(p.subtract(origin).dot(axis)) > display_rounding(p): return false
    return true

## Display triangles of polygon `ids` (indices into its corners): ear
## clipping in its own plane. An ear is taken when each of its corners lies
## farther from the opposite side than the single-precision display can
## blur (display_rounding) and no other corner lies in or on it; when none
## is that thick, the thickest unblocked one (a polygon only thin ears can
## cover: the least thin is shown). An error when no ear is left at all.
func straight_display(mesh: const MeshBuilder*, ids: const i64[], out: Growing[i64]*) -> !:
    let n = ids.length
    var normal = Vector3()
    for at in 0..<n: normal = normal.add(mesh.points[(usize)ids[at]].cross(mesh.points[(usize)ids[(at + 1) % n]]))
    out.clear()
    # A convex polygon (every corner turning its way, or straight): the fan
    # from the corner whose fan triangles are thickest, when the display
    # shows them all.
    var convex = true
    for at in 0..<n:
        let a = mesh.points[(usize)ids[(at + n - 1) % n]]
        let b = mesh.points[(usize)ids[at]]
        let c = mesh.points[(usize)ids[(at + 1) % n]]
        if b.subtract(a).cross(c.subtract(b)).dot(normal) < 0.0: convex = false
    if convex:
        var apex = n
        var best = 0.0
        for candidate in 0..<n:
            var least = 1.0e300
            for k in 1..<n - 1:
                least = math.min(least, ear(mesh, ids, candidate, (candidate + k) % n, (candidate + k + 1) % n, normal))
                if least <= best: break
            if least > best:
                apex = candidate
                best = least
        if apex < n and best >= 1.0:
            for k in 1..<n - 1:
                try out.push((i64)apex)
                try out.push((i64)((apex + k) % n))
                try out.push((i64)((apex + k + 1) % n))
            return
    var left = Growing[usize]()
    defer left.close()
    for at in 0..<n: try left.push(at)
    var scan: usize = 0
    while left.count > 3:
        # Of the unblocked ears the display shows, the best shaped (least
        # aspect); when none shows, the thickest.
        var chosen = left.count
        var best = 0.0
        var shape = 0.0
        for tries in 0..<left.count:
            let k = (scan + tries) % left.count
            let ia = left.items[(k + left.count - 1) % left.count]
            let ib = left.items[k]
            let ic = left.items[(k + 1) % left.count]
            let thickness = ear(mesh, ids, ia, ib, ic, normal)
            if thickness <= 0.0 or (best >= 1.0 and thickness < 1.0): continue
            let quality = roundness(mesh.points[(usize)ids[ia]], mesh.points[(usize)ids[ib]], mesh.points[(usize)ids[ic]])
            if best >= 1.0 and quality <= shape: continue
            if best < 1.0 and thickness < 1.0 and thickness <= best: continue
            var blocked = false
            for other in left.view():
                if other == ia or other == ib or other == ic: continue
                if inside_or_on(mesh.points[(usize)ids[other]], mesh.points[(usize)ids[ia]], mesh.points[(usize)ids[ib]], mesh.points[(usize)ids[ic]], normal):
                    blocked = true
                    break
            if blocked: continue
            chosen = k
            best = thickness
            shape = quality
        if chosen == left.count: error(invalid, "a polygon has no ear to show it by")
        try out.push((i64)left.items[(chosen + left.count - 1) % left.count])
        try out.push((i64)left.items[chosen])
        try out.push((i64)left.items[(chosen + 1) % left.count])
        # Its middle corner leaves the polygon.
        for at in chosen..<left.count - 1: left.items[at] = left.items[at + 1]
        left.count -= 1
        scan = chosen % left.count
    let ia = left.items[0]
    let ib = left.items[1]
    let ic = left.items[2]
    if ear(mesh, ids, ia, ib, ic, normal) <= 0.0: error(invalid, "a polygon's last triangle turns over")
    try out.push((i64)ia)
    try out.push((i64)ib)
    try out.push((i64)ic)

## How round triangle `a`, `b`, `c` is: twice its area over its longest
## side squared (the inverse of its aspect; 0 for a needle).
func roundness(a: Vector3, b: Vector3, c: Vector3) -> f64:
    let longest = math.max(b.subtract(a).length(), math.max(c.subtract(b).length(), a.subtract(c).length()))
    if not (longest > 0.0): return 0.0
    return b.subtract(a).cross(c.subtract(a)).length() / (longest * longest)

## How thick corners `a`, `b`, `c` of polygon `ids` are as an ear (in the
## polygon's own facing, `normal`): 0 when
## they turn against the polygon (or not at all), else the least of each
## corner's height over the opposite side in display roundings there (at
## least 1: the display shows it as it is).
func ear(mesh: const MeshBuilder*, ids: const i64[], a: usize, b: usize, c: usize, normal: Vector3) -> f64:
    let pa = mesh.points[(usize)ids[a]]
    let pb = mesh.points[(usize)ids[b]]
    let pc = mesh.points[(usize)ids[c]]
    let cross = pb.subtract(pa).cross(pc.subtract(pa))
    if cross.dot(normal) <= 0.0: return 0.0
    # Its area as the polygon faces: an ear standing on edge to it (three
    # samples of a trim bending out of the surface) has none.
    let twice = cross.dot(normal) / math.max(normal.length(), nonzero)
    let sides: f64[3] = [pc.subtract(pb).length(), pa.subtract(pc).length(), pb.subtract(pa).length()]
    # As conditioned as geocore admits a display triangle.
    let longest = math.max(sides[0], math.max(sides[1], sides[2]))
    if twice <= math.max(nonzero, longest * longest * display_conditioning): return 0.0
    let points: Vector3[3] = [pa, pb, pc]
    var least = 1.0e300
    for k in 0..<(usize)3: least = math.min(least, twice / math.max(sides[k] * display_rounding(points[k]), nonzero))
    return least

## Whether `p` lies in or on triangle `a`, `b`, `c` (turning about `normal`).
func inside_or_on(p: Vector3, a: Vector3, b: Vector3, c: Vector3, normal: Vector3) -> bool:
    return b.subtract(a).cross(p.subtract(a)).dot(normal) >= 0.0 and c.subtract(b).cross(p.subtract(b)).dot(normal) >= 0.0 and a.subtract(c).cross(p.subtract(c)).dot(normal) >= 0.0

## How small a display triangle's cross product may be against its longest
## side squared before geocore takes it as degenerate.
let display_conditioning: f64 = 1e-14