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 categoriesAt the preprocessing phase, the algorithm determines the one-way priority of all polygons in relation to the

P <| Q or Q |> P

P is on the front side of Q if at least one vertex of P makes the plane equation of Q greater than zero and all other vertices of P makes the plane equation not less than zero.P >| Q or Q |< P

P is on the back side of Q if at least one vertex of P makes the plane equation of Q less than zero and all other vertices of P makes the plane equation not greater than zero.P \- Q

P is cut by Q if at least one vertex of P makes the plane equation of Q less than zero and at least one vertex of P makes the plane equation of Q greater than zero.P -- Q

P and Q are coplanar if all vertices of P make the plane equation Q equal to zero.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 <| SandQ >| S

Q <| SandP >| 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 |< Dor

D >| S |> CIf 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.

The next step adds absolute priority polygons to the feudal priority tree
and deletes them from the one-way priority table. In the *i*th row, if there are
no polygons under the categories "back side" and "cutting", the *i*th polygon
has absolute back priority. This polygon is added to the bunch Bj on the right
side of the current connecting node. The *i*th 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

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 ----The pointsp(t) = \p_{i}B_{i,n}(t) / ---- i=0 0 <= t <= 1

n! BFor cubic curves (_{i,n}(t) = ---------- (1 - t)^{n - i}t^{i}i!(n - i)!

BThe expression for_{0,3}= -t^{3}+ 3t^{2}- 3t + 1 B_{1,3}= 3t^{3}- 6t^{2}+ 3t B_{2,3}= -3t^{3}+ 3t^{2}B_{3,3}= t^{3}

A fast method to evaluatep(t) = (1 - t)^{3}p_{0}+ 3t(1 - t)^{2}p_{1}+ 3t^{2}(1 - t)p_{2}+ t^{3}p_{3}

d d n! --- Bthe derivative of the Bézier curve_{i,n}(t) = --- ---------- t^{i}(1 - t)^{n-i}dt dt i!(n - i)! i n! (n - i)n! = ---------- t^{i-1}(1 - t)^{n-i}- ---------- (1 - t)^{n-i-1}i!(n - i)! i!(n - i)! n(n - 1)! n(n - 1)! = ---------------- t^{i-1}(1 - t)^{n-i}- -------------- t^{i}(1 - t)^{n-i-1}(i - 1)!(n - i)! i!(n - i - 1)! = n(B_{i-1,n-1}(t) - B_{i,n-1}(t))

n d ---- ---[6].p(t) = n \ (B_{i-1,n-1}(t) - B_{i,n-1}(t))p_{i}dt / ---- i=0 n n-1 ---- ---- = n \ B_{i-1,n-1}(t)p_{i}- n \ B_{i,n-1}(t)p_{i}/ / ---- ---- i=1 i=0 n-1 n-1 ---- ---- = n \ B_{i,n-1}(t)p_{i+1}- n \ B_{i,n-1}(t)p_{i}/ / ---- ---- i=0 i=0 n-1 ---- = n \ (p_{i+1}-p_{i}) B_{i,n-1}(t) / ---- i=0

A *rational Bézier curve* of degree *n*, can have its shape
modified without changing the control polygon. The weights
w_{i} influence the shape of the curve
given fixed points **p**_{i}.

n 1 ----For a rational cubic curve, the expression isp(t) = ------ \ w_{i}p_{i}B_{i,n}(t) w(t) / ---- i=0 n ---- w(t) = \ w_{i}B_{i,n}(t) / ---- i=0

(1 - t)A^{3}p_{0}w_{0}+ 3t(1 - t)^{2}p_{1}w_{1}+ 3t^{2}(1 - t)p_{2}w_{2}+ t^{3}p_{3}w_{3}p(t) = ------------------------------------------------------ (1 - t)^{3}w_{0}+ 3t(1 - t)^{2}w_{1}+ 3t^{2}(1 - t)w_{2}+ t^{3}w_{3}

m n ---- ----The pointsp(s, t) = \ \p_{ij}B_{i,m}(s) B_{j,n}(t) / / ---- ---- i=0 j=0 0 <= s <= 1 0 <= t <= 1

| (1 - t)where the contol net^{3}|p(s, t) = [(1 - s)^{3}3s(1 - s)^{2}3s^{2}(1 - s) s^{3}]P| 3t(1 - t)^{2}| | 3t^{2}(1 - t) | | t^{3}|

|The derivatives of the tensor product Bézier surface, with respect top_{00}p_{01}p_{02}p_{03}| P = |p_{10}p_{11}p_{12}p_{13}| |p_{20}p_{21}p_{22}p_{23}| |p_{30}p_{31}p_{32}p_{33}|

n m-1 d ---- ---- ---[6].p(s, t) = m \ \ (p_{i+1,j}-p_{i,j})p_{i,j}B_{i,m-1}(s) B_{j,n}(t) ds / / ---- ---- j=0 i=0 m n-1 d ---- ---- ---p(s, t) = n \ \ (p_{i,j+1}-p_{i,j})p_{i,j}B_{j,n-1}(t) B_{i,m}(s) dt / / ---- ---- i=0 j=0

A *Bézier triangle* of degree *n* is defined as

----The variablesp(s, t) = \p_{ijk}B_{ijk,n}(s, t) / ---- i+j+k=n 0 <= s <= 1 0 <= t <= 1 0 <= (1 - s - t) <= 1

n! B_{ijk, n}(s, t) = ------- (1 - s - t)^{i}s^{j}t^{k}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 ----There arep(t) = \P_{i}N_{i,p}(t) / ---- i=0 0 <= t <= (n - p + 2)

| 1 if tand_{i}<= t < t_{i+1}N_{i,0}(t) = | | 0 otherwise

t - tThe support for each N_{i}N_{i,p}(t) = ------------ N_{i,p-1}(t) + t_{i+p}- t_{i}t_{i+p+1}- t -------------- N_{i+1,p-1}(t) t_{i+p+1}- t_{i+1}

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

tand the basis functions are_{0}= 0 t_{3}= 1 t_{6}= 4 t_{1}= 0 t_{4}= 2 t_{7}= 4 t_{2}= 0 t_{5}= 3 t_{8}= 4

Nwhere_{0,3}(t) = (1 - t)^{2}N_{2,1}(t) N_{1,3}(t) = 0.5t(4 - 3t)N_{2,1}(t) + 0.5(2 - t)^{2}N_{3,1}(t) N_{2,3}(t) = 0.5t^{2}N_{2,1}(t) + 0.5(-2t^{2}+ 6t - 3)N_{3,1}(t) + 0.5(3 - t)^{2}N_{4,1}(t) N_{3,3}(t) = 0.5(t - 1)^{2}N_{3,1}(t) + 0.5(-2t^{2}+ 10t - 11)N_{4,1}(t) + 0.5(3 - t)^{2}N_{4,1}(t) + 0.5(4 - t)^{2}N_{5,1}(t) N_{4,3}(t) = 0.5(t - 2)^{2}N_{4,1}(t) + 0.5(-3t^{2}+ 20t - 32)N_{5,1}(t) N_{5,3}(t) = (t - 3)^{2}N_{5,1}(t)

N_{0,1}(t) = 1 for t = 0, 0 otherwise N_{1,1}(t) = 1 for t = 0, 0 otherwise N_{2,1}(t) = 1 for t on [0,1], 0 otherwise N_{3,1}(t) = 1 for t on [1,2], 0 otherwise N_{4,1}(t) = 1 for t on [2,3], 0 otherwise N_{5,1}(t) = 1 for t on [3,4], 0 otherwise

p_{0}(t) = (1 - t)^{2}p_{0}+ 0.5t(4 - 3t)p_{1}+ 0.5t^{2}p_{2}p_{1}(t) = 0.5(2 - t)^{2}p_{1}+ 0.5(-2t^{2}+ 6t - 3)p_{2}+ 0.5(t - 1)^{2}p_{3}p_{2}(t) = 0.5(3 - t)^{2}p_{2}+ 0.5(-2t^{2}+ 10t - 11)p_{3}+ 0.5(t - 2)^{2}p_{4}p_{3}(t) = 0.5(4 - t)^{2}p_{3}+ 0.5(-3t^{2}+ 20t - 32)p_{4}+ (t - 3)^{2}p_{5}

A *tensor product B-spline surface* is defined as

m n ---- ----The pointsp(s, t) = \ \p_{ij}N_{i,m}(s) N_{j,n}(t) / / ---- ---- i=0 j=0 0 <= s <= 1 0 <= t <= 1

The properties common to all splines are

[2].

Affine invariance:An affine transformation of a spline is accomplished by applying the transformation to its control points.Convex hull:All splines are contained within the convex hull defined by its control lattice.Oscillation:The number of intersections between a spline surface (or a line for spline curves in two dimensions) and a plane is, at most, equal to the number of intersections between the plane and the control lattice. Splines, therefore, have less oscillations than its control lattice.Local control:Each control point influences the shape of the spline between a pair of consecutiveknots, the joining point between two partitions of the spline.Shape pararmeters:The shape of splines are governed by control points, knots, weights, tension, bias and curvature.Degrees of freedom:Refinement and subdivision algorithms exist that increase the number of degrees of freedom for splines without changing the shape of the spline.Conic sections:The spline model can represent conic sections including circles, ellipses, spheres and surfaces of revolution.Approximation/Interpolation:The spline model has a unified representation for approximation splines and interpolation splines.

[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