Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.9

0.7.9 / src / geometries / shading / smooth_normals.lucb

## Smooth shading normals, the kernels of ShadingCache: each corner averages
## the normals of the faces around its point, weighted by their angle there,
## over the faces within the cusp angle of its own face (60 degrees, as
## Houdini's default), so hard edges stay hard. Where no two faces at a point
## lie past the cusp of each other, all its corners agree and one normal per
## point serves them. A mesh with the edge mark `sharp` (the Hard Edges, Soft
## Edges and Smooth by Angle tools' attribute, Blender's sharp edges and
## Maya's hard and soft edges) shades by its edges instead: the faces round a
## point fall into fans split at its edges marked hard (sharp > 0), joined
## across edges marked soft (sharp < 0), and across an unmarked edge when its
## two faces meet within the cusp; each corner takes its fan's normal. All
## passes run in parallel and share nothing.
from luce_std import math
from core.attributes import Attribute
import memory
from luce_std import parallel
from core.float3 import Float3
from math.vector import Vector3
import core.ranges
from core.bits import trailing_zeros

## cos(60 degrees): faces meeting at a sharper angle keep separate normals.
let cusp_cosine: f64 = 0.5

## The arrays smooth normals read.
pub struct Surface:
    pub let positions: const Float3[]
    pub let offsets: const i32[]
    pub let corners: const i32[]
    pub let normals: const Float3[]
    pub let incident_offsets: const i32[]
    pub let incident_faces: const i32[]
    ## The edge marks, when the mesh has `sharp` on its edges.
    pub let marks: const EdgeMarks*? = none

## What shading by edge marks reads: each corner's face and edge (the edge
## to the next corner), each edge's corners, and the `sharp` mark per edge
## (above 0 hard, below 0 soft, 0 by the cusp).
pub struct EdgeMarks:
    pub let corner_faces: const i32[]
    pub let corner_edges: const i32[]
    pub let edge_corner_offsets: const i32[]
    pub let edge_corners: const i32[]
    pub let sharp: const Attribute*

## Every point's normal into `output`, and whether each point's corners split
## at a cusp (`split`); true when any point does.
pub func point_normals(shape: const Surface*, output: Float3[], split: bool[]) -> bool:
    var work = PointWork(shape, output, split)
    ranges.each_range(shape.positions.length, 2048, (void*)&work, points_range)
    return work.splits.load(.acquire) != 0

## Every corner's normal: its point's where the point does not split, else
## the average over the faces within the cusp of the corner's own face.
pub func corner_normals(shape: const Surface*, points: const Float3[], split: const bool[], output: Float3[]):
    var work = CornerWork(shape, points, split, output)
    ranges.each_range(shape.offsets.length - 1, 2048, (void*)&work, corners_range)

## Every point of a face around a moved point, ascending, each once; the
## caller frees the list. The work is the moved points' neighbourhood's,
## whatever the mesh's size.
pub func affected_points(shape: const Surface*, moved: const u32[]) -> u32[]!:
    # The points of the faces round each moved point, each once, in
    # ascending order: marked in a bit per point over the span they reach,
    # then read off in order (a sort of every corner took most of a sculpt
    # stroke's frame on a 1M-face mesh).
    var low = shape.incident_offsets.length
    var high: usize = 0
    for point in moved:
        for at in (usize)shape.incident_offsets[(usize)point]..<(usize)shape.incident_offsets[(usize)point + 1]:
            let face = (usize)shape.incident_faces[at]
            for corner in (usize)shape.offsets[face]..<(usize)shape.offsets[face + 1]:
                let reached = (usize)shape.corners[corner]
                low = reached if reached < low else low
                high = reached if reached > high else high
    if low > high: return try new u32[0] --- in memory.heap
    let words = (high - low) // 64 + 1
    let marks = try new u64[words] --- in memory.heap
    defer free(marks) in memory.heap
    memory.set(u8[]((u8*)marks.data, words * 8), 0)
    var count: usize = 0
    for point in moved:
        for at in (usize)shape.incident_offsets[(usize)point]..<(usize)shape.incident_offsets[(usize)point + 1]:
            let face = (usize)shape.incident_faces[at]
            for corner in (usize)shape.offsets[face]..<(usize)shape.offsets[face + 1]:
                let bit = (usize)shape.corners[corner] - low
                let mask = (u64)1 << (u64)(bit % 64)
                if marks[bit // 64] & mask == 0:
                    marks[bit // 64] = marks[bit // 64] | mask
                    count += 1
    let affected = try new u32[count] --- in memory.heap
    var kept: usize = 0
    for word in 0..<words:
        var bits = marks[word]
        while bits != 0:
            affected[kept] = (u32)(low + word * 64 + (usize)trailing_zeros(bits))
            kept += 1
            bits = bits & (bits - 1)
    return affected

## Redo the per-point normals of `points` into `output` (point p at
## p - `offset`), marking in `split` (the same way) those that now split at a
## cusp; true when any does (per-point storage no longer holds).
pub func refresh_points(shape: const Surface*, points: const u32[], output: Float3[], split: bool[], offset: usize = 0) -> bool:
    var work = RefreshWork(shape, points, output, split, offset)
    ranges.each_range(points.length, 1024, (void*)&work, refresh_range)
    return work.splits.load(.acquire) != 0

## Redo the per-corner normals at `points` into `output` (corner c at c -
## `offset`).
pub func refresh_corners(shape: const Surface*, points: const u32[], output: Float3[], offset: usize = 0):
    var none_split: bool[]
    var work = RefreshWork(shape, points, output, none_split, offset)
    ranges.each_range(points.length, 1024, (void*)&work, corners_at_range)

struct PointWork:
    let shape: const Surface*
    let output: Float3[]
    let split: bool[]
    var splits: @u32

func points_range(context: void*, first: usize, end: usize, worker: usize):
    let work = (PointWork*)context
    for point in first..<end:
        let result = point_normal(work.shape, point)
        work.output[point] = Float3.of(result.0)
        work.split[point] = result.1
        if result.1: work.splits.store(1, .relaxed)

struct CornerWork:
    let shape: const Surface*
    let points: const Float3[]
    let split: const bool[]
    let output: Float3[]

func corners_range(context: void*, first: usize, end: usize, worker: usize):
    let work = (CornerWork*)context
    for face in first..<end:
        for corner in (usize)work.shape.offsets[face]..<(usize)work.shape.offsets[face + 1]:
            let point = (usize)work.shape.corners[corner]
            work.output[corner] = Float3.of(corner_normal(work.shape, face, corner)) if work.split[point] else work.points[point]

struct RefreshWork:
    let shape: const Surface*
    let points: const u32[]
    let output: Float3[]
    let split: bool[]
    let offset: usize
    var splits: @u32

func refresh_range(context: void*, first: usize, end: usize, worker: usize):
    let work = (RefreshWork*)context
    for at in first..<end:
        let point = (usize)work.points[at]
        let result = point_normal(work.shape, point)
        work.output[point - work.offset] = Float3.of(result.0)
        work.split[point - work.offset] = result.1
        if result.1: work.splits.store(1, .relaxed)

func corners_at_range(context: void*, first: usize, end: usize, worker: usize):
    let work = (RefreshWork*)context
    let shape = work.shape
    for at in first..<end:
        let point = work.points[at]
        for index in (usize)shape.incident_offsets[(usize)point]..<(usize)shape.incident_offsets[(usize)point + 1]:
            let face = (usize)shape.incident_faces[index]
            for corner in (usize)shape.offsets[face]..<(usize)shape.offsets[face + 1]:
                if (u32)shape.corners[corner] == point:
                    work.output[corner - work.offset] = Float3.of(corner_normal(shape, face, corner))

## A point's angle-weighted average over all its faces, and whether any two
## of them lie past the cusp of each other.
pub func point_normal(shape: const Surface*, point: usize) -> (Vector3, bool):
    if let marks = shape.marks: return marked_point_normal(shape, marks, point)
    let first = (usize)shape.incident_offsets[point]
    let end = (usize)shape.incident_offsets[point + 1]
    var sum = Vector3()
    var split = false
    for index in first..<end:
        let face = (usize)shape.incident_faces[index]
        let normal = shape.normals[face].vector()
        for other in first..<index:
            split = split or normal.dot(shape.normals[(usize)shape.incident_faces[other]].vector()) < cusp_cosine
        sum = sum.add(normal.multiply_scalar(corner_angle(shape, face, point)))
    let length = sum.length()
    if length > 1e-20: return (sum.multiply_scalar(1.0 / length), split)
    if end > first: return (shape.normals[(usize)shape.incident_faces[first]].vector(), split)
    return (Vector3(0.0, 1.0, 0.0), split)

## The angle-weighted normal of `corner` (of `face`) over the faces around its
## point within the cusp angle; the face normal when they cancel.
pub func corner_normal(shape: const Surface*, face: usize, corner: usize) -> Vector3:
    if let marks = shape.marks: return fan_normal(shape, marks, face, corner).0
    let own = shape.normals[face].vector()
    let point = (usize)shape.corners[corner]
    var sum = Vector3()
    for index in (usize)shape.incident_offsets[point]..<(usize)shape.incident_offsets[point + 1]:
        let other = (usize)shape.incident_faces[index]
        let normal = shape.normals[other].vector()
        if normal.dot(own) < cusp_cosine: continue
        sum = sum.add(normal.multiply_scalar(corner_angle(shape, other, point)))
    let length = sum.length()
    return sum.multiply_scalar(1.0 / length) if length > 1e-20 else own

## The interior angle of `face` at `point` (its first corner there).
func corner_angle(shape: const Surface*, face: usize, point: usize) -> f64:
    let start = (usize)shape.offsets[face]
    let count = (usize)shape.offsets[face + 1] - start
    for at in 0..<count:
        if (usize)shape.corners[start + at] != point: continue
        let here = shape.positions[point].vector()
        let previous = shape.positions[(usize)shape.corners[start + (at + count - 1) % count]].vector().subtract(here)
        let next = shape.positions[(usize)shape.corners[start + (at + 1) % count]].vector().subtract(here)
        let lengths = previous.length() * next.length()
        if lengths <= 1e-30: return 0.0
        return math.acos(math.max(-1.0, math.min(1.0, previous.dot(next) / lengths)))
    return 0.0

## A point's normal by its edge marks: its first face's fan, and whether the
## faces round it fall into more than one fan.
func marked_point_normal(shape: const Surface*, marks: const EdgeMarks*, point: usize) -> (Vector3, bool):
    let first = (usize)shape.incident_offsets[point]
    let end = (usize)shape.incident_offsets[point + 1]
    if end == first: return (Vector3(0.0, 1.0, 0.0), false)
    let face = (usize)shape.incident_faces[first]
    let corner = corner_at(shape, face, point)
    let fan = fan_normal(shape, marks, face, corner)
    return (fan.0, fan.1 < end - first)

## The corner of `face` at `point` (its first there).
func corner_at(shape: const Surface*, face: usize, point: usize) -> usize:
    for corner in (usize)shape.offsets[face]..<(usize)shape.offsets[face + 1]:
        if (usize)shape.corners[corner] == point: return corner
    return (usize)shape.offsets[face]

## The angle-weighted normal of the fan of faces round `corner`'s point
## that `face` lies in (walked both ways round the point across the edges
## that do not split), and how many faces the fan holds.
func fan_normal(shape: const Surface*, marks: const EdgeMarks*, face: usize, corner: usize) -> (Vector3, usize):
    let point = (usize)shape.corners[corner]
    let around = (usize)shape.incident_offsets[point + 1] - (usize)shape.incident_offsets[point]
    var sum = shape.normals[face].vector().multiply_scalar(corner_angle(shape, face, point))
    var count: usize = 1
    # Forward across the edge leaving the corner, then (unless the walk came
    # round to `face`) backward across the edge arriving at it.
    let forward = walk_fan(shape, marks, face, corner, (usize)marks.corner_edges[corner], around)
    sum = sum.add(forward.0)
    count += forward.1
    if not forward.2:
        let backward = walk_fan(shape, marks, face, corner, (usize)marks.corner_edges[previous_corner(shape, face, corner)], around)
        sum = sum.add(backward.0)
        count += backward.1
    let length = sum.length()
    return (sum.multiply_scalar(1.0 / length) if length > 1e-20 else shape.normals[face].vector(), count)

## From `face` (its `corner` at the point) across `edge` and on round the
## point while the edges do not split: the faces' weighted normals, how many,
## and whether the walk came back to `face` (a closed fan). At most `limit`
## faces are taken, so a tangled point cannot loop.
func walk_fan(shape: const Surface*, marks: const EdgeMarks*, face: usize, corner: usize, edge: usize, limit: usize) -> (Vector3, usize, bool):
    let point = (usize)shape.corners[corner]
    var sum = Vector3()
    var count: usize = 0
    var here = face
    var crossing = edge
    while count < limit:
        let first = (usize)marks.edge_corner_offsets[crossing]
        if (usize)marks.edge_corner_offsets[crossing + 1] - first != 2: break
        var other = (usize)marks.edge_corners[first]
        if (usize)marks.corner_faces[other] == here: other = (usize)marks.edge_corners[first + 1]
        let next = (usize)marks.corner_faces[other]
        if next == here: break
        if splits(shape, marks, crossing, here, next): break
        if next == face: return (sum, count, true)
        # The next face's corner at the point, and its other edge there.
        let at = other if (usize)shape.corners[other] == point else next_corner(shape, next, other)
        let before = previous_corner(shape, next, at)
        crossing = (usize)marks.corner_edges[before] if (usize)marks.corner_edges[at] == crossing else (usize)marks.corner_edges[at]
        sum = sum.add(shape.normals[next].vector().multiply_scalar(corner_angle(shape, next, point)))
        count += 1
        here = next
    return (sum, count, false)

## Whether `edge` between faces `a` and `b` splits their shading.
func splits(shape: const Surface*, marks: const EdgeMarks*, edge: usize, a: usize, b: usize) -> bool:
    let mark = marks.sharp.number(edge, 0)
    if mark > 0.0: return true
    if mark < 0.0: return false
    return shape.normals[a].vector().dot(shape.normals[b].vector()) < cusp_cosine

func next_corner(shape: const Surface*, face: usize, corner: usize) -> usize:
    return corner + 1 if corner + 1 < (usize)shape.offsets[face + 1] else (usize)shape.offsets[face]

func previous_corner(shape: const Surface*, face: usize, corner: usize) -> usize:
    return corner - 1 if corner > (usize)shape.offsets[face] else (usize)shape.offsets[face + 1] - 1