diff options
author | Mattes D <github@xoft.cz> | 2014-11-20 10:13:10 +0100 |
---|---|---|
committer | Mattes D <github@xoft.cz> | 2014-11-20 10:13:10 +0100 |
commit | 288cbf12cb66ed9f026f81bb13e945c68cfefd13 (patch) | |
tree | fa97f48bbd8b871aa556c79974a2f64e76272ac0 /src/Noise/InterpolNoise.h | |
parent | Mobs: Fixed crash with terrain too high. (diff) | |
parent | Merge pull request #1603 from mc-server/ImprovedNoise (diff) | |
download | cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.tar cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.tar.gz cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.tar.bz2 cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.tar.lz cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.tar.xz cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.tar.zst cuberite-288cbf12cb66ed9f026f81bb13e945c68cfefd13.zip |
Diffstat (limited to '')
-rw-r--r-- | src/Noise/InterpolNoise.h | 524 |
1 files changed, 524 insertions, 0 deletions
diff --git a/src/Noise/InterpolNoise.h b/src/Noise/InterpolNoise.h new file mode 100644 index 000000000..683b54563 --- /dev/null +++ b/src/Noise/InterpolNoise.h @@ -0,0 +1,524 @@ + +// InterpolNoise.h + +// Implements the cInterpolNoise class template representing a noise that interpolates the values between integer coords from a single set of neighbors + + + + + +#pragma once + +#include "Noise.h" + +#define FAST_FLOOR(x) (((x) < 0) ? (((int)x) - 1) : ((int)x)) + + + + + +//////////////////////////////////////////////////////////////////////////////// +// cInterpolCell2D: + +template <typename T> +class cInterpolCell2D +{ +public: + cInterpolCell2D( + const cNoise & a_Noise, ///< Noise to use for generating the random values + NOISE_DATATYPE * a_Array, ///< Array to generate into [x + a_SizeX * y] + int a_SizeX, int a_SizeY, ///< Count of the array, in each direction + const NOISE_DATATYPE * a_FracX, ///< Pointer to the array that stores the X fractional values + const NOISE_DATATYPE * a_FracY ///< Pointer to the attay that stores the Y fractional values + ): + m_Noise(a_Noise), + m_WorkRnds(&m_Workspace1), + m_CurFloorX(0), + m_CurFloorY(0), + m_Array(a_Array), + m_SizeX(a_SizeX), + m_SizeY(a_SizeY), + m_FracX(a_FracX), + m_FracY(a_FracY) + { + } + + + /** Generates part of the output noise array using the current m_WorkRnds[] values */ + void Generate( + int a_FromX, int a_ToX, + int a_FromY, int a_ToY + ) + { + for (int y = a_FromY; y < a_ToY; y++) + { + NOISE_DATATYPE Interp[2]; + NOISE_DATATYPE FracY = T::coeff(m_FracY[y]); + Interp[0] = Lerp((*m_WorkRnds)[0][0], (*m_WorkRnds)[0][1], FracY); + Interp[1] = Lerp((*m_WorkRnds)[1][0], (*m_WorkRnds)[1][1], FracY); + int idx = y * m_SizeX + a_FromX; + for (int x = a_FromX; x < a_ToX; x++) + { + m_Array[idx++] = Lerp(Interp[0], Interp[1], T::coeff(m_FracX[x])); + } // for x + } // for y + } + + + /** Initializes m_WorkRnds[] with the specified values of the noise at the specified integral coords. */ + void InitWorkRnds(int a_FloorX, int a_FloorY) + { + m_CurFloorX = a_FloorX; + m_CurFloorY = a_FloorY; + (*m_WorkRnds)[0][0] = m_Noise.IntNoise2D(m_CurFloorX, m_CurFloorY); + (*m_WorkRnds)[0][1] = m_Noise.IntNoise2D(m_CurFloorX, m_CurFloorY + 1); + (*m_WorkRnds)[1][0] = m_Noise.IntNoise2D(m_CurFloorX + 1, m_CurFloorY); + (*m_WorkRnds)[1][1] = m_Noise.IntNoise2D(m_CurFloorX + 1, m_CurFloorY + 1); + } + + + /** Updates m_WorkRnds[] for the new integral coords */ + void Move(int a_NewFloorX, int a_NewFloorY) + { + // Swap the doublebuffer: + int OldFloorX = m_CurFloorX; + int OldFloorY = m_CurFloorY; + Workspace * OldWorkRnds = m_WorkRnds; + m_WorkRnds = (m_WorkRnds == &m_Workspace1) ? &m_Workspace2 : &m_Workspace1; + + // Reuse as much of the old workspace as possible: + // TODO: Try out if simply calculating all 4 elements each time is faster than this monster loop + int DiffX = OldFloorX - a_NewFloorX; + int DiffY = OldFloorY - a_NewFloorY; + for (int x = 0; x < 2; x++) + { + int cx = a_NewFloorX + x; + int OldX = x - DiffX; // Where would this X be in the old grid? + for (int y = 0; y < 2; y++) + { + int cy = a_NewFloorY + y; + int OldY = y - DiffY; // Where would this Y be in the old grid? + if ((OldX >= 0) && (OldX < 2) && (OldY >= 0) && (OldY < 2)) + { + (*m_WorkRnds)[x][y] = (*OldWorkRnds)[OldX][OldY]; + } + else + { + (*m_WorkRnds)[x][y] = (NOISE_DATATYPE)m_Noise.IntNoise2D(cx, cy); + } + } + } + m_CurFloorX = a_NewFloorX; + m_CurFloorY = a_NewFloorY; + } + +protected: + typedef NOISE_DATATYPE Workspace[2][2]; + + /** The noise used for generating the values at integral coords. */ + const cNoise & m_Noise; + + /** The current random values; points to either m_Workspace1 or m_Workspace2 (doublebuffering) */ + Workspace * m_WorkRnds; + + /** Buffer 1 for workspace doublebuffering, used in Move() */ + Workspace m_Workspace1; + + /** Buffer 2 for workspace doublebuffering, used in Move() */ + Workspace m_Workspace2; + + /** Coords of the currently calculated m_WorkRnds[]. */ + int m_CurFloorX, m_CurFloorY; + + /** The output array to generate into. */ + NOISE_DATATYPE * m_Array; + + /** Dimensions of the output array. */ + int m_SizeX, m_SizeY; + + /** Arrays holding the fractional values of the coords in each direction. */ + const NOISE_DATATYPE * m_FracX; + const NOISE_DATATYPE * m_FracY; +} ; + + + + + +//////////////////////////////////////////////////////////////////////////////// +// cInterpolCell3D: + +/** Holds a cache of the last calculated integral noise values and interpolates between them en masse. +Provides a massive optimization for cInterpolNoise. +Works by calculating multiple noise values (that have the same integral noise coords) at once. The underlying noise values +needn't be recalculated for these values, only the interpolation is done within the unit cube. */ +template <typename T> +class cInterpolCell3D +{ +public: + cInterpolCell3D( + const cNoise & a_Noise, ///< Noise to use for generating the random values + NOISE_DATATYPE * a_Array, ///< Array to generate into [x + a_SizeX * y] + int a_SizeX, int a_SizeY, int a_SizeZ, ///< Count of the array, in each direction + const NOISE_DATATYPE * a_FracX, ///< Pointer to the array that stores the X fractional values + const NOISE_DATATYPE * a_FracY, ///< Pointer to the attay that stores the Y fractional values + const NOISE_DATATYPE * a_FracZ ///< Pointer to the array that stores the Z fractional values + ): + m_Noise(a_Noise), + m_WorkRnds(&m_Workspace1), + m_CurFloorX(0), + m_CurFloorY(0), + m_CurFloorZ(0), + m_Array(a_Array), + m_SizeX(a_SizeX), + m_SizeY(a_SizeY), + m_SizeZ(a_SizeZ), + m_FracX(a_FracX), + m_FracY(a_FracY), + m_FracZ(a_FracZ) + { + } + + + /** Generates part of the output array using current m_WorkRnds[]. */ + void Generate( + int a_FromX, int a_ToX, + int a_FromY, int a_ToY, + int a_FromZ, int a_ToZ + ) + { + for (int z = a_FromZ; z < a_ToZ; z++) + { + int idxZ = z * m_SizeX * m_SizeY; + NOISE_DATATYPE Interp2[2][2]; + NOISE_DATATYPE FracZ = T::coeff(m_FracZ[z]); + for (int x = 0; x < 2; x++) + { + for (int y = 0; y < 2; y++) + { + Interp2[x][y] = Lerp((*m_WorkRnds)[x][y][0], (*m_WorkRnds)[x][y][1], FracZ); + } + } + for (int y = a_FromY; y < a_ToY; y++) + { + NOISE_DATATYPE Interp[2]; + NOISE_DATATYPE FracY = T::coeff(m_FracY[y]); + Interp[0] = Lerp(Interp2[0][0], Interp2[0][1], FracY); + Interp[1] = Lerp(Interp2[1][0], Interp2[1][1], FracY); + int idx = idxZ + y * m_SizeX + a_FromX; + for (int x = a_FromX; x < a_ToX; x++) + { + m_Array[idx++] = Lerp(Interp[0], Interp[1], T::coeff(m_FracX[x])); + } // for x + } // for y + } // for z + } + + + /** Initializes m_WorkRnds[] with the specified Floor values. */ + void InitWorkRnds(int a_FloorX, int a_FloorY, int a_FloorZ) + { + m_CurFloorX = a_FloorX; + m_CurFloorY = a_FloorY; + m_CurFloorZ = a_FloorZ; + (*m_WorkRnds)[0][0][0] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX, m_CurFloorY, m_CurFloorZ); + (*m_WorkRnds)[0][0][1] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX, m_CurFloorY, m_CurFloorZ + 1); + (*m_WorkRnds)[0][1][0] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX, m_CurFloorY + 1, m_CurFloorZ); + (*m_WorkRnds)[0][1][1] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX, m_CurFloorY + 1, m_CurFloorZ + 1); + (*m_WorkRnds)[1][0][0] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX + 1, m_CurFloorY, m_CurFloorZ); + (*m_WorkRnds)[1][0][1] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX + 1, m_CurFloorY, m_CurFloorZ + 1); + (*m_WorkRnds)[1][1][0] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX + 1, m_CurFloorY + 1, m_CurFloorZ); + (*m_WorkRnds)[1][1][1] = (NOISE_DATATYPE)m_Noise.IntNoise3D(m_CurFloorX + 1, m_CurFloorY + 1, m_CurFloorZ + 1); + } + + + /** Updates m_WorkRnds[] for the new Floor values. */ + void Move(int a_NewFloorX, int a_NewFloorY, int a_NewFloorZ) + { + // Swap the doublebuffer: + int OldFloorX = m_CurFloorX; + int OldFloorY = m_CurFloorY; + int OldFloorZ = m_CurFloorZ; + Workspace * OldWorkRnds = m_WorkRnds; + m_WorkRnds = (m_WorkRnds == &m_Workspace1) ? &m_Workspace2 : &m_Workspace1; + + // Reuse as much of the old workspace as possible: + // TODO: Try out if simply calculating all 8 elements each time is faster than this monster loop + int DiffX = OldFloorX - a_NewFloorX; + int DiffY = OldFloorY - a_NewFloorY; + int DiffZ = OldFloorZ - a_NewFloorZ; + for (int x = 0; x < 2; x++) + { + int cx = a_NewFloorX + x; + int OldX = x - DiffX; // Where would this X be in the old grid? + for (int y = 0; y < 2; y++) + { + int cy = a_NewFloorY + y; + int OldY = y - DiffY; // Where would this Y be in the old grid? + for (int z = 0; z < 2; z++) + { + int cz = a_NewFloorZ + z; + int OldZ = z - DiffZ; + if ((OldX >= 0) && (OldX < 2) && (OldY >= 0) && (OldY < 2) && (OldZ >= 0) && (OldZ < 2)) + { + (*m_WorkRnds)[x][y][z] = (*OldWorkRnds)[OldX][OldY][OldZ]; + } + else + { + (*m_WorkRnds)[x][y][z] = (NOISE_DATATYPE)m_Noise.IntNoise3D(cx, cy, cz); + } + } // for z + } // for y + } // for x + m_CurFloorX = a_NewFloorX; + m_CurFloorY = a_NewFloorY; + m_CurFloorZ = a_NewFloorZ; + } + +protected: + typedef NOISE_DATATYPE Workspace[2][2][2]; + + /** The noise used for generating the values at integral coords. */ + const cNoise & m_Noise; + + /** The current random values; points to either m_Workspace1 or m_Workspace2 (doublebuffering) */ + Workspace * m_WorkRnds; + + /** Buffer 1 for workspace doublebuffering, used in Move() */ + Workspace m_Workspace1; + + /** Buffer 2 for workspace doublebuffering, used in Move() */ + Workspace m_Workspace2; + + /** The integral coords of the currently calculated WorkRnds[] */ + int m_CurFloorX, m_CurFloorY, m_CurFloorZ; + + /** The output array where the noise is calculated. */ + NOISE_DATATYPE * m_Array; + + /** Dimensions of the output array. */ + int m_SizeX, m_SizeY, m_SizeZ; + + /** Arrays holding the fractional values of the coords in each direction. */ + const NOISE_DATATYPE * m_FracX; + const NOISE_DATATYPE * m_FracY; + const NOISE_DATATYPE * m_FracZ; +} ; + + + + + +//////////////////////////////////////////////////////////////////////////////// +// cInterpolNoise: + +template <typename T> +class cInterpolNoise +{ + /** Maximum size, for each direction, of the generated array. */ + static const int MAX_SIZE = 256; + +public: + cInterpolNoise(int a_Seed): + m_Noise(a_Seed) + { + } + + + /** Sets a new seed for the generators. Relays the seed to the underlying noise. */ + void SetSeed(int a_Seed) + { + m_Noise.SetSeed(a_Seed); + } + + + /** Fills a 2D array with the values of the noise. */ + void Generate2D( + NOISE_DATATYPE * a_Array, ///< Array to generate into [x + a_SizeX * y] + int a_SizeX, int a_SizeY, ///< Count of the array, in each direction + NOISE_DATATYPE a_StartX, NOISE_DATATYPE a_EndX, ///< Noise-space coords of the array in the X direction + NOISE_DATATYPE a_StartY, NOISE_DATATYPE a_EndY ///< Noise-space coords of the array in the Y direction + ) const + { + ASSERT(a_SizeX > 0); + ASSERT(a_SizeY > 0); + ASSERT(a_SizeX < MAX_SIZE); + ASSERT(a_SizeY < MAX_SIZE); + ASSERT(a_StartX < a_EndX); + ASSERT(a_StartY < a_EndY); + + // Calculate the integral and fractional parts of each coord: + int FloorX[MAX_SIZE]; + int FloorY[MAX_SIZE]; + NOISE_DATATYPE FracX[MAX_SIZE]; + NOISE_DATATYPE FracY[MAX_SIZE]; + int SameX[MAX_SIZE]; + int SameY[MAX_SIZE]; + int NumSameX, NumSameY; + CalcFloorFrac(a_SizeX, a_StartX, a_EndX, FloorX, FracX, SameX, NumSameX); + CalcFloorFrac(a_SizeY, a_StartY, a_EndY, FloorY, FracY, SameY, NumSameY); + + cInterpolCell2D<T> Cell(m_Noise, a_Array, a_SizeX, a_SizeY, FracX, FracY); + + Cell.InitWorkRnds(FloorX[0], FloorY[0]); + + // Calculate query values using Cell: + int FromY = 0; + for (int y = 0; y < NumSameY; y++) + { + int ToY = FromY + SameY[y]; + int FromX = 0; + int CurFloorY = FloorY[FromY]; + for (int x = 0; x < NumSameX; x++) + { + int ToX = FromX + SameX[x]; + Cell.Generate(FromX, ToX, FromY, ToY); + Cell.Move(FloorX[ToX], CurFloorY); + FromX = ToX; + } // for x + Cell.Move(FloorX[0], FloorY[ToY]); + FromY = ToY; + } // for y + } + + + /** Fills a 3D array with the values of the noise. */ + void Generate3D( + NOISE_DATATYPE * a_Array, ///< Array to generate into [x + a_SizeX * y + a_SizeX * a_SizeY * z] + int a_SizeX, int a_SizeY, int a_SizeZ, ///< Count of the array, in each direction + NOISE_DATATYPE a_StartX, NOISE_DATATYPE a_EndX, ///< Noise-space coords of the array in the X direction + NOISE_DATATYPE a_StartY, NOISE_DATATYPE a_EndY, ///< Noise-space coords of the array in the Y direction + NOISE_DATATYPE a_StartZ, NOISE_DATATYPE a_EndZ ///< Noise-space coords of the array in the Z direction + ) const + { + // Check params: + ASSERT(a_SizeX > 1); + ASSERT(a_SizeY > 1); + + ASSERT(a_SizeX < MAX_SIZE); + ASSERT(a_SizeY < MAX_SIZE); + ASSERT(a_SizeZ < MAX_SIZE); + ASSERT(a_StartX < a_EndX); + ASSERT(a_StartY < a_EndY); + ASSERT(a_StartZ < a_EndZ); + + // Calculate the integral and fractional parts of each coord: + int FloorX[MAX_SIZE]; + int FloorY[MAX_SIZE]; + int FloorZ[MAX_SIZE]; + NOISE_DATATYPE FracX[MAX_SIZE]; + NOISE_DATATYPE FracY[MAX_SIZE]; + NOISE_DATATYPE FracZ[MAX_SIZE]; + int SameX[MAX_SIZE]; + int SameY[MAX_SIZE]; + int SameZ[MAX_SIZE]; + int NumSameX, NumSameY, NumSameZ; + CalcFloorFrac(a_SizeX, a_StartX, a_EndX, FloorX, FracX, SameX, NumSameX); + CalcFloorFrac(a_SizeY, a_StartY, a_EndY, FloorY, FracY, SameY, NumSameY); + CalcFloorFrac(a_SizeZ, a_StartZ, a_EndZ, FloorZ, FracZ, SameZ, NumSameZ); + + cInterpolCell3D<T> Cell( + m_Noise, a_Array, + a_SizeX, a_SizeY, a_SizeZ, + FracX, FracY, FracZ + ); + + Cell.InitWorkRnds(FloorX[0], FloorY[0], FloorZ[0]); + + // Calculate query values using Cell: + int FromZ = 0; + for (int z = 0; z < NumSameZ; z++) + { + int ToZ = FromZ + SameZ[z]; + int CurFloorZ = FloorZ[FromZ]; + int FromY = 0; + for (int y = 0; y < NumSameY; y++) + { + int ToY = FromY + SameY[y]; + int CurFloorY = FloorY[FromY]; + int FromX = 0; + for (int x = 0; x < NumSameX; x++) + { + int ToX = FromX + SameX[x]; + Cell.Generate(FromX, ToX, FromY, ToY, FromZ, ToZ); + Cell.Move(FloorX[ToX], CurFloorY, CurFloorZ); + FromX = ToX; + } + Cell.Move(FloorX[0], FloorY[ToY], CurFloorZ); + FromY = ToY; + } // for y + Cell.Move(FloorX[0], FloorY[0], FloorZ[ToZ]); + FromZ = ToZ; + } // for z + } + +protected: + + /** The noise used for the underlying value generation. */ + cNoise m_Noise; + + + /** Calculates the integral and fractional parts along one axis. + a_Floor will receive the integral parts (array of a_Size ints). + a_Frac will receive the fractional parts (array of a_Size floats). + a_Same will receive the counts of items that have the same integral parts (array of up to a_Size ints). + a_NumSame will receive the count of a_Same elements (total count of different integral parts). */ + void CalcFloorFrac( + int a_Size, + NOISE_DATATYPE a_Start, NOISE_DATATYPE a_End, + int * a_Floor, NOISE_DATATYPE * a_Frac, + int * a_Same, int & a_NumSame + ) const + { + ASSERT(a_Size > 0); + + // Calculate the floor and frac values: + NOISE_DATATYPE val = a_Start; + NOISE_DATATYPE dif = (a_End - a_Start) / (a_Size - 1); + for (int i = 0; i < a_Size; i++) + { + a_Floor[i] = FAST_FLOOR(val); + a_Frac[i] = val - a_Floor[i]; + val += dif; + } + + // Mark up the same floor values into a_Same / a_NumSame: + int CurFloor = a_Floor[0]; + int LastSame = 0; + a_NumSame = 0; + for (int i = 1; i < a_Size; i++) + { + if (a_Floor[i] != CurFloor) + { + a_Same[a_NumSame] = i - LastSame; + LastSame = i; + a_NumSame += 1; + CurFloor = a_Floor[i]; + } + } // for i - a_Floor[] + if (LastSame < a_Size) + { + a_Same[a_NumSame] = a_Size - LastSame; + a_NumSame += 1; + } + } +}; + + + + + +/** A fifth-degree curve for interpolating. +Implemented as a functor for better chance of inlining. */ +struct Interp5Deg +{ + static NOISE_DATATYPE coeff(NOISE_DATATYPE a_Val) + { + return a_Val * a_Val * a_Val * (a_Val * (a_Val * 6 - 15) + 10); + } +}; + +typedef cInterpolNoise<Interp5Deg> cInterp5DegNoise; + + + |