Large-scale Complex Scenes The Visibility Of Judgment And Rejection Technology Research And Implementation

Along with the developing of computer graphics, 3-dementional virtual scene is being accept by more and more people because of its higher naturalness and authenticity, with better Interactivity, nowadays virtual reality is being widely used, as in 3D game, military manoeuvre, Aviation simulation, geographic information system and machine building, ect. Since these industries are developing very quickly, especially because of 3D game is very fashionable, large amount of reseachs of the speeding up rendering algorithms are availble, and the visibility culling method is a main hot spot.In a typical outdoor city scene, there are lots of buildings with high density and occlusion with each other. At this situation, the best speeding up rendering algorithm is occlusing culling method. Occlusion culling method is based on spatial subdivision techniques, which is try to generate a hierarchical data structure to manage all the objects in the scene, so this paper first discussd about the related algorithms about the kd-tree, then made some improvements and simplifications on the traditional algorithms of kd-tree in consideration of characteristics of outdoor city scene, finally realized a light kd-tree generation algorithm which is suit for the city scene.Consider about how to chose the parting plane, our algorithm use a local greedy method instead of the global optimal method.Every time we compute the cost of the partition only among several candidates,and chose the lowest cost one as the parting plane. The finally experiment shows this metiod can generate relatively balanced hierarchical data structure with a low cost.Graphics hardware is changing for the better day by day, since the scale and complexity of scenes are advanced at a very high speed,use the graphics hardware to speed up the rendering is a unchangeable trend. Take advantage of the GPU query function, this paper researched and realized a GPU-based occlusion culling algorithm.The algorithm uses kd-tree to subdivide the space.We explored the temporal and spatial coherence of computer graphics to the full to minimize the number of nodes ?for visibility test and to reduce the delays due to the latency of query results.On the basis of this,this paper researched and implemented a method to deduce the visibility information on the hierarchical data structure.Take advantage of the characteristics of the subspace generated by the ke-tree,we implemented a method to duduce the visibility information between the adjacent subspace.According to the cost of visibility test, we used several kind of visibility tests,reduced the amount of GPU queries.We also used a batch processing method to reduce the amount of render state changing time.Establish the probability computing model of the GPU query.Through the way to compute the cost of direct rendering, the cost of GPU query and the probability of object to remain its visibility, we can decide weather to query the object or not,reduced the amount of the queries time futher.Finally we did a preliminary design about the crowd animation demonstration system, which used the kd-tree generation algorithm and GPU-based occlusion culling algorithm. Our experiment proved that the GPU-based occlusion culling algorithm can effectively improve the rendering speed of large-scale and complex scene.