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 */
32package com.jme3.terrain.heightmap;
33
34import com.jme3.math.FastMath;
35import java.util.Random;
36import java.util.logging.Level;
37import java.util.logging.Logger;
38import 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 */
45public 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     */
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     */
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
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     */
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     */
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     */
246    protected float getOffset(Random random, float offsetRange, int[] coords, float average) {
247        return 2 * (random.nextFloat() - 0.5F) * offsetRange;
248    }
249
250    public float getPersistence() {
251        return persistence;
252    }
253
254    public void setPersistence(float persistence) {
255        this.persistence = persistence;
256    }
257
258    public float getRange() {
259        return range;
260    }
261
262    public void setRange(float range) {
263        this.range = range;
264    }
265
266    public long getSeed() {
267        return seed;
268    }
269
270    public void setSeed(long seed) {
271        this.seed = seed;
272    }
273}
274