Line data Source code
1 : #include "catch.hpp"
2 : #include <cmath>
3 : #include "QuadTree.h"
4 : #include "QuadTreeNode.h"
5 : #include "DisplayList.h"
6 :
7 : namespace {
8 :
9 : // QuadTree's destructor does not delete the tree; callers must free nodes.
10 230 : void freeQuadTreeNode(QuadTreeNode *n) {
11 230 : if (n == NULL)
12 176 : return;
13 270 : for (int i = 0; i < 4; ++i) {
14 216 : freeQuadTreeNode(n->child[i]);
15 216 : }
16 54 : delete n;
17 230 : }
18 :
19 3 : int countDisplayList(DisplayList *list) {
20 3 : int n = 0;
21 11 : for (QuadTreeNode *p = list->head; p != NULL; p = p->next) {
22 8 : ++n;
23 8 : }
24 3 : return n;
25 : }
26 :
27 9 : bool isLeaf(QuadTreeNode *n) {
28 9 : if (n == NULL)
29 0 : return false;
30 18 : return n->child[0] == NULL && n->child[1] == NULL && n->child[2] == NULL &&
31 9 : n->child[3] == NULL;
32 9 : }
33 :
34 : } // namespace
35 :
36 14 : SCENARIO( "QuadTree spatial partition", "[QuadTree]" ) {
37 15 : GIVEN( "A tree that is already a leaf at root" ) {
38 2 : QuadTree qt;
39 2 : REQUIRE(qt.root == NULL);
40 :
41 2 : qt.buildTree(qt.root, 0.0f, 10.0f, 0.0f, 10.0f, 10.0f);
42 2 : REQUIRE(qt.root != NULL);
43 :
44 3 : THEN( "bounds and bounding sphere match implementation formulas" ) {
45 1 : REQUIRE(qt.root->min[0] == Approx(0.0f));
46 1 : REQUIRE(qt.root->max[0] == Approx(10.0f));
47 1 : REQUIRE(qt.root->min[1] == Approx(0.0f));
48 1 : REQUIRE(qt.root->max[1] == Approx(10.0f));
49 :
50 1 : Vector o;
51 1 : qt.root->boundingSphere.getOriginVector(o);
52 1 : REQUIRE(o.x == Approx(5.0f));
53 1 : REQUIRE(o.y == Approx(0.0f));
54 1 : REQUIRE(o.z == Approx(-5.0f));
55 : // NOTE: the radius formula uses the full diagonal (sqrt(w²+h²)) rather
56 : // than the circumradius (half-diagonal). The sphere is 2x oversized,
57 : // causing conservative over-rendering. See known bugs for the fix.
58 1 : const float expectedR = std::sqrt(200.0f);
59 1 : REQUIRE(qt.root->boundingSphere.getRadius() == Approx(expectedR));
60 1 : }
61 :
62 3 : THEN( "root has no children" ) {
63 1 : REQUIRE(isLeaf(qt.root));
64 1 : }
65 :
66 2 : freeQuadTreeNode(qt.root);
67 2 : qt.root = NULL;
68 2 : }
69 :
70 20 : GIVEN( "A 20x20 region with scale 10 (splits into four leaves)" ) {
71 7 : QuadTree qt;
72 7 : qt.buildTree(qt.root, 0.0f, 20.0f, 0.0f, 20.0f, 10.0f);
73 :
74 8 : THEN( "root has four children and each is a leaf" ) {
75 1 : REQUIRE(qt.root->child[0] != NULL);
76 1 : REQUIRE(qt.root->child[1] != NULL);
77 1 : REQUIRE(qt.root->child[2] != NULL);
78 1 : REQUIRE(qt.root->child[3] != NULL);
79 5 : for (int i = 0; i < 4; ++i) {
80 4 : REQUIRE(isLeaf(qt.root->child[i]));
81 4 : }
82 1 : }
83 :
84 8 : THEN( "child[0] covers xMin-midX, zMin-midZ" ) {
85 1 : QuadTreeNode *c = qt.root->child[0];
86 1 : REQUIRE(c->min[0] == Approx(0.0f));
87 1 : REQUIRE(c->max[0] == Approx(10.0f));
88 1 : REQUIRE(c->min[1] == Approx(0.0f));
89 1 : REQUIRE(c->max[1] == Approx(10.0f));
90 1 : }
91 :
92 : // Verify the XZ bounding sphere convention holds for child nodes:
93 : // y=0 (ground plane), z=-centerZ (negated), radius is the full diagonal.
94 8 : THEN( "child[0] bounding sphere follows XZ convention" ) {
95 1 : Vector o;
96 1 : qt.root->child[0]->boundingSphere.getOriginVector(o);
97 1 : REQUIRE(o.x == Approx(5.0f));
98 1 : REQUIRE(o.y == Approx(0.0f));
99 1 : REQUIRE(o.z == Approx(-5.0f));
100 1 : REQUIRE(qt.root->child[0]->boundingSphere.getRadius() == Approx(std::sqrt(200.0f)));
101 1 : }
102 :
103 8 : THEN( "child[1] covers xMin-midX, midZ-zMax" ) {
104 1 : QuadTreeNode *c = qt.root->child[1];
105 1 : REQUIRE(c->min[0] == Approx(0.0f));
106 1 : REQUIRE(c->max[0] == Approx(10.0f));
107 1 : REQUIRE(c->min[1] == Approx(10.0f));
108 1 : REQUIRE(c->max[1] == Approx(20.0f));
109 1 : }
110 :
111 8 : THEN( "child[2] covers midX-xMax, zMin-midZ" ) {
112 1 : QuadTreeNode *c = qt.root->child[2];
113 1 : REQUIRE(c->min[0] == Approx(10.0f));
114 1 : REQUIRE(c->max[0] == Approx(20.0f));
115 1 : REQUIRE(c->min[1] == Approx(0.0f));
116 1 : REQUIRE(c->max[1] == Approx(10.0f));
117 1 : }
118 :
119 8 : THEN( "child[3] covers midX-xMax, midZ-zMax" ) {
120 1 : QuadTreeNode *c = qt.root->child[3];
121 1 : REQUIRE(c->min[0] == Approx(10.0f));
122 1 : REQUIRE(c->max[0] == Approx(20.0f));
123 1 : REQUIRE(c->min[1] == Approx(10.0f));
124 1 : REQUIRE(c->max[1] == Approx(20.0f));
125 1 : }
126 :
127 8 : THEN( "buildLeafList collects four nodes" ) {
128 1 : DisplayList list;
129 1 : qt.buildLeafList(&list);
130 1 : REQUIRE(countDisplayList(&list) == 4);
131 1 : }
132 :
133 7 : freeQuadTreeNode(qt.root);
134 7 : qt.root = NULL;
135 7 : }
136 :
137 15 : GIVEN( "A 20x10 strip (split along X only)" ) {
138 2 : QuadTree qt;
139 2 : qt.buildTree(qt.root, 0.0f, 20.0f, 0.0f, 10.0f, 10.0f);
140 :
141 3 : THEN( "two children along X, both leaves" ) {
142 1 : REQUIRE(qt.root->child[0] != NULL);
143 1 : REQUIRE(qt.root->child[1] != NULL);
144 1 : REQUIRE(qt.root->child[2] == NULL);
145 1 : REQUIRE(qt.root->child[3] == NULL);
146 1 : REQUIRE(isLeaf(qt.root->child[0]));
147 1 : REQUIRE(isLeaf(qt.root->child[1]));
148 1 : REQUIRE(qt.root->child[0]->min[0] == Approx(10.0f));
149 1 : REQUIRE(qt.root->child[0]->max[0] == Approx(20.0f));
150 1 : REQUIRE(qt.root->child[1]->min[0] == Approx(0.0f));
151 1 : REQUIRE(qt.root->child[1]->max[0] == Approx(10.0f));
152 1 : }
153 :
154 3 : THEN( "buildLeafList collects two nodes" ) {
155 1 : DisplayList list;
156 1 : qt.buildLeafList(&list);
157 1 : REQUIRE(countDisplayList(&list) == 2);
158 1 : }
159 :
160 2 : freeQuadTreeNode(qt.root);
161 2 : qt.root = NULL;
162 2 : }
163 :
164 15 : GIVEN( "A 10x20 strip (split along Z only)" ) {
165 2 : QuadTree qt;
166 2 : qt.buildTree(qt.root, 0.0f, 10.0f, 0.0f, 20.0f, 10.0f);
167 :
168 3 : THEN( "two children along Z, both leaves" ) {
169 1 : REQUIRE(qt.root->child[0] == NULL);
170 1 : REQUIRE(qt.root->child[1] == NULL);
171 1 : REQUIRE(qt.root->child[2] != NULL);
172 1 : REQUIRE(qt.root->child[3] != NULL);
173 1 : REQUIRE(isLeaf(qt.root->child[2]));
174 1 : REQUIRE(isLeaf(qt.root->child[3]));
175 1 : REQUIRE(qt.root->child[2]->min[1] == Approx(0.0f));
176 1 : REQUIRE(qt.root->child[2]->max[1] == Approx(10.0f));
177 1 : REQUIRE(qt.root->child[3]->min[1] == Approx(10.0f));
178 1 : REQUIRE(qt.root->child[3]->max[1] == Approx(20.0f));
179 1 : }
180 :
181 3 : THEN( "buildLeafList collects two nodes" ) {
182 1 : DisplayList list;
183 1 : qt.buildLeafList(&list);
184 1 : REQUIRE(countDisplayList(&list) == 2);
185 1 : }
186 :
187 2 : freeQuadTreeNode(qt.root);
188 2 : qt.root = NULL;
189 2 : }
190 13 : }
191 :
192 2 : SCENARIO( "QuadTree traverseTree", "[QuadTree]" ) {
193 2 : GIVEN( "A built tree" ) {
194 1 : QuadTree qt;
195 1 : qt.buildTree(qt.root, 0.0f, 20.0f, 0.0f, 20.0f, 10.0f);
196 :
197 : // traverseTree is a debug-only utility (PRINT_DEBUG) and a no-op in
198 : // production builds (DEBUG=0). Smoke-tested here to confirm the
199 : // recursive traversal terminates without crashing.
200 2 : WHEN( "traverseTree is called" ) {
201 2 : THEN( "it does not crash" ) {
202 1 : qt.traverseTree();
203 1 : }
204 1 : }
205 :
206 1 : freeQuadTreeNode(qt.root);
207 1 : qt.root = NULL;
208 1 : }
209 1 : }
210 :
211 3 : SCENARIO( "QuadTreeNode default construction", "[QuadTreeNode]" ) {
212 4 : GIVEN( "A default node" ) {
213 2 : QuadTreeNode n;
214 :
215 3 : THEN( "children are null, bounds are zero, and next is null" ) {
216 5 : for (int i = 0; i < 4; ++i) {
217 4 : REQUIRE(n.child[i] == NULL);
218 4 : }
219 1 : REQUIRE(n.min[0] == Approx(0.0f));
220 1 : REQUIRE(n.max[0] == Approx(0.0f));
221 1 : REQUIRE(n.min[1] == Approx(0.0f));
222 1 : REQUIRE(n.max[1] == Approx(0.0f));
223 1 : REQUIRE(n.next == NULL);
224 1 : }
225 :
226 3 : THEN( "bounding sphere defaults to zero origin and zero radius" ) {
227 1 : Vector o;
228 1 : n.boundingSphere.getOriginVector(o);
229 1 : REQUIRE(o.x == Approx(0.0f));
230 1 : REQUIRE(o.y == Approx(0.0f));
231 1 : REQUIRE(o.z == Approx(0.0f));
232 1 : REQUIRE(n.boundingSphere.getRadius() == Approx(0.0f));
233 1 : }
234 2 : }
235 2 : }
|
