Line data Source code
1 : #include "QuadTree.h"
2 :
3 : //------------------------------------------------------------------------------
4 86 : QuadTree::QuadTree()
5 86 : { root = NULL; }
6 :
7 : //------------------------------------------------------------------------------
8 86 : QuadTree::~QuadTree() {}
9 :
10 : //------------------------------------------------------------------------------
11 9 : void QuadTree::buildTree(Terrain* t) {
12 9 : buildTree(root, 0.0f, ((t->getXSize() - 1.0f) * t->getScaleFactor()), 0.0f, ((t->getZSize() - 1.0f) * t->getScaleFactor()), t->getScaleFactor());
13 9 : }
14 : //------------------------------------------------------------------------------
15 63 : int QuadTree::buildTree(
16 : QuadTreeNode* &p, const float &xMin, const float &xMax, const float &zMin,
17 : const float &zMax, const float &scaleFactor
18 : ) {
19 : PRINT_DEBUG_LVL(5, "Leaf:\n");
20 : PRINT_DEBUG_LVL(5, "x=%f\n", (((xMax - xMin)/ 2.0f) + xMin));
21 : PRINT_DEBUG_LVL(5, "z=%f\n", (-(((zMax - zMin)/ 2.0f) + zMin)));
22 : PRINT_DEBUG_LVL(5, "sqrt=%f\n", sqrt(((zMax - zMin) * (zMax - zMin)) + ((xMax - xMin) * (xMax - xMin))));
23 :
24 63 : p = new QuadTreeNode();
25 :
26 63 : p->min[0] = xMin;
27 63 : p->min[1] = zMin;
28 63 : p->max[0] = xMax;
29 63 : p->max[1] = zMax;
30 :
31 126 : p->boundingSphere.setSphere(
32 63 : (((xMax-xMin) / 2.0f) + xMin),
33 63 : 0.0f,
34 63 : (-(((zMax-zMin) / 2.0f) + zMin)),
35 63 : sqrt(((zMax - zMin) * (zMax - zMin)) + ((xMax - xMin) * (xMax - xMin)))
36 : );
37 :
38 63 : if (((xMax - xMin) > scaleFactor) && ((zMax - zMin) <= scaleFactor)) {
39 2 : buildTree(p->child[0], ((xMax + xMin) / 2.0f), xMax, zMin, zMax, scaleFactor);
40 2 : buildTree(p->child[1], xMin, ((xMax + xMin) / 2.0f), zMin, zMax , scaleFactor);
41 2 : }
42 61 : else if (((xMax - xMin) <= scaleFactor) && ((zMax - zMin) > scaleFactor)) {
43 2 : buildTree(p->child[2], xMin, xMax, zMin, ((zMax + zMin) / 2.0f), scaleFactor);
44 2 : buildTree(p->child[3], xMin, xMax, (zMax + zMin) / 2.0f, zMax, scaleFactor);
45 :
46 2 : }
47 59 : else if (((xMax - xMin) > scaleFactor) && ((zMax - zMin) > scaleFactor)) {
48 8 : buildTree(p->child[0], xMin, ((xMax + xMin) / 2.0f), zMin, ((zMax + zMin) / 2.0f), scaleFactor);
49 8 : buildTree(p->child[1], xMin, ((xMax + xMin) / 2.0f), (zMax + zMin) / 2.0f, zMax, scaleFactor);
50 8 : buildTree(p->child[2], ((xMax+xMin) / 2.0f), xMax, zMin, ((zMax + zMin) / 2.0f), scaleFactor);
51 8 : buildTree(p->child[3], ((xMax+xMin) / 2.0f), xMax, ((zMax + zMin) / 2.0f), zMax , scaleFactor);
52 8 : }
53 : else {
54 : PRINT_DEBUG_LVL(5, "Leaf:\n");
55 : PRINT_DEBUG_LVL(5, "x=%f,%f\n", xMin, xMax);
56 : PRINT_DEBUG_LVL(5, "z=%f,%f\n", zMin, zMax);
57 :
58 : PRINT_DEBUG_LVL(5, "Leaf:\n");
59 : PRINT_DEBUG_LVL(5, "x=%f\n", (((xMax - xMin) / 2.0f) + xMin));
60 : PRINT_DEBUG_LVL(5, "z=%f\n", (-(((zMax - zMin) / 2.0f) + zMin)));
61 : PRINT_DEBUG_LVL(5, "sqrt=%f\n", sqrt(((zMax - zMin) * (zMax - zMin)) + ((xMax - xMin) * (xMax - xMin))));
62 : }
63 :
64 63 : return (1);
65 0 : }
66 :
67 : //------------------------------------------------------------------------------
68 1 : void QuadTree::traverseTree() {
69 1 : traverseTree(root);
70 1 : }
71 :
72 : //------------------------------------------------------------------------------
73 21 : void QuadTree::traverseTree(QuadTreeNode* n) {
74 21 : if (n != NULL) {
75 : PRINT_DEBUG("---------------------------\n");
76 : PRINT_DEBUG("min x: %d, max x: %d\n", (int)n->min[0], (int)n->max[0]);
77 : PRINT_DEBUG("min z: %d max z: %d\n", (int)n->min[1], (int)n->max[1]);
78 : PRINT_DEBUG("---------------------------\n");
79 :
80 25 : for (int i = 0; i < 4; i++) {
81 20 : traverseTree(n->child[i]);
82 20 : }
83 5 : }
84 : else {
85 : PRINT_DEBUG("------------------\n");
86 : PRINT_DEBUG("leaf node\n");
87 : PRINT_DEBUG("------------------\n");
88 : }
89 21 : }
90 :
91 : //------------------------------------------------------------------------------
92 9 : int QuadTree::buildDisplayList(DisplayList* l, Camera* c) {
93 9 : buildDisplayList(root, l, c);
94 9 : return (0);
95 : }
96 :
97 : //------------------------------------------------------------------------------
98 3 : int QuadTree::buildLeafList(DisplayList* l) {
99 3 : buildLeafList(root, l);
100 3 : return (0);
101 : }
102 :
103 : //------------------------------------------------------------------------------
104 45 : int QuadTree::buildDisplayList(QuadTreeNode* n, DisplayList* l, Camera* c) {
105 45 : if (n != NULL) {
106 9 : int r = c->frustum.testSphere(n->boundingSphere);
107 9 : switch(r)
108 : {
109 : case -1:
110 0 : return (0);
111 : case 1:
112 : //bTestChildren = false;
113 0 : break;
114 : case 0:
115 : // check if the box is in view
116 : //switch(pPovCamera->Frustrum().ContainsAaBox(pNode->m_bbox)) {
117 : //case IN:
118 : //bTestChildren = false;
119 : // break;
120 : //case OUT:
121 : //return;
122 : //}
123 9 : break;
124 : }
125 :
126 9 : if (n->child[0] == NULL && n->child[1] == NULL && n->child[2] == NULL && n->child[3] == NULL) {
127 9 : l->insertLast(n);
128 9 : }
129 :
130 45 : for (int i = 0; i < 4; i++) {
131 36 : buildDisplayList(n->child[i], l, c);
132 36 : }
133 9 : }
134 :
135 45 : return (0);
136 45 : }
137 :
138 : //------------------------------------------------------------------------------
139 47 : int QuadTree::buildLeafList(QuadTreeNode* n, DisplayList* l) {
140 47 : if (n != NULL) {
141 11 : if (n->child[0] == NULL && n->child[1] == NULL && n->child[2] == NULL && n->child[3] == NULL) {
142 8 : l->insertLast(n);
143 8 : }
144 :
145 55 : for (int i = 0; i < 4; i++) {
146 44 : buildLeafList(n->child[i], l);
147 44 : }
148 11 : }
149 :
150 47 : return (0);
151 : }
|
