Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.7

0.7.7 / src / selecting / walkers.lucb

## Loop and ring walkers over a mesh's corners, with the rules Blender's
## edge-loop walker follows (read in its bmesh_walkers_impl.cc, written here
## our own way):
##
## - Inside a mesh a loop crosses each point of four edges (or two) to the
##   edge across it, past half the point's faces, every edge it crosses
##   having two faces; any other point (a pole) ends it.
## - A loop started on a boundary edge runs along the boundary, through the
##   fan of faces at each point to the next boundary edge; it stops at a
##   corner of two edges (an outer corner) and where it would leave or join
##   an n-gon's side.
## - A loop started on an n-gon's side whose ends have three edges and
##   three faces (the n-gon is the hub) runs along the hub's sides while
##   their points keep three edges.
## - A ring crosses each quad to its opposite edge; it stops at faces that
##   are not quads, boundaries and edges of more than two faces.
## - A face loop is the quads a ring passes through.
##
## Corner `c`'s edge runs from its point to the next corner's point.

## The corner of `corner`'s face whose edge is the other edge of that face
## at `point` (the point is one of the corner's edge's ends).
func other_at(topology: const Topology*, corner: usize, point: usize) -> usize:
    return topology.previous(corner) if (usize)topology.corners[corner] == point else topology.next(corner)

## How many faces meet at point `point` (each counts its two edges there).
func faces_at(topology: const Topology*, point: usize) -> usize:
    var total: usize = 0
    for at in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
        total += edge_faces(topology, (usize)topology.point_edges[at])
    return total // 2

## The first corner of edge `edge` (-1 for an edge without faces).
func first_corner(topology: const Topology*, edge: usize) -> i64:
    let start = (usize)topology.edge_corner_offsets[edge]
    if start == (usize)topology.edge_corner_offsets[edge + 1]: return -1
    return (i64)topology.edge_corners[start]

## The edge between points `a` and `b`, or -1.
func edge_between(topology: const Topology*, a: usize, b: usize) -> i64:
    for at in (usize)topology.point_edge_offsets[a]..<(usize)topology.point_edge_offsets[a + 1]:
        let edge = (usize)topology.point_edges[at]
        if other_point(topology, edge, a) == b: return (i64)edge
    return -1

## A boundary edge on an n-gon's side next to another boundary edge (the
## n-gon delimit's test).
func single_side(topology: const Topology*, edge: usize) -> bool:
    if edge_faces(topology, edge) != 1: return false
    let corner = (usize)topology.edge_corners[(usize)topology.edge_corner_offsets[edge]]
    let face = (usize)topology.corner_faces[corner]
    if face_sides(topology, face) <= 4: return false
    return edge_faces(topology, (usize)topology.corner_edges[topology.next(corner)]) == 1 or edge_faces(topology, (usize)topology.corner_edges[topology.previous(corner)]) == 1

## One walk along an edge loop: the edge it is on, the point it came from
## and the rule it follows (set when it starts).
struct LoopWalk:
    var edge: usize
    var last: usize
    let boundary: bool
    let single: bool
    ## The n-gon it runs along the sides of (-1: none).
    let hub: i64

## The hub of a loop started on `edge`: its largest face when that has five
## sides or more and an end of the edge has three edges and three faces.
func hub_of(topology: const Topology*, edge: usize) -> i64:
    if edge_faces(topology, edge) == 1: return -1
    var hub_end = false
    for side in 0..<(usize)2:
        let point = (usize)topology.edge_points[edge * 2 + side]
        if topology.valence(point) == 3 and faces_at(topology, point) == 3: hub_end = true
    if not hub_end: return -1
    var best: i64 = -1
    var sides: usize = 0
    for at in 0..<edge_faces(topology, edge):
        let face = edge_face(topology, edge, at)
        if face_sides(topology, face) > sides:
            sides = face_sides(topology, face)
            best = (i64)face
    return best if sides > 4 else -1

## The edge the walk steps onto from its edge across its far point, or -1.
func loop_step(topology: const Topology*, walk: const LoopWalk*) -> i64:
    let point = other_point(topology, walk.edge, walk.last)
    let valence = topology.valence(point)
    if walk.hub >= 0:
        if valence != 3: return -1
        # Along the hub's side: the edge from the point to its neighbor in
        # the hub that is not where the walk came from.
        let hub = (usize)walk.hub
        for corner in (usize)topology.offsets[hub]..<(usize)topology.offsets[hub + 1]:
            if (usize)topology.corners[corner] != point: continue
            let before = (usize)topology.corners[topology.previous(corner)]
            let after = (usize)topology.corners[topology.next(corner)]
            let toward = after if before == walk.last else before
            let next = edge_between(topology, point, toward)
            if next < 0 or edge_faces(topology, (usize)next) == 1: return -1
            return next
        return -1
    let start = first_corner(topology, walk.edge)
    if start < 0: return -1
    var corner = (usize)start
    if not walk.boundary:
        # Across a point of four (or two) edges: half its faces further.
        if valence != 4 and valence != 2: return -1
        for _ in 0..<valence // 2:
            corner = other_at(topology, corner, point)
            let twin = topology.twin(corner)
            if edge_faces(topology, (usize)topology.corner_edges[corner]) != 2 or twin < 0: return -1
            corner = (usize)twin
        let next = (usize)topology.corner_edges[corner]
        return -1 if next == walk.edge else (i64)next
    # Along a boundary: an outer corner (two edges) ends it, unless the
    # edge is an n-gon's side; else through the fan to the next boundary
    # edge.
    if valence == 2 and not walk.single: return -1
    for _ in 0..<valence + 1:
        corner = other_at(topology, corner, point)
        let faces = edge_faces(topology, (usize)topology.corner_edges[corner])
        if faces == 1:
            let next = (usize)topology.corner_edges[corner]
            if next == walk.edge or single_side(topology, next) != walk.single: return -1
            return (i64)next
        let twin = topology.twin(corner)
        if faces != 2 or twin < 0: return -1
        corner = (usize)twin
    return -1

## Walk the loop of `start` through its point `through` (its second point
## when `forward`), setting each edge in `seen` and appending it to `order`
## (when given) until the loop ends or closes.
func walk_loop(topology: const Topology*, start: usize, forward: bool, seen: BitsBuilder*, order: Growing[u32]*?) -> !:
    let boundary = edge_faces(topology, start) == 1
    let behind = (usize)topology.edge_points[start * 2 + (0 if forward else 1)]
    var walk = LoopWalk(start, behind, boundary, boundary and single_side(topology, start), hub_of(topology, start))
    for _ in 0..<topology.edges():
        let next = loop_step(topology, &walk)
        if next < 0 or seen.view().get((usize)next): return
        let edge = (usize)next
        seen.set(edge)
        if let list = order: try list.push((u32)edge)
        walk.last = other_point(topology, walk.edge, walk.last)
        walk.edge = edge

## The edge loops of every edge in `edges`, added to `out`.
pub func loops_of(topology: const Topology*, edges: Bits, out: BitsBuilder*) -> !:
    for word in 0..<edges.words.length:
        var pending = edges.words[word]
        while pending != 0:
            let edge = word * 64 + (usize)trailing_zeros(pending)
            pending = pending & (pending - 1)
            out.set(edge)
            try walk_loop(topology, edge, true, out, none)
            try walk_loop(topology, edge, false, out, none)

## The run of the loop through `a` that reaches `b`, the shorter way round,
## into `out`; false when `b` is not on `a`'s loop.
pub func loop_run(topology: const Topology*, a: usize, b: usize, out: BitsBuilder*) -> bool!:
    var best = Growing[u32]()
    defer best.close()
    var found = false
    for pass in 0..<(usize)2:
        let forward = pass == 0
        var seen = try BitsBuilder.zeros(topology.edges())
        defer seen.close()
        seen.set(a)
        var order = Growing[u32]()
        defer order.close()
        try walk_loop(topology, a, forward, &seen, &order)
        for at in 0..<order.count:
            if (usize)order.items[at] != b: continue
            if not found or at + 1 < best.count:
                try best.assign(order.items[..<at + 1])
                found = true
            break
    if not found: return false
    out.set(a)
    for edge in best.view(): out.set((usize)edge)
    return true

## From corner `start` across its face to the opposite edge, and on through
## the next face, while the faces are quads: each edge into `edges`, each
## quad into `faces` (when given).
func walk_ring(topology: const Topology*, start: usize, edges: BitsBuilder*?, faces: BitsBuilder*?, seed: usize):
    var corner = start
    for _ in 0..<topology.edges():
        let face = (usize)topology.corner_faces[corner]
        if face_sides(topology, face) != 4: return
        if let quads = faces:
            if quads.view().get(face): return
            quads.set(face)
        let opposite = topology.next(topology.next(corner))
        let edge = (usize)topology.corner_edges[opposite]
        if let ring = edges:
            if edge == seed or ring.view().get(edge): return
            ring.set(edge)
        if edge_faces(topology, edge) != 2: return
        let across = topology.twin(opposite)
        if across < 0: return
        corner = (usize)across

## The edge rings of every edge in `edges`, added to `out`.
pub func rings_of(topology: const Topology*, edges: Bits, out: BitsBuilder*):
    for word in 0..<edges.words.length:
        var pending = edges.words[word]
        while pending != 0:
            let edge = word * 64 + (usize)trailing_zeros(pending)
            pending = pending & (pending - 1)
            out.set(edge)
            if edge_faces(topology, edge) > 2: continue
            for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
                walk_ring(topology, (usize)topology.edge_corners[at], out, none, edge)

## The face loop crossing edge `edge` (the quads its ring passes through),
## added to `faces`.
pub func face_loop(topology: const Topology*, edge: usize, faces: BitsBuilder*):
    if edge_faces(topology, edge) != 2: return
    for at in (usize)topology.edge_corner_offsets[edge]..<(usize)topology.edge_corner_offsets[edge + 1]:
        walk_ring(topology, (usize)topology.edge_corners[at], none, faces, edge)

## Every boundary edge connected to a boundary edge of `edges` through
## boundary points: whole boundaries (Blender's boundary walker).
pub func boundaries_of(topology: const Topology*, edges: Bits, out: BitsBuilder*) -> !:
    let queue = try new u32[topology.edges()] --- in memory.heap
    defer free(queue) in memory.heap
    var tail: usize = 0
    for word in 0..<edges.words.length:
        var pending = edges.words[word]
        while pending != 0:
            let edge = word * 64 + (usize)trailing_zeros(pending)
            pending = pending & (pending - 1)
            if edge_faces(topology, edge) != 1 or out.view().get(edge): continue
            out.set(edge)
            queue[tail] = (u32)edge
            tail += 1
    var head: usize = 0
    while head < tail:
        let edge = (usize)queue[head]
        head += 1
        for side in 0..<(usize)2:
            let point = (usize)topology.edge_points[edge * 2 + side]
            for at in (usize)topology.point_edge_offsets[point]..<(usize)topology.point_edge_offsets[point + 1]:
                let next = (usize)topology.point_edges[at]
                if edge_faces(topology, next) != 1 or out.view().get(next): continue
                out.set(next)
                queue[tail] = (u32)next
                tail += 1