22.2. 22.2 Description of point sets with equations

Coordinate systems provide means to specify points by numbers. Conditions on these numbers, on the other hand, may define sets of points. Conditions are formulated by equations. The coordinates found as the solution of these equations define the point set.

Let us now consider how these equations can be established.

22.2.1. 22.2.1 Solids

A solid is a subset of the three-dimensional Euclidean space. To define this subset, continuous function is used which maps the coordinates of points onto the set of real numbers. We say that a point belongs to the solid if the coordinates of the point satisfy the following implicit inequality:

Points satisfying inequality are the internal points, while points defined by are the external points. Because of the continuity of function , points satisfying equality are between external and internal points and are called the boundary surface of the solid. Intuitively, function describes the signed distance between a point and the boundary surface.

We note that we usually do not consider any point set as a solid, but also require that the point set does not have lower dimensional degeneration (e.g. hanging lines or surfaces), i.e. that arbitrarily small neighborhoods of each point of the boundary surface contain internal points.

Figure 22.1 lists the defining functions of the sphere, the box, and the torus.

Figure 22.1.  Functions defining the sphere, the block, and the torus.

Functions defining the sphere, the block, and the torus.

22.2.2. 22.2.2 Surfaces

Points having coordinates that satisfy equation are on the boundary surface. Surfaces can thus be defined by this implicit equation. Since points can also be given by the place vectors, the implicit equation can be formulated for the place vectors as well:

A surface may have many different equations. For example, equations , , and M are algebraically different, but they have the same roots and thus define the same set of points.

A plane of normal vector and place vector contains those points for which vector is perpendicular to the normal, thus their dot product is zero. Based on this, the points of a plane are defined by the following vector or scalar equations:

where are the coordinates of the normal and . If the normal vector has unit length, then expresses the signed distance between the plane and the origin of the coordinate system. Two planes are said to be parallel if their normals are parallel.

In addition to using implicit equations, surfaces can also be defined by parametric forms. In this case, the Cartesian coordinates of surface points are functions of two independent variables. Denoting these free parameters by and , the parametric equations of the surface are:

The implicit equation of a surface can be obtained from the parametric equations by eliminating free parameters . Figure 22.2 includes the parametric forms of the sphere, the cylinder and the cone.

Figure 22.2.  Parametric forms of the sphere, the cylinder, and the cone, where Parametric forms of the sphere, the cylinder, and the cone, where u,v\in[0,1] ..

Parametric forms of the sphere, the cylinder, and the cone, where u,v\in[0,1] .


Parametric forms can also be defined directly for the place vectors:

Points of a triangle are the convex combinations of points , and , that is

From this definition we can obtain the usual two-variate parametric form of a triangle substituting by , by , and by :

22.2.3. 22.2.3 Curves

By intersecting two surfaces, we obtain a curve that may be defined formally by the implicit equations of the two intersecting surfaces

but this is needlessly complicated. Instead, let us consider the parametric forms of the two surfaces, given as and , respectively. The points of the intersection satisfy vector equation , which corresponds to three scalar equations, one for each coordinate of the three-dimensional space. Thus we can eliminate three from the four unknowns , and obtain a one-variate parametric equation for the coordinates of the curve points:

Similarly, we can use the vector form:

Figure 22.3 includes the parametric equations of the ellipse, the helix, and the line segment.

Figure 22.3.  Parametric forms of the ellipse, the helix, and the line segment, where Parametric forms of the ellipse, the helix, and the line segment, where t\in[0,1] ..

Parametric forms of the ellipse, the helix, and the line segment, where t\in[0,1] .


Note that we can define curves on a surface by fixing one of free parameters . For example, by fixing the parametric form of the resulting curve is . These curves are called iso-parametric curves.

Two points define a line. Let us select one point and call the place vector of this point the place vector of the line. On the other hand, the vector between the two points is the direction vector. Any other point of the line can be obtained by a translation of the point of the place vector parallel to the direction vector. Denoting the place vector by and the direction vector by , the equation of the line is:

Two lines are said to be parallel if their direction vectors are parallel.

Instead of the complete line, we can also specify the points of a line segment if parameter is restricted to an interval. For example, the equation of the line segment between points and is:

According to this definition, the points of a line segment are the convex combinations of the endpoints.

22.2.4. 22.2.4 Normal vectors

In computer graphics we often need the normal vectors of the surfaces (i.e. the normal vector of the tangent plane of the surface). Let us take an example. A mirror reflects light in a way that the incident direction, the normal vector, and the reflection direction are in the same plane, and the angle between the normal and the incident direction equals to the angle between the normal and the reflection direction. To carry out such and similar computations, we need methods to obtain the normal of the surface.

The equation of the tangent plane is obtained as the first order Taylor approximation of the implicit equation around point :

Points and are on the surface, thus and , resulting in the following equation of the tangent plane:

Comparing this equation to equation (22.1), we can realize that the normal vector of the tangent plane is

The normal vector of parametric surfaces can be obtained by examining the iso-parametric curves. The tangent of curve defined by fixing parameter is obtained by the first-order Taylor approximation:

Comparing this approximation to equation (22.2) describing a line, we conclude that the direction vector of the tangent line is . The tangent lines of the curves running on a surface are in the tangent plane of the surface, making the normal vector perpendicular to the direction vectors of these lines. In order to find the normal vector, both the tangent line of curve and the tangent line of curve are computed, and their cross product is evaluated since the result of the cross product is perpendicular to the multiplied vectors. The normal of surface is then

22.2.5. 22.2.5 Curve modelling

Parametric and implicit equations trace back the geometric design of the virtual world to the establishment of these equations. However, these equations are often not intuitive enough, thus they cannot be used directly during design. It would not be reasonable to expect the designer working on a human face or on a car to directly specify the equations of these objects. Clearly, indirect methods are needed which require intuitive data from the designer and define these equations automatically. One category of these indirect approaches apply control points. Another category of methods work with elementary building blocks (box, sphere, cone, etc.) and with set operations.

Let us discuss first how the method based on control points can define curves. Suppose that the designer specified points , and that parametric curve of equation should be found which “follows” these points. For the time being, the curve is not required to go through these control points.

We use the analogy of the centre of mass of mechanical systems to construct our curve. Assume that we have sand of unit mass, which is distributed at the control points. If a control point has most of the sand, then the centre of mass is close to this point. Controlling the distribution of the sand as a function of parameter to give the main influence to different control points one after the other, the centre of mass will travel through a curve running close to the control points.

Let us put weights at control points at parameter . These weighting functions are also called the basis functions of the curve. Since unit weight is distributed, we require that for each the following identity holds:

For some , the respective point of the curve curve is the centre of mass of this mechanical system:

Note that the reason of distributing sand of unit mass is that this decision makes the denominator of the fraction equal to 1. To make the analogy complete, the basis functions cannot be negative since the mass is always non-negative. The centre of mass of a point system is always in the convex hull of the participating points, thus if the basis functions are non-negative, then the curve remains in the convex hull of the control points.

Footnote. The convex hull of a point system is by definition the minimal convex set containing the point system.

The properties of the curves are determined by the basis functions. Let us now discuss two popular basis function systems, namely the basis functions of the Bézier-curves and the B-spline curves.

22.2.5.1.  Bézier-curve.

Pierre Bézier, a designer working at Renault, proposed the Bernstein polynomials as basis functions. Bernstein polynomials can be obtained as the expansion of according to binomial theorem:

The basis functions of Bézier curves are the terms of this sum ():

Figure 22.4.  A Bézier curve defined by four control points and the respective basis functions (A Bézier curve defined by four control points and the respective basis functions (m=3 ).).

A Bézier curve defined by four control points and the respective basis functions (m=3 ).


According to the introduction of Bernstein polynomials, it is obvious that they really meet condition and in , which guarantees that Bézier curves are always in the convex hulls of their control points. The basis functions and the shape of the Bézier curve are shown in Figure 22.4. At parameter value the first basis function is 1, while the others are zero, therefore the curve starts at the first control point. Similarly, at parameter value the curve arrives at the last control point. At other parameter values, all basis functions are positive, thus they simultaneously affect the curve. Consequently, the curve usually does not go through the other control points.

22.2.5.2.  B-spline.

The basis functions of the B-spline can be constructed applying a sequence of linear blending. A B-spline weights the number of control points by -degree polynomials. Value is called the order of the curve. Let us take a non-decreasing series of parameter values, called the knot vector:

Figure 22.5.  Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles.. Arrows indicate useful interval Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles. where we can find Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles. number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles.

Construction of B-spline basis functions. A higher order basis function is obtained by blending two consecutive basis functions on the previous level using a linearly increasing and a linearly decreasing weighting, respectively. Here the number of control points is 5, i.e. m=4 . Arrows indicate useful interval [t_{k-1},t_{m+1}] where we can find m+1 number of basis functions that add up to 1. The right side of the figure depicts control points with triangles and curve points corresponding to the knot values by circles.


By definition, the th first order basis function is 1 in the th interval, and zero elsewhere (Figure 22.5):

Using this definition, number of first order basis functions are established, which are non-negative zero-degree polynomials that sum up to 1 for all parameters. These basis functions have too low degree since the centre of mass is not even a curve, but jumps from control point to control point.

The order of basis functions, as well as the smoothness of the curve, can be increased by blending two consecutive basis functions with linear weighting (Figure 22.5). The first basis function is weighted by linearly increasing factor in domain , where the basis function is non-zero. The next basis function, on the other hand, is scaled by linearly decreasing factor in its domain where it is non zero. The two weighted basis functions are added to obtain the tent-like second order basis functions. Note that while a first order basis function is non-zero in a single interval, the second order basis functions expand to two intervals. Since the construction makes a new basis function from every pair of consecutive lower order basis functions, the number of new basis functions is one less than that of the original ones. We have just second order basis functions. Except for the first and the last first order basis functions, all of them are used once with linearly increasing and once with linearly decreasing weighting, thus with the exception of the first and the last intervals, i.e. in , the new basis functions also sum up to 1.

The second order basis functions are first degree polynomials. The degree of basis functions, i.e. the order of the curve, can be arbitrarily increased by the recursive application of the presented blending method. The dependence of the next order basis functions on the previous order ones is as follows:

Note that we always take two consecutive basis functions and weight them in their non-zero domain (i.e. in the interval where they are non-zero) with linearly increasing factor and with linearly decreasing factor , respectively. The two weighted functions are summed to obtain the higher order, and therefore smoother basis function. Repeating this operation times, -order basis functions are generated, which sum up to 1 in interval . The knot vector may have elements that are the same, thus the length of the intervals may be zero. Such intervals result in 0/0 like fractions, which must be replaced by value 1 in the implementation of the construction.

The value of the th -order basis function at parameter can be computed with the following Cox-deBoor-Mansfield recursion:

B-Spline( )

  1  
                           IF
                         
                              
                         Trivial case.   2    
                           THEN
                         
                        
                           IF
                         
                           3       
                           THEN
                         
                        
                           RETURN
                         1   4       
                           ELSE
                         
                        
                           RETURN
                         0   5  
                           IF
                         
                           6    
                           THEN
                         
                              
                         Previous with linearly increasing weight.   7    
                           ELSE
                         
                              
                         Here: 0/0 = 1.   8  
                           IF
                         
                           9    
                           THEN
                         
                              
                         Next with linearly decreasing weight.  10    
                           ELSE
                         
                              
                         Here: 0/0 = 1.  11  
                        
                           B-spline(
                           
                           )
                         
                        
                        
                           B-spline(
                           
                           )
                              
                         Recursion.  12  
                           RETURN
                         
                         
                     

Figure 22.6.  A B-spline interpolation. Based on points A B-spline interpolation. Based on points \vec{p}_{0},\ldots,\vec{p}_{m} to be interpolated, control points \vec{c}_{-1},\ldots,\vec{c}_{m+1} are computed to make the start and end points of the segments equal to the interpolated points. to be interpolated, control points A B-spline interpolation. Based on points \vec{p}_{0},\ldots,\vec{p}_{m} to be interpolated, control points \vec{c}_{-1},\ldots,\vec{c}_{m+1} are computed to make the start and end points of the segments equal to the interpolated points. are computed to make the start and end points of the segments equal to the interpolated points.

A B-spline interpolation. Based on points \vec{p}_{0},\ldots,\vec{p}_{m} to be interpolated, control points \vec{c}_{-1},\ldots,\vec{c}_{m+1} are computed to make the start and end points of the segments equal to the interpolated points.


In practice, we usually use fourth-order basis functions , which are third-degree polynomials, and define curves that can be continuously differentiated twice. The reason is that bent rods and motion paths following the Newton laws also have this property.

While the number of control points is greater than the order of the curve, the basis functions are non-zero only in a part of the valid parameter set. This means that a control point affects just a part of the curve. Moving this control point, the change of the curve is local. Local control is a very important property since the designer can adjust the shape of the curve without destroying its general form.

A fourth-order B-spline usually does not go through its control points. If we wish to use it for interpolation, the control points should be calculated from the points to be interpolated. Suppose that we need a curve which visits points at parameter values , respectively (Figure 22.6). To find such a curve, control points should be found to meet the following interpolation criteria:

These criteria can be formalized as linear equations with unknowns, thus the solution is ambiguous. To make the solution unambiguous, two additional conditions should be imposed. For example, we can set the derivatives (for motion paths, the speed) at the start and end points.

B-spline curves can be further generalized by defining the influence of the th control point as the product of B-spline basis function and additional weight of the control point. The curve obtained this way is called the Non-Uniform Rational B-Spline, abbreviated as NURBS, which is very popular in commercial geometric modelling systems.

Using the mechanical analogy again, the mass put at the th control point is , thus the centre of mass is:

The correspondence between B-spline and NURBS basis functions is as follows:

Since B-spline basis functions are piece-wise polynomial functions, NURBS basis functions are piece-wise rational functions. NURBS can describe quadratic curves (e.g. circle, ellipse, etc.) without any approximation error.

22.2.6. 22.2.6 Surface modelling

Parametric surfaces are defined by two variate functions . Instead of specifying this function directly, we can take finite number of control points which are weighted with the basis functions to obtain the parametric function:

Similarly to curves, basis functions are expected to sum up to 1, i.e. everywhere. If this requirement is met, we can imagine that the control points have masses depending on parameters , and the centre of mass is the surface point corresponding to parameter pair .

Basis functions are similar to those of curves. Let us fix parameter . Changing parameter , curve is obtained on the surface. This curve can be defined by the discussed curve definition methods:

where is the basis function of the selected curve type.

Of course, fixing differently we obtain another curve of the surface. Since a curve of a given type is unambiguously defined by the control points, control points must depend on the fixed value. As parameter changes, control point also runs on a curve, which can be defined by control points :

Figure 22.7.  Iso-parametric curves of surface.

Iso-parametric curves of surface.


Substituting this into equation (22.8), the parametric equation of the surface is:

Unlike curves, the control points of a surface form a two-dimensional grid. The two-dimensional basis functions are obtained as the product of one-variate basis functions parameterized by and , respectively.

22.2.7. 22.2.7 Solid modelling with blobs

Free form solids – similarly to parametric curves and surfaces – can also be specified by finite number of control points. For each control point , let us assign influence function , which expresses the influence of this control point at distance . By definition, the solid contains those points where the total influence of the control points is not smaller than threshold (Figure 22.8):

With a single control point a sphere can be modeled. Spheres of multiple control points are combined together to result in an object having smooth surface (Figure 22.8). The influence of a single point can be defined by an arbitrary decreasing function that converges to zero at infinity. For example, Blinn proposed the

influence functions for his blob method.

22.2.8. 22.2.8 Constructive solid geometry

Another type of solid modelling is constructive solid geometry (CSG for short), which builds complex solids from primitive solids applying set operations (e.g. union, intersection, difference, complement, etc.) (Figures 22.9 and 22.10). Primitives usually include the box, the sphere, the cone, the cylinder, the half-space, etc. whose functions are known.

Figure 22.8.  The influence decreases with the distance. Spheres of influence of similar signs increase, of different signs decrease each other.

The influence decreases with the distance. Spheres of influence of similar signs increase, of different signs decrease each other.


Figure 22.9.  The operations of constructive solid geometry for a cone of implicit function The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ). and for a sphere of implicit function The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).: union (The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).), intersection (The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).), and difference (The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).).

The operations of constructive solid geometry for a cone of implicit function f and for a sphere of implicit function g : union (\max(f,g) ), intersection (\min(f,g) ), and difference (\min(f,-g) ).


Figure 22.10.  Constructing a complex solid by set operations. The root and the leaf of the CSG tree represents the complex solid, and the primitives, respectively. Other nodes define the set operations (U: union, Constructing a complex solid by set operations. The root and the leaf of the CSG tree represents the complex solid, and the primitives, respectively. Other nodes define the set operations (U: union, \setminus : difference).: difference).

Constructing a complex solid by set operations. The root and the leaf of the CSG tree represents the complex solid, and the primitives, respectively. Other nodes define the set operations (U: union, \setminus : difference).


The results of the set operations can be obtained from the implicit functions of the solids taking part of this operation:

  • intersection of and : ;

  • union of and : .

  • complement of : .

  • difference of and : .

Implicit functions also allow to morph between two solids. Suppose that two objects, for example, a box of implicit function and a sphere of implicit function need to be morphed. To define a new object, which is similar to the first object with percentage and to the second object with percentage , the two implicit equations are weighted appropriately:

Exercises

22.2-1 Find the parametric equation of a torus.

22.2-2 Prove that the fourth-order B-spline with knot-vector [0,0,0,0,1,1,1,1] is a Bézier curve.

22.2-3 Give the equations for the surface points and the normals of the waving flag and waving water disturbed in a single point.

22.2-4 Prove that the tangents of a Bézier curve at the start and the end are the lines connecting the first two and the last two control points, respectively.

22.2-5 Give the algebraic forms of the basis functions of the second, the third, and the fourth-order B-splines.

22.2-6 Develop an algorithm computing the path length of a Bézier curve and a B-spline. Based on the path length computation move a point along the curve with uniform speed.