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