Unit-II

Curves and Fractals

 Curve Generation:-
Many real world object are neither perfectly flat nor smoothly curved but often have
rough, jagged contours. For drawing these things we can use two approaches to
draw curved lines
a) One approach is to use a curve generation algorithm such as DDA.
b) Second approach the curve is approximated by a number of small straight line
segments.

Circular Arc Generation Using DDA Algorithm:

 The equation for an arc in the angle parameter can be given as
x=Rcosɵ +x0
y=Rsinɵ +y0 --------------------------------- (1)
 Where, (x0, y0 ) is the center of curvature , & R is the radius of arc.

 Differentiating equation (1) we get,

dx= - Rsinɵ dɵ
dy= Rcosɵ dɵ -------------------- (2)
 From equation (1) we can solve for Rcosɵ & Rsinɵ as follows
x=Rcosɵ +x0
i.e. Rcosɵ = x- x0 And
y=Rsinɵ +y0
i.e. Rsinɵ=y- y0 -------------------------------- (3)
 Substituting valued of R cosɵ & Rsinɵ from equation (3) in equation (2) we
get.
dx= - (y- y0 ) dɵ And
dy= (x- x0 ) dɵ ---------------------------- (4)
 The values of dx & dy indicate in x & y increment respectively, to be added in
the current point on the arc . Therefore we can write,
x2 = x1 +dx = x1 -( y1 – y0 ) dɵ
y2 = y1 +dy = y1 +( x2 – x0 ) dɵ ----------------------- (5)
  From equation (5) we can see the next point on the arc is the function of dɵ. To
have smooth curve the neighboring points on the arc should be close to each
other.
 To achieve this, the value of dɵ should be small enough not to leave gaps in the
arc. Usually, the value of dɵ can be determined from the equation .
dɵ= Min (0.01,1/(3.2*( | x- x0 | + | y- y0 | )))

Algorithm:
1. Read the center of a curvature , say (x0 , y0 )
2. Read the angle , say ɵ
3. Read the starting point of the arc , say (x,y)
4. Calculate dɵ
dɵ= Min (0.01,1/(3.2*( | x- x0 | + | y- y0 | )))
5. Initialize Angle = 0
6. While (Angle < ɵ)
do
{ plot (x,y)
x = x - ( y – y0 ) * dɵ
y = y + ( x – x0 ) * dɵ
Angle = Angle + dɵ
}
7. Stop

Problems in True-Curve Generation Approach:-

a) To specify a curve, we need more information than just its endpoints.
b) It is difficult to apply transformation.
c) New clipping algorithm is required to clip arcs.
d) The curve generation algorithm for curves other than circular or elliptical such as
airplane wings or cars or human faces etc.

 Representation of Parametric & Non-Parametric Curves:-

Parametric Curves :
A parametric surface is defined by equations that generate
vertex coordinates as a function of one or more free variables.
Non-Parametric Curves :
Nonparametric curve which is simply defined as a specific
set of vertices which are generally connected with straight lines.

 Spline Representation :
  To produce a smooth through a designed set of points, a flexible strip called spline
is used.
 Such a spline curve can be mathematically described with a piecewise cubic
polynomial function whose first & second derivatives are continuous across the
various curve section.
 We can , specify a spline curve by giving a set of coordinates position, called
control points, which indicates the general shape of the curve.
 When polynomial sections are fitted so that the curve passes through all control
points as shown in fig (a) , the resulting curve is said to interpolate the set of control
points.
 On the other hand, when the polynomial are fitted to the path which is not
necessarily passing through all control points, the resulting curve is said to
approximation the set of control points as shown in fig (b).

 Spline Specification:
There are three basic ways of specification spline curve:
I. We can state the set of boundary condition that are imposed on the spline.
II. We can state the matrix that characteristics the spline.
III. We can state set of blending function that calculate the positions along the curve
path by specifying combination of geometric constraints on the curve.
• Advantage: Smooth with just a few control point
• Disadvantage: Can be hard to control
• Uses:
a) Representation Of Smooth Shapes. Either As Outlines In 2D Or With
Patches Or Subdivision Surfaces In 3D
b) Animation Paths

 Parametric Representation of Circle & Ellipse:-

 Parametric Representation of Circle:-

 A circle can be defined as the locus of all points that satisfy the equations
x = r cos(t) y = r sin(t)
 where x,y are the coordinates of any point on the circle,
a) r is the radius of the circle and
 b) t is the parameter - the angle subtended by the point at the circle's center.

 Parametric Representation of Ellipse:-

An ellipse can be defined as the locus of all points that satisfy the equations
x = a cos t y = b sin t
where:
a) x,y are the coordinates of any point on the ellipse,
b) a, b are the radius on the x and y axes respectively,
c) t is the parameter, which ranges from 0 to 2π radians.

 Bezier curves:-
 Bezier curve is discovered by the French engineer Pierre Bezier. These curves
can be generated under the control of other points.
 Approximate tangents by using control points are used to generate curve.
 The Bezier curve can be represented mathematically as –

Where pi is the set of points and Bin(t) represents the Bernstein polynomials which
are given by −

Where n is the polynomial degree, i is the index, and t is the variable.

  The simplest Bézier curve is the straight line from the point P0 to P1. A
quadratic Bezier curve is determined by three control points. A cubic Bezier
curve is determined by four control points.

 Properties of Bezier Curves:

a) They generally follow the shape of the control polygon, which consists of the
segments joining the control points.
b) They always pass through the first and last control points.
c) They are contained in the convex hull of their defining control points.
d) The degree of the polynomial defining the curve segment is one less that the
number of defining polygon point. Therefore, for 4 control points, the degree of
the polynomial is 3, i.e. cubic polynomial.
e) No straight line intersects a Bezier curve more times than it intersects its control
polygon.
f) They are invariant under an affine transformation.
g) Bezier curves exhibit global control means moving a control point alters the
shape of the whole curve.
h) A given Bezier curve can be subdivided at a point t=t0 into two Bezier segments
which join together at the point corresponding to the parameter value t=t0.

B-Spline curves:-

The Bezier-curve produced by the Bernstein basis function has limited flexibility.
 First, the number of specified polygon vertices fixes the order of the resulting
polynomial which defines the curve.
 The second limiting characteristic is that the value of the blending function is
nonzero for all parameter values over the entire curve.
The B-spline basis contains the Bernstein basis as the special case. The B-spline basis
is non-global.
 B-spline curve is defined as a linear combination of control points Pi and B-
spline basis function Ni, k (t) given by

Where,
 {pi: i=0, 1, 2….n} are the control points
 k is the order of the polynomial segments of the B-spline curve. Order k means that
the curve is made up of piecewise polynomial segments of degree k - 1,
 the Ni,k(t) are the “normalized B-spline blending functions”. They are described by
the order k and by a non-decreasing sequence of real numbers normally called the
“knot sequence”.

The Ni, k functions are described as follows –

and if k > 1,

And t€ (tk-1 , tn+1 )

 Properties of B-spline Curve:-

a) The sum of the B-spline basis functions for any parameter value is 1.
b) Each basis function is positive or zero for all parameter values.
c) Each basis function has precisely one maximum value, except for k=1.
d) The maximum order of the curve is equal to the number of vertices of defining
polygon.
e) The degree of B-spline polynomial is independent on the number of vertices of
defining polygon.
f) B-spline allows the local control over the curve surface because each vertex
affects the shape of a curve only over a range of parameter values where its
associated basis function is nonzero.
g) The curve exhibits the variation diminishing property.
h) The curve generally follows the shape of defining polygon.
i) Any affine transformation can be applied to the curve by applying it to the
vertices of defining polygon.
j) The curve line within the convex hull of its defining polygon.

 Fractals:-
To draw a Mountain, Trees, rivers, clouds we use rough, jagged & random surfaces.
Such surfaces are called as Fractals.
Examples of Fractals: Clouds, Grass, Fire, Modeling Mountains, Coastline,
Branches of a tree etc.
 Fractals are used in many areas such as −
1. Astronomy − For analyzing galaxies, rings of Saturn, etc.
2. Biology/Chemistry − For depicting bacteria cultures, Chemical reactions, human
anatomy, molecules, plants,
3. Others − For depicting clouds, coastline and borderlines, data compression,
diffusion, economy, fractal art, fractal music, landscapes, special effect, etc.

 Classification of fractals:-
Fractals can be classified according to their self similarity. There are three parts
of self similarity found in fractals:
a) Self Similar Fractals:-
 These fractals have parts that are scaled down versions of the entire object.
 We construct the object subparts by applying a scaling parameter’s to the
overall shape.
 We can use same scaling or different scaling factor s for all subparts. This
fractal is used to model trees, clouds & terrain.
b) Self Affine:-
 Formed with different scaling parameters sx, sy, sz in different coordinates
direction.
 This fractal used to model Terrain, Water, clouds etc.
c) Invariant Fractal Sets :-
 This class of fractals included self squaring fractals such as Mandelbrot set,
which are formed with squaring function in complex space, & self inverse
fractals, from with inversion procedure.

 Topological Dimension:-
 Consider an object composed of elastic or clay.
 If the object deformed into a line or line segment we assign its dimension Dt = 1.
 If object deforms into a plane or half disk we assign its dimension Dt = 2.
 If object deforms into all space or half space or sphere we assign its dimension
Dt = 3.
 The dimension Dt is referred to as the Topological Dimension.

 Fractal Dimension:-
 Imagine that a line segment of length L is divided into N identical pieces. The
length of each line segment I can be given as l=L/N
 The ratio of length of original line segment & the length of each part of the line
segment is referred to as scaling factor & is given as. S=L/l
 
From above two equation we can write N=s i.e. N=s1
In other words we can say that if we scale a line segment a line segment by a
factor 1/s then we have to add N pieces together to get the original line
segment. If we scale square by a factor 1/s we will get a small square In case of
s=2 we require 4 pieces of square to get original square. In general we can write
N=s2 Similarly for cubical object we have N=s3
 We have seen that we can specify the dimension of the object by a variable D.
Here the exponent of s is a measure of object dimension. Thus we can write,
N=s D .
Solving for D we get D=log N/log s This D is called Fractal Dimension.

 Hilbert’s curves:-
 The Hilbert’s curves can be constructed by following successive approximations. If
a square is divided into four quadrants we can draw the first approximation to the
Hilbert’s curves by connecting center point of each quadrant.
 The second approximation to the Hilbert’s curves can be drawn by further
subdividing each of the quadrants & connecting their centers before moving to next
major quadrant.
 The third approximation subdivides the quadrants again. Connecting their centers of
finest level of quadrant before stepping to the next level of the quadrant.

First Approximation Second Approximation Third Approximation

From the above figure we can easily note the following points about Hilbert’s
Curve.
a) If we infinitely extend the approximation to the Hilbert’s curve the curve fills
the smaller quadrants but never cross itself.
b) The curve is close to every point in the square.
c) The curve passes through a point on a grid, which becomes twice as fine with
each subdivision.
d) There is no limit to subdivision & therefore length of curve is infinite.
e) With each subdivision length of curve increases by factor of 4.
f) At each subdivision the scale changes by 2but length changes by 4 therefore for
Hilbert’s curve Topological Dimension is one but the fractal Dimension is 2.

 Koch curve:-
 The Koch Curve can be drawn by dividing line into 4 equal segments with scaling
factor 1/3 & middle two segments are so adjusted that they form adjacent sides of an
equilateral triangle as shown in first approximation of the curve.
 To apply the second approximation to the Koch curve we have to repeat the above
process for each of the four segments. The resultant curve as shown in second
approximation curve.
 The resultant curve has more wiggles & its length is 16/9 times the original length.

From the above fig. we can easily note the following points about the Koch
curve:
a) Each repetition increases the length of the curve by factor 4/3.
b) Length of curve is infinite.
c) Unlike Hilbert’s Curve , It doesn’t fill an area.
d) It doesn’t deviate much from its original shape.
e) If we reduce the scale of the curve of the curve by 3, we find the curve that
looks just like the original one; but we must assemble 4 such to make the
original , so we have 4=3D
f) Solving for D we get D=log3 4 = log 4 / log 3=1.2618
Therefore for Koch Curve Topological dimension is 1 but fractal dimension I
1.2618.