surfaceshapegeometry.java

world wind java sdk 源码

                    splitAtDateline(t, terrain);
                else
                    intersectTerrain(t, terrain);
            }
        }
    }

    //
    // Computes the intersect of a Triangle with the given terrain grid. Output is a collection of
    // 3,4,5,6 sided polygons.
    //
    // This algorithm is modelled after a standard polygon scan-line conversion algorithm (see Foley and Van Dam),
    // except that rather than a boolean decision about whether a "pixel" is inside/outside, we need to compute
    // the exact intersect wherever terrain gridcells intersect the Triangle edges.
    //
    private void intersectTerrain(Triangle t, RectangularTessellator.RectGeometry terrain) {

        ActiveEdge e0 = new ActiveEdge(t.vertices[0], t.vertices[1]);
        ActiveEdge e1 = new ActiveEdge(t.vertices[1], t.vertices[2]);
        ActiveEdge e2 = new ActiveEdge(t.vertices[0], t.vertices[2]);

        ArrayList<ActiveEdge> edges = new ArrayList<ActiveEdge>(3);

        // Insert the edges into the list sorted by their p0-latitude. Don't insert an edge whose endpoints
        // have equal latitude; i.e,. one that runs horizontally.

        if (Math.abs(e0.deltaY) > EPSILON) {
            edges.add(e0);
        }
        if (Math.abs(e1.deltaY) > EPSILON) {
            if (e1.p0Lat < e0.p0Lat) {
                edges.add(0, e1);
            } else {
                edges.add(e1);
            }
        }
        if (Math.abs(e2.deltaY) > EPSILON) {
            if (e2.p0Lat < edges.get(0).p0Lat) {
                edges.add(0, e2);
            } else if (edges.size() == 2 && e2.p0Lat < edges.get(1).p0Lat) {
                edges.add(1, e2);
            } else {
                edges.add(e2);
            }
        }
        if (edges.size() < 2) { // degenerate triangle!
            return;
        }

        // Get the first two edges;  skip any edge that is completely below our terrain grid...
        Iterator<ActiveEdge> iter = edges.iterator();
        e0 = iter.next();
        e1 = iter.next();
        if (e0.p1Lat <= terrain.getMinLatitude()) {
            if (iter.hasNext()) {
                e0 = e1;
                e1 = iter.next();
            } else {
                return;
            }
        }
        if (e1.p1Lat <= terrain.getMinLatitude()) {
            if (iter.hasNext()) {
                e1 = iter.next();
            } else {
                return;
            }
        }

        double leftLon = e0.p0Lon;
        double rightLon = e1.p0Lon;
        double lowerLat = e0.p0Lat;
        int currRow = terrain.getRowAtLat(lowerLat);
        if (currRow >= terrain.getNumRows()) { // all edges above our terrain...
            return;
        }

        if (currRow < 0) {
            // one or both edges extend below our terrain grid
            currRow = 0;
            lowerLat = terrain.getLatAtRow(currRow);
            leftLon = e0.getLonAtLat(lowerLat);
            rightLon = e1.getLonAtLat(lowerLat);
        }

        // make sure left is left, right is right...
        if (leftLon > rightLon) {
            double tmp = leftLon;
            leftLon = rightLon;
            rightLon = tmp;
        }

        Vertex lowerLeft = new Vertex(leftLon, lowerLat);
        Vertex lowerRight = new Vertex(rightLon, lowerLat);

        // Begin the "scan converting" against the rows of the terrain grid...
        while (true) {
            double upperLat = terrain.getLatAtRow(currRow + 1);
            if (upperLat <= e0.p1Lat && upperLat <= e1.p1Lat) {
                currRow++;
            } else {
                if (upperLat > e0.p1Lat) {
                    upperLat = e0.p1Lat;
                }
                if (upperLat > e1.p1Lat) {
                    upperLat = e1.p1Lat;
                }
            }

            Vertex upperLeft;
            upperLeft = new Vertex(e0.getLonAtLat(upperLat), upperLat);

            Vertex upperRight;
            upperRight = new Vertex(e1.getLonAtLat(upperLat), upperLat);

            if (upperLeft.x > upperRight.x) {
                Vertex tmp = upperLeft;
                upperLeft = upperRight;
                upperRight = tmp;
            }

            // At this point, we have a quad that has two parallel sides coinciding with rows of the terrain grid,
            // the other two opposite sides are from the triangle. This quad possibly extends out beyond the
            // grid. Clip it against each grid cell that it touches.

            double minLon = (lowerLeft.x < upperLeft.x) ? lowerLeft.x : upperLeft.x;
            double maxLon = (lowerRight.x > upperRight.x) ? lowerRight.x : upperRight.x;
            int begCol = terrain.getColAtLon(minLon);
            int endCol = terrain.getColAtLon(maxLon);
            if (!(begCol >= terrain.getNumCols() || endCol < 0)) {

                Polygon quadStrip = new Polygon();
                quadStrip.addVertex(lowerLeft.x, lowerLeft.y);
                quadStrip.addVertex(upperLeft.x, upperLeft.y);
                quadStrip.addVertex(upperRight.x, upperRight.y);
                quadStrip.addVertex(lowerRight.x, lowerRight.y);

                if (begCol < 0) {
                    // clip at left edge of our terrain grid...
                    quadStrip.splitAtXPlane(terrain.getMinLongitude());
                    begCol = 0;
                }
                if (endCol >= terrain.getNumCols()) {
                    // clip at right edge of a our terrain grid...
                    quadStrip = quadStrip.splitAtXPlane(terrain.getMaxLongitude());
                    endCol = terrain.getNumCols() - 1;
                }

                // now clip against any interior grid cells...
                for (int i = begCol + 1; i <= endCol; i++) {
                    // clip against the ith grid boundary...
                    double lon = terrain.getLonAtCol(i);

                    Polygon left = quadStrip.splitAtXPlane(lon);
                    if (left != null) {
                        left.convertToXYZ(terrain);
                        this.polygons.add(left);
                    }
                }

                quadStrip.convertToXYZ(terrain);
                this.polygons.add(quadStrip);


            }

            // reached the "upper" vertex of an edge?
            if (upperLat >= e0.p1Lat) {
                if (iter.hasNext()) {
                    e0 = iter.next();
                } else {
                    break;
                }
            }
            if (upperLat >= e1.p1Lat) {
                if (iter.hasNext()) {
                    e1 = iter.next();
                } else {
                    break;
                }
            }

            // off the top of our terrain grid?
            if (currRow >= terrain.getNumRows()) {
                break;
            }
            lowerLeft = upperLeft;
            lowerRight = upperRight;
        }

    }

    private void splitAtDateline(Triangle t, RectangularTessellator.RectGeometry terrain) {
        Polygon right = new Polygon();

        for (int i=0; i<3; i++) {
            double lat = t.vertices[i].getLatitude().degrees;
            double lon = t.vertices[i].getLongitude().degrees;
            if (lon > 0.) lon -= Angle.POS360.degrees;
            right.addVertex(lon, lat);
        }

        Polygon left = right.splitAtXPlane(Angle.NEG180.degrees);

        // Make triangles out of our two polygons and throw them at the terrain intersector.
        // Since the polygons are convex, we'll effectively generate a triangle fan.
        Triangle tri = new Triangle();
        for (int i=2; i<left.numVerts; i++) {
            // We need to "normalize" the longitudes for the "left" polygon...
            tri.vertices[0] = new LatLon(Angle.fromDegrees(left.xy[0][1]), Angle.fromDegrees(left.xy[0][0]+Angle.POS360.degrees));
            tri.vertices[1] = new LatLon(Angle.fromDegrees(left.xy[i-1][1]), Angle.fromDegrees(left.xy[i-1][0]+Angle.POS360.degrees));
            tri.vertices[2] = new LatLon(Angle.fromDegrees(left.xy[i][1]), Angle.fromDegrees(left.xy[i][0]+Angle.POS360.degrees));
            intersectTerrain(tri, terrain);
        }

        for (int i=2; i<right.numVerts; i++) {
            tri.vertices[0] = new LatLon(Angle.fromDegrees(right.xy[0][1]), Angle.fromDegrees(right.xy[0][0]));
            tri.vertices[1] = new LatLon(Angle.fromDegrees(right.xy[i-1][1]), Angle.fromDegrees(right.xy[i-1][0]));
            tri.vertices[2] = new LatLon(Angle.fromDegrees(right.xy[i][1]), Angle.fromDegrees(right.xy[i][0])); 
            intersectTerrain(tri, terrain);
        }

    }

    //
    // This Polygon class is used to encode pieces of the intersect of our SurfaceShapeGeometry with a terrain grid.
    //
    private class Polygon {
        double[][] xy;
        int numVerts;

        public Polygon() {
            xy = new double[6][2];
            numVerts = 0;
        }

        public void addVertex(double x, double y) throws IllegalStateException {
            if (numVerts >= xy.length) {
                // TODO:  I8N this
                throw new IllegalStateException("SOMETHING'S DREADFULLY WRONG!!");
            }
            xy[numVerts][0] = x;
            xy[numVerts][1] = y;
            ++numVerts;
        }

        //
        // Splits this Polygon into two at the given "splitPlane". The splitPlane is presumed to be vertical,
        // i.e., a line of constant longitude.
        //
        // Returns the Polygon to the left of the splitPlane, and modifies this Polygon to contain the
        // righthand result of the split.
        //
        public Polygon splitAtXPlane(double splitPlane) {
            double[][] leftPoly = new double[6][2];
            double[][] rightPoly = new double[6][2];
            int numLeft = 0;
            int numRight = 0;

            for (int i = 0; i < numVerts; i++) {
                if (xy[i][0] < splitPlane) {
                    leftPoly[numLeft++] = xy[i];
                } else if (xy[i][0] > splitPlane) {
                    rightPoly[numRight++] = xy[i];
                }

                int j = (i + 1) % numVerts;
                double t = intersectAtX(splitPlane, xy[i][0], xy[j][0]);

                if (t < 0. || t > 1.) {
                    continue;
                }
                double[] newXY = new double[2];
                newXY[0] = splitPlane;
                newXY[1] = valAtParam(t, xy[i][1], xy[j][1]);
                if (newXY[1] == Double.MAX_VALUE) {
                    newXY[1] = xy[i][1];
                }  // parallel...

                // NOTE THAT BOTH POLYGONS SHARE A REFERENCE TO THE SAME ARRAY!
                leftPoly[numLeft++] = newXY;
                rightPoly[numRight++] = newXY;
            }
            xy = rightPoly;
            numVerts = numRight;

            Polygon p = null;
            if (numLeft > 0) {
                p = new Polygon();
                p.xy = leftPoly;
                p.numVerts = numLeft;
            }

            return p;
        }

        //
        // Computes the value along a parameterized line.
        //
        private double valAtParam(double t, double p0, double p1) {
            double delta = p1 - p0;
            if (Math.abs(delta) < 1.e-10) {
                return Double.MAX_VALUE;
            }
            return p0 + t * delta;
        }

        //
        // Returns the parameter along a parameterized line where the given X-intersect occurs.
        //
        private double intersectAtX(double x, double x2, double x1) {
            double delta = x2 - x1;
            if (Math.abs(delta) < 1.e-10) {
                return Double.MAX_VALUE;
            }
            return (x2 - x) / delta;
        }

        //
        // Replaces the lat-lon coordinates with XYZ values interpolated from the terrain grid.
        //
        public void convertToXYZ(RectangularTessellator.RectGeometry terrain) {
            Vec4 refPoint = getReferencePoint();
            for (int i=0; i<this.numVerts; i++) {
                // Note in the following call, we have a double[2] going in, replaced by a double[3] coming out...
                xy[i] = terrain.getPointAt(xy[i][Y], xy[i][X]);
                xy[i][X] -= refPoint.x;
                xy[i][Y] -= refPoint.y;
                xy[i][Z] -= refPoint.z;
            }
        }
    }

    //
    // TODO:  Is there still utility in using this class in leu of something else?   --RLB
    //
    private class Vertex {

        public Vertex(double x, double y) {
            this.x = x;
            this.y = y;
        }

        double x;
        double y;
    }

    //
    // A bundle of info needed to track "active edges" during our "scan conversion" of triangles against the
    // terrain raster (grid).
    //
    private class ActiveEdge {

        double p0Lon, p0Lat;
        double p1Lon, p1Lat;
        double deltaX;
        double deltaY;
        int begRow, endRow;
        int begCol, endCol;

        public ActiveEdge(LatLon p0, LatLon p1) {
            // we want to guarantee p0 <= p1
            if (p0.getLatitude().degrees > p1.getLatitude().degrees) {
                this.p0Lon = p1.getLongitude().degrees;
                this.p0Lat = p1.getLatitude().degrees;
                this.p1Lon = p0.getLongitude().degrees;
                this.p1Lat = p0.getLatitude().degrees;
            } else {
                this.p0Lon = p0.getLongitude().degrees;
                this.p0Lat = p0.getLatitude().degrees;