Planet Rendering: Part 1 - The Basics

<< WARNING: Long! >> Introduction: As some of you might have noticed from other threads on this forum, I am developing a planetary-scale 3D graphics engine for our game, "The Keepers" (link in my signature). The game will involve the simulation of an entire planet. On the engine's side, this will involve procedural generation of terrain features (including features such as vegetation coverage, rivers, etcetera), real-time deformation of the terrain, simulation of water (seas and oceans in partcular), weather simulation, and rendering of the terrain, plants, water, and atmosphere based on the generated data. The engine is currently in early stages of development, and the planetary simulation/rendering part of the engine is in design stages. Following my own interest in the area, and the interest expressed in this recent thread, I have decided to initiate a series of threads, each focusing on a different aspect of the realistic simulation and rendering of a virtual planet. In the beginning of each thread, I will provide a references section with links to previous threads in the series and other threads, articles, papers, and so on, which are relevant to that particlar thread. This series is intended to serve as a reference for everyone developing a terrain engine, particularly those interested in procedural worlds, contineuous ("infinite") terrain, and/or planetary scale engines (somewhat like this famous sky thread). The success of this series depends entirely on your participation and cooperation. Note: I suppose this would be a good time to ask everyone who decides to participate to stick to the topic of the corresponding thread. PS: Did you notice the icon I used for this thread? Get it?

---

References: The Virtual Terrain Project [website] Infinite world. tiling maps [gamedev thread] - includes basis for geo-quadtree idea (see below). Spherical Trees [gamedev thread] Geomipmaping [paper] Octrees [tutorial] Adaptive Binary Trees [gamedev thread] (some posts down the thread) Quaternions [article] Anyone knows some good links regarding quadtrees (I don't need them myself, but other people that read this thread might need them)? Some more links regarding octrees are also welcome (as well as any other link you think is relevant).

---

Ok. Let's begin. As stated by the title, this thread is about the basics of planet rendering, which means the following:

• The concepts of continuous and semi-continuous data representation .
• Basic data structures and representation. Note that additional data structures may be discussed in following threads, if necessary.
• Basic algorthims (LOD, frustum culling, etc.), in the context of that data representation.

An important assumption that I'll be making throughout the dicussion is that all distances and sizes are scaled realistically (e.g an object 100 meters in diameter should be exactly 5 times larger than another object that is 20 meters in diameter). First, let's define continuous data representation . Continuous data representation, is a data representation which does not introduce borders to the data. Such a representation is probably the most comfortable when dealing with continuous data, such as the hight data of the surface of a planet. Unforetunately, I am not familiar with any continous (or semi-contuous, defined below) data representations in the comupter science or 3D graphics literature (altough I have some of my own thoughts on the topic, which I'll describe later in this post), so I cannot bring examples (other than what I'll describe below). If anyone is familiar with such data representations, please post some links and/or a description of the basic ideas behind those schemes. As a famous example for a non-continuous data representation, consider a heightmap. Clearly, it introduces boundaries to the data, since one could only move so far in any direction along the heightmap (e.g. one can't move more than 255 pixels to the right, starting at the top-left pixel of a 256x256 pixel heightmap). A semi-continuous data representation is a data representation that is continuous along at least one dimension, and non-continuous along at least one other dimention (note that this implies multi-dimentional data, e.g. 3D data). An example of data that will benefit from a semi-continuous representation is wheather parameters ditribution in the atmosphere of a planet (temperature, pressure, humidity, and air-flow vectors are examples of such parameters). Such data is semi-continuous because an atmosphere is continuous in the horizontal dimensions (the dimensions paralel to the planet's surface), but limited in the vertical dimension (it has a minimum and maximum altitudes). All of the data that will be used for the simulation and rendering of our virtual planet will most likely need to be represented in either continuous or semi-continuous form. As originally suggested in this thread, I have considered the use of spherical polar coordinates to contuously represent the various data of the planet. This would consist of an ordinary octtree, quadtree, or ABT, built and maintained in sperical polar coordinates. However, I have reached the conclusion that, while a significant improvement (for the purpose of planet simulation and rendering) over the cartesian versions of these structures, the polar-coordinate versions would still suffer from the same non-continuity problems as their cartesian counterparts. This is in part due to the non-continuity of the polar coordinates themselves (e.g. once you reach 180 degrees longtitude, you'd have to wrap back to -180 degrees to continue). A better solution would be a geosphere like structure. The basic idea of the structure is the same as a quadtree, but with the following adjustments:

• The nodes of the tree would represent triangular areas, rather than rectangular areas as in a conventional quadtree.
• While the root node would represent the entire planet, as you would probably do with an ordinary quadtree, its four child nodes would represent the four faces of a trangular piramid which is the basis for the geosphere, as suggested by TerranFury in this thread.
• The nodes would subdivide as decribed in the same thread.
• Each node would store pointers to its three neighbours, in addition to the regular child (and possibly parent) pointers. This is crucial for the continuity of the data representation.
• Each node would have a minimum and maximum altitude.

Note that each node completely contains its children, in terms of volume and position. Since each node is connected with its neighbors in a continuous fashion, there is probably little or no sence in destinguishing the "center" child of a node from the "corner" children. For data requiring a 3D representation, rather than a 2D one, the structure can be extended to an octtree, by subdividing along the altitude vector as well (it would then become a semi-continuous representation, since the data is limited along the altitude vector). For lack of a better name, I will call this structure a geo-quadtree , and its corresponding octtree version a geo-octtree . Issues that should be discussed regarding these structures:

• How to handle neighbor pointers between nodes of different subdivision levels?
• How to represent the volume of each node? Positions of the corners? Some other method?
• Other?

Other solutions are also welcome. For the frame of reference, a right-hand cartesian system seems adequate, whereas its origin is at the center of the planet, and its "up" axis (y in OpenGL) points towards the north pole of the planet. Representing positions, orientation, etc. Again, polar coordinates (lattitude, longtitude, altitude) were considered for the representation of positions. However, due to their discontinuity (mentioned above), and the problems of converting between cartesian coordinates and polar coordinates, they seem rather inadequate. A different option would be to use quaternions and altitude values, whereas the quaternion would specifiy the "horizontal" position and the altitude would specify the "vertical" position. Quaternions are particularly handy in that one could easily (and continuously) traverse the surface of the planet by interpolating between the source and destination quaternions. However, it may be somewhat problematic to do physical simulations if positions are (partially) represented as quaternions. Question: how can one find the angle between two quaternions (not sure this makes much sence as such, since quaternions are essentially 4D, but it does make sence to find the angle between two positions/orientations that are represented by quaternions)? Another option is to use an axis-angle pair instead of the quaternions. For positions combined with an orientation, the axis should probably be perpendicular to the "forward" vector of the object and to the radius vector (the vector from the center of the planet to the object). For "pure" positions (i.e. no orientation), any axis that is perpendicular to the radius vector will do. This may be more comfortable for physics, but interpolation gets more tricky... then again, interpolation might not be necessary in the first place... It may be possible that a standard cartesian vector, possibly in unit-vector+length form, would be sufficient, but I am not sure as to the continuity of such a representation. If it is sufficient, it would, by far, be the most convinient for physics. Whatever the representation, it should have the following properties:

• Continuous
• Easy to find angle between two positions (the more efficient, the better - this is important for horizon culling, which is described below)
• Easy to work with when it comes to physics. For example, if polar coordinates didn't have their other problems, they could have been used directly in physics, since on the local scale the two are almost the same (since the angles involved are extremely small)

Any thoughts on this matter? This brings us to orientations. It would seem that any method would do here, including a second quaternion, a roll/pitch/yaw triplet, and others. Feel free to correct me. The standard vector and plane representations will probably do as well (a couple of small adjustments may be needed for planes). Again, correct me if I'm wrong. A few extra words regarding planes. As you should know, the standard equation for a plane is Ax+By+Cz+D=0, or Ax+By+Cz = -D. Conviniently enough, (A,B,C) is the normal vector of the plane, and if it is normalized, then |D| is the distance of the plane from the origin. In other words, if the (A,B,C) vector is normalized, then in our frame of reference (which I mentioned above) (A,B,C) is a vector on the surface of a unit sphere, which is concentric with our planet, and |D| is the altitude of the plane. This will come in handy later. So to represent a plane, we should probably add two constraints: a) the (A,B,C) vector must be kept normalized (this restriction also simplifies point-distance-from-plane calculations), and b) we will use the slightly modified plane equation Ax+By+Cz-D=0, and require that D>0. This implies that the (A,B,C) vector must always point away from the origin (and never towards it), and that a paralel plane that is the same distance away from the origin but on its other side, will be given by (-A)x+(-B)y+(-C)z-D=0. This allows us to introduce two new concepts, which are demonstrated by the following image: The circle represents our planet, with its center being the origin. The blue line represent the D(A,B,C) vector, and the red line represents the plane. Everything within the white region is considered to be on the inner side of the plane , and everything in the gray region is considered to be on the outer side of the plane . As before, other ideas are welcome. Some basic algorithms Horizon culling: The first thing to do for horizon culling is to compute the angle between the camera and any one object. Any object that is farther than a known angle theta from the camera can be culled away. By calculating the angle between the camera and the vertices of each node of our geo-quadtree, heirarchial horizon culling can be acheived. The angle theta is a direct function of the altitude of the camera, and can be easily precalculated and stored in a LUT. It is imporatnt to note, that since some objects (such as high mountains) can be seen beyond the horizon, theta should be larger than the angle from the camera to the horizon: As can be seen from the image, theta is given by: theta = arccos(R/h) + arccos(R/H), where R is the radius of the planet, not including the atmosphere (i.e. the minimum surface altitude, measured from the center of the planet), h is the altitude of the camera (measured from the center of the planet), and H is the maximum altitude that an object can reach (again, measured from the center). Frustum culling: Frustum culling may be done in one of two ways. The first one is to convert the whatever-position-representation of the geo-quadtree nodes' vertices to conventional cartesian coordinates, and proceed as normal. The other way is to take advantage of the way we represent our planes: The gray area represents the geo-quadtree node we are testing. The culling against each of the frustum's planes is done by calculating two treshold values for the plane's D parameter, using the formula D=R*cos(theta), where R is the minimum/maximum radius of the volume we're testing, and theta is the angle between the plane's (A,B,C) vector and the coorsponding side of the volume (marked in blue in the image). If the plane's actual D is lower than the minimum treshold, than the volume is entirely on the outer side of the plane. If the plane's actual D is higher than the maximum treshold, than the volume is entirely on the inner side of the plane. Otherwise, the plane intersects the volume. I am not sure which of the two methods is more efficient, and which optimization are possible with each one... As always, comments, suggetions, etcetera are welcome. Occlusion culling: I am not yet sure exactly how to acheive this, but a possible way may involve the culling of geo-octree nodes against other geo-octree nodes that are known to be underground. LOD: This can be done in one of many different methods, but geomipmamping seems a good choice here, with the adjustment that we work with traingular regions instead of rectangular ones: The red lines represent the pach boundaries. An inportant issue to consider here, is how would one handle large level-of-detail changes, e.g. to represent the height data of a river shore, which runs though a large relatively flat area... Let the discussions begin! Michael K., Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die! [edited by - technobot on April 4, 2003 7:08:42 PM]