prototypes/screenCompress/landscape.cpp

/*
 * Modification History
 *
 * 2006-September-26   Jason Rohrer
 * Switched to cosine interpolation.
 * Added optimizations discovered with profiler.  Reduced running time by 18%.
 */


#include "landscape.h"

#include <math.h>
#include <stdlib.h>

#include "minorGems/util/SimpleVector.h"


double landscape( double inX, double inY, double inT,
                  double inBaseFrequency, double inRoughness,
                  int inDetail ) {

    if( inDetail < 0 ) {
        return 0.0;
        }
    else {
        // frequency of octave
        double frequency = inBaseFrequency * pow( 2, inDetail );
        double amplitude = pow( inRoughness, inDetail );
        return amplitude * noise4d( inX * frequency,
                                    inY * frequency,
                                    // index different planes of noise
                                    inDetail,
                                    inT )
            + landscape( inX, inY, inT, inBaseFrequency, inRoughness,
                         inDetail - 1 );
        }
    }


double variableRoughnessLandscape( double inX, double inY, double inT,
                                   double inBaseFrequency,
                                   double inRoughnessChangeFrequency,
                                   double inMinRoughness,
                                   double inMaxRoughness,
                                   int inDetail ) {

    double roughnessFreqX = inX * inRoughnessChangeFrequency;
    double roughnessFreqY = inY * inRoughnessChangeFrequency;

    // use low-frequency noise 4d to select landscape roughness
    // between 0 and 1
    double roughness =
        ( noise4d( 6, roughnessFreqX, roughnessFreqY, inT ) + 1 ) / 2;

    // move roughness into specified range
    roughness =
        roughness * ( inMaxRoughness - inMinRoughness ) +
        inMinRoughness;

    return landscape( inX, inY, inT, inBaseFrequency, roughness, inDetail );
    }


int getRandomPoints( double inStartX, double inEndX,
                     double inStartY, double inEndY,
                     double inT,
                     double inSampleStepSize,
                     double inDensity,
                     double **outXCoordinates,
                     double **outYCoordinates ) {

    SimpleVector<double> *xCoordinates = new SimpleVector<double>();
    SimpleVector<double> *yCoordinates = new SimpleVector<double>();

    // discretize startX and start Y so that sample grid for differently-placed
    // windows always meshes
    // use ceil to ensure that starting points are always inside the
    // inStart/inEnd bounds
    double discretizedStartX =
        inSampleStepSize * ceil( inStartX / inSampleStepSize );
    double discretizedStartY =
        inSampleStepSize * ceil( inStartY / inSampleStepSize );

    // put a point wherever we have a zero-crossing
    double lastSample = 1;

    for( double x=discretizedStartX; x<=inEndX; x+=inSampleStepSize ) {
        for( double y=discretizedStartY; y<=inEndY; y+=inSampleStepSize ) {
            double landscapeSample =
                variableRoughnessLandscape(
                    30 * x + 1000, 30 * y + 1000, inT + 1000,
                    0.01, 0.001, 0.25, 0.65, 0 );

            // shift landscape up to reduce chance of zero-crossing
            landscapeSample = (1-inDensity) * 0.5 + 0.5 + landscapeSample ;

            if( landscapeSample < 0 &&
                lastSample >= 0 ||
                landscapeSample >= 0 &&
                landscapeSample < 0 ) {

                // sign change

                // hit
                xCoordinates->push_back( x );
                yCoordinates->push_back( y );
                }

            lastSample = landscapeSample;
            }
        }

    *outXCoordinates = xCoordinates->getElementArray();
    *outYCoordinates = yCoordinates->getElementArray();

    int numPoints = xCoordinates->size();

    delete xCoordinates;
    delete yCoordinates;

    return numPoints;
    }


/**
 * Computes a 32-bit random number.
 * Use linear congruential method.
 *
 * @param inSeed the seed to use.
 */
// this is the readable version of the funcion
// it has been turned into a set of macros below
inline unsigned long random32_readable( unsigned long inSeed ) {
    // this is the true hot-spot of the entire landscape function
    // thus, optimization is warranted.

    // multiplier = 3141592621
    // use hex to avoid warnings
    //unsigned long multiplier = 0xBB40E62D;
    //unsigned long increment = 1;

    // better:
    // unsigned long multiplier = 196314165
    // unsigned long increment  = 907633515

    // this will automatically be mod-ed by 2^32 because of the limit
    // of the unsigned long type
    // return multiplier * inSeed + increment;
    //return 0xBB40E62D * inSeed + 1;
    //return 196314165 * inSeed + 907633515;

    //int n = ( inSeed << 13 ) ^ inSeed;
    //return n * (n * n * 15731 + 789221) + 1376312589;

    //const unsigned long Num1 = (inSeed * 0xFEA09B9DLU) + 1;
	//const unsigned long Num2 = ((inSeed * 0xB89C8895LU) + 1) >> 16;
	//return Num1 ^ Num2;

    /*
    unsigned int rseed=(inSeed*15064013)^(inSeed*99991+604322121)^(inSeed*45120321)^(inSeed*5034121+13);

    const unsigned long Num1 = (inSeed * 0xFEA09B9DLU) + 1;

    const unsigned long Num2 = ((inSeed * 0xB89C8895LU) + 1) >> 16;

    rseed *= Num1 ^ Num2;

    return rseed;
    */

    const unsigned long Num1 = (inSeed * 0xFEA09B9DLU) + 1;
	const unsigned long Num2 = ((inSeed^Num1) * 0x9C129511LU) + 1;
	const unsigned long Num3 = (inSeed * 0x2512CFB8LU) + 1;
	const unsigned long Num4 = ((inSeed^Num3) * 0xB89C8895LU) + 1;
	const unsigned long Num5 = (inSeed * 0x6BF962C1LU) + 1;
	const unsigned long Num6 = ((inSeed^Num5) * 0x4BF962C1LU) + 1;

	return Num2 ^ (Num4 >> 11) ^ (Num6 >> 22);
    }


// faster as a set of macros
#define Num1( inSeed ) \
    ( ( inSeed * 0xFEA09B9DLU ) + 1 )

#define Num2( inSeed ) \
    ( ( ( inSeed ^ Num1( inSeed ) ) * 0x9C129511LU ) + 1 )

#define Num3( inSeed ) \
    ( ( inSeed * 0x2512CFB8LU ) + 1 )

#define Num4( inSeed ) \
    ( ( ( inSeed ^ Num3( inSeed ) ) * 0xB89C8895LU ) + 1 )

#define Num5( inSeed ) \
    ( ( inSeed * 0x6BF962C1LU ) + 1 )

#define Num6( inSeed ) \
    ( ( ( inSeed ^ Num5( inSeed ) ) * 0x4BF962C1LU ) + 1 )

#define random32( inSeed ) \
    ( Num2( inSeed ) ^ (Num4( inSeed ) >> 11) ^ (Num6( inSeed ) >> 22) )


#define invMaxIntAsDouble 2.32830643708e-10
// 1/(x/2) = 2*(1/x)
//double invHalfMaxIntAsDouble = 2 * invMaxIntAsDouble;
//  2.32830643708e-10
//+ 2.32830643708e-10
//-------------------
//  4.65661287416e-10
#define invHalfMaxIntAsDouble 4.65661287416e-10


#define mixFour( x, y, z, t ) ( x ^ (y * 57) ^ (z * 131) ^ (t * 2383) )


/**
 * Maps 4d integer coordinates into a [-1..1] noise space.
 *
 * @param x, y, z, t  the 4d coordinates.
 *
 * @return a random value in the range [-1..1]
 */
// keep readable version around for reference
// it has been replaced by a macro below
inline double noise4dInt32_readable( unsigned long x,
                                     unsigned long y,
                                     unsigned long z,
                                     unsigned long t ) {


    //double maxIntAsDouble = 4294967295.0;

    // modular addition automatic
    // multiply x, y, z, and t by distinct primes to
    // avoid correllations.
    // using xor ( ^ ) here seems to avoid correllations that show
    // up when using addition.

    // mix x, y, z, and t
    unsigned long randomSeed =
        x ^
        y * 57 ^
        z * 131 ^
        t * 2383;

    // a random value between 0 and max unsigned long
    unsigned long randomValue = random32( randomSeed );

    // a random value between 0 and 2
    double zeroTwoValue = randomValue * invHalfMaxIntAsDouble;

    // a random value between -1 and 1
    return zeroTwoValue - 1;
    }


// noise4dInt32 function call itself was the slowest spot in code
// (found with profiler)
// turn into a set of macros

// matches original parameter format
#define noise4dInt32( x, y, z, t ) \
    random32( mixFour( x, y, z, t ) ) \
    * invHalfMaxIntAsDouble - 1

// problem:  now that random32 is a macro, we are passing the unevaluated
// expression, ( x ^ (y * 57) ^ (z * 131) ^ (t * 2383) ), down into it.
// it is being evaluated 6 times within the depths of the random32 macro

// thus, we need to provide a new format where the caller can precompute
// the mix for us.  This is even faster.
#define noise1dInt32( precomputedMix ) \
    random32( precomputedMix ) \
    * invHalfMaxIntAsDouble - 1


/*
 * The following functions (blendNoiseNd) do 4d linear interpolation
 * one dimension at a time.
 *
 * The end result is 8 calls to blendNoise1d (and 16 calls to noise4dInt32).
 *
 * This method was inspired by the functional implementations---I am
 * decomposing a complicated problem into sub-problems that are easier
 * to solve.
 */


// faster than f * b + (1-f) * a
// one less multiply
#define linearInterpolation( t, a, b ) ( a + t * ( b - a ) )


/**
 * Blends 4d discrete (integer-parameter) noise function along one dimension
 * with 3 fixed integer parameters.
 */
inline double blendNoise1d( double x,
                     unsigned long y,
                     unsigned long z,
                     unsigned long t ) {

    double floorX = floor( x );
    unsigned long floorIntX = (unsigned long)floorX;

    if( floorX == x ) {
        unsigned long precomputedMix = mixFour( floorIntX, y, z, t );

        return noise1dInt32( precomputedMix );
        }
    else {
        unsigned long ceilIntX = floorIntX + 1;

        // cosine interpolation
        // from http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
        double ft = ( x - floorX ) * M_PI;
        double f = ( 1 - cos( ft ) ) * .5;


        // need to pre-store intermediate values because noise4dInt32 is a
        // macro
        // thus, we end up calling the noise1dInt32 function instead

        unsigned long precomputedMix = mixFour( floorIntX, y, z, t );
        double valueAtFloor = noise1dInt32( precomputedMix );

        precomputedMix = mixFour( ceilIntX, y, z, t );
        double valueAtCeiling = noise1dInt32( precomputedMix );

        return linearInterpolation( f, valueAtFloor, valueAtCeiling );
        }
    }


/**
 * Blends 4d discrete (integer-parameter) noise function along 2 dimensions
 * with 2 fixed integer parameters.
 */
double blendNoise2d( double x,
                     double y,
                     unsigned long z,
                     unsigned long t ) {

    double floorY = floor( y );
    unsigned long floorIntY = (unsigned long)floorY;

    if( floorY == y ) {
        return blendNoise1d( x, floorIntY, z, t );
        }
    else {
        unsigned long ceilIntY = floorIntY + 1;

        // cosine interpolation
        // from http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
        double ft = ( y - floorY ) * M_PI;
        double f = ( 1 - cos( ft ) ) * .5;

        return ( f ) * blendNoise1d( x, ceilIntY, z, t ) +
               ( 1 - f ) * blendNoise1d( x, floorIntY, z, t );
        }
    }


/**
 * Blends 4d discrete (integer-parameter) noise function along 3 dimensions
 * with 1 fixed integer parameters.
 */
double blendNoise3d( double x,
                     double y,
                     double z,
                     unsigned long t ) {

    double floorZ = floor( z );
    unsigned long floorIntZ = (unsigned long)floorZ;

    if( floorZ == z ) {
        return blendNoise2d( x, y, floorIntZ, t );
        }
    else {
        unsigned long ceilIntZ = floorIntZ + 1;

        // cosine interpolation
        // from http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
        double ft = ( z - floorZ ) * M_PI;
        double f = ( 1 - cos( ft ) ) * .5;

        return ( f ) * blendNoise2d( x, y, ceilIntZ, t ) +
               ( 1 - f ) * blendNoise2d( x, y, floorIntZ, t );
        }
    }


/**
 * Blends 4d discrete (integer-parameter) noise function along 4 dimensions.
 */
double noise4d( double x,
                double y,
                double z,
                double t ) {

    double floorT = floor( t );
    unsigned long floorIntT = (unsigned long)floorT;

    if( floorT == t ) {
        return blendNoise3d( x, y, z, floorIntT );
        }
    else {
        unsigned long ceilIntT = floorIntT + 1;

        // cosine interpolation
        // from http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
        double ft = ( t - floorT ) * M_PI;
        double f = ( 1 - cos( ft ) ) * .5;

        return ( f ) * blendNoise3d( x, y, z, ceilIntT ) +
               ( 1 - f ) * blendNoise3d( x, y, z, floorIntT );
        }
    }