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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
/* This file is part of the Spring engine (GPL v2 or later), see LICENSE.html */
#include "Sim/Misc/QuadField.h"
#include "System/float3.h"
#include "System/myMath.h"
#include <stdlib.h>
#include <time.h>
#define BOOST_TEST_MODULE QuadField
#include <boost/test/unit_test.hpp>
static inline float randf()
{
return rand() / float(RAND_MAX);
}
BOOST_AUTO_TEST_CASE( QuadField )
{
srand( time(NULL) );
static const int WIDTH = 3;
static const int HEIGHT = 3;
static const int TEST_RUNS = 50000;
int2 mapDims = int2(WIDTH, HEIGHT);
CQuadField qf(mapDims, SQUARE_SIZE);
// necessary for QuadFieldQuery
quadField = &qf;
int bitmap[WIDTH * HEIGHT];
bool fail = false;
for (int n = 0; n < TEST_RUNS; ++n) {
// clear
for (int i = 0; i < WIDTH * HEIGHT; ++i) {
bitmap[i] = 0;
}
// generate ray
float3 start;
start.x = randf() * WIDTH * 3 - WIDTH;
start.z = randf() * HEIGHT * 3 - HEIGHT;
float3 dir;
dir.x = randf() - 0.5f;
dir.z = randf() - 0.5f;
dir.x *= (randf() < 0.2f) ? 0 : 1; // special case #1: dir.x/z == 0 are a special cases
dir.z *= (randf() < 0.2f) ? 0 : 1; // in GetQuadsOnRay(). We want to check those codes, too
dir.SafeNormalize();
float length = randf() * (WIDTH + HEIGHT) * 0.5f;
length = (randf() < 0.2f) ? randf() : length; // special case #1: when start & end are in the same quad
// #1: very naive way to raytrace (step-based interpolation)
auto plot = [&](float3 pos) {
const int x = Clamp<int>(pos.x, 0, WIDTH - 1);
const int z = Clamp<int>(pos.z, 0, HEIGHT - 1);
const int idx = z * WIDTH + x;
bitmap[idx] |= 1;
};
for (float l = 0.f; l <= length; l+=0.001f) {
float3 pos = start + dir * l;
plot(pos);
}
plot(start);
plot(start + dir * length);
// #2: raytrace via QuadField
{
QuadFieldQuery qfQuery;
qf.GetQuadsOnRay(qfQuery, start * SQUARE_SIZE, dir, length * SQUARE_SIZE);
assert( std::adjacent_find(qfQuery.quads->begin(), qfQuery.quads->end()) == qfQuery.quads->end() ); // check for duplicates
for (int qi: *qfQuery.quads) {
bitmap[qi] |= 2;
}
}
// check if #1 & #2 iterate same quads
for (int i = 0; i < WIDTH * HEIGHT; ++i) {
if (bitmap[i] == 0 || bitmap[i] == 3)
continue;
// only break when GetQuadsOnRay() returned LESS quads than the naive solution
// cause the naive solution uses step-based interpolation, and so it might jump
// over some edges when the ray is very close to the corner intersection (of 4 quads)
bool isAdditionalQuad = (bitmap[i] == 2);
if (!isAdditionalQuad) {
int* istart = reinterpret_cast<int*>(&start.x);
int* idir = reinterpret_cast<int*>(&dir.x);
int* ilength = reinterpret_cast<int*>(&length);
printf("start: 0x%X 0x%X 0x%X dir: 0x%X 0x%X 0x%X length: 0x%X\n", istart[0], istart[1], istart[2], idir[0], idir[1], idir[2], *ilength);
fail = true;
break;
}
}
if (fail) break;
}
BOOST_CHECK_MESSAGE(!fail, "Too less quads returned!");
}
|
