## Computer Graphics

Solved Answers from 2014

Answer 2: a) Mid point Line Drawing Algorithm

• Line passes between E and NE.
• Point that is closer to intersection of Q must be chosen, either E or NE
• Let the distance between points E and Q be dQ and
between points E and M be dM.
• The decision variable works between the distance dQ and dM.
(decision variable, d depends upon dQ - dM)
• If d < 0; when Mid point is above the line intersecting at Point Q (dM > dQ); then point E is to be chosen.
• If d > 0; when Mid point lies below the line intersecting at point Q (dQ > dM); then point NE is chosen.
• If d = 0; either point (E or NE) is chosen consistently.
• Now we need to understand and prove mathematically:
• Line Equation as a funtion f(x): y = mx + B; where m = dy/dx
• So, we can also say that y = (dy/dx)x + B
• Line equation as implicit function: f(x,y) = ax + by + c = 0
• So, from above,
y.dx = dx.x + B.dx
dx.x - y.dy + B.dx = 0
• By comparing the co-efficients, we can say that:
a = dy, b = -dx and c = B.dx
###### Properties(proof by case analysis):
• F(Xm, Ym) = 0; when any point M is on line.
• F(Xm, Ym) < 0; when any point M is above line.
• F(Xm, Ym) > 0; when any point M is below line.
• The decision of choosing the point is based on the value of the function at mid point M at (Xp + 1, Yp + 0.5)
• We define f(Xp + 1, Yp + 0.5) as the decision variable, d
• So, D = F(Xp + 1, Yp + 0.5)

### Increment M by one in x-direction.

Dnew = F(Xp + 1 + 1, Yp + 0.5)
= a(Xp + 2) + b(Yp + 0.5) + c
Dold = a(Xp + 1) + b(Yp + 0.5) + c
• Dnew - Dold ( = a) is the incremental difference, ΔE
• Or Dnew = Dold + a
• Also, ΔE = a; or ΔE = dy
• Now, Dnew = Dold + ΔE or
Dnew = Dold + dy

### Increment M by one in x-direction and y-direction.

Dnew = F(Xp + 1 + 1, Yp + 0.5 + 1)
= a(Xp + 2) + b(Yp + 1.5) + c
Dold = a(Xp + 1) + b(Yp + 1.5) + c
• Dnew - Dold ( = a + b) is the incremental difference, ΔE
• Or Dnew = Dold + a + b
• Also, ΔE = a + b; or ΔE = dy - dx
• Now, Dnew = Dold + ΔE or
Dnew = Dold + dy - dx
• At each step, the Mid-Point Line Algorithm, chooses between 2 pixels based on the size of the decision variable (d) calculated at the previous step
• First mid-point first, D = Dstart is at (Xo + 1, Yo + 0.5)
= a(Xo + 1) + b(Yo + 0.5) + c
= aXo + a + bYo + b/2 +c
= F(Xo,Yo) + a + b/2
• But F(Xo, Yo) = 0 as the point is on the line
• Therefore, Dstart = a + b/2 = dy - dx/2
• use Dstart to choose second pixel and so-on.
This is how Mid-Point Line Algorithm works!
```  Answer 2) b)
End-Points are: (0,0) and (5,5)
x1 = 0, x2 = 0 and y1 = 5, y2 = 5
dy = y2-y1 and dx = x2-x1
=> dy = 5 and dx = 5
Dstart = 2dy - dx
= 10 - 5
= 5
ΔE = 2dy = 10
ΔNE = 2(dy - dx)
= 2(5-5)
=0
if d <= 0
d = d + ΔdE, x = x + 1
if d > 0
d = d + ΔdNE, x = x + 1, y = y + 1
1) Dstart = 5 > 0;
d = 5 + 0 = 5
x = 1; y = 1

2) d = 5 + 0 = 5
x = 2; y = 2

3) d = 5 + 0 = 5
x = 3, y = 3

4) d = 5 + 0 = 5
x = 4, y = 4

5) d = 5 + 0 = 5
x = 5, y = 5

```
Interactive Computer Graphics Vs Non-Interactive Graphics
Interactive Computer Graphics Non-Interactive Graphics
1 Involves a two-way communication between a computer and a user. No user involvement is present
2 The observer or the user operating it, is given an input device for iteracting with the system User does not have any kind of control over the image.
3 For example: the video game controller of the ping pong game. This helps him to signal his/her request to the computer. No controller for user required as interaction is not there.
4 The computer can modify the displayed picture appropriately on receiving signals from input devices. Image is merely the product of static stored programs
5 User can give a series of commands, each one generating a graphical response from the computer. In this way, the user maintains a conservation, a dialogue, wth the computer. The image is totally under the control of program instructions, no under the user. Example: Screen Savers

Raster vs Random Scan
Raster Scan Random Scan
1) It has ability to display areas filled with solid colors or patterns 1) Only draws lines and characters
2) Uses interlacing 2) Don't use interlacing
3)The beam is moved all over the screen one scan line at a time. 3)The beam is moved between the end points of the graphics primitives
4) Lower resolution 4) Higher resolution
5) Less expensive 5) More expensive
6) Refresh rate is independent of picture complexity. 6) Refresh rate directly depends on picure complexity.
7) Uses monochrome or shadow mask type 7) Uses monochrome or beam penetration type
8) Editing is difficult 8) Editing is easy
9)produces jagged lines 9)produces smooth lines

Answer 6a: Boundary Representation
• It is also known as B-Rep
• It is a method to represent solid shapes using the limits.
• It is an extension to the wire-frame model by adding face information to the latter.
• In B-rep, a solid is bounded by its surface and has its interior and exterior.
• There are two types of information in B-rep:
1. Topological
It provides the relationships among vertices, edges and faces, and also include orientation of edges and faces.
2. Geometric
It provides the actual dimensions of its entities.
• The orientation of faces is important.
Using right-hand rule, the ordering of vertices is done, guaranteeing that the normal vector of that face is pointing to the exterior of the solid.
• Normally, order is counterclockwise.
• Boundary Representation of top surface can be
• 6,7,2,1 or
• 7,2,1,6 or
• 2,1,6,7 or
• 1,6,7,2

Constructive Solid Geometry (CSG)
CSG involves a technique to represent and model solid complex surfaces or objects by using differnt Boolean operators. It presents the shapes that are usually visually complex in appearance.
In 3D computer graphics, and CAD, CSG is mainly used for procedural modeling of solids. It can also be performed on polygon meshes.
A CSG solid is constructed from few primitives, i.e, through blocks, wedges, spheres, cylinders, cones and toruses.
Data Structures of CSG representation are based on the concept of trees. The data of the solid model is stored in its database in a tree called CSG tree. It uses inverted tree which is an ordered binary tree for the representation of data. This means that the root node is on the top. By ordering, it is meant that each tree node has a left and branches. Binary means that each node has two sub-nodes, i.e two branches.
The total number of nodes of a tree directly depends upon the number of primitives of the solid to which it is decomposed to. If there are 'n' primitives, there are (n-1) Boolean operations, and the total no. of nodes will be (2n - 1) nodes in the CSG tree.
Some CSG primitives used for representation are:
Block:
This is a cube whose geometry is defined by its width W, height H, and depth D.
Cylinder:
This is a right circular cylinder whose geometry is defined by its its radius R and length H.
Sphere:
This is defined by its radius R.
Cone:
This is a right circular cone whose geometry is defined by base radius R, and height H.
Wedge:
This is a right-angled wedge whose height H, width W and base depth D form its geometric data.
Torus:
The geometry is defined by the inner radius R1 and the outer radius R2.
Polygon Mesh
A polygon mesh is a collection of edges, vertices, and polygons connected such that each edge is shared by atmost 2 polygons.
Polygon meshes can be used to represent objects with curved surfaces, although representation is only approximate.

Obvious errors can be made arbitrarily small by using more and more polygons to create a piece wise linear approximation, but this increases space requirements.
A polygon mesh consists of three kinds of mesh elements: vertices, edges and faces. The information describing the mesh elements are mesh connectivity and mesh geometry. The connectivity or the topology defines the incidence relationships of mesh elements. While, the mesh geometry gives the information about the position and other geometric characteristics of each vertex.
```
A) Points are the vertices of the polygon.
Each point can be shared by many adjacent polygons of the same mesh.

B) Edges are the straight line segments that join two adjacent points.
Edges can't be shared by no more than two polygons. Edges that are not shared represent the boundary of the polygon mesh object and are displayed in light blue if boundaries and hard edges are visible in a 3D view.

C) Polygons are the closed shapes that make up the "tiles" of the mesh.
```