terrain/terraHeightGen/main.cpp

Go to the documentation of this file.

/*
 * main.cpp
 *
 * Copyright (C) 2009,2010  Thomas A. Vaughan
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

// includes --------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <math.h>

#include "common/wave_ex.h"
#include "datahash/datahash_text.h"
#include "datahash/datahash_util.h"
#include "geometry/geometry_2d.h"
#include "geometry/geometry_3d.h"
#include "geometry/xform_2d.h"
#include "perf/perf.h"
#include "pgmppm/pgmppm.h"              // PGM/PPM files
#include "util/date.h"
#include "util/file.h"


// statics and typedefs --------------------------------------------------------

static const int s_minGrid              = 2;

static const char * s_hfieldVersion     = "0.1";

static const int s_yIntExtent           = 255;


// fixed points
typedef std::vector<point3d_t> vec_points_t;

typedef point2d_t<float> point_t;
typedef rect2d_t<float> rect_t;



// heightfield data used
struct hdata_t {
        // constructor, manipulators
        hdata_t(void) throw() : yData(NULL) { this->clear(); }
        ~hdata_t(void) throw() { this->clear(); }
        void clear(void) throw() {
                        xGrid = zGrid = 0;
                        nFloats = 0;
                        xzScale = 0;
                        yScale = -1;
                        yMin = yMax = 0;
                        fixedPoints.clear();
                        if (yData) {
                                delete[] yData;
                                yData = NULL;
                        }
                }

        void allocate(void) {
                        ASSERT(!yData, "Already allocated?");
                        nFloats = (xGrid + 1) * (zGrid + 1);
                        DPRINTF("Allocating grid of %d floats total",
                            nFloats);
                        yData = new float[nFloats];
                        ASSERT_THROW(yData, "out of memory");
                }

        void setHeightInt(IN int x, IN int z, IN float y) {
                        ASSERT(yData, "need to allocate");
                        int idx = getIndex(x, z);
                        yData[idx] = y;
                }

        void setHeightFloat(IN float x, IN float z, IN float y) {
                        int ix = (int)((x / xzScale) + 0.5);
                        int iz = (int)((z / xzScale) + 0.5);
                        //DPRINTF("  ix,iz = (%d, %d)", ix, iz);
                        setHeightInt(ix, iz, y);
                }

        float getHeightInt(IN int x, IN int z) const {
                        ASSERT(yData, "need to allocate");
                        int idx = getIndex(x, z);
                        return yData[idx];
                }

        int getIndex(IN int x, IN int z) const {
                        ASSERT(x >= 0 && x <= xGrid, "bad x: %d", x);
                        ASSERT(z >= 0 && z <= zGrid, "bad z: %d", z);
                        return (z * (xGrid + 1)) + x;
                }

        float getYScale(void) const throw() {
                        return yScale;
                }

        float getXZScale(void) const throw() {
                        return xzScale;
                }

        // data fields
        int             xGrid;          // grid point width in x-direction
        int             zGrid;
        int             nFloats;
        float           xzScale;        // distance between adjacent points
        float           yScale;
        float           yMin;
        float           yMax; 
        float *         yData;          // the actual y-Data at each x,z value
        vec_points_t    fixedPoints;
        vec_points_t    seedPoints;
};




static float
randX
(
IN float max
)
throw()
{
        // given max, returns a random number between -max and +max
        static const float s_invMax = 1.0 / RAND_MAX;
        return 2.0 * (rand() * s_invMax - 0.5) * max;
}



static float
randMid
(
IN float min,
IN float max
)
throw()
{
        // return a random point close to the middle of the min/max
        float W = max - min;
        float avg = 0.5 * (min + max);

        return avg + randX(0.3 * W);    
}



static void
parsePoints
(
IN hdata_t * hdata,
IN const Datahash * input,
IN const char * name,
IN float yMax,
OUT vec_points_t& vec
)
{
        ASSERT(hdata, "null");
        ASSERT(input, "null");
        ASSERT(name, "null");
        vec.clear();

        // any there?
        if (!input->count(name)) {
                return;         // nope
        }

        // determine some values
        float xMax = hdata->xGrid * hdata->xzScale;
        float zMax = hdata->zGrid * hdata->xzScale;

        Datahash::iterator_t i;
        input->getIterator(name, i);
        while (const hash_value_t * phv = input->getNextElementUnsafe(i)) {
                if (phv->hash)
                        continue;       // skip complex values
                const char * val = phv->text.c_str();

                point3d_t fp;
                parsePoint3d(val, fp);
                fp.dump(name);

                // x,z coordinates should be 0-1
                ASSERT_THROW(fp.x >= 0 && fp.x <= 1, "Bad x: " << fp.x);
                ASSERT_THROW(fp.z >= 0 && fp.z <= 1, "Bad z: " << fp.z);

                // okay, now scale the x,z coordinates
                fp.x *= xMax;
                fp.z *= zMax;
                fp.y *= yMax;

                vec.push_back(fp);
        }
        DPRINTF("Parsed %d points of name '%s'", (int) vec.size(), name);
}



static void
overlayPoints
(
IN hdata_t * hdata,
IN vec_points_t& vec
)
{
        perf::Timer timer("overlayFixed");
        ASSERT(hdata, "null");

        // run through all points
        for (vec_points_t::const_iterator i = vec.begin(); i != vec.end();
             ++i) {
                const point3d_t& fp = *i;

        //      fp.dump("Setting this now...");
                hdata->setHeightFloat(fp.x, fp.z, fp.y);
        }
}



static void
calculateYScale
(
IN hdata_t * hdata
)
{
        ASSERT(hdata, "null");
        ASSERT(hdata->yData, "should have allocated by now");
        ASSERT(hdata->nFloats > 0, "no data?");

        float yMin = hdata->yData[0];
        float yMax = yMin;

        for (int i = 1; i < hdata->nFloats; ++i) {
                float y = hdata->yData[i];
                if (y < yMin) {
                        yMin = y;
                } else if (y > yMax) {
                        yMax = y;
                }
        }

        DPRINTF("Calculated (ymin,ymax) = (%f, %f)", yMin, yMax);
        float dY = yMax - yMin;
        if (dY <= 0.0) {
                hdata->yScale = 1.0;
        } else {
                hdata->yScale = dY / s_yIntExtent;
        }
        DPRINTF("  Calculated yScale: %f", hdata->getYScale());
        hdata->yMin = yMin;
        hdata->yMax = yMax;
}



static void
generateFlat
(
IN hdata_t * hdata,
IN const Datahash * algo
)
{
        ASSERT(hdata, "null");
        ASSERT(algo, "null");

        // get the flat y-value to use
        float y = getFloat(algo, "y");
        DPRINTF("Flat algorithm is using base y-value: %f", y);

        // set all grid points to flat y value
        int xGrid = hdata->xGrid;
        int zGrid = hdata->zGrid;
        for (int i = 0; i <= xGrid; ++i) {
                for (int j = 0; j <= zGrid; ++j) {
                        hdata->setHeightInt(i, j, y);
                }
        }
}



static void
iterateFractal
(
IN hdata_t * hdata,
IN int dx,
IN float dy
)
{
        ASSERT(hdata, "null");
        ASSERT(dx > 0, "bad dx: %d", dx);
        ASSERT(dy > 0, "bad dy: %f", dy);

        int W = hdata->xGrid;

        // first loop: go in Z-rows, add X midpoints
        int mid = dx / 2;
        for (int z = 0; z <= W; z += dx) {
                for (int x = mid; x <= W; x += dx) {
                        float y0 = hdata->getHeightInt(x - mid, z);
                        float y1 = hdata->getHeightInt(x + mid, z);
//                      float y = hdata->getHeightInt(x, z);
                //      float avg = y0 + y1 + randX(dy) + 2 * y;
                        float avg = y0 + y1 + randX(dy);
                        hdata->setHeightInt(x, z, 0.5 * avg);
                }
        }

        // second loop: go in X-rows, add Z midpoints
        for (int x = 0; x <= W; x += dx) {
                for (int z = mid; z <= W; z += dx) {
                        float y0 = hdata->getHeightInt(x, z - mid);
                        float y1 = hdata->getHeightInt(x, z + mid);
//                      float y = hdata->getHeightInt(x, z);

                        //float avg = y0 + y1 + randX(dy) + 2 * y;
                        float avg = y0 + y1 + randX(dy);
                        hdata->setHeightInt(x, z, 0.5 * avg);
                }
        }

        // third loop: go in middle of both
        for (int x = mid; x <= W; x += dx) {
                for (int z = mid; z <= W; z += dx) {
                        float y0 = hdata->getHeightInt(x, z - mid);
                        float y1 = hdata->getHeightInt(x, z + mid);
                        float y2 = hdata->getHeightInt(x - mid, z);
                        float y3 = hdata->getHeightInt(x + mid, z);
                        //float y = hdata->getHeightInt(x, z);
//                      DPRINTF("y = %f", y);
                //      float avg = y0 + y1 + y2 + y3 + 2 * randX(dy) + 4 * y;
                        float avg = y0 + y1 + y2 + y3;
                        hdata->setHeightInt(x, z, 0.25 * avg);
                }
        }
}



static void
generateFractal
(
IN hdata_t * hdata,
IN const Datahash * algo
)
{
        ASSERT(hdata, "null");
        ASSERT(algo, "null");

        // has to be square!
        ASSERT_THROW(hdata->xGrid == hdata->zGrid,
            "Has to be a square grid!");
        int W = hdata->xGrid;

        // get important factors
        float dy = getFloat(algo, "dy");
        ASSERT_THROW(dy >= 0, "Bad dy: " << dy);

        float reduce = getFloat(algo, "reduce");
        ASSERT_THROW(reduce >=0 && reduce <= 1,
            "Bad reduce: " << reduce);

        // get seed points
        vec_points_t seeds;
        parsePoints(hdata, algo, "seed", dy, seeds);

        // overlay the fixed points
        overlayPoints(hdata, seeds);

        // how many iterations?
        int nIter = (int)((log(W) / log(2)) + 0.5);
        DPRINTF("W=%d --> %d iterations", W, nIter);

        int dx = W;
        while (dx > 1) {
                // okay, do this iteration!
                iterateFractal(hdata, dx, dy);
                dx /= 2;
                dy *= reduce;
        }
}



static void
getTransform
(
IN float X,
IN float Z,
OUT xform_2d_t& T
)
{
        // NOTE: R can be negative!
        T.clear();

        // get origin
        float x = randMid(0, 1) * X;
        float z = randMid(0, 1) * Z;

        xform_2d_t trans;
        trans.setTranslate(-x, -z);

        // now get rotation angle
        float angle = randX(M_PI);
        xform_2d_t rotate;
        rotate.setZRotate(angle);

        T.setToProductOf(rotate, trans);
}



static void
addSplit
(
IN hdata_t * hdata,
IN const xform_2d_t& T,
IN float dy
)
throw()
{
        ASSERT(hdata, "NULL");
        ASSERT(dy > 0, "Bad dy");

        float xzScale = hdata->xzScale;
        int isign = 1 - 2 * (rand() % 2);

        // now walk through all points and adjust based on split 
        for (int ix = 0; ix <= hdata->xGrid; ++ix) {
                float x = ix * xzScale;
                for (int iz = 0; iz <= hdata->zGrid; ++iz)  {
                        float z = iz * xzScale;

                        point_t p(x, z);
                        point_t q;
                        T.transformPoint(p, q);
        //              DPRINTF("(%f, %f) --> (%f, %f)", p.x, p.y, q.x, q.y);
                        float y = hdata->getHeightInt(ix, iz);
                        if (q.y < 0) {
                                hdata->setHeightInt(ix, iz, y + isign * dy);
                        } else {
                                hdata->setHeightInt(ix, iz, y - isign * dy);
                        }
                }
        }
}



static void
generateSplit
(
IN hdata_t * hdata,
IN const Datahash * algo
)
{
        ASSERT(hdata, "null");
        ASSERT(algo, "null");

        float dy = getFloat(algo, "dy");
        ASSERT_THROW(dy > 0, "Bad splitting dy: " << dy);

        float nIter = getInt(algo, "nIter");
        ASSERT_THROW(nIter > 0, "Bad split iteration count: " << nIter);

        // get other parameters
        float xzScale = hdata->xzScale;
        float W = hdata->xGrid * xzScale;
        float L = hdata->zGrid * xzScale;

        // now walk through iterations
        int splitsPerIteration = 1;
        for (int n = 0; n < nIter; ++n) {
                for (int i = 0; i < splitsPerIteration; ++i) {
                        xform_2d_t T;
                        getTransform(W, L, T);
                        addSplit(hdata, T, dy);
                }
                splitsPerIteration *= 2;
                dy /= 2;
        }
}



static smart_ptr<hdata_t>
createHeightfield
(
IN Datahash * input
)
{
        ASSERT(input, "null");

        smart_ptr<hdata_t> hdata = new hdata_t;
        ASSERT_THROW(hdata, "out of memory");

        // pull out x,z grid values
        hdata->xGrid = getInt(input, "xGrid");
        hdata->zGrid = getInt(input, "zGrid");
        DPRINTF("Heightfield grid extent is %dx%d", hdata->xGrid, hdata->zGrid);
        DPRINTF("  (This means we store a %dx%d grid)",
            hdata->xGrid + 1, hdata->zGrid + 1);
        ASSERT_THROW(hdata->xGrid >= s_minGrid,
            "xGrid is too small: " << hdata->xGrid << " vs. " << s_minGrid);
        ASSERT_THROW(hdata->zGrid >= s_minGrid,
            "zGrid is too small: " << hdata->zGrid << " vs. " << s_minGrid);

        // pull out scaling factor
        hdata->xzScale = getFloat(input, "xzScale");
        ASSERT_THROW(hdata->xzScale > 0.0,
            "Bad xzScale: " << hdata->xzScale);

        // allocate memory
        hdata->allocate();

        // iterate algorithms
        Datahash::iterator_t i;
        input->getIterator("algorithm", i);
        std::string key;
        hash_value_t hv;
        while (input->getNextElement(i, key, hv)) {
                if (!hv.hash)
                        continue;       // skip simple elements
                const Datahash * algo = hv.hash;
                ASSERT(algo, "null");
                const char * type = getString(algo, "type");
                DPRINTF("Terrain generation algorithm: %s", type);
                std::string timerName = "algorithm timer (type=";
                timerName += type;
                timerName += ")";
                {
                        perf::Timer timer(timerName.c_str());
                        if (!strcmp("flat", type)) {
                                generateFlat(hdata, algo);
                        } else if (!strcmp("fractal", type)) {
                                generateFractal(hdata, algo);
                        } else if (!strcmp("split", type)) {
                                generateSplit(hdata, algo);
                        } else {
                                ASSERT_THROW(false,
                                    "Unknown terrain generation algorithm "
                                    "type: '" << type << "'");
                        }
                }
        }

        // all done!
        return hdata;
}



static smart_ptr<hdata_t>
createHeightfield
(
IN const char * inputFile
)
{
        ASSERT(inputFile, "null");

        smart_ptr<Datahash> input = readHashFromTextFile(inputFile);
        ASSERT_THROW(input, "failed to create input hash from file: "
            << inputFile);

        smart_ptr<hdata_t> hdata = createHeightfield(input);
        ASSERT_THROW(hdata, "Failed to create heightfield data?");

        // now calculate yScale
        calculateYScale(hdata);
        ASSERT(hdata->getYScale() > 0,
            "Should have calculated proper y-scale by now");

        return hdata;
}



static int
writePgmPixel
(
IN void * context,
IN int x,
IN int z
)
{
        hdata_t * hdata = (hdata_t *) context;
        ASSERT(hdata, "null context?");

        int idx = hdata->getIndex(x, z);
        ASSERT(idx >= 0 && idx < hdata->nFloats, "Bad index: %d", idx);

        float y = hdata->yData[idx];
        float dy = y - hdata->yMin;
        int iy = int((dy / hdata->getYScale()) + 0.5);
//      DPRINTF(" h(%d,%d) = %f --> dy = %f --> %d", x, z, y, dy, iy);
        return iy;
}



static void
writeHeightfield
(
IN const hdata_t * hdata,
IN const char * outputName
)
{
        perf::Timer timer("writeHeightfield");
        ASSERT(hdata, "null");
        ASSERT(outputName, "null");

        std::string hfieldFilename = outputName;
        hfieldFilename += ".hfield";

        std::string pgmFilename = outputName;
        pgmFilename += ".pgm";

        std::string date;
        getDisplayableDateFromNetTime(time(NULL), date);

        DPRINTF("Writing heightfield metadata to file: %s",
            hfieldFilename.c_str());

        std::ofstream output(hfieldFilename.c_str());
        ASSERT_THROW(output.good(), "Failed to open file for writing: "
            << hfieldFilename);
        output << "#\n";
        output << "# " << hfieldFilename << "\n";
        output << "#\n";
        output << "# This is an auto-generated hfield file.\n";
        output << "#\n";
        output << "# Generated: " << date << "\n";
        output << "#\n";
        output << "\n";
        output << "hfieldVersion\t" << s_hfieldVersion << "\n";
        output << "heightfield {\n";
        output << "\tyScale\t" << hdata->getYScale() << "\t# meters per y-tick\n";
        output << "\txzScale\t" << hdata->getXZScale() << "\t# meters per grid point\n";
        output << "\n";
        output << "\t# relative paths to heightfield and texture files\n";
        output << "\thfieldFile\t" << pgmFilename << "\n";
        output << "\ttextureFile\t" << outputName << ".ppm\n";
        output << "}\n";

        // okay, now write output PGM file
        std::ofstream pgmOut(pgmFilename.c_str());
        ASSERT_THROW(pgmOut.good(), "Failed to open file for writing: "
            << pgmFilename);
        pgmppm::writePgm(pgmOut, hdata->xGrid + 1, hdata->zGrid + 1,
            255, writePgmPixel, (void *) hdata);
}



//
//      entry point
//

int
main
(
IN int argc,
IN const char * argv[]
)
{
        ASSERT(3 == argc, "usage: terraHeightGen <input-file> <output-name>");
        const char * inputFile = argv[1];
        const char * outputName = argv[2];

        // start everything up
        int retval = 0;
        try {
                perf::Timer timer("overall program timer");
                srand(time(NULL));
                smart_ptr<hdata_t> hdata = createHeightfield(inputFile);
                ASSERT(hdata, "null");
                writeHeightfield(hdata, outputName);
        } catch (std::exception& e) {
                DPRINTF("Exception during startup!");
                DPRINTF("%s", e.what());
                retval = 1;
        } catch (...) {
                DPRINTF("Unknown exception during startup!");
                retval = 2;
        }

        perf::dumpTimingSummary(std::cerr);

        return retval;
}