Application of octree algorithm in three-dimensional blanking of packaging CAD

First, the overview of three-dimensional graphics blanking

Modeling is the basis of three-dimensional computer graphics processing, and the elimination of hidden surfaces, hidden lines (referred to as blanking) is the key to three-dimensional modeling. Blanking is the use of some algorithm to eliminate invisible lines or faces from an object or draw it with a dashed line. The core of the blanking algorithm is to determine whether the surface of the 3D model is visible. 

In terms of abstraction, a blanking algorithm can be regarded as a five-tuple, that is HA = (I, O, D, P, S) where I is the set of three-dimensional objects to be blanked; O is blanked The set of two-dimensional objects to be processed; D is the data structure used for blanking processing; P is the set of basic operational procedures required for blanking processing, including classification, sorting, three-dimensional coordinate transformation, perspective projection transformation, and basic Graphical element intersection calculation, two-region overlap judgment, point-to-area human inclusion test, and face orientation test; S is a blanking strategy, that is, the order in which the above basic operation processes are adopted.

The blanking algorithm is usually divided into two categories, object space algorithm and image space algorithm, depending on whether the objects are directly defined by the object or whether they are projected. The object-space algorithm compares the objects in the scene with the components of the object to determine which surfaces are visible. The image-space algorithm judges the visible surfaces corresponding to each pixel point by point on the projection plane. Although the basic idea of ​​various kinds of blanking algorithms is different, most of them adopt sorting and coherence methods to improve efficiency. 

Application of octree tree algorithm in 3D graphics blanking

1) Use an octree to represent a three-dimensional body.

Hierarchical tree structures, called octrees, can be used to represent entities in a graphics system. Constructing a tree structure requires that each node conforms to a three-dimensional space area. This entity represents the use of spatial correlation to reduce the storage needs of three-dimensional objects. It also provides a convenient way of storing information about the interior of the object. 

The octree coding method divides a three-dimensional space area (generally a cube) into octants, and stores eight data elements at each node of the tree. Each element of a three-dimensional space is called a voxel, or voxel. When all the voxels in the limit have the same type, the value of this type is stored in the corresponding node data element. The empty area of ​​the space is represented as the voxel type "void". The heterogeneity limit is subdivided into limits, and the corresponding data element of the node points to the next node in the tree. This sub-regression proceeds recursively until the area contains only a homogeneous threshold, at which time each node in the tree has 0 to 8 direct descendants, as shown in Figure 1.

Three-dimensional space area

Data elements in the octree node representation

Figure 1 octree data structure

2  Method of displaying an object represented by a linear octree

A linear octree is a representation that only lists all the full leaf nodes. The representation of each node is very simple, so this octree takes up very little memory. When we halved the cube, we numbered each quadrant in the way of Figure 1. In this way, each node can be represented by a string of n-bit octal digits, with the left-most digit corresponding to the first division, and the rest sequentially. After the nodes are encoded, the entire octree is traversed according to the depth of the first way, followed by the number of leaf nodes listed in sequence. 

When displaying an object represented by an octree, we first assume that the position of the viewpoint is (x1, y1, z1), and the direction from the origin to the viewpoint can also be considered as the normal vector of the observation plane. According to the positive and negative components of (x1, y1, z1), we determine the priority of different quadrants when they are displayed, so as to list the queues of the display order of the nodes in the linear octree. This guarantee shows what you see. According to this, when determining the display order of the cubes in different quadrants, the most likely to be occluded is placed at the front, and the least likely to be occluded is at the rearmost. For example, when x1, y1, z1 are all greater than zero, its priority order is.

3 octree tree algorithm

When the observed object is represented by an octree representation, the octree nodes are usually mapped to the viewing patch in the forward order to eliminate them. The idea of ​​this method is this: Assume that the direction of observation happens to meet the content corresponding to the four nodes of 0, 1, 2, and 3, so that the face in front of the four sub-areas is visible, and the following four sub-areas are visible. , or the back part of the first four sub-sections, may be blocked by the front. Based on this hypothetical observation direction and display object arrangement, if we process the octree nodes in the natural order of 0,1,...,6,7, or traverse the representation object in depth-first order. The octree, when it meets the leaf node, if the pixel in the frame buffer corresponding to it is still the background color, then the value of the display attribute corresponding to this node is taken as the value of these pixels. If the pixel is not a background value, don't change it. In this way, pixel positions corresponding to voxels that were originally unoccupied are always blank. A node that is completely occluded, because its subnodes must also be occluded, does not have to deal with them. 

By introducing the necessary transformation of the octree beforehand, it can be changed to the above "standard" case, that is, different viewpoints and viewing directions can be handled by the transformation. Therefore, we always assume that we only deal with this "standard" situation. It also assumes that the octree first becomes a visible quadtree representation and is finally transferred to the frame buffer. 

4 concrete implementation of concrete examples

The author of this article takes Visual C++60 as a development tool and uses this algorithm to complete the convex blanking. Taking a specific convex body as an example, as shown in FIG. 2 , a hidden perspective view thereof is drawn. The ten vertices of the convex polyhedron have been numbered counterclockwise. The coordinates of the 1 to 10 vertices are (2,27,−2), (2,27,0), (2,−27, respectively). 0), (2,  27,  2), (2,  27,  2), (2, 27,  2), (2, 2 7, 0) (0,17,2), (0, 17,2) and (2, 27, 0). 

(Wen/Fu Chunying and Ke Zhi Liu Zhipeng)

<China Packaging Industry>