The Research On View Frustum Culling Geometric Algorithm And Testing Method

With the development of 3D geometry model becoming more and more lifelike and complex, the method to reduce the complicated large-scale virtual environment, speed up the rendering efficiency and maintain the system stability is the key to 3-D display system. The high-performance view frustum culling algorithm plays the vital role on improving the collision detection efficiency and enhancing the realism and immersion of the virtual environment.The view frustum culling algorithm is an important and basic algorithm in computer graphics. In this paper, after having summarized all kinds of typical algorithms, analyzed their advantage, application and some limitation, we have researched view frustum culling algorithm in geometric point of view and much further research work on algorithm’s stability has been done. The main contents are presented as follows:(1) While the existing typical algorithms belong to algebraic method, we have designed the view frustum culling algorithm based on geometry and the projection principle in geometric point of view. The theory of view frustum culling geometric algorithm is that a proper computational corrdinate system is built, where the space position relation of view frustum and line segment is transformed into the plane position relation of trapezoid and line segment by simple orthographic projection. This geometric dimension reduction method helps to solve space geometric singular issue.(2) After discussing classification method, an objective complete and detailed test sample based on projection principle has been designed to comprehensively evaluate algorithm’s stability and speed. Because projection principle transforms view frustum culling issue into the plane position relation, geometric singular relation becomes clearer and simpler by using two plane projections. By the plane relation’s guidance, we have designed a test sample which includes all kinds of typical position relations of view frustum and line segment, especially 78 kinds of geometric singular relations, making culling algorithm’s test not in a blind and random way.(3) At last, our view frustum culling geometric algorithm, classical Liang-Barsky algorithm and a basic algorithm of 6 planes intersection have been implemented on Visual C++ with C program. On the basement of qualitative analysis, these 3 algorithms have been tested on stability and speed, which is the first complete combing and test, finds and points out these algorithms’ characteristics.In this paper, the view frustum culling algorithm based on geometry and projection principle havs almost utilized the culling algorithms’ common theory, method and technology, including division coding, parameterization, projection and bounding box, etc. These theories apply to Cohen-Sutherland algorithm, Nicholl-Lee-Nicholl algorithm, Liang-Barsky algorithm, Cyrus-Beck algorithm and box encoding algorithm. So the test sample we have designed works for these algorithms’ stability test, which equals to do a complete test for these algorithms. Because this paper highlights algorithm’s stability, our test sample and its theory provide an important reference value for geometric algorithm with high-demanding stability.