KdTree4TriangularMeshes

Algorithm

Node *buildKdTree(ini, end, triangles)
{
  sort triangles by k-n centroid coordinate
  median = (ini + end)/2
  node.triangle = triangles[med]
  node.left  = buildKdTree(ini, median, points) 
  node.right = buildKdTree(median, fim, points)
  node.aabb  = union(node.triangle.aabb, node.left.aabb, node.right.aabb)
  return node
}

---

2D Folder

A KdTree implementation for triangular 2D mesh.

• Keys:

  • d: Minus one depth
  • D: Plus one depth
  • v: View the whole kd-tree

• The Triangles:

• kd-Tree per depth:

• The whole kd-Tree:

---

3D Folder

A KdTree implementation for triangular 3D mesh.

• Keys:
  • A: Open mesh
  • b: Minus one depth
  • B: Plus one depth
  • g: Turn grid on/off
  • p: Fill surface

---

• kd-Tree per depth: