.
Feudal Priority Trees 09.october.1997 GFX

by Hin Jang

Interactive displays of complex polyhedral objects require a hidden-surface removal algorithm that maintains efficiently the priority relations among all polygons. One such method uses the notion of feudal priority which, at the preprocessing phase, identifies the relative placement of polygons. This phase of the algorithm is only executed once for a given environment. A rendering priorty list evolves from traversing the feudal priority tree whenever the viewpoint changes.

The algorithm described herein introduces several notions of priority as follows [1]

One-way priority of a polygon P relative to polygon Q is denoted P -> Q and is classified into four categories

If there are no polygons on the front side of P, then P has absolute front priority. All polygons that are coplanar and have the same unit direction with P have the same priority as P.

If there are no polygons on the back side of P, then P has absolute back priority. All polygons that are coplanar and have the same unit direction with P have the same priority as P.

The group of polygons P and Q are separated by a plane S or a plane S is the separating plane of P and Q if one of the following conditions is true

P <| S and Q >| S
Q <| S and P >| S

Of the remaining polygons, after the removal of all polygons with either absolute front priority or absolute back priority, there could exist a separating plane S to all other polygons. If such a plane is found to separate the polygons into groups C and D, then the arrangement is denoted

C <| S |< D or
D >| S |> C

If a separating plane cannot be found, a splitting plane S is chosen. Polygons are assigned into groups C or D. Polygons cut by S are split into two smaller polygons and each of these is assigned to the appropriate group.

At the preprocessing phase, the algorithm determines the one-way priority of all polygons in relation to the ith polygon. A one-way priority table lists all polygons under their appropriate category. Polygons that are under the "coplanar" category in the ith row are copied into the rows of these coplanar polygons. These polygons are then placed under categories "front side" and "back side" depending on their normal direction with the ith polygon.

The next step adds absolute priority polygons to the feudal priority tree and deletes them from the one-way priority table. In the ith row, if there are no polygons under the categories "back side" and "cutting", the ith polygon has absolute back priority. This polygon is added to the bunch Bj on the right side of the current connecting node. The ith row is deleted from the table. A polygon with absolute front priorty is determined in a similar manner. This polygon is added to the bunch Fj on the left side of the current connecting node and the row from which this polygon was found is deleted. After this first iteration, when all absolute priority polygons are found, the polygons are deleted from all the rows that remain in the table. The process continues for the i + 1 row and so forth until no polygons in the table meet the absolute priority criteria. The polygons in bunches Fj and Bj surround all polygons below them in a feudal priority tree.

                           root

                            +
                           / \
                         /  |  \
                       /    |    \
                    F1      |      B1
                   /        |        \
                 /          |          \
              F2           S1            B2
                         /  |  \
                       /    |    \
                     /      |      \
                   +       O1        +
                 / | \             / | \
                /  |  \           /  |  \
              F1   |   B1       F1   |   B2
                   |                 |
                  S2                S3
                /  |  \           /  |  \
              .    |    .       .    |    .
             .     .     .     .     .     .

The one-way priority table, at this stage, does not contain any absolute priority polygons. In the ith row, if no polygon is under the category "cutting" then polygon Q is the separating plane to all other polygons except those coplanar with Q. If there is more than one candidate separating plane, the one with the most balanced polygons on both sides is chosen. The polygon is a switch node in the feudal priority tree with the label Sk where k > 0. Those polygons on the front side of Sk are put in the group Gf and those on back side of Sk are put in the group Gb. The process of determining the absolute priority polygons in these groups is identical to the process described earlier. If a separating plane does not exist, then some polygon Q is chosen as the splitting plane Sk. The subsequent groupings of Gb and Gf are similarily defined. Those polygons that are coplanar with the splitting plane Q are added to the bunch Ok.

The algorithm traverses a feudal priority tree in depth-order. The run-time performance of this algorithm exceeds that of similiar spatial ordering schemes because the occurance of polygon splitting is kept at a minimum, back-face culling is required only at the switch nodes and within certain bunches, and optimal tree balance can be maintained easily [1].



[1] Chen, H., and W. Wang, "The Feudal Priority Algorithm on Hidden-Surface Removal," Computer Graphics, SIGGRAPH 1996 Proceedings, 30(4):55-64

[2] Fuchs, H., Z.M. Kedem and B.F. Naylor, "On Visible Surface Generation by a Priori Tree Structure," Computer Graphics, 14(3):124-133, July 1980

[3] Naylor, B.F., A Priori Based Technique for Determining Visibility Priority for 3-D Scenes, Ph.D. Dissertation, University of Texas at Dallas, May 1981


.
Bézier Forms 08.december.1997 GFX

by Hin Jang
revised on 05.september.1999

The Bézier forms of curves and surfaces, named after French mathematician Pierre Bézier, are parametric entities primarily used in computer-aided geometric design. What follows is a brief review of these forms.

A Bézier curve of degree n is defined as

             n
            ----
   p(t)  =  \     pi Bi,n(t)
            /
            ----
            i=0

   0 <= t <= 1

The points pi form the Bézier control polygon. The Berstein polynomials are
                  n!
   Bi,n(t)  =  ----------  (1 - t)n - i ti
              i!(n - i)!

For cubic curves (n = 3), for example,

   B0,3  =  -t3 + 3t2 - 3t + 1
   B1,3  =   3t3 - 6t2 + 3t
   B2,3  =  -3t3 + 3t2
   B3,3  =   t3

The expression for p(t) is then

   p(t)  =  (1 - t)3p0  +  3t(1 - t)2p1  +  3t2(1 - t)p2  +  t3p3

A fast method to evaluate p(t) is forward differencing, a simplied form of an adaptive scheme. From the derivative of the Berstein polynomial Bi, n (t)

   d              d       n!
  --- Bi,n(t)  =  ---  ---------- ti (1 - t)n-i
  dt             dt   i!(n - i)!


                    i n!                       (n - i)n!
              =  ---------- ti-1 (1 - t)n-i  -  ---------- (1 - t)n-i-1
                 i!(n - i)!                    i!(n - i)!


                    n(n - 1)!                          n(n - 1)!
              =  ---------------- ti-1 (1 - t)n-i  -  -------------- ti (1 - t)n-i-1
                 (i - 1)!(n - i)!                    i!(n - i - 1)!


              =  n(Bi-1,n-1(t) - Bi,n-1(t))

the derivative of the Bézier curve p(t) is
                    n
    d              ----
   --- p(t)  =  n  \     (Bi-1,n-1(t) - Bi,n-1(t)) pi
   dt              /
                   ----
                   i=0


                    n                         n-1
                   ----                      ----
             =  n  \     Bi-1,n-1(t) pi  -  n  \     Bi,n-1(t) pi
                   /                         /
                   ----                      ----
                   i=1                       i=0


                    n-1                       n-1
                   ----                      ----
             =  n  \     Bi,n-1(t) pi+1  -  n  \     Bi,n-1(t) pi
                   /                         /
                   ----                      ----
                   i=0                       i=0


                    n-1
                   ----
             =  n  \     (pi+1 - pi) Bi,n-1(t)
                   /
                   ----
                   i=0

[6].

A rational Bézier curve of degree n, can have its shape modified without changing the control polygon. The weights wi influence the shape of the curve given fixed points pi.

                      n
              1      ----
   p(t)  =  ------   \     wi pi Bi,n(t)
             w(t)    /
                     ----
                     i=0
             n
            ----
   w(t)  =  \     wi Bi,n(t)
            /
            ----
             i=0

For a rational cubic curve, the expression is
             (1 - t)3p0w0 + 3t(1 - t)2p1w1 + 3t2(1 - t)p2w2 + t3p3w3
   p(t)  =  ------------------------------------------------------
                (1 - t)3w0 + 3t(1 - t)2w1 + 3t2(1 - t)w2 + t3w3


A tensor product Bézier surface p(s, t) of degree m by n is defined as
                m      n
               ----   ----
   p(s, t)  =  \      \      pij Bi,m(s) Bj,n(t)
               /      /
               ----   ----
               i=0    j=0

   0 <= s <= 1
   0 <= t <= 1

The points pi j form a Bézier control net, the vertices of the characteristic polyhedron that surrounds the surface. The Berstein polynomials Bi, m(s) and Bj, n(t) are defined as for Bézier curves. For a bicubic surface, the expression is
                                                       | (1 - t)3   |
   p(s, t)  =  [(1 - s)3  3s(1 - s)2  3s2(1 - s)  s3] P | 3t(1 - t)2 |
                                                       | 3t2(1 - t) |
                                                       | t3         |

where the contol net P is

         | p00  p01  p02  p03 |
   P  =  | p10  p11  p12  p13 |
         | p20  p21  p22  p23 |
         | p30  p31  p32  p33 |

The derivatives of the tensor product Bézier surface, with respect to s and t, are
                       n      m-1
    d                 ----   ----
   --- p(s, t)  =  m  \      \      (pi+1,j - pi,j) pi,j Bi,m-1(s) Bj,n(t)
   ds                 /      /
                      ----   ----
                      j=0    i=0


                       m      n-1
    d                 ----   ----
   --- p(s, t)  =  n  \      \      (pi,j+1 - pi,j) pi,j Bj,n-1(t) Bi,m(s)
   dt                 /      /
                      ----   ----
                      i=0    j=0

[6].

A Bézier triangle of degree n is defined as


               ----
   p(s, t)  =  \     pijk Bijk,n(s, t)
               /
               ----
              i+j+k=n

   0 <= s <= 1
   0 <= t <= 1

   0 <= (1 - s - t) <= 1

The variables i, j and k are non-negative integers whose sum is n and the points pi j k form a triangular Bézier control net. The bivariate Berstein polynomials of degree n are
                      n!
   Bijk, n(s, t)  =  -------  (1 - s - t)i sj tk
                    i!j!k!



[1] Bernstein, S., Démonstration du théorème de Weierstrass fondeé sur le calcul des probabilités. Harkov Soobs. Matem ob-va, 13:1-2, 1912

[2] Bézier, P., Procédé de définition numérique des courbes et surfaces non mathématiques. Automatisme, XIII(5):189-196, 1968

[3] Bézier, P., Mathematical and Practical Possibilities of UNISURF. In R. Barnhill and R. Riesenfeld, editors, Computer Aided Geometric Design, Academic Press, 127-152, 1974

[4] Bézier, P., Essay de définition numérique des courbes et des surfaces expérimentales. Ph.D. dissertation, University of Paris VI, France, 1977

[5] Boehm, W., "Generating the Bézier Points of B-spline Curves and Surfaces," Computer Aided Design, 13(6):365-366, 1981

[6] Farin, G., Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide, Fourth Edition, Academic Press, San Diego, 1997

[7] Foley, J.D., A. van Dam, S.K. Feiner, and J.F. Hughes, Computer Graphics Principles and Practice, Second Edition, Addison-Wesley, Reading, 488-491, 1990

[8] Shao, L., and H. Zhou, "Curve Fitting with Bézier Cubics," Graphical Models and Image Processing, 58(3):223-232, May 1996

[9] Vaishnav, H., and A. Rockwood, "Calculating Offsets of a Bézier Curve," ACM Proceedings on the Second Symposium on Solid Modeling, 491-492, 1993


.
Splines 14.december.1997 GFX

by Hin Jang
revised on 16.january.1999

Spline curves and surfaces are defined in a highly malleable and compact representation allowing for local control and smoothness. Definitions and properties of these constructs are reviewed briefly herein.

The most common spline curve is the B-spline curve and is defined as the weighted sum of basis functions.


             n
            ----
   p(t)  =  \      Pi Ni,p(t)
            /
            ----
            i=0

   0 <= t <= (n - p + 2)

There are n + 1 control points Pi. The basis functions are defined by the relation

              |  1   if ti <= t < ti+1
   Ni,0(t)  =  |
              |  0   otherwise


and

                 t - ti
   Ni,p(t)  =  ------------ Ni,p-1(t)  +
                ti+p - ti


                 ti+p+1 - t
              -------------- Ni+1,p-1(t)
                ti+p+1 - ti+1

The support for each Ni, p(t) is non-zero on the interval [ti, ti + p].

For a quadratic B-spline p(t), where n = 5 and p = 3, the knot values are


   t0  =  0      t3  =  1      t6  =  4
   t1  =  0      t4  =  2      t7  =  4
   t2  =  0      t5  =  3      t8  =  4

and the basis functions are

   N0,3(t)  =  (1 - t)2 N2,1(t)
   N1,3(t)  =  0.5t(4 - 3t)N2,1(t) + 0.5(2 - t)2 N3,1(t)
   N2,3(t)  =  0.5t2 N2,1(t) + 0.5(-2t2 + 6t - 3)N3,1(t) + 0.5(3 - t)2 N4,1(t)
   N3,3(t)  =  0.5(t - 1)2 N3,1(t) + 0.5(-2t2 + 10t - 11)N4,1(t) +
              0.5(3 - t)2 N4,1(t) + 0.5(4 - t)2 N5,1(t)
   N4,3(t)  =  0.5(t - 2)2 N4,1(t) + 0.5(-3t2 + 20t - 32)N5,1(t)
   N5,3(t)  =  (t - 3)2 N5,1(t)  

where

   N0,1(t)  =  1 for t = 0, 0 otherwise
   N1,1(t)  =  1 for t = 0, 0 otherwise
   N2,1(t)  =  1 for t on [0,1], 0 otherwise
   N3,1(t)  =  1 for t on [1,2], 0 otherwise
   N4,1(t)  =  1 for t on [2,3], 0 otherwise
   N5,1(t)  =  1 for t on [3,4], 0 otherwise
 
p(t) is the composite of four curve segments defined as such

   p0(t)  =  (1 - t)2p0 + 0.5t(4 - 3t)p1 + 0.5t2p2
   p1(t)  =  0.5(2 - t)2p1 + 0.5(-2t2 + 6t - 3)p2 + 0.5(t - 1)2p3
   p2(t)  =  0.5(3 - t)2p2 + 0.5(-2t2 + 10t - 11)p3 + 0.5(t - 2)2p4
   p3(t)  =  0.5(4 - t)2p3 + 0.5(-3t2 + 20t - 32)p4 + (t - 3)2p5

A tensor product B-spline surface is defined as

                m      n
               ----   ----
   p(s, t)  =  \      \      pij Ni,m(s) Nj,n(t)
               /      /
               ----   ----
               i=0    j=0

   0 <= s <= 1
   0 <= t <= 1

The points pi j form a rectangular control net. The B-spline basis functions Ni, m(s) and Nj, n(t) are defined as for B-spline curves over a partition of the real axis called a knot vector [5].

The properties common to all splines are

[2].



[1] Barghiel, C., R. Bartels, and D. Forsey, Pasting Spline Surfaces, TR-95-32, Department of Computer Science, University of British Columbia, 1995

[2] Blanc, C., and C. Schlick, "X-Splines: A Spline Model Designed for the End-User," Computer Graphics, SIGGRAPH 1995 Proceedings, 29(4):377-386

[3] de Boor, C., "On Calculating with B-splines," Journal of Approximation Theory, 6(1):50-62, 1972

[4] Eck, M., and H. Hoppe, "Automatic Reconstruction of B-Spline Surfaces of Arbitrary Topological Type," Computer Graphics, SIGGRAPH 1996 Proceedings, 30(4):325-334

[5] Farin, G., Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide, Fourth Edition, Academic Press, San Diego, 1997

[6] Foley, J.D., A. van Dam, S.K. Feiner, and J.F. Hughes, Computer Graphics Principles and Practice, Second Edition, Addison-Wesley, Reading, 491-507, 1990

[7] Halstead, M.A., B.A. Barsky, S.A. Klein, and R.B. Mandell, "Reconstructing Curved Surfaces From Specular Reflection Patterns Using Spline Surface Fitting of Normals," Computer Graphics, SIGGRAPH 1996 Proceedings, 30(4):335-342

[8] Loop, C., "Smooth Spline Surfaces over Irregular Meshes," Computer Graphics, SIGGRAPH 1994 Proceedings, 28(4):303-310

[9] Qin, H., and D. Terzopoulos, "Dynamic Manipulation of Trianguluar B-Splines," ACM Proceedings on the Third Symposium on Solid Modeling, 351-360, 1995