use strafesnet_common::{model,integer};
use strafesnet_common::integer::fixed_types::F192_96;
use strafesnet_common::integer::vec3::Vector3;
use strafesnet_common::integer::{Planar64,Planar64Vec3,Ratio};

use crate::{valve_transform_normal,valve_transform_dist};

#[derive(Hash,Eq,PartialEq)]
struct Face{
	normal:Planar64Vec3,
	dot:Planar64,
}

#[derive(Debug)]
struct Faces{
	faces:Vec<Vec<Planar64Vec3>>,
}

fn solve3(c0:&Face,c1:&Face,c2:&Face)->Option<Ratio<Vector3<F192_96>,F192_96>>{
	let n0_n1=c0.normal.cross(c1.normal);
	let det=c2.normal.dot(n0_n1);
	if det.abs().is_zero(){
		return None;
	}
	Some((
		c1.normal.cross(c2.normal)*c0.dot
		+c2.normal.cross(c0.normal)*c1.dot
		+c0.normal.cross(c1.normal)*c2.dot
	)/det)
}

#[derive(Debug)]
pub enum PlanesToFacesError{
	InitFace1,
	InitFace2,
	InitIntersection,
	FindNewIntersection,
	// Narrow(strafesnet_common::integer::NarrowError),
	EmptyFaces,
	InfiniteLoop1,
	InfiniteLoop2,
}
impl std::fmt::Display for PlanesToFacesError{
	fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{
		write!(f,"{self:?}")
	}
}
impl core::error::Error for PlanesToFacesError{}

fn planes_to_faces(face_list:std::collections::HashSet<Face>)->Result<Faces,PlanesToFacesError>{
	let mut faces=Vec::new();
	// for each face, determine one edge at a time until you complete the face
	'face: for face0 in &face_list{
		// 1. find first edge
		// 2. follow edges around face

		// === finding first edge ===
		// 1. pick the most perpendicular set of 3 faces
		// 2. check if any faces occlude the intersection
		// 3. use this test to replace left and right alternating until they are not occluded

		// find the most perpendicular face to face0
		let mut face1=face_list.iter().min_by_key(|&p|{
			face0.normal.dot(p.normal).abs()
		}).ok_or(PlanesToFacesError::InitFace1)?;

		// direction of edge formed by face0 x face1
		let edge_dir=face0.normal.cross(face1.normal);

		// find the most perpendicular face to both face0 and face1
		let mut face2=face_list.iter().max_by_key(|&p|{
			// find the best *oriented* face (no .abs())
			edge_dir.dot(p.normal)
		}).ok_or(PlanesToFacesError::InitFace2)?;

		let mut detect_loop=200u8;

		let mut intersection=solve3(face0,face1,face2).ok_or(PlanesToFacesError::InitIntersection)?;

		// repeatedly update face1, face2 until all faces form part of the convex solid
		'find: loop{
			detect_loop=detect_loop.checked_sub(1).ok_or(PlanesToFacesError::InfiniteLoop1)?;
			// test if any *other* faces occlude the intersection
			for new_face in &face_list{
				// new face occludes intersection point
				if (new_face.dot.widen_128()/Planar64::ONE).lt_ratio(new_face.normal.dot(intersection.num)/intersection.den){
					// replace one of the faces with the new face
					// dont' try to replace face0 because we are exploring that face in particular
					if let Some(new_intersection)=solve3(face0,new_face,face2){
						// face1 does not occlude (or intersect) the new intersection
						if (face1.dot.widen_128()/Planar64::ONE).gt_ratio(face1.normal.dot(new_intersection.num)/new_intersection.den){
							face1=new_face;
							intersection=new_intersection;
							continue 'find;
						}
					}
					if let Some(new_intersection)=solve3(face0,face1,new_face){
						// face2 does not occlude (or intersect) the new intersection
						if (face2.dot.widen_128()/Planar64::ONE).gt_ratio(face2.normal.dot(new_intersection.num)/new_intersection.den){
							face2=new_face;
							intersection=new_intersection;
							continue 'find;
						}
					}
				}
			}

			// we have found a set of faces for which the intersection is on the convex solid
			break 'find;
		}

		// check if face0 must go, meaning it is a degenerate face and does not contribute anything to the convex solid
		for new_face in &face_list{
			if core::ptr::eq(face0,new_face){
				continue;
			}
			if core::ptr::eq(face1,new_face){
				continue;
			}
			if core::ptr::eq(face2,new_face){
				continue;
			}
			// new_face occludes intersection meaning intersection is not on convex solid and face0 is degenrate
			if (new_face.dot.widen_128()/Planar64::ONE).lt_ratio(new_face.normal.dot(intersection.num)/intersection.den){
				// abort! reject face0 entirely
				continue 'face;
			}
		}

		// === follow edges around face ===
		// Note that we chose face2 such that the 3 faces create a particular winding order.
		// If we choose a consistent face to follow (face1, face2) it will always wind with a consistent chirality

		let mut detect_loop=200u8;

		// keep looping until we meet this face again
		let face1=face1;
		let mut face=Vec::new();
		loop{
			// push point onto vertices
			// problem: this may push a vertex that does not fit in the fixed point range and is thus meaningless
			face.push(intersection.divide().narrow_64().unwrap());

			// we looped back around to face1, we're done!
			if core::ptr::eq(face1,face2){
				break;
			}

			// the measure
			let edge_dir=face0.normal.cross(face2.normal);

			// the dot product to beat
			let d_intersection=edge_dir.dot(intersection.num)/intersection.den;

			// find the next face moving clockwise around face0
			let (new_face,new_intersection,_)=face_list.iter().filter_map(|new_face|{
				// ignore faces that are part of the current edge
				if core::ptr::eq(face0,new_face)
				  |core::ptr::eq(face2,new_face){
					return None;
				}
				let new_intersection=solve3(face0,face2,new_face)?;

				// the d value must be larger
				let d_new_intersection=edge_dir.dot(new_intersection.num)/new_intersection.den;
				if d_new_intersection.le_ratio(d_intersection){
					return None;
				}

				Some((new_face,new_intersection,d_new_intersection))
			}).min_by_key(|&(_,_,d)|d).ok_or(PlanesToFacesError::FindNewIntersection)?;

			face2=new_face;
			intersection=new_intersection;

			detect_loop=detect_loop.checked_sub(1).ok_or(PlanesToFacesError::InfiniteLoop2)?;
		}

		faces.push(face);
	}

	if faces.is_empty(){
		Err(PlanesToFacesError::EmptyFaces)
	}else{
		Ok(Faces{
			faces,
		})
	}
}

#[expect(dead_code)]
#[derive(Debug)]
pub enum BrushToMeshError{
	SliceBrushSides,
	MissingPlane,
	InvalidFaceCount{
		count:usize,
	},
	InvalidPlanes(PlanesToFacesError),
}
impl std::fmt::Display for BrushToMeshError{
	fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{
		write!(f,"{self:?}")
	}
}
impl core::error::Error for BrushToMeshError{}

pub fn faces_to_mesh(faces:Vec<Vec<Planar64Vec3>>)->model::Mesh{
	// generate the mesh
	let mut mb=model::MeshBuilder::new();
	let color=mb.acquire_color_id(glam::Vec4::ONE);
	let tex=mb.acquire_tex_id(glam::Vec2::ZERO);
	// normals are ignored by physics
	let normal=mb.acquire_normal_id(integer::vec3::zero());

	let polygon_list=faces.into_iter().map(|face|{
		face.into_iter().map(|pos|{
			let pos=mb.acquire_pos_id(pos);
			mb.acquire_vertex_id(model::IndexedVertex{
				pos,
				tex,
				normal,
				color,
			})
		}).collect()
	}).collect();

	let polygon_groups=vec![model::PolygonGroup::PolygonList(model::PolygonList::new(polygon_list))];
	let physics_groups=vec![model::IndexedPhysicsGroup{
		groups:vec![model::PolygonGroupId::new(0)],
	}];
	let graphics_groups=vec![];

	mb.build(polygon_groups,graphics_groups,physics_groups)
}

pub fn brush_to_mesh(bsp:&vbsp::Bsp,brush:&vbsp::Brush)->Result<model::Mesh,BrushToMeshError>{
	let brush_start_idx=brush.brush_side as usize;
	let sides_range=brush_start_idx..brush_start_idx+brush.num_brush_sides as usize;
	let sides=bsp.brush_sides.get(sides_range).ok_or(BrushToMeshError::SliceBrushSides)?;
	let face_list=sides.iter().map(|side|{
		// The so-called tumor brushes have TRIGGER bit set
		// but also ignore visleaf hint and skip sides
		const TUMOR:vbsp::TextureFlags=vbsp::TextureFlags::HINT.union(vbsp::TextureFlags::SKIP).union(vbsp::TextureFlags::TRIGGER);
		if let Some(texture_info)=bsp.texture_info(side.texture_info as usize){
			if texture_info.flags.intersects(TUMOR){
				return None;
			}
		}
		let plane=bsp.plane(side.plane as usize)?;
		Some(Face{
			normal:valve_transform_normal(plane.normal.into()),
			dot:valve_transform_dist(plane.dist.into()),
		})
	}).collect::<Option<std::collections::HashSet<_>>>().ok_or(BrushToMeshError::MissingPlane)?;

	if face_list.len()<4{
		return Err(BrushToMeshError::InvalidFaceCount{count:face_list.len()});
	}

	let faces=planes_to_faces(face_list).map_err(BrushToMeshError::InvalidPlanes)?;

	let mesh=faces_to_mesh(faces.faces);

	Ok(mesh)
}

pub fn unit_cube()->model::Mesh{
	let face_list=[
		Face{normal:integer::vec3::X,dot:Planar64::ONE},
		Face{normal:integer::vec3::Y,dot:Planar64::ONE},
		Face{normal:integer::vec3::Z,dot:Planar64::ONE},
		Face{normal:integer::vec3::NEG_X,dot:Planar64::ONE},
		Face{normal:integer::vec3::NEG_Y,dot:Planar64::ONE},
		Face{normal:integer::vec3::NEG_Z,dot:Planar64::ONE},
	].into_iter().collect();
	let faces=planes_to_faces(face_list).unwrap();
	let mesh=faces_to_mesh(faces.faces);
	mesh
}

#[cfg(test)]
mod test{
	use super::*;
	#[test]
	fn test_cube(){
		let face_list=[
			Face{normal:integer::vec3::X,dot:Planar64::ONE},
			Face{normal:integer::vec3::Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_X,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Z,dot:Planar64::ONE},
		].into_iter().collect();
		let faces=planes_to_faces(face_list).unwrap();
		assert_eq!(faces.faces.len(),6);
		dbg!(faces);
	}
	#[test]
	fn test_cube_with_degernate_face(){
		let face_list=[
			Face{normal:integer::vec3::X,dot:Planar64::ONE},
			Face{normal:integer::vec3::Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_X,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Z,dot:Planar64::EPSILON},
		].into_iter().collect();
		let faces=planes_to_faces(face_list).unwrap();
		assert_eq!(faces.faces.len(),6);
		dbg!(faces);
	}
	#[test]
	fn test_cube_with_degernate_face2(){
		let face_list=[
			Face{normal:integer::vec3::X,dot:Planar64::ONE},
			Face{normal:integer::vec3::Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_X,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_X+integer::vec3::NEG_Z,dot:-Planar64::EPSILON},
		].into_iter().collect();
		let faces=planes_to_faces(face_list).unwrap();
		assert_eq!(faces.faces.len(),5);
		dbg!(faces);
	}
	#[test]
	fn test_cube_with_degernate_face3(){
		let face_list=[
			Face{normal:integer::vec3::X,dot:Planar64::ONE},
			Face{normal:integer::vec3::Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_X,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Y,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_Z,dot:Planar64::ONE},
			Face{normal:integer::vec3::NEG_X+integer::vec3::NEG_Z,dot:Planar64::EPSILON},
		].into_iter().collect();
		let faces=planes_to_faces(face_list).unwrap();
		assert_eq!(faces.faces.len(),7);
		dbg!(faces);
	}
}
