three-dimensional model

Octree three-dimensional data structure

Using octree to represent three-dimensional shape can be regarded as a generalization of quadtree method in three-dimensional space or an improvement of three-dimensional voxel array method. The logical structure of the octree is as follows: Assuming that the object V to be represented can be placed in a sufficiently large cube C, the edge length of C is the n-th power of 2, and the object VC, its octree can be defined by the following recursive method: each node of the octree corresponds to a subcube of C, and the root of the tree corresponds to C itself. If V = C, then the octree of V has only the root, if V is not equal to C. Then C is divided into eight sub-cubes, each of which corresponds to a sub-node of the tree root. As long as a sub-cube is not completely blank or occupied by V, it will be divided into eight equal parts, and the corresponding node will have eight sub-nodes. Such recursive judgment and segmentation are carried out until the corresponding cube of the node is completely blank or occupied by V, or its size is predefined voxel size, and a certain “rounding” between the voxel and V is made so that voxels are either considered blank or V occupied。

Nodes on the octree can be classified into three categories：

1. Grey Node， the corresponding cube is partially occupied by V；

2. White Node, the corresponding cube has no V content；

3. Black nodes, the corresponding cubes are all occupied by V。

The latter two types are also called leaf nodes. Because the structure of octree is very similar to that of quadtree, the storage structure of octree can follow the quadtree method. According to different storage methods, octree can also be called regular, linear, one-to-eight octree and so on。

Rule octree

The storage structure of the octree is to represent each node in the tree with a record of nine fields, one of which describes the characteristics of the node, and the other eight segments are used as pointers to its eight sub-nodes. This is the most common storage structure used to represent tree data. There are many defects in regular octree. The biggest problem is that pointers occupy a lot of space. Therefore, although this method is very natural and easy to master, it is not ideal in the utilization of storage space。

Linear octree

Linear octree pays attention to how to improve space utilization. It traverses the octree in a predetermined order and converts the octree into a consistent linear table. Each element of the table corresponds to a node. Linear octree not only saves storage space, but also is more convenient for some operations. But the cost is a loss of flexibility, as shown in Figures 3-18 and 3-19。

A pair of octree

A non-leaf node has eight child nodes, which are marked as 0, 1, 2, 3, 4, 5, 6, 7 for determination. As can be seen from the introduction above, if a record corresponds to a node, the eigenvalues of the eight sub-nodes of the node are described in the record. The pointer gives the storage place of the records corresponding to the eight sub-nodes, and implicitly assumes the storage order of the records of these sub-nodes. That is to say, even if a record is unnecessary, the corresponding storage location must be free there to ensure that records of other peer nodes are not mistakenly accessed. Of course, there will be some waste, unless it is a complete octree, that is, all leaf nodes appear at the same level, and the nodes in all layers above that level are non-nodes. In order to overcome this shortcoming, one is to increase the computational load, that is, before accessing the corresponding node records, first check its parent node records, look at the previous several leaf nodes, so as to know how to access the required node records. The storage requirement of this method is undoubtedly the smallest, but it needs to increase the amount of calculation; the other is to add some information to the record, so that the calculation work can be appropriately reduced or more convenient. For example, three bytes are added to the original record, one is divided into eight, and each sub-node corresponds to three, representing the offset of its sub-node in the pointer pointing area. Therefore, in order to find the record location of its sub-nodes, it is necessary to multiply the position pointed by the pointer with the offset value (0-7) by the number of bytes occupied by the record, so that the description of a node is recorded as follows：

The octree obtained in this way is the same as before, except that there are three bytes more before each record。

Display of three-dimensional data

Three-dimensional display usually uses cross-section, equidistant plane, multi-layer plane and three-dimensional block diagram and other forms. Most of the three-dimensional display technology is limited to the two-dimensional form of CRT screen and drawing paper. People can observe the three-dimensional shape of geographical phenomena, but they can not be analyzed as discrete entities, such as three-dimensional can not be measured, stretched, changed shape or combined. 。 With the help of three-dimensional display technology, contour maps, cross-sectional maps, multi-layer planes and perspective maps can be formed by discrete elevation points, which can be completed manually at first, and quickly and efficiently by various computer programs. Figure 3-20 shows a representation of three-dimensional data。