Abstract:
The present invention is to provide a culling method, used in the computer graphics systems, for determining the visibility of two adjacent polygons of a polyhedron at the same time. It also provides a culling apparatus, which uses the method to execute the culling test. The culling apparatus comprises one multiplier, three multiplexers, two registers, one adder/subtractor, and a controller with a set of instructions to control the whole procedure.

Description:
BACKGROUND OF THE INVENTION 
     A. Field of the Invention 
     This invention relates generally to a method and an apparatus for culling and, more particularly, to a method and an apparatus for accelerating culling tests in computer graphics systems. 
     B. Description of the Related Art 
     A computer graphics system is commonly used to display three-dimensional representations of an object on a two-dimensional display screen. In a typical computer graphics system, an object to be rendered is divided into a plurality of graphics primitives. The graphics primitives are basic components of a graphics picture and may be defined by geometries of a point, line, vector, or polygon, such as a triangle. The graphics primitives are fed through a graphics pipeline where various types of processing occur and are then rendered on a display. 
     Culling, also called backface elimination, is an operation that compares the orientation of polygons in a polyhedron with the viewpoint or center of projection, and removes those polygons that cannot be seen. On average, half of the polygons in a polyhedron are backfacing and the advantage of this process is by using a simple test to remove these polygons. The test for visibility is straightforward and is best carried out in view space. We calculate the outward normal of a polygon and examine the sign of the dot product of this normal vector and the vector from the center of projection, as illustrated in FIG.  1 . 
     As shown in FIG. 1 are the outward normal vector of a polygon N p , and the ‘line of sight’ vector N from the center of the face to the viewpoint. Based on these two vectors, the visibility of a polygon is defined as: 
      Visibility= N   p   ·N &gt;0 
     Where: 
     N p  is the polygon normal 
     N is the ‘line of sight’ vector 
     In order to determine whether a polygon is visible on a two-dimensional flat screen, select three points V 1 , V 2 , and V 3  from the polygon where the V 1  is the center point, V 2  and V 3  are any points on the surface which satisfy the condition that V 1 , V 2 , and V 3  are not on the same line, and (V 1 , V 2 , V 3 ) is distributed counterclockwise. 
     From the visibility test: 
     
       
         Visibility= N   p   ·N [( V   2   −V   1 )×( V   3   −V   1 )]·( V   1   −V   0 )&gt;0 
       
     
     Where: 
     V 0  is the viewpoint (0, 0, 0), and 
     V 1 , V 2 , and V 3  are the selected vertices (x 1 , y 1 , z 1 ), (x 2 , y 2 , z 2 ), and (x 3 , y 3 , z 3 ) for a triangle. 
     The calculation for the visibility test is:        Visibility   =     |           x   1           y   1           z   1               x   2           y   2           z   2               x   3           y   3           z   3           |     &gt;   0                              
     Although the equation for the culling test may seem to be relatively simple and straightforward, it takes twelve multiplication processes and five addition/subtraction processes to complete the whole calculation to test the visibility for one triangle. For two triangles, hence, it takes 24 multiplications and 10 addition/subtractions. Not only is the calculation process unwieldy but also time-consuming. 
     SUMMARY OF THE INVENTION 
     In view of these problems, the object of the present invention is to provide a method and an apparatus for use in computer graphics system which can render and display graphics primitives faster. 
     In one aspect of the present invention, a method is provided for determining, at the same time, whether two adjacent polygons of a polyhedron are visible on a 2-dimensional visual display unit. The test can be done more easily and rapidly. It lends itself to rapid real-time culling and eliminates surfaces certain to be not visible at the observer&#39;s viewpoint. 
     Another aspect of the present invention is to provide an apparatus to execute the culling test described above. The culling apparatus comprises one multiplier, three multiplexers, two registers, one adder/subtractor, and a computer program with a set of commands controlling the flow and process of data. The instruction commands may be installed in ROM to be used in the computer graphic systems in order to compute and control all data inputs and outputs of culling test. 
     The benefits of this invention will become evident as the present invention is described more fully below. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a geometric description of the culling operation. 
     FIG. 2 illustrates two adjacent triangles, according to one aspect of the present invention, sharing two vertices and one common side. 
     FIG. 3 is a schematic diagram illustrating the computation of culling tests for two adjacent triangles. 
     FIG. 4 is a block diagram of the culling test circuit of one preferred embodiment of the present invention. 
    
    
     TABLE 1 is a program for the culling test of two adjacent triangles according to one aspect of the present invention. 
     TABLE 2 is a step by step algorithm for the program shown in TABLE 1. 
     TABLE 3 is a program for the culling test which uses two multipliers and one adder according to one aspect of the present invention. 
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     As shown in FIG. 2, the two adjacent triangles, assumed not to be on the same plane of a 3-dimensional object, share two vertices. The present invention takes two adjacent triangles to perform the culling test synchronously, in order to save computation time and costs. If the selected triangles Δ 123  and Δ 423  of two adjacent polygons comprise four vertices {V 1 , V 2 , V 3 , V 4 }, the culling test of the present invention for Δ 123  and Δ 423  produce two outcomes. The calculation process is described below.          Δ   123     =       |                      x   1           y   1           z   1               x   2           y   2           z   2               x   3           y   3           z   3           |     =                    x   1     |                      y   2           z   2               y   3           z   3           |                +     y   1       |                      z   2           x   2               z   3           x   3           |                +     z   1       |                      x   2           y   2               x   3           y   3           |     
          Δ   423       =       |           x   4           y   4           z   4               x   2           y   2           z   2               x   3           y   3           z   3           |     =       x   4     |           y   2           z   2               y   3           z   3           |     +     y   4       |           z   2           x   2               z   3           x   3           |     +     z   4       |           x   2           y   2               x   3           y   3           |                                  
     From the two equations above, Δ 123  and Δ 423  have three common terms:          |                      y   2           z   2               y   3           z   3           |                ,     |                      z   2           x   2               z   3           x   3           |                ,     and              |                      x   2           y   2               x   3           y   3           |     ,                          
     denoted by S 5 , S 7  and S 9  respectively. By calculating these common terms before generating two test outcomes for the adjacent triangles, the present invention utilizes the present method and saves the computation time of culling test. 
     With reference to FIG. 2, the coordinates of the common vertices for Δ 123  and Δ 423  are V 2 (x 2 , y 2 , z 2 ) and V 3 (x 3 , y 3 , z 3 ), and side {overscore (V 2 V 3 )} is the common side for both triangles. Calculations for all embodiments described below are based on these coordinators as shown in FIG.  2 . 
     FIG. 3 is one embodiment of the present invention. The architecture of the embodiment could provide two test outcomes simultaneously. The circuit is designed to compute common terms first then generate the outcomes. 
     From the calculation algorithms, the first step of the culling test is to compute the 6 terms: (y 2 *z 3 ), (z 2 *y 3 ), (z 2 *x 3 ), (x 2 *z 3 ), (x 2 *y 3 ), and (y 2 *x 3 ), and results are denoted by P 1 , P 2 , P 3 , P 4 , P 5 , and P 6  respectively. 
     Secondly, compute the result of the 3 common terms (P 1 −P 2 ), (P 3 −P 4 ), and (P 5 −P 6 ), results are denoted by S 5 , S 7 , and S 9  respectively. 
     Thirdly, bring in the third vertex of each triangle to the computation. Results for (x 1 *S 5 ), (x 4 *S 5 ), (y 1 *S 7 ), (y 4 *S 7 ), (z 1 *S 9 ) and (z 4 *S 9 ) are denoted by P 8 , P 9 , P 10 , P 11 , P 12  and P 13  respectively. 
     In mathematical expressions:          Δ   123     =                  x   1     |                      y   2           z   2               y   3           z   3           |                +     y   1       |                      z   2           x   2               z   3           x   3           |                +     z   1       |                      x   2           y   2               x   3           y   3           |     
                  Δ   123     =         x   1          (         y   2          z   3       -       z   2          y   3         )       +       y   1          (         z   2          x   3       -       x   2          z   3         )       +       z   1          (         x   2          y   3       -       y   2          x   3         )                     =         x   1          (       P   1     -     P   2       )       +       y   1          (       P   3     -     P   4       )       +       z   1          (       P   5     -     P   6       )                     =         x   1     *     S   5       +       y   1     *     S   7       +       z   1     *     S   9                     =       P   8     +     P   10     +     P   12                           Δ   423     =                  x   4     |                      y   2           z   2               y   3           z   3           |                +     y   4       |                      z   2           x   2               z   3           x   3           |                +     z   4       |                      x   2           y   2               x   3           y   3           |     
                  Δ   423     =         x   4          (         y   2          z   3       -       z   2          y   3         )       +       y   4          (         z   2          x   3       -       x   2          z   3         )       +       z   4          (         x   2          y   3       -       y   2          x   3         )                     =         x   4          (       P   1     -     P   2       )       +       y   4          (       P   3     -     P   4       )       +       z   4          (       P   5     -     P   6       )                     =         x   4     *     S   5       +       y   4     *     S   7       +       z   4     *     S   9                     =       P   9     +     P   11     +     P   13                                        
     Because computer can execute only one task at a time, it adds up two terms of the equations first, before adding the third ones to obtain the culling outcome. Thus:                Δ   123     =       P   8     +     P   10     +     P   12                   =       (       P   8     +     P   10       )     +     P   12                   =       S   13     +     P   12                             Δ   423     =       P   9     +     P   11     +     P   13                   =       (       P   9     +     P   11       )     +     P   13                   =       S   14     +     P   13                                    
     If the culling test for Δ 123 =S 13 +P 12  is greater than zero, the polygon where Δ 123  is selected from is visible; on the other hand, if the test outcome for Δ 123  is equal to or less than zero, the polygon is not visible. Likewise, if the test outcome for Δ 423  is greater than zero, the polygon is visible; if the test outcome is not equal to zero, the polygon is not visible. 
     Suppose the pipeline depths of all adders and multipliers used are equal to 3. With enough number of adders and multipliers, the five calculation steps of culling test for both Δ 123  and Δ 423 , as shown in FIG. 3, can be completed within 15 cycles to obtain the outcomes. 
     Shown in FIG. 4 is an aspect of the culling test circuit for the present invention. In this embodiment, a controller  410  is used to control the culling test circuit. The controller  410  controls the data input order to the first multiplexer  421  and the multiplier  430 , and data selections of the three multiplexers  421 ,  422 , and  423 . The culling test circuit consists of one multiplier, one adder/subtractor, two registers, and three multiplexers. The multiplier  430  receives two input data at beginning of each cycle for the computation, and the adder/subtractor  450  generates one output data at the end of each cycle. The whole computation process takes about 20 cycles to test the visibility of two adjacent planes of a 3-dimensional object. 
     Specifically speaking, the first multiplexer  421  has two receiving terminals where the first receiving terminal receives first primitive data from the system controller  410  and is sent to the second receiving terminal of the multiplier  430 . The multiplier  430  has two receiving terminals where the first input terminal receives second primitive data from the system controller  410 , and the second input terminal receives the output signal of the first multiplexer  421 . The first register (R)  441  is used to store data received from the multiplier  430 . The second register is used to store data received from said multiplier  430  as well. The second multiplexer  422  has two receiving terminals where the first terminal receives signals from the multiplier  430  and the third multiplexer  423  also has two receiving terminals receiving signals from the first and the second registers  441  and  442 . The adder receives two primitives data from the second and third multiplexer  422  and  423 , adds to or subtracts from the third multiplexer  423  the primitive data values stored in the second multiplexer  422 . The outcome is then feedback to the first and the second multiplexers  421  and  422  until the whole procedure is completed. 
     Suppose the pipeline depths for both the multiplier  430  and the adder/subtractor  450  are 3, it means that if a computation starts at cycle K, the result of that computation will be obtained at cycle (K+3). One of the programs for the circuit to compute culling test is illustrated in TABLE 1. Take TABLE 1 as an example. A statement “P 1 =y 2 *z 3 ” at cycle  1  means that the computation of y 2  multiplies by z 3  is commenced at cycle  1 . The controller  410  starts to feed the first primitive data z 3  to the first multiplexer  421  and the second primitive data y 2  to the multiplier  430 . The multiplier then calculates the product of y 2  and z 3 , and its result P 1  is obtained at cycle  4 . The product P 1  is then stored temporarily at a memory medium, the first register  441 . Meanwhile, the computation of P 2 =y 3 *z 2  starts at cycle  2  in the same manner and obtains the result P 2  at cycle  5 . The result is then sent to the second multiplexer  422 . After obtaining the values of P 1  and P 2  at the fifth cycle, the computation P 1 −P 2 , denoted by S 5 , can then be commenced and the result is output to a multiplexer, the first and second multiplexer  421  and  422 . The rest can be explained by analogy. TABLE 2 is the detailed operation process that is induced from the FIG.  4  and TABLE 1. 
     Let S 5 , S 7 , and S 9  denote the common terms:                     y   2           z   2               y   3           z   3                ,                z   2           x   3               z   3           x   3                                       
     and                     x   2           y   2               x   3           y   3                .                          
     Take the calculation for S 5  as an example:                  S   5     =     |                      y   2           z   2               y   3           z   3           |                 =         y   2          z   3       -       z   2          y   3                     =       P   1     -     P   2                                         
     In accordance with FIG.  4  and TABLE 1, the value of P 1  is available at cycle  4  and is stored in the first register  441  and the value of P 2  is obtained at cycle  5  and output to the second multiplexer  422 . The subtraction of P 2  from P 1  starts at cycle  5  and the result S 5  is obtained at cycle  8 . Likewise, the calculations for S 7  and S 9  start at cycle  7  and  9 , and the results are obtained at cycle  10  and  12  respectively. 
     After obtaining the results for S 5 , S 7 , and S 9 , the system then begins the computation of (x 1 *S 5 ) at cycle  8 , (y 1 *S 7 ) at cycle  10 , and (z 1 *S 9 ) at cycle  12 . The culling test for Δ 123  is the sum of these 3 terms, denoted by P 8 , P 10  and P 12 . The final outcome for Δ 123  is then obtained at cycle  19 . The test outcome for triangle Δ 243  is obtained at cycle  20  in the same manner. 
     The controller  410  controls the whole process. It may be pre-installed in the read only memory to control the flow of data and the data selection of the three multiplexers  421 ,  422 , and  423 . 
     At the present time, the culling tests for any planes on a 3-dimensional object are computed individually. It takes 35 cycles to complete culling tests for two different planes of a 3-dimensional object. However, according to this invention, the total time required for two culling tests is 20 cycles. If more calculation devices are provided, for example, more multipliers or adders/subtractors, the total calculation time can be further reduced. For example, if two multipliers and one adder/subtractor are provided, the outcomes of two culling tests can be obtained at cycle  18 . The detailed computation procedures are shown in TABLE 3. 
     While the present invention has been shown and described with reference to a preferred embodiment thereof, and in terms of the illustrative drawings and algorithmic tables, it should not be considered as limited thereby. Various possible modifications, omissions, and alterations could be conceived of by one skilled in the art to the form and the content of any particular embodiment, without departing from the scope of the present invention. 
     
       
         
               
               
               
             
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 T 
                 Multiplier 
                 Adder/Subtractor 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1. 
                  P 1  = y 2  * z 3   
                   
               
               
                 2. 
                  P 2  = y 3  * z 2   
               
               
                 3. 
                  P 3  = z 2  * x 3   
               
               
                 4. 
                  P 4  = z 3  * x 2   
               
               
                 5. 
                  P 5  = x 2  * y 3   
                  S 5  = P 1  − P 2   
               
               
                 6. 
                  P 6  = x 3  * y 2   
               
               
                 7. 
                   
                  S 7  = P 3  − P 4   
               
               
                 8. 
                  P 8  = x 1  * S 5   
               
               
                 9. 
                  P 9  = x 4  * S 5   
                  S 9  = P 5  − P 6   
               
               
                 10. 
                 P 10  = y 1  * S 7   
               
               
                 11. 
                 P 11  = y 4  * S 7   
               
               
                 12. 
                 P 12  = z 1  * S 9   
               
               
                 13. 
                 P 13  = z 4  * S 9   
                 S 13  = P 8  + P 10   
               
               
                 14. 
                   
                 S 14  = P 9  + P 11   
               
               
                 15. 
               
               
                 16. 
                   
                 Δ 123  =  P 12  + S 13   
               
               
                 17. 
                   
                 Δ 423  =  P 13  + S 14   
               
               
                 18. 
               
               
                 19. 
               
               
                 20. 
               
               
                   
               
             
          
         
       
     
     
       
         
               
               
               
               
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                   
                   
                 Input 2 
                 Mulitplier 
                 Output 
                   
                   
                 3 rd   
                 2 nd   
                   
                   
               
               
                 T 
                 Input 1 
                 1 st  Multiplexer 
                 (x) 
                 (x) 
                 1 st  Reg. 
                 2 nd  Reg. 
                 Multiplexer 
                 Multiplexer 
                 +/− 
                 Output (+/−) 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1. 
                 y 2   
                 z 3  : — 
                 P 1  = y 2  * z 3   
                   
                   
                   
                   
                   
                   
                   
               
               
                 2. 
                 y 3   
                 z 3  : — 
                 P 2  = y 3  * z 2   
               
               
                 3. 
                 y 2   
                 x 3  : — 
                 P 3  = z 2  * x 3   
               
               
                 4. 
                 z 3   
                 x 3  : — 
                 P 4  = z 3  * x 2   
                 P 1   
                 P 1   
               
               
                 5. 
                 x 2   
                 y 3  : — 
                 P 5  = x 2  * y 3   
                 P 2   
                 P 1   
                   
                 P 1  : — 
                 P 2  : — 
                 S 5  = P 1  − P 2   
               
               
                 6. 
                 x 3   
                 y 2  : — 
                 P 6  = x 3  * y 2   
                 P 3   
                 P 3   
                   
                   
                 — : — 
               
               
                 7. 
                   
                   
                   
                 P 4   
                 P 3   
                   
                 P 3  : — 
                 P 4  : — 
                 S 7  = P 3  − P 4   
               
               
                 8. 
                 x 1   
                 — : S 5   
                 P 8  = x 1  * S 5   
                 P 5   
                 P 5   
                   
                   
                 — : S 5   
                   
                 S 5   
               
               
                 9. 
                 x 4   
                 — : S 5   
                 P 9  = x 4  * S 5   
                 P 6   
                 P 5   
                   
                 P 5  : — 
                 P 6  : — 
                 S 9  = P 5  − P 6   
               
               
                 10. 
                 y 1   
                 — : S 7   
                 P 10  = y 1  * S 7   
                   
                   
                   
                   
                 P 6  : S 7   
                   
                 S 7   
               
               
                 11. 
                 y 4   
                 — : S 7   
                 P 11  = y 4  * S 7   
                 P 8   
                 P 8   
                   
                   
                 P 6  : — 
               
               
                 12. 
                   
                 S 7  : S 9   
                 P 12  = z 1  * S 9   
                 P 9   
                 P 8   
                 P 9   
                 — : S 9   
               
               
                 13. 
                   
                 S 7  : S 9   
                 P 13  = z 4  * S 9   
                 P 10   
                 P 8   
                 P 9    
                 P d  : — 
                 — : P 10   
                 S 13  = P 8  + P 10   
               
               
                 14. 
                   
                 S 7  : S 9   
                   
                 P 11   
                 P 11   
                 P 9    
                 — : P 9   
                 P 11  : — 
                 S 14  = P 9   + P 11   
               
               
                 15. 
                   
                 S 7  : S 9   
                   
                 P 12   
                 P 12   
                   
                   
                 — : P 10   
               
               
                 16. 
                   
                 S 13  : S 9   
                   
                 P 13   
                 P 13   
                   
                 P 12  : — 
                 —: S 13   
                 Δ 123  = P 12  + S 13   
                 S 13   
               
               
                 17. 
                   
                 S 13  : S 14   
                   
                   
                 P 13   
                   
                 P 13  : — 
                 —: S 14   
                 Δ 423  = P 13  + S 14   
                 S 14   
               
               
                 18. 
               
               
                 19. 
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 Δ 123   
               
               
                 20. 
                   
                   
                   
                   
                   
                   
                   
                   
                   
                 Δ 423   
               
               
                   
               
             
          
         
       
     
     
       
         
               
               
               
               
             
               
               
               
               
             
           
               
                 TABLE 3 
               
               
                   
               
               
                 T 
                 Multiplier 1 
                 Multiplier 2 
                 +/− 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1. 
                  P 1  = y 2  * z 3   
                  P 2  = y 3  * z 2   
                   
               
               
                 2. 
                  P 3  = z 2  * x 3   
                  P 4  = z 3  * x 2   
               
               
                 3. 
                  P 5  = x 2  * y 3   
                  P 6  = x 3  * y 2   
               
               
                 4. 
                   
                   
                  S 5  = P 1  − P 2   
               
               
                 5. 
                   
                   
                  S 7  = P 3  − P 4   
               
               
                 6. 
                   
                   
                  S 9  = P 5  − P 6   
               
               
                 7. 
                  P 8  =  x 1  * S 5   
                  P 9  = x 4  * S 5   
               
               
                 8. 
                 P 10  =  y 1  * S 7   
                 P 11  = y 4  * S 7   
               
               
                 9. 
                 P 12  =  z 1  * S 9   
                 P 13  = z 4  * S 9   
               
               
                 10. 
               
               
                 11. 
                   
                   
                 S 13  = P 8  + P 10   
               
               
                 12. 
                   
                   
                 S 14  = P 9  + P 11   
               
               
                 13. 
               
               
                 14. 
                   
                   
                 Δ 123  = P 12  + S 13   
               
               
                 15. 
                   
                   
                 Δ 423  = P 13  + S 14   
               
               
                 16. 
               
               
                 17. 
               
               
                 18.