Cafu Engine
Terrain.hpp
1 /*
2 Cafu Engine, http://www.cafu.de/
3 Copyright (c) Carsten Fuchs and other contributors.
4 This project is licensed under the terms of the MIT license.
5 */
6 
7 #ifndef CAFU_TERRAIN_HPP_INCLUDED
8 #define CAFU_TERRAIN_HPP_INCLUDED
9 
10 #include "Templates/Array.hpp"
11 #include "Math3D/BoundingBox.hpp"
12 #include "Math3D/Brush.hpp"
13 #include "Math3D/Plane3.hpp"
14 
15 
16 /// This class represents terrains, offering methods for LoD rendering and collision detection.
17 class TerrainT
18 {
19  public:
20 
21  // TODO 1: Rename "e" to "error" and "r" to "radius".
22  // TODO 2: Should we really derive from Vector3fT? Can we omit x and y (and instead compute it on the fly when required)?
23  struct VertexT : public Vector3fT
24  {
25  float e; ///< Error.
26  float r; ///< Bounding sphere radius.
27  };
28 
29  struct ViewInfoT
30  {
31  bool cull; ///< Perform view culling when set.
32  float nu; ///< Inverse of error tolerance in radians. Note that this is equivalent to the "magic" number in the original SOARX class by Andras Balogh.
33  float nu_min; ///< Lower morph parameter.
34  float nu_max; ///< Upper morph parameter.
35  Vector3fT viewpoint; ///< The viewpoint. Corresponds to Camera::m_position in the original code by Andras Balogh.
36  Plane3fT viewplanes[5]; ///< View frustum planes (without the "far" plane). Corresponds to Camera::m_frustum_planes in the original code by Andras Balogh.
37  };
38 
39  /// An error class that is thrown upon init errors in the constructor.
40  class InitError {};
41 
42 
43  /// Constructor for creating a simple dummy terrain.
44  /// The main purpose is to be able to store TerrainTs in container classes.
45  TerrainT();
46 
47  /// The constructor for creating and initializing the terrain from the file specified by FileNameHeightMap.
48  /// FileNameHeightMap should be the file name of a gray-scale heightmap in bmp, tga, or png file format.
49  /// The heightmap must be square, and the side lengths be of the form (2^n)+1, where n is in range 1...15.
50  /// (Thus, the smallest permissible heightmap has size 3x3, the largest 32769x32769.)
51  /// The bounding box BB determines the lateral dimensions of the terrain.
52  /// If FailSafe is set to false, InitError is thrown on problems reading the file or violation of the
53  /// above constraints. Otherwise, a simple default heightmap is substituted.
54  TerrainT(const char* FileNameHeightMap, const BoundingBox3fT& BB_, bool FailSafe=true) /*throw (InitError)*/;
55 
56  /// Constructor as above, except that instead of the bounding box, a Resolution vector is passed in.
57  /// The resolution describes the distance between two elements of the height map in x- and y-direction,
58  /// as well as the distance between two height values (z-direction). The resulting terrain is centered at the origin.
59  TerrainT(const char* FileNameHeightMap, const Vector3fT& Resolution, bool FailSafe=true) /*throw (InitError)*/;
60 
61  /// The constructor for creating and initializing the terrain from the data specified in HeightData.
62  /// The heightmap must be square, and the side lengths be of the form (2^n)+1, where n is in range 1...15.
63  /// (Thus, the smallest permissible heightmap has size 3x3, the largest 32769x32769.)
64  /// The bounding box BB determines the lateral dimensions of the terrain.
65  TerrainT(const unsigned short* HeightData, unsigned long SideLength, const BoundingBox3fT& BB_) /*throw (InitError)*/;
66 
67  /// Updates the vertices in the given rectangle with new heights from the given height field.
68  /// Note that this method is a HACK, because it INVALIDATES the auxiliary data that is computed in the constructor;
69  /// the nested error metrics, radii and collision data in the quad-tree all become INVALID after a call to this method.
70  /// The purpose of this method is to allow for quick but temporary changes in terrain heights of small magnitude,
71  /// e.g. while the mouse button is held down for a single tool application in a terrain editor.
72  /// @param HeightData A pointer to a new heightmap of dimensions GetSize()*GetSize() from which the new heights are taken.
73  /// @param PosX The x-origin of the rectangle in which the vertices are updated.
74  /// @param PosY The y-origin of the rectangle in which the vertices are updated.
75  /// @param SizeX The width of the rectangle in which the vertices are updated.
76  /// @param SizeY The height of the rectangle in which the vertices are updated.
77  void UpdateHeights(const unsigned short* HeightData, unsigned long PosX, unsigned long PosY, unsigned long SizeX, unsigned long SizeY);
78 
79  /// This functions returns a pointer to the vertices of the terrain,
80  /// intended for use with the ComputeIndexStripByRefinement() function.
81  const VertexT* GetVertices() const;
82 
83  /// Returns the number of vertices along one side of the terrain/heightmap, e.g. 257, 513, 1025, ...
84  unsigned long GetSize() const { return Size; }
85 
86  /// Returns the bounding-box (i.e. the lateral dimensions) of the terrain/heightmap.
87  const BoundingBox3fT& GetBB() const { return BB; }
88 
89  /// This function computes a triangle strip of vertices that approximates the terrain according to the parameters in VI.
90  /// For this purpose, geo-morphing is employed in order to prevent sudden popping and to simultaneously allow for greater
91  /// error tolerances.
92  /// The returned array is global and thus mutable. It will change upon the next call to this function of *any* terrain object.
94 
95  /// This function computes a triangle strip that approximates the terrain according to the parameters in VI.
96  /// For this purpose, the method of refinement is employed, and there is no geo-morphing to prevent sudden popping.
97  /// The returned triangle strip consists of indices into the array of terrain vertices, which in turn can be obtained
98  /// by calling the GetVertices() function. Note that the real strip index data starts at index 1 of the returned array,
99  /// and thus the first entry (at array index 0) should be skipped or ignored.
100  /// Also, the returned array is global and thus mutable. It will change upon the next call to this function of *any* terrain object.
101  ArrayT<unsigned long>& ComputeIndexStripByRefinement(const ViewInfoT& VI) const;
102 
103  /// This function computes a triangle strip of vectors that approximates the terrain according to the parameters in VI.
104  /// For this purpose, geo-morphing is employed in order to prevent sudden popping and simultaneously allow for greater
105  /// error tolerances. Note that the real strip vector data starts at index 1 of the returned array, and thus the first
106  /// entry (at array index 0) should be skipped or ignored.
107  /// Also, the returned array is global and thus mutable. It will change upon the next call to this function of *any* terrain object.
108  ArrayT<Vector3fT>& ComputeVectorStripByMorphing(const ViewInfoT& VI) const;
109 
110  /// Traces the (relative) bounding box TraceBB from the (absolute) Origin along Dir towards the end position Origin+VectorScale(Dir, Trace.Fraction).
111  /// The result is returned in Trace, indicating if and where the trace was stopped.
112  void TraceBoundingBox(const BoundingBox3dT& TraceBB, const VectorT& Origin, const VectorT& Dir, VB_Trace3T<double>& Trace) const;
113 
114 
115  private:
116 
117  class QuadTreeT
118  {
119  private:
120 
121  unsigned long Child00Index; ///< Lower left child index into a given array of QuadTreeT.
122  unsigned long Child01Index; ///< Upper left child index into a given array of QuadTreeT.
123  unsigned long Child10Index; ///< Lower right child index into a given array of QuadTreeT.
124  unsigned long Child11Index; ///< Upper right child index into a given array of QuadTreeT.
125 
126  float HeightMin;
127  float HeightMax;
128 
129  unsigned long LowerLeftVertexIndex; ///< If this node is a child, this is the index of its lower left vertex.
130  unsigned long UpperRightVertexIndex; ///< If this node is a child, this is the index of its upper right vertex.
131 
132 
133  public:
134 
135  QuadTreeT() { } ///< Default constructor, required for use with ArrayT.
136  QuadTreeT(TerrainT& Terrain, unsigned long LowerLeftVertIdx, unsigned long UpperRightVertIdx, unsigned long Level);
137  void TraceBoundingBox(const TerrainT& Terrain, double BBMinX, double BBMinY, double BBMaxX, double BBMaxY, const BoundingBox3T<double>& BB, const VectorT& Origin, const VectorT& Dir, VB_Trace3T<double>& Trace) const;
138  };
139 
140  friend class QuadTreeT;
141 
142 
143  // This is the actual internal representation of the terrain.
144  ArrayT<VertexT> Vertices; ///< Array of all terrain vertices.
145  unsigned long Size; ///< Lateral dimensions of the terrain/heightmap, e.g. 257, 513, 1025, ...
146  unsigned long Levels; ///< Size==2^(Levels/2)+1
147  BoundingBox3fT BB; ///< Lateral dimensions in world coordinates.
148  ArrayT<QuadTreeT> QuadTree; ///< All nodes of the QuadTree for this terrain (the last element is the root), used for collision detection (that is, TraceBoundingBox()).
149 
150  // Const data used in ComputeVectorStrip().
151  /*const*/ bool mCVS_Side;
152  /*const*/ bool mCVS_Bottom;
153 
154  // Working data used in ComputeVectorStrip().
155  mutable bool mCVS_LeftOnly;
156  mutable bool mCVS_First;
157  mutable unsigned long mCVS_CurrentLevel;
158 
159 
160  // Helper functions for the constructor.
161  const VertexT& GetVertex(unsigned long i, unsigned long j) const { return Vertices[i+Size*j]; }
162  VertexT& GetVertex(unsigned long i, unsigned long j) { return Vertices[i+Size*j]; }
163  void ComputeVertexLoD(unsigned long i, unsigned long j, int di, int dj, unsigned long n);
164  void Init(const char* FileNameHeightMap, const BoundingBox3fT* BB_, const Vector3fT* Resolution, bool FailSafe);
165 
166  // Helper functions for ComputeVectorStrip().
167  class CVS_VertexT;
168  void CVS_GetVertex(CVS_VertexT& v) const;
169  bool CVS_Active(CVS_VertexT& v, float zEdge, unsigned long& planes) const;
170  void CVS_Append(const CVS_VertexT& v) const;
171  void CVS_TurnCorner() const;
172  void CVS_RefineTop() const;
173  void CVS_Refine(const CVS_VertexT& i, const CVS_VertexT& j, float zA, float zB, bool in, bool out, unsigned long planes) const;
174  void CVS_RefineL(const CVS_VertexT& i, const CVS_VertexT& j, float zA, bool in, unsigned long planes) const;
175  void CVS_RefineR(CVS_VertexT i, CVS_VertexT j, float zB, bool out, unsigned long planes) const;
176 
177  // Helper functions for ComputeIndexStripByRefinement().
178  void Refine_AppendStripIndex(unsigned long VertexIndex, bool Parity) const;
179  void Refine_SubMesh(unsigned long l, /* TRIANGLE( */unsigned long i, unsigned long j, unsigned long k/*)*/) const;
180  void Refine_SubMeshVisible(unsigned long l, /* TRIANGLE( */unsigned long i, unsigned long j, unsigned long k/*)*/, unsigned long m) const;
181 
182  // Helper functions for ComputeVectorStripByMorphing().
183  void Morph_AppendStripVector(unsigned long VertexIndex, bool Parity, float z) const;
184  void Morph_SubMesh(unsigned long l, /* TRIANGLE( */unsigned long i, unsigned long j, unsigned long k/*)*/, float za, float zl, float zr) const;
185  void Morph_SubMeshVisible(unsigned long l, /* TRIANGLE( */unsigned long i, unsigned long j, unsigned long k/*)*/, float za, float zl, float zr, unsigned long m) const;
186 };
187 
188 #endif
float nu_max
Upper morph parameter.
Definition: Terrain.hpp:34
This classes describes the trace (Verfolgungsergebnis) of a vector or a bounding box with regards to ...
Definition: Brush.hpp:18
This class represents terrains, offering methods for LoD rendering and collision detection.
Definition: Terrain.hpp:17
ArrayT< unsigned long > & ComputeIndexStripByRefinement(const ViewInfoT &VI) const
This function computes a triangle strip that approximates the terrain according to the parameters in ...
Definition: Terrain.cpp:1023
const BoundingBox3fT & GetBB() const
Returns the bounding-box (i.e. the lateral dimensions) of the terrain/heightmap.
Definition: Terrain.hpp:87
Vector3fT viewpoint
The viewpoint. Corresponds to Camera::m_position in the original code by Andras Balogh.
Definition: Terrain.hpp:35
bool cull
Perform view culling when set.
Definition: Terrain.hpp:31
An error class that is thrown upon init errors in the constructor.
Definition: Terrain.hpp:40
const VertexT * GetVertices() const
This functions returns a pointer to the vertices of the terrain, intended for use with the ComputeInd...
Definition: Terrain.cpp:125
TerrainT()
Constructor for creating a simple dummy terrain.
Definition: Terrain.cpp:481
void TraceBoundingBox(const BoundingBox3dT &TraceBB, const VectorT &Origin, const VectorT &Dir, VB_Trace3T< double > &Trace) const
Traces the (relative) bounding box TraceBB from the (absolute) Origin along Dir towards the end posit...
Definition: Terrain.cpp:1182
float r
Bounding sphere radius.
Definition: Terrain.hpp:26
ArrayT< Vector3fT > & ComputeVectorStripByMorphing(const ViewInfoT &VI) const
This function computes a triangle strip of vectors that approximates the terrain according to the par...
Definition: Terrain.cpp:1150
float nu
Inverse of error tolerance in radians. Note that this is equivalent to the "magic" number in the orig...
Definition: Terrain.hpp:32
Definition: Terrain.hpp:23
Plane3fT viewplanes[5]
View frustum planes (without the "far" plane). Corresponds to Camera::m_frustum_planes in the origina...
Definition: Terrain.hpp:36
unsigned long GetSize() const
Returns the number of vertices along one side of the terrain/heightmap, e.g. 257, 513...
Definition: Terrain.hpp:84
void UpdateHeights(const unsigned short *HeightData, unsigned long PosX, unsigned long PosY, unsigned long SizeX, unsigned long SizeY)
Updates the vertices in the given rectangle with new heights from the given height field...
Definition: Terrain.cpp:542
float e
Error.
Definition: Terrain.hpp:25
ArrayT< Vector3fT > & ComputeVectorStrip(const TerrainT::ViewInfoT &VI) const
This function computes a triangle strip of vertices that approximates the terrain according to the pa...
Definition: Terrain.cpp:558
Definition: Terrain.hpp:29
float nu_min
Lower morph parameter.
Definition: Terrain.hpp:33
Definition: Renderer.hpp:16