More robust oriented bounding box computations

[javagl]

The OrientedBoundingBox::fromPoints method implements an eigenvector-based approach for computing the oriented bounding box of the given set of points, as decribed in "Collision queries using oriented bounding boxes" by Stefan Gottschalk (PDF file).

This approach is prone to distortions - roughly: When there is a "dense" set of points that do not contribute to the actual extremes, then these points will cause a suboptimal eigenvector to be computed. This can be observed, for example, in these cases:

1. An oriented bounding box of a cube-shaped set of points: The bounding box is not tightly fitting

   

2. An oriented bounding box that was computed from the corners of the first bounding box - this fits perfectly:

   

3. When adding a few more of the original points, the oriented bounding box becomes worse:

   

This happens although these inner points should not affect the bounding box. This phenomenon is also described in the original thesis:

Approaches for improving the robustness are described in the thesis as well. The most important one is to compute the bounding box not based on all points, but only based on the points of the convex hull of the original points. The idea here is that only the "extreme" points should contribute to the eigenvector computation.

I tried this out, with the quickhull3d library. It does improve the result in some cases - for example, the case 3. from the list above does no longer cause any problems. But still, depending on the exact arrangement of the points, the convex hull may not solve the issue. For example, when computing the convex hull of the cube-shaped set of points, then the hull contains some triangles that are not exactly the "cube faces", but only inserted due to inaccuracies. Depending on where exactly these points are, they may still distort the eigenvectors.

I tried to go one step further, and applied the MeshoptSimplifier.simplify method of the meshoptimizer library to the convex hull, with the goal to get rid of the triangles that are only caused by these inaccuracies. But even when the (optimized) convex hull is a perfect cube, the approach does not necessarily yield good (or even "not bad") oriented bounding boxes:

The thesis specifically mentions an approach for computing the covariance matrix (that serves as the basis for computing the eigenvectors) based on triangles (and not only based on vertices/points). But....

• the implementation becomes a bit more complex
• it still requires the computation of the convex hull
• it might still require the optimization/simplification of the convex hull
• and it's still not clear whether that would solve the issue and yield "good" bounding boxes more reliably

[javagl]

I did some experiments for computing the bounding box with https://github.com/Esri/dito.ts . The results are summarized in CesiumGS/3d-tiles-tools#79 (comment) .

The tl;dr is: The method is noticably slower, but gives better results in nearly all cases.

The implementation in dito.ts was ported from the original C/C++-based implementation. It uses some vector math (really simple things, add/subtract/dot/length) that is implemented based on raw arrays. Iff this method should be supported by CesiumJS, then one could consider to implement it based on the existing Cartesian* classes.

[javagl]

Just establishing a connection to #4785 here...

[ggetz]

@javagl Would you call these duplicates? I'd be in favor of consolidating these issues.

[javagl]

@ggetz The older issue does not provide sooo much specific information beyond this one, except for

• The link to "Game Engine Gems 2"
• A link to Culling / OBB optimizations #2861 with some additional links and somewhat broader questions

(The task to port the results from CesiumGS/3d-tiles-tools#79 (comment) to CesiumJS is on my TODO-list, but in the "When I'm really bored"-section 😁 )

I think that either of them could be closed. This one has a bit more specific information. So closing the older one with a comment pointing to this one could make sense.