吉吉于

分形地形算法

好久没写东西,这个算法是去年就看到别人有用THREE.JS写过,自己也玩一下。

关于分形地形请参考这篇文章:http://gameprogrammer.com/fractal.html

在线演示

(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);

		renderer.shadowCameraNear = 3;
		renderer.shadowCameraFar = camera.far;
		renderer.shadowCameraFov = 50;

		renderer.shadowMapBias = 0.0039;
		renderer.shadowMapDarkness = 0.5;

		renderer.shadowMapEnabled = true;
		renderer.shadowMapSoft = true;

		setupLights();

		$container.append(renderer.domElement);
	}

	function setupLights(){

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

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

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

	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;
		mesh.castShadow = true;
		mesh.receiveShadow = true;

		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));
			geometry.vertices.push(new THREE.Vertex(center.clone().addSelf(v)));

			var line = new THREE.Line(
				geometry,

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

			scene.add(line);
		}
	}

	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);
    	scene.add(mesh);
    }

    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 };
})();

 

转载请注明:于哲的博客 » 分形地形算法