Non-subgroup version of graph traversal

piet-gpu-simple-kernel-1.metal

struct StackElement {
    PietGroupRef group;
    uint index;
    float2 offset; // Maybe pack as short2?
}

kernel1(Buf scene, PietGroupRef root) {
    StackElement stack[MAX_STACK];
    uint stack_ix = 0;
    uint group = root;
    uint n = PietGroup_n(scene, group);
    BboxRef bboxes = PietGroup_bboxes(scene, group);
    ItemRef items = PietGroup_items(scene, group);
    float2 offset = PietGroup_offset(scene, group);
    uint index = 0;

    tilegroup_bounds = bounds of the tilegroup for this thread;

    while (1) {
        if (index < n) {
            bool hit = false;
            bool is_group = false;
            short2 bbox = Bbox_read(scene, bboxes + index * BBOX_SIZE);
            bool hit = bbox_intersects(bbox, tilegroup_bounds);
            if (hit) {
                if PietItem_tag(scene, items + index * PIET_ITEM_SIZE) == Group {
                    is_group = true;
                }
            }

            if (hit && !is_group) {
                ItemRef itemref;
                itemref.item = items + index * PIET_ITEM_SIZE;
                itemref.offset = offset;
                write itemref to output
            }

            if (is_group) {
                PietGroupRef new_group = items + index * PIET_ITEM_SIZE;
                uint next_ix = index + 1;
                if (next_ix < n) {
                    // Push stack
                    StackElement el;
                    el.group = group;
                    el.index = next_ix;
                    el.offset = offset;
                    stack[stack_ix] = el;
                    stack_ix++;
                }
                group = new_group;
                n = PietGroup_n(scene, group);
                bboxes = PietGroup_bboxes(scene, group);
                items = PietGroup_items(scene, group);
                offset += PietGroup_offset(scene, group);
                index = 0;
            } else {
                index += 1;
            }
        }
    } else {
        // processed all items in this group; pop the stack
        if (stack_ix == 0) {
            break;
        }
        stack_ix--;
        group = stack[stack_ix].group;
        index = stack[stack_ix].index;
        offset = stack[stack_ix].offset;
        n = PietGroup_n(scene, group);
        bboxes = PietGroup_bboxes(scene, group);
        items = PietGroup_items(scene, group);
    }
}