1 /* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 package com.jme3.terrain.heightmap; 33 34 import com.jme3.math.FastMath; 35 import java.util.Random; 36 import java.util.logging.Level; 37 import java.util.logging.Logger; 38 import javax.management.JMException; 39 40 /** 41 * <code>MidpointDisplacementHeightMap</code> generates an heightmap based on 42 * the midpoint displacement algorithm. See Constructor javadoc for more info. 43 * @author cghislai 44 */ 45 public class MidpointDisplacementHeightMap extends AbstractHeightMap { 46 47 private static final Logger logger = Logger.getLogger(MidpointDisplacementHeightMap.class.getName()); 48 private float range; // The offset in which randomness will be added 49 private float persistence; // How the random offset evolves with increasing passes 50 private long seed; // seed for random number generator 51 52 /** 53 * The constructor generates the heightmap. After the first 4 corners are 54 * randomly given an height, the center will be heighted to the average of 55 * the 4 corners to which a random value is added. Then other passes fill 56 * the heightmap by the same principle. 57 * The random value is generated between the values <code>-range</code> 58 * and <code>range</code>. The <code>range</code> parameter is multiplied by 59 * the <code>persistence</code> parameter each pass to smoothen close cell heights. 60 * Extends this class and override the getOffset function for more control of 61 * the randomness (you can use the coordinates and/or the computed average height 62 * to influence the random amount added. 63 * 64 * @param size 65 * The size of the heightmap, must be 2^N+1 66 * @param range 67 * The range in which randomness will be added. A value of 1 will 68 * allow -1 to 1 value changes. 69 * @param persistence 70 * The factor by which the range will evolve at each iteration. 71 * A value of 0.5f will halve the range at each iteration and is 72 * typically a good choice 73 * @param seed 74 * A seed to feed the random number generator. 75 * @throw JMException if size is not a power of two plus one. 76 */ MidpointDisplacementHeightMap(int size, float range, float persistence, long seed)77 public MidpointDisplacementHeightMap(int size, float range, float persistence, long seed) throws Exception { 78 if (size < 0 || !FastMath.isPowerOfTwo(size - 1)) { 79 throw new JMException("The size is negative or not of the form 2^N +1" 80 + " (a power of two plus one)"); 81 } 82 this.size = size; 83 this.range = range; 84 this.persistence = persistence; 85 this.seed = seed; 86 load(); 87 } 88 89 /** 90 * The constructor generates the heightmap. After the first 4 corners are 91 * randomly given an height, the center will be heighted to the average of 92 * the 4 corners to which a random value is added. Then other passes fill 93 * the heightmap by the same principle. 94 * The random value is generated between the values <code>-range</code> 95 * and <code>range</code>. The <code>range</code> parameter is multiplied by 96 * the <code>persistence</code> parameter each pass to smoothen close cell heights. 97 * @param size 98 * The size of the heightmap, must be 2^N+1 99 * @param range 100 * The range in which randomness will be added. A value of 1 will 101 * allow -1 to 1 value changes. 102 * @param persistence 103 * The factor by which the range will evolve at each iteration. 104 * A value of 0.5f will halve the range at each iteration and is 105 * typically a good choice 106 * @throw JMException if size is not a power of two plus one. 107 */ MidpointDisplacementHeightMap(int size, float range, float persistence)108 public MidpointDisplacementHeightMap(int size, float range, float persistence) throws Exception { 109 this(size, range, persistence, new Random().nextLong()); 110 } 111 112 /** 113 * Generate the heightmap. 114 * @return 115 */ 116 @Override load()117 public boolean load() { 118 // clean up data if needed. 119 if (null != heightData) { 120 unloadHeightMap(); 121 } 122 heightData = new float[size * size]; 123 float[][] tempBuffer = new float[size][size]; 124 Random random = new Random(seed); 125 126 tempBuffer[0][0] = random.nextFloat(); 127 tempBuffer[0][size - 1] = random.nextFloat(); 128 tempBuffer[size - 1][0] = random.nextFloat(); 129 tempBuffer[size - 1][size - 1] = random.nextFloat(); 130 131 float offsetRange = range; 132 int stepSize = size - 1; 133 while (stepSize > 1) { 134 int[] nextCoords = {0, 0}; 135 while (nextCoords != null) { 136 nextCoords = doSquareStep(tempBuffer, nextCoords, stepSize, offsetRange, random); 137 } 138 nextCoords = new int[]{0, 0}; 139 while (nextCoords != null) { 140 nextCoords = doDiamondStep(tempBuffer, nextCoords, stepSize, offsetRange, random); 141 } 142 stepSize /= 2; 143 offsetRange *= persistence; 144 } 145 146 for (int i = 0; i < size; i++) { 147 for (int j = 0; j < size; j++) { 148 setHeightAtPoint((float) tempBuffer[i][j], j, i); 149 } 150 } 151 152 normalizeTerrain(NORMALIZE_RANGE); 153 154 logger.log(Level.INFO, "Midpoint displacement heightmap generated"); 155 return true; 156 } 157 158 /** 159 * Will fill the value at (coords[0]+stepSize/2, coords[1]+stepSize/2) with 160 * the average from the corners of the square with topleft corner at (coords[0],coords[1]) 161 * and width of stepSize. 162 * @param tempBuffer the temprary heightmap 163 * @param coords an int array of lenght 2 with the x coord in position 0 164 * @param stepSize the size of the square 165 * @param offsetRange the offset range within a random value is picked and added to the average 166 * @param random the random generator 167 * @return 168 */ doSquareStep(float[][] tempBuffer, int[] coords, int stepSize, float offsetRange, Random random)169 protected int[] doSquareStep(float[][] tempBuffer, int[] coords, int stepSize, float offsetRange, Random random) { 170 float cornerAverage = 0; 171 int x = coords[0]; 172 int y = coords[1]; 173 cornerAverage += tempBuffer[x][y]; 174 cornerAverage += tempBuffer[x + stepSize][y]; 175 cornerAverage += tempBuffer[x + stepSize][y + stepSize]; 176 cornerAverage += tempBuffer[x][y + stepSize]; 177 cornerAverage /= 4; 178 float offset = getOffset(random, offsetRange, coords, cornerAverage); 179 tempBuffer[x + stepSize / 2][y + stepSize / 2] = cornerAverage + offset; 180 181 // Only get to next square if the center is still in map 182 if (x + stepSize * 3 / 2 < size) { 183 return new int[]{x + stepSize, y}; 184 } 185 if (y + stepSize * 3 / 2 < size) { 186 return new int[]{0, y + stepSize}; 187 } 188 return null; 189 } 190 191 /** 192 * Will fill the cell at (x+stepSize/2, y) with the average of the 4 corners 193 * of the diamond centered on that point with width and height of stepSize. 194 * @param tempBuffer 195 * @param coords 196 * @param stepSize 197 * @param offsetRange 198 * @param random 199 * @return 200 */ doDiamondStep(float[][] tempBuffer, int[] coords, int stepSize, float offsetRange, Random random)201 protected int[] doDiamondStep(float[][] tempBuffer, int[] coords, int stepSize, float offsetRange, Random random) { 202 int cornerNbr = 0; 203 float cornerAverage = 0; 204 int x = coords[0]; 205 int y = coords[1]; 206 int[] dxs = new int[]{0, stepSize / 2, stepSize, stepSize / 2}; 207 int[] dys = new int[]{0, -stepSize / 2, 0, stepSize / 2}; 208 209 for (int d = 0; d < 4; d++) { 210 int i = x + dxs[d]; 211 if (i < 0 || i > size - 1) { 212 continue; 213 } 214 int j = y + dys[d]; 215 if (j < 0 || j > size - 1) { 216 continue; 217 } 218 cornerAverage += tempBuffer[i][j]; 219 cornerNbr++; 220 } 221 cornerAverage /= cornerNbr; 222 float offset = getOffset(random, offsetRange, coords, cornerAverage); 223 tempBuffer[x + stepSize / 2][y] = cornerAverage + offset; 224 225 if (x + stepSize * 3 / 2 < size) { 226 return new int[]{x + stepSize, y}; 227 } 228 if (y + stepSize / 2 < size) { 229 if (x + stepSize == size - 1) { 230 return new int[]{-stepSize / 2, y + stepSize / 2}; 231 } else { 232 return new int[]{0, y + stepSize / 2}; 233 } 234 } 235 return null; 236 } 237 238 /** 239 * Generate a random value to add to the computed average 240 * @param random the random generator 241 * @param offsetRange 242 * @param coords 243 * @param average 244 * @return A semi-random value within offsetRange 245 */ getOffset(Random random, float offsetRange, int[] coords, float average)246 protected float getOffset(Random random, float offsetRange, int[] coords, float average) { 247 return 2 * (random.nextFloat() - 0.5F) * offsetRange; 248 } 249 getPersistence()250 public float getPersistence() { 251 return persistence; 252 } 253 setPersistence(float persistence)254 public void setPersistence(float persistence) { 255 this.persistence = persistence; 256 } 257 getRange()258 public float getRange() { 259 return range; 260 } 261 setRange(float range)262 public void setRange(float range) { 263 this.range = range; 264 } 265 getSeed()266 public long getSeed() { 267 return seed; 268 } 269 setSeed(long seed)270 public void setSeed(long seed) { 271 this.seed = seed; 272 } 273 } 274