Chapter II: LOD Introduction
Chapter III: Related Research
Chapter 4: LOD Algorithm
Section 1: Basic ideas
Section 2: Data Storage
Section III: Node Evaluation System
Section IV: Grid rendering
Section 5: Generation of Grid
Section 6: Optimization.
Chapter 5: Crop
Chapter 6: Performance Test
Part II: Simplification of terrain based on LOD algorithm
Speech
Terrain rendering is the core part of an outdoor rendering engine. What is the key to achieving a large-scale terrain rendering system how to simplify terrain, abandon unnecessary rendering actions (such as seeing the rendered triangles and unnecessary details) to speed up the rendering speed. Dynamic LOD technology is undoubtedly a powerful solution.
Chapter II: LOD Introduction
When we want to have a very real scene, we are often unobsive due to the complexity of the scene itself. We must start from the geometric characteristics of the scene, simplify the complexity of the scene by appropriate methods. Level Details (Levels of Details) is raised in this case.
We know that when the object in the scene is far from the observer, they observed that they are often just a few pixels on the screen after projection transformation. We don't have to draw all the details for such objects, we can consolidate some triangles without losing the visual effect of the picture. For general applications, we usually create a model of several different detail layers for the same object, as the model of the cattle below, the highest level of detail level, while the leftmost is quite simplified. Such techniques are in terrain rendering, we also call multiple resolution Terrain.
(Figure 2.1) Of the hierarchy of cattle, picture from Tsinghua University Distance Education Network
These different detail layers can be established before the program is running. It can also be generated at runtime. We can depart from a full-detail model. The simplified operation can be divided into three types through a series of simplified operations, and simplify operations can be divided into three types (see [Reference 31]): The vertex delete, edge compression and wrap shrink technology. By doing this, we can select the appropriate model under specific applications, without having to use all detail models each time, which greatly reduces the number of scene triangles.
Terrain As a special geometric object, we have some special skills when using LOD law. Because terrain is usually a rule rectangular grid. Its simplification mode can have two types: the simplification of the rules and the simplification of the rules, the simplification of the rules is usually used for this rectangular grid with the UP-to-Down, divided into the strategy, typical with four trigemia And binary tree, they start from the minimum details level of the scene, as needed, continuously improve details. Simplification of the non-rule is usually processed using a down-to-Up method. Its implementation is usually less.
(Fig. 2.2) Simplified (left) and non-rule of simplification (right). Image from [Reference 2,12]
When implementing the LOD algorithm, in addition to how to simplify the geometry, there is a very important issue to determine whether it is simplified for an object, or how to decide which level detail model to use the object to represent objects . We need to establish an evaluation system, which is determined by this evaluation system to simplify the object to what levels. This evaluation system is usually related to perspective. The object from the perspective is usually only less details, and it is necessary to more detail. In addition, the characteristics of the object itself must also take into account. For example, a flat surface only requires a small triangle to show better. And an uneven surface is a matter of course, more triangles need to be depicted.
When rendering the terrain with the LOD algorithm, there is a very important issue is the geometric deformation problem. Due to the discardment of some details, with the movement of the viewpoint, the distant place is likely to suddenly appear, this The phenomenon is also known as "jump" ("POP"). We must eliminate this phenomenon or at least control it within an acceptable range. It is understood that the LOD algorithm is not very complicated. This paper considers that its key point can be summarized as follows:
1 data storage layout.
The layout of data in memory must facilitate the implementation of the algorithm, and it is best to reduce the number of operating system's latch interrupts, which is to reduce the number of data exchange between internal and external.
2 How to generate a continuous LOD type terrain grid
During the terrain LOD process, the two are excessive can be smooth between the regions of different levels of details.
3 node evaluation system.
This system must make the generated mesh to reduce geometric changes, try to close the picture quality to the intensive terrain. At the same time, we must also ensure real time.
Chapter III Related Research
In the past few years, it has been developed by a practical algorithm that has been quantified. Bryan Turner mentioned in his paper [Reference 32], the LOD topographic method can be summarized by three excellent papers, which are [References 12, 4 and 7], in [Reference 12], Hoppe Description A model of Progressive Mesh, which is a mode upheld. [Reference 4] The author is LindStrom, which uses a quadruple data structure that divides one of the Tesseltes and establisten the Tesellates with a four-fork tree. [Reference 7] The author is Duchaineau, which describes a ruled ROAM based on binary triangular tree structure (real-time optimized adaptive grid). Each small piece (PATCH) is a separate orthodal equilateral triangle, from its vertex to the midpoint of the opposite side, the triangular triangle is two new positive side triangles, and the segmentation is recurrent, which can be repeated until the quilt triangle Detail level to the hope. The latter two papers are all simplified patterns of rules, and the strategies of dividends are used. The Hoppe is an irregular simplified mode that adds detail to any triangle or deletes any vertices and edges.
Hoppe's law is relatively small, it is difficult to see it outside his article, the method of Lindstrom and Duchaineau is different. They represent the current two mainstream rules: based on the four-fork of LOD terrain and based on the binary tree. LOD terrain segmentation.
The above three articles are quite good and wonderful. But there is a certain difficulty and complex. More in this article is the techniques in [References 2 and 13]. Both use four trigemia ideas, this is basically the same as [Reference 4], but more simple and fast, and the vertex evaluation system provided by [Reference 2] is very fast. Unfortunately, both have no improvement of memory data layout to solve the storage problem of terrain data.
As a hot problem in the field of game development, natural LOD algorithms are from game developers, as above [Reference 13] is from 2000 GDC. At the same time, there is already a considerable part of the game successfully adopted a variety of different LOD algorithms, such as Tread Marks, Myth, Soul Ride, etc. [Reference 8] The author of Thatcher Ulrich in his article describes a four-tree-based algorithm applied to Soul Ride as a SOUL RIDE game developer (see WWW. Gamasutra.com). Unlike the algorithm of the college, the algorithm of game developers is usually more simple and fast.
Chapter 4 LOD Algorithm
1. Basic ideas are presented before the basic algorithm, in order to see, this article must do the following provisions on the terrain to be rendered: the terrain must be a square area. And the size must be. At the same time, the sampling interval must be uniform.
(Fig. 4.1) A four-fork tree of a terrain indicates that each square in the left is a node of the quadrush, and the pink is the area that the viewer can see.
As shown in Figure 4.1, we use the concept of a quadruple to describe a multi-resolution terrain. Each square in the figure is a node of the four-fork tree, and each node saves the information of a certain area, including: center point Height, from the entire intact terrain, we recursively put the constant segmentation of the terrain into four areas, the larger the depth of the divided, the higher the resolution. That is, the division depth improves one layer, and the sampling density is doubled. Figure 4.2 demonstrating the process of dividing.
Figure 4.2, segmentation process diagram, Level 1 to 2, only two nodes are divided
Figure 4.3 shows the information we have to save in a quadruple node. As will be seen in the fourth section of this chapter, how to use this information to render the terrain area represented by this node.
(Figure 4.3) Information recorded in a node, red-centered point, black is a side point, and the corner of blue. A total of 9 points.
The concept of the four-fork tree is used to indicate that there are many advantages in the multi-resolution terrain, and one of the most direct and effective benefits is cropping, as shown in Figure 4.1, where the red area is part of the observer. We can easily know that the observer can see is just a green node, and the white node does not need to consider. Therefore, we can simply discard the area that can be simply discarded in the early days of the node recursive segmentation.
With the logical representation of the terrain, we also have to establish a node evaluation system to determine when a node needs to be continued, when this node cannot be seen by the observer, the node will be directly discarded ). If a node is not discarded, it is not necessary to continue to split, then this node will be sent to the rendering API for chamber rendering.
2. Data storage
Topographic data is typically stored in a high graph, which is a two-dimensional array structure in memory. We know that the binary tree can have sequential structures and chain structures, which can also use similar sequential structures. Different is here we use a two-dimensional array rather than a one-dimensional array. We store the full resolution terrain data in a 2D array, information of the quadruple node (information of 9 top points) can be read directly in an array by an index. Also create a flag array of the same size as this terrain data array, which indicates the status of the quadruple node. If a node needs to be continued, we mark the corresponding position as 1, otherwise the mark is 0, as shown in Figure 4.4, the representation of the question mark is not accessed, (note that the value of the place where the area is not accessed is uncertain of).
Why is it easy to know if the array of Figure 4.4 is aligned. (For terrain that does not meet the size requirements, we must split it into the size of the requirements, and then splicing.) For the simplicity of the algorithm, this article only considers the size of the terrain.
(Figure 4.4) A terrain marking array () schematic, the right side is the terrain rendered with this tag array, where the black point indicates that the current node needs to continue segmentation, and the hollow point means that there is no need to continue segmentation.
The access of the two-dimensional array is in accordance with the line or by list. Taking into account the regionality of the observer movement, this paper attempts to use a two-dimensional array stored in the area, that is, the block size of the block is physically divided into a block, the size of the block cannot be too large, and it is not too small. Considering that the memory page size of Intel's CPU is 4K, the size of the block should be 64 × 64, this article uses 32 × 32 blocks. Such a storage structure can improve the storage efficiency at a certain level, reducing the number of memory wages. Methods on how to make storage structures have been introduced in many articles, [Reference 1] gives a memory data structure called clustered memory data, which can effectively reduce the performance impact of memory contacts. 3. Node evaluation system
First we have to establish a node evaluation system to determine when it will continue to segment a node. We divide this evaluation system into two parts. First, the viewpoint is related, and the other is the rough layer of the terrain itself. The cropping is theoretically part of the node evaluation system, but considering its particularity, we will introduce them in a single chapter.
(Figure 4.5) Schematic diagram of point distance factors, L is the distance from the center of the node. D is the size of the node
1 The more details we hope to be close to the observers, the less, the less. When applied to a node, the distance factor must also be considered. Therefore, in connection with Figure 4.5 we are as follows:
(C is an adjustable factor)
Where l is the center position of the node to the distance of the viewpoint, D is the size of the node, when they meet this formula, the node needs to continue segmentation. Where C is an adjustable factor, the greater the C, the more terrain details. The less detail.
2 The second second need to consider the roughness of the terrain itself, we hope that the topographic undulation is relatively rugged, and the flat place does not require us to waste too much.
As shown in Figure 4.6, first we consider the 9 top points contained in a node, where the center point 4 bots will cause certain errors in the node, and the 5 error difference is shown in Figure 4.6. DH0 - DH4 shown. The larger the value, the larger the terrain indicated by this node. In addition, we have to take into account the roughness DH5 - DH8 of all four sub-nodes of this node, as shown in Figure 4.6. (If this node reaches the topography of the highest resolution, it is not necessary to consider this step). We take the largest of the nine values (DH0 - DH8) divided by the size of the node as the roughness of this node, ie r = max (DH0, ... DH8) / D. It can be seen that the calculation of roughness is a recursive process, taking into account the computational complexity and its value of its value, we need to calculate the roughness evaluation value in advance, and store it in a two-dimensional array.
Figure 4.6, the degree of topical roughness, the left figure represents 5 roughness information inside the node, and the right figure represents its roughness information of its own roughness information and the roughness information of all of its sub-nodes.
Now we give the second evaluation formula, a roughness evaluation formula:
(For roughness adjustment factor)
For the roughness adjustment factor, the greater the degree of detail. In combination of two formulas, we get the final node evaluation formula:
The letter meaning in the formula is the same, when F <1 is satisfied, the node needs to continue segmentation.
At this point, the entire node evaluation system has been completed, but I have to mention the concept of geometric changes. Geometric clusters cause "jump" phenomenon, that is, as a change in viewpoint, some details will suddenly disappear and appear. Solving this phenomena is more difficult, currently in some articles, through special methods or even interpolated methods to eliminate or reduce geometric changes ([Reference 12], etc.), but implement such a system is difficult, calculate The cost is also very big. Second method is to project the R value to the screen space, and the obtained value is named Projected Pixel Error ([Reference 3], etc.). But by experiment, I don't think this is a good method (see [Reference 8]). Therefore, this article does not use this concept of this Pixel Error. In fact, this article does not adopt any specially eliminating geometric system, but we can reduce geometric changes by appropriate adjustment C and C2, because for a video game, as long as you can control geometric change in one acceptable It can be within the range. 4. Grid rendering
The terrain is ultimately implemented by a recursive process. We traverse the entire quartz tree. When we reach the leaves of the quad tree, when a node is no longer divided, we can draw this node.
This paper uses a triangular fan (Triangle Fan) to draw nodes, which is a natural way because a node contains a center point and several points around the center point, so that this arrangement just forms a triangular fan. As shown in Figure 4.7A.
(a) (b) (c) (d)
Figure 4.7
When we generate a grid, we also have a note that the two different resolution nodes are spliced, as shown in Figure 4.7B. We must eliminate this crack, Figure 4.7C demonstrates the method of adding a side of the stitching to eliminate cracks, Figure 4.7D uses a method of removing one side. Relatively, the first method is more complicated, but it is also more comprehensive because the resolution of the two nodes at the splicing can be different. The second method is more simple, it requires the gap between the two nodes at the splicing to no more than 1. This paper uses the second method, which will be described in more information on how to meet this requirements in the form of the grid below.
With the example of Figure 4.8, we detail how to generate a triangular fan that meets the requirements. The gray area in the figure is part of our current rendering. First, we guarantee that four corners of a node (Corner Vertex see Figure 4.3) is definitely used in a triangular fan, for the remaining four sides (Edge Vertex), check the nodes adjacent to this node, Because of the sharing of other nodes, if the corresponding neighboring node is not activated, we must skip this edge. If the neighboring node above this node is not split, we want to skip the one labeled X-tag. Bound.
Figure 4.8 Rendering diagram of the topographic mesh in which the gray node is the region where the current rendered
5. Grid generation
Before rendering the grid, we must update the four-fork tree, generate how to meet the specification quadrush, in the previous section, we have given the hierarchical difference between adjacent two nodes, otherwise the place in stitching Cracks will occur, Figure 4.9A shows an example of a conforming quadruple tree, and Figure 4.9B shows an illegal four-tree example.
(a) legal (B) illegal
Figure 4.9 Examples of conforming and unregistered four-forked
Therefore, we must have a set of rules to ensure the legitimacy of the generated quadruple tree.
Usually, we use two ways to traverse the quadrush, we generate terrain grids, the second rendering grid, while eliminating the hierarchical difference between nodes. Here, we use a more effective way to generate a quadruple tree ---- use the prophet principles to traverse the quadrush. That is, a hierarchy is generated once, and it only needs to traverse the quadruple tree once. We use two queues, and a queue saves all nodes currently being processed, and another queue saves all the next hierarchical nodes generated after processing the current level node. After processing the nodes in all current hierarchy, you can go to the next level (simple exchange of two queues). For those nodes that do not continue to segment and have reached the maximum resolution, we will send them to the rendering API for rendering.
This has a lot of advantages. First, every node that is the same as the node level is generated because of each of the nodes. We can see if all nodes adjacent to this node are to see if they exist, and if they exist, they can continue to segment this node, and they cannot split it. At the same time, we can also have enough information when they travers the quadrush, let us draw triangles. According to the method of this chapter, we only need to check the resolution than that of this node. Node. These nodes have been generated before this.
Second, we don't have to reset the status of the four-fork tree each time (empty marking array). This is very helpful to increase speed. For example, if the size of a terrain is 2048 × 2048. Then the size of this tag array is 4m. To empty a 4M size array is a small overhead at time. In the program of this article, a 2048 × 2048 map is tested, and the FPS value at the time of the annotation of the marker is 35. FPS is 78 when it is not emptied. Amazing is more than double!
Below I gave birth to a pseudo code for mesh:
Function Generatemeshbegin
Push the root node to the cur_Queue
Level = 0
Loop Not Reach The Full Resolution
{
For Each Quad-Tree Node in Cur_Queue
{
IF (Node Is Not Inside the View Frustum)
{
Simple Skip this Node
}
Else if (Level = Full Resolution Level -1)
{
Draw the node
}
Else
{
For Each Sub-Node in this Node
Check Dependcy
IF (Subnodecansubdivid () and subnodeneedactive ())
{
Push this sub node to next_level_queue
SET this sub node flag to vs_active
}
Else
{
SET this sub node flag to vs_disable
} END IF
End for
IF no sub node is activ
{
Disable this node
SET All Four Sub-Node Flag to vs_disable
Draw the node
}
Else if some sub-node is active
{
Draw the node
} END IF
} END IF
End for
SWAP (cur_queue, next_level_queue);
Level = Next Level
End loop
END FUNCTION
Function nodecansubdivid as bool
Begincheck the four neighbor node.
IF all neighbor node is activ
Return True
Else
Return False
END IF
END FUNCTION
6. Optimize
The algorithm described above is theoretically more rigorous, but slightly significantly complex, and the speed is not very fast. Below, I will optimize and simplify it.
In the above algorithm, a part of the four sub-nodes of a node are split, and the other part is not divided, it has brought a lot of trouble to our rendering, and every time we handle a node, we must check four A child node, troublesome. For this purpose [Reference 13], the following rules are given: the four sub-nodes are split when any of the four subtots of a node needs to continue segmentation. In the program of this article, this rule is further: When a node needs to be divided, all four sub-nodes are generated and put into the next level of queue.
According to this simplified idea, the tag array in Figure 4.4 will eventually be shown in Figure 4.10. Comparison Figure 4.4 right diagram, we find that there is a simplified algorithm to generate more terrain details, that is, more triangles are needed. However, due to the need to judge less, it is more advantageous to simplify the algorithm in the speed of operation.
The simplified generation algorithm of the marker array in Figure 4.10 (Fig. 4.4) corresponds to a simplified generation algorithm
Below I give the optimized pseudo code, compare the above algorithm, it looks more concise.
Function Generatemeshbegin
Push the root node to the cur_Queue
Level = 0
Loop While Not Reach The Full Resolution
{
For Each Quad-Tree Node in Cur_Queue
{
IF (Node Is Not Inside the View Frustum)
{
Simple Skip this Node
}
Else if (Level = Full Resolution Level -1)
{
Draw the node
}
Else IF (Nodecansubdivid () and nodeeedactive ())
{
Sub Divide this Node
SET All Four Sub-Node Flag to vs_ACTIVE
Push the for sub-node to the next_level_queue
}
Else
{
Disable the node
SET All Four Sub-Node Flag to vs_disable
Draw this node
} END IF
End for
SWAP (cur_queue, next_level_queue);
Level = Next Level
End loop
END FUNCTION
Chapter 5: Crop
Typically, the 3D API provides a built-in crop system, but these crop systems are after viewing and projection transform. That is, cutting is made in the projection space. Therefore, we need to create a method, crop before the average matrix transformation, and our crop system must have the ability to cut a node of a quadruple tree.
In the projection process, there is a projecting body, and we can see this object when the object is in this project body, otherwise the object will be cropped. Therefore, this projection body is also commonly referred to as viewfrustum. When the orthogonal projection is performed, the projection body is a rectangular square, and the projection body is a flat cone when performing perspective projection. Below we export our crop system as an example of a flat head. As shown in Figure 5.1, a projector consists of six faces, and a planar equation can be expressed. We specify whether a vertex is in the inside of the projection body in the direction of the project body, as long as we enter the vertex coordinates into the equation of six faces, it can be judged by the symbol of the results of the test results. The inside of the project body (all symbols are positive). Below we decentralize the equation of six faces of the projecting body in the world space.
Figure 5.1 Projecting body, the left picture is the project body in the world space. The picture is the projection body after projected transformation.
Figure 5.2 The size of the projection formation after transform.
The project body of the world space will become a form after projection transformation, as shown in Figure 5.1. This dimension is shown in Figure 5.2. We can easily get the equation of six faces of this form, they are.
We assume that there is a point (X0, Y0, Z0, 1) on a plane in these six planes, where the coordinates prior to the projection transformation are ().
This plane is equation.
The equation in the world space before projection transformation.
Then you must meet and.
If the transformation matrix is T. then
.
Combine these three equations, we can get it immediately.
Combined with the equation of six faces in the projection space, we can now easily get the equation of the six faces of the projector in the world space.
We already have the equation of tailoring body. When we need to cut a vertex, these six equations are already enough. But we have to judge the visibility of a region, we have some additional calculations. As shown in Figure 5.3, the relationship between an object and the projection can be roughly divided into: surrounding, surrounded, intersecting, and separation. The largest light blue rectangles in the figure surround the entire projector. The dark green small rectangle is completely surrounded by the projector. Light green rectangles and projectors intersect. These three cases can be seen. The remaining red rectangles is separated from the projection body, only it is completely invisible.
Figure 5.3 Relationship between objects and projection body.
When the visibility of the node is handled, due to the irregularity of the node. We also need to introduce the concept of envelop. The so-called surrounding body is to use a relatively simple geometry to meter another more complicated geometry, so that it is just a geometry. Compared to the appropriate envelopes have rectangles, squares and spheres. The sphere treatment is the most simple, but the approximation is also the worst. We build a surrounding body for each node. As long as we test this enclosure, we can decide a visibility of a node, because the enclosure is certainly greater than this node, so we can guarantee that there will be no visible nodes are cropped in projection. Outside of body.
Chapter 6: Performance Test
1. Memory consumption: The memory consumption of the LOD algorithm this article is only related to the size of the terrain, and this relationship is linear. For each vertex in the terrain, the information we need is as follows: Height information (1 bytes), roughness information (floating point, 4 bytes). Four trigem information (1 bytes). So each vertex requires 6 bytes to save. For a 4097 × 4097 map, we need 96M storage space, which is almost today that the RAM size of the PC should be calculated in GB, it should not be a big problem. At the same time, it is considered that this article is a static data structure, and there should be many optimization rooms in memory consumption.
2. Speed and Image Quality: The algorithm herein is not controlled by constant speed, nor is therefore control of constant triangle numbers. The number of triangular triangles is related to the size of the terrain itself in addition to the size of C, C2. In general, C = 3, C2 = 30 can achieve a better effect. When C = 4.5, there is basically no problem with geometry. And FPS is more than 120 (using detail textures), and the speed is completely required. 3. Example Test: I have selected the map size of 2049 × 2049 and 4097 × 4097. The map uses Photoshop's layered cloud function, and modifies the map tool with this article presentation. Texture is mixed for regional ternate texture. The details of the texture are closed (ie, only one clipphory mapping). The test platform is Intel Celeron II 1.2G, NVIDIA GFORCE 2 / MX400, 128M RAM. The operating system is Windows 2000SP2. The graphics card driver version is 4345 official release. Note that the driver must be installed correctly, and the driver provided by Windows2000 does not support OpenGL.
Table 6.1: 2049 × 2049 Map of rendering results.
The height map for test is 2049 × 2049. Use two-color mode rendering. Used to demonstrate the generated triangular fan, the center of the triangular fan is red, the point around it is white. The center is blue triangle fan indicates that this place has reached a full resolution. C = 25, C2 = 2.5. Triangle number 6529. View distance 600. FPS = 167 c = 50, C2 = 5.0. Triangle number 11192. View distance 600. FPS = 138 c = 25, C2 = 2.5. Triangle number 2174. View distance 600. FPS = 237. Grid coloring mode C = 50, C2 = 5.0. Triangle number 13221. View distance 600. FPS = 124. Grid coloring mode
Table 6.1: 4097 × 4097 Map of rendering results.
The height of the use c = 35, C2 = 3.5. Triangle number 10877. Vision distance 6000. FPS = 137
The speed of this algorithm is basically related to C, C2, and Figure 6.1 is the relationship between these two factors and speeds and triangles. C = 35 in the test data in the figure, C2 from 2.5 to 10.0. Since these two are visible, the speed and triangle is roughly a linear relationship.
Figure 6.1 The relationship between triangle numbers, FPS and C × C2. The red line is an FPS value, the green line is a triangular quantity
When you select 4097 × 4097 map, there is no change in the operating speed of the algorithm, as the topographic area that needs to be rendered is limited to the inside of the visitor. When a map of 8193 × 8193 is selected, the loss of the memory shortage caused by memory is more serious, and if it is basically unable to run under Windows 98.
Part III: Generating technology of true sense scenes.
Chapter 7: Sky and lens glare
Chapter 8: Bulletin Board Technology
Chapter 9: Details of the surface
Chapter 10: Jingjing
Chapter 11: Motion Blur
Part IV: Conclusions and Prospects
appendix
A: Generation of terrain data
B: Reference
the third part
Generative technology of true sense scene
Speech
An outdoor scene rendering engine must have a real sense of rendering, including more details, rendering the surface vegetation, etc., or even a variety of weather effects. All of these can make the scene look more natural and more realistic. In the following chapters, this article will implement several major items.
Chapter 7: Sky and lens glare
1. Sky: If you can't see the sky in an outdoor scene is an unimaginable. Blue sky white clouds can make the palens in the field of view. The sky covered with dark clouds can make the scene look more depressed. Usually, the realization of the sky has a circular and box-shaped. The circular sky has a lot of advantages, but it is more complicated, especially when mapping textures. The box-shaped sky is very simple. Its main disadvantage is that the sky will have a very obvious deformed when the sky is near. There are many articles about the generation of Sky Geometric models. If [Reference 33] is a good sky, making a tutorial. Figure 7.1 Schematic diagram of a circular sky. The left is a hemispherical sky, and the upper arc top sky is on the right. Image from [Reference 33]
The sky is the most difficult thing to create texture, of course you can find a photo of the sky, but this sky is static. Secondly, it is used to dynamically generate the texture of the sky using an algorithm, and the algorithm that generates this texture is usually used using Perlin Noise. An exciting article on the generation of the sky is available at http://freespace.virgin.net/hu.elias. This method is very good, but the deadly shortcomings generate a large texture is not fast enough, although it can reach a certain real-time, the speed is very slow when applied to the entire engine. The final method is to make textures with the video files of the sky. Although the speed is not very fast, it is more fast than the speed of generating textures with Perlin Noise. (The demo program of this article comes with a demonstration video texture, which uses DirectShow to play the video file, map the play results as textures to the geometry.)
2. Lens glare: People who have a little photographic experience know that when we align the camera's lens, there will be halo phenomena, which is also called a lens glare. The size of the halo is related to the lens. When we placed a sun in the scene, it would have an amazing effect if this halo phenomenon is realized.
The sun simulation is very simple. As long as you place a circular object in the specific location of the scene. The lens halo requires some additional processing. First let's take a look at a glare. As shown in Figure 7.2.
Figure 7.2 Lens Glare Schematic, the left picture is a renderings generated by Photoshop, and the right figure is a schematic diagram of its components.
The lens halo consists of a series of aura, all of which are arranged on a straight line. This line is determined by the position of the luminescent object and the center of the screen. The shape of these aura has a multi-middle manner, typically used as a radiationed figure as a light of the luminescent object, and the annular image of different thicknesses is used.
We need to use Alpha Blending to combine these aura in the scene when combining these aurans. Usually we use the Alpha Blending formula
All of the aura is drawn into a scene as a two-dimensional object. Therefore, the position of the light-emitting object on the screen needs to be calculated by itself, while calculating the position of the luminescent object on the screen, we can also obtain the information of the Z-BUFFER of this position to determine whether the luminescent object can be seen when it can be seen. When you are not visible, the halo is naturally invisible. The figure below shows an example of a lens halo generated by the above algorithm.
Figure 7.3, the lens flare schematic, the left figure is an independent effect, the right image is the effect picture after combining the scene. Image from this article Demo
Finally, it must be noted that the glare must be drawn after all the objects in the scene are drawn.
Chapter 8: Bulletin Board Technology
BNOARD is an object that is always moving toward the observer. Usually it is a polygon. Outside scenarios usually have some objects, such as objects such as trees, columns, or the details are very many to be expressed as models, or they are both the same as any one direction (such as pillars). We simply expand these objects with a polygonal plus texture map.
With Billboard to show that the trees are very effective, the famous simulated driving game NEED for Speed 5 is implemented in this technology. The trees we have seen are actually just a rectangle, as shown in Figure 8.1, the rectangle can rotate around a shaft, so that the rectangle always facing the observer. Therefore, no matter which angle you go, you can only see the front of the rectangle, and you won't see the flat side. Figure 8.1Billboard schematic illustration of trees
In addition, Billboard is usually used in the particle system, because particles in the 3D scene should always be opposed to the observer. A typical example of this application is Quake III and Unreal's flaming flame.
Billboard's implementation is in two places, one is the pattern of texture maps, which is usually used in transparent maps, and we can use Alpha Test's functionality in OpenGL / Direct3D, in OpenGL / Direct 3D. . Alpha blending features are generally used for the desired particle system. The second key place is how to make one side of the polygon is always toward the observer, as shown in Figure 8.2.
Figure 8.2Billboard rotational angle calculation, where red arrow is the head of the camera, the blue arrow is Billboard original, Z is the central axis of rotation
We only need to rotate the polygonal angle R. The size of the angle R can be calculated using the following formula:. The central axis of rotation can be calculated by the following formula:.
Chapter 9: Details of the surface
The surface details involved very much, the main aspects: ground texture, ground shadow (brightness map).
1. Ground texture is relatively large due to outdoor scenes, usually requires a large texture to express the details of the ground. But too much surface texture takes a lot of texture memory, and the two graphics cards are not necessarily support.
Methods to solve this problem typically have two, one is to split large textures into small units, dynamically load required textures (this technology is also known as Texture Tiling, see [Reference 24]). Another method is to use multiple texture maps, which use a larger texture to express the topography of the terrain, and then use a small texture and the first topographic modulation (Texture Blending) As a result, the second texture usually uses a loop map (ie, the U, V coordinates of the map is greater than 1). Different detail textures can express different landforms.
In contrast, the second method is more simple, the effect is better, and the only thing to note is where different detail texture is transitioned. To mix the textures of the transitions in advance, otherwise, in different details, the transitions of the texture will be very hard, very ugly.
Figure 9.1 Detail Texture Schematic, the left figure is not using the detail texture, the right picture is used in the details. Image from this article Demo
2 Brightness Figure In addition to the illumination and shadow effects in a 3-dimensional scene, it can improve the real level of the scene.
The calculation of the illumination needs to be specified for each triangle, the dynamic calculation method is too slow, and the in advance requires a large amount of additional storage space, and the memory method in the LOD algorithm is not an easy task. Another problem is a shadow problem, and the generation of real-time shadows has always been a difficult point in graphics. Not to mention under the outdoor scene, the shadow that is dynamically generated in real time is basically impossible.
One of the two problems is to use a brightness map, then modulate the texture of the brightness map and the ground to obtain the final surface texture map, this method does not require additional calculation at the time of operation, no additional storage.
When calculating the brightness map, we need to specify a location of a light source to the scene, which is usually the position of the lens halo luminous body (sun). The brightness of a point is determined by the triangle of all shared paths. The brightness of any of these triangles is calculated as shown below: Figure 9.2. Brightness graph calculation, where R is a triangular method vector and an angle of the light direction
According to common sense, only the face towards the light source will be illuminated. Assuming that the intensity of the ambient light of the full scene is IE, this is determined by the following algorithm: in Figure 9.2:
IF COS (r)> 0
I = COS (R) × (1 - IE) IE;
Else
I = IE;
The calculation of shadows is as follows:
Figure 9.3, a shadow schematic, where A is in the shadow zone, B is directly illuminated
When it is determined whether a vertex is in the shadow area, we need to check the vertices between this vertex and the light source one by one. Verify that the light of the light source is blocked by the vertex, as shown in Figure 9.3, the light of the light source cannot be directly taken directly to A, so A is in the shaded area. If a point is in the shadow area, its brightness is directly equal to the brightness IE of the ambient light. Otherwise, its brightness is determined by the algorithm exported by Figure 9.2.
Finally, we also need to modulate the calculated brightness map and texture, this paper uses the simplest way, which is the component of the respective colors of the corresponding point on the luminance value (0-1.0).
Chapter 10: Jingjing
The images that are usually used with computer rendering are very sharp, regardless of the far or near objects look very clear. But the truth is not the case, and the far from the observer seems to be blurred, rather than the object on the focus of two eyes observed.
The method of achieving a second phenomenon is described in detail in [Reference 24], and it is not very necessary to achieve this effect, and the impact on the rendering speed is also great. It is not introduced here. As for the first phenomenon, the simplest and effective method is to use fog. The details about the fog are introduced in almost all OpenGL, Direct3D books.
The calculation equation of the fog usually has three, which is recommended by this article. Another advantage of using the fog effect is that the distant (located outside) triangle cut is not to generate a "jumping" phenomenon, because the distant scenery has completely become the color of the fog. It provides an infinite imagination of an infinite perspective. The figure below is a legend using the fog and does not use the fog effect.
Figure 10.1 The left picture is open the fog effect, the right picture is turned off the fog effect. Image from this article Demo
Chapter 11: Motion Blur
Motion blurry a dynamic effect, it is due to the exposure of the film of the camera for a certain period of time, if there is a change in the exposure process, a fuzzy effect is generated on the film, which is called motion blur. Motion fuzzy phenomenon is very common on movies and photography.
The motion blur is very important in the scene of sports. You will find that if you lack the vague blur will bring serious distortion, look at the computer animation that doesn't use motion blur, you will find that the object is quickly moved, the picture lacks coherence and realism . In the analog driving game NEED for speed, the ground will change the blurry when the racing is high-speed, giving people a feeling of blowing.
Figure 11.1 Motion blur schematic diagram. Image from [Reference 19]
Methods to achieve motion blurring have been described in detail in [Reference 19]. In this article, the author used time sampling way to achieve motion blur, this is a precise motion blurred implementation, usually this Methods To implement the "Accumulation Buffer", the use of cumulative cache can be found in OpenGL, Direct3D books. Under normal circumstances, we can achieve more ideal motion effects as long as you accumulate 3 to 5 times, but this very shortcoming is to seriously reduce the speed of operation. When we take N times, the running speed is not carried out. 1 / n of motion blur. Such a price cannot be accepted in a game program. As a secondary solution, we can save the previous rendering results, then weaken after a certain proportion weaken into the current rendering result. Assuming that the current rendering result is P1, the previous frame is P2, and finally the current frame is P. The mixed formula is as follows: p = (1-f) × p1 f × p2. Where f is a fuzzy factor, the greater f, the more obvious the motion blur. This approach only needs to render a scenario, which is not very much on the operating speed. This method is given below in OpenGL:
1. First build a sufficiently big texture,
2. Rendering scenes into the frame buffer.
3. Set the texture of the pre-previous frame content to the current texture.
4. Draw a rectangle as large as the viewport, mixing this rectangle in the formula given above and the rendering results in step 3 together.
5. Copy the mix result into the texture object (GLCOPYSUBTEXIMAGE).
6. Repeat steps 2-5 to draw the next frame.
Since some OpenGL drivers do not support direct rendering to the texture, it is more troublesome to implement with OpenGL and the effects of speed are more affected. In Direct3D, you can render the scene directly into the texture, which is small in the speed, which is small, but also simple, but the basic principle is still the same, and details will not be described here. The following figure is an example of using this method.
Figure 11.2 Motion blur. Image from this article Demo
Part IV: Conclusions and Prospects
This article has basically implemented a rendering core part of an outdoor 3D gaming engine. Although the algorithm provided is not very accurate, the speed is very fast, and the DEMO implemented by this article algorithm can run very smoothly on the current popular personal computer. After adding the technique of the third part of this article, the picture quality is greatly improved. The figure below shows the screenshot of the demo program of this article. All effects have been opened.
But there are still many problems that are in a hurry, mainly include the following:
1. Memory Management This article uses the memory data structure that considers the problem of memory is not very good at certain extent, but the effect is not very good. Since the map is loaded as a two-dimensional array, it is linear structure. The redundancy of the data is relatively large. It can be considered to improve the use of chain data structures.
2. Geometric changes.
3. Unlimited repeating map A map is also larger, and the current mainstream game is a map loop. That is, it will return to the beginning along one direction to the edge of the map. Can't walk the end of the map.
4. The existence of water in the water surface is normal, such as lake, small river, etc. The water surface should be refurbished around the scene, and the reflection is generally drawn twice in the template buffer, but this is very large for the overhead of the outdoor large scene and is also difficult. We need a way to simulate the surface of the water surface.
5. Various weather effects This article is simply simple to achieve the sky, there are many phenomena in the real nature, such as rain, lightning, snow, wind, etc. Plus these weather effects will make the scene more change.
Part 5: Appendix
A generation of terrain data
There are two ways to generate terrain data:
First, use a random function called Perlin Noise to generate a high and low undulating terrain. Perlin Noise is used to generate a terrain, which is particularly effective in [Reference 14], in this approach.
The second method is fractal, usually also called the Diamond-Square algorithm. This approach is more effective when used to generate several mountains. About this algorithm can find a detailed introduction at www.fractal3d.com.
B reference and resources
references
[1]. XiaoHong Bao and Renato Pajarola LOD-based Clustering Techniques for Optimizing Large-scale Terrain Storage and Visualization "Department of Information & Computer Science University of California .Irvine.
[2]. Stefan R? Ttger, Wolfgang Heidrich and Philipp Slusalleck, Hans-Peter Seidel Real-Time Generation of Continuous Levels of Detail for Height Fields University Erlangen-Nürnberg
[3] P LINDSTROM AND V.PASCUCCI Visualization of Large Terrains Made Easy Lawrence Livermore National Laboratory August 7, 2001
[4] p.lindstrom and v.Pascucccci Terrain Simplification Simplified: a General Framework for View-Dependent Out-of-Core Lawrence Livermore National Laboratory May 8, 2002
[5] P.Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust and Gregory A. Turner Real-Time, Continuous Level of Detail Rendering of Height Fields In SIGGRAPH 96 Conference Proceedings, pp. 109-118, Aug 1996.
[6] Reinhard Klein and Andreas Schilling Efficient Multi-Resolution Models for Progressive Terrain Rendering
[7] Mark Duchaineau, Murray Wolinski, David E. Sigeti, Mark C. Miller, Charles Aldrich and Mark B. Mineev-Weinstein ROAMing Terrain:.. Real-time, Optimally Adapting Meshes Proceedings of the Conference on Visualization '97, pp 81-88, OCT 1997
[8] Thatcher Ulrich Continuous Lod Terrain Meshing Using Adaptive Quad-Trees Www. Gamasutra.com
[9] Luis Sempé, Terrain Rendering Using Heightmaps March 2002, http://www.sphergames.com/[10] Renato Pajarola, Eth Zürich labei Terrain Visualization Using The Restricted Quadtree Triangulation
[11] Wang Hongwu Dong Shihai "a Dynamic Multi-resolution Terrain Model" "Peking University Computer Graphics Research Institute
[12] hugues Hoppe Smooth View-Dependent Level-of-Detail Control and ITS Application To Terrain Rendering Microsoft Release
[13] Louis Castle, Jonathan Lanier and James McNeill Real-Time Continuous Level of Detail (LOD) for PCS AND CONSOLES TECHNICAL Presentation GDC 2000
[14] hugo perlin noise
[15] China Game Developer Network "Billboard Technique Details"
[16] China Game Developer Network "Billboard"
[17] China Game Developer Network "Based on the invisible object elimination algorithm included in cone"
[18] China Game Developer Network "OpenGL Render into Texture" (OpenGL RENDER-TOTURE)
[19] China Game Developer Network "Motion Blur" (Motion Blur is seen in Hugo Home)
[20] Michael Tanczos The Art of Modeling Lens Flars http://www.gamedev.net/
[21] Alan Gordie Lens Flare Tutorial http://www.gamedev.net/
[22] Jackie Neider, Tom Davis and Mason Woo "OpenGL Programming Guide" OpenGL ARB AddSION-WESLLY
[23] "OpenGL Super Collection" People's Posts Publishing House
[24] Tom McReynolds Programming with OpenGL: Advanced Rendering SGI Siggraph `97 Course
[25] Microsoft DirectX SDK Document
[26] MESA LIB 4.03 Source Code
[27] Microsoft MSDN -OpenGL Section
[28] OpenGL Specification (Version 1.1, Version 1.2, Version 1.3 Version 1.4)
[29] "Computer Graphics Algorithm Basic" Machinery Industry Press
[30] Sun Jiaguang, etc. "Computer Graphics" Tsinghua University Press
[31] Tsinghua University Distance Education "Chapter 4" Real Time True Demporative Techniques "Chapter 4
[32] Bryan Turner (Dreams WOO Translation) "Roam Real Time Dynamic LOD Terrain Rendering"
[33] Luis R. Sempé, Sky Demo http://www.spheregames.com/
Resource
Nehe's opengl tutorials nehe.gamedev.net
FLIPCODE www.flipcode.com
Gametutorials: http://www.gametututorials.net/
NVIDIA: Developer.nvidia.com
OpenGL: www.opengl.org/mesa: www.mesa3d.org
Directx: www.microsoft.com/directx/
GameDev: www.gamedev.net
Chinese Game Developer: Mays.Soage.com
China Game Resource Network: www.gameres.com
