gov/nasa/worldwind/globes/EllipsoidRectangularTessellator.java

   1 /*
   2 Copyright (C) 2001, 2006 United States Government
   3 as represented by the Administrator of the
   4 National Aeronautics and Space Administration.
   5 All Rights Reserved.
   6 */
   7 package gov.nasa.worldwind.globes;
   8
   9 import com.sun.opengl.util.*;
  10 import gov.nasa.worldwind.*;
  11 import gov.nasa.worldwind.geom.*;
  12
  13 import javax.media.opengl.*;
  14 import java.nio.*;
  15 import java.util.*;
  16
  17 /**
  18  * @author tag
  19  * @version $Id: EllipsoidRectangularTessellator.java 1787 2007-05-08 17:11:30Z dcollins $
  20  */
  21 public class EllipsoidRectangularTessellator extends WWObjectImpl implements Tessellator
  22 {
  23     // TODO: Make all this configurable
  24     private static final int DEFAULT_DENSITY = 24;
  25     private static final double DEFAULT_LOG10_RESOLUTION_TARGET = 1.3;
  26     private static final int DEFAULT_MAX_LEVEL = 12;
  27     private static final int DEFAULT_NUM_LAT_SUBDIVISIONS = 5;
  28     private static final int DEFAULT_NUM_LON_SUBDIVISIONS = 10;
  29
  30     private static class RenderInfo
  31     {
  32         private final int density;
  33         private final Point referenceCenter;
  34         private final DoubleBuffer vertices;
  35         private final DoubleBuffer texCoords;
  36         private final IntBuffer indices;
  37         private final int resolution;
  38
  39         private RenderInfo(int density, DoubleBuffer vertices, DoubleBuffer texCoords, Point refCenter, int resolution)
  40         {
  41             this.density = density;
  42             this.vertices = vertices;
  43             this.texCoords = texCoords;
  44             this.referenceCenter = refCenter;
  45             this.indices = RectTile.getIndices(this.density);
  46             this.resolution = resolution;
  47         }
  48
  49         private long getSizeInBytes()
  50         {
  51             return 16 + (this.vertices.limit() + this.texCoords.limit()) * Double.SIZE;
  52         }
  53     }
  54
  55     private static class CacheKey
  56     {
  57         private final Sector sector;
  58         private int resolution;
  59         private final double verticalExaggeration;
  60         private int density;
  61
  62         private CacheKey(RectTile tile, int resolution, double verticalExaggeration, int density)
  63         {
  64             this.sector = tile.sector;
  65             this.resolution = resolution;
  66             this.verticalExaggeration = verticalExaggeration;
  67             this.density = density;
  68         }
  69
  70         @Override
  71         public String toString()
  72         {
  73             return "density " + this.density + " ve " + this.verticalExaggeration + " resolution " + this.resolution
  74                 + " sector " + this.sector;
  75         }
  76
  77         public boolean equals(Object o)
  78         {
  79             if (this == o)
  80                 return true;
  81             if (o == null || getClass() != o.getClass())
  82                 return false;
  83
  84             CacheKey cacheKey = (CacheKey) o;
  85
  86             if (density != cacheKey.density)
  87                 return false;
  88             if (resolution != cacheKey.resolution)
  89                 return false;
  90             if (Double.compare(cacheKey.verticalExaggeration, verticalExaggeration) != 0)
  91                 return false;
  92             //noinspection RedundantIfStatement
  93             if (sector != null ? !sector.equals(cacheKey.sector) : cacheKey.sector != null)
  94                 return false;
  95
  96             return true;
  97         }
  98
  99         public int hashCode()
 100         {
 101             int result;
 102             long temp;
 103             result = (sector != null ? sector.hashCode() : 0);
 104             result = 31 * result + resolution;
 105             temp = verticalExaggeration != +0.0d ? Double.doubleToLongBits(verticalExaggeration) : 0L;
 106             result = 31 * result + (int) (temp ^ (temp >>> 32));
 107             result = 31 * result + density;
 108             return result;
 109         }
 110     }
 111
 112     private static class RectTile implements SectorGeometry
 113     {
 114         private static final HashMap<Integer, DoubleBuffer> parameterizations = new HashMap<Integer, DoubleBuffer>();
 115         private static final HashMap<Integer, IntBuffer> indexLists = new HashMap<Integer, IntBuffer>();
 116
 117         private final Globe globe;
 118         private final int level;
 119         private final Sector sector;
 120         private final Cylinder extent; // extent of triangle in object coordinates
 121         private final int density;
 122         private final double log10CellSize;
 123         private long byteSize;
 124         private RenderInfo ri;
 125
 126         private PickSupport pickSupport = new PickSupport();
 127         private int minColorCode = 0;
 128         private int maxColorCode = 0;
 129
 130         public RectTile(Globe globe, int level, int density, Sector sector)
 131         {
 132             this.globe = globe;
 133             this.level = level;
 134             this.density = density;
 135             this.sector = sector;
 136             this.extent = Sector.computeBoundingCylinder(globe, 1d, this.getSector());
 137             double cellSize = (sector.getDeltaLatRadians() * globe.getRadius()) / density;
 138             this.log10CellSize = Math.log10(cellSize);
 139         }
 140
 141         public Sector getSector()
 142         {
 143             return this.sector;
 144         }
 145
 146         public Extent getExtent()
 147         {
 148             return this.extent;
 149         }
 150
 151         public long getSizeInBytes()
 152         {
 153             return this.byteSize;
 154         }
 155
 156         private RectTile[] split()
 157         {
 158             Sector[] sectors = this.sector.subdivide();
 159
 160             RectTile[] subTiles = new RectTile[4];
 161             subTiles[0] = new RectTile(this.globe, this.level + 1, this.density, sectors[0]);
 162             subTiles[1] = new RectTile(this.globe, this.level + 1, this.density, sectors[1]);
 163             subTiles[2] = new RectTile(this.globe, this.level + 1, this.density, sectors[2]);
 164             subTiles[3] = new RectTile(this.globe, this.level + 1, this.density, sectors[3]);
 165
 166             return subTiles;
 167         }
 168
 169         private void makeVerts(DrawContext dc)
 170         {
 171             int resolution = dc.getGlobe().getElevationModel().getTargetResolution(dc, this.sector, this.density);
 172
 173             if (this.ri != null && this.ri.resolution >= resolution)
 174                 return;
 175
 176             CacheKey cacheKey = new CacheKey(this, resolution, dc.getVerticalExaggeration(), this.density);
 177             this.ri = (RenderInfo) WorldWind.memoryCache().getObject(cacheKey);
 178             if (this.ri != null)
 179                 return;
 180
 181             this.ri = this.buildVerts(dc, this.density, resolution, true);
 182             if (this.ri != null && this.ri.resolution >= 0)//&& this.ri.elevationsFullyResolved)
 183                 WorldWind.memoryCache().add(this.ri.resolution, this.ri, this.byteSize = this.ri.getSizeInBytes());
 184         }
 185
 186         private RenderInfo buildVerts(DrawContext dc, int density, int resolution, boolean makeSkirts)
 187         {
 188             int numVertices = (density + 3) * (density + 3);
 189             java.nio.DoubleBuffer verts = BufferUtil.newDoubleBuffer(numVertices * 3);
 190
 191             Globe globe = dc.getGlobe();
 192             ElevationModel.Elevations elevations = globe.getElevationModel().getElevations(this.sector, resolution);
 193
 194             double latMin = this.sector.getMinLatitude().radians;
 195             double latMax = this.sector.getMaxLatitude().radians;
 196             double dLat = (latMax - latMin) / density;
 197
 198             double lonMin = this.sector.getMinLongitude().radians;
 199             double lonMax = this.sector.getMaxLongitude().radians;
 200             double dLon = (lonMax - lonMin) / density;
 201
 202             int iv = 0;
 203             double lat = latMin;
 204             double verticalExaggeration = dc.getVerticalExaggeration();
 205             double exaggeratedMinElevation = makeSkirts ? globe.getMinElevation() * verticalExaggeration : 0;
 206             double equatorialRadius = globe.getEquatorialRadius();
 207             double eccentricity = globe.getEccentricitySquared();
 208
 209             LatLon centroid = sector.getCentroid();
 210             Point refCenter = globe.computePointFromPosition(centroid.getLatitude(), centroid.getLongitude(), 0d);
 211
 212             for (int j = 0; j <= density + 2; j++)
 213             {
 214                 double cosLat = Math.cos(lat);
 215                 double sinLat = Math.sin(lat);
 216                 double rpm = equatorialRadius / Math.sqrt(1.0 - eccentricity * sinLat * sinLat);
 217                 double lon = lonMin;
 218                 for (int i = 0; i <= density + 2; i++)
 219                 {
 220                     double elevation = verticalExaggeration * elevations.getElevation(lat, lon);
 221                     if (j == 0 || j >= density + 2 || i == 0 || i >= density + 2)
 222                     {   // use abs to account for negative elevation.
 223                         elevation -= exaggeratedMinElevation >= 0 ? exaggeratedMinElevation : -exaggeratedMinElevation;
 224                     }
 225
 226                     double x = ((rpm + elevation) * cosLat * Math.sin(lon)) - refCenter.getX();
 227                     double y = ((rpm * (1.0 - eccentricity) + elevation) * sinLat) - refCenter.getY();
 228                     double z = ((rpm + elevation) * cosLat * Math.cos(lon)) - refCenter.getZ();
 229
 230                     verts.put(iv++, x).put(iv++, y).put(iv++, z);
 231
 232                     if (i > density)
 233                         lon = lonMax;
 234                     else if (i != 0)
 235                         lon += dLon;
 236                 }
 237                 if (j > density)
 238                     lat = latMax;
 239                 else if (j != 0)
 240                     lat += dLat;
 241             }
 242
 243             return new RenderInfo(density, verts, getParameterization(density), refCenter, elevations.getResolution());
 244         }
 245
 246         public void renderMultiTexture(DrawContext dc, int numTextureUnits)
 247         {
 248             if (dc == null)
 249             {
 250                 String msg = WorldWind.retrieveErrMsg("nullValue.DrawContextIsNull");
 251                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 252                 throw new IllegalArgumentException(msg);
 253             }
 254
 255             if (numTextureUnits < 1)
 256             {
 257                 String msg = WorldWind.retrieveErrMsg("generic.NumTextureUnitsLessThanOne");
 258                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 259                 throw new IllegalArgumentException(msg);
 260             }
 261
 262             this.render(dc, numTextureUnits);
 263         }
 264
 265         public void render(DrawContext dc)
 266         {
 267             if (dc == null)
 268             {
 269                 String msg = WorldWind.retrieveErrMsg("nullValue.DrawContextIsNull");
 270                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 271                 throw new IllegalArgumentException(msg);
 272             }
 273
 274             this.render(dc, 1);
 275         }
 276
 277         private long render(DrawContext dc, int numTextureUnits)
 278         {
 279             if (this.ri == null)
 280             {
 281                 String msg = WorldWind.retrieveErrMsg("nullValue.RenderInfoIsNull");
 282                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 283                 throw new IllegalStateException(msg);
 284             }
 285
 286             dc.getView().pushReferenceCenter(dc, ri.referenceCenter);
 287
 288             GL gl = dc.getGL();
 289             gl.glPushClientAttrib(GL.GL_CLIENT_VERTEX_ARRAY_BIT);
 290             gl.glEnableClientState(GL.GL_VERTEX_ARRAY);
 291             gl.glVertexPointer(3, GL.GL_DOUBLE, 0, this.ri.vertices.rewind());
 292
 293             for (int i = 0; i < numTextureUnits; i++)
 294             {
 295                 gl.glClientActiveTexture(GL.GL_TEXTURE0 + i);
 296                 gl.glEnableClientState(GL.GL_TEXTURE_COORD_ARRAY);
 297                 gl.glTexCoordPointer(2, GL.GL_DOUBLE, 0, ri.texCoords.rewind());
 298             }
 299
 300             gl.glDrawElements(javax.media.opengl.GL.GL_TRIANGLE_STRIP, this.ri.indices.limit(),
 301                 javax.media.opengl.GL.GL_UNSIGNED_INT, this.ri.indices.rewind());
 302
 303             gl.glPopClientAttrib();
 304
 305             dc.getView().popReferenceCenter(dc);
 306
 307             return this.ri.indices.limit() - 2; // return number of triangles rendered
 308         }
 309
 310         public void renderWireframe(DrawContext dc, boolean showTriangles, boolean showTileBoundary)
 311         {
 312             if (dc == null)
 313             {
 314                 String msg = WorldWind.retrieveErrMsg("nullValue.DrawContextIsNull");
 315                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 316                 throw new IllegalArgumentException(msg);
 317             }
 318
 319             if (this.ri == null)
 320             {
 321                 String msg = WorldWind.retrieveErrMsg("nullValue.RenderInfoIsNull");
 322                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 323                 throw new IllegalStateException(msg);
 324             }
 325
 326             java.nio.IntBuffer indices = getIndices(this.ri.density);
 327             indices.rewind();
 328
 329             dc.getView().pushReferenceCenter(dc, this.ri.referenceCenter);
 330
 331             javax.media.opengl.GL gl = dc.getGL();
 332             gl.glPushAttrib(
 333                 GL.GL_DEPTH_BUFFER_BIT | GL.GL_POLYGON_BIT | GL.GL_TEXTURE_BIT | GL.GL_ENABLE_BIT | GL.GL_CURRENT_BIT);
 334             gl.glEnable(GL.GL_BLEND);
 335             gl.glBlendFunc(GL.GL_SRC_ALPHA, GL.GL_ONE);
 336             gl.glDisable(javax.media.opengl.GL.GL_DEPTH_TEST);
 337             gl.glEnable(javax.media.opengl.GL.GL_CULL_FACE);
 338             gl.glCullFace(javax.media.opengl.GL.GL_BACK);
 339             gl.glDisable(javax.media.opengl.GL.GL_TEXTURE_2D);
 340             gl.glColor4d(1d, 1d, 1d, 0.2);
 341             gl.glPolygonMode(javax.media.opengl.GL.GL_FRONT, javax.media.opengl.GL.GL_LINE);
 342
 343             if (showTriangles)
 344             {
 345                 gl.glPushClientAttrib(GL.GL_CLIENT_VERTEX_ARRAY_BIT);
 346                 gl.glEnableClientState(GL.GL_VERTEX_ARRAY);
 347
 348                 gl.glVertexPointer(3, GL.GL_DOUBLE, 0, this.ri.vertices);
 349                 gl.glDrawElements(javax.media.opengl.GL.GL_TRIANGLE_STRIP, indices.limit(),
 350                     javax.media.opengl.GL.GL_UNSIGNED_INT, indices);
 351
 352                 gl.glPopClientAttrib();
 353             }
 354
 355             dc.getView().popReferenceCenter(dc);
 356
 357             if (showTileBoundary)
 358                 this.renderPatchBoundary(dc, gl);
 359
 360             gl.glPopAttrib();
 361         }
 362
 363         private void renderPatchBoundary(DrawContext dc, GL gl)
 364         {
 365             // TODO: Currently only works if called from renderWireframe because no state is set here.
 366             // TODO: Draw the boundary using the vertices along the boundary rather than just at the corners.
 367             gl.glColor4d(1d, 0, 0, 1d);
 368             Point[] corners = this.sector.computeCornerPoints(dc.getGlobe());
 369
 370             gl.glBegin(javax.media.opengl.GL.GL_QUADS);
 371             gl.glVertex3d(corners[0].x(), corners[0].y(), corners[0].z());
 372             gl.glVertex3d(corners[1].x(), corners[1].y(), corners[1].z());
 373             gl.glVertex3d(corners[2].x(), corners[2].y(), corners[2].z());
 374             gl.glVertex3d(corners[3].x(), corners[3].y(), corners[3].z());
 375             gl.glEnd();
 376         }
 377
 378         public void renderBoundingVolume(DrawContext dc)
 379         {
 380             ((Cylinder) this.getExtent()).render(dc);
 381         }
 382
 383         public void pick(DrawContext dc, java.awt.Point pickPoint)
 384         {
 385             if (this.ri == null)
 386                 return;
 387
 388             renderTrianglesWithUniqueColors(dc, ri);
 389
 390             int colorCode = pickSupport.getTopColor(dc, pickPoint);
 391             if (colorCode < minColorCode || colorCode > maxColorCode)
 392                 return;
 393
 394             double EPSILON = (double) 0.00001f;
 395
 396             int triangleIndex = colorCode - minColorCode - 1;
 397
 398             if ((null != ri.indices) && (triangleIndex < ri.indices.capacity() - 2))
 399             {
 400                 double centerX = ri.referenceCenter.getX();
 401                 double centerY = ri.referenceCenter.getY();
 402                 double centerZ = ri.referenceCenter.getZ();
 403
 404                 int vIndex = 3 * ri.indices.get(triangleIndex);
 405                 Point v0 = new Point((ri.vertices.get(vIndex++) + centerX),
 406                     (ri.vertices.get(vIndex++) + centerY),
 407                     (ri.vertices.get(vIndex) + centerZ));
 408
 409                 vIndex = 3 * ri.indices.get(triangleIndex + 1);
 410                 Point v1 = new Point((ri.vertices.get(vIndex++) + centerX),
 411                     (ri.vertices.get(vIndex++) + centerY),
 412                     (ri.vertices.get(vIndex) + centerZ));
 413
 414                 vIndex = 3 * ri.indices.get(triangleIndex + 2);
 415                 Point v2 = new Point((ri.vertices.get(vIndex++) + centerX),
 416                     (ri.vertices.get(vIndex++) + centerY),
 417                     (ri.vertices.get(vIndex) + centerZ));
 418
 419                 // get triangle edge vectors and plane normal
 420                 Point e1 = v1.subtract(v0);
 421                 Point e2 = v2.subtract(v0);
 422                 Point N = e1.cross(e2);  // if N is 0, the triangle is degenerate, we are not dealing with it
 423
 424                 Line ray = dc.getView().computeRayFromScreenPoint(pickPoint.getX(), pickPoint.getY());
 425
 426                 Point w0 = ray.getOrigin().subtract(v0);
 427                 double a = -N.dot(w0);
 428                 double b = N.dot(ray.getDirection());
 429                 if (java.lang.Math.abs(b) < EPSILON) // ray is parallel to triangle plane
 430                     return;                    // if a == 0 , ray lies in triangle plane
 431                 double r = a / b;
 432
 433                 Point intersect = ray.getOrigin().add(ray.getDirection().multiply(r));
 434                 Position pp = dc.getGlobe().computePositionFromPoint(intersect);
 435
 436                 // Draw the elevation from the elevation model, not the geode.
 437                 double elev = dc.getGlobe().getElevation(pp.getLatitude(), pp.getLongitude());
 438                 Position p = new Position(pp.getLatitude(), pp.getLongitude(), elev);
 439
 440                 PickedObject po = new PickedObject(colorCode, p, pp.getLatitude(), pp.getLongitude(), elev, true);
 441                 dc.addPickedObject(po);
 442             }
 443         }
 444
 445         private void renderTrianglesWithUniqueColors(DrawContext dc, RenderInfo ri)
 446         {
 447             if (dc == null)
 448             {
 449                 String message = WorldWind.retrieveErrMsg("nullValue.DrawContextIsNull");
 450                 WorldWind.logger().log(java.util.logging.Level.FINE, message);
 451                 throw new IllegalStateException(message);
 452             }
 453
 454             if (ri.vertices == null)
 455                 return;
 456
 457             ri.vertices.rewind();
 458             ri.indices.rewind();
 459
 460             javax.media.opengl.GL gl = dc.getGL();
 461
 462             if (null != ri.referenceCenter)
 463                 dc.getView().pushReferenceCenter(dc, ri.referenceCenter);
 464
 465             minColorCode = dc.getUniquePickColor().getRGB();
 466             int trianglesNum = ri.indices.capacity() - 2;
 467
 468             gl.glBegin(GL.GL_TRIANGLES);
 469             for (int i = 0; i < trianglesNum; i++)
 470             {
 471                 java.awt.Color color = dc.getUniquePickColor();
 472                 gl.glColor3ub((byte) (color.getRed() & 0xFF),
 473                     (byte) (color.getGreen() & 0xFF),
 474                     (byte) (color.getBlue() & 0xFF));
 475
 476                 int vIndex = 3 * ri.indices.get(i);
 477                 gl.glVertex3d(ri.vertices.get(vIndex), ri.vertices.get(vIndex + 1), ri.vertices.get(
 478                     vIndex + 2));
 479
 480                 vIndex = 3 * ri.indices.get(i + 1);
 481                 gl.glVertex3d(ri.vertices.get(vIndex), ri.vertices.get(vIndex + 1), ri.vertices.get(
 482                     vIndex + 2));
 483
 484                 vIndex = 3 * ri.indices.get(i + 2);
 485                 gl.glVertex3d(ri.vertices.get(vIndex), ri.vertices.get(vIndex + 1), ri.vertices.get(
 486                     vIndex + 2));
 487             }
 488             gl.glEnd();
 489             maxColorCode = dc.getUniquePickColor().getRGB();
 490
 491             if (null != ri.referenceCenter)
 492                 dc.getView().popReferenceCenter(dc);
 493         }
 494
 495         public Point getSurfacePoint(Angle latitude, Angle longitude, double metersOffset)
 496         {
 497             if (latitude == null || longitude == null)
 498             {
 499                 String msg = WorldWind.retrieveErrMsg("nullValue.LatLonIsNull");
 500                 WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 501                 throw new IllegalArgumentException(msg);
 502             }
 503
 504             if (!this.sector.contains(latitude, longitude))
 505             {
 506                 // not on this geometry
 507                 return null;
 508             }
 509
 510             if (this.ri == null)
 511                 return null;
 512
 513             double lat = latitude.getDegrees();
 514             double lon = longitude.getDegrees();
 515
 516             double bottom = this.sector.getMinLatitude().getDegrees();
 517             double top = this.sector.getMaxLatitude().getDegrees();
 518             double left = this.sector.getMinLongitude().getDegrees();
 519             double right = this.sector.getMaxLongitude().getDegrees();
 520
 521             double leftDecimal = (lon - left) / (right - left);
 522             double bottomDecimal = (lat - bottom) / (top - bottom);
 523
 524             int row = (int) (bottomDecimal * (this.density));
 525             int column = (int) (leftDecimal * (this.density));
 526
 527             double l = createPosition(column, leftDecimal, ri.density);
 528             double h = createPosition(row, bottomDecimal, ri.density);
 529
 530             Point result = RectTile.interpolate(row, column, l, h, ri);
 531             result = result.add(ri.referenceCenter);
 532             if (metersOffset != 0)
 533                 result = applyOffset(this.globe, result, metersOffset);
 534
 535             return result;
 536         }
 537
 538         /**
 539          * Offsets <code>point</code> by <code>metersOffset</code> meters.
 540          *
 541          * @param globe        the <code>Globe</code> from which to offset
 542          * @param point        the <code>Point</code> to offset
 543          * @param metersOffset the magnitude of the offset
 544          * @return <code>point</code> offset along its surface normal as if it were on <code>globe</code>
 545          */
 546         private static Point applyOffset(Globe globe, Point point, double metersOffset)
 547         {
 548             Point normal = globe.computeSurfaceNormalAtPoint(point);
 549             point = Point.fromOriginAndDirection(metersOffset, normal, point);
 550             return point;
 551         }
 552
 553         /**
 554          * Computes from a column (or row) number, and a given offset ranged [0,1] corresponding to the distance along
 555          * the edge of this sector, where between this column and the next column the corresponding position will fall,
 556          * in the range [0,1].
 557          *
 558          * @param start   the number of the column or row to the left, below or on this position
 559          * @param decimal the distance from the left or bottom of the current sector that this position falls
 560          * @param density the number of intervals along the sector's side
 561          * @return a decimal ranged [0,1] representing the position between two columns or rows, rather than between two
 562          *         edges of the sector
 563          */
 564         private static double createPosition(int start, double decimal, int density)
 565         {
 566             double l = ((double) start) / (double) density;
 567             double r = ((double) (start + 1)) / (double) density;
 568
 569             return (decimal - l) / (r - l);
 570         }
 571
 572         /**
 573          * Calculates a <code>Point</code> that sits at <code>xDec</code> offset from <code>column</code> to
 574          * <code>column + 1</code> and at <code>yDec</code> offset from <code>row</code> to <code>row + 1</code>.
 575          * Accounts for the diagonals.
 576          *
 577          * @param row    represents the row which corresponds to a <code>yDec</code> value of 0
 578          * @param column represents the column which corresponds to an <code>xDec</code> value of 0
 579          * @param xDec   constrained to [0,1]
 580          * @param yDec   constrained to [0,1]
 581          * @param ri     the render info holding the vertices, etc.
 582          * @return a <code>Point</code> geometrically within or on the boundary of the quadrilateral whose bottom left
 583          *         corner is indexed by (<code>row</code>, <code>column</code>)
 584          */
 585         private static Point interpolate(int row, int column, double xDec, double yDec, RenderInfo ri)
 586         {
 587             row++;
 588             column++;
 589
 590             int numVerticesPerEdge = ri.density + 3;
 591
 592             int bottomLeft = row * numVerticesPerEdge + column;
 593
 594             bottomLeft *= 3;
 595
 596             int numVertsTimesThree = numVerticesPerEdge * 3;
 597
 598             Point bL = new Point(ri.vertices.get(bottomLeft), ri.vertices.get(bottomLeft + 1), ri.vertices.get(
 599                 bottomLeft + 2));
 600             Point bR = new Point(ri.vertices.get(bottomLeft + 3), ri.vertices.get(bottomLeft + 4),
 601                 ri.vertices.get(bottomLeft + 5));
 602
 603             bottomLeft += numVertsTimesThree;
 604
 605             Point tL = new Point(ri.vertices.get(bottomLeft), ri.vertices.get(bottomLeft + 1), ri.vertices.get(
 606                 bottomLeft + 2));
 607             Point tR = new Point(ri.vertices.get(bottomLeft + 3), ri.vertices.get(bottomLeft + 4),
 608                 ri.vertices.get(bottomLeft + 5));
 609
 610             return interpolate(bL, bR, tR, tL, xDec, yDec);
 611         }
 612
 613         /**
 614          * Calculates the point at (xDec, yDec) in the two triangles defined by {bL, bR, tL} and {bR, tR, tL}. If
 615          * thought of as a quadrilateral, the diagonal runs from tL to bR. Of course, this isn't a quad, it's two
 616          * triangles.
 617          *
 618          * @param bL   the bottom left corner
 619          * @param bR   the bottom right corner
 620          * @param tR   the top right corner
 621          * @param tL   the top left corner
 622          * @param xDec how far along, [0,1] 0 = left edge, 1 = right edge
 623          * @param yDec how far along, [0,1] 0 = bottom edge, 1 = top edge
 624          * @return the point xDec, yDec in the co-ordinate system defined by bL, bR, tR, tL
 625          */
 626         private static Point interpolate(Point bL, Point bR, Point tR, Point tL, double xDec, double yDec)
 627         {
 628             double pos = xDec + yDec;
 629             if (pos == 1)
 630             {
 631                 // on the diagonal - what's more, we don't need to do any "oneMinusT" calculation
 632                 return new Point(tL.x() * yDec + bR.x() * xDec, tL.y() * yDec + bR.y() * xDec,
 633                     tL.z() * yDec + bR.z() * xDec);
 634             }
 635             else if (pos > 1)
 636             {
 637                 // in the "top right" half
 638
 639                 // vectors pointing from top right towards the point we want (can be thought of as "negative" vectors)
 640                 Point horizontalVector = (tL.subtract(tR)).multiply(1 - xDec);
 641                 Point verticalVector = (bR.subtract(tR)).multiply(1 - yDec);
 642
 643                 return tR.add(horizontalVector).add(verticalVector);
 644             }
 645             else
 646             {
 647                 // pos < 1 - in the "bottom left" half
 648
 649                 // vectors pointing from the bottom left towards the point we want
 650                 Point horizontalVector = (bR.subtract(bL)).multiply(xDec);
 651                 Point verticalVector = (tL.subtract(bL)).multiply(yDec);
 652
 653                 return bL.add(horizontalVector).add(verticalVector);
 654             }
 655         }
 656
 657         public String toString()
 658         {
 659             return "level " + this.level + ", density " + this.density + ", sector " + this.sector;
 660         }
 661
 662         protected static java.nio.DoubleBuffer getParameterization(int density)
 663         {
 664             if (density < 1)
 665             {
 666                 density = 1;
 667             }
 668
 669             // Approximate 1 to avoid shearing off of right and top skirts in SurfaceTileRenderer.
 670             // TODO: dig into this more: why are the skirts being sheared off?
 671             final double one = 0.999999;
 672
 673             java.nio.DoubleBuffer p = parameterizations.get(density);
 674             if (p != null)
 675                 return p;
 676
 677             int coordCount = (density + 3) * (density + 3);
 678             p = com.sun.opengl.util.BufferUtil.newDoubleBuffer(2 * coordCount);
 679             double delta = 1d / density;
 680             int k = 2 * (density + 3);
 681             for (int j = 0; j < density; j++)
 682             {
 683                 double v = j * delta;
 684
 685                 // skirt column; duplicate first column
 686                 p.put(k++, 0d);
 687                 p.put(k++, v);
 688
 689                 // interior columns
 690                 for (int i = 0; i < density; i++)
 691                 {
 692                     p.put(k++, i * delta); // u
 693                     p.put(k++, v);
 694                 }
 695
 696                 // last interior column; force u to 1.
 697                 p.put(k++, one);//1d);
 698                 p.put(k++, v);
 699
 700                 // skirt column; duplicate previous column
 701                 p.put(k++, one);//1d);
 702                 p.put(k++, v);
 703             }
 704
 705             // Last interior row
 706             //noinspection UnnecessaryLocalVariable
 707             double v = one;//1d;
 708             p.put(k++, 0d); // skirt column
 709             p.put(k++, v);
 710
 711             for (int i = 0; i < density; i++)
 712             {
 713                 p.put(k++, i * delta); // u
 714                 p.put(k++, v);
 715             }
 716             p.put(k++, one);//1d); // last interior column
 717             p.put(k++, v);
 718
 719             p.put(k++, one);//1d); // skirt column
 720             p.put(k++, v);
 721
 722             // last skirt row
 723             int kk = k - 2 * (density + 3);
 724             for (int i = 0; i < density + 3; i++)
 725             {
 726                 p.put(k++, p.get(kk++));
 727                 p.put(k++, p.get(kk++));
 728             }
 729
 730             // first skirt row
 731             k = 0;
 732             kk = 2 * (density + 3);
 733             for (int i = 0; i < density + 3; i++)
 734             {
 735                 p.put(k++, p.get(kk++));
 736                 p.put(k++, p.get(kk++));
 737             }
 738
 739             parameterizations.put(density, p);
 740
 741             return p;
 742         }
 743
 744         private static java.nio.IntBuffer getIndices(int density)
 745         {
 746             if (density < 1)
 747                 density = 1;
 748
 749             // return a pre-computed buffer if possible.
 750             java.nio.IntBuffer buffer = indexLists.get(density);
 751             if (buffer != null)
 752                 return buffer;
 753
 754             int sideSize = density + 2;
 755
 756             int indexCount = 2 * sideSize * sideSize + 4 * sideSize - 2;
 757             buffer = com.sun.opengl.util.BufferUtil.newIntBuffer(indexCount);
 758             int k = 0;
 759             for (int i = 0; i < sideSize; i++)
 760             {
 761                 buffer.put(k);
 762                 if (i > 0)
 763                 {
 764                     buffer.put(++k);
 765                     buffer.put(k);
 766                 }
 767
 768                 if (i % 2 == 0) // even
 769                 {
 770                     buffer.put(++k);
 771                     for (int j = 0; j < sideSize; j++)
 772                     {
 773                         k += sideSize;
 774                         buffer.put(k);
 775                         buffer.put(++k);
 776                     }
 777                 }
 778                 else // odd
 779                 {
 780                     buffer.put(--k);
 781                     for (int j = 0; j < sideSize; j++)
 782                     {
 783                         k -= sideSize;
 784                         buffer.put(k);
 785                         buffer.put(--k);
 786                     }
 787                 }
 788             }
 789
 790             indexLists.put(density, buffer);
 791
 792             return buffer;
 793         }
 794     }
 795
 796     private final java.util.ArrayList<RectTile> topLevels;
 797     private SectorGeometryList currentTiles = new SectorGeometryList();
 798     private Frustum currentFrustum;
 799     private int currentLevel;
 800     private int maxLevel = DEFAULT_MAX_LEVEL;//14; // TODO: Make configurable
 801     private Sector sector; // union of all tiles selected during call to render()
 802     private int density = DEFAULT_DENSITY; // TODO: make configurable
 803
 804     public EllipsoidRectangularTessellator(Globe globe)
 805     {
 806         this.topLevels = createTopLevelTiles(globe, DEFAULT_NUM_LAT_SUBDIVISIONS, DEFAULT_NUM_LON_SUBDIVISIONS);
 807     }
 808
 809     public Sector getSector()
 810     {
 811         return this.sector;
 812     }
 813
 814     private ArrayList<RectTile> createTopLevelTiles(Globe globe, int nRows, int nCols)
 815     {
 816         ArrayList<RectTile> tops = new ArrayList<RectTile>(nRows * nCols);
 817
 818         double deltaLat = 180d / nRows;
 819         double deltaLon = 360d / nCols;
 820         Angle lastLat = Angle.NEG90;
 821
 822         for (int row = 0; row < DEFAULT_NUM_LAT_SUBDIVISIONS; row++)
 823         {
 824             Angle lat = lastLat.addDegrees(deltaLat);
 825             if (lat.getDegrees() + 1d > 90d)
 826                 lat = Angle.POS90;
 827
 828             Angle lastLon = Angle.NEG180;
 829
 830             for (int col = 0; col < DEFAULT_NUM_LON_SUBDIVISIONS; col++)
 831             {
 832                 Angle lon = lastLon.addDegrees(deltaLon);
 833                 if (lon.getDegrees() + 1d > 180d)
 834                     lon = Angle.POS180;
 835
 836                 tops.add(new RectTile(globe, 0, this.density, new Sector(lastLat, lat, lastLon, lon)));
 837                 lastLon = lon;
 838             }
 839             lastLat = lat;
 840         }
 841
 842         return tops;
 843     }
 844
 845     public SectorGeometryList tessellate(DrawContext dc)
 846     {
 847         if (dc == null)
 848         {
 849             String msg = WorldWind.retrieveErrMsg("nullValue.DrawContextIsNull");
 850             WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 851             throw new IllegalArgumentException(msg);
 852         }
 853
 854         if (dc.getView() == null)
 855         {
 856             String msg = WorldWind.retrieveErrMsg("nullValue.ViewIsNull");
 857             WorldWind.logger().log(java.util.logging.Level.FINE, msg);
 858             throw new IllegalStateException(msg);
 859         }
 860
 861         this.currentTiles.clear();
 862         this.currentLevel = 0;
 863         this.sector = null;
 864
 865         this.currentFrustum = dc.getView().getFrustumInModelCoordinates();
 866         for (RectTile tile : topLevels)
 867         {
 868             this.selectVisibleTiles(dc, tile);
 869         }
 870
 871         dc.setVisibleSector(this.getSector());
 872
 873         for (SectorGeometry tile : this.currentTiles)
 874         {
 875             ((RectTile) tile).makeVerts(dc);
 876         }
 877
 878         return this.currentTiles;
 879     }
 880
 881     private void selectVisibleTiles(DrawContext dc, RectTile tile)
 882     {
 883         if (!tile.getExtent().intersects(this.currentFrustum))
 884             return;
 885
 886         if (this.currentLevel < this.maxLevel && needToSplit(dc, tile))
 887         {
 888             ++this.currentLevel;
 889             RectTile[] subtiles = tile.split();
 890             for (RectTile child : subtiles)
 891             {
 892                 this.selectVisibleTiles(dc, child);
 893             }
 894             --this.currentLevel;
 895             return;
 896         }
 897         this.sector = tile.getSector().union(this.sector);
 898         this.currentTiles.add(tile);
 899     }
 900
 901     private static boolean needToSplit(DrawContext dc, RectTile tile)
 902     {
 903         Point[] corners = tile.sector.computeCornerPoints(dc.getGlobe());
 904         Point centerPoint = tile.sector.computeCenterPoint(dc.getGlobe());
 905
 906         View view = dc.getView();
 907         double d1 = view.getEyePoint().distanceTo(corners[0]);
 908         double d2 = view.getEyePoint().distanceTo(corners[1]);
 909         double d3 = view.getEyePoint().distanceTo(corners[2]);
 910         double d4 = view.getEyePoint().distanceTo(corners[3]);
 911         double d5 = view.getEyePoint().distanceTo(centerPoint);
 912
 913         double minDistance = d1;
 914         if (d2 < minDistance)
 915             minDistance = d2;
 916         if (d3 < minDistance)
 917             minDistance = d3;
 918         if (d4 < minDistance)
 919             minDistance = d4;
 920         if (d5 < minDistance)
 921             minDistance = d5;
 922
 923         double logDist = Math.log10(minDistance);
 924         boolean useTile = tile.log10CellSize <= (logDist - DEFAULT_LOG10_RESOLUTION_TARGET);
 925
 926         return !useTile;
 927     }
 928
 929     public static void main(String[] args)
 930     {
 931         int density = 5;
 932
 933         DoubleBuffer tcs = RectTile.getParameterization(density);
 934         IntBuffer indices = RectTile.getIndices(density);
 935
 936         tcs.rewind();
 937         indices.rewind();
 938         for (int i = 0; i < indices.limit(); i++)
 939         {
 940             int index = indices.get(i);
 941             System.out.println(index + ": " + tcs.get(2 * index) + ", " + tcs.get(2 * index + 1));
 942         }
 943     }
 944 }