Seeking some information on BVH optimization

[lmtss]

Hi,

I'm new to physics engine and I'm learning optimization of bvh through your code. Could you provide some references about your implementation? Like some papers?

Tree_BinnedRefine.cs confuses me a bit, I wonder if there is a literature reference for this.

[RossNordby]

Binned BVH builders are described in this paper: https://www.sci.utah.edu/~wald/Publications/2007/ParallelBVHBuild/fastbuild.pdf

During a refinement step, the Tree applies binned builders to parts of a tree (not just subsets of leaves; blobs of internal nodes can be optimized too). It turns out that, over time, this converges to high quality with very low per-step cost.

There is some trickiness to deciding where to apply those refinements. The BroadPhase schedules them near the root and close to a subset of leaves stochastically chosen partially by increases in SAH cost that indicate the existing structure is becoming worse.

It's worth noting that the Tree implementation is old. By far the oldest part of bepuphysics2. A lot of it is based on assumptions and requirements that no longer exist, so don't be surprised if you find some pretty dang suboptimal stuff in there. It's on the todo list for a major overhaul. The new version will still be conceptually similar on a high level, though; I don't anticipate moving away from incremental binned optimization.

[lmtss]

Thank you!

I was referring to major structural changes to the binned refiner which would make that kind of allocation less necessary

What kind of binned builder makes preallocation less necessary? I think the binned builder needs to pre-allocate some space to store the information of each bin (bin-bounds, bin-leafcount..) and the indexmap of the leaf nodes. I can only think of reducing some unnecessary caches, such as the precalculating centroids mentioned in the comments

[RossNordby]

I'd expect a fairly similar amount of memory to be used overall (within some constant factor), It's mostly just moving allocations around in a way that could be a bit more convenient for the implementation. stackalloc where possible and useful, for example. Possibly some changes for a better vectorized implementation.

[lmtss]

Thank you for your patience in answering my doubts.

[RossNordby]

Well, I got around to actually revamping the binned refinement process. Turns out there were a lot of opportunities for improvements. The only preallocations are now some data for bins:

bepuphysics2/BepuPhysics/Trees/Tree_BinnedBuilder.cs

Lines 112 to 121 in 32eb5b9

	struct Bins
	{
	public Buffer<BoundingBox4> BinBoundingBoxes;
	public Buffer<BoundingBox4> BinBoundingBoxesScan;
	public Buffer<int> BinLeafCounts;
	public int MinimumBinCount;
	public int MaximumBinCount;
	public float LeafToBinMultiplier;
	public int MicrosweepThreshold;
	}

It works on the input buffers in-place, so there's no need for additional resources.

It's also 4-6 times faster :P

(Not quite done; it's not actually used in the engine yet- going to implement a multithreaded codepath too.)

[lmtss]

Cool! This is a good reference!! Thank you!