Space Sim
Loading...
Searching...
No Matches
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
15layout (local_size_x = WORKGROUP_SIZE) in;
16
17struct MortonEntry
18{
19 uint pid;
20 uint morton;
21 // uint64_t key;
22};
23layout(std430, binding=2) buffer MortonData {
24
25 MortonEntry entry[];
26};
27struct 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
39layout(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};
50int 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
71int 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
77void 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(local_size_x=16, local_size_y=16, local_size_z=1) in
int main(int argc, char *argv[])
Definition main.c:1726
vec3 max
Definition com22.comp:49
vec4 com_m
Definition com22.comp:45
int next
Definition com22.comp:50
ivec4 lrpd
Definition com22.comp:52
vec4 min
Definition com22.comp:47
Definition bounds.comp:30
Definition types.h:109
const vec3 delta[8]
uint morton(uint x, uint y, uint z)
Definition morton.comp:68
int shared_prefix(uint m0, uint pid0, uint m1, uint pid1)
Definition tree.comp:50
#define WORKGROUP_SIZE
Definition types.h:171
#define MAX_DEPTH
Definition types.h:154
#define BODY_COUNT
Definition types.h:39
#define MAX_NODES
Definition types.h:40
Definition types.h:47
uniform float t
Definition water.comp:23