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
67
68
69
70
71
72
73
74
75
76
77
78
79

#include "BSPTree.h"
#include <iostream>

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

  vmml::vec3f center = findCenter(triangles);
  std::cout << "Center at " << center << std::endl;

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

  plane = Plane(*planeT);
  std::cout << "The plane normal is " << plane.getNormal() << std::endl;

  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;
    }
  }

  std::cout << "All in all: " << triangles.size() << " triangles" << std::endl;
  std::cout << "Coplanar: " << this->triangles.size() << " triangles" << std::endl;
  std::cout << "Front: " << front.size() << " triangles" << std::endl;
  std::cout << "Back: " << back.size() << " triangles" << std::endl;

  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;
    }
  }

  vmml::vec3f tCenter = current->getCenter();
  std::cout << "Nearest triangle center at " << tCenter << std::endl;
  std::cout << "DistanceSq is " << distanceSq << std::endl;

  return current;
}