This PR replaces AffineTransform3D.estimateBounds(RealInterval) with a more efficient algorithm (O(n^2) in number of dimensions instead of O(2^n)).
Intermediate commits have a test comparing old vs new version and benchmarks. (So this PR should probably be squashed.)
The old algorithm took the corners of the input interval, passed them through the transform, then computed the bounding box of the transformed points.
The idea of the new algorithm is along these lines:
We can easily write an affine transform S that transforms the unit cube (min at origin, side length one) to the input interval.
Then we have to find the bounding box of the transformed unit cube via this * S.
Then ignore the translation part. That can be easily applied afterwards, shifting the estimated bounding box. So we only look at the 3x3 rotation/scale/shear matrix of this * S. Let's call this 3x3 matrix A. Because S is a diagonal matrix, A simply consists of scaled columns of this.
Now: The origin transforms to the origin. The unit vectors along each axis transform to the columns of A.
Because this is a linear transform, the transformed corners are the sum of all combinations of 0..3 of the transformed unit vectors. The bounding box is found without explicitly computing these corners, by looking at each dimension individually.
For example, for the minimum in X: origin is transformed to origin, so minimum can not be > 0. To get it lower than 0, we take those transformed unit vectors that have X<0. Summing over these 0..3 values X<0 gives the minimum in X. And analogous for max X and other dimensions.
This PR replaces
AffineTransform3D.estimateBounds(RealInterval)with a more efficient algorithm (O(n^2) in number of dimensions instead of O(2^n)).Intermediate commits have a test comparing old vs new version and benchmarks. (So this PR should probably be squashed.)
The old algorithm took the corners of the input interval, passed them through the transform, then computed the bounding box of the transformed points.
The idea of the new algorithm is along these lines:
We can easily write an affine transform
Sthat transforms the unit cube (min at origin, side length one) to the input interval. Then we have to find the bounding box of the transformed unit cube viathis * S.Then ignore the translation part. That can be easily applied afterwards, shifting the estimated bounding box. So we only look at the 3x3 rotation/scale/shear matrix of
this * S. Let's call this 3x3 matrixA. BecauseSis a diagonal matrix,Asimply consists of scaled columns ofthis.Now: The origin transforms to the origin. The unit vectors along each axis transform to the columns of
A. Becausethisis a linear transform, the transformed corners are the sum of all combinations of 0..3 of the transformed unit vectors. The bounding box is found without explicitly computing these corners, by looking at each dimension individually. For example, for the minimum in X: origin is transformed to origin, so minimum can not be > 0. To get it lower than 0, we take those transformed unit vectors that have X<0. Summing over these 0..3 values X<0 gives the minimum in X. And analogous for max X and other dimensions.Finally, add the translation part.