Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.8

0.7.8 / src / verbs / extrude_walls.lucb

## Extrude's faces (extrude.lucb): the input's points, the fronts and the
## wall rows between, then each face in its place (a group face on its
## fronts, keeping its id; the others as they were, or with merged walls),
## then the walls. With Manifold, a wall that would lie in the plane of the
## face beside it is left out and that face takes the wall's points into its
## boundary instead; a boundary point every remaining face of which is such a
## face (one or two of them, the line through it straight) then goes, so a
## face pushed into a box shortens its sides rather than doubling them.

## Manifold's merges: per corner of a face beside the group, the group
## corner whose wall it takes (-1 none); per corner of a group face, whether
## its wall merged; per input point, whether it goes; per face, whether it
## takes a wall.
struct Merges:
    var taken: Growing[i32]
    var merged: Growing[u8]
    var dropped: Growing[u8]
    var faces: Growing[u8]

    func init():
        self.taken = Growing[i32]()
        self.merged = Growing[u8]()
        self.dropped = Growing[u8]()
        self.faces = Growing[u8]()

    func close():
        self.taken.close()
        self.merged.close()
        self.dropped.close()
        self.faces.close()

## The extrusion's mesh: points, fronts, wall rows, faces in place, walls.
func build_faces(input: const VerbInput*, output: VerbOutput*, topology: const Topology*, fronts: const Fronts*, regions: const Regions*, settings: Extrusion) -> !:
    let mesh = input.mesh
    var builder = &output.builder
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    output.built = true
    let first_front = builder.point_count()
    for front in 0..<fronts.count():
        _ = try builder.point(front_place(mesh, fronts, regions, settings, front, 1.0), fronts.points.items[front])
    # Wall rows between each boundary point and its front: rows 1..<divisions.
    let rows = settings.divisions
    let first_row = builder.point_count()
    for row in 1..<rows:
        let t = (f64)row / (f64)rows
        for front in 0..<fronts.count():
            _ = try builder.point(front_place(mesh, fronts, regions, settings, front, t), fronts.points.items[front])
    let layout = WallLayout(first_front, first_row, rows, fronts.count())
    # The fronts' and rows' points, in the order made, renumbered with the
    # points below: what a drag's next frame places again (Mesh.trail).
    output.trail_points.clear()
    for at in first_front..<builder.point_count(): try output.trail_points.push((u32)at)
    var merges = Merges()
    defer merges.close()
    try find_merges(mesh, topology, input.group, fronts, regions, settings, &merges)
    let faces = topology.faces()
    var walls_made: usize = 0
    for face in 0..<faces:
        if not input.group.get(face): continue
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            if walls(topology, input.group, corner, settings) and merges.merged.items[corner] == 0: walls_made += rows
    output.selection = try BitsBuilder.zeros(faces + walls_made)
    output.selection_domain = Domain.face
    var run: usize = 0
    for face in 0..<faces:
        let grouped = input.group.get(face)
        if not grouped and merges.faces.items[face] == 0: continue
        try builder.copy_faces(mesh, run, face)
        run = face + 1
        if not grouped:
            try merged_face(topology, fronts, builder, &merges, layout, face)
            continue
        output.selection.set(face)
        try builder.face((i32)face, settings.inset == 0.0)
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            let front = fronts.of_corner.items[corner]
            try front_corner(topology, builder, (i32)(first_front + (usize)front), corner, fronts.shifts.items[(usize)front], mesh)
        try builder.end_face()
    try builder.copy_faces(mesh, run, faces)
    # Walls: along each boundary edge a→b, rows from the input points to the
    # fronts, facing the way the face beside them did.
    for face in 0..<faces:
        if not input.group.get(face): continue
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            if not walls(topology, input.group, corner, settings) or merges.merged.items[corner] != 0: continue
            let next = topology.next(corner)
            let front_a = (usize)fronts.of_corner.items[corner]
            let front_b = (usize)fronts.of_corner.items[next]
            let a = WallSide(corner, front_a, fronts.shifts.items[front_a])
            let b = WallSide(next, front_b, fronts.shifts.items[front_b])
            for row in 0..<rows:
                try builder.face((i32)face)
                try wall_corner(topology, builder, mesh, a, row, layout)
                try wall_corner(topology, builder, mesh, b, row, layout)
                try wall_corner(topology, builder, mesh, b, row + 1, layout)
                try wall_corner(topology, builder, mesh, a, row + 1, layout)
                try builder.end_face()
    var renumbered = Growing[i32]()
    defer renumbered.close()
    for point in output.trail_points.view(): try renumbered.push((i32)point)
    try builder.drop_unused_points(none, &renumbered)
    for (at, point) in renumbered.view().indexed(): output.trail_points.items[at] = (u32)point if point >= 0 else dropped_point

## A trail entry for a front or row point the build dropped (unused).
let dropped_point: u32 = 0xFFFFFFFF

## Where the fronts and the wall rows' points are in the builder.
struct WallLayout:
    let first_front: usize
    let first_row: usize
    let rows: usize
    let fronts: usize

    ## Front `front`'s point on row `row` (1..rows; rows is the front).
    func at(front: usize, row: usize) -> i32:
        if row == self.rows: return (i32)(self.first_front + front)
        return (i32)(self.first_row + (row - 1) * self.fronts + front)

## Manifold's merges (see Merges); nothing without Manifold.
func find_merges(mesh: const Mesh*, topology: const Topology*, group: Bits, fronts: const Fronts*, regions: const Regions*, settings: Extrusion, merges: Merges*) -> !:
    try merges.taken.fill(topology.corners.length, -1)
    try merges.merged.fill(topology.corners.length, 0)
    try merges.dropped.fill(topology.points, 0)
    try merges.faces.fill(topology.faces(), 0)
    if not settings.manifold: return
    let normals = mesh.face_normal_span()
    let faces = topology.faces()
    let walled = try new u8[topology.points] --- in memory.heap
    defer free(walled) in memory.heap
    # A front each merged wall's points move to (for a lone face's line).
    let front_at = try new i32[topology.points] --- in memory.heap
    defer free(front_at) in memory.heap
    for at in 0..<topology.points:
        walled[at] = 0
        front_at[at] = -1
    for face in 0..<faces:
        if not group.get(face): continue
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            if not walls(topology, group, corner, settings): continue
            let next = topology.next(corner)
            let twin = topology.twin(corner)
            if twin >= 0 and in_plane(mesh, fronts, regions, settings, normals[(usize)topology.corner_faces[(usize)twin]].vector(), corner, next):
                merges.merged.items[corner] = 1
                merges.taken.items[(usize)twin] = (i32)corner
                merges.faces.items[(usize)topology.corner_faces[(usize)twin]] = 1
                front_at[(usize)topology.corners[corner]] = fronts.of_corner.items[corner]
                front_at[(usize)topology.corners[next]] = fronts.of_corner.items[next]
            else:
                walled[(usize)topology.corners[corner]] = 1
                walled[(usize)topology.corners[next]] = 1
    # Around each point: the faces beside the group that took a wall at it,
    # and those that did not.
    let taking = try new u32[topology.points] --- in memory.heap
    defer free(taking) in memory.heap
    let plain = try new u32[topology.points] --- in memory.heap
    defer free(plain) in memory.heap
    let line_to = try new i32[topology.points] --- in memory.heap
    defer free(line_to) in memory.heap
    for at in 0..<topology.points:
        taking[at] = 0
        plain[at] = 0
        line_to[at] = -1
    for face in 0..<faces:
        if group.get(face): continue
        for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
            let point = (usize)topology.corners[corner]
            let before = topology.previous(corner)
            let out_taken = merges.taken.items[corner] >= 0
            let in_taken = merges.taken.items[before] >= 0
            if not out_taken and not in_taken:
                plain[point] += 1
                continue
            taking[point] += 1
            # The face's other edge at the point, for a lone face's line.
            if out_taken != in_taken: line_to[point] = topology.corners[topology.next(corner)] if in_taken else topology.corners[before]
    for point in 0..<topology.points:
        if walled[point] != 0 or plain[point] != 0 or taking[point] == 0 or taking[point] > 2: continue
        if taking[point] == 1 and not straight(mesh, fronts, regions, settings, point, line_to[point], front_at[point]): continue
        merges.dropped.items[point] = 1

## Whether the wall on group corner `corner`'s edge (to `next`) would lie in
## the plane facing `normal`: both its fronts move within it.
func in_plane(mesh: const Mesh*, fronts: const Fronts*, regions: const Regions*, settings: Extrusion, normal: Vector3, corner: usize, next: usize) -> bool:
    let ends: usize[2] = [corner, next]
    for end in ends:
        let front = (usize)fronts.of_corner.items[end]
        let move = front_place(mesh, fronts, regions, settings, front, 1.0).subtract(point_of(mesh, fronts.points.items[front]))
        let length = move.length()
        if length == 0.0 or math.abs(normal.dot(move)) > 0.00001 * length: return false
    return true

## Whether a lone face's edge at `point` (to `other`) runs along the point's
## move to its front `front`, so the point can go from the face's straight
## side.
func straight(mesh: const Mesh*, fronts: const Fronts*, regions: const Regions*, settings: Extrusion, point: usize, other: i32, front: i32) -> bool:
    if other < 0 or front < 0: return false
    let here = point_of(mesh, (i32)point)
    let side = point_of(mesh, other).subtract(here)
    let move = front_place(mesh, fronts, regions, settings, (usize)front, 1.0).subtract(here)
    return side.cross(move).length() <= 0.000001 * side.length() * move.length()

## Face `face` beside the group with the walls it takes: at its corner on a
## merged edge (b to a here, a to b in the group face) the path from b
## through b's rows and front to a's front and rows; the points that go are
## left out.
func merged_face(topology: const Topology*, fronts: const Fronts*, builder: TopologyBuilder*, merges: const Merges*, layout: WallLayout, face: usize) -> !:
    try builder.face((i32)face)
    for corner in (usize)topology.offsets[face]..<(usize)topology.offsets[face + 1]:
        let point = topology.corners[corner]
        if merges.dropped.items[(usize)point] == 0: try builder.corner(point, (i32)corner)
        let wall = merges.taken.items[corner]
        if wall < 0: continue
        let a = (usize)wall
        let b = topology.next(a)
        let front_a = (usize)fronts.of_corner.items[a]
        let front_b = (usize)fronts.of_corner.items[b]
        let next = (i32)topology.next(corner)
        let b_kept = merges.dropped.items[(usize)topology.corners[b]] == 0
        let a_kept = merges.dropped.items[(usize)topology.corners[a]] == 0
        for row in 1..<layout.rows:
            if b_kept: try builder.corner(layout.at(front_b, row), (i32)corner)
        try builder.corner(layout.at(front_b, layout.rows), (i32)corner)
        try builder.corner(layout.at(front_a, layout.rows), next)
        for back in 1..<layout.rows:
            if a_kept: try builder.corner(layout.at(front_a, layout.rows - back), next)
    try builder.end_face()

## One end of a wall: the face corner it starts from, its front and that
## front's rim shift.
struct WallSide:
    let corner: usize
    let front: usize
    let shift: Vector3

## A wall corner on row `row` (0 the input point, `rows` the front): its
## values blend like the front's, by the share of the inset it has made.
func wall_corner(topology: const Topology*, builder: TopologyBuilder*, mesh: const Mesh*, side: WallSide, row: usize, layout: WallLayout) -> !:
    if row == 0: return try builder.corner(topology.corners[side.corner], (i32)side.corner)
    let t = (f64)row / (f64)layout.rows
    try front_corner(topology, builder, layout.at(side.front, row), side.corner, side.shift.multiply_scalar(t), mesh)

## A front corner: the face's own corner, blended with its neighbors by how
## far the inset moved the point along the face's two edges (exact for
## values linear across a flat face, like projected UVs).
func front_corner(topology: const Topology*, builder: TopologyBuilder*, point: i32, corner: usize, shift: Vector3, mesh: const Mesh*) -> !:
    if shift.length() == 0.0: return try builder.corner(point, (i32)corner)
    let before = topology.previous(corner)
    let after = topology.next(corner)
    let here = point_of(mesh, topology.corners[corner])
    let e1 = point_of(mesh, topology.corners[before]).subtract(here)
    let e2 = point_of(mesh, topology.corners[after]).subtract(here)
    let a11 = e1.dot(e1)
    let a12 = e1.dot(e2)
    let a22 = e2.dot(e2)
    let determinant = a11 * a22 - a12 * a12
    if math.abs(determinant) < 0.000000000001 * math.max(a11 * a22, 0.000000000001): return try builder.corner(point, (i32)corner)
    let r1 = e1.dot(shift)
    let r2 = e2.dot(shift)
    let alpha = (r1 * a22 - r2 * a12) / determinant
    let beta = (r2 * a11 - r1 * a12) / determinant
    let parents: i32[3] = [(i32)corner, (i32)before, (i32)after]
    let weights: f32[3] = [(f32)(1.0 - alpha - beta), (f32)alpha, (f32)beta]
    try builder.mixed_corner(point, parents[..<3], weights[..<3])