mathematics – Triangle area selection using BVH raycasting

Let’s assume I’m already storing a BVH acceleration structure per mesh on my engine and I’d like start
making area selection like on many DCC tools out there, for instance, blender.

With blender you can do {rectangular, circle, lasso} selection to select faces and I’d like to understand the maths behind these algorithms. If I was using color picking techniques these sort of algorithms would be obvious but when using BVH+raycasting I’m still failing to understand the algo/maths behind it.

So, could you please explain the logic behind those? For instance, I assume rectangular selection should be easier to implement than circle/lasso, so how would you gather all screen projected triangles living inside the rectangular selection created by the mouse?

algorithms – BVH construction without sorting

Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives directly or using an index which is then sorted. What if we are not allowed to change the order of the primitives? More formally:

Let $P={p_1, p_2, …, p_k}$ be an ordered set of primitives. A BVH can be constructed by splitting the set of indices $I={1,2,…,k}$ into two subsets $I_l$ and $I_r$ so that $I_lcap I_r=emptyset$ and $I_l cup I_r=I$. $I_l$ and $I_r$ correspond to the indices of all primitives in the left and right child node of the root node. This procedure then repeats recursively for $I_l$ and $I_r$ and so on.
Now add the additional constraint that $forall i in I_l forall j in I_r(i<j)$. This prevents rearranging and makes the problem quite interesting in my opinion.

The quality of the best achievable BVH without rearranging primitives depends heavily on the initial order of the primitives. Instead of choosing a spatial split position, for example using the surface area heuristic, we are restricted to choosing a split index instead. My guess is that this would make agglomerative clustering algorithms much more attractive, as only adjacent primitives can be clustered together, not arbitrary pairs of primitives.

Has this problem been studied in the literature before?

data structures – Why are these BVH split heuristic formulas different?

I’ve been doing some research into changing the split heuristic I use for a work project comprised of a BVH binary tree.

The heuristic I currently use is centroid median as described here, but I seek to use the surface area heuristic (SAH) now. Several papers denote the cost function for determining the split as:

$$c(A, B) = t_{trav} + p_{A}sum_{i=1}^{N_{A}}t_{isect}(a_{i}) + p_{B}sum_{i=1}^{N_{B}}t_{isect}(b_{i})$$

Notionally it is described in detail here, but to summarize, it is the cost of a ray intersect of primitives at this split.

However, I’ve seen an optimization technique, described as “binning”, where $K$ pre-determined bins are computed and therefore the cost function for determining the split is:

$$c(A, B) = A_{a}N_{a} + A_{b}N_{b}$$

This is outlined here in Section 3.1, as well is several other documents (1, 2, 3).

What’s the rational/reasoning behind these two different cost models?