# 分形地形算法

```(function() {

function generateTerrain(width, height, smoothness) {
var smoothness = typeof smoothness === 'undefined' ? 1 : smoothness;
var size = smallestPowerOfTwoAfter(Math.max(width, height));

var squareTerrain = generateSquareTerrain(size, smoothness);
var terrain = [];

for (var i = 0; i <= height; ++i) {
terrain.push(squareTerrain[i].slice(0, width + 1));
}

return terrain;
}

function smallestPowerOfTwoAfter(n) {
var ret = 1;
while (ret < n) {
ret <<= 1;
}
return ret;
}

function generateSquareTerrain(size, smoothness) {

if (size & (size - 1)) {
throw new Error('Expected terrain size to be a power of 2, received ' +
size + ' instead.');
}

var mat = generateMatrix(size + 1);
iterate(mat, smoothness);

return mat;
}

function generateMatrix(size) {
var matrix = [];

for (var i = 0; i < size; i++) {
var row = [];
for (var j = 0; j < size; ++j) {
row.push(0);
}
matrix.push(row);
};

return matrix;
}

function iterate(matrix, smoothness) {

var counter = 0;

var numIteration = Math.log(matrix.length - 1) / Math.LN2;
while (counter++ < numIteration) {
diamond(matrix, counter, smoothness);
square(matrix, counter, smoothness);
}
}

function diamond(matrix, depth, smoothness) {

var len = matrix.length;
var terrainSize = len - 1;
var numSegs = 1 << (depth - 1);
var span = terrainSize / numSegs;
var half = span / 2;

for (var x = 0; x < terrainSize; x += span) {
for (var y = 0; y < terrainSize; y += span) {
//  (x, y)
//    \
//     a---b---c
//     |   |   |
//     d---e---f
//     |   |   |
//     g---h---i
//
//     \___ ___/
//         V
//       span
//
var va = [x, y];
var vc = [x + span, y];
var ve = [x + half, y + half];
var vg = [x, y + span];
var vi = [x + span, y + span];

var heights = [va, vc, vg, vi].map(function(v) {
return matrix[v[1]][v[0]];
});

var avg = average(heights);

var offset = getH(smoothness, depth);

matrix[ve[1]][ve[0]] = avg + offset;
}
}
}

function square(matrix, depth, smoothness) {

var len = matrix.length
var terrainSize = len - 1;
var numSegs = 1 << (depth - 1);
var span = terrainSize / numSegs;
var half = span / 2;

for (var x = 0; x < terrainSize; x += span) {
for (var y = 0; y < terrainSize; y += span) {
//       h = avg(g, c, i, m) + random;
//       f = avg(a, g, k, i) + random;
//       j = f;
//
//  (x, y)
//    \
//     a---b---c---d---e
//     | \ | / | \ | / |
//     f---g---h---i---j
//     | / | \ | / | \ |
//     k---l---m---n---o
//     | \ | / | \ | / |
//     p---q---r---s---t
//     | / | \ | / | \ |
//     u---v---w---x---y
//
//     \___ ___/
//         V
//       span
//
var va = [x, y];
var vb = [x + half, y];
var vc = [x + span, y];
var vf = [x, y + half];
var vg = [x + half, y + half];
var vh = [x + span, y + half];
var vk = [x, y + span];
var vl = [x + half, y + span];
var vm = [x + span, y + span];

var vhr = [x + half * 3, y + half];
if (vhr[0] > terrainSize) vhr[0] = half;

var vfl = [x - half, y + half]
if (vfl[0] < 0) vfl[0] = terrainSize - half;

var vlu = [x + half, y + half * 3];
if (vlu[1] > terrainSize) vlu[1] = half;

var vba = [x + half, y - half]
if (vba[1] < 0) vba[1] = terrainSize - half;

squareHelper(matrix, depth, smoothness, va, vg, vk, vfl, vf);
squareHelper(matrix, depth, smoothness, va, vba, vc, vg, vb);
squareHelper(matrix, depth, smoothness, vc, vhr, vm, vg, vh);
squareHelper(matrix, depth, smoothness, vk, vg, vm, vlu, vl);
}
}

for (var y = 0; y < terrainSize; y += span) {
matrix[y][terrainSize] = matrix[y][0];
}
for (var x = 0; x < terrainSize; x += span) {
matrix[terrainSize][x] = matrix[0][x];
}
}

function squareHelper(matrix, depth, smoothness, a, b, c, d, t) {
var heights = [a, b, c, d].map(function(v) {
return matrix[v[1]][v[0]];
});
var avg = average(heights);
var offset = getH(smoothness, depth);
matrix[t[1]][t[0]] = avg + offset;
}

function getH(smoothness, depth) {
var sign = Math.random() > 0.5 ? 1 : -1;
var reduce = 1;
for (var i = 0; i < depth; ++i) {
reduce *= Math.pow(2, -smoothness);
}
return sign * Math.random() * reduce;
}

function average(numbers) {
var sum = 0;
numbers.forEach(function(v) {
sum += v;
});
return sum / numbers.length;
}

var root;
if (typeof exports !== 'undefined' && exports !== null) {
root = exports;
} else {
root = window;
}
root.generateTerrain = generateTerrain;

}).call(this);

var RandomPool = (function() {

var origRandom = Math.random;
var pool       = [];
var counter    = 0;

function next() {
var rand;
if (counter >= pool.length) {
rand = origRandom();
pool.push(rand);
} else {
rand = pool[counter];
}
counter++;
return rand;
};

function seek(index) {
counter = Math.min(index, pool.length);
}

function reset() {
counter = 0;
pool = [];
}

function hook() {
Math.random = next;
}

function unhook() {
Math.random = origRandom;
}

return {
next         : next,
seek         : seek,
reset        : reset,
hook         : hook,
unhook       : unhook
};

})();

var TerrainModel = (function(){

var model;

function update(opts){

var size = opts.size || 32;
var smoothness = opts.smoothness || 1.0;
var zScale = opts.zScale || 200;

model = generateTerrain(size, size, smoothness);
updateZ(zScale);
}

function updateZ(z){
var width = model[0].length;
var height = model.length;
var terrain = [];

var i, j;
var row;
for(i = 0; i < height; ++i){
row = [];
for(j = 0; j < width; ++j){
row.push(model[i][j] * z);
}
terrain.push(row);
}
\$.publish('terrain-update',[terrain]);
}

return {
update : update,
updateZ : updateZ
};
})();

var TerrainView = (function(){

var renderer;
var scene;
var camera;
var mesh;

function init(container){

var \$container = \$(container);
var width = \$container.width();
var height = \$container.height();
var ratio = width / height;
var near = 1;
var far = 6000;
var fov = 45;

scene = new THREE.Scene();

camera = new THREE.PerspectiveCamera(fov, ratio, near, far);
camera.position.y = 400;

if(!Detector.webgl){
renderer = new THREE.CanvasRenderer();
}else{
renderer = new THREE.WebGLRenderer({
clearColor: 0xf1f1f1,
clearAlpha: 1,
antialias: true
});
}

renderer.setSize(width, height);

setupLights();

\$container.append(renderer.domElement);
}

function setupLights(){

var ambientLight = new THREE.AmbientLight(0xffffff, 0.9);

var mainLight = new THREE.SpotLight(0xffffff, 1.0);
mainLight.position.set(500, 500, 500);

var auxLight = new THREE.SpotLight(0xffffff, 1.0);
auxLight.position.set(-300, 500, -400);
}

function getTerrainMesh(model){

var modelWidth = model[0].length - 1;
var modelHeight = model.length - 1;

var segLength = getOptimalSegLength(modelWidth, modelHeight);

var height = (model.length - 1) * segLength;
var width = (model[0].length - 1) * segLength;

var mesh = new THREE.Mesh(
new THREE.PlaneGeometry(width, height, model.length - 1, model.length - 1),
new THREE.MeshLambertMaterial({
color: 0xbb3355,
wireframe: true,
})
);
mesh.rotation.x = -Math.PI / 2;

var vertices = mesh.geometry.vertices;
for(var i = 0; i< model.length; ++i){
for(var j = 0; j < model.length; ++j){
vertices[i * model.length + j].position.z = model[i][j];
}
}
return mesh;
}

function getOptimalSegLength(width, height){
return ~~(640 / Math.max(width, height));
}

function drawCoordinate(center, length){

var orthogonal = [
[new THREE.Vector3(length, 0, 0), 0xff0000],
[new THREE.Vector3(0, length, 0), 0x00ff00],
[new THREE.Vector3(0, 0, length), 0x0000ff]
];

for(var i = 0; i< orthogonal.length; ++i){
var v = orthogonal[i][0];
color = orthogonal[i][1];

var geometry = new THREE.Geometry();

geometry.vertices.push(new THREE.Vertex(center));

var line = new THREE.Line(
geometry,

new THREE.LineBasicMaterial({
color: color,
opacity: 1,
linewidth: 3
})
);

}
}

function getTexture(model, width, height){

var modelWidth = model[0].length - 1;
var modelHeight = model.length;

var ratio = width / modelWidth;

var canvas = document.createElement('canvas');
canvas.width = width;
canvas.height = height;

var context = canvas.getContext('2d');

var imageData = context.getImageData(0, 0, width, height);
var pixels = imageData.data;
var i = 0;
var xx = 0;
var yy = 0;
var rgba;
for(var y = 0; y < height; ++y){
for(var x = 0; x < width; ++x){
yy = ~~(y / ratio);
xx = ~~(x / ratio);
rgba = elevation2RGBA(modelp[yy][xx]);
pixels[i++] = rgba[0];
pixels[i++] = rgba[1];
pixels[i++] = rgba[2];
pixels[i++] = rgba[3];
}
}
context.putImageData(imageData, 0, 0);

texture = new THREE.Texture(
canvas,
new THREE.UVMapping(),
THREE.ClampToEdgeWrapping,
THREE.ClampToEdgeWrapping
);
texture.needsUpdate = true;
return texture;
}

function elevation2RGBA(elevation) {
if (elevation > 0.5) {
return [255, 255, 255, 255];
} else if (elevation > 0){
return [104, 53, 20, 255];
} else {
return [58, 131, 21, 255];
}
}

function update(evt, model){
scene.remove(mesh);
mesh = getTerrainMesh(model);
}

function animate (interval) {
var timer = new Date().getTime() * 0.0001;
camera.position.x = Math.cos(timer) * 800;
camera.position.z = Math.sin(timer) * 800;
camera.lookAt(scene.position);

requestAnimationFrame(animate, interval);
renderer.render(scene, camera);
}

return {
init			: init,
update 			: update,
animate     	: animate,
drawCoordinate  : drawCoordinate
};
})();

var TerrainController = (function(){

var view = TerrainView;
var model = TerrainModel;

function init () {
RandomPool.hook();

initUI();
animate();
bindEvents();

update();
}

function initUI(){
view.init('#container');
}

function  animate () {
view.animate(30);
}

function bindEvents(){
\$.subscribe('terrain-update', view.update);
}

function reset(){
RandomPool.reset();
update();
}

function  update () {
RandomPool.seek(0);
var opts  = {
size : 64,
smoothness : 1.0,
zScale : 220
};
model.update(opts);
}

function updateZ(){
var zScale = 220;
model.updateZ(zScale);
}

return { init : init };
})();```