Method for accelerating the rendering of successive images of a 3-dimensional graphics scene and related memory medium

Method for accelerating the coloring of three-dimensional spatial graphics panoramic continuous image and related memory media

The invention relates to a method for displaying a continuous frame of a graphic model on a computer screen.

The establishment of the animation industry is based on the fact that a static image is continuously displayed at high frequency to human eyes to complete animation or obvious movement, where each image represents a small and increasing movement relative to the former. The frequency provided can be displayed to the static image of the human eye more than the so-called "frequency fusion", because the eye can not detect it, in fact only see different images, and in the illusion through the cooperation of the eye and brain to see a continuous Moving images.

Modern graphics systems make extensive use of this fact, and what all these systems have in common is to capture a continuous image of digital information, which is then displayed on a suitable display screen with sufficient high frequency. When it is desired to display these images with high resolution, then of course the display screen itself must have many pixels, which in turn requires the display frame of each digital image data to have a large amount of data. In fact, this not only means that a large amount of memory is required to store the digital image data, but more importantly, it requires extremely fast processing so that it can process the image data frames that appear on the display screen at a rate not less than the fusion frequency, which is about 30 Hz.

Graphic models are generally constructed from static objects, which represent a fixed background and one or more dynamic objects moving in the fixed background. In fact, the moving image is derived by generating a large number of pixel data frames, and each frame represents a small amount of movement between a frame and its successors, and the pixels seen in each frame represent the real-time image seen by an observer. The real-time image changes between consecutive frames because of the movement of dynamic objects in the static panorama and the changing vision of the observer.

An important task in computer graphics is to calculate visibility. Knowing the geometric model of a panorama and a viewpoint, the purpose of visibility calculation (also called hidden surface removal) is to find out which models in the viewpoint can be seen. The performance of the visibility calculation level, if it is found that an element of the geometric model is not visible, other time-consuming calculations (such as shadows) do not need to be performed in this element, which can greatly affect the entire coloring process.

It should be noted that although the visibility calculation is generally performed before the graphic image is displayed, the display of this image has nothing to do with the visibility calculation and will not be executed all the time. In addition, it will not only consider the enhanced display of graphics images, although it is expected to accelerate the calculation of the visibility of graphics images. For example, the graphic model can be stored in a computer far away from the user, and the dynamic change of the graphic model can be executed by the operator of the remote computer. This change must be reflected in the model stored in the user's location by sending updated information to the user's computer, so that its graphical model version can be corrected. In this case, it can be expected to reduce the amount of updated data as much as possible. This data requires the user's computer communication, because the communication channel (usually the network) is usually the main bottleneck in the computer system that causes the system performance to decline. It may be the following situation. The graphical model updated by the user does not display itself, but forms the basis for further calculations and processing, such as part of a simulated machine. In other words, the speed of rendering the graphic image is the most important in all cases, and the display of the graphic image can be selective.

The following is to discuss the practice methods to improve the speed of the visibility algorithm, and refer to the following papers: 1. Heber and Garland published in the "Graphics Interface Annual Conference" "Rapid Shading Multi-resolution Model" (1994 May 5 Month, Bavo City, Alberta Province)

2. Fankhorse was published in "RING: Master-Slave System for Multi-Servo Environments" of "Interactive 3D Graphics 1995 Annual Conference" (ACM SIGGRAPH, April 1995, Monterey, California, pages 85-92)

3. Green, Cass and Miller published in the "SIGGRAPH93 Annual Conference" "Level Z-Zone Visibility" (August 1993, Anaheim, California, ACM Computer Graphics 27(4), 231-238 Page)

4. Nalle published "3D geometric model segmentation tree image representation and generation" at the "Graphics Interface 92 Annual Conference" (May 1992, Vancouver, pages 201-212)

5. Green and Cass published in the "SIGGRAPH 94 Annual Conference" "Complicated Environment Limiting Error Glyph Smoothing Technology Coloring" (August 1994, Orlando, Florida, ACM Computer Graphics 28(4), pages 59-66 )

6. Sodasky and Goldman in the "Computer Graphics Conference (September 1996)" "Dynamic Panorama Output Sensing Visibility Algorithm and Application of Virtual Reality" (August 26, 1996, 1996) European Graphics Conference)

7. Earnshaw, Chidon and Bama presented "Internet visualization and virtual reality" at the "Visualization Annual Conference" (November 1992, Jerusalem, Israel)

8. Nalle, Amannadi, and Sibert published in "SIGGRAPH'90 Annual Meeting" "Merge BSP trees to generate polyhedral group operations" (ACM Computer Graphics, Dallas, Texas, 24(4), 115-124 , August 1994)

The execution time of visibility calculations can become a problem for large and complex models that have a large number of graphics primitives. Consider, for example, a detailed model of a large building. Although it may include millions of polygons, only a small part of it can be seen from any point of view. In this kind of panorama, it is better if the execution time of the visibility calculation algorithm is exactly linearly proportional to the number of visual primitives, rather than proportional to the total number of primitives in the model.

If the execution time of each frame of the visibility algorithm (except for any initiation) is linearly proportional to n+f(N), it is called output sensing, where N is the number of primitives in the entire model, and n is the visual basis The number of elements, and f(N) is much smaller than N. f(N) is the (inevitable) redundancy added by the algorithm. Other sensory visibility calculation algorithms are also called occlusion picking or visibility picking algorithms, but most visibility algorithms are not output-sensing For example, the well-known Z-zone visibility algorithm is not output-sensing, because it checks each polygon in the model, even if the processing of each polygon is fast (such as in hardware), the execution time is still The total number of polygons is proportional.

In the recent real-time 3D rendering, Heber and Garland claimed that the output-sensing visibility algorithm is the basis of the future graphics system, because the Z-buffer visibility algorithm is the most familiar and popular visibility algorithm. But its disadvantage is that it is not output-sensing. Many recent studies have extended the Z-buffer visibility algorithm to make it output-sensing.

This kind of research on output-sensing visibility calculation has just started recently, and no commercial system has been launched yet. For example, SGI's IRIS executor high-performance graphics package software and IBM's 3DIX structure and mechanical model visualizer both use viewing table picking and multi-resolution representation (detailed layer switching) to speed up rendering, but neither uses visibility picking. .

If the important part of the model is dynamic, its complexity is a serious problem. The known output-sensing visual algorithm is even more ineffective in this case, in addition to the time required to color the visible part of its graphic model , And spent a lot of time on updating it. Examples of large models with various dynamic objects are environments where multiple users roam at the same time, such as the RING system of Funchal and the Elfa World of World Corporation. In the existing visibility algorithm, the model in each users workstation must reflect the current location of other users. In a decentralized environment, it takes more time to update this model and more time for the movement of other users. Transmission on the communication line.

Using hierarchical data structure to subdivide the object space seems to be the nature of all output-sensing visibility algorithms: it is necessary to use hierarchical spatial data structure to select large and occluded spatial regions, and it is not necessary to explicitly consider each object in these regions. This method is used in Green et al.s hierarchical Z-buffer algorithm and Nalles BSP tree mapping method. However, the spatial data structure does not need to be strictly limited to a hierarchical type. For example, it can be a direct periodic graph, while a brother point It is not necessary to indicate disjointed areas of space.

The hierarchical Z-buffer algorithm is based on the general Z-buffer, but uses two hierarchical data structures, one is an octave tree and the other is a Z pyramid. The lowest layer of the pyramid is a flat Z buffer. In all other layers, the lower There is one pixel in every 2x2 square pixels in a layer, and its value is equal to the largest (farthest) z of these 4 pixels.

At the beginning of the algorithm, an eight-point tree is constructed in the entire model. This operation is time-consuming and takes longer than calculating the visibility from a single viewpoint. However, if the model is static, the same can be used. The octave tree calculates visibility from many different viewpoints.

In order to calculate the visibility from a viewpoint, first start the Z pyramid to be infinite in all pixels of all layers, and then recursively from the root of the octave tree. Each octet tree node encountered is determined by Z The current content of the pyramid is checked for occlusion. If the node is completely hidden, it can be ignored. The Z pyramid is updated and the 8 sub-points are recursively inspected from near to far. Because of the previous and subsequent sequence, there is a good chance that the closer one will be removed from the base. The meta finds that the far node is occluded, so it saves all the subtrees to which the far node belongs.

Use pyramids for quick node and primitive visibility check: find the lowest pyramid level, where a single pixel still covers the entire mapping of primitives or nodes. If the z value temporarily stored in the pixel is still close to the nearest z mapped, then the entire primitive or node cannot be seen. Otherwise, divide the map into 4 and check each of the 4 corresponding pixels in the next layer.

The latest version of the hierarchical Z-buffer algorithm proposed by Green and Cass uses an image space quad-tree to replace the Z pyramid, which makes the performance slightly worse, but can effectively implement the glyph smoothing technology.

Nalles mapping algorithm uses the same principles as the layered Z-buffer algorithm to perform output-sensing visibility calculations. In the early calculations, most of the model is omitted, and the data structure constructed during preprocessing is used. But Nalle uses a more complex data structure: BSP (Binary Space Partition) tree.

A BSP tree can be defined in any dimension. It is a binary tree, in which each node represents a certain hyperplane, and the left subtree of the node corresponds to the negative half space of the hyperplane, and the right subnumber corresponds to the positive half space. For example, Figure 1a shows the case of 22, where each point represents a line, and each subtree represents an area in the plane. Figure 1b shows the hierarchical relationship between nodes and the corresponding regions of the hyperplane starting from root A. Each region is represented by a number to distinguish each node, which is represented by a letter. It can also store additional data representing each area, such as color data.

In the case of 3D, the BSP tree is the normal general form of the octet tree. The plane separating each node does not need to be in the middle of the node and does not need to be parallel to the axis. In fact, if the model consists of the entire plane and polygonal surfaces, the BSP tree is generally sufficient It correctly represents the panorama itself and does not require any additional data structure. It only maintains the "in/out" attribute of the distribution at each leaf point. This is contrary to the octave tree, which is generally only regarded as an auxiliary data structure in computer graphics, not Represents the model itself.

Nalle proposed to use a 2D BSP tree to represent the image, and only scan it at the last stage to convert it into a raster image for actual display. He shows an algorithm to map a 3D BSP tree, which represents a panoramic model, and becomes a 2D BSP tree that represents its image. This algorithm recursively inspects the input BSP tree from near and far, ignoring all the spatial regions occluded by the model plane. In the same way, it also achieves output-sensitivity, that is, it is obtained in the hierarchical Z-buffer algorithm: Remove a large amount of hidden space in batches, and do not specifically check each object in these parts. Contrary to the hierarchical Z-buffer algorithm, Nalles mapping algorithm does not need to represent data structures other than the model and images. Furthermore, the construction of the hierarchical spatial data structure (3D BSP tree in this example) is extremely time-consuming, but it is constructed only once as the previous processing level, and then used for visibility calculation from many different viewpoints.

Both the hierarchical Z-buffer and BSP tree mapping in the output-sensing visibility algorithm were developed to handle static panoramas, although Green et al. proposed an optimal method to handle the animation sequence (after a large amount of redundancy, approximately x2 acceleration), but restrict these sequences to "walking through", where the entire model is static and only the viewpoint changes between boxes. In the visibility picking algorithm that produces the correct results, the latest spatial data of the model must be used. If any objects in the model move or deform, the following data structure will be incorrect and must be updated. It is unacceptable to construct it from a fresh start, because as mentioned above, this is an extremely expensive operation, usually more expensive than the flat Z-buffer algorithm for coloring the one-box.

Therefore, it is desired to provide an improved method to display graphic images, which applies the visibility picking algorithm to the dynamic panorama, and also uses it to minimize the update redundancy of those parts of the model that may be seen by the user. .

The object of the present invention is to provide a method for displaying a continuous frame or image of a graphic panorama on a computer screen, which can still reduce or eliminate the above-mentioned disadvantages.

The special purpose of the present invention is to provide an improved visibility algorithm that allows rapid update of the data structure and therefore can be processed more efficiently.

According to the broad features of the present invention, a process of coloring a three-dimensional spatial graphic panorama is provided. The panorama includes a plurality of static and/or dynamic objects composed of geometric elements. A method for accelerating the rendering of the continuous image of the panorama includes the following steps:( a) In the initial step: (1) Determine which dynamic objects are visible and those that are hidden in their initial positions; (2) At each time period Δt, a temporary limited size of hidden dynamic objects is generated after the mapping moves, and It is not necessary to be equal for all dynamic objects; (3) Construct a spatial data structure that includes static objects, visible dynamic objects in their initial positions, and temporarily limited sizes of hidden dynamic objects; and (4) Events that maintain time Queue, where it is no longer certain that the temporary limited size can contain its dynamic objects; (b) The dynamic object will be hidden, and it is no longer sure to be included in its temporary limited size (because the event queue is recorded in this way, or because the object The movement of violating some assumptions of temporarily limited size), insert the spatial data structure instead of each temporary limited size; (c) output-sensingly process the spatial data structure to color the visible part so that its dynamic objects can replace the visible (D) Generate a temporary limited size of the hidden dynamic object, which does not have a temporary limited size, insert the temporary limited size into the spatial database instead of the hidden dynamic object, and insert the time of the temporary limited size into the event queue Column, it is no longer determined that the temporarily limited size can include its dynamic objects; and (e) Repeat steps (b) to (d) to color each image.

According to a special practical example of this method, a possible visual dynamic object list of all possible visual dynamic objects is generated in the initial step, and step (a) includes the following steps: (1) The possible visual dynamic object list is started to include all dynamic objects And the event queue to become empty; and (2) construct a spatial data structure containing static objects; and step (b) includes the following steps: (1) hide dynamic objects, which are no longer determined to be included in their respective temporarily limited sizes (Because the event queue is recorded in this way, or because the movement of the object violates some assumptions that produce a temporarily limited size), insert the table of possible visual dynamic objects; and (2) get the current position of each object in the table of possible visual dynamic objects, And insert it into the spatial data structure.

The other parts of the method are roughly the same, except that as the previously hidden dynamic object becomes visible and as the previously visible dynamic object becomes hidden, the visible dynamic object table may be updated all the time.

In order to achieve the best performance, the hierarchical structure of the spatial data is better. Although it will reduce the performance, although it is still better than the above method, it can still be obtained with a non-hierarchical spatial data structure such as a fixed grid.

According to the broad features of the present invention, a process of coloring a three-dimensional spatial graphic panorama is provided, the panorama includes a plurality of static and/or dynamic objects composed of geometric elements, and a redundancy to avoid hiding dynamic objects in the continuous image of the panorama A processing method to accelerate the coloring of the continuous image of the panorama. The method includes each hidden dynamic object: (a) predicting a period of time Δt, where it is assumed that the hidden dynamic object remains hidden; and (b) during the period of time Δt, no coloring The hidden dynamic object processes the panorama with output-sensitivity.

According to specific specific examples, the assumption also includes settings, and the time period is expressed in time units or equivalent terms (such as the number of consecutive images).

<p>10System</p><p>11Processor Unit</p><p>12Memory</p><p>13Display</p>

In order to understand the present invention and see how it can be implemented in practice, some specific examples will now be explained by non-limiting examples and with reference to the accompanying drawings. Among them: Figure 1 is a schematic diagram of a 2D BSP tree; Figures 2a, 2b, and 2c are The vertical view of the octave tree at each level of the natural update method; Figures 3a, 3b, and 3c are the vertical views of the octave tree at each level of the basic update method; Figures 4a, 4b are the icons of the two test panoramas, respectively The evaluation method is based on the natural and basic update methods; Figures 5a and 5b are respectively a 3D object and a temporarily limited size diagram, which are used in the method according to the second specific example of the present invention; Figures 6a, 6b, and 6c show the flow chart of the present invention. The main operating steps of the main and secondary programs of the second embodiment of the invention; Figures 7a and 7b show the main operating steps of the main program in the variant of the second embodiment of the present invention; Figures 8a, 8b, and 8c are based on The graph shows the performance of the algorithm according to the second specific example of the present invention under different conditions; FIG. 9 is a diagram of a test panorama to evaluate the method according to the second specific example of the present invention; FIG. 10 is shown graphically in FIG. 9 Shows the performance of the algorithm according to the second specific example of the present invention under different conditions of the test panorama; and the block diagram of FIG. 11 shows the functions of the main components of the system implementing the present invention.

The present invention is based on the following understanding that there are two ways to quickly update the data structure: 1. Minimize the time required to update the dynamic object structure; 2. Minimize the number of dynamic objects in the structure that must be updated. Although the second method seems to be more suitable for market demand, the first method is also explained for complete purposes.

Figures 2a, 2b, and 2c show vertical views of the octave tree at various levels of the natural update method, in which an object is deleted from the octet tree and then inserted back into a new position, so Figure 2a shows static and dynamic primitives The beginning and the present model of is represented by white and black circles respectively. Starting from the root of the octet corresponding to the complete outer square, the octet nodes are successively deleted as shown in Figure 2b to delete the dynamic primitives, leaving only the white circles representing the dynamic primitives. In Figure 2c, the dynamic primitive is inserted into its new position to generate an octet tree node. This method called N is much better than rebuilding the entire octave tree, but it is still not the best: the octet tree node will be deleted and generated unnecessarily, in addition, when searching for the node to insert the object, it will happen in an unnecessarily long path superior. The update can be optimized by taking advantage of the temporal coherence in the animation sequence: the continuous images in the sequence are expected to be similar to each other. There is a similar correspondence between the continuous frame time and the state of the model: dynamic objects generally jump from one place near the panorama to another indiscriminately. The position is similar to the shape. Therefore, if the primitive is deleted and inserted according to the natural method N, the octet tree node may be deleted unnecessarily, and it will only be generated immediately.

It should be noted that the depth of the octave tree does not have to be related to the number of objects in it, and an octave tree of arbitrary depth can be obtained by placing the objects closer together.

Figures 3a, 3b, and 3c are vertical views of all levels of octave trees of improved update method B, where octave trees can be updated more quickly by using the following fact that limits the changes in the tree to extremely small subtrees, which contain Dynamic primitives for old and new positions. The node at the root of this subtree is shown in Figure 3a as v=LCA (primitive, new_config), which is the smallest common parent point of all nodes and contains the old and new configurations of the primitive. The octet update method is now to find v, delete the dynamic primitive from the sub-octet under v (still in its old position) as shown in Figure 3b, and insert it into the new sub-octet in the same sub-octet. The location is shown in Figure 3c. It can be proved that method B is correct, that is, the result of its transmission is the same as that of natural method N. Similarly, it shows that method B is the best, which means that it does not make unnecessary deletions or generate any node of the octet tree (the possible exception is the generation of empty leaf points).

If the octave tree is deeper, it means a large and complex model, and it is expected that the leaves are closer to v than the roots. This is because temporarily coherent, that is, it is expected that the position of each dynamic object is close to its position in the previous frame, and because the separation is high (large ) The plane of the octet tree node is smaller than the plane separating the small nodes and the distance between the two is longer. Therefore, the probability of objects crossing the separated plane decreases exponentially with the height of the nodes separated by the plane. This is in contrast to the situation where there is no temporary continuity, and dynamic objects jump between frames at will, in this case crossing the separated plane The object probability decreases exponentially with the height of the node.

Further improvement can be obtained by merging the LCV discovery level with the delayed primitives in the octet tree, because both operations occur in the bottom-up search of the octet tree.

If each primitive is attached to several octave nodes (such as in the hierarchical Z-buffer algorithm) instead of belonging to a single node, the upward search for the octave starts from the lowest stage node group, and the object belongs to that Group. Each search refers to a certain degree in the tree, in which the related node group contains primitives that are obviously combined with primitives, and the parent points of lower-rank subsidiary nodes. The search will continue until the group is reduced to a single node, and then continue in the case of the primitive to which the single node belongs.

If there is a dynamic object o that contains several primitives, all of them can be combined for the purpose of finding the smallest node. v=CLA (o, new_config) contains all primitives at o in its old and new configurations. Under v, the primitive is deleted from the subtree and then inserted into a new position. On the contrary, it is better to move the primitives to their new positions one by one under the natural algorithm N, and the primitives that have not been moved can be used as position supporters to prevent unnecessary deletion of octet tree nodes.

If there are two degree objects a and b, if the node LCA and LCA are the same, or one of them is the parent of the other and is not too high, it is worth combining them. If there are more than two dynamic objects, they should be combined so that the height difference between the LCA of different objects in each group is not too large, and one of these LCA is the parent point of all the others.

Referring now to the first test panorama of FIG. 4a, it is used to evaluate the actual performance of the octet update algorithm for dynamic primitives to which multiple octet nodes belong without forming a group. The first test panorama is very simple and consists of small squares moving in a large square. The small square moves repeatedly parallel to the x-axis, and its moving step is equal to half of its side length, so that the distance between it and the nearest side of the large square is still Equal to the side length of the small square. The total octet update time is measured in all steps. The performance of the octet update algorithm is always better than the above natural algorithm. The correct acceleration achieved depends on the ratio of the size of the block, and roughly the ratio of it to the side of the block is found The index is proportional. This is because in fact the depth of the octave tree depends on the distance between the objects in the model. As the small square becomes smaller and closer to the edge of the large square, the octave tree must become deeper to separate the two objects. This directly affects the execution time of the natural algorithm, but for the bottom-up octave tree update The algorithm is less effective, and most of the update operations are not determined by the height of the octave tree.

Fig. 4b shows the second test panorama, which is modeled with 4 complete objects, such as chairs, boards, glass and candles, which are more complex (and more practical) than the first test panorama of Fig. 4a. The model contains 5745 geometric elements (in the polygon in this special case), resulting in an octave of depth 11. The dynamic objects of the second test panorama are also small squares, and the time around a candlestick has an increment of 1, and the octet update algorithm according to the present invention can still achieve a 2.7 times acceleration in the second test panorama of FIG. 4b.

Compared with the first test panorama in Figure 4a, only the entire octave tree is created in the dynamic object. In the second test panorama in Figure 4b, almost all the octave trees are constructed for the static part of the model. The second test panorama Most of the speedup in is not the result of removing the node deletion, but narrowing the search octet every time a dynamic object is inserted into a new position in the octet.

The first way to minimize the time required to update the structure of a dynamic object has been described, and now the second way to reduce the number of dynamic objects to a minimum is described, in which the structure of the object must be updated. Consider the purpose of the updated spatial data structure to achieve better performance. If each dynamic object can be predicted, the limited size of a certain area space will completely include the objects of the entire cycle of the animation sequence, and then these sizes will be inserted into the space of the model. Data structure, dynamic objects can be ignored unless the visibility picking algorithm finds that the limited size can be seen. For example, you can find out the limited size of the revolving door on the hinge, moving on the rail of the train, etc. The performance of this kind of example depends on the tightness of the limited size. In an extreme case, the possible position of the dynamic object is not known at all, and the limited size is equal to the entire model space, because these sizes are (almost) always visible and must be in each case. Each dynamic object is checked in the box, so the visibility calculation is not output-sensing. In other extreme cases, the limited size is very tight and equal to the object itself. In fact, a dynamic object becomes static because it cannot move, and the visibility calculation becomes an output-sensitivity because it is in a static model.

It is not always possible to find a limited size in the entire cycle of an animation sequence. It is especially difficult in interactive applications such as virtual reality (VR), simulators and video games, where the path of dynamic objects is not predicted and the animation cycle is unlimited , Even if the limited size can be found, it will be too large and too loose, and will not contribute much to the output sensitivity.

Therefore, according to the present invention, a temporary limited size (TBV) of a short period of time is calculated instead of the entire animation sequence. For example, if the maximum speed of each dynamic object is known, if the position of an object is obtained at a certain time, it is possible to calculate the limit range of its position at any future time. In a more general case, the TBV does not need to be circular. For example, a dynamic object may have a great speed and a preset trajectory, or the great speed or movement resistance may be different in different directions. TBV is based on some known limitations that may change in dynamic objects, such as extreme linearity and/or rotation speed and/or acceleration, non-penetration through walls and floors, etc. The restrictions used to construct TBV can be imposed by the user plane of the interactive system or by stimulus rules such as physical restrictions such as solid non-penetration. The restrictions are not absolute, but can be random, that is, the object does not have to always respect these restrictions. It is just assumed to execute with a certain degree of probability. Possible changes in dynamic objects include any geometric corrections, including movement, rotation, scaling, cutting, changing the configuration of voice objects, and arbitrary deformation. Roughly suppose there is a method to find the limited size of each dynamic object from the time of the current frame to any desired moment in the future. This future moment constitutes the expiration date of the TBV, and the time period arriving at this date is the effective period of the limited size. The hidden dynamic objects can only be considered in the following cases, if the limited size of the dynamic object can be seen, or if the end date of the size is reached, or if the object violates some probability restrictions of the construction size.

It should be noted that the temporary limit size is calculated in a hurry, and the trajectory of the object needs to be unpredicted. Therefore, we determine the compatibility with interactive applications, where information such as simulation, video games and virtual reality (VR) are unpredictable.

Once the dynamic object has been checked and it is found that it cannot be seen, there is still the problem of choosing the correct end date of its TBV. If the end date is selected too quickly, the dynamic object must be considered in a short time, thus reducing efficiency. In other words, if the future If the date is too far away, the size limit will be too loose, and you will see it after a short time.

If the viewpoint is fixed, most of the occlusions in the panorama are static objects (such as the walls of buildings), and the best effective period of TBV can be accurately calculated. Starting from the initial effective period of a frame, the period is repeated Double until the static object no longer hides the limited size, and then use a binary search to find the correct moment when the size is initially visible. The coloring process must maintain the event queue of the end date, similar to the priority queue used for simulation, as long as the correct time is limited in size. The coloring process must maintain the event queue of the end date, similar to the priority queue used for simulation, as long as the limited size is tight enough to maintain other sensitivity, because most sizes will remain invisible during their effective period.

If the viewpoint is not fixed, the above method does not need to find the best end date. Because it finds the almost visible TBV, that is, it can be seen in one frame. Even a slight movement of the viewpoint can show the user a part of the size, so it is convenient to refer to the dynamic object. Therefore, if the viewpoint is movable, it is best not to use such a long effective period. The better choice is to use a short period (such as half) to get a smaller limit size, which takes a longer time to see. Or choose the modified effective period so that if the last period of the TBV of the dynamic object is too short (the TBV disappears before you see it), the next TBV of the same object will have a longer effective period, in the opposite case it will have Shorter period.

The above-mentioned TBV technology can be implemented in conjunction with the hierarchical Z-buffer visibility algorithm. TBV optimizes the update of the octave tree. The visibility algorithm uses this octave tree to draw the panorama and detects which ones have been seen TBV. The dynamic object should provide its trajectory in advance as an animation script, or have the maximum known speed or some other known movement restrictions.

Referring to Figures 5a and 5b, the first case shown in which the limited size will be constructed as a scanning plane with a linear curve along the trajectory of the object limit frame. Therefore, Figure 5a shows a typical room which forms the basis of a graphic model containing a fixed table. The opposite sides and each pair of chairs move towards the table. The chair closer to the left of the table will be slightly unstable when it moves towards the table. Figure 5b shows the final result of the 4 chairs.

In the second example, only the maximum known speed of the dynamic object is known, and the limited size of each dynamic object is a sphere centered on the last known position of the object. The radius of the sphere is its effective period multiplied by the maximum separation ( Plus the radius of the object), the effective period can be a constant, variable or large value (extend from the end of the animation sequence if known).

6a, 6b, and 6c are flowcharts respectively showing the main operation steps of the primary and secondary procedures of the first specific example of the present invention, so as to accelerate the coloring of the continuous image of the three-dimensional spatial graphics panorama.

Perform the following steps in the initial moving step (a) shown in Figure 6a: (1) Determine which dynamic objects are visible and those that are hidden in their initial positions; (2) During each time period Δt, move in its projection The temporary limited size of the hidden dynamic object is generated later, and it does not have to be equal for all dynamic objects; (3) Construct a spatial data structure that includes static objects, visible dynamic objects in their initial positions, and temporary hidden dynamic objects Limited size; and (4) a queue of events that maintains time, where it is no longer determined that the temporary limited size can include each dynamic object.

Then in step (b), it is no longer determined that the hidden dynamic object is included in each temporary limited size (because the event queue is so recorded, or because the movement of the object violates some assumptions that generate the temporary limited size), insert the spatial data structure Instead of temporarily limiting the size.

Next, in step (c), another secondary program of Fig. 6c is shown, and the spatial data structure is output-sensedly processed (visited) to make the visible part of it colored, so as to replace the visible temporary limited size by its dynamic objects . In the example where the spatial data structure is hierarchical, the tour is a recursive procedure, and in the following example that the spatial data structure is non-hierarchical such as a normal grid, the tour is repeated. In step (d), a temporary limited size of the hidden dynamic object is generated, which does not have the temporary limited size, and the temporary limited size is inserted into the spatial database instead of the hidden dynamic object. Then insert the time of the temporarily limited size into the event queue, where it is no longer determined that the temporary limited size can include its dynamic objects (end time), and then repeat steps (b) and (d) to color each image.

It should be noted that the term event queue should be interpreted in a logical manner, that is, it is not limited to an instance of any specific data structure.

Referring now to Figures 7a and 7b, the flowchart shows the main operating steps according to the changes in the main program described in Figure 5a above. The basic difference between the two specific examples is that the dynamic objects are initially classified as hidden or possible to see. arrive. In the specific example of FIG. 6a, it is clearly determined in the initial step (a). In the changes shown in Figures 7a and 7b, the initial step (a) generates a list of possible visual dynamic objects of all possible visual dynamic objects, and inserts all dynamic objects into it. In the subsequent processing of coloring the first image, it is obvious that some dynamic objects are actually hidden in the list of possible visual dynamic objects, and thus the list of possible visual dynamic objects is updated. Because in this case, there is no clear distinction between hidden and possible visual dynamic objects in the initial step (a), and the initial step itself is faster. However, this requires more processing at the beginning of the tour procedure (step (c)) when rendering the first image.

Comparing the performance of the Temporary Limiting Size Technology (TBV) with the hierarchical Z-buffer algorithm, the octet tree of each dynamic object is updated in each frame (HZB), and only the general Z-buffer (ZB) is used in each frame. Color all the objects in one box. On the SGI IRIS purple blue XS4 4000 with Z buffer, GL inventory is used to display all the tests. The panoramic model used for testing is a building composed of interconnected rooms, each room is set with a table, and the dynamic object is a chair, which follows the trajectory close to the table as shown in Figure 4a. In order to test the net benefits of TBV technology, TBV and HZB naturally update the octave tree.

Figures 8a, 8b, and 8c graphically show the performance of the algorithm according to the present invention under different conditions. Figure 8a shows the three technical performances of the following models, namely increased size, static polygons with changes, and dynamic polygons fixed at 1100 number. It can be expected that the execution time of ZB is linear in the size of the model, while the execution time of HZB and TBV is nearly constant, because the same number of objects can be seen regardless of the size of the model. The performance of TBV is better, because in fact only half of the dynamic objects can be seen.

In Figure 8b, the performance of the three technologies is compared with the increased size model, where the ratio of the number of dynamic objects to the total number of objects in the model is fixed at a constant 80%. Therefore, there are always 4 moving chairs in each room. In this example, both ZB and HZB have a linear execution time relative to the size of the model. The performance of HZB is much worse than that of ZB, because the octave tree needs to be updated all the time, resulting in huge Redundancy. TBV does not have to have many new values of these octatrees, thus greatly improving performance.

Figure 8c shows the results obtained by the three techniques, that is, increasing the number of dynamic objects in a static model of a fixed size, which contains 125 rooms and tables, which are represented by 16,250 static polygons and an indefinite number of dynamic polygons. This shows that the performance increase obtained by TBV is proportional to the dynamic objects in the model.

Therefore, it can be seen that the TBV algorithm according to the present invention is superior to the existing visibility algorithm, especially when most panoramic polygons are dynamic.

The TBV technology does not need to update the basic data structure (octet tree or BSP tree) of the visibility algorithm for most dynamic objects, such as invisible objects and TBV that are still valid. However, this technology has another very important advantage. In addition to the auxiliary data structure, the panoramic model itself does not need to be updated for these hidden objects, and it can maintain its original configuration and characteristics. If these objects exhibit complex movements, deformations, etc., this can save a lot of calculations. The data of these objects in the model will be incorrect, but this is not important because it is not visible at all.

Consider a multi-user virtual environment, such as the RING system of Funchal. Many users can roam at the same time through a shared 3D virtual building, and see each other's graphic display in the appropriate location of the building. In the master-slave configuration, the function of each users workstation is the client, and the central server (or server network) updates each client into a geometric shape that they can see. Part of this geometric shape depends on other clients. . The server itself keeps updating the geometry of each user. With TBV technology, some general procedures can be saved. The server can maintain the users TBV, which cannot be seen by any other users at present, and it will only be viewed from Among these customers, the geometric shape update is requested, and the customer becomes likely to see it, or its TBV disappears. Or when the servers first see each other, each pair of clients can establish peer-to-peer communication between each other, and the clients perform their own visibility calculations. When the TBV technology determines that another user can be seen, that is A client who requests to update another user through a peer-to-peer connection.

In a VRMUD environment without a central server such as Earnshaw et al., or a server that only holds the static part of the model, TBV can still remove more communication redundancy in a distributed VR system. In addition to having each station broadcast its movement and deformation, each station can specifically track other users who can see it. For all other users, it will maintain the TBV, and once the TBV disappears or cannot be seen That is, the geometric shape is required to be updated.

The extended hierarchical Z-buffer algorithm has been used to implement this algorithm to a dynamic panorama, and the details are as described with reference to the drawings of Figs. 6a and 6b. The current system is executed on a single workstation, the viewpoint moves through the panorama under the control of the user, and the program simulates all other users.

Figure 9 is another test panorama used to test the performance of various coloring technologies with the Silicon Graphics Indy R5000. The number of static objects and the number of visible dynamic objects are maintained at 13,220 and 14,946 polygons respectively. The number of hidden dynamic objects can be changed by increasing the number of people in the building.

Figure 10 shows that the execution time of the planar Z-buffer (ZB) is proportional to the total number of objects in the panorama. The hierarchical Z-buffer algorithm (HZB) requires the octave to be new in each dynamic object, so its performance is better than ZB Value difference. The TBV technology according to the present invention only updates the octave tree of visual dynamic objects, and its execution time is almost constant compared with ZB and HZB.

It will be understood that although specific examples have been described by referring to dynamically updating an eight-tree database structure, the present invention is also applicable to other database structures, including hierarchical and non-hierarchical types. The modification of the non-hierarchical spatial data structure such as the general grid structure has been explained by referring to FIG. 6b of the accompanying drawings.

It should be noted that the present invention also includes other hierarchical spatial data structures. For example, the present invention can be used to dynamically update the BSP tree, which is then displayed by Nalle's visibility selection algorithm. But this is not a direct generalization of the same technology, because the characteristics of the BSP tree are not the same as the octave tree and the kD tree; the BSP tree (with the leaf "in/out" attribute) is used by the visibility algorithm to represent the object itself, however The octet tree and kD tree are just auxiliary data structures to supplement the boundary display.

In order to make the visibility algorithm output-sensing relative to the number of dynamic objects, the following data structure should be maintained: D: A group of all dynamic objects, each with a unique identifier (ID) and the last observation time, these are hidden The dynamic object also has: a TBV, represented by the BSP tree, the end time of the TBV, and a set of leaves that point to the S intersecting the TBV (described below).

S: A BSP tree is the union of the static panorama and the TBV of the hidden dynamic object in D. A group of dynamic object IDs belong to each leaf of bf S. If the object ID is invisible and its TBV intersects the leaf, it is in this group .

T: A BSP tree represents the entire panorama including static panorama, visible dynamic objects and TBV with hidden dynamic objects. Each leaf of T has a group of dynamic object IDs. If the corresponding dynamic object is visible and intersects with the leaf, or is hidden and its TBV intersects with the leaf, the ID is in the group.

Q: The event queue of the TBV termination event that hides the dynamic object.

V: ID of a group of visible dynamic objects.

The above-mentioned dynamic objects can be embodied or autonomous moving objects of some other users, which are controlled by programs such as the clawed frog control object in the VRML 2.0 model.

The algorithm uses 2 subroutines: del_TBV (delete the temporary limit size) to accept the ID of the hidden dynamic object, and change the state of the object from hidden to (possibly) visible, and uni_vis (combine a visible object with the panorama) to process a visible object .

del_TBV (ID):

1. Delete the ID from the leaf of S that contains the ID.

2. If possible, merge the leaves of S.

3. VVu (ID).

In the del_TBV step, the leaf of S containing the ID is given by the leaf group that maintains the corresponding dynamic object in D. In step 2, the leaves that should be merged are brothers, which contain the same ID group after step 1 is deleted. The merging is from bottom to top, and when the brothers terminate, they are not all leaves, or have different ID groups.

uni_VIS (ID):

1. Obtain the BSP tree B representing the current configuration of the dynamic object corresponding to the ID.

2. TTuB, insert ID into each leaf of T that intersects with B in the union.

In the uni_vis step, you can get B. If you connect through communication, the correct content of the communication depends on the characteristics of the dynamic object. For example, if the object is solid, all that needs to be transmitted (after the first frame) are the movement and rotation parameters. , It may be that 4x4 of the same kind is transformed into matrix A, and tree B is multiplied by A by each coordinate of the objects BSP tree, and by A^-1Multiply each plane formula. For sound objects, they need to be converted in each solid section. For deformed objects, the communication can include some deformation parameters, or a complete BSP tree representing the current form of the object.

The union operation performed in step 2 is as described by Nalle et al.: In each user's workstation, all dynamic objects in D are regarded as visible at the beginning, and have a final observation time earlier than the final frame. Start S as a union of all static objects, T and Q are empty, and V at the beginning contains the IDs of all dynamic objects.

Perform the following steps in each frame at each station: 1. For each object ID of the terminated TBV, it is determined by Q, and for each object ID, which violates the restriction on the probability of generating its TBV, it is called del_TBV (ID), If possible, merge the leaves.

2.TS

3. Make uni_vis (ID) in each ID of V

4. Operate Nalle's visibility algorithm on T to display the visible plane. In each leaf of T encountered in this tour, each ID of an invisible object whose TBV intersects with the leaf is made: (a )del_TBV (ID)

(b) uni_vis (ID) For each ID of the visual object that intersects the leaf, update the last observation time to which the ID belongs in V. When checking back from the node, if possible, merge the leaves.

5. For each dynamic object in V, the last observation time is earlier than the current frame, do: (a) Get the TBV of the object until a certain time in the future

(b) Insert TBV into Q and S

(c) Delete the ID of the object from V

Step 1 of the algorithm deals with hidden dynamic objects. Its TBV is terminated by deleting its TBV and moving it to group V. Note that V contains possible visible dynamic objects, which are not necessarily visible objects. It will be too early at this level. Determine a certain visibility, so we only deal with some objects a little bit, and its TBV has been terminated with those who may be visible, because it is visible in the previous frame. The leaf to be merged is a brother, which contains the same ID group after deletion.

In steps 2 and 3, construct a PBS tree T representing the entire panorama, which is used in step 4, which is the core of the algorithm.

Step 4 displays the panorama, and processes the exposed TBV by treating it as processed and the same way that it has terminated instead of becoming visible. This step requires special care because it visits the hierarchical data structure and corrects it at the same time. Therefore, the merging of the sibling leaves, which contains the same ID group, is delayed until we want to check back from the parent point. It should also be noted that the union operation of step 4(b) retains the overall structure of the BSP tree, but only replaces the leaf points with subtrees. If this happens, you should also visit the new subtree.

Finally, step 5 deals with dynamic objects that are no longer visible. If such an object is controlled by another station, the station should provide the BSP tree representing the TBV of the object when requested, and the request should also send its future The time until the provided TBV should be valid.

The algorithm accomplishes the output-sensitivity goal about the number of dynamic objects by ignoring such objects unless they can be seen. However, the present invention has some redundancy. The amount is not linear with the size of the entire panorama. For most frames, no time is wasted when updating and displaying invisible dynamic objects. Not only is it found that it is invisible in fact, but only in the BSP tree. Cannot be reached during the tour. If TBV is chosen carefully (if modified termination is used), TBV exposure will only occur on a few invisible objects, and TBV termination will occur less frequently over time.

Treat static objects as zero-speed dynamic objects, but update visible dynamic objects in each frame, and do not expect to update visible static objects in the same way, especially if this update occurs on a slower network (although it can be seen There are fewer static objects), so the algorithm handles static objects differently from dynamic objects.

It will be understood that the termination time can be selected according to the above-mentioned different criteria, for example, the time period Δt can be set as a constant or equal to the remaining time period of the panorama. Similarly, if desired, the time period Δt can be set equal to a random time period or inversely proportional to the speed of each dynamic object.

Referring now to the block diagram of FIG. 11, which shows the functions and main components of the system, the system 10 includes a processing unit 11 and a display 13 connected to a storage medium 12. The processing unit 11 can be a traditional CPU such as the Pentium processor produced by Intel Corporation, but it will be understood that the system 10 does not need to be constructed with different components as shown in FIG. 11, so by a further example, the processing unit 11 If desired, it can be implemented in distributed processing units such as networks in various regions or remote locations.

The processing unit 11 can perform the above-mentioned various method steps. For details, please refer to FIGS. 6a to 6c and FIGS. 7a, 7b in the drawings, and utilizes the spatial data structure stored in the memory medium 12. The spatial data structure includes static objects, which are visible. The dynamic objects, and the temporarily limited size, are related to the mapping movement of the hidden dynamic objects in each time period Δt, and all the dynamic objects need not be the same.

The user application program is executed under the control of the processing unit 11, which can respond to the spatial data structure to accelerate the rendering of a panoramic continuous image.

In the following patent application scope, letters and numbers have been used to indicate the steps provided for patent application, and the purpose is only for convenience of explanation, and does not necessarily imply that this is any specific order for performing the steps.

The present invention has been explained to a certain degree of particularity, but it should be understood that many modifications and changes can be made to the present invention without departing from the scope and spirit of the following patent applications.