BSPTree.cpp


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

#include "BSPTree.h"


BSPTree::BSPTree(const std::list<Triangle> &triangles) : frontTree(0), backTree(0) {
  if(triangles.empty())
    return;

  const Triangle *planeT = findNearestTriangle(triangles, findCenter(triangles));

  plane = Plane(*planeT);

  std::list<Triangle> front, back;

  for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
    if(plane.contains(*t)) {
      this->triangles.push_back(*t);
      continue;
    }
    else if(plane.isInFront(*t)) {
      front.push_back(*t);
      continue;
    }
    else if(plane.isBehind(*t)) {
      back.push_back(*t);
      continue;
    }
  }

  if(!front.empty())
    frontTree = new BSPTree(front);

  if(!back.empty())
    backTree = new BSPTree(back);
}


vmml::vec3f BSPTree::findCenter(const std::list<Triangle> &triangles) {
  vmml::vec3f v;

  for(std::list<Triangle>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
    v += t->getCenter();
  }

  return v/triangles.size();
}

const Triangle* BSPTree::findNearestTriangle(const std::list<Triangle> &triangles, const vmml::vec3f &v) {
  if(triangles.empty())
    return 0;

  std::list<Triangle>::const_iterator t = triangles.begin();

  const Triangle *current = &*t;
  float distanceSq = current->getCenter().squared_distance(v);

  for(++t; t != triangles.end(); ++t) {
    float d = t->getCenter().squared_distance(v);

    if(d < distanceSq) {
      current = &*t;
      distanceSq = d;
    }
  }

  return current;
}