[
https://issues.apache.org/jira/browse/GEOMETRY-119?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17316279#comment-17316279
]
Matt Juntunen commented on GEOMETRY-119:
----------------------------------------
I was able to get the best performance using the following code. It tries the
unscaled norm first (which should be the majority of cases in actual usage) and
then, failing that, attempts to scale the coordinate values.
{code:java}
private static Unit tryCreateNormalized(final double x, final double y, final
double z,
final boolean throwOnFailure) {
// Compute the inverse norm directly. If the result is a non-zero
real number,
// then we can go ahead and construct the unit vector immediately.
If not,
// we'll do some extra work for edge cases.
final double norm = Math.sqrt((x * x) + (y * y) + (z * z));
final double normInv = 1.0 / norm;
if (Vectors.isRealNonZero(normInv)) {
return new Unit(
x * normInv,
y * normInv,
z * normInv);
}
// Direct computation did not work. Try scaled versions of the
coordinates
// to handle overflow and underflow.
final double scaledX;
final double scaledY;
final double scaledZ;
final double maxCoord = Math.max(Math.max(Math.abs(x),
Math.abs(y)), Math.abs(z));
if (maxCoord > UNSCALED_MAX) {
scaledX = x * SCALE_DOWN_FACTOR;
scaledY = y * SCALE_DOWN_FACTOR;
scaledZ = z * SCALE_DOWN_FACTOR;
} else {
scaledX = x * SCALE_UP_FACTOR;
scaledY = y * SCALE_UP_FACTOR;
scaledZ = z * SCALE_UP_FACTOR;
}
final double scaledNormInv = 1.0 / Math.sqrt(
(scaledX * scaledX) +
(scaledY * scaledY) +
(scaledZ * scaledZ));
if (Vectors.isRealNonZero(scaledNormInv)) {
return new Unit(
scaledX * scaledNormInv,
scaledY * scaledNormInv,
scaledZ * scaledNormInv);
} else if (throwOnFailure) {
throw Vectors.illegalNorm(norm);
}
return null;
}
{code}
I also ran some performance metrics on using {{Optional}} vs just returning
null. The two approaches are virtually the same with small numbers of inputs
but there is a consistent penalty for large numbers of inputs. The table below
shows scores averaged over 5 benchmark runs with an input of 10000 vectors.
||method||score (ns)||
|optional|426715.7478|
|null|407998.161|
Based on this, I believe the best approach is to skip using {{Optional}} and
just use {{normalizeOrNull}}. Calllers can easily use {{Optional}} in their own
code and accept the performance penalty by just calling
{{Optional.ofNullable(v.normalizeOrNull)}}. However, if we returned
{{Optional}} from the vector method, there would be no way for calllers to opt
out of the penalty.
I've updated the [PR|https://github.com/apache/commons-geometry/pull/143] with
these changes. Any more thoughts on this?
> Vector normalizeOrDefault() method
> ----------------------------------
>
> Key: GEOMETRY-119
> URL: https://issues.apache.org/jira/browse/GEOMETRY-119
> Project: Apache Commons Geometry
> Issue Type: Improvement
> Reporter: Matt Juntunen
> Priority: Major
>
> A frequent use case when working with vectors, especially vectors coming from
> external data, is attempting to normalize the vector, and if this is not
> possible, to use an alternative value. For example, the
> {{QuaternionRotation}} code
> [here|https://github.com/apache/commons-geometry/blob/master/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/rotation/QuaternionRotation.java#L86]
> does exactly this; it attempts to normalize a vector and failing that (ie,
> if the vector is exactly zero), it returns a substitute value. The
> {{QuaternionRotation}} class is able to take advantage of our internal
> {{Vectors.tryNormalize()}} but callers outside of the library are not able to
> do so and so are left with 2 choices:
> 1. wrap the {{normalize()}} call in a try-catch and handle the exception
> thrown on illegal norm values, or
> 2. compute and test the norm prior to calling {{normalize()}} to ensure that
> the call won't fail, resulting in 2 computations of the norm.
> Neither of these options are very good.
> I propose adding a new method to the Euclidean Vector classes to handle this
> situation: {{normalizeOrDefault()}}. The method would accept a default value
> (possibly null) to return if the vector cannot be normalized. The normal
> would then only need to be computed once and an exception would not need to
> be thrown in case of failure. The behavior of the current {{normalize}}
> method would be the same.
> Examples:
> {code:java}
> // get some kind of normal, preferably vec but +z will also do
> Vector3D.Unit norm = vec.normalizeOrDefault(Vector3D.Unit.PLUS_Z);
> {code}
> {code:java}
> // throw a very use-case specific error message
> Vector3D norm = vec.normalizeOrDefault(null);
> if (norm == null) {
> throw new Exception("Invalid triangle at index " + i + ": cannot compute
> normal.");
> }
> {code}
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
