
// FractalMesh.java
// Andrew Davison, April 2005, ad@fivedots.coe.psu.ac.th

/* Generuje fraktální síť pro krajinu.

  Tato síť má svůj střed v bodu (0,0) na rovině XZ a 
  rozpíná se do vzdálenosti WORLD_LEN/2.
  Y-ová souřadnice reprezentuje výšku krajiny.

  Síť je uložena jako 2D-pole, kde jsou z-ové souřadnice uloženy jako
  řádky a x-ové jako sloupce. mesh[0][0] uchovává levý zadní bod sítě,
  který odpovídá záporné hodnotě souřadnic z a x.

  Počet bodů v síti, který určuje konstanta WORLD_LEN, je definován
  jako 2^x. Metoda divideMesh() se volá x-krát, takže výsledná síť
  obsahuje buňky se stranami o velikost 1 dílek.

  Síť generujeme pomocí algoritmu podobného, jako je popsán zde:
     "Fractal Terrain Generation -  Midmoint Displacement"
     od Jasona Shankela, část 4.18, strana 503-507
     V knize 'Game Programming Gems', Mark DeLoura
     Charles River Media, 2000


  ------
  Rada od Toma Egana: nahradit volání metody Math.random() metodou
  Random.nextDouble(), čímž by pro daný koeficient plochosti 
  došlo k vygenerování naprosto stejné krajiny. 

  Nezbytné změny jsou v kódu deaktivovány komentáři a vysvětleny 
  v kapitole 26.
*/

import java.io.*;
import java.util.Random;

import javax.vecmath.*;
import java.text.DecimalFormat;


public class FractalMesh
{
  private static final int WORLD_LEN = 64;
  /* Hotnota konstanta WORLD_LEN by měla být mocninou 2,
     protože ji budeme opakovaně dělit dvěma, dokud se
     nedostaneme na buňku sítě velikosti 1.*/

  // rozsah výšek je v rozmezí 10 dílků
  private final static double MIN_HEIGHT = -2.0;
  private final static double MAX_HEIGHT = 8.0;


  private Point3d mesh[][];    // uchovává body (x,y,z) sítě
  private DecimalFormat df;    // pro výstup údajů o síti

  private double flatness;
  /* Hodnota použitá pro snížení hodnoty proměnné dHeight při
     každém rekursivním volání metody divideMesh(). Větší hodnoty
     způsobí hladší povrch. menší více chaotický
  */

  private Random rnd;   // pro generování náhodných čísel


  public FractalMesh(double flat)
  {
    flatness = flat;
    mesh = new Point3d[WORLD_LEN+1][WORLD_LEN+1];
    df = new DecimalFormat("0.##");  // 2 dm
    rnd = new Random(1L);       // pevně dané semínko
    makeMesh();
  } // konec metody: FractalMesh()


  private void makeMesh()
  /* Inicializuje 4 rohy sítě náhodnými výškami v rámci
     rozmezí MIN a MAX. Poté začne rekursivně generovat 
     středové body voláním metody divideMesh(). */
  {
    System.out.println("Sestavuji krajinu ... strpení prosím");
    mesh[0][0] =    // zadní levý
      new Point3d( -WORLD_LEN/2, randomHeight(), -WORLD_LEN/2 );

    mesh[0][WORLD_LEN] =    // zadní pravý
      new Point3d( WORLD_LEN/2, randomHeight(), -WORLD_LEN/2 );

    mesh[WORLD_LEN][0] =    // přední levý
      new Point3d( -WORLD_LEN/2, randomHeight(), WORLD_LEN/2 );

    mesh[WORLD_LEN][WORLD_LEN] =    // přední pravý
      new Point3d( WORLD_LEN/2, randomHeight(), WORLD_LEN/2 );

    divideMesh( (MAX_HEIGHT-MIN_HEIGHT)/flatness, WORLD_LEN/2);

  } // konec metody: makeMesh()


  private double randomHeight()
  // mezi MIN_HEIGHT a MAX_HEIGHT
  {  return (Math.random()*(MAX_HEIGHT-MIN_HEIGHT) + MIN_HEIGHT);  
     // return (rnd.nextDouble()*(MAX_HEIGHT-MIN_HEIGHT) + MIN_HEIGHT);
              // pro opravu náhodných hodnot
  }


  private void divideMesh(double dHeight, int stepSize)
  /* V každém kroku musíme ještě před čtvercovým krokem pro celou síť 
     provést krok kosočtvercový. */
  {
    int xPt, zPt;
    if (stepSize >= 1) {   // zastav rekurzi jakmile stepSize je < 1

      // kosočtvercový krok pro všechny středové body na této úrovni
      zPt = stepSize;
      while (zPt < WORLD_LEN+1) {
        xPt = stepSize;
        while (xPt < WORLD_LEN+1) {
           mesh[zPt][xPt] = getDiamond(zPt, xPt, dHeight, stepSize);
           xPt += (stepSize*2);
        }
        zPt += (stepSize*2);
      }

      // čtvercový krok pro všechny okolní body
      zPt = stepSize;
      while (zPt < WORLD_LEN+1) {
        mesh[zPt][0] = getSquare(zPt, 0, dHeight, stepSize);  // velý sloupec
        xPt = stepSize;
        while (xPt < WORLD_LEN+1) {
           getSquares(zPt, xPt, dHeight, stepSize);  // zadní a pravé buňky
           xPt += (stepSize*2);
        }
        zPt += (stepSize*2);
      }

      xPt = stepSize;
      while (xPt < WORLD_LEN+1) {
        mesh[WORLD_LEN][xPt] = 
          getSquare(WORLD_LEN, xPt, dHeight, stepSize);  // přední řádek
        xPt += (stepSize*2);
      }

      divideMesh(dHeight/flatness, stepSize/2);
    }
  }  // konec metody: divideMesh()


  private void getSquares(int z, int x, double dHeight, int stepSize)
  {
    mesh[cCoord(z-stepSize)][x] =    // zadní
           getSquare(cCoord(z-stepSize), x, dHeight, stepSize);

    mesh[z][cCoord(x+stepSize)] =    // pravý
           getSquare(z, cCoord(x+stepSize), dHeight, stepSize);
  } // konec metody: getSquares()
  


  private Point3d getDiamond(int z, int x, double dHeight, int stepSize)
  {
    // System.out.println("getDiamond: " + z + ", " + x + " /" + stepSize);
    Point3d leftBack = mesh[cCoord(z-stepSize)][cCoord(x-stepSize)];
    Point3d rightBack = mesh[cCoord(z-stepSize)][cCoord(x+stepSize)];
    Point3d leftFront = mesh[cCoord(z+stepSize)][cCoord(x-stepSize)];
    Point3d rightFront = mesh[cCoord(z+stepSize)][cCoord(x+stepSize)];
    double height =
         calcHeight(leftBack, rightBack, leftFront, rightFront, dHeight);
    double xWorld = x - (WORLD_LEN/2);
    double zWorld = z - (WORLD_LEN/2);

    return new Point3d(xWorld, height, zWorld);
  } // konec metody: getDiamond()


  private Point3d getSquare(int z, int x, double dHeight, int stepSize)
  {
    // System.out.println("getSquare: " + z + ", " + x + " /" + stepSize);
    Point3d back = mesh[cCoord(z-stepSize)][x];
    Point3d front = mesh[cCoord(z+stepSize)][x];
    Point3d left = mesh[z][cCoord(x-stepSize)];
    Point3d right = mesh[z][cCoord(x+stepSize)];
    double height = calcHeight(back, front, left, right, dHeight);
    double xWorld = x - (WORLD_LEN/2);
    double zWorld = z - (WORLD_LEN/2);

    return new Point3d(xWorld, height, zWorld);
  } // konec metody: getSquare()
  

  private int cCoord(int coordIdx)
  /* Je-li index souřadnice menší než 0, větší než WORLD_LEN
     pak použij  souřadnici na opačné straně hrany sítě.
  */
  {
    if (coordIdx < 0)
      return WORLD_LEN + coordIdx;
    else if (coordIdx > WORLD_LEN)
      return coordIdx - WORLD_LEN;
    else
      return coordIdx;
  } // konec metody: cCoord()


  private double calcHeight(Point3d back, Point3d front,
                       Point3d left, Point3d right, double dHeight)
  /* Je-li vypočtená výška < MIN_HEIGHT, nastav ji na MIN_HEIGHT.
     Je-li na druhou stranu > MAX_HEIGHT, nastav ji na modulo MAX_HEIGHT.
  */
  {
    double height = (back.y + front.y + left.y + right.y)/4.0f +
											   randomRange(dHeight);
    if (height < MIN_HEIGHT)
      height = MIN_HEIGHT;
    else if (height > MAX_HEIGHT)
      height = height%MAX_HEIGHT;
    return height;
  }  // konec metody: calcHeight()


  private double randomRange(double h)
  // mezi -h a h
  {  return ((Math.random() * 2 * h) - h);  
     // return ((rnd.nextDouble() * 2 * h) - h);   // na opravu náhodné hodnoty
  }



  public Point3d[] getVertices()
  /* Vrátí síť jako pole vrcholů. Každá skupina 4 bodů se použije 
     k vytvoření objektu typu TexturedPlane.

     Body setřídíme tak, aby byla rovina specifikována proti směru hodinových
     ručiček, což je důležité při jejím potažení texturou.
  */
  { int numVerts = WORLD_LEN*WORLD_LEN*4;
    Point3d vertices[] = new Point3d[numVerts];
    
    int vPos = 0;
    for(int z=0; z<WORLD_LEN; z++) {
      for(int x=0; x<WORLD_LEN; x++) {
        vertices[vPos++] = mesh[z+1][x];     // tvorba proti směru hodinových ručiček
        vertices[vPos++] = mesh[z+1][x+1];   // od levého spodního bodu
        vertices[vPos++] = mesh[z][x+1];
        vertices[vPos++] = mesh[z][x];
      }
    }
    return vertices;
  }  // konec metody: getVertices



  // ---------------------- ladění ------------------


  public void printMesh(int axis)
  // osové hodnoty: x=0, y=1, z=2
  {
    File f = new File("mesh.txt");
    PrintWriter pw = null;
    try {
      pw = new PrintWriter(new FileWriter(f),true);

      if (axis == 0)
        pw.println("---------- x-ové souřadnice světa ------------");
      else if (axis == 1)
        pw.println("---------- y-ové souřadnice světa ------------");
      else 
        pw.println("---------- z-ové souřadnice světa ------------");

      for(int z=0; z<WORLD_LEN+1; z++) {
        for(int x=0; x<WORLD_LEN+1; x++)
          if (axis == 0)
            pw.print( df.format(mesh[z][x].x) + " ");
          else if (axis == 1)
            pw.print( df.format(mesh[z][x].y) + " ");
          else
           pw.print( df.format(mesh[z][x].z) + " ");
        pw.println();
      }
      pw.println("--------------------------------------");

      System.out.println("Síť byla zapsána do souboru mesh.txt");
    }
    catch(Exception e)
    {  System.out.println("Nemohu zapsat síť do souboru mesh.txt");  }
  }  // konec metody: printMesh()


}  // konec třídy: FractalMesh