background:
This is the 3D Engine dev. Series Tutorial of Delphi 3D. (Www.delphi3d.net)
This Site is written and maintained by tom nuydens.
From the basic view system to advanced PVS (Possible Visible Set), it has an introduction. It is difficult to write deep shallow, don't think Tom Nuydens is a legendary figure, he is 22 years old, and he has just graduated from University. I really don't roll rolling!
My translation:
I have recently seen Computer Graphics, I found this station, I found it is useful, so I am translated by Learning by Doing && Share && Just For Fun (Welcome to Id), and add some of my understanding and some Expand (Maths, Some New Figures etc.). So, The Original Delphi 3d Engine Dev. Tutorial Series Copyright by Tom Nuyden and this Translation and the Expanded Part Copyright by John_cash:). (Under the bottom of the picture is painted by the picture board, bitter? :( SO , All Rights Reserved)
This is a tutorial for 12 articles ... long ...
==============================================================================================================================================
Issue 2: Visibility Determination Algorithms (visibility)
Visibility discrimination - 3D Engine core
What is visibility discrimination?
3D is drawn to avoid redrawing as much as possible, as can be seen in the six-sided sonas above, so the remaining of the remaining (back face cooling) will be deleted before the remaining three faces. This is just a simple example. It is imagined. How many faces in Quake, don't use VD, even if you use hardware drawing, you can understand the importance of visibility judgment.
The policy selection of VD will greatly affect the efficiency of Engine. Obviously, if every point is redrawn, your engine will spend a lot of time to draw the invisible surface, resulting in the loss of efficiency; on the other hand, if you are perfect, even if you are not willing to redraw, This is really important when SOFTWARE RENDERING is to weigh the VD algorithm and partially redraw. More than just drawing, VD is needed, and the viewing transformation, referring to the World Coordinate system to the user coordinate system), it is necessary to minimize the surface that needs to be changed, of course, we don't need to change those look. No face. There are many ways to delete invisible polygons. The following is discussed from the most basic beginning, and some advanced technologies will be involved.
Basic algorithms
Excluding the most direct and simpler way to remove the polygon, the easiest way is back face culling. Rear deletion Based on the following assumption: "The polygon is a closed polyhedron, and only one side is visible." Imagine the surface of the six-sided body, what is the characteristic of an invisible face? ---- The normal line of the plane and the user's line of sight is greater than 90 degrees. It can be used in a point as shown in the figure, and when the order result is <0, it is not visible to the surface.
The next step is to do, delete the face behind you. How to delete? All vertices of Z <0 under the user coordinates.
Is there anything to do? of course. The final step is to delete the viewfrustum.
In the picture, the gray is view frustum, and the foreigner is called View Pyramid, which is surrounded by six four sides. Among them, dark gray triangles 1, in View Frustum, not deleted, and 2 will need to be deleted. Specifically determined using a flat equation:
S (x, y, z) = ax by CZ-D
If your linear algebra has not been forgotten, it should be understood that (a, b, c) gives the plane normal, S (x, y, z) result is (x, y, z) to a plane distance . OK, bring all vertices of the polygon to be judged to S (X, Y, Z), depending on the positive, negative, 0 values, it can be judged outside, within, within, and on (this is related to the definition of the polygonal normal) Thus determining whether the polygon is removed.
Note: If you really have forgotten, I will push it:
The plane of the vector form can be remembered: n * (x - p) = 0 n is the normal, P is the plane.
Bring x (x, y, z), n (a, b, c) into, obtained: AX by Cz = n * p.
Among them, * is a bit.
Octrees (top tree)
The above deletion algorithm, the efficiency is still not high, it is necessary to use the advanced point technology. The top tree, itself is the 3D version of the binary tree. The division of space recursive is used to set the organizers (similar to BSP (BINARY SPATIE Partition). For example: (see from the Z axis)
If you can determine if a sub-space is not visible, all polygons in this space can be deleted. Trouble is, for the polygons in the visible sub-space, Octree does not provide a method of visibility, if it is too thin, it is likely to be disappeared, recursively, and decline, ... .., still want to debug?) . In addition, Octree's division method is clearly suitable for right coordinates. If you use geometric coordinates, it may not be so easy. :) Portal Rendering (entrance)
What is portal?
When the space is divided into a convex polyhedron, it is possible to cut it. That is, this face is divided into two when the original child space is divided, and this is a portal.
In the figure, the two sub-spaces are connected through a portal (similar to the role of the door). The picture shows that Portal is a polygon that does not need to be drawn and does not block the line of sight.
Portal Rendering is more than the basic algorithm is deleted in the VIEW FRUSTUM. Since the obtained subspace is a convex polyhedron, there is no sorting problem of polygons (imagine, standing in a convex ploose, of course, the order of drawing is not related, because all faces are visible). The algorithm starts from the area where the observer is located, plots all polygons, and if there is portal, the portal is cut into the visual body, and the area of the Portal connection is drawn. When two portals meet, you need to cut the latter to the previous portal. Figure:
Of course, if a Portal is finally invisible, the area it connects is not visible.
Dynamic LOD
Dynamic LODs are often used in the genamic LOD (Dynamic LOVEL OFETAIL), which is used to simplify the drawing of the distance. For example, in the Delta, the terrain in the distance will be coarse, and you will get close, the terrain will become more and more detailed (more and more triangles). You can usually be implemented in Octree, as shown in the figure:
(This picture is from: www.gametutorials.com)
Another similar technology called: Real-time tessellation refers to the model uses different fineness to accommodate different requirements.
In fact, both techniques are used to reduce the number of polygons (/ mass) to be displayed, rather than visibility.
Conclusion
This is a few common algorithms that require more detailed content, you can go to flipcode.com GameDev.net Gamasutra.com Gametutorials.com. Of course, an Engine can be mixed with multiple technologies, such as BSP and Octree mix, Octree and Portal mix, etc ..
Next time: Portal Rendering. (The famous "Duke Nukem Forever" is always the portal engine.
