Graphics Model Answer
Question 1 [10 marks]
[a] Derive the mid-point line drawing algorithm for lines with slopes greater than
one. (5 Marks)
Answer
f(x,y)=(y-ys)dx – (x-xs)dy
dintial = F(x+0.5,y+1) = )=(y+1-y)dx – (x+0.5-x)dy = dx-0.5dy = 2dx-dy (2)
d>0
dNE = d(x+1.5,y+2)- Dintial = 2dx-1.5dy – (dx-0.5dy) = dx – dy = 2dx – 2dy (1.5)
d<=0
dN = d(x+0.5,y+2)- Dintial = 2dx-0.5dy – (dx-0.5dy) = dx = 2dx (1.5)
[b] Write the first 10 values of the decision variable when drawing a circle
centered at (200, 300) and having a radius of 50 using Bresenham’s mid-point
algorithm. Write the generated points. (consider the second octant computations)
(5 Marks)
dintial =1-R;
d<0
dN=2*x+2;
d>=0
dNE=2*(x-y)+5;
centre = (200,300)
Decision Computed The8-Generated points
Variable (D) point(x,y)
(0,50) (200,350), (200,250), (200,350), (200,250),
(350,200), (250,200), (350,200), (250,200)
-49 “<0” (1,50) (201,350), (201,250), (199,350), (199,250),
(350,201), (250,201), (350,199), (250,199)
-47“<0” (2,50) And So on ……..
-43“<0” (3,50)
-37“<0” (4,50)
-29“<0” (5,50)
-19“<0” (6,50)
-7“<0” (7,50)
7“>=0” (8,49)
-74“<0” (9,49)
Question 2 [10 marks]
[a] Derive the Hermite’s cubic curve matrix. Write an algorithm to draw the cubic
Hermite curves. Write an algorithm to draw cardinal splines using Hermite curve
algorithm. [5 marks] => [2 for Hermite Derivation, 2 for Hermite Algorithm and 1
for cardinal splines algorithm]
Answer
Hermite Curve Derivation
Hermite curve uses the curve endpoints and the tangents at the endpoints to draw the
curve.
The endpoints are represented as third order (cubic) parametric equation as:
Therefore, the derivatives/tangents with respect to t are:
Hermite curves use four constraints to compute the 4 coefficients of each function. We’ll
derive the coefficients of x(t) only because those of y(t) will follow a similar procedure.
The constraints on x(t) are:
Substituting in x(t) and x’(t) with t=0 and t=1:
Putting the above equations in matrix form:
To solve for the coefficients, we get the inverse matrix as below:
Hermite Algorithm
Using the Hermite basis matrix above, we can say that x(t) can be computed directly
And similarly, y(t)
Loop over the control points taking each two consecutive points:
1. Multiply the basis Matrix with P0.x,T0.x,P1.x,T1.x
xcoeff=GetHermiteCoeff(P0.x,T0.x,P1.x,T1.x);
2. Multiply the basis Matrix with P0.y,T0.y,P1.y,T1.y
ycoeff=GetHermiteCoeff(P0.y,T0.y,P1.y,T1.y);
a. if(numpoints < 2) return;
b. Compute step of t
double dt=1.0/(numpoints-1);
c. Loop over t interval from 0 – 1 with the step
i. Compute x(t) as the dot product of xcoeff and the vector [t3 t2 t 1]
ii. Computer y(t) as the dot product of ycoeff and the vector [t3 t2 t 1]
iii. Plot the point [x(t), y(t)]
Cardinal Splines Algorithm using Hermite
For a given set of points P0, P1, P2, …, Pn, we can draw a curve passing through P1, P2,…,Pn-1 by
calling the Hermite curve drawing algorithm for every interval Pi-Pi+1 , i=1,2,..,n-2. The slope
at Pi is given by:
c is called the ‘tension’ of the curve that takes values from 0 to 1.
1. Set c1 = 1-c
2. Compute T0 as c1*(P[2].x-P[0].x),c1*(P[2].y-P[0].y)
3. Loop over the given set of points starting at the 2nd point:
a. Compute T1 as c1*(P[i+1].x-P[i-1].x),c1*(P[i+1].y-P[i-1].y)
b. Call Hermite algorithm defined above passing (P[i-1], T0, P[i], T1)
c. Set T0 = T1
[b] Explain the recursion in the Bezier curve drawing. Derive a simple algorithm drawing
cubic Bezier curves based on the recursion. [5 marks] => [2 for explanation and 3 for the
algorithm]
Answer
De Casteljau’s Algorithm to recursively draw a Bezier curve. Any Bezier curve can be split
into multiple parts to trace out the curve as straight lines
It’s basic idea is by subdividing each curve segment to produce two separate curve
segments and generate new set of control points for them and draw each segment with
Bezier.
Algorithm:
Start with 4 given points/control points (a, b, c, d)
1. Calculate the midpoints (e, f, g) between these points
2. Calculate the midpoints (h, i)
3. Calculate the midpoint (j)
4. If the length of the lines (ae, eh, hj) are all less than q (where q is chosen to give
smooth curve – typically 1 < q < 10)
a. draw straight lines ae, eh, hj
5. else
a. start again using a, e, h, j as the four known starting points
6. If the length of the lines (ji, ig, gd) are all less than q
a. Draw straight lines ji, ig and gd
7. Else
a. Start again using j, i, g, d as the four known starting points
Question 3 [10 marks]
Given the parametric quadratic curve equations:
2
x (t )=α 0 + α 1 t+α 2 t
2
y ( t ) =β 0+ β1 t+ β 2 t
t ∈ [ 0 ,1 ]
[a] Write an algorithm that takes the coefficients: α 0 , α 1 , α 2 , β0 , β 1 , β2 as parameters and
draws the curve by direct use of the equations. [5 marks]
[b] Derive an algorithm based on the second order difference to draw the curve efficiently
(using floating point addition only) [5 marks]