Extremely long triangles can result in poor tree construction

[gkjohnson]

If a geometry has extremely long triangles then it can result in nonoptimal bounds tree. Consider a 5 x 5 plane with the middle 3 x 3 vertices being offset by a large number:

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 X X X 0 0
0 0 X X X 0 0
0 0 X X X 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

0 is not offset, X is offset by 50 units in z

The current algorithm always uses the longest edge for both CENTER and AVERAGE strategies but in the above case for the first many splits with will almost always be on the Z Axis because even after splitting on z the triangles must be encapsulated by the bounds meaning the bounding box is just as long as the parent and Z will again be selected as the long edge.

It may be more intensive but selecting an edge based on how much resultant bounds overlap there is or which axis has the widest distribution of triangle centroids might be best.

Possible solutions

• take the axis that has the most spread out centroids
• take the axis that has on average the thinnest bounds

edit: A flat strip of triangles will illustrate this same behavior