///|
pub fn Vector3::new(x~ : Double, y~ : Double, z~ : Double) -> Vector3 {
  { x, y, z }
}

///|
pub fn Vector3::from_points(start : Point3, end : Point3) -> Vector3 {
  { x: end.x - start.x, y: end.y - start.y, z: end.z - start.z }
}

///|
pub fn Vector3::to_point(self : Vector3) -> Point3 {
  { x: self.x, y: self.y, z: self.z }
}

///|
pub fn Vector3::add(self : Vector3, other : Vector3) -> Vector3 {
  { x: self.x + other.x, y: self.y + other.y, z: self.z + other.z }
}

///|
pub fn Vector3::subtract(self : Vector3, other : Vector3) -> Vector3 {
  { x: self.x - other.x, y: self.y - other.y, z: self.z - other.z }
}

///|
pub fn Vector3::scale(self : Vector3, factor : Double) -> Vector3 {
  { x: self.x * factor, y: self.y * factor, z: self.z * factor }
}

///|
pub fn Vector3::dot(self : Vector3, other : Vector3) -> Double {
  self.x * other.x + self.y * other.y + self.z * other.z
}

///|
pub fn Vector3::cross(self : Vector3, other : Vector3) -> Vector3 {
  {
    x: self.y * other.z - self.z * other.y,
    y: self.z * other.x - self.x * other.z,
    z: self.x * other.y - self.y * other.x,
  }
}

///|
pub fn Vector3::length(self : Vector3) -> Double {
  self.dot(self).sqrt()
}

///|
pub fn Vector3::normalized(self : Vector3) -> Vector3 {
  let length = self.length()
  if length == 0.0 {
    { x: 0.0, y: 0.0, z: 0.0 }
  } else {
    self.scale(1.0 / length)
  }
}

///|
pub fn Vector3::is_zero(self : Vector3) -> Bool {
  self.x == 0.0 && self.y == 0.0 && self.z == 0.0
}

///|
fn triangle_points(
  mesh : Mesh,
  triangle : (Int, Int, Int),
) -> (Point3, Point3, Point3)? {
  let (a, b, c) = triangle
  match (mesh.points.get(a), mesh.points.get(b), mesh.points.get(c)) {
    (Some(left), Some(middle), Some(right)) => Some((left, middle, right))
    _ => None
  }
}

///|
pub fn triangle_normal(mesh : Mesh, triangle : (Int, Int, Int)) -> Vector3 {
  match triangle_points(mesh, triangle) {
    Some((a, b, c)) =>
      Vector3::from_points(a, b).cross(Vector3::from_points(a, c)).normalized()
    None => Vector3::{ x: 0.0, y: 0.0, z: 0.0 }
  }
}

///|
pub fn triangle_area(mesh : Mesh, triangle : (Int, Int, Int)) -> Double {
  match triangle_points(mesh, triangle) {
    Some((a, b, c)) =>
      Vector3::from_points(a, b).cross(Vector3::from_points(a, c)).length() /
      2.0
    None => 0.0
  }
}

///|
fn edge_key(left : Int, right : Int) -> String {
  if left < right {
    left.to_string() + ":" + right.to_string()
  } else {
    right.to_string() + ":" + left.to_string()
  }
}

///|
fn mesh_edges(mesh : Mesh) -> Map[String, Array[Int]] {
  let edges : Map[String, Array[Int]] = Map([])
  for triangle_index, triangle in mesh.triangles {
    let (a, b, c) = triangle
    for key in [edge_key(a, b), edge_key(b, c), edge_key(c, a)] {
      edges.update_or_default(key, [triangle_index], values => {
        values.push(triangle_index)
        values
      })
    }
  }
  edges
}

///|
fn triangle_neighbors(
  mesh : Mesh,
  edges : Map[String, Array[Int]],
  triangle_index : Int,
) -> Array[Int] {
  let result : Array[Int] = []
  match mesh.triangles.get(triangle_index) {
    Some((a, b, c)) =>
      for key in [edge_key(a, b), edge_key(b, c), edge_key(c, a)] {
        for neighbor in edges.get(key).unwrap_or([]) {
          if neighbor != triangle_index && !result.contains(neighbor) {
            result.push(neighbor)
          }
        }
      }
    None => ()
  }
  result
}

///|
fn component_count(mesh : Mesh, edges : Map[String, Array[Int]]) -> Int {
  let visited : Map[Int, Bool] = Map([])
  let mut components = 0
  for triangle_index in 0.. break
          Some(current) => {
            cursor += 1
            for neighbor in triangle_neighbors(mesh, edges, current) {
              if !visited.contains(neighbor) {
                visited[neighbor] = true
                queue.push(neighbor)
              }
            }
          }
        }
      }
    }
  }
  components
}

///|
/// Calculate topology quality and geometric measurements for a mesh.
pub fn mesh_stats(mesh : Mesh) -> MeshStats {
  let edges = mesh_edges(mesh)
  let mut boundary_edge_count = 0
  let mut non_manifold_edge_count = 0
  for _, triangles in edges {
    if triangles.length() == 1 {
      boundary_edge_count += 1
    } else if triangles.length() > 2 {
      non_manifold_edge_count += 1
    }
  }
  let mut degenerate_triangle_count = 0
  let mut surface_area = 0.0
  let mut signed_volume = 0.0
  for triangle in mesh.triangles {
    let area = triangle_area(mesh, triangle)
    surface_area += area
    if area < 0.000000000001 {
      degenerate_triangle_count += 1
    }
    match triangle_points(mesh, triangle) {
      Some((a, b, c)) => {
        let origin = Vector3::{ x: a.x, y: a.y, z: a.z }
        let middle = Vector3::{ x: b.x, y: b.y, z: b.z }
        let right = Vector3::{ x: c.x, y: c.y, z: c.z }
        signed_volume += origin.dot(middle.cross(right)) / 6.0
      }
      None => ()
    }
  }
  {
    point_count: mesh.points.length(),
    triangle_count: mesh.triangles.length(),
    boundary_edge_count,
    non_manifold_edge_count,
    degenerate_triangle_count,
    connected_component_count: component_count(mesh, edges),
    surface_area,
    signed_volume,
  }
}

///|
pub fn MeshStats::is_closed(self : MeshStats) -> Bool {
  self.boundary_edge_count == 0 &&
  self.non_manifold_edge_count == 0 &&
  self.triangle_count > 0
}

///|
pub fn MeshStats::is_manifold(self : MeshStats) -> Bool {
  self.non_manifold_edge_count == 0
}

///|
pub fn MeshStats::volume(self : MeshStats) -> Double {
  self.signed_volume.abs()
}

///|
pub fn MeshStats::headline(self : MeshStats) -> String {
  "points=" +
  self.point_count.to_string() +
  " triangles=" +
  self.triangle_count.to_string() +
  " area=" +
  self.surface_area.to_string() +
  " volume=" +
  self.volume().to_string() +
  " boundary=" +
  self.boundary_edge_count.to_string() +
  " components=" +
  self.connected_component_count.to_string()
}

///|
pub fn MeshAnalysis::from_mesh(mesh : Mesh) -> MeshAnalysis {
  {
    mesh,
    stats: mesh_stats(mesh),
    bounds: bounds_of_mesh(mesh),
    normals: mesh.triangles.map(triangle => triangle_normal(mesh, triangle)),
  }
}

///|
pub fn MeshAnalysis::is_valid(self : MeshAnalysis) -> Bool {
  self.stats.point_count > 0 &&
  self.stats.triangle_count > 0 &&
  self.stats.is_manifold() &&
  self.stats.degenerate_triangle_count == 0
}

///|
fn rectangle_extrusion_mesh(geometry : Geometry) -> Mesh {
  let width = geometry.profile_width.unwrap_or(0.0)
  let height = geometry.profile_height.unwrap_or(0.0)
  let depth = geometry.depth.unwrap_or(0.0)
  if width <= 0.0 || height <= 0.0 || depth <= 0.0 {
    return { points: [], triangles: [] }
  }
  let half_width = width / 2.0
  let half_height = height / 2.0
  let points : Array[Point3] = [
    { x: -half_width, y: -half_height, z: 0.0 },
    { x: half_width, y: -half_height, z: 0.0 },
    { x: half_width, y: half_height, z: 0.0 },
    { x: -half_width, y: half_height, z: 0.0 },
    { x: -half_width, y: -half_height, z: depth },
    { x: half_width, y: -half_height, z: depth },
    { x: half_width, y: half_height, z: depth },
    { x: -half_width, y: half_height, z: depth },
  ]
  let triangles = [
    (0, 2, 1),
    (0, 3, 2),
    (4, 5, 6),
    (4, 6, 7),
    (0, 1, 5),
    (0, 5, 4),
    (1, 2, 6),
    (1, 6, 5),
    (2, 3, 7),
    (2, 7, 6),
    (3, 0, 4),
    (3, 4, 7),
  ]
  { points, triangles }
}

///|
fn circle_extrusion_mesh(geometry : Geometry, segments : Int) -> Mesh {
  let radius = geometry.profile_radius.unwrap_or(0.0)
  let depth = geometry.depth.unwrap_or(0.0)
  let count = if segments < 3 { 3 } else { segments }
  if radius <= 0.0 || depth <= 0.0 {
    return { points: [], triangles: [] }
  }
  let points : Array[Point3] = []
  for index in 0.. Mesh raise ParseError {
  match geometry.kind {
    Extrusion =>
      if geometry.profile_radius is Some(_) {
        circle_extrusion_mesh(geometry, 24)
      } else {
        rectangle_extrusion_mesh(geometry)
      }
    FacetedBrep | TriangulatedMesh =>
      mesh_for_geometry(index, geometry.source_id)
    _ => { points: geometry.points, triangles: [] }
  }
}

///|
pub fn mesh_for_product_advanced(
  index : ModelIndex,
  product : Product,
) -> Mesh raise ParseError {
  let meshes = geometries_for_product(index, product).map(geometry => {
    mesh_for_geometry_advanced(index, geometry)
  })
  transform_mesh(product_transform(index, product), merge_meshes(meshes))
}

///|
pub fn analyze_product_mesh(
  index : ModelIndex,
  product : Product,
) -> MeshAnalysis raise ParseError {
  MeshAnalysis::from_mesh(mesh_for_product_advanced(index, product))
}

///|
fn point_bucket(point : Point3, tolerance : Double) -> String {
  let safe = if tolerance <= 0.0 { 0.000001 } else { tolerance }
  let x = @math.floor(point.x / safe + 0.5).to_string()
  let y = @math.floor(point.y / safe + 0.5).to_string()
  let z = @math.floor(point.z / safe + 0.5).to_string()
  x + ":" + y + ":" + z
}

///|
/// Weld nearby points and rewrite triangle indices deterministically.
pub fn weld_mesh(mesh : Mesh, tolerance : Double) -> Mesh {
  let point_map : Map[String, Int] = Map([])
  let points : Array[Point3] = []
  let remap : Array[Int] = []
  for point in mesh.points {
    let key = point_bucket(point, tolerance)
    match point_map.get(key) {
      Some(index) => remap.push(index)
      None => {
        let index = points.length()
        point_map[key] = index
        points.push(point)
        remap.push(index)
      }
    }
  }
  let triangles : Array[(Int, Int, Int)] = []
  for triangle in mesh.triangles {
    let (a, b, c) = triangle
    match (remap.get(a), remap.get(b), remap.get(c)) {
      (Some(left), Some(middle), Some(right)) if left != middle &&
        middle != right &&
        left != right => triangles.push((left, middle, right))
      _ => ()
    }
  }
  { points, triangles }
}

///|
pub fn remove_degenerate_triangles(mesh : Mesh, tolerance : Double) -> Mesh {
  mesh.triangles.fold(init={ points: mesh.points, triangles: [] }, (
    result,
    triangle,
  ) => {
    if triangle_area(mesh, triangle) > tolerance {
      result.triangles.push(triangle)
    }
    result
  })
}

///|
pub fn limit_mesh_triangles(mesh : Mesh, maximum : Int) -> Mesh {
  if maximum <= 0 || mesh.triangles.length() <= maximum {
    return mesh
  }
  { points: mesh.points, triangles: mesh.triangles[:maximum].to_owned() }
}

///|
pub fn mesh_to_json_stats(analysis : MeshAnalysis) -> String {
  "{\"points\":" +
  analysis.stats.point_count.to_string() +
  ",\"triangles\":" +
  analysis.stats.triangle_count.to_string() +
  ",\"boundary_edges\":" +
  analysis.stats.boundary_edge_count.to_string() +
  ",\"non_manifold_edges\":" +
  analysis.stats.non_manifold_edge_count.to_string() +
  ",\"surface_area\":" +
  analysis.stats.surface_area.to_string() +
  ",\"volume\":" +
  analysis.stats.volume().to_string() +
  "}"
}