1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

use std::collections::HashMap;

use ptr::{Ptr, EdgeRc};
use mesh::HalfEdgeMesh;

fn merge_tuple_opt<A, B>(o: (Option<A>, Option<B>)) -> Option<(A, B)> {
  match o {
    (Some(a), Some(b)) => Some((a, b)),
    _ => None
  }
}

fn vert_ab_key(e: & EdgeRc) -> Option<(u32, u32)> {
  let id_origin = e.borrow().origin.upgrade().map(|o| o.borrow().id);
  let id_next_origin = e.borrow().next.upgrade().and_then(|n| n.borrow().origin.upgrade()).map(|o| o.borrow().id);
  merge_tuple_opt((id_origin, id_next_origin))
}

fn vert_ba_key(e: & EdgeRc) -> Option<(u32, u32)> { vert_ab_key(e).map(|tuple| (tuple.1, tuple.0)) }

/// Takes what is assumed to be a fully constructed mesh, with no
/// pair links, and establishes pair links between adjacent edges.
/// If this function runs successfully on a mesh, all links in the mesh
/// should point to their adjacent pair
pub fn connect_pairs(mesh: &mut HalfEdgeMesh) -> Result<(), &'static str> {
  // Two-stage algorithm: first collect all edge A -> B relationships,
  // Then go through and look for edges that are B -> A
  let mut edge_hash: HashMap<(u32, u32), & EdgeRc> = HashMap::new();

  for ref edge in mesh.edges.values() {
    // The types returned by match arms must be the same,
    // hence the braces and semicolon used in the first branch
    match vert_ab_key(edge) {
      Some(key) => { edge_hash.insert(key, edge); },
      // This happens if one of the mesh edges doesn't have a valid .origin or .next.origin pointer
      None => { return Err("Could not hash all mesh edges"); }
    }
  }

  for ref edge in mesh.edges.values() {
    // This if statement should skip half the edges, because two
    // edge pairs are set each time it's true
    if !edge.borrow().pair.is_valid() {
      if let Some(key) = vert_ba_key(edge) {
        match edge_hash.get(& key) {
          Some(pair_edge) => {
            // if one edge A -> B matches another edge B -> A, the edges are adjacent
            edge.borrow_mut().take_pair(Ptr::new(pair_edge));
            pair_edge.borrow_mut().take_pair(Ptr::new(edge));
          },
          None => { /* Happens when mesh is not closed */
            return Err("Could not find pair edge");
          }
        }
      } else {
        // Theoretically this shouldn't ever happen
        // because of the early return in the previous match block
        return Err("Could not find reverse hash for mesh edge");
      }
    }
  }

  Ok(())
}

/// Utility function for reporting problems with edge connectivity
pub fn report_connect_err(res: Result<(), &str>) {
  if let Err(e) = res {
    println!("Error connecting mesh pairs! Mesh is not valid! {}", e);
  }
}

/// Checks if edge pair connections are all valid
pub fn are_edge_pairs_valid(mesh: & HalfEdgeMesh) -> Result<(), &'static str> {
  let mut edge_hash: HashMap<(u32, u32), & EdgeRc> = HashMap::new();

  for ref edge in mesh.edges.values() {
    // The types returned by match arms must be the same,
    // hence the braces and semicolon used in the first branch
    match vert_ab_key(edge) {
      Some(key) => { edge_hash.insert(key, edge); },
      // This happens if one of the mesh edges doesn't have a valid .origin or .next.origin pointer
      None => { return Err("Could not hash all mesh edges"); }
    }
  }

  for ref edge in mesh.edges.values() {
    match vert_ba_key(edge) {
      Some(key) => {
        match edge_hash.get(& key) {
          Some(ref pair) => {
            if (edge.borrow().pair.upgrade().as_ref() != Some(pair)) ||
               (pair.borrow().pair.upgrade().as_ref() != Some(edge)) {
                return Err("Pairs don't match");
            }
          },
          None => { return Err("Could not find a pair edge"); }
        }
      },
      None => { return Err("Could not find reverse hash for mesh edge"); }
    }
  }

  Ok(())
}