//! Brush geometry validation helpers shared by editor tools and hydration.

use bevy::prelude::*;

use crate::{BrushDesc, ComponentInstanceId};
use std::collections::HashMap;

const EPSILON: f32 = 0.0001;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BrushPolygonError {
    TooFewVertices,
    NonFiniteVertex,
    DuplicateVertex,
    ZeroArea,
    SelfIntersecting,
    NonConvex,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BrushDiagnosticSeverity {
    Warning,
    Error,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BrushDiagnostic {
    pub severity: BrushDiagnosticSeverity,
    pub face: Option<ComponentInstanceId>,
    pub message: String,
}

#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct BrushValidationReport {
    pub diagnostics: Vec<BrushDiagnostic>,
}

impl BrushValidationReport {
    pub fn is_valid(&self) -> bool {
        !self
            .diagnostics
            .iter()
            .any(|diagnostic| diagnostic.severity == BrushDiagnosticSeverity::Error)
    }

    pub fn push(
        &mut self,
        severity: BrushDiagnosticSeverity,
        face: Option<ComponentInstanceId>,
        message: impl Into<String>,
    ) {
        self.diagnostics.push(BrushDiagnostic {
            severity,
            face,
            message: message.into(),
        });
    }
}

pub fn validate_brush(brush: &BrushDesc) -> BrushValidationReport {
    let mut report = BrushValidationReport::default();
    if brush.faces.is_empty() {
        report.push(BrushDiagnosticSeverity::Error, None, "Brush has no faces.");
        return report;
    }

    for face in &brush.faces {
        if face.vertices.len() < 3 {
            report.push(
                BrushDiagnosticSeverity::Error,
                Some(face.id.clone()),
                "Face has fewer than three vertices.",
            );
            continue;
        }
        if !face.vertices.iter().all(|vertex| vertex.is_finite()) {
            report.push(
                BrushDiagnosticSeverity::Error,
                Some(face.id.clone()),
                "Face contains non-finite vertex coordinates.",
            );
        }
        for i in 0..face.vertices.len() {
            for j in (i + 1)..face.vertices.len() {
                if face.vertices[i].distance_squared(face.vertices[j]) <= EPSILON * EPSILON {
                    report.push(
                        BrushDiagnosticSeverity::Error,
                        Some(face.id.clone()),
                        "Face contains duplicate vertices.",
                    );
                    break;
                }
            }
        }
        if face.plane.normal.try_normalize().is_none() {
            report.push(
                BrushDiagnosticSeverity::Error,
                Some(face.id.clone()),
                "Face plane normal is invalid.",
            );
        }
        if polygon_area_3d(&face.vertices) <= EPSILON {
            report.push(
                BrushDiagnosticSeverity::Error,
                Some(face.id.clone()),
                "Face area is zero or degenerate.",
            );
        }
        if let (Some(plane_normal), Some(geometry_normal)) = (
            face.plane.normal.try_normalize(),
            polygon_normal_3d(&face.vertices),
        ) {
            if plane_normal.dot(geometry_normal) < -0.5 {
                report.push(
                    BrushDiagnosticSeverity::Error,
                    Some(face.id.clone()),
                    "Face plane normal is inverted relative to its vertices.",
                );
            }
        }
        if !face.uv_scale.is_finite() || face.uv_scale.cmpeq(Vec2::ZERO).any() {
            report.push(
                BrushDiagnosticSeverity::Warning,
                Some(face.id.clone()),
                "Face UV scale is zero or non-finite.",
            );
        }
        if !face.uv_offset.is_finite() {
            report.push(
                BrushDiagnosticSeverity::Warning,
                Some(face.id.clone()),
                "Face UV offset is non-finite.",
            );
        }
        if !face.uv_rotation.is_finite() {
            report.push(
                BrushDiagnosticSeverity::Warning,
                Some(face.id.clone()),
                "Face UV rotation is non-finite.",
            );
        }
    }

    let non_manifold_edges = count_non_manifold_edges(brush);
    if non_manifold_edges > 0 {
        report.push(
            BrushDiagnosticSeverity::Error,
            None,
            format!("Brush has {non_manifold_edges} open or non-manifold edge(s)."),
        );
    }

    report
}

pub fn signed_area_xz(vertices: &[Vec3]) -> f32 {
    if vertices.len() < 3 {
        return 0.0;
    }
    vertices
        .iter()
        .zip(vertices.iter().cycle().skip(1))
        .take(vertices.len())
        .map(|(a, b)| a.x * b.z - b.x * a.z)
        .sum::<f32>()
        * 0.5
}

pub fn normalize_floor_polygon(vertices: &[Vec3]) -> Result<Vec<Vec3>, BrushPolygonError> {
    if vertices.len() < 3 {
        return Err(BrushPolygonError::TooFewVertices);
    }
    if !vertices.iter().all(|vertex| vertex.is_finite()) {
        return Err(BrushPolygonError::NonFiniteVertex);
    }

    let mut normalized = Vec::with_capacity(vertices.len());
    for vertex in vertices {
        if normalized.last().is_some_and(|previous: &Vec3| {
            previous.xz().distance_squared(vertex.xz()) <= EPSILON * EPSILON
        }) {
            continue;
        }
        normalized.push(*vertex);
    }
    if normalized.len() >= 2
        && normalized[0]
            .xz()
            .distance_squared(normalized[normalized.len() - 1].xz())
            <= EPSILON * EPSILON
    {
        normalized.pop();
    }
    if normalized.len() < 3 {
        return Err(BrushPolygonError::TooFewVertices);
    }

    for i in 0..normalized.len() {
        for j in (i + 1)..normalized.len() {
            if normalized[i].xz().distance_squared(normalized[j].xz()) <= EPSILON * EPSILON {
                return Err(BrushPolygonError::DuplicateVertex);
            }
        }
    }
    Ok(normalized)
}

pub fn validate_simple_floor_polygon(vertices: &[Vec3]) -> Result<(), BrushPolygonError> {
    let vertices = normalize_floor_polygon(vertices)?;
    let area = signed_area_xz(&vertices);
    if self_intersects_xz(&vertices) {
        return Err(BrushPolygonError::SelfIntersecting);
    }
    if area.abs() <= EPSILON {
        return Err(BrushPolygonError::ZeroArea);
    }
    Ok(())
}

pub fn validate_floor_polygon(vertices: &[Vec3]) -> Result<(), BrushPolygonError> {
    let vertices = normalize_floor_polygon(vertices)?;
    validate_simple_floor_polygon(&vertices)?;
    if !is_convex_xz(&vertices) {
        return Err(BrushPolygonError::NonConvex);
    }
    Ok(())
}

pub fn decompose_floor_polygon_to_convex(
    vertices: &[Vec3],
) -> Result<Vec<Vec<Vec3>>, BrushPolygonError> {
    let mut vertices = normalize_floor_polygon(vertices)?;
    validate_simple_floor_polygon(&vertices)?;
    if is_convex_xz(&vertices) {
        if signed_area_xz(&vertices) < 0.0 {
            vertices.reverse();
        }
        return Ok(vec![vertices]);
    }

    if signed_area_xz(&vertices) < 0.0 {
        vertices.reverse();
    }

    let mut remaining = vertices;
    let mut triangles = Vec::with_capacity(remaining.len().saturating_sub(2));
    while remaining.len() > 3 {
        let Some(ear_index) = find_ear_xz(&remaining) else {
            return Err(BrushPolygonError::NonConvex);
        };
        let prev = (ear_index + remaining.len() - 1) % remaining.len();
        let next = (ear_index + 1) % remaining.len();
        triangles.push(vec![remaining[prev], remaining[ear_index], remaining[next]]);
        remaining.remove(ear_index);
    }
    triangles.push(remaining);
    Ok(merge_convex_parts(triangles))
}

fn merge_convex_parts(mut parts: Vec<Vec<Vec3>>) -> Vec<Vec<Vec3>> {
    let mut merged_any = true;
    while merged_any {
        merged_any = false;
        'pairs: for a in 0..parts.len() {
            for b in (a + 1)..parts.len() {
                let Some(merged) = merge_convex_pair(&parts[a], &parts[b]) else {
                    continue;
                };
                parts[a] = merged;
                parts.remove(b);
                merged_any = true;
                break 'pairs;
            }
        }
    }
    parts
}

fn merge_convex_pair(a: &[Vec3], b: &[Vec3]) -> Option<Vec<Vec3>> {
    let mut edges = Vec::<(Vec3, Vec3)>::with_capacity(a.len() + b.len());
    for part in [a, b] {
        for index in 0..part.len() {
            edges.push((part[index], part[(index + 1) % part.len()]));
        }
    }

    let mut boundary = Vec::<(Vec3, Vec3)>::new();
    let mut removed_shared_edges = 0;
    for (index, edge) in edges.iter().enumerate() {
        let is_reversed_duplicate = edges.iter().enumerate().any(|(other_index, other)| {
            index != other_index && same_point_xz(edge.0, other.1) && same_point_xz(edge.1, other.0)
        });
        if is_reversed_duplicate {
            removed_shared_edges += 1;
        } else {
            boundary.push(*edge);
        }
    }
    if removed_shared_edges != 2 || boundary.len() < 3 {
        return None;
    }

    let mut polygon = Vec::with_capacity(boundary.len());
    let first = boundary.remove(0);
    polygon.push(first.0);
    let mut current = first.1;
    while !boundary.is_empty() {
        let next_index = boundary
            .iter()
            .position(|edge| same_point_xz(edge.0, current))?;
        let (_, next) = boundary.remove(next_index);
        if !same_point_xz(current, polygon[0]) {
            polygon.push(current);
        }
        current = next;
    }
    if !same_point_xz(current, polygon[0]) {
        return None;
    }

    let mut polygon = normalize_floor_polygon(&polygon).ok()?;
    if signed_area_xz(&polygon) < 0.0 {
        polygon.reverse();
    }
    validate_floor_polygon(&polygon).ok()?;
    Some(polygon)
}

fn find_ear_xz(vertices: &[Vec3]) -> Option<usize> {
    vertices.iter().enumerate().find_map(|(index, current)| {
        let prev_index = (index + vertices.len() - 1) % vertices.len();
        let next_index = (index + 1) % vertices.len();
        let prev = vertices[prev_index];
        let next = vertices[next_index];
        if orient_xz(prev, *current, next) <= EPSILON {
            return None;
        }
        let contains_other_vertex = vertices.iter().enumerate().any(|(candidate, point)| {
            candidate != prev_index
                && candidate != index
                && candidate != next_index
                && point_in_triangle_xz(*point, prev, *current, next)
        });
        (!contains_other_vertex).then_some(index)
    })
}

fn point_in_triangle_xz(point: Vec3, a: Vec3, b: Vec3, c: Vec3) -> bool {
    let ab = orient_xz(a, b, point);
    let bc = orient_xz(b, c, point);
    let ca = orient_xz(c, a, point);
    ab >= -EPSILON && bc >= -EPSILON && ca >= -EPSILON
}

fn same_point_xz(a: Vec3, b: Vec3) -> bool {
    a.xz().distance_squared(b.xz()) <= EPSILON * EPSILON
}

fn self_intersects_xz(vertices: &[Vec3]) -> bool {
    for a in 0..vertices.len() {
        let b = (a + 1) % vertices.len();
        for c in (a + 1)..vertices.len() {
            let d = (c + 1) % vertices.len();
            if a == c || a == d || b == c || b == d {
                continue;
            }
            if segments_intersect_xz(vertices[a], vertices[b], vertices[c], vertices[d]) {
                return true;
            }
        }
    }
    false
}

fn segments_intersect_xz(a: Vec3, b: Vec3, c: Vec3, d: Vec3) -> bool {
    let ab_c = orient_xz(a, b, c);
    let ab_d = orient_xz(a, b, d);
    let cd_a = orient_xz(c, d, a);
    let cd_b = orient_xz(c, d, b);
    ab_c.signum() != ab_d.signum() && cd_a.signum() != cd_b.signum()
}

fn is_convex_xz(vertices: &[Vec3]) -> bool {
    let winding = signed_area_xz(vertices).signum();
    vertices.iter().enumerate().all(|(index, current)| {
        let prev = vertices[(index + vertices.len() - 1) % vertices.len()];
        let next = vertices[(index + 1) % vertices.len()];
        let turn = orient_xz(prev, *current, next);
        turn.abs() <= EPSILON || turn.signum() == winding
    })
}

fn orient_xz(a: Vec3, b: Vec3, c: Vec3) -> f32 {
    let ab = b.xz() - a.xz();
    let ac = c.xz() - a.xz();
    ab.x * ac.y - ab.y * ac.x
}

fn polygon_area_3d(vertices: &[Vec3]) -> f32 {
    if vertices.len() < 3 {
        return 0.0;
    }
    let origin = vertices[0];
    let mut area = 0.0;
    for index in 1..(vertices.len() - 1) {
        area += (vertices[index] - origin)
            .cross(vertices[index + 1] - origin)
            .length()
            * 0.5;
    }
    area
}

fn polygon_normal_3d(vertices: &[Vec3]) -> Option<Vec3> {
    if vertices.len() < 3 || !vertices.iter().all(|vertex| vertex.is_finite()) {
        return None;
    }
    let origin = vertices[0];
    let mut normal = Vec3::ZERO;
    for index in 1..(vertices.len() - 1) {
        normal += (vertices[index] - origin).cross(vertices[index + 1] - origin);
    }
    normal.try_normalize()
}

fn count_non_manifold_edges(brush: &BrushDesc) -> usize {
    let mut edge_counts = HashMap::<(QuantizedVertex, QuantizedVertex), usize>::new();
    for face in &brush.faces {
        if face.vertices.len() < 3 || !face.vertices.iter().all(|vertex| vertex.is_finite()) {
            continue;
        }
        for index in 0..face.vertices.len() {
            let a = QuantizedVertex::from(face.vertices[index]);
            let b = QuantizedVertex::from(face.vertices[(index + 1) % face.vertices.len()]);
            if a == b {
                continue;
            }
            let edge = if a <= b { (a, b) } else { (b, a) };
            *edge_counts.entry(edge).or_default() += 1;
        }
    }
    edge_counts.values().filter(|count| **count != 2).count()
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
struct QuantizedVertex {
    x: i64,
    y: i64,
    z: i64,
}

impl From<Vec3> for QuantizedVertex {
    fn from(value: Vec3) -> Self {
        Self {
            x: (value.x / EPSILON).round() as i64,
            y: (value.y / EPSILON).round() as i64,
            z: (value.z / EPSILON).round() as i64,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn p(x: f32, z: f32) -> Vec3 {
        Vec3::new(x, 0.0, z)
    }

    #[test]
    fn validates_convex_floor_polygon() {
        assert!(validate_floor_polygon(&[p(-1.0, -1.0), p(1.0, -1.0), p(1.0, 1.0)]).is_ok());
    }

    #[test]
    fn rejects_self_intersecting_polygon() {
        assert_eq!(
            validate_floor_polygon(&[p(-1.0, -1.0), p(1.0, 1.0), p(1.0, -1.0), p(-1.0, 1.0),]),
            Err(BrushPolygonError::SelfIntersecting)
        );
    }

    #[test]
    fn rejects_non_convex_polygon() {
        assert_eq!(
            validate_floor_polygon(&[
                p(-1.0, -1.0),
                p(1.0, -1.0),
                p(0.0, 0.0),
                p(1.0, 1.0),
                p(-1.0, 1.0),
            ]),
            Err(BrushPolygonError::NonConvex)
        );
    }

    #[test]
    fn normalizes_adjacent_and_closing_duplicate_floor_points() {
        let normalized = normalize_floor_polygon(&[
            p(-1.0, -1.0),
            p(-1.0, -1.0),
            p(1.0, -1.0),
            p(1.0, 1.0),
            p(-1.0, 1.0),
            p(-1.0, -1.0),
        ])
        .expect("normalized polygon");

        assert_eq!(normalized.len(), 4);
        assert!(validate_floor_polygon(&normalized).is_ok());
    }

    #[test]
    fn decomposes_concave_floor_polygon_into_convex_parts() {
        let parts = decompose_floor_polygon_to_convex(&[
            p(-1.0, -1.0),
            p(1.0, -1.0),
            p(0.0, 0.0),
            p(1.0, 1.0),
            p(-1.0, 1.0),
        ])
        .expect("convex decomposition");

        assert_eq!(parts.len(), 2);
        for part in parts {
            assert!(validate_floor_polygon(&part).is_ok());
        }
    }

    #[test]
    fn merges_l_shaped_floor_polygon_to_two_convex_parts() {
        let parts = decompose_floor_polygon_to_convex(&[
            p(0.0, 0.0),
            p(4.0, 0.0),
            p(4.0, 1.0),
            p(1.0, 1.0),
            p(1.0, 4.0),
            p(0.0, 4.0),
        ])
        .expect("convex decomposition");

        assert_eq!(parts.len(), 2);
        for part in parts {
            assert!(validate_floor_polygon(&part).is_ok());
        }
    }

    #[test]
    fn reports_invalid_brush_faces() {
        let mut brush = BrushDesc::default();
        brush.faces[0].vertices.clear();
        let report = validate_brush(&brush);
        assert!(!report.is_valid());
        assert!(report
            .diagnostics
            .iter()
            .any(|diagnostic| diagnostic.message.contains("fewer than three")));
    }

    #[test]
    fn reports_uv_warnings_without_invalidating_brush() {
        let mut brush = BrushDesc::default();
        brush.faces[0].uv_scale = Vec2::ZERO;
        brush.faces[1].uv_offset = Vec2::new(f32::NAN, 0.0);
        brush.faces[2].uv_rotation = f32::INFINITY;
        let report = validate_brush(&brush);
        assert!(report.is_valid());
        assert_eq!(
            report
                .diagnostics
                .iter()
                .filter(|diagnostic| diagnostic.severity == BrushDiagnosticSeverity::Warning)
                .count(),
            3
        );
        assert!(report
            .diagnostics
            .iter()
            .any(|diagnostic| diagnostic.message.contains("UV offset")));
        assert!(report
            .diagnostics
            .iter()
            .any(|diagnostic| diagnostic.message.contains("UV rotation")));
    }

    #[test]
    fn reports_inverted_face_normals() {
        let mut brush = BrushDesc::default();
        brush.faces[0].plane.normal = -brush.faces[0].plane.normal;
        let report = validate_brush(&brush);
        assert!(!report.is_valid());
        assert!(report
            .diagnostics
            .iter()
            .any(|diagnostic| diagnostic.message.contains("inverted")));
    }

    #[test]
    fn reports_open_edges() {
        let mut brush = BrushDesc::default();
        brush.faces.pop();
        let report = validate_brush(&brush);
        assert!(!report.is_valid());
        assert!(report
            .diagnostics
            .iter()
            .any(|diagnostic| diagnostic.message.contains("non-manifold")));
    }

    #[test]
    fn validates_extruded_prism_winding() {
        let brush = BrushDesc::extruded_prism(
            &[p(-1.0, -1.0), p(1.0, -1.0), p(1.0, 1.0), p(-1.0, 1.0)],
            1.0,
        )
        .expect("valid prism");
        let report = validate_brush(&brush);
        assert!(
            report.is_valid(),
            "unexpected diagnostics: {:?}",
            report.diagnostics
        );
    }
}
