From Manta Wiki

kd-tree build code

The khoff build code was written by Kenny Hoff at SGI. It is a clean open source rewrite of the original build code used in May 2005. The code hasn't been integrated into the svn repository because the builder isn't being actively maintained and uses a separate software infrastructure.

Questions

What does each parameter mean?

Here is Kenny Hoff's description of each parameter:

On Wednesday 08 February 2006 6:15 pm, you wrote:

>> Can you remind me again what each of these parameters does technically?

Sure, basically, we *only* use ChildParentCostRatio now. The fast splitting and the empty volume splitting were shown numerous times to have no effect for our more complex models. The intel folks seemed to get benefit from the volume split, but there models were either very small or very regular (e.g. soda hall, etc).

>> ChildParentCostRatio=0.90

The sum of the costs of the children must be at most 90% of the parent cost before allowing the split.

>> MaxSizeToSlowSplit=7219045

If the number of triangles in a node is > MaxSizeToSlowSplit, then just use a simple fast split (e.g. middle of longest axis). The idea here was that most of the top level splits are just trying to chop off huge volumes anyways, so just go for the middle. Also, these are where most of the build time is spent (Hansong said that for the Boeing, 30% of the time is spent on the very first split). We normally just slow split everything now, but I rarely see any change in performance for far lower values. If you want to see the other extreme, put this value to 0. Then the entire tree will be fast splits. In this case, I've seen as much as 50% reduced performance. The slow splits at or near the leaves seems to be a HUGE win.

>> FracOfParentVolToSplit=0.10

This is straight from Intel's paper. They try to favor large empty volumes higher in the tree. So, as a fast first check, they try the min/max extremes and see if it creates an empty volume of at least 10% of the original parent volume. If it does, trivially split it off.

BTW, I have the new, much cleaner tree-building code that builds in a breadth-first fashion straight to disk. The sequential version has a minimal memory footprint and is quite efficient. However, I've had a lot of difficulty parallelizing it, so we've put that work on hold in favor of working on inner loop Manta optimizations.