Chapter 5. Fundamental 3D Objects
After a long play (rpwt -_- |||), it finally came to the core technology. This is the final chapter of the basic class (the basic class is not finished when PART I is finished?)
Spatial segmentation is to divide WORLD into several parts, then determine which partial engines should be rendered, and which parts are not required. It can also be used to determine the details of each portion (that is, what level of detail is rendered). In GAIA, spatial segmentation is achieved with a quadruple tree.
The Motivation Behind Scene ORGANIZATION
Any render pipeline is to determine which objects need to be rendered, which is the motive for us to spare. Check if an object is visible, it is to view this object is in the Frustum. The last time someone asked in BBS: What is the triangle thing? I immediately ft.
The object is visible as long as any part is in FRustum. A relatively simple method is to load objects with a border of BOX, then an object can know if it can be seen (6 faces of Box).
Each face in the cone can be seen as a plane in the space. Each is used in a normal (pointing to the interior of the cone). If a part of an object is in the direction of these half-plane, it is visible.
There is a simplified method: divide a large space into a small rectangle, called Sector. Then just determine if the sector is visible, if you can see, then the objects you have in the sector are sent to rendering.
This method has achieved efficiency, but throws off the accuracy. Because the Object in many visible sector is also invisible. Then there is an improved method: all the sector intersecting the Frustum boundaries must further test each Object.
If the object is scattered, it is still equivalent to TEST all Object, which is not efficient. Then continue to improve: divide the sector into large blocks, then subsequently divided into a tree. If the parents are not visible, then the child must be invisible. If the parents can be seen, we will continue to Test their children.
The Basic Quadtree
Four-tree and top trees are treated to express space relationships. The four-fork tree is used for 2D, divided by a rectangle into 4 equals, each can continue to subdivision. The top tree is used for 3D, dividing each cube into 8 equivalents, and then continues to subdivide.
Because the vertical height in GAIA is relatively low, it can be seen as a plane, which is also the reason why you don't have to use itree. However, we can extend QUADTREE to make it a pseudo 3D tree.
In theory, the number of nodes in Quadtree is minimized. That is to say, if there is no object on a branch, it is null, and the nodes below it are ignored. But so although it saves space, it lacks dynamic efficiency. Once there is a moving object, add the operation of the delete node is too frequent.
In order to avoid this, GAIA is used in GAIA to represent the quadtree of all nodes, even if the NULL node is also expressed. This will not consider adding deletion nodes, but it consumes a lot of memory.
In fact, Quadtree should be able to see a 2-dimensional line segment tree. Find the ALGO of an object as follows:
STEP 1. Check all children of the current node. If there is no child, Goto Step 3. Step 2. If the object is fully enclosed by one of the children's nodes, the child node is used as the current node, then Goto Step 1. Step 3. This object is this node, add, then exit. ENHANCING THE QUADTREE
Because the process of finding the added node is time consuming, if it is a very dynamic game, then most of the time is used to find the node. Therefore, if there is a method that directly determines the position of the node insertion. Fortunately, Matt Pritchard provides us with a way. (In order to understand this
If each layer of a quad tree can be expressed in a two-dimensional array, then each node should be said:
Node [level] [x] [y]
In addition, there are two restrictions on this method, but Pritchard said that these are not limited:
1) The coordinate axis must be a power of 2, such as 256x256. If it is not, it can't be used? Hey, just get it.
2) The number of trees should be determined in advance. This is determined in advance for many cases. The maximum number of layers is MaxLevel.
For an object, how do I determine its Level and XY value? For example, our coordinates are 256x256, MaxLevel = 7, there is a rectangular object, the upper left corner is (190, 110), the lower right corner is (195, 125). Then we need to calculate two quantities, one is a value different from both ends on the X-axis or, one is to take the value of both ends on the Y-axis or. as follows:
10111110 (190) xor 11000011 (195) -------------------- 01111101
01101110 (110) xor 01111101 (125) -------------------- 00010011
At this time, check the position where their highest bit is located, then use the maximum number of layers to determine the number of layers on a particular axis:
Levelx = maxlevel - highbitset (1111101) = 7 - 6 = 1LEVELY = MaxLevel - HighbitSet (10011) = 7 - 4 = 3
Then the number of this object is their smaller:
Level = min (levelx, level) = 1
This determines its number of layers. The following is a need to determine its location. The location is to use any one of the object to right, the number of digits of the right shift should be:
Shiftbit = MaxLevel - Level 1 = 7 - 1 1 = 7
Then, the value of XY is calculated (any point taken is the point of the upper corner of the object, X1 = 190, y1 = 110):
X = x1 >> shiftBit = 1Y = Y1 >> shiftBit = 0
Then the node to which this object belongs is Node [1] [1] [0].
They are all operations, I feel that it is effective ...
Adding Another Dimension To The Quadtree
If you want to give a z-axis, you should use Octree. But this kind of efficiency is a big discount (Quadtree is a low complexity of Octree). Then, use a relatively compromised approach to establish a pseudo Z axis, which is 32 layers on the Z-axis and describes 32 bit. If an object is on the 4567th, its height is 11110000 (both the first 24 bits are 0). So if you insert an object, use the height domain of the or lower node. If the test object belongs to a specific layer, the AND is a bit (getting a non-zero value).
It is also an operation, it seems that the engine is indeed a pursuit of efficiency.
Fast Quadtree Searches
To find a 3D volume, you have to convert it into a 2D Shape and a 32BITS height and then use Shape and this high look.
For example, there is a given volume, then check the root. If the z of this node includes this volume of Z, then check it four children. This has been investigated, and if an Object of this node is interspersed, add this node to a LIST behind. This Link List is the last result when the lookup is completed.
In addition, if the Z-Mask of a node changes, its ancestors should also adjust accordingly.
Slow Quadtree Searches
Is there fast? Slowness means more comparison and operation. In fact, the main reason for this is to find the item collection in cones.
The shape of the cone is not ruled, it is a cone. Then you can use a box to wrap the cone, then use the Box Fast Search to find this efficiency, but you will find a lot of objects that don't belong to the cone but belong to BOX. So, in order to avoid this, use the cone to check it.
This is optional. If you use fast rendering, you can use FAST Search, because more objects can not be too much time. But if you use a lot of Shader as advanced rendering, it is also good to use a Slow Search because it saves more rendering times.
I have learned this chapter, at least understand what is Quadtree, although I haven't used it, but I have already felt it. Originally, this chapter didn't need to watch so long, just in this week, I suddenly had a big illness, so I was delayed for a long time, and I finally finished the rest of the rest. Basic knowledge is finished, and later enter the real terrain study.
