use crate::{Point3, Result, UnitVec3, Vector3};
const DEGENERATE_SIN: f64 = 1.0e-12;
pub fn compute_point_normals(points: &[Point3], faces: &[[u32; 3]]) -> Result<Vec<UnitVec3>> {
let sums = accumulate_point_normals(points, faces)?;
let mut normals = Vec::with_capacity(sums.len());
for (i, sum) in sums.iter().enumerate() {
let unit = UnitVec3::try_new(*sum, 1.0e-12).ok_or_else(|| {
format!(
"Point {i} has no well-defined normal. It belongs to no face, belongs only to \
degenerate faces, or its incident face normals cancel exactly."
)
})?;
normals.push(unit);
}
Ok(normals)
}
pub fn compute_point_normals_where_defined(
points: &[Point3],
faces: &[[u32; 3]],
) -> Result<Vec<Option<UnitVec3>>> {
let sums = accumulate_point_normals(points, faces)?;
Ok(sums
.iter()
.map(|sum| UnitVec3::try_new(*sum, 1.0e-12))
.collect())
}
fn accumulate_point_normals(points: &[Point3], faces: &[[u32; 3]]) -> Result<Vec<Vector3>> {
let mut sums = vec![Vector3::zeros(); points.len()];
for face in faces.iter() {
let p = [
*points
.get(face[0] as usize)
.ok_or("Face refers to a point which does not exist")?,
*points
.get(face[1] as usize)
.ok_or("Face refers to a point which does not exist")?,
*points
.get(face[2] as usize)
.ok_or("Face refers to a point which does not exist")?,
];
let Some(normal) = compute_face_normal(&p) else {
continue;
};
for k in 0..3 {
let e1 = p[(k + 1) % 3] - p[k];
let e2 = p[(k + 2) % 3] - p[k];
let angle = e1.cross(&e2).norm().atan2(e1.dot(&e2));
sums[face[k] as usize] += normal.into_inner() * angle;
}
}
Ok(sums)
}
pub fn compute_face_normal(p: &[Point3; 3]) -> Option<UnitVec3> {
let e1 = p[1] - p[0];
let e2 = p[2] - p[0];
let cross = e1.cross(&e2);
if cross.norm() <= DEGENERATE_SIN * e1.norm() * e2.norm() {
return None;
}
Some(UnitVec3::new_normalize(cross))
}
#[cfg(test)]
mod tests {
use super::*;
use approx::assert_relative_eq;
fn cube() -> (Vec<Point3>, Vec<[u32; 3]>) {
let mut points = Vec::new();
for x in [-1.0, 1.0] {
for y in [-1.0, 1.0] {
for z in [-1.0, 1.0] {
points.push(Point3::new(x, y, z));
}
}
}
let quads = [
[1, 5, 7, 3], [0, 2, 6, 4], [0, 4, 5, 1], [2, 3, 7, 6], [4, 6, 7, 5], [0, 1, 3, 2], ];
let mut faces = Vec::new();
for q in quads {
faces.push([q[0], q[1], q[2]]);
faces.push([q[0], q[2], q[3]]);
}
(points, faces)
}
fn flat_grid(n: u32) -> (Vec<Point3>, Vec<[u32; 3]>) {
let mut points = Vec::new();
for j in 0..n {
for i in 0..n {
points.push(Point3::new(i as f64, j as f64, 0.0));
}
}
let mut faces = Vec::new();
for j in 0..n - 1 {
for i in 0..n - 1 {
let a = j * n + i;
faces.push([a, a + 1, a + n + 1]);
faces.push([a, a + n + 1, a + n]);
}
}
(points, faces)
}
#[test]
fn cube_corners_point_along_the_diagonals() -> Result<()> {
let (points, faces) = cube();
let normals = compute_point_normals(&points, &faces)?;
assert_eq!(normals.len(), 8);
for (normal, point) in normals.iter().zip(points.iter()) {
let expected = UnitVec3::new_normalize(point.coords);
assert_relative_eq!(
normal.into_inner(),
expected.into_inner(),
epsilon = 1.0e-12
);
}
Ok(())
}
#[test]
fn the_corner_that_area_weighting_gets_wrong_is_exact() -> Result<()> {
let (points, faces) = cube();
let normals = compute_point_normals(&points, &faces)?;
assert_eq!(points[1], Point3::new(-1.0, -1.0, 1.0));
let d = 1.0 / 3.0_f64.sqrt();
assert_relative_eq!(
normals[1].into_inner(),
Vector3::new(-d, -d, d),
epsilon = 1.0e-12
);
Ok(())
}
#[test]
fn a_flat_sheet_is_normal_everywhere() -> Result<()> {
let (points, faces) = flat_grid(4);
for normal in compute_point_normals(&points, &faces)? {
assert_relative_eq!(normal.into_inner(), Vector3::z(), epsilon = 1.0e-12);
}
Ok(())
}
#[test]
fn a_smooth_surface_lands_close_to_the_analytic_normal() -> Result<()> {
let sphere = crate::Mesh3::create_sphere(1.0, 2.4e-3)?;
let normals = compute_point_normals(sphere.points(), sphere.faces())?;
let mut worst: f64 = 0.0;
for (normal, point) in normals.iter().zip(sphere.points()) {
let expected = UnitVec3::new_normalize(point.coords);
worst = worst.max(normal.angle(&expected));
}
assert!(
worst.to_degrees() < 3.0,
"worst deviation from the radial normal was {} degrees",
worst.to_degrees()
);
Ok(())
}
#[test]
fn degenerate_faces_are_skipped() -> Result<()> {
let points = vec![
Point3::new(0.0, 0.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(1.0, 1.0, 0.0),
Point3::new(0.0, 1.0, 0.0),
];
let faces = vec![[0, 1, 2], [0, 2, 3], [0, 1, 1]];
for normal in compute_point_normals(&points, &faces)? {
assert_relative_eq!(normal.into_inner(), Vector3::z(), epsilon = 1.0e-12);
}
Ok(())
}
#[test]
fn collinear_faces_are_skipped() -> Result<()> {
let points = vec![
Point3::new(0.0, 0.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(2.0, 0.0, 0.0),
Point3::new(0.0, 1.0, 0.0),
Point3::new(1.0, 1.0, 0.0),
Point3::new(2.0, 1.0, 0.0),
];
let faces = vec![[0, 1, 4], [0, 4, 3], [1, 2, 5], [1, 5, 4], [0, 1, 2]];
for normal in compute_point_normals(&points, &faces)? {
assert_relative_eq!(normal.into_inner(), Vector3::z(), epsilon = 1.0e-12);
}
Ok(())
}
#[test]
fn a_point_with_no_faces_is_an_error() {
let points = vec![
Point3::new(0.0, 0.0, 0.0),
Point3::new(1.0, 0.0, 0.0),
Point3::new(0.0, 1.0, 0.0),
Point3::new(5.0, 5.0, 5.0), ];
let faces = vec![[0, 1, 2]];
let err = compute_point_normals(&points, &faces)
.unwrap_err()
.to_string();
assert!(err.contains("Point 3"), "{err}");
}
#[test]
fn an_out_of_range_face_index_is_an_error() {
let (points, mut faces) = flat_grid(3);
faces.push([0, 1, 99]);
assert!(compute_point_normals(&points, &faces).is_err());
}
#[test]
fn scale_does_not_change_the_result() -> Result<()> {
let (big, faces) = cube();
let small: Vec<Point3> = big.iter().map(|p| *p * 1.0e-6).collect();
for (a, b) in compute_point_normals(&big, &faces)?
.iter()
.zip(compute_point_normals(&small, &faces)?.iter())
{
assert_relative_eq!(a.into_inner(), b.into_inner(), epsilon = 1.0e-12);
}
Ok(())
}
#[test]
fn face_normal_rejects_degenerate_triangles() {
let a = Point3::new(0.0, 0.0, 0.0);
let b = Point3::new(1.0, 0.0, 0.0);
assert!(compute_face_normal(&[a, b, b]).is_none());
assert!(compute_face_normal(&[a, b, Point3::new(2.0, 0.0, 0.0)]).is_none());
let n = compute_face_normal(&[a, b, Point3::new(0.0, 1.0, 0.0)]).unwrap();
assert_relative_eq!(n.into_inner(), Vector3::z(), epsilon = 1.0e-12);
}
}