passage/gamma256/gameSource/landscape.cpp
2025-10-03 02:19:59 -04:00

454 lines
13 KiB
C++

/*
* 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 int random32_readable( unsigned int inSeed ) {
// this is the true hot-spot of the entire landscape function
// thus, optimization is warranted.
// multiplier = 3141592621
// use hex to avoid warnings
//unsigned int multiplier = 0xBB40E62D;
//unsigned int increment = 1;
// better:
// unsigned int multiplier = 196314165
// unsigned int increment = 907633515
// this will automatically be mod-ed by 2^32 because of the limit
// of the unsigned int 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 int Num1 = (inSeed * 0xFEA09B9DU) + 1;
//const unsigned int Num2 = ((inSeed * 0xB89C8895U) + 1) >> 16;
//return Num1 ^ Num2;
/*
unsigned int rseed=(inSeed*15064013)^(inSeed*99991+604322121)^(inSeed*45120321)^(inSeed*5034121+13);
const unsigned int Num1 = (inSeed * 0xFEA09B9DU) + 1;
const unsigned int Num2 = ((inSeed * 0xB89C8895U) + 1) >> 16;
rseed *= Num1 ^ Num2;
return rseed;
*/
const unsigned int Num1 = (inSeed * 0xFEA09B9DU) + 1;
const unsigned int Num2 = ((inSeed^Num1) * 0x9C129511U) + 1;
const unsigned int Num3 = (inSeed * 0x2512CFB8U) + 1;
const unsigned int Num4 = ((inSeed^Num3) * 0xB89C8895U) + 1;
const unsigned int Num5 = (inSeed * 0x6BF962C1U) + 1;
const unsigned int Num6 = ((inSeed^Num5) * 0x4BF962C1U) + 1;
return Num2 ^ (Num4 >> 11) ^ (Num6 >> 22);
}
// faster as a set of macros
#define Num1( inSeed ) \
( ( inSeed * 0xFEA09B9DU ) + 1 )
#define Num2( inSeed ) \
( ( ( inSeed ^ Num1( inSeed ) ) * 0x9C129511U ) + 1 )
#define Num3( inSeed ) \
( ( inSeed * 0x2512CFB8U ) + 1 )
#define Num4( inSeed ) \
( ( ( inSeed ^ Num3( inSeed ) ) * 0xB89C8895U ) + 1 )
#define Num5( inSeed ) \
( ( inSeed * 0x6BF962C1U ) + 1 )
#define Num6( inSeed ) \
( ( ( inSeed ^ Num5( inSeed ) ) * 0x4BF962C1U ) + 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 int x,
unsigned int y,
unsigned int z,
unsigned int 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 int randomSeed =
x ^
y * 57 ^
z * 131 ^
t * 2383;
// a random value between 0 and max unsigned int
unsigned int 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 int y,
unsigned int z,
unsigned int t ) {
double floorX = floor( x );
unsigned int floorIntX = (unsigned int)floorX;
if( floorX == x ) {
unsigned int precomputedMix = mixFour( floorIntX, y, z, t );
return noise1dInt32( precomputedMix );
}
else {
unsigned int 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 int 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 int z,
unsigned int t ) {
double floorY = floor( y );
unsigned int floorIntY = (unsigned int)floorY;
if( floorY == y ) {
return blendNoise1d( x, floorIntY, z, t );
}
else {
unsigned int 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 int t ) {
double floorZ = floor( z );
unsigned int floorIntZ = (unsigned int)floorZ;
if( floorZ == z ) {
return blendNoise2d( x, y, floorIntZ, t );
}
else {
unsigned int 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 int floorIntT = (unsigned int)floorT;
if( floorT == t ) {
return blendNoise3d( x, y, z, floorIntT );
}
else {
unsigned int 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 );
}
}
/**
* Blends 4d discrete (integer-parameter) noise function along 3 dimensions
* to get a 3D noise function.
*/
double noise3d( double x,
double y,
double z ) {
return blendNoise3d( x, y, z, 0 );
}