OBD talk:PNTA

From HERE

A description of some of the basic algorithms and their shortcomings is listed below:

1. The mean of the input points – This very simple and linear algorithm is the simplest of all but can give extremely bad results due to point clustering. The sphere can have up to twice the optimal radius. Clearly this is not the way to go.
2. A sphere contained within an AABB – A simple approximation is to find the AABB enclosing all points and obtaining the midpoint (the sphere's center) and the radius to be the distance from this center to the farthest point. While this approach is fairly simple and provides adequate results, it does not compare to the optimal solution.
3. Computing a sphere using maximum spread – This approach attempts to find the axis direction of the maximum spread of the input points and uses it as the diameter of the sphere. The points most extreme on the axis are selected and the center is set halfway between them. Although an interesting approach, it suffers from problems due to point clustering and internal points ruining the covariance.
4. Brute force – Since a sphere in 3D is uniquely defined by four points (two in 2D), a simple brute force approach might attempt to find the minimum sphere by trying all combination of spheres made up by four points, three points and two points, keeping the minimum-sized sphere that contains all points. This approach is the worst with a running complexity of O(n5).

AFAIK, OniSplit uses 1, and as for Oni, it may even be using "0" (a sphere containing the AABB). Is this correct?

geyser 23:22, 24 May 2008 (CEST)