13 3D Object Representations (B-Splines, sweep, CSG, Fractals)

T. Raghuveera

Objectives:

• Understand the properties of B-Spline curves
• Understand the theory behind Sweep, CSG and Fractal representations of objects

Discussion:

Recall the discussion from the previous module, on B-Splines, where we have used Cox-DE Boor recurrence relations to derive B -Spline blending functions of order ‘m’. Below is the figure representing the B-Spline blending functions of order ‘3’ i.e., degree 2, which are called Quadratic B-Spline blending functions.

Cubic Periodic B-Splines:

Let’s put m=4, and k=0,1,2,…n, on Uniform knot vector T(t0=0, t1=1, … ., tn=n), the Blending functions we get are called Cubic functions, and the spline curves thus formed are called Cubic B-Spline curves. If we follow the same derivation procedure as given in the previous module (Mod-12) using Cox-De Boor relation, we get the equations for the first Cubic B-Spline blending function N0,4(t) as below.

It can be observed that the function N0,4(t) has its span in the interval [0,4], and so N1,4(t) has its span in the interval [1,5] and so on. The cubic B-Spline blending function shapes are as given below. Cubic B-Splines exhibit 2-smoothness, unlike the quadratic curves, which are only 1 smooth. Also that the dependency between the number of control points, and the degree of the curves is thus broken, which is an important requirement for blending functions. Nk,4(t) are shifted versions of N0,4(t), where the shift is k units to the right, assuming uniform knot vector.

Properties of B-Splines:

a) The mth order B-Spline function are piecewise polynomials of order m à have Cm-2 continuity. àe.g B-     Spline order 4 have C2 continuity.

b) Convex Hull Property: A B-spline curve is contained in the convex hull of at most m control points.

c) The B-spline blending function Nk,m(t) begins at tk and ends at tk+1 . Its support is [tk ,tk+1]

d) The range of the parameter t is divided among a total of L+m knots

e) The order m can never exceed the number of control points L+1 i.e., m ≤ L+1

f) Each curve segment is affected by m–1 control points.

g) Any one control point can affect the shape of at most m-1 curve sections.

h) If standard knot vector is used B-splines will interpolate the first and last control points.

i) Each B-spline function Nk,m(t) is non-negative for every t, and the family of such functions sums to     unity, that is

    j) Exhibit Affine Invariance

k)Bezier Curves are Special Cases of B-spline Curves (when m=L+1=4, on the standard knot vector)

l) Exhibit Variation Diminishing property.

If the properties are closely observed, a good chunk of them are similar to that of Bezier splines. The properties, f and g listed above, address the issue of Local control as this being the important requirement, for blending functions. The property ‘f’ reads, ‘each of the curve segment is effected by only (m-1) control points’, that means, if we want to locally control the shape of a curve without effecting the other part of the curve, it is possible, by adjusting either of the 3 control points, that influence the curve section, thus achieving local control. The property ‘g’ reads: ‘any one control point can affect the shape of at most (m-1) curve sections’, and means that, a control point can influence the shape of (m-1) curve sections and not all, in this sense, it achieves the objective of local control. Property ‘h’ says that, if ‘standard knot vector’ is used, B-Spline curve interpolates the first and last control points (as we know from Bezier curves). So we can make a B-spline curve behave like a Bezier curve, on standard knot vector (as given in the properties). Let’s understand what is a ‘standard knot vector’ and how do we derive it.

Standard Knot Vector:

If this knot vector is used the curve interpolates the first and last control points. The steps to derive a standard knot vector, given, ‘order’ m and ‘no. of control points’, L+1, are as follows:

i.  There are a total of L+m+1 knots

ii. The initial m knots all share the value 0

iii.The knots tm to tL increase in increments of 1 through 1 till L–m+1

iv.The final m knots tL+1 to tL+m  all equal L–m+2

Ex: When m=4 and there are 8 control points the standard knot vector is T(0,0,0,0,1,2,3,4,5,5,5,5). If the knot vector in the above example is closely observed, there are some knots that are repeated and these knots are called multiple knots. The knots, 0, 5 are called multiple knots with a multiplicity of 4.

Splines curves generated on standard knot vector are called ‘Open B -Splines’. As property ‘i’ reads, Cubic Bezier curves are a special case of B-Splines, when standard knot vector is used and m=L+1=4. (You can try this as a proof.)

Sweep Representations:

Let’s focus on the other 3D object representation techniques, and one of them is called sweep representation. Sweep representation assumes that we have a 2D object at hand and shall produce a 3D object by sweep. Sweep is simply an extension of an object along a specific direction or path. The two categories of sweep are Translational sweep and Rotational Sweep. Translational sweep involves extending an object along a specific direction forming 3D shapes. For ex: see the figure below, assume a circle represented in parametric form P(u), when this is extended along a direction using parameter v, the trace produced is hollow straight tube like shape as shown below.

Rotational sweep involves rotating an object about a specific axis by 360° forming 3D shapes. For ex: see the figure below, Assume a circle represented in parametric form P(u), also assume an axis of rotation, which is shown as a straight line, when the 2D circle shape is rotated about the axis of rotation by 360°, the shape produced is a hollow circular tube as shown, which is a 3D shape.

Constructive Solid Geometry (CSG):

CSG is an interesting technique used to represent 3D objects, by using Boolean operations. This is an example of solid modeling where we model not only the outer surface but also the inside of an object. Here complex 3D shapes are created by applying Boolean operations on simple or primitive 3D shapes. The standard Boolean operations performed are union, intersection and difference. These operations can also be applied hierarchically over a collection of shapes. Shown below are two basic shapes cube and a cylinder (figure (a)), the intersection of which gives shape shown in figure (b), the difference of which gives shape shown in figure (c).

CSG implementation using Ray Casting technique:

Ray Casting is a technique where a ray is fired from each pixel location on a 2D plane into the outer space along exactly a perpendicular direction i.e., the z-direction (if the firing plane is assumed as the XY plane) as shown in the figure below. As the ray hits surfaces of various objects, along its path, we apply Boolean operations and decide the final shape based on the surface limits.

Shown below is a ray fire into the 3D space along z-direction, from a pixel on the XY plane. The ray touches points A, C, B, D along its path, where AB are the bounds of obj1, and CD are the bounds of obj2 as shown below.

Octree representation:

This is an example of solid modeling or space partitioning representation of 3 D objects. Before we get to understand what Octree representation is, let’s try to understand Quadtree representation which is in 2D space. As shown in the figure below, a 2D space is divided into 4 quadrants, then each quadrant is investigated for non-homogeneity, and divide any non-homogeneous quadrant further into 4 sub quadrants, and repeat this process till all sub quadrants are homogeneous (as shown in the figure below).

If we extend the discussion for 3D space, what we get are homogeneous volumes, and the representation is called Octree because a 3D space is subdivided into 8 volume octants. We divide the non-homogeneous volumes further into 8 octants, and we repeat this process till all volumes are homogeneous, as shown below. Each volume element is called a voxel (volume pixel)

BSP (Binary Space Partitioning) trees:

This is also an example of solid modeling. Here a 3D space is divided into two using an infinitely large 2D plane. This plane is called the plane of sub-division, and it divides the 3D space into two parts. The planes are generally chosen such that, they are extensions of surface planes of 3D objects in the world. In 2D, the space is divided into two, by a line, while in 3D it’s a plane. As can be seen in the figure below, in 2D, space A is divided by a line X into two regions say B, C. Now another line say Y divides, the region B into two say D and E. The binary tree formed is shown in the figure. We can extend the same discussion for 3D but now it’s a plane that divides a volume into two sub volumes as shown.

Fractals:

Fractals are procedural elements that are used to create shapes such as mountains, Clouds, terrain, coast line, trees, fern and so on. A procedure is repeatedly applied by allowing variations in every iteration, to get fractal shapes. The techniques discussed in the previous sections, are not efficient for representing some naturally occurring shapes like those mentioned above, and fractals have come to rescue. The best example is, viewing a mountain: from a distance a mountain appears with smooth edges. As we move closer or as we zoom in, more details appear and the surfaces and edges are no smoother, instead they are more rugged. With still more zoom, roughness increases and the more rugged edges appear. With every zoom level more details appear.

A Fractal has two basic characteristics:

• infinite detail at every point
• Certain self-similarity between the object parts and the overall features of the object.

‘Infinite detail’ means, the size of the object is not finite. As we tend to see more and more details and higher zoom levels, the size of the object tends to infinity, but the coordinate extents of the object remain bound within a finite region of space.

‘Self-similarity’ means subparts are scaled down version of the whole.

Classification of fractals:

• Statistically Self-Similar fractals:–  Parts have same statistical properties as original
• Initiator: start with a shape
• Same or different scaling factor for all sub-parts
• Generator: replace subparts with a self-similar random pattern
• Commonly used to model trees, shrubs and other plants
• Deterministically Self-Similar Fractals
• Parts are scaled copies of original
• Initiator: start with a shape
• Generator: replace subparts with scaled copy of original
• Commonly used to model trees, shrubs and other plants
• Self-affine Fractals
• Parts have same statistical properties as original
• Initiator: start with a shape
• Uses different scaling parameters in different directions
• Generator: replace subparts with a self-affine random pattern
• Commonly used to model Terrain, Water and clouds.
• Invariant Fractals
• Formed with non-linear transformations
• Initiator: functions in complex space
• Uses squaring and inversion of functions in complex space.
• Ex: Mandelbrot sets (shown in the figure below), Julia Sets.

Fractal Dimension:

Unlike Euclidean dimension, fractal dimension (D) is a measure of roughness or fragmentation of the object, and it not always an integer.

Shown below in the figure is sub -division of Euclidean object to obtain a self-similar fractal, assuming a fixed scaling factor ½ . The figure shows the relation between the number of sub parts ‘n’ and the scaling factor ‘s’. DE represents Euclidean dimension. As shown, for a line we know that DE=1, and for two sub parts (n=2), the scaling factor s must be ½ . For a square, DE=2, and for four sub parts (n=4), the scaling factor s must be ½. For a cube, DE=3, and for the same scaling factor ½ we obtain 8 sub parts (n=8). The relation between n and s can now be written as

ns^DE=1,

The fractal dimension D can be represented in the same form as

ns^D=1

Solving the expression for D, by taking natural logarithms on both sides, we get

Koch Curve:

Also known as the ‘snow flake’ curve, is a pure self-similar fractal, obtained by repeatedly applying a procedure as shown.

  Steps:

• Start with an initial shape called the initiator (consider a Triangle as initiator)

• Use a generator shape (divide one side of initiator into 3 parts, consider a 1/3 part, and arrange 4 such parts as the shape of generator) as shown

• Replace the sides of the initiator with the generator to get the 1st generation curve.
• Repeat this process and create other generations as shown in the figure below.

The Koch curve shown above, is for 3 generations, assuming the initiator shape as the 0th generation. If observed carefully, the length of the shape in the 1st generation is larger than that of 0th generation, by a factor, and so are the lengths of the other generations when compared with their previous generations. That means, the size is growing but the space/area that it takes is almost the same as any other generation, thus the idea of ‘infinite detail in finite space’.

If we assume that the length of the side of the initial shape is 1, and then the length generator is 4/3, thus after 1st iteration, the side of the initiator is larger by a factor of 1/3. The length of each side of the Koch curve increases by a factor of 4/3 at each step, while the line segment lengths are reduced by a factor of 1/3. The fractal dimension for the Koch curve can be computed as assuming n=4, s=1/3.

ln 4

                      ln 3              1.26

Thus the fractal dimension D of Koch curve is neither 1 nor 2 but a fractional value 1.26.

Particle Systems:

These are used to model phenomena such as fire, explosions, smoke, moving water, sparks, falling leaves, clouds, fog, snow, dust, meteor tails, stars and galaxies, or abstract visual effects like glowing trails, magic spells and so on.

Summary:

• Understood the properties of B-Splines,
• Learnt what are open B-Splines, and standard knot vector
• earnt other representations like sweep, CSG, BSP, Octrees, Fractals.