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