Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-3d

Source of release 0.9.6

0.9.6 / src / renderers / box_select.lucb

## Box selection in Base, as the viewport's marquee selects: points inside a
## screen rectangle, and the edges and faces it touches (Houdini's rule:
## meeting the box is enough). Through the depth, or only what shows there:
## an id pass of the visible faces (IdImage, from Renderer.select_box), else
## view rays when no id pass is at hand. Objects ask BoxSelect.touches.
## A window (`wholly`, Fusion's left-to-right box and the CAD rule) takes
## only edges and faces whose every point is inside the box.
## Every loop here is over the mesh's own arrays; callers never loop over
## its elements.
import interop
from luce_std import math
import errors
from luce_geocore.geocore import Vector3, Matrix4, Mesh, Selection
from luce_geocore.kernel import BitsBuilder, GroupReport, Domain, adopt_selection, selection_bits
from cameras.camera import Camera, Projection
from renderers.edit_screen import project

## A screen rectangle in logical pixels, y down.
pub struct ScreenBox:
    pub let left: f64
    pub let top: f64
    pub let right: f64
    pub let bottom: f64

    ## The box between corners (x0, y0) and (x1, y1), either way round.
    pub static func between(x0: f64, y0: f64, x1: f64, y1: f64) -> ScreenBox:
        return ScreenBox(math.min(x0, x1), math.min(y0, y1), math.max(x0, x1), math.max(y0, y1))

    pub func holds(x: f64, y: f64) -> bool:
        return x >= self.left and x <= self.right and y >= self.top and y <= self.bottom

    ## The part of the screen segment a → b inside the box, as fractions
    ## along it (Liang-Barsky), or none when the segment misses the box.
    pub func clip(a: Vector3, b: Vector3) -> Along?:
        var start = 0.0
        var end = 1.0
        let dx = b.x - a.x
        let dy = b.y - a.y
        let steps: f64[4] = [-dx, dx, -dy, dy]
        let room: f64[4] = [a.x - self.left, self.right - a.x, a.y - self.top, self.bottom - a.y]
        for side in 0..<(usize)4:
            if steps[side] == 0.0:
                if room[side] < 0.0: return none
                continue
            let t = room[side] / steps[side]
            if steps[side] < 0.0:
                start = math.max(start, t)
            else:
                end = math.min(end, t)
            if start > end: return none
        return Along(start, end)

## A stretch of a segment, as fractions from its start.
pub struct Along:
    pub let start: f64
    pub let end: f64

## What shows at each pixel of a view: the last id pass (face + 1 per pixel,
## zero where nothing is), its faces answered as cage faces through
## `owners` when it drew a subdivided display (empty: its own faces).
pub struct IdImage:
    pub let pixels: const u8[]
    pub let width: u32
    pub let height: u32
    pub let owners: const u32[]

    ## The face at (x, y), or -1 where nothing is (or outside the image).
    pub func face(x: f64, y: f64) -> i64:
        if not (x >= 0.0 and y >= 0.0 and x < (f64)self.width and y < (f64)self.height): return -1
        let at = ((usize)y * (usize)self.width + (usize)x) * 4
        let bytes = self.pixels
        let id = (i64)((u32)bytes[at] | ((u32)bytes[at + 1] << 8) | ((u32)bytes[at + 2] << 16) | ((u32)bytes[at + 3] << 24)) - 1
        if id < 0 or self.owners.length == 0: return id
        return (i64)self.owners[(usize)id] if (usize)id < self.owners.length else -1

    ## Whether the component with points `a` and `b` (-1: a point alone)
    ## shows at (x, y): within a pixel, a face holding it is seen there, or
    ## nothing covers that spot at all.
    pub func shows(mesh: const Mesh*, x: f64, y: f64, a: i64, b: i64) -> bool:
        var covered = false
        for row in 0..<(usize)3:
            for column in 0..<(usize)3:
                let face = self.face(x + (f64)column - 1.0, y + (f64)row - 1.0)
                if face < 0: continue
                covered = true
                if holds_point(mesh, face, a) and (b < 0 or holds_point(mesh, face, b)): return true
        return not covered

pub struct BoxSelect:
    let reserved: u8 = 0

    ## `current` (on points, edges or faces of `mesh`) changed by what the
    ## screen box from (x0, y0) to (x1, y1) of a `width` x `height` view
    ## through `camera` touches: replaced (operation 0), added to (1) or
    ## taken from (2). With `visible_only`, only what view rays reach
    ## (Renderer.select_box asks the GPU instead, once a frame drew `mesh`);
    ## with `wholly`, only edges and faces wholly inside the box.
    pub static func select(mesh: interop.Reference[Mesh], camera: interop.Reference[Camera], current: interop.Reference[Selection],
                           x0: f64, y0: f64, x1: f64, y1: f64, width: f64, height: f64, operation: i64, visible_only: bool = true, wholly: bool = false) -> interop.Reference[Selection]!:
        let projection = try camera.value().projection(math.max(1.0, width) / math.max(1.0, height))
        return try box_selection(try mesh.get(), Matrix4(), projection, ScreenBox.between(x0, y0, x1, y1), width, height, try current.get(), operation, visible_only, none, wholly)

    ## Whether `mesh` (in world space) shows anywhere in the box from
    ## (x0, y0) to (x1, y1) through the depth: one of its faces meets it,
    ## or for a mesh of points alone one of its points is inside. An object
    ## pick by box: its bounds answer first when they can.
    pub static func touches(mesh: interop.Reference[Mesh], camera: interop.Reference[Camera], x0: f64, y0: f64, x1: f64, y1: f64, width: f64, height: f64) -> bool!:
        let geometry = try mesh.get()
        let p = try camera.value().projection(math.max(1.0, width) / math.max(1.0, height))
        let box = ScreenBox.between(x0, y0, x1, y1)
        let view = BoxView(mesh = geometry, world = Matrix4(), inverse = Matrix4(), p = p, box = box, width = width, height = height, ids = none, rays = false)
        let bounds = geometry.bounds()
        var left = 1.0e300
        var top = 1.0e300
        var right = -1.0e300
        var bottom = -1.0e300
        var ahead = true
        for corner in 0..<(usize)8:
            let point = Vector3(bounds.maximum.x if corner % 2 == 1 else bounds.minimum.x, bounds.maximum.y if (corner // 2) % 2 == 1 else bounds.minimum.y,
                                bounds.maximum.z if corner >= 4 else bounds.minimum.z)
            let at = project(point, p, width, height)
            ahead = ahead and at.z > p.near
            left = math.min(left, at.x)
            top = math.min(top, at.y)
            right = math.max(right, at.x)
            bottom = math.max(bottom, at.y)
        if ahead:
            if right < box.left or left > box.right or bottom < box.top or top > box.bottom: return false
            if left >= box.left and right <= box.right and top >= box.top and bottom <= box.bottom: return true
        if geometry.face_count() == 0:
            for point in 0..<geometry.point_count():
                let at = view.screen(point)
                if at.z > p.near and box.holds(at.x, at.y): return true
            return false
        for face in 0..<geometry.face_count():
            if view.face_meets(face): return true
        return false

## `chosen` changed by what `box` touches of `mesh` (placed by `world`) in a
## `width` x `height` view through `p`; see BoxSelect.select. `ids`, when
## given, says what shows (visible only); else `visible_only` casts rays.
## With `wholly`, an edge or face counts only when all its points are in the
## box (and it shows there, when only what shows counts).
pub func box_selection(mesh: const Mesh*, world: Matrix4, p: Projection, box: ScreenBox, width: f64, height: f64, chosen: const Selection*,
                       operation: i64, visible_only: bool, ids: IdImage?, wholly: bool = false) -> interop.Reference[Selection]!:
    if operation < 0 or operation > 2: error(errors.invalid, "a box selection replaces (0), adds (1) or removes (2)")
    let domain = chosen.domain()
    if domain != 0 and domain != 2 and domain != 4: error(errors.invalid, "a box selects points, edges or faces")
    let count = (usize)chosen.size()
    let inverse = try world.inverse()
    # A mesh without faces has nothing to hide its points.
    let rays = visible_only and ids == none and mesh.face_count() > 0
    let view = BoxView(mesh = mesh, world = world, inverse = inverse, p = p, box = box, width = width, height = height,
                       ids = ids if visible_only and mesh.face_count() > 0 else none, rays = rays)
    var bits = (try BitsBuilder.copy_of(selection_bits(chosen))) if operation != 0 else (try BitsBuilder.zeros(count))
    errdefer bits.close()
    if domain == 0:
        for point in 0..<count:
            let at = view.screen((i64)point)
            if at.z <= p.near or not box.holds(at.x, at.y): continue
            if try view.point_shows((i64)point, at): mark(&bits, point, operation)
    elif domain == 4:
        let edges = try mesh.edge_span()
        for edge in 0..<count:
            let a = (i64)edges[edge * 2]
            let b = (i64)edges[edge * 2 + 1]
            let start = view.screen(a)
            let end = view.screen(b)
            if start.z <= p.near or end.z <= p.near: continue
            if wholly and not (box.holds(start.x, start.y) and box.holds(end.x, end.y)): continue
            let along = box.clip(start, end) else continue
            if try view.edge_shows(a, b, start, end, along): mark(&bits, edge, operation)
    elif wholly:
        # Faces wholly inside, shown there (by the id pass, or rays).
        var seen = try BitsBuilder.zeros(count)
        defer seen.close()
        if let image = view.ids:
            faces_seen(&seen, image, box, count, 0)
        for face in 0..<count:
            if not view.face_inside((i64)face): continue
            if view.ids != none:
                if not seen.view().get(face): continue
            elif rays and not (try view.face_seen((i64)face)):
                continue
            mark(&bits, face, operation)
    elif view.ids != none:
        faces_seen(&bits, view.ids else error(errors.invalid, "no id image"), box, count, operation)
    else:
        for face in 0..<count:
            if not view.face_meets((i64)face): continue
            if not rays or try view.face_seen((i64)face): mark(&bits, face, operation)
    return try adopt_selection(bits.finish(), count, Domain.point if domain == 0 else (Domain.edge if domain == 4 else Domain.face), (u64)mesh.topology_hash(), GroupReport())

## The faces an id image shows inside `box` are those under it.
func faces_seen(bits: BitsBuilder*, image: IdImage, box: ScreenBox, count: usize, operation: i64):
    if box.right < 0.0 or box.bottom < 0.0 or box.left >= (f64)image.width or box.top >= (f64)image.height: return
    let left = (usize)math.max(0.0, math.floor(box.left))
    let top = (usize)math.max(0.0, math.floor(box.top))
    let right = (usize)math.min((f64)image.width - 1.0, math.floor(box.right))
    let bottom = (usize)math.min((f64)image.height - 1.0, math.floor(box.bottom))
    for y in top..<bottom + 1:
        for x in left..<right + 1:
            let face = image.face((f64)x, (f64)y)
            if face >= 0 and (usize)face < count: mark(bits, (usize)face, operation)

func mark(bits: BitsBuilder*, at: usize, operation: i64):
    if operation == 2:
        bits.clear(at)
    else:
        bits.set(at)

## Whether face `face` has point `point` among its corners.
func holds_point(mesh: const Mesh*, face: i64, point: i64) -> bool:
    let offsets = mesh.offset_span()
    if face < 0 or (usize)face + 1 >= offsets.length: return false
    let corners = mesh.corner_span()
    for corner in (usize)offsets[(usize)face]..<(usize)offsets[(usize)face + 1]:
        if (i64)corners[corner] == point: return true
    return false

## A mesh seen through a view for one box: where its points land, and
## whether a component shows (by `ids`, by view rays, or always).
struct BoxView:
    let mesh: const Mesh*
    let world: Matrix4
    let inverse: Matrix4
    let p: Projection
    let box: ScreenBox
    let width: f64
    let height: f64
    let ids: IdImage?
    let rays: bool

    ## Point `point` on screen: x, y and its view depth.
    func screen(point: i64) -> Vector3:
        return project(self.place(point), self.p, self.width, self.height)

    ## Point `point` in world space.
    func place(point: i64) -> Vector3:
        let local = self.mesh.point_span()[(usize)point].vector().add(self.mesh.position_origin())
        return self.world.transform_point(local)

    func point_shows(point: i64, at: Vector3) -> bool!:
        if let image = self.ids:
            return image.shows(self.mesh, at.x, at.y, point, -1)
        if not self.rays: return true
        return try self.reaches(self.place(point))

    ## Edge (a, b), its ends on screen at `start` and `end`, shows inside the
    ## box: somewhere along its part in the box (a sample every 2 pixels).
    func edge_shows(a: i64, b: i64, start: Vector3, end: Vector3, along: Along) -> bool!:
        if let image = self.ids:
            let length = math.hypot(end.x - start.x, end.y - start.y) * (along.end - along.start)
            let samples = (i64)math.clamp(math.ceil(length / 2.0), 1.0, 256.0)
            for k in 0..<samples:
                let t = along.start + (along.end - along.start) * ((f64)k + 0.5) / (f64)samples
                if image.shows(self.mesh, start.x + (end.x - start.x) * t, start.y + (end.y - start.y) * t, a, b): return true
            return false
        if not self.rays: return true
        let middle = (along.start + along.end) * 0.5
        let origin = self.place(a)
        return try self.reaches(origin.add(self.place(b).subtract(origin).multiply_scalar(middle)))

    ## Whether every corner of face `face` is on screen inside the box.
    func face_inside(face: i64) -> bool:
        let offsets = self.mesh.offset_span()
        let corners = self.mesh.corner_span()
        for corner in (usize)offsets[(usize)face]..<(usize)offsets[(usize)face + 1]:
            let at = self.screen((i64)corners[corner])
            if at.z <= self.p.near or not self.box.holds(at.x, at.y): return false
        return true

    ## Whether face `face` meets the box on screen: one of its sides crosses
    ## it, or (all in front of the camera) it holds the box's middle.
    func face_meets(face: i64) -> bool:
        let offsets = self.mesh.offset_span()
        let corners = self.mesh.corner_span()
        let first = (usize)offsets[(usize)face]
        let last = (usize)offsets[(usize)face + 1]
        let middle_x = (self.box.left + self.box.right) * 0.5
        let middle_y = (self.box.top + self.box.bottom) * 0.5
        var ahead = true
        var winding = 0.0
        for corner in first..<last:
            let a = self.screen((i64)corners[corner])
            let b = self.screen((i64)corners[corner + 1 if corner + 1 < last else first])
            if a.z <= self.p.near or b.z <= self.p.near:
                ahead = false
                continue
            if self.box.clip(a, b) != none: return true
            winding += math.atan2((a.x - middle_x) * (b.y - middle_y) - (a.y - middle_y) * (b.x - middle_x), (a.x - middle_x) * (b.x - middle_x) + (a.y - middle_y) * (b.y - middle_y))
        return ahead and math.abs(winding) > math.pi

    ## By view rays: face `face` is the first thing seen toward its middle
    ## or a spot just inside one of its corners, inside the box; or, when
    ## none of those is in the box, under the box's middle.
    func face_seen(face: i64) -> bool!:
        let offsets = self.mesh.offset_span()
        let corners = self.mesh.corner_span()
        let first = (usize)offsets[(usize)face]
        let last = (usize)offsets[(usize)face + 1]
        var center = Vector3()
        for corner in first..<last:
            center = center.add(self.place((i64)corners[corner]))
        center = center.multiply_scalar(1.0 / (f64)(last - first))
        var inside = false
        for corner in first..<last + 1:
            let spot = center if corner == last else self.place((i64)corners[corner]).multiply_scalar(0.95).add(center.multiply_scalar(0.05))
            let at = project(spot, self.p, self.width, self.height)
            if at.z <= self.p.near or not self.box.holds(at.x, at.y): continue
            inside = true
            if try self.first_face(spot) == face: return true
        if inside: return false
        let p = self.p
        let x = (self.box.left + self.box.right) * 0.5
        let y = (self.box.top + self.box.bottom) * 0.5
        return try self.first_face(p.ray_origin(x, y, self.width, self.height).add(p.ray_direction(x, y, self.width, self.height))) == face

    ## The face the view ray toward world point `point` meets first (-1: none).
    func first_face(point: Vector3) -> i64!:
        let eye = self.inverse.transform_point(self.p.eye_for(point))
        return try self.mesh.ray_face(eye, try self.inverse.transform_point(point).subtract(eye).normalized())

    ## Whether the view ray to world point `point` meets nothing of the
    ## mesh before it.
    func reaches(point: Vector3) -> bool!:
        let eye = self.inverse.transform_point(self.p.eye_for(point))
        let offset = self.inverse.transform_point(point).subtract(eye)
        let distance = offset.length()
        if distance < 1.0e-12: return true
        let hit = try self.mesh.ray_distance(eye, try offset.normalized())
        return hit < 0.0 or hit >= distance * (1.0 - 1.0e-5) - 1.0e-9