WorldWind Sphere Line Intersection Bug?

Question

I'm seeing what appears to be contradictory behavior out of WorldWind's Sphere-Line intersection logic. I create a Sphere and Line and they intersect but then the intersection returns null (scan code for comment: // *** This is where it gets whacky).

Here is what's going on visually (the line is gray it's there but hard to see):

public class WWTest extends ApplicationTemplate {

    public static class VisualizationFrame extends ApplicationTemplate.AppFrame {

        public VisualizationFrame() {
            super(new Dimension(1200, 1024));
            final Globe globe = getWwd().getModel().getGlobe();

            //Create a sphere at 0,0 on the surface of the Earth wtih a 60 NMi radius
            final Vec4 sphereCenter = globe.computePointFromLocation(LatLon.ZERO);
            final Sphere sphere = new Sphere(sphereCenter, 111120);
            // Draw the sphere
            final RenderableLayer sphereLayer = new RenderableLayer();
            sphereLayer.addRenderable(sphere);

            final RenderableLayer pathLayer = new RenderableLayer();
            // Create a line at 10k feet (3048 meters) that starts outside the sphere at (2,-2) and proceeds into the sphere at (0.5, 0.5)
            final Position lineStart = Position.fromDegrees(2, -2, 3048);
            final Position lineEnds = Position.fromDegrees(0.5, 0.5, 3048);
            final Path asPath = new Path(lineStart, lineEnds);
            pathLayer.addRenderable(asPath);

            // Now that we've visualized the line, let's do some intersection math
            final Vec4 lineStartsAsVec = globe.computePointFromPosition(lineStart);
            final Vec4 lineEndsAsVec = globe.computePointFromPosition(lineEnds);
            final Line asLine = Line.fromSegment(lineStartsAsVec, lineEndsAsVec);

            // *** This is where it gets whacky - true, but no intersection?
            final boolean doesIntersect = sphere.intersects(asLine);
            final Intersection[] intersection = sphere.intersect(asLine);
            //outputs: Intersection found: null
            System.out.println(doesIntersect ? "Intersection found: " + Arrays.toString(intersection) : "No intersection, Why Not!?!?"); 

            insertBeforeCompass(getWwd(), sphereLayer);
            insertBeforeCompass(getWwd(), pathLayer);
            getWwd().getView().setEyePosition(Position.fromDegrees(0, 0, 500_000));
            getLayerPanel().update(getWwd());
        }
    }

    public static void main(String[] args) {
        ApplicationTemplate.start("World Wind Sphere-Line Intersection", VisualizationFrame.class);

    }
}

And here are the dependencies I declared to get WorldWind into my maven project (I also did try version '2.0.0-986', but that didn't seem to help):

<dependency>
    <groupId>gov.nasa</groupId>
    <artifactId>worldwind</artifactId>
    <version>2.0.0</version>
</dependency>
<dependency>
    <groupId>gov.nasa</groupId>
    <artifactId>worldwindx</artifactId>
    <version>2.0.0</version>
</dependency>
<dependency>
    <groupId>org.jogamp.gluegen</groupId>
    <artifactId>gluegen-rt-main</artifactId>
    <version>2.2.4</version>
</dependency>
<dependency>
    <groupId>org.jogamp.jogl</groupId>
    <artifactId>jogl-all-main</artifactId>
    <version>2.2.4</version>
</dependency>

To be completely thorough, here are the code imports:

import gov.nasa.worldwind.geom.Intersection;
import gov.nasa.worldwind.geom.LatLon;
import gov.nasa.worldwind.geom.Line;
import gov.nasa.worldwind.geom.Position;
import gov.nasa.worldwind.geom.Sphere;
import gov.nasa.worldwind.geom.Vec4;
import gov.nasa.worldwind.globes.Globe;
import gov.nasa.worldwind.layers.RenderableLayer;
import gov.nasa.worldwind.render.Path;
import gov.nasa.worldwindx.examples.ApplicationTemplate;
import static gov.nasa.worldwindx.examples.ApplicationTemplate.insertBeforeCompass;
import java.awt.Dimension;
import java.util.Arrays;

Lyra

The primary technical POC of worldwind has been contacted and said this bug will be put in their queue to be fixed. Thanks for your help Chris and Kyle :) – Lyra

Answer 1

If you look at the implementation of Sphere#intersect() it is expecting the line in coordinates centered at the sphere's origin (not the Earth's) which is almost certainly a bug. You should be able to do:

final Vec4 pa = lineStartsAsVec.subtract3(sphereCenter);
final Vec4 pb = lineEndsAsVec.subtract3(sphereCenter);
final Line asLine2 = Line.fromSegment(pa, pb);
final Intersection[] intersection = sphere.intersect(asLine2);

Keep in mind that the intersections returned are still in Cartesian coordinates centered at the sphere's origin, so to transform them back to World Wind Cartesian you need to do:

final Vec4 intersectionPos = intersection[0].getIntersectionPoint().add3(sphereCenter);

The implementation also considers the line to be infinitely long so it will return two points, not one.

It would be pretty straight forward to implement your own version of intersect() that works in normal coordinates and takes into account the length of the line, see here.

Willin

@Chris_K if you're available/interested in helping write some challenging efficient WGS-84 computational geometry routines please shoot me a message, I should be easy to find on FB, Twitter, LinkedIn, etc. – Lyra

Answer 2

If you look at the Worldwind source code, specifically the intersects() and intersect() methods of the Sphere class and step through them with your code as input, you see the following:

The method:

public boolean intersects(Line line)

returns true because the distance from the sphere centre to the line is less than the radius of the sphere, as expected.

For the method:

public final Intersection[] intersect(Line line)

it turns out that the discriminant of the quadratic is less than zero (i.e. there are no real roots to the quadratic equation - two distinct complex roots).

The WorldWind API reference is here.

The specific methods involved are:

    /**
 * Tests for intersection with a <code>Line</code>.
 *
 * @param line the <code>Line</code> with which to test for intersection
 *
 * @return true if <code>line</code> intersects or makes a tangent with the surface of this <code>Sphere</code>
 *
 * @throws IllegalArgumentException if <code>line</code> is null
 */
public boolean intersects(Line line)
{
    if (line == null)
    {
        String msg = Logging.getMessage("nullValue.LineIsNull");
        Logging.logger().severe(msg);
        throw new IllegalArgumentException(msg);
    }
    return line.distanceTo(this.center) <= this.radius;
}

and:

    /**
 * Obtains the intersections of this sphere with a line. The returned array may be either null or of zero length if
 * no intersections are discovered. It does not contain null elements and will have a size of 2 at most. Tangential
 * intersections are marked as such. <code>line</code> is considered to have infinite length in both directions.
 *
 * @param line the <code>Line</code> with which to intersect this <code>Sphere</code>
 *
 * @return an array containing all the intersections of this <code>Sphere</code> and <code>line</code>
 *
 * @throws IllegalArgumentException if <code>line</code> is null
 */
public final Intersection[] intersect(Line line)
{
    if (line == null)
    {
        String message = Logging.getMessage("nullValue.LineIsNull");
        Logging.logger().severe(message);
        throw new IllegalArgumentException(message);
    }

    double a = line.getDirection().getLengthSquared3();
    double b = 2 * line.selfDot();
    double c = line.getOrigin().getLengthSquared3() - this.radius * this.radius;

    double discriminant = Sphere.discriminant(a, b, c);
    if (discriminant < 0)
        return null;

    double discriminantRoot = Math.sqrt(discriminant);
    if (discriminant == 0)
    {
        Vec4 p = line.getPointAt((-b - discriminantRoot) / (2 * a));
        return new Intersection[] {new Intersection(p, true)};
    }
    else // (discriminant > 0)
    {
        Vec4 near = line.getPointAt((-b - discriminantRoot) / (2 * a));
        Vec4 far = line.getPointAt((-b + discriminantRoot) / (2 * a));
        return new Intersection[] {new Intersection(near, false), new Intersection(far, false)};
    }
}

which uses:

    /**
 * Calculates a discriminant. A discriminant is useful to determine the number of roots to a quadratic equation. If
 * the discriminant is less than zero, there are no roots. If it equals zero, there is one root. If it is greater
 * than zero, there are two roots.
 *
 * @param a the coefficient of the second order pronumeral
 * @param b the coefficient of the first order pronumeral
 * @param c the constant parameter in the quadratic equation
 *
 * @return the discriminant "b squared minus 4ac"
 */
private static double discriminant(double a, double b, double c)
{
    return b * b - 4 * a * c;
}

in this case your code fails the:

if (discriminant < 0)

test.

It looks like I've been a bit slow in answering this question, and in the meantime it has been pointed out by Chris K that this is due to the intersect() method expecting the line coordinates to be centered at the origin of the sphere and not of Earth.

As Chris K said, this seems to be a bug and should probably be logged with the maintainers of this source code.

Tiffanytiffi