| // SPDX-License-Identifier: Apache-2.0 OR MIT OR Unlicense |
| |
| // The reduction phase for the blend/union test |
| |
| #version 450 |
| |
| // At least for now, N_SEQ is hardwired at 1 |
| #define LG_WG_SIZE 8 |
| #define WG_SIZE (1 << LG_WG_SIZE) |
| #define PART_SIZE WG_SIZE |
| |
| layout(local_size_x = WG_SIZE, local_size_y = 1) in; |
| |
| // The bicyclic semigroup (monoid) |
| struct Bic { |
| uint a; |
| uint b; |
| }; |
| |
| struct BicBbox { |
| Bic bic; |
| uint pad2; |
| uint pad3; |
| vec4 bbox; |
| }; |
| |
| Bic bic_combine(Bic x, Bic y) { |
| uint m = min(x.b, y.a); |
| return Bic(x.a + y.a - m, x.b + y.b - m); |
| } |
| |
| // Node type values |
| #define OPEN_PAREN 0 |
| #define CLOSE_PAREN 1 |
| |
| struct Node { |
| uint node_type; |
| uint pad1; |
| uint pad2; |
| uint pad3; |
| vec4 bbox; |
| }; |
| |
| vec4 bbox_union(vec4 a, vec4 b) { |
| return vec4(min(a.xy, b.xy), max(a.zw, b.zw)); |
| } |
| |
| layout(binding = 0) readonly buffer InBuf { |
| Node[] inbuf; |
| }; |
| |
| layout(binding = 1) buffer BicBuf { |
| BicBbox[] bicbuf; |
| }; |
| |
| // Output buffer for stack slice data |
| layout(binding = 2) buffer StackBuf { |
| // open question: do we need the parent link or are bboxes sufficient? |
| vec4[] stack; |
| }; |
| |
| shared Bic sh_bic[WG_SIZE]; |
| shared vec4 sh_bbox[WG_SIZE]; |
| |
| void main() { |
| Node inp = inbuf[gl_GlobalInvocationID.x]; |
| uint node_type = inp.node_type; |
| vec4 bbox = inp.bbox; |
| Bic bic = Bic(uint(node_type == CLOSE_PAREN), uint(node_type == OPEN_PAREN)); |
| sh_bic[gl_LocalInvocationID.x] = bic; |
| sh_bbox[gl_LocalInvocationID.x] = bbox; |
| for (uint i = 0; i < LG_WG_SIZE; i++) { |
| barrier(); |
| uint other_ix = gl_LocalInvocationID.x + (1u << i); |
| if (other_ix < WG_SIZE) { |
| bic = bic_combine(bic, sh_bic[other_ix]); |
| bbox = bbox_union(bbox, sh_bbox[other_ix]); |
| } |
| barrier(); |
| sh_bic[gl_LocalInvocationID.x] = bic; |
| sh_bbox[gl_LocalInvocationID.x] = bbox; |
| } |
| if (gl_LocalInvocationID.x == 0) { |
| BicBbox bic_bbox = BicBbox(bic, 0, 0, bbox); |
| bicbuf[gl_WorkGroupID.x] = bic_bbox; |
| } |
| barrier(); |
| // Number of elements in stack slice output by this partition |
| uint size = sh_bic[0].b; |
| bic = Bic(0, 0); |
| if (gl_LocalInvocationID.x + 1 < WG_SIZE) { |
| bic = sh_bic[gl_LocalInvocationID.x + 1]; |
| } |
| // Do stream compaction |
| if (inp.node_type == OPEN_PAREN && bic.a == 0) { |
| uint out_ix = gl_WorkGroupID.x * PART_SIZE + size - bic.b - 1; |
| stack[out_ix] = sh_bbox[gl_LocalInvocationID.x]; |
| } |
| } |