lavapipe: Use the common BVH framework
Based on !28446.
There were a few changes required to make this work:
- A patch that adds lavapipe support to the radix sort code had to be ported.
- The ploc build shader has to handle the small subgroup size used by lavapipe.
- The gallivm loop limiting has to be removed, since the ploc build shader has a loop that waits for other threads to finish and the loop limit can run out before that is the case.
- Deep BVHs have to be flattened, because lavapipe uses a fixed size stack. The algorithm for flattening looks like this:
- Count the number of total child leaf nodes for every internal.
- Search for subtrees that need to be flattened (if the leaf node count exceeds a threshold calculated from the node depth)
- Build a list of every leaf/internal node of the subtree.
- Build a "flat" BVH by recursively splitting the leaf node list in the middle.