Space Sim
Toggle main menu visibility
Loading...
Searching...
No Matches
src
particles
tree.comp
Go to the documentation of this file.
1
2
#version 440
8
#define WORKGROUP_SIZE 128
9
#define RADIX_SORT_BINS 128
10
#define SUBGROUP_SIZE 32
11
12
#define BODY_COUNT 15000
13
#define MAX_NODES 45000
14
15
layout
(local_size_x =
WORKGROUP_SIZE
) in;
16
17
struct
MortonEntry
18
{
19
uint
pid
;
20
uint
morton
;
21
// uint64_t key;
22
};
23
layout
(std430, binding=2) buffer
MortonData
{
24
25
MortonEntry
entry[];
26
};
27
struct
Node
{
28
vec4
com_m
;
29
// min and size
30
vec4
min
;
31
// max and next
32
vec3
max
;
33
int
next
;
34
// left child, right child, parent, depth
35
ivec4
lrpd
;
36
// ivec4 next;
37
};
38
#define MAX_DEPTH 64
39
layout
(std430, binding=4) buffer
NodeData
{
40
uint ready_queue[
MAX_NODES
];
41
uint children_remaining[
MAX_NODES
];
42
uint depth_offsets[
MAX_DEPTH
+1];
43
vec4
com_m[
MAX_NODES
];
44
vec4
lrsn[
MAX_NODES
];
45
// min and parent
46
vec4
nmin[
MAX_NODES
];
47
// max and depth
48
vec4
nmax[
MAX_NODES
];
49
};
50
int
shared_prefix
(uint m0, uint pid0, uint m1, uint pid1) {
51
uint x = m0 ^ m1;
52
int
count = 0;
53
for
(
int
i = 31; i >= 0; i--)
54
{
55
if
((x & (uint(1) << i)) == uint(0)) count++;
56
else
{
57
return
count;
58
}
59
}
60
uint p = pid0 ^ pid1;
61
for
(
int
i = 31; i >= 0; i--)
62
{
63
if
((p & (uint(1) << i)) == uint(0)) count++;
64
else
{
65
return
count;
66
}
67
}
68
return
count;
69
}
70
71
int
delta
(
int
a,
int
b)
72
{
73
if
(b < 0 || b >=
BODY_COUNT
)
return
-1;
74
return
shared_prefix
(entry[a].
morton
, entry[a].pid, entry[b].
morton
, entry[b].pid);
75
}
76
77
void
main
()
78
{
79
int
i = int(gl_GlobalInvocationID.x);
80
if
(i >=
BODY_COUNT
- 1)
return
;
81
82
// the least common prefixes between left and right leaves
83
int
left_lcp = (i > 0) ?
shared_prefix
(entry[i].
morton
, entry[i].pid, entry[i-1].
morton
, entry[i-1].pid) : -1;
84
int
right_lcp = (i <
BODY_COUNT
-1) ?
shared_prefix
(entry[i].
morton
, entry[i].pid, entry[i+1].
morton
, entry[i+1].pid) : -1;
85
86
// dir
87
int
d = (right_lcp > left_lcp) ? 1 : -1;
88
89
int
delta_min =
delta
(i, i - d);
90
int
lmax = 2;
91
// search in dir to find the point we break with delta_min
92
while
(
true
)
93
{
94
int
idx = int(i) + lmax * d;
95
if
(idx < 0 || idx >=
BODY_COUNT
)
break
;
96
if
(
shared_prefix
(entry[i].
morton
, entry[i].pid, entry[idx].
morton
, entry[idx].pid) <= delta_min)
break
;
97
lmax *= 2;
98
}
99
100
// search for the opposite end of the split
101
int
l = 0;
102
for
(
int
t
= lmax / 2;
t
>= 1;
t
/= 2)
103
{
104
int
idx = int(i) + (l +
t
) * d;
105
if
(idx < 0 || idx >=
BODY_COUNT
)
continue
;
106
if
(
shared_prefix
(entry[i].
morton
, entry[i].pid, entry[idx].
morton
, entry[idx].pid) > delta_min) l +=
t
;
107
}
108
109
110
int
j = i + l * d;
111
int
first = min(i, j);
112
int
last = max(i, j);
113
int
split = first;
114
int
step = last - first;
115
116
// full delta from start to finish
117
int
delta_node =
delta
(first, last);
118
do
{
119
step = (step + 1) >> 1;
120
int
new_split = split + step;
121
// trying to find the lowest split to find node bounds
122
if
(new_split < last)
123
{
124
int
delta
=
delta
(first, new_split);
125
if
(
delta
> delta_node) split = new_split;
126
}
127
}
while
(step > 1);
128
129
// body count is our leaf count
130
uint parent_node =
BODY_COUNT
+ i;
131
132
// LEFT CHILD
133
if
(split == first)
134
{
135
lrsn[parent_node].x = intBitsToFloat(first);
136
}
137
else
138
{
139
lrsn[parent_node].x = intBitsToFloat(
BODY_COUNT
+ split);
140
}
141
142
// RIGHT CHILD
143
if
(split + 1 == last)
144
{
145
lrsn[parent_node].y = intBitsToFloat(split + 1);
146
}
147
else
148
{
149
lrsn[parent_node].y = intBitsToFloat(
BODY_COUNT
+ split + 1);
150
}
151
152
153
// set parent of both children to parent node index
154
nmin[floatBitsToInt(lrsn[parent_node].x)].w = intBitsToFloat(
int
(parent_node));
155
nmin[floatBitsToInt(lrsn[parent_node].y)].w = intBitsToFloat(
int
(parent_node));
156
157
158
}
layout
layout(local_size_x=16, local_size_y=16, local_size_z=1) in
main
int main(int argc, char *argv[])
Definition
main.c:1726
Node::max
vec3 max
Definition
com22.comp:49
MortonEntry::pid
uint pid
Definition
bounds.comp:31
Node::com_m
vec4 com_m
Definition
com22.comp:45
Node::next
int next
Definition
com22.comp:50
Node::lrpd
ivec4 lrpd
Definition
com22.comp:52
Node::min
vec4 min
Definition
com22.comp:47
MortonEntry
Definition
bounds.comp:30
Node
Definition
types.h:109
delta
const vec3 delta[8]
Definition
marching_cubes.comp:91
morton
uint morton(uint x, uint y, uint z)
Definition
morton.comp:68
shared_prefix
int shared_prefix(uint m0, uint pid0, uint m1, uint pid1)
Definition
tree.comp:50
WORKGROUP_SIZE
#define WORKGROUP_SIZE
Definition
types.h:171
MAX_DEPTH
#define MAX_DEPTH
Definition
types.h:154
BODY_COUNT
#define BODY_COUNT
Definition
types.h:39
MAX_NODES
#define MAX_NODES
Definition
types.h:40
MortonData
Definition
types.h:140
NodeData
Definition
types.h:156
vec4
Definition
types.h:47
t
uniform float t
Definition
water.comp:23
Generated by
1.18.0