tim/prune/threedee/TerrainHelper.java

   1 package tim.prune.threedee;
   2
   3 import java.awt.image.BufferedImage;
   4 import java.io.File;
   5 import java.io.IOException;
   6
   7 import javax.imageio.ImageIO;
   8 import javax.vecmath.Point3d;
   9 import javax.vecmath.TexCoord2f;
  10
  11 import tim.prune.data.Altitude;
  12 import tim.prune.data.Coordinate;
  13 import tim.prune.data.DataPoint;
  14 import tim.prune.data.DoubleRange;
  15 import tim.prune.data.Field;
  16 import tim.prune.data.FieldList;
  17 import tim.prune.data.Latitude;
  18 import tim.prune.data.Longitude;
  19 import tim.prune.data.Track;
  20 import tim.prune.data.TrackExtents;
  21 import tim.prune.data.UnitSetLibrary;
  22 import tim.prune.gui.map.MapUtils;
  23
  24 /**
  25  * Helper for generating the arrays needed for the 3d terrain
  26  */
  27 public class TerrainHelper
  28 {
  29         /** Number of nodes on each side of the square grid */
  30         private int _gridSize = 0;
  31
  32         /**
  33          * Constructor
  34          * @param inGridSize grid size
  35          */
  36         public TerrainHelper(int inGridSize) {
  37                 _gridSize = inGridSize;
  38         }
  39
  40         /**
  41          * @return grid size
  42          */
  43         public int getGridSize() {
  44                 return _gridSize;
  45         }
  46
  47
  48         /**
  49          * Convert the terrain coordinates from raw form to TriangleStripArray form
  50          * (with repeated nodes)
  51          * @param inRawPoints array of raw points as formed from the track
  52          * @return point coordinates as array
  53          */
  54         public Point3d[] getTerrainCoordinates(Point3d[] inRawPoints)
  55         {
  56                 final int numNodes = _gridSize * _gridSize;
  57                 if (_gridSize <= 1 || inRawPoints == null || inRawPoints.length != numNodes) {return null;}
  58                 // Put these nodes into a new result array (repeating nodes as necessary)
  59                 final int resultSize = _gridSize * (_gridSize * 2 - 2);
  60                 Point3d[] result = new Point3d[resultSize];
  61                 final int numStrips = _gridSize - 1;
  62                 int resultIndex = 0;
  63                 for (int strip=0; strip<numStrips; strip++)
  64                 {
  65                         for (int col=0; col<_gridSize; col++)
  66                         {
  67                                 int bottomNodeIndex = strip * _gridSize + col;
  68                                 int topNodeIndex = bottomNodeIndex + _gridSize;
  69                                 result[resultIndex++] = inRawPoints[bottomNodeIndex];
  70                                 result[resultIndex++] = inRawPoints[topNodeIndex];
  71                         }
  72                 }
  73                 return result;
  74         }
  75
  76
  77         /**
  78          * Get the texture coordinates as an array
  79          * @return texture coordinates as array
  80          */
  81         public TexCoord2f[] getTextureCoordinates()
  82         {
  83                 if (_gridSize <= 1) {return null;}
  84                 final int numNodes = _gridSize * _gridSize;
  85                 final float gridStep = 1.0f / (_gridSize - 1);
  86                 // Build all the required nodes
  87                 TexCoord2f[] nodes = new TexCoord2f[numNodes];
  88                 for (int i=0; i<_gridSize; i++)
  89                 {
  90                         for (int j=0; j<_gridSize; j++)
  91                         {
  92                                 nodes[j * _gridSize + i] = new TexCoord2f(gridStep * i, 1.0f - gridStep * j);
  93                         }
  94                 }
  95                 // Now put these nodes into a new result array (repeating nodes as necessary)
  96                 final int resultSize = _gridSize * (_gridSize * 2 - 2);
  97                 TexCoord2f[] result = new TexCoord2f[resultSize];
  98                 final int numStrips = _gridSize - 1;
  99                 int resultIndex = 0;
 100                 for (int strip=0; strip<numStrips; strip++)
 101                 {
 102                         for (int col=0; col<_gridSize; col++)
 103                         {
 104                                 int bottomNodeIndex = strip * _gridSize + col;
 105                                 int topNodeIndex = bottomNodeIndex + _gridSize;
 106                                 result[resultIndex++] = nodes[bottomNodeIndex];
 107                                 result[resultIndex++] = nodes[topNodeIndex];
 108                         }
 109                 }
 110                 return result;
 111         }
 112
 113         /**
 114          * @return strip lengths as array
 115          */
 116         public int[] getStripLengths()
 117         {
 118                 final int numStrips = _gridSize - 1;
 119                 final int nodesPerStrip = _gridSize * 2;
 120                 int[] result = new int[numStrips];
 121                 for (int i=0; i<numStrips; i++) {
 122                         result[i] = nodesPerStrip;
 123                 }
 124                 return result;
 125         }
 126
 127         /**
 128          * Create a grid of points in a new Track
 129          * @param inDataTrack track from which the extents should be obtained
 130          * @return Track containing all the points in the grid
 131          */
 132         public Track createGridTrack(Track inDataTrack)
 133         {
 134                 // Work out the size of the current track
 135                 TrackExtents extents = new TrackExtents(inDataTrack);
 136                 extents.applySquareBorder();
 137                 DoubleRange xRange = extents.getXRange();
 138                 DoubleRange yRange = extents.getYRange();
 139                 // Create the array of points
 140                 final int numPoints = _gridSize * _gridSize;
 141                 final double xStep = xRange.getRange() / (_gridSize - 1);
 142                 final double yStep = yRange.getRange() / (_gridSize - 1);
 143                 DataPoint[] points = new DataPoint[numPoints];
 144                 for (int i=0; i<_gridSize; i++)
 145                 {
 146                         double pY = yRange.getMinimum() + i * yStep;
 147                         for (int j=0; j<_gridSize; j++)
 148                         {
 149                                 // Create a new point with the appropriate lat and long, with no altitude
 150                                 double pX = xRange.getMinimum() + j * xStep;
 151                                 DataPoint point = new DataPoint(
 152                                         new Latitude(MapUtils.getLatitudeFromY(pY), Coordinate.FORMAT_DECIMAL_FORCE_POINT),
 153                                         new Longitude(MapUtils.getLongitudeFromX(pX), Coordinate.FORMAT_DECIMAL_FORCE_POINT),
 154                                         null);
 155                                 //System.out.println("Created point at " + point.getLatitude().output(Coordinate.FORMAT_DEG_MIN_SEC)
 156                                 //      + ", " + point.getLongitude().output(Coordinate.FORMAT_DEG_MIN_SEC));
 157                                 points[i * _gridSize + j] = point;
 158                         }
 159                 }
 160                 // Put these into a new track
 161                 Field[] fields = {Field.LATITUDE, Field.LONGITUDE, Field.ALTITUDE};
 162                 Track grid = new Track(new FieldList(fields), points);
 163                 return grid;
 164         }
 165
 166         /**
 167          * Write the given terrain track out to an indexed png file
 168          * @param inModel three-d data model with terrain
 169          * @param inPngFile file to write to
 170          */
 171         public void writeHeightMap(ThreeDModel inModel, File inPngFile)
 172         {
 173                 BufferedImage image = new BufferedImage(_gridSize, _gridSize, BufferedImage.TYPE_BYTE_INDEXED);
 174                 for (int y=0; y<_gridSize; y++)
 175                 {
 176                         for (int x=0; x<_gridSize; x++)
 177                         {
 178                                 double heightValue = inModel.getScaledTerrainValue(y * _gridSize + x) * 256;
 179                                 // Need to ask colour model what rgb to use for this index (a little round-the-houses)
 180                                 image.setRGB(x, y, image.getColorModel().getRGB((int) heightValue));
 181                         }
 182                 }
 183                 try
 184                 {
 185                         ImageIO.write(image, "PNG", inPngFile);
 186                 }
 187                 catch (IOException ioe) {System.err.println(ioe.getClass().getName() + " - " + ioe.getMessage());}
 188         }
 189
 190
 191         /**
 192          * Try to fix the voids in the given terrain track by averaging neighbour values where possible
 193          * @param inTerrainTrack terrain track to fix
 194          */
 195         public void fixVoids(Track inTerrainTrack)
 196         {
 197                 int numVoids = countVoids(inTerrainTrack);
 198                 if (numVoids == 0) {return;}
 199                 //System.out.println("Starting to fix, num voids = " + numVoids);
 200                 // Fix the holes which are surrounded on all four sides by non-holes
 201                 fixSingleHoles(inTerrainTrack);
 202                 //System.out.println("Fixed single holes, now num voids = " + countVoids(inTerrainTrack));
 203                 // Maybe there is something to do in the corners?
 204                 fixCornersAndEdges(inTerrainTrack);
 205                 //System.out.println("Fixed corners, now num voids = " + countVoids(inTerrainTrack));
 206                 // Now fix the bigger holes, which should fix everything left
 207                 fixBiggerHoles(inTerrainTrack);
 208                 final int numHolesLeft = countVoids(inTerrainTrack);
 209                 if (numHolesLeft > 0) {
 210                         System.out.println("Fixed bigger holes, now num voids = " + countVoids(inTerrainTrack));
 211                 }
 212         }
 213
 214         /**
 215          * @param inTerrainTrack terrain track
 216          * @return number of voids (points without altitudes)
 217          */
 218         private static int countVoids(Track inTerrainTrack)
 219         {
 220                 // DEBUG: Show state of voids first
 221 //              final int gridSize = (int) Math.sqrt(inTerrainTrack.getNumPoints());
 222 //              StringBuilder sb = new StringBuilder();
 223 //              for (int i=0; i<inTerrainTrack.getNumPoints(); i++)
 224 //              {
 225 //                      if ((i%gridSize) == 0) sb.append('\n');
 226 //                      if (inTerrainTrack.getPoint(i).hasAltitude()) {
 227 //                              sb.append('A');
 228 //                      } else {
 229 //                              sb.append(' ');
 230 //                      }
 231 //              }
 232 //              System.out.println("Voids:" + sb.toString());
 233                 // END DEBUG
 234
 235                 int numVoids = 0;
 236                 if (inTerrainTrack != null)
 237                 {
 238                         for (int i=0; i<inTerrainTrack.getNumPoints(); i++) {
 239                                 if (!inTerrainTrack.getPoint(i).hasAltitude()) {
 240                                         numVoids++;
 241                                 }
 242                         }
 243                 }
 244                 return numVoids;
 245         }
 246
 247         /**
 248          * Just deal with single holes surrounded by at least four direct neighbours
 249          * @param inTerrainTrack terrain track to fix
 250          */
 251         private void fixSingleHoles(Track inTerrainTrack)
 252         {
 253                 // Holes with neighbours in all directions
 254                 final int startIndex = 1, endIndex = _gridSize - 2;
 255                 for (int x = startIndex; x <= endIndex; x++)
 256                 {
 257                         for (int y = startIndex; y <= endIndex; y++)
 258                         {
 259                                 int pIndex = x * _gridSize + y;
 260                                 // Get the point and its neighbours
 261                                 final DataPoint p = inTerrainTrack.getPoint(pIndex);
 262                                 if (!p.hasAltitude())
 263                                 {
 264                                         final DataPoint pl = inTerrainTrack.getPoint(pIndex - 1);
 265                                         final DataPoint pr = inTerrainTrack.getPoint(pIndex + 1);
 266                                         final DataPoint pu = inTerrainTrack.getPoint(pIndex + _gridSize);
 267                                         final DataPoint pd = inTerrainTrack.getPoint(pIndex - _gridSize);
 268                                         // Check if the points are null??
 269                                         if (pl == null || pr == null || pu == null || pd == null)
 270                                         {
 271                                                 System.err.println("Woah. Got a null point in fixSingleHoles. x=" + x + ", y=" + y + ", grid=" + _gridSize);
 272                                                 System.err.println("index=" + pIndex);
 273                                                 if (pl == null) System.err.println("pl is null");
 274                                                 if (pr == null) System.err.println("pr is null");
 275                                                 if (pu == null) System.err.println("pu is null");
 276                                                 if (pd == null) System.err.println("pd is null");
 277                                                 continue;
 278                                         }
 279                                         // Check that all the neighbours have altitudes
 280                                         if (pl.hasAltitude() && pr.hasAltitude() && pu.hasAltitude() && pd.hasAltitude())
 281                                         {
 282                                                 // Now check the double-neighbours
 283                                                 final DataPoint pll = inTerrainTrack.getPoint(pIndex - 2);
 284                                                 final DataPoint prr = inTerrainTrack.getPoint(pIndex + 2);
 285                                                 final DataPoint puu = inTerrainTrack.getPoint(pIndex + 2 * _gridSize);
 286                                                 final DataPoint pdd = inTerrainTrack.getPoint(pIndex - 2 * _gridSize);
 287
 288                                                 double altitude = 0.0;
 289                                                 if (pll != null && pll.hasAltitude() && prr != null && prr.hasAltitude()
 290                                                         && puu != null && puu.hasAltitude() && pdd != null && pdd.hasAltitude())
 291                                                 {
 292                                                         // Use the double-neighbours too to take into account the gradients
 293                                                         altitude = (
 294                                                                   pl.getAltitude().getMetricValue() * 1.5
 295                                                                 - pll.getAltitude().getMetricValue() * 0.5
 296                                                                 + pr.getAltitude().getMetricValue() * 1.5
 297                                                                 - prr.getAltitude().getMetricValue() * 0.5
 298                                                                 + pd.getAltitude().getMetricValue() * 1.5
 299                                                                 - pdd.getAltitude().getMetricValue() * 0.5
 300                                                                 + pu.getAltitude().getMetricValue() * 1.5
 301                                                                 - puu.getAltitude().getMetricValue() * 0.5) / 4.0;
 302                                                 }
 303                                                 else
 304                                                 {
 305                                                         // no double-neighbours, just use neighbours
 306                                                         altitude = (
 307                                                                   pl.getAltitude().getMetricValue()
 308                                                                 + pr.getAltitude().getMetricValue()
 309                                                                 + pd.getAltitude().getMetricValue()
 310                                                                 + pu.getAltitude().getMetricValue()) / 4.0;
 311                                                 }
 312                                                 // Set this altitude in the point
 313                                                 p.setFieldValue(Field.ALTITUDE, "" + altitude, false);
 314                                                 // force value to metres
 315                                                 p.getAltitude().reset(new Altitude((int) altitude, UnitSetLibrary.UNITS_METRES));
 316                                         }
 317                                 }
 318                         }
 319                 }
 320         }
 321
 322         /**
 323          * Try to fix the corners and edges, if they're blank
 324          * @param inTerrainTrack terrain track
 325          */
 326         private void fixCornersAndEdges(Track inTerrainTrack)
 327         {
 328                 fixCorner(inTerrainTrack, 0, 1, 1);
 329                 fixCorner(inTerrainTrack, _gridSize-1, -1, 1);
 330                 fixCorner(inTerrainTrack, (_gridSize-1)*_gridSize, 1, -1);
 331                 fixCorner(inTerrainTrack, _gridSize*_gridSize-1, -1, -1);
 332                 fixEdge(inTerrainTrack, 0, 1);
 333                 fixEdge(inTerrainTrack, _gridSize-1, _gridSize);
 334                 fixEdge(inTerrainTrack, (_gridSize-1)*_gridSize, -_gridSize);
 335                 fixEdge(inTerrainTrack, _gridSize*_gridSize-1, -1);
 336         }
 337
 338         /**
 339          * Fix a single corner by searching along adjacent edges and averaging the nearest neighbours
 340          * @param inTerrainTrack terrain track
 341          * @param inCornerIndex index of corner to fill
 342          * @param inXinc increment in x direction (+1 or -1)
 343          * @param inYinc increment in y direction (+1 or -1)
 344          */
 345         private void fixCorner(Track inTerrainTrack, int inCornerIndex, int inXinc, int inYinc)
 346         {
 347                 DataPoint corner = inTerrainTrack.getPoint(inCornerIndex);
 348                 if (corner == null || corner.hasAltitude()) {return;}
 349                 // Corner hasn't got an altitude, we'll have to look for it
 350                 int sIndex1 = inCornerIndex, sIndex2 = inCornerIndex;
 351                 Altitude alt1 = null, alt2 = null;
 352
 353                 for (int i=1; i<_gridSize && !corner.hasAltitude(); i++)
 354                 {
 355                         sIndex1 += inXinc;
 356                         sIndex2 += (inYinc * _gridSize);
 357                         // System.out.println("To fill corner " + inCornerIndex + ", looking at indexes " + sIndex1 + " and " + sIndex2);
 358                         if (alt1 == null)
 359                         {
 360                                 DataPoint source1 = inTerrainTrack.getPoint(sIndex1);
 361                                 if (source1 != null && source1.hasAltitude()) {alt1 = source1.getAltitude();}
 362                         }
 363                         if (alt2 == null)
 364                         {
 365                                 DataPoint source2 = inTerrainTrack.getPoint(sIndex2);
 366                                 if (source2 != null && source2.hasAltitude()) {alt2 = source2.getAltitude();}
 367                         }
 368                         // Can we average these?
 369                         if (alt1 != null && alt2 != null)
 370                         {
 371                                 // System.out.println("Averaging values " + alt1.getMetricValue() + " and " + alt2.getMetricValue());
 372                                 int newAltitude = (int) ((alt1.getMetricValue() + alt2.getMetricValue()) / 2.0);
 373                                 corner.setFieldValue(Field.ALTITUDE, "" + newAltitude, false);
 374                         }
 375                 }
 376         }
 377
 378         /**
 379          * Fix any holes found in the specified edge
 380          * @param inTerrainTrack terrain track
 381          * @param inCornerIndex index of corner to start from
 382          * @param inInc increment along edge
 383          */
 384         private void fixEdge(Track inTerrainTrack, int inCornerIndex, int inInc)
 385         {
 386                 int prevIndexWithAlt = -1;
 387                 int sIndex = inCornerIndex;
 388                 if (inTerrainTrack.getPoint(sIndex).hasAltitude()) {prevIndexWithAlt = 0;}
 389                 for (int i=1; i<_gridSize; i++)
 390                 {
 391                         sIndex += inInc;
 392                         if (inTerrainTrack.getPoint(sIndex).hasAltitude())
 393                         {
 394                                 if (prevIndexWithAlt >= 0 && prevIndexWithAlt < (i-1))
 395                                 {
 396                                         final int gapLen = i - prevIndexWithAlt;
 397                                         final double alt1 = inTerrainTrack.getPoint(prevIndexWithAlt).getAltitude().getMetricValue();
 398                                         final double alt2 = inTerrainTrack.getPoint(i).getAltitude().getMetricValue();
 399                                         for (int j = 1; j < gapLen; j++)
 400                                         {
 401                                                 // System.out.println("Fill in " + (prevIndexWithAlt + j) + " using " + prevIndexWithAlt + " and " + i);
 402                                                 final double alt = alt1 + (alt2-alt1) * j / gapLen;
 403                                                 final DataPoint p = inTerrainTrack.getPoint(inCornerIndex + (prevIndexWithAlt + j) * inInc);
 404                                                 p.setFieldValue(Field.ALTITUDE, "" + (int) alt, false);
 405                                         }
 406                                 }
 407                                 prevIndexWithAlt = i;
 408                         }
 409                 }
 410         }
 411
 412         /**
 413          * Try to fix bigger holes by interpolating between neighbours
 414          * @param inTerrainTrack terrain track
 415          */
 416         private void fixBiggerHoles(Track inTerrainTrack)
 417         {
 418                 double[] altitudes = new double[inTerrainTrack.getNumPoints()];
 419                 for (int i=0; i<_gridSize; i++)
 420                 {
 421                         int prevHoriz = -1, prevVert = -1;
 422                         for (int j=0; j<_gridSize; j++)
 423                         {
 424                                 if (inTerrainTrack.getPoint(i * _gridSize + j).hasAltitude())
 425                                 {
 426                                         if (prevHoriz > -1 && prevHoriz != (j-1))
 427                                         {
 428 //                                              System.out.println("Found a gap for y=" + i +" between x=" + prevHoriz + " and " + j + " (" + (j-prevHoriz-1) + ")");
 429                                                 double startVal = inTerrainTrack.getPoint(i * _gridSize + prevHoriz).getAltitude().getMetricValue();
 430                                                 double endVal   = inTerrainTrack.getPoint(i * _gridSize + j).getAltitude().getMetricValue();
 431                                                 for (int k=prevHoriz + 1; k< j; k++)
 432                                                 {
 433                                                         double val = startVal + (k-prevHoriz) * (endVal-startVal) / (j-prevHoriz);
 434                                                         if (altitudes[i * _gridSize + k] > 0.0) {
 435                                                                 altitudes[i * _gridSize + k] = (altitudes[i * _gridSize + k] + val) / 2.0;
 436                                                         }
 437                                                         else {
 438                                                                 altitudes[i * _gridSize + k] = val;
 439                                                         }
 440                                                 }
 441                                         }
 442                                         prevHoriz = j;
 443                                 }
 444                                 if (inTerrainTrack.getPoint(j * _gridSize + i).hasAltitude())
 445                                 {
 446                                         if (prevVert > -1 && prevVert != (j-1))
 447                                         {
 448 //                                              System.out.println("Found a gap for x=" + i +" between y=" + prevVert + " and " + j + " (" + (j-prevVert-1) + ")");
 449                                                 double startVal = inTerrainTrack.getPoint(prevVert * _gridSize + i).getAltitude().getMetricValue();
 450                                                 double endVal   = inTerrainTrack.getPoint(j * _gridSize + i).getAltitude().getMetricValue();
 451                                                 for (int k=prevVert + 1; k< j; k++)
 452                                                 {
 453                                                         double val = startVal + (k-prevVert) * (endVal-startVal) / (j-prevVert);
 454                                                         if (altitudes[k * _gridSize + i] > 0.0) {
 455                                                                 altitudes[k * _gridSize + i] = (altitudes[k * _gridSize + i] + val) / 2.0;
 456                                                         }
 457                                                         else {
 458                                                                 altitudes[k * _gridSize + i] = val;
 459                                                         }
 460                                                 }
 461                                         }
 462                                         prevVert = j;
 463                                 }
 464                         }
 465                 }
 466                 // Now the doubles have been set and/or averaged, we can set the values in the points
 467                 for (int i=0; i<inTerrainTrack.getNumPoints(); i++)
 468                 {
 469                         DataPoint p = inTerrainTrack.getPoint(i);
 470                         if (!p.hasAltitude() && altitudes[i] > 0.0)
 471                         {
 472                                 p.setFieldValue(Field.ALTITUDE, "" + altitudes[i], false);
 473                                 p.getAltitude().reset(new Altitude((int) altitudes[i], UnitSetLibrary.UNITS_METRES));
 474                         }
 475                 }
 476         }
 477 }