BREP_RANSAC 0.1.0

//! Deterministic CAD-style synthetic tessellations used by tests and benches.
use crate::{
    AnalyticSurface, ConeSurface, CylinderSurface, Mesh, PlaneSurface, SphereSurface, TorusSurface,
    Vec3,
};
use std::f64::consts::TAU;

/// Parametric domain, resolution, and deterministic perturbations for a
/// synthetic analytic patch.
#[derive(Clone, Copy, Debug)]
pub struct Patch {
    /// Inclusive parameter interval in the surface's first coordinate.
    pub u: [f64; 2],
    /// Inclusive parameter interval in the surface's second coordinate.
    pub v: [f64; 2],
    /// Number of grid cells in the first parameter direction.
    pub u_segments: usize,
    /// Number of grid cells in the second parameter direction.
    pub v_segments: usize,
    /// Small component-wise coordinate perturbation used to emulate floating
    /// point noise introduced by CAD transforms and serialization.
    pub jitter: f64,
    /// Signed displacement along the exact carrier normal. This is independent
    /// from [`Self::jitter`] so geometric noise can be varied without changing
    /// the floating-point perturbation sequence.
    pub position_noise: f64,
    /// Tangential perturbation applied only to independently supplied vertex
    /// normals, expressed as a dimensionless vector magnitude.
    pub normal_noise: f64,
    /// Randomize each grid cell's diagonal with the deterministic seed.
    pub irregular_triangulation: bool,
    /// Parameter-density exponents. `1.0` is uniform; values above one cluster
    /// vertices near the lower bound and values below one near the upper bound.
    pub density_power: [f64; 2],
    /// Deterministic seed for all independent perturbation streams.
    pub seed: u64,
}
impl Default for Patch {
    fn default() -> Self {
        Self {
            u: [0.0, 1.0],
            v: [0.0, 1.0],
            u_segments: 24,
            v_segments: 16,
            jitter: 0.0,
            position_noise: 0.0,
            normal_noise: 0.0,
            irregular_triangulation: false,
            density_power: [1.0, 1.0],
            seed: 1,
        }
    }
}

/// Tessellate an analytic patch into an indexed mesh without supplied normals.
pub fn tessellate(surface: AnalyticSurface, patch: Patch) -> Mesh {
    tessellate_impl(surface, patch, false)
}

/// Tessellate a synthetic patch and attach analytic normals generated
/// independently from position perturbations. This mirrors CAD tessellators
/// that emit derivative normals alongside their indexed positions.
pub fn tessellate_with_normals(surface: AnalyticSurface, patch: Patch) -> Mesh {
    tessellate_impl(surface, patch, true)
}

fn tessellate_impl(surface: AnalyticSurface, patch: Patch, with_normals: bool) -> Mesh {
    assert!(patch.u_segments > 0 && patch.v_segments > 0);
    assert!(patch.jitter.is_finite() && patch.jitter >= 0.0);
    assert!(patch.position_noise.is_finite() && patch.position_noise >= 0.0);
    assert!(patch.normal_noise.is_finite() && patch.normal_noise >= 0.0);
    assert!(patch
        .density_power
        .iter()
        .all(|power| power.is_finite() && *power > 0.0));
    // Independent streams ensure toggling one perturbation does not silently
    // change the realization of another.
    let mut jitter_rng = Rng(patch.seed ^ 0x4a49_5454_4552);
    let mut position_rng = Rng(patch.seed ^ 0x504f_5349_5449_4f4e);
    let mut normal_rng = Rng(patch.seed ^ 0x4e4f_524d_414c);
    let mut topology_rng = Rng(patch.seed ^ 0x544f_504f_4c4f_4759);
    let mut vertices = Vec::with_capacity((patch.u_segments + 1) * (patch.v_segments + 1));
    let mut normals =
        with_normals.then(|| Vec::with_capacity((patch.u_segments + 1) * (patch.v_segments + 1)));
    for j in 0..=patch.v_segments {
        let tv = (j as f64 / patch.v_segments as f64).powf(patch.density_power[1]);
        let v = patch.v[0] + tv * (patch.v[1] - patch.v[0]);
        for i in 0..=patch.u_segments {
            let tu = (i as f64 / patch.u_segments as f64).powf(patch.density_power[0]);
            let u = patch.u[0] + tu * (patch.u[1] - patch.u[0]);
            let exact = point(surface, u, v);
            let exact_normal = surface
                .normal_at(exact)
                .expect("synthetic surface vertex must have a normal");
            let mut p = exact;
            if patch.jitter > 0.0 {
                p += Vec3::new(
                    jitter_rng.signed(),
                    jitter_rng.signed(),
                    jitter_rng.signed(),
                ) * patch.jitter;
            }
            if patch.position_noise > 0.0 {
                p += exact_normal * (position_rng.signed() * patch.position_noise);
            }
            vertices.push(p);
            if let Some(normals) = &mut normals {
                let mut normal = exact_normal;
                if patch.normal_noise > 0.0 {
                    let (e1, e2) = frame(exact_normal);
                    normal = (normal
                        + e1 * (normal_rng.signed() * patch.normal_noise)
                        + e2 * (normal_rng.signed() * patch.normal_noise))
                        .normalized()
                        .expect("perturbed synthetic normal must be finite");
                }
                normals.push(normal);
            }
        }
    }
    let stride = patch.u_segments + 1;
    let mut triangles = Vec::with_capacity(patch.u_segments * patch.v_segments * 2);
    for j in 0..patch.v_segments {
        for i in 0..patch.u_segments {
            let a = (j * stride + i) as u32;
            let b = a + 1;
            let d = ((j + 1) * stride + i) as u32;
            let c = d + 1;
            let forward_diagonal = if patch.irregular_triangulation {
                topology_rng.next() & 1 == 0
            } else {
                (i + j) % 2 == 0
            };
            if forward_diagonal {
                triangles.push([a, b, c]);
                triangles.push([a, c, d]);
            } else {
                triangles.push([a, b, d]);
                triangles.push([b, c, d]);
            }
        }
    }
    let mut mesh = Mesh::new(vertices, triangles);
    mesh.vertex_normals = normals;
    mesh
}

fn frame(axis: Vec3) -> (Vec3, Vec3) {
    axis.orthonormal_basis().expect("valid synthetic axis")
}
fn point(surface: AnalyticSurface, u: f64, v: f64) -> Vec3 {
    match surface {
        AnalyticSurface::Plane(PlaneSurface { origin, normal }) => {
            let (e1, e2) = frame(normal);
            origin + e1 * u + e2 * v
        }
        AnalyticSurface::Sphere(SphereSurface { center, radius }) => {
            let theta = u;
            let phi = v;
            center + Vec3::new(phi.cos() * theta.cos(), phi.cos() * theta.sin(), phi.sin()) * radius
        }
        AnalyticSurface::Cylinder(CylinderSurface {
            axis_origin,
            axis,
            radius,
        }) => {
            let (e1, e2) = frame(axis);
            axis_origin + axis * v + (e1 * u.cos() + e2 * u.sin()) * radius
        }
        AnalyticSurface::Cone(ConeSurface {
            apex,
            axis,
            half_angle,
        }) => {
            let (e1, e2) = frame(axis);
            let radius = v * half_angle.tan();
            apex + axis * v + (e1 * u.cos() + e2 * u.sin()) * radius
        }
        AnalyticSurface::Torus(TorusSurface {
            center,
            axis,
            major_radius,
            minor_radius,
        }) => {
            let (e1, e2) = frame(axis);
            let radial = e1 * u.cos() + e2 * u.sin();
            center
                + radial * (major_radius + minor_radius * v.cos())
                + axis * (minor_radius * v.sin())
        }
    }
}

/// Generate the canonical full or representative patch for a primitive type.
///
/// The returned exact carrier is the ground truth for the generated mesh.
pub fn canonical(surface_type: crate::SurfaceType, segments: usize) -> (AnalyticSurface, Mesh) {
    let n = segments.max(4);
    match surface_type {
        crate::SurfaceType::Plane => {
            let s = AnalyticSurface::Plane(PlaneSurface {
                origin: Vec3::new(1., 2., 3.),
                normal: Vec3::new(0., 0., 1.),
            });
            (
                s,
                tessellate(
                    s,
                    Patch {
                        u: [-2., 2.],
                        v: [-1.5, 1.5],
                        u_segments: n,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            )
        }
        crate::SurfaceType::Sphere => {
            let s = AnalyticSurface::Sphere(SphereSurface {
                center: Vec3::new(1., -2., 0.5),
                radius: 3.,
            });
            (
                s,
                tessellate(
                    s,
                    Patch {
                        u: [0., TAU],
                        v: [-1.35, 1.35],
                        u_segments: n * 2,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            )
        }
        crate::SurfaceType::Cylinder => {
            let s = AnalyticSurface::Cylinder(CylinderSurface {
                axis_origin: Vec3::new(1., 2., -1.),
                axis: Vec3::Z,
                radius: 2.5,
            });
            (
                s,
                tessellate(
                    s,
                    Patch {
                        u: [0., TAU],
                        v: [0., 5.],
                        u_segments: n * 2,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            )
        }
        crate::SurfaceType::Cone => {
            let s = AnalyticSurface::Cone(ConeSurface {
                apex: Vec3::new(-1., 2., -3.),
                axis: Vec3::Z,
                half_angle: 0.4,
            });
            (
                s,
                tessellate(
                    s,
                    Patch {
                        u: [0., TAU],
                        v: [2., 7.],
                        u_segments: n * 2,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            )
        }
        crate::SurfaceType::Torus => {
            let s = AnalyticSurface::Torus(TorusSurface {
                center: Vec3::new(1., -1., 2.),
                axis: Vec3::Z,
                major_radius: 4.,
                minor_radius: 1.,
            });
            (
                s,
                tessellate(
                    s,
                    Patch {
                        u: [0., TAU],
                        v: [0., TAU],
                        u_segments: n * 2,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            )
        }
    }
}

/// Generate a deterministic trimmed patch of the supplied analytic carrier.
pub fn partial(surface: AnalyticSurface, segments: usize) -> Mesh {
    let n = segments.max(3);
    let patch = match surface {
        AnalyticSurface::Plane(_) => Patch {
            u: [-0.3, 0.8],
            v: [0.1, 0.7],
            u_segments: n,
            v_segments: n,
            ..Default::default()
        },
        AnalyticSurface::Sphere(_) => Patch {
            u: [0.2, 1.0],
            v: [-0.3, 0.35],
            u_segments: n,
            v_segments: n,
            ..Default::default()
        },
        AnalyticSurface::Cylinder(_) => Patch {
            u: [0.25, 0.75],
            v: [1., 4.],
            u_segments: n,
            v_segments: n,
            ..Default::default()
        },
        AnalyticSurface::Cone(_) => Patch {
            u: [0.3, 1.2],
            v: [2., 5.],
            u_segments: n,
            v_segments: n,
            ..Default::default()
        },
        AnalyticSurface::Torus(_) => Patch {
            u: [0.2, 1.1],
            v: [-0.5, 0.45],
            u_segments: n,
            v_segments: n,
            ..Default::default()
        },
    };
    tessellate(surface, patch)
}

/// Concatenate disconnected meshes while offsetting triangle indices.
///
/// Supplied vertex normals are retained only when every input has them.
pub fn merge(meshes: &[Mesh]) -> Mesh {
    let mut out = Mesh::default();
    let preserve_normals = meshes.iter().all(|mesh| mesh.vertex_normals.is_some());
    if preserve_normals {
        out.vertex_normals = Some(Vec::new());
    }
    for mesh in meshes {
        let offset = out.vertices.len() as u32;
        out.vertices.extend_from_slice(&mesh.vertices);
        if let (Some(out_normals), Some(normals)) = (&mut out.vertex_normals, &mesh.vertex_normals)
        {
            out_normals.extend_from_slice(normals);
        }
        out.triangles
            .extend(mesh.triangles.iter().map(|t| t.map(|i| i + offset)));
    }
    out
}

/// Ground-truth inventory for one analytic region of a combined model.
#[derive(Clone, Debug)]
pub struct SyntheticRegion {
    /// Stable descriptive name used by tests and benchmark reports.
    pub name: &'static str,
    /// Exact infinite analytic carrier.
    pub surface: AnalyticSurface,
    /// Triangle IDs belonging to this region in the combined mesh.
    pub triangle_indices: Vec<usize>,
}

/// CAD-like synthetic mesh with explicit analytic and unresolved truth.
#[derive(Clone, Debug)]
pub struct CombinedModel {
    /// Combined indexed mesh.
    pub mesh: Mesh,
    /// Analytic ground-truth regions.
    pub regions: Vec<SyntheticRegion>,
    /// Triangles intentionally not generated from an analytic carrier.
    pub unresolved_triangles: Vec<usize>,
}

fn combined_model(
    analytic: Vec<(&'static str, AnalyticSurface, Mesh)>,
    unresolved: Vec<Mesh>,
) -> CombinedModel {
    let mut pieces = Vec::with_capacity(analytic.len() + unresolved.len());
    let mut regions = Vec::with_capacity(analytic.len());
    let mut triangle_offset = 0;
    for (name, surface, mesh) in analytic {
        let triangle_indices =
            (triangle_offset..triangle_offset + mesh.triangles.len()).collect::<Vec<_>>();
        triangle_offset += mesh.triangles.len();
        regions.push(SyntheticRegion {
            name,
            surface,
            triangle_indices,
        });
        pieces.push(mesh);
    }
    let unresolved_start = triangle_offset;
    for mesh in unresolved {
        triangle_offset += mesh.triangles.len();
        pieces.push(mesh);
    }
    CombinedModel {
        mesh: merge(&pieces),
        regions,
        unresolved_triangles: (unresolved_start..triangle_offset).collect(),
    }
}

fn exact_patch(surface: AnalyticSurface, patch: Patch) -> Mesh {
    tessellate_with_normals(surface, patch)
}

/// Two coaxial shaft diameters separated by a planar shoulder and bounded by
/// planar end patches. Regions intentionally keep separate vertex ownership,
/// matching per-face CAD tessellation buffers.
pub fn stepped_shaft(segments: usize) -> CombinedModel {
    let n = segments.max(6);
    let large = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::ZERO,
        axis: Vec3::Z,
        radius: 2.0,
    });
    let small = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::ZERO,
        axis: Vec3::Z,
        radius: 1.25,
    });
    let planes = [
        ("lower end", 0.0, [-1.2, 1.2], [-1.2, 1.2]),
        ("shoulder", 2.0, [-2.0, 2.0], [-0.35, 0.35]),
        ("upper end", 5.0, [-0.9, 0.9], [-0.9, 0.9]),
    ];
    let mut regions = vec![
        (
            "large cylinder",
            large,
            exact_patch(
                large,
                Patch {
                    u: [0.0, TAU],
                    v: [0.0, 2.0],
                    u_segments: n * 2,
                    v_segments: n,
                    ..Default::default()
                },
            ),
        ),
        (
            "small cylinder",
            small,
            exact_patch(
                small,
                Patch {
                    u: [0.0, TAU],
                    v: [2.0, 5.0],
                    u_segments: n * 2,
                    v_segments: n,
                    ..Default::default()
                },
            ),
        ),
    ];
    for (name, z, u, v) in planes {
        let surface = AnalyticSurface::Plane(PlaneSurface {
            origin: Vec3::new(0.0, 0.0, z),
            normal: Vec3::Z,
        });
        regions.push((
            name,
            surface,
            exact_patch(
                surface,
                Patch {
                    u,
                    v,
                    u_segments: n,
                    v_segments: n / 2,
                    ..Default::default()
                },
            ),
        ));
    }
    combined_model(regions, Vec::new())
}

/// Coaxial cylinders joined by an exact conical transition with planar ends.
pub fn conical_transition(segments: usize) -> CombinedModel {
    let n = segments.max(6);
    let lower = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::ZERO,
        axis: Vec3::Z,
        radius: 2.0,
    });
    let angle = (1.0_f64 / 3.0).atan();
    let cone = AnalyticSurface::Cone(ConeSurface {
        apex: Vec3::new(0.0, 0.0, -4.0),
        axis: Vec3::Z,
        half_angle: angle,
    });
    let upper = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::ZERO,
        axis: Vec3::Z,
        radius: 3.0,
    });
    let mut regions = Vec::new();
    for (name, surface, v) in [
        ("lower cylinder", lower, [0.0, 2.0]),
        ("conical transition", cone, [6.0, 9.0]),
        ("upper cylinder", upper, [5.0, 7.0]),
    ] {
        regions.push((
            name,
            surface,
            exact_patch(
                surface,
                Patch {
                    u: [0.0, TAU],
                    v,
                    u_segments: n * 2,
                    v_segments: n,
                    ..Default::default()
                },
            ),
        ));
    }
    for (name, z, extent) in [("lower end", 0.0, 1.5), ("upper end", 7.0, 2.5)] {
        let surface = AnalyticSurface::Plane(PlaneSurface {
            origin: Vec3::new(0.0, 0.0, z),
            normal: Vec3::Z,
        });
        regions.push((
            name,
            surface,
            exact_patch(
                surface,
                Patch {
                    u: [-extent, extent],
                    v: [-extent, extent],
                    u_segments: n,
                    v_segments: n,
                    ..Default::default()
                },
            ),
        ));
    }
    combined_model(regions, Vec::new())
}

/// Cylinder and plane carriers accompanied by a quarter-torus fillet patch.
pub fn toroidal_fillet(segments: usize) -> CombinedModel {
    let n = segments.max(6);
    let cylinder = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::ZERO,
        axis: Vec3::Z,
        radius: 4.0,
    });
    let torus = AnalyticSurface::Torus(TorusSurface {
        center: Vec3::new(0.0, 0.0, 3.0),
        axis: Vec3::Z,
        major_radius: 4.0,
        minor_radius: 0.75,
    });
    let plane = AnalyticSurface::Plane(PlaneSurface {
        origin: Vec3::new(0.0, 0.0, 3.75),
        normal: Vec3::Z,
    });
    combined_model(
        vec![
            (
                "cylinder",
                cylinder,
                exact_patch(
                    cylinder,
                    Patch {
                        u: [0.0, TAU],
                        v: [0.0, 3.0],
                        u_segments: n * 2,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            ),
            (
                "toroidal fillet",
                torus,
                exact_patch(
                    torus,
                    Patch {
                        u: [0.0, TAU],
                        v: [0.0, std::f64::consts::FRAC_PI_2],
                        u_segments: n * 2,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            ),
            (
                "plane",
                plane,
                exact_patch(
                    plane,
                    Patch {
                        u: [-3.0, 3.0],
                        v: [-3.0, 3.0],
                        u_segments: n,
                        v_segments: n,
                        ..Default::default()
                    },
                ),
            ),
        ],
        Vec::new(),
    )
}

/// A small surviving analytic patch next to a deliberately non-analytic local
/// shard, representative of a partially successful boolean fallback.
pub fn localized_partial_failure(segments: usize) -> CombinedModel {
    let n = segments.max(8);
    let cylinder = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::new(2.0, -1.0, 0.5),
        axis: Vec3::new(0.2, -0.3, 0.9).normalized().unwrap(),
        radius: 5.0,
    });
    let analytic = exact_patch(
        cylinder,
        Patch {
            u: [0.35, 0.62],
            v: [1.8, 2.35],
            u_segments: n,
            v_segments: n / 2,
            irregular_triangulation: true,
            density_power: [1.7, 0.8],
            seed: 0x0050_4152_5449_414c,
            ..Default::default()
        },
    );
    let shard = Mesh::new(
        vec![
            Vec3::new(10.0, 0.0, 0.0),
            Vec3::new(11.0, 0.2, 0.1),
            Vec3::new(10.2, 1.1, -0.2),
            Vec3::new(10.4, 0.3, 1.3),
            Vec3::new(11.2, 1.0, 0.8),
        ],
        vec![
            [0, 1, 2],
            [0, 3, 1],
            [1, 3, 4],
            [2, 4, 3],
            [0, 2, 3],
            [1, 4, 2],
        ],
    );
    combined_model(
        vec![("surviving cylinder patch", cylinder, analytic)],
        vec![shard],
    )
}

/// Generate a numerically demanding very small spherical patch.
pub fn very_small_patch() -> (AnalyticSurface, Mesh) {
    let surface = AnalyticSurface::Sphere(SphereSurface {
        center: Vec3::new(1.0, -2.0, 0.5),
        radius: 3.0,
    });
    let mesh = exact_patch(
        surface,
        Patch {
            u: [0.4, 0.405],
            v: [0.2, 0.204],
            u_segments: 12,
            v_segments: 10,
            ..Default::default()
        },
    );
    (surface, mesh)
}

/// Generate a cylinder whose coordinates and radius are large in model units.
pub fn large_scale_patch() -> (AnalyticSurface, Mesh) {
    let surface = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::ZERO,
        axis: Vec3::Z,
        radius: 1.0e5,
    });
    let mesh = exact_patch(
        surface,
        Patch {
            u: [0.1, 0.7],
            v: [-2.0e5, 3.0e5],
            u_segments: 24,
            v_segments: 16,
            ..Default::default()
        },
    );
    (surface, mesh)
}

/// Generate a spherical patch translated far from the coordinate origin.
pub fn far_origin_patch() -> (AnalyticSurface, Mesh) {
    let surface = AnalyticSurface::Sphere(SphereSurface {
        center: Vec3::new(1.0e9, -2.0e9, 3.0e9),
        radius: 250.0,
    });
    let mesh = exact_patch(
        surface,
        Patch {
            u: [0.2, 1.1],
            v: [-0.4, 0.35],
            u_segments: 20,
            v_segments: 16,
            ..Default::default()
        },
    );
    (surface, mesh)
}

/// Generate a very long, narrow planar patch.
pub fn high_aspect_patch() -> (AnalyticSurface, Mesh) {
    let surface = AnalyticSurface::Plane(PlaneSurface {
        origin: Vec3::new(-3.0, 4.0, 1.0),
        normal: Vec3::new(0.2, 0.1, 0.97).normalized().unwrap(),
    });
    let mesh = exact_patch(
        surface,
        Patch {
            u: [-500.0, 500.0],
            v: [-0.005, 0.005],
            u_segments: 80,
            v_segments: 2,
            ..Default::default()
        },
    );
    (surface, mesh)
}

/// Two disconnected CAD faces whose carrier radii differ by five orders of
/// magnitude.  Keeping both in one mesh exercises component-local fitting in
/// the presence of a much larger global bounding box.
pub fn mixed_scale_model() -> CombinedModel {
    let small = AnalyticSurface::Sphere(SphereSurface {
        center: Vec3::new(0.03, -0.02, 0.01),
        radius: 1.0e-2,
    });
    let large = AnalyticSurface::Cylinder(CylinderSurface {
        axis_origin: Vec3::new(1.0e4, -2.0e4, 3.0e4),
        axis: Vec3::new(0.2, -0.3, 0.9).normalized().unwrap(),
        radius: 1.0e3,
    });
    combined_model(
        vec![
            (
                "small sphere",
                small,
                exact_patch(
                    small,
                    Patch {
                        u: [0.0, TAU],
                        v: [-1.1, 1.1],
                        u_segments: 16,
                        v_segments: 10,
                        ..Default::default()
                    },
                ),
            ),
            (
                "large cylinder",
                large,
                exact_patch(
                    large,
                    Patch {
                        u: [0.0, TAU],
                        v: [-2.0e3, 2.0e3],
                        u_segments: 20,
                        v_segments: 8,
                        ..Default::default()
                    },
                ),
            ),
        ],
        Vec::new(),
    )
}

struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9e3779b97f4a7c15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
        z ^ (z >> 31)
    }
    fn signed(&mut self) -> f64 {
        ((self.next() >> 11) as f64) * (2.0 / (1u64 << 53) as f64) - 1.0
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn all_generators_are_valid() {
        for ty in [
            crate::SurfaceType::Plane,
            crate::SurfaceType::Sphere,
            crate::SurfaceType::Cylinder,
            crate::SurfaceType::Cone,
            crate::SurfaceType::Torus,
        ] {
            let (_, m) = canonical(ty, 8);
            m.analyze(&Default::default()).unwrap();
            assert!(!m.triangles.is_empty());
        }
    }
    #[test]
    fn partial_torus_points_are_exact() {
        let (s, _) = canonical(crate::SurfaceType::Torus, 8);
        let m = partial(s, 8);
        assert!(m
            .vertices
            .iter()
            .all(|&p| s.signed_distance(p).abs() < 1e-12));
    }

    #[test]
    fn supplied_synthetic_normals_match_the_analytic_surface() {
        let (surface, _) = canonical(crate::SurfaceType::Torus, 8);
        let mesh = tessellate_with_normals(
            surface,
            Patch {
                u: [0.2, 0.7],
                v: [-0.4, 0.3],
                u_segments: 5,
                v_segments: 4,
                ..Default::default()
            },
        );
        let normals = mesh.vertex_normals.as_ref().unwrap();
        assert_eq!(normals.len(), mesh.vertices.len());
        for (&point, &normal) in mesh.vertices.iter().zip(normals) {
            assert!(normal.dot(surface.normal_at(point).unwrap()) > 1.0 - 1.0e-12);
        }
        mesh.analyze(&Default::default()).unwrap();
    }

    #[test]
    fn perturbation_streams_are_deterministic_and_independent() {
        let (surface, _) = canonical(crate::SurfaceType::Cylinder, 8);
        let base = Patch {
            u: [0.2, 0.9],
            v: [-1.0, 2.0],
            u_segments: 9,
            v_segments: 7,
            jitter: 1.0e-9,
            position_noise: 2.0e-4,
            irregular_triangulation: true,
            density_power: [1.7, 0.65],
            seed: 0x1234_5678,
            ..Default::default()
        };
        let positions_only = tessellate(surface, base);
        let first = tessellate_with_normals(
            surface,
            Patch {
                normal_noise: 3.0e-3,
                ..base
            },
        );
        let second = tessellate_with_normals(
            surface,
            Patch {
                normal_noise: 3.0e-3,
                ..base
            },
        );
        assert_eq!(first, second);
        assert_eq!(positions_only.vertices, first.vertices);
        assert_eq!(positions_only.triangles, first.triangles);
        assert!(first
            .vertex_normals
            .as_ref()
            .unwrap()
            .iter()
            .all(|normal| { normal.is_finite() && (normal.length() - 1.0).abs() < 1.0e-12 }));
    }

    #[test]
    fn density_and_irregular_topology_controls_change_only_the_requested_parts() {
        let (surface, _) = canonical(crate::SurfaceType::Plane, 8);
        let uniform = tessellate(
            surface,
            Patch {
                u_segments: 7,
                v_segments: 5,
                seed: 99,
                ..Default::default()
            },
        );
        let dense = tessellate(
            surface,
            Patch {
                u_segments: 7,
                v_segments: 5,
                density_power: [2.0, 0.5],
                seed: 99,
                ..Default::default()
            },
        );
        assert_eq!(uniform.triangles, dense.triangles);
        assert_ne!(uniform.vertices, dense.vertices);

        let irregular = tessellate(
            surface,
            Patch {
                u_segments: 7,
                v_segments: 5,
                irregular_triangulation: true,
                seed: 99,
                ..Default::default()
            },
        );
        assert_eq!(uniform.vertices, irregular.vertices);
        assert_ne!(uniform.triangles, irregular.triangles);
        irregular.analyze(&Default::default()).unwrap();
    }

    #[test]
    fn cad_combined_models_have_valid_disjoint_region_inventories() {
        for model in [
            stepped_shaft(8),
            conical_transition(8),
            toroidal_fillet(8),
            localized_partial_failure(8),
        ] {
            model.mesh.analyze(&Default::default()).unwrap();
            let mut assigned = vec![false; model.mesh.triangles.len()];
            for region in &model.regions {
                assert!(!region.triangle_indices.is_empty(), "{}", region.name);
                for &triangle in &region.triangle_indices {
                    assert!(!assigned[triangle], "overlapping region inventory");
                    assigned[triangle] = true;
                }
            }
            for &triangle in &model.unresolved_triangles {
                assert!(!assigned[triangle]);
                assigned[triangle] = true;
            }
            assert!(assigned.into_iter().all(|value| value));
        }
    }

    #[test]
    fn explicit_scale_and_aspect_cases_are_valid() {
        for (surface, mesh) in [
            very_small_patch(),
            large_scale_patch(),
            far_origin_patch(),
            high_aspect_patch(),
        ] {
            mesh.analyze(&Default::default()).unwrap();
            assert!(mesh.vertices.iter().all(|point| point.is_finite()));
            assert!(mesh
                .vertices
                .iter()
                .all(|&point| surface.signed_distance(point).abs() < 1.0e-5));
        }
    }
}