-
Notifications
You must be signed in to change notification settings - Fork 37
/
basics.cpp
201 lines (185 loc) · 6.14 KB
/
basics.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include "precomp.h"
#include "basics.h"
// THIS SOURCE FILE:
// Code for the article "How to Build a BVH", part 1: basics. Link:
// https://jacco.ompf2.com/2022/04/13/how-to-build-a-bvh-part-1-basics
// This is bare-bones BVH construction and traversal code, running in
// a minimalistic framework.
// Feel free to copy this code to your own framework. Absolutely no
// rights are reserved. No responsibility is accepted either.
// For updates, follow me on twitter: @j_bikker.
TheApp* CreateApp() { return new BasicBVHApp(); }
// triangle count
#define N 64
// forward declarations
void Subdivide( uint nodeIdx );
void UpdateNodeBounds( uint nodeIdx );
// minimal structs
struct Tri { float3 vertex0, vertex1, vertex2; float3 centroid; };
__declspec(align(32)) struct BVHNode
{
float3 aabbMin, aabbMax;
uint leftFirst, triCount;
bool isLeaf() { return triCount > 0; }
};
struct Ray { float3 O, D; float t = 1e30f; };
// application data
Tri tri[N];
uint triIdx[N];
BVHNode bvhNode[N * 2];
uint rootNodeIdx = 0, nodesUsed = 1;
// functions
void IntersectTri( Ray& ray, const Tri& tri )
{
const float3 edge1 = tri.vertex1 - tri.vertex0;
const float3 edge2 = tri.vertex2 - tri.vertex0;
const float3 h = cross( ray.D, edge2 );
const float a = dot( edge1, h );
if (a > -0.0001f && a < 0.0001f) return; // ray parallel to triangle
const float f = 1 / a;
const float3 s = ray.O - tri.vertex0;
const float u = f * dot( s, h );
if (u < 0 || u > 1) return;
const float3 q = cross( s, edge1 );
const float v = f * dot( ray.D, q );
if (v < 0 || u + v > 1) return;
const float t = f * dot( edge2, q );
if (t > 0.0001f) ray.t = min( ray.t, t );
}
bool IntersectAABB( const Ray& ray, const float3 bmin, const float3 bmax )
{
float tx1 = (bmin.x - ray.O.x) / ray.D.x, tx2 = (bmax.x - ray.O.x) / ray.D.x;
float tmin = min( tx1, tx2 ), tmax = max( tx1, tx2 );
float ty1 = (bmin.y - ray.O.y) / ray.D.y, ty2 = (bmax.y - ray.O.y) / ray.D.y;
tmin = max( tmin, min( ty1, ty2 ) ), tmax = min( tmax, max( ty1, ty2 ) );
float tz1 = (bmin.z - ray.O.z) / ray.D.z, tz2 = (bmax.z - ray.O.z) / ray.D.z;
tmin = max( tmin, min( tz1, tz2 ) ), tmax = min( tmax, max( tz1, tz2 ) );
return tmax >= tmin && tmin < ray.t && tmax > 0;
}
void IntersectBVH( Ray& ray, const uint nodeIdx )
{
BVHNode& node = bvhNode[nodeIdx];
if (!IntersectAABB( ray, node.aabbMin, node.aabbMax )) return;
if (node.isLeaf())
{
for (uint i = 0; i < node.triCount; i++ )
IntersectTri( ray, tri[triIdx[node.leftFirst + i]] );
}
else
{
IntersectBVH( ray, node.leftFirst );
IntersectBVH( ray, node.leftFirst + 1 );
}
}
void BuildBVH()
{
// populate triangle index array
for (int i = 0; i < N; i++) triIdx[i] = i;
// calculate triangle centroids for partitioning
for (int i = 0; i < N; i++)
tri[i].centroid = (tri[i].vertex0 + tri[i].vertex1 + tri[i].vertex2) * 0.3333f;
// assign all triangles to root node
BVHNode& root = bvhNode[rootNodeIdx];
root.leftFirst = 0, root.triCount = N;
UpdateNodeBounds( rootNodeIdx );
// subdivide recursively
Subdivide( rootNodeIdx );
}
void UpdateNodeBounds( uint nodeIdx )
{
BVHNode& node = bvhNode[nodeIdx];
node.aabbMin = float3( 1e30f );
node.aabbMax = float3( -1e30f );
for (uint first = node.leftFirst, i = 0; i < node.triCount; i++)
{
uint leafTriIdx = triIdx[first + i];
Tri& leafTri = tri[leafTriIdx];
node.aabbMin = fminf( node.aabbMin, leafTri.vertex0 ),
node.aabbMin = fminf( node.aabbMin, leafTri.vertex1 ),
node.aabbMin = fminf( node.aabbMin, leafTri.vertex2 ),
node.aabbMax = fmaxf( node.aabbMax, leafTri.vertex0 ),
node.aabbMax = fmaxf( node.aabbMax, leafTri.vertex1 ),
node.aabbMax = fmaxf( node.aabbMax, leafTri.vertex2 );
}
}
void Subdivide( uint nodeIdx )
{
// terminate recursion
BVHNode& node = bvhNode[nodeIdx];
if (node.triCount <= 2) return;
// determine split axis and position
float3 extent = node.aabbMax - node.aabbMin;
int axis = 0;
if (extent.y > extent.x) axis = 1;
if (extent.z > extent[axis]) axis = 2;
float splitPos = node.aabbMin[axis] + extent[axis] * 0.5f;
// in-place partition
int i = node.leftFirst;
int j = i + node.triCount - 1;
while (i <= j)
{
if (tri[triIdx[i]].centroid[axis] < splitPos)
i++;
else
swap( triIdx[i], triIdx[j--] );
}
// abort split if one of the sides is empty
int leftCount = i - node.leftFirst;
if (leftCount == 0 || leftCount == node.triCount) return;
// create child nodes
int leftChildIdx = nodesUsed++;
int rightChildIdx = nodesUsed++;
bvhNode[leftChildIdx].leftFirst = node.leftFirst;
bvhNode[leftChildIdx].triCount = leftCount;
bvhNode[rightChildIdx].leftFirst = i;
bvhNode[rightChildIdx].triCount = node.triCount - leftCount;
node.leftFirst = leftChildIdx;
node.triCount = 0;
UpdateNodeBounds( leftChildIdx );
UpdateNodeBounds( rightChildIdx );
// recurse
Subdivide( leftChildIdx );
Subdivide( rightChildIdx );
}
void BasicBVHApp::Init()
{
// intialize a scene with N random triangles
for (int i = 0; i < N; i++)
{
float3 r0 = float3( RandomFloat(), RandomFloat(), RandomFloat() );
float3 r1 = float3( RandomFloat(), RandomFloat(), RandomFloat() );
float3 r2 = float3( RandomFloat(), RandomFloat(), RandomFloat() );
tri[i].vertex0 = r0 * 9 - float3( 5 );
tri[i].vertex1 = tri[i].vertex0 + r1, tri[i].vertex2 = tri[i].vertex0 + r2;
}
// construct the BVH
BuildBVH();
}
void BasicBVHApp::Tick( float deltaTime )
{
// draw the scene
screen->Clear( 0 );
// define the corners of the screen in worldspace
float3 p0( -1, 1, -15 ), p1( 1, 1, -15 ), p2( -1, -1, -15 );
Ray ray;
Timer t;
for (int y = 0; y < SCRHEIGHT; y++) for (int x = 0; x < SCRWIDTH; x++)
{
// calculate the position of a pixel on the screen in worldspace
float3 pixelPos = p0 + (p1 - p0) * (x / (float)SCRWIDTH) + (p2 - p0) * (y / (float)SCRHEIGHT);
// define the ray in worldspace
ray.O = float3( 0, 0, -18 );
ray.D = normalize( pixelPos - ray.O );
// initially the ray has an 'infinite length'
ray.t = 1e30f;
#if 0
for( int i = 0; i < N; i++ ) IntersectTri( ray, tri[i] );
#else
IntersectBVH( ray, rootNodeIdx );
#endif
if (ray.t < 1e30f) screen->Plot( x, y, 0xffffff );
}
float elapsed = t.elapsed() * 1000;
printf( "tracing time: %.2fms (%5.2fK rays/s)\n", elapsed, sqr( 630 ) / elapsed );
}
// EOF