Mid-Point Circle Algorithm and Bresenham's Line Trace

PART 1: Mid-Point Circle Algorithm

Concept

The Mid-Point Circle Algorithm draws a circle using only integer arithmetic (additions/subtractions). At each step it uses a decision parameter to choose between two candidate pixels.

Eight-Way Symmetry

A circle centered at origin has 8-fold symmetry. If $(x, y)$ lies on the circle, so do:

$$(\pm x, \pm y), \quad (\pm y, \pm x)$$

So only one octant (0 to 45°) needs to be computed; the rest are reflected.

Circle Function

For a circle of radius $r$ centered at origin:

$$f(x, y) = x^2 + y^2 - r^2$$

• $f < 0$: point inside
• $f = 0$: point on circle
• $f > 0$: point outside

Decision Parameter

Starting at $(0, r)$, moving in $+x$, the next pixel is either E $(x+1, y)$ or SE $(x+1, y-1)$. The midpoint is $\left(x+1, y-\tfrac{1}{2}\right)$:

$$P_k = f\left(x_k+1,\ y_k-\tfrac{1}{2}\right) = (x_k+1)^2 + \left(y_k-\tfrac{1}{2}\right)^2 - r^2$$

Initial value:

$$P_0 = \tfrac{5}{4} - r \approx 1 - r$$

Decision Rule

Algorithm

1. (x, y) = (0, r);  P = 1 - r
2. Plot (x, y) and 8 symmetric points
3. While x < y:
       x = x + 1
       if P < 0:  P = P + 2x + 1
       else:      y = y - 1;  P = P + 2x - 2y + 1
       Plot (x, y) and 8 symmetric points

Advantages

• Integer arithmetic only, no floating point
• Fast and efficient
• Accurate circle approximation

PART 2: Bresenham's Line Trace from (6, 9) to (2, 3)

Given data

• Start: $(x_1, y_1) = (6, 9)$
• End: $(x_2, y_2) = (2, 3)$

Step 1: Differences

$$\Delta x = |x_2 - x_1| = |2 - 6| = 4$$ $$\Delta y = |y_2 - y_1| = |3 - 9| = 6$$

Since $\Delta y > \Delta x$, slope $> 1$, so we step along the y-axis and decide x.

Direction of travel (from start to end):

• x decreases: $x_{inc} = -1$
• y decreases: $y_{inc} = -1$

Step 2: Initial Decision Parameter

For the steep case (driving along y):

$$P_0 = 2\Delta x - \Delta y = 2(4) - 6 = 2$$

Step 3: Update Rules (driving along y)

where $2\Delta x = 8$ and $2\Delta x - 2\Delta y = 8 - 12 = -4$.

Step 4: Trace Table

Plot start point $(6, 9)$. Then iterate for $\Delta y = 6$ steps (y from 9 down to 3).

Final Plotted Points

$$(6, 9),\ (5, 8),\ (5, 7),\ (4, 6),\ (3, 5),\ (3, 4),\ (2, 3)$$

Verification

Line has slope $\dfrac{3-9}{2-6} = \dfrac{-6}{-4} = 1.5$. The traced points correctly approximate this steep line, ending exactly at $(2, 3)$. ✓

Cohen-Sutherland Line Clipping Algorithm and Sutherland-Hodgeman Polygon Clipping

STEP 1 - EXTRACT (Given Data)

Polygon vertices:

• $A(100, 150)$
• $B(200, 250)$
• $C(300, 200)$

Clipping window (triangular) vertices:

• $W_1(100, 300)$
• $W_2(300, 300)$
• $W_3(200, 100)$

Task: State Cohen-Sutherland line clipping algorithm; clip triangle ABC against triangular window using Sutherland-Hodgeman.

STEP 2 - SOLVE

Part 1: Cohen-Sutherland Line Clipping Algorithm

The clipping window divides the plane into 9 regions, each with a 4-bit outcode:

1001 | 1000 | 1010
-----+------+-----
0001 | 0000 | 0010
-----+------+-----
0101 | 0100 | 0110

Bit assignments (from left): Top ($y>y_{max}$), Bottom ($y<y_{min}$), Right ($x>x_{max}$), Left ($x<x_{min}$).

Algorithm:

1. For endpoints $P_1(x_1,y_1)$, $P_2(x_2,y_2)$, compute their 4-bit outcodes.
2. Trivial accept: if $\text{code}(P_1)\ \text{OR}\ \text{code}(P_2)=0000$, draw the whole line.
3. Trivial reject: if $\text{code}(P_1)\ \text{AND}\ \text{code}(P_2)\neq 0000$, discard the line.
4. Otherwise: pick an endpoint with a nonzero outcode, compute its intersection with the corresponding window boundary:
   • Left: $y=y_1+m(x_{min}-x_1),\ x=x_{min}$
   • Right: $y=y_1+m(x_{max}-x_1),\ x=x_{max}$
   • Bottom: $x=x_1+\tfrac{1}{m}(y_{min}-y_1),\ y=y_{min}$
   • Top: $x=x_1+\tfrac{1}{m}(y_{max}-y_1),\ y=y_{max}$
5. Replace the outside endpoint with the intersection point, recompute its outcode, and repeat from step 2 until accept or reject.

Part 2: Sutherland-Hodgeman Polygon Clipping

Window edges (traversed so interior lies to the left):

Let me verify orientation. Vertices $W_1(100,300),W_2(300,300),W_3(200,100)$. The centroid is $\left(\tfrac{100+300+200}{3},\tfrac{300+300+100}{3}\right)=(200,\ 233.3)$.

Inside test: For directed edge $W_a\to W_b$, point $P$ is inside if $$f(P)=(x_b-x_a)(y_p-y_a)-(y_b-y_a)(x_p-x_a)\ge 0.$$

Check orientation using centroid for each edge; adjust sign so centroid is inside.

Edge 1: $W_1(100,300)\to W_2(300,300)$

$f(P)=(300-100)(y_p-300)-(300-300)(x_p-100)=200(y_p-300)$

Centroid: $200(233.3-300)<0$. So centroid gives negative; inside means $f(P)\le 0$, i.e. $y_p\le 300$.

All inside. Output list I: A(100,150), B(200,250), C(300,200)

Edge 2: $W_2(300,300)\to W_3(200,100)$

$f(P)=(200-300)(y_p-300)-(100-300)(x_p-300)$ $=-100(y_p-300)+200(x_p-300)$

Centroid $(200,233.3)$: $-100(-66.7)+200(-100)=6670-20000=-13330<0$. So inside means $f(P)\le 0$.

Compute for each vertex of list I:

• A(100,150): $-100(150-300)+200(100-300)=15000-40000=-25000\le0$ → Inside
• B(200,250): $-100(250-300)+200(200-300)=5000-20000=-15000\le0$ → Inside
• C(300,200): $-100(200-300)+200(300-300)=10000+0=+10000>0$ → Outside

Process pairs of list I (A→B→C→A):

A(in)→B(in): add B. B(in)→C(out): add intersection of BC with edge 2.

Line B(200,250)→C(300,200): parametric $x=200+100t,\ y=250-50t$. Edge 2 line: through (300,300) and (200,100): direction $(-100,-200)$, i.e. slope $2$, line $y-300=2(x-300)\Rightarrow y=2x-300$.

Substitute: $250-50t=2(200+100t)-300=100+200t$ $250-50t=100+200t\Rightarrow150=250t\Rightarrow t=0.6$ $x=200+60=260,\ y=250-30=220$. → Intersection $P_1(260,220)$. Add $P_1$.

C(out)→A(in): add intersection of CA with edge 2, then add A.

Line C(300,200)→A(100,150): $x=300-200t,\ y=200-50t$. Into $y=2x-300$: $200-50t=2(300-200t)-300=300-400t$ $200-50t=300-400t\Rightarrow350t=100\Rightarrow t=0.2857$ $x=300-57.14=242.86,\ y=200-14.29=185.71$. → $P_2(242.86,185.71)$. Add $P_2$, then A.

Output list II: B(200,250), $P_1$(260,220), $P_2$(242.86,185.71), A(100,150)

Edge 3: $W_3(200,100)\to W_1(100,300)$

$f(P)=(100-200)(y_p-100)-(300-100)(x_p-200)$ $=-100(y_p-100)-200(x_p-200)$

Centroid: $-100(133.3)-200(0)=-13330<0$. Inside means $f(P)\le 0$.

Check list II:

• B(200,250): $-100(150)-200(0)=-15000\le0$ → Inside
• $P_1$(260,220): $-100(120)-200(60)=-12000-12000=-24000\le0$ → Inside
• $P_2$(242.86,185.71): $-100(85.71)-200(42.86)=-8571-8572=-17143\le0$ → Inside
• A(100,150): $-100(50)-200(-100)=-5000+20000=+15000>0$ → Outside

Process pairs (B→$P_1$→$P_2$→A→B):

B(in)→$P_1$(in): add $P_1$ $P_1$(in)→$P_2$(in): add $P_2$ $P_2$(in)→A(out): add intersection of $P_2$A with edge 3.

Edge 3 line through (200,100),(100,300): slope $=\tfrac{300-100}{100-200}=-2$, line $y-100=-2(x-200)\Rightarrow y=-2x+500$. Line $P_2(242.86,185.71)\to A(100,150)$: $x=242.86-142.86t,\ y=185.71-35.71t$. $185.71-35.71t=-2(242.86-142.86t)+500=-485.72+285.72t+500=14.28+285.72t$ $185.71-14.28=285.72t+35.71t\Rightarrow171.43=321.43t\Rightarrow t=0.5333$ $x=242.86-76.19=166.67,\ y=185.71-19.05=166.67$. → $P_3(166.67,166.67)$. Add $P_3$.

A(out)→B(in): add intersection of AB with edge 3, then add B. Line A(100,150)→B(200,250): $x=100+100t,\ y=150+100t$. Into $y=-2x+500$: $150+100t=-2(100+100t)+500=300-200t$ $150+100t=300-200t\Rightarrow300t=150\Rightarrow t=0.5$ $x=150,\ y=200$. → $P_4(150,200)$. Add $P_4$, then B.

Final Clipped Polygon

Vertices: $$P_1(260,220),\ P_2(242.86,185.71),\ P_3(166.67,166.67),\ P_4(150,200),\ B(200,250)$$

Rendering in Computer Graphics and Phong Shading Method

Definition of Rendering (1 mark)

Rendering is the process of generating a final 2D image from a 3D scene description by applying lighting, shading, color, and other visual effects to the geometric objects in the scene. It transforms a mathematical model of a scene into a realistic or stylized visual output.

As stated in the notes:

"Scene description + Illumination Model + Rendering Technique = Image"

In other words, polygon (surface) rendering is the process of calculating intensity and color considerations for polygon surfaces so that objects appear realistic on screen.

Phong Shading Method (3 marks)

Phong Shading (also called Normal-Vector Interpolation Shading) is an advanced surface rendering technique that produces smooth and realistic shading across polygon surfaces.

Concept

Instead of interpolating intensity values (as in Gouraud shading), Phong Shading interpolates the surface normal vectors across each polygon surface. The illumination model is then applied at every individual pixel using the interpolated normal, producing a much more accurate and realistic result.

Algorithm / Steps

1. Calculate the surface normal vector at each vertex of the polygon using the surrounding surface geometry.

2. Interpolate the normal vectors across the entire polygon surface (both along edges and across scan lines) to obtain a normal vector at every interior pixel.

3. Apply the illumination model (e.g., Phong illumination model with ambient, diffuse, and specular components) at each pixel using its interpolated normal vector.

4. Assign the computed intensity to each pixel on the surface.

Diagram (Conceptual)

Vertex N1          Vertex N2
   *-----------------*
    \   Interpolated  \
     \   Normals at    \
      \  each pixel    \
       *-----------------*
     Vertex N3

At every pixel inside the polygon, a normal is interpolated and lighting is computed individually.

Advantages of Phong Shading (0.5 mark)

• Produces highly realistic images with accurate specular highlights.
• Eliminates the Mach band effect (intensity discontinuities visible in flat shading).
• Handles specular reflections much better than Gouraud shading because lighting is computed per pixel.
• Gives smooth shading across polygon surfaces.

Disadvantages of Phong Shading (0.5 mark)

• Computationally expensive because the illumination model must be applied at every pixel rather than just at vertices.
• Slower rendering compared to flat shading and Gouraud shading.
• Requires more memory and processing power, making it less suitable for real-time applications (historically).

Summary Table

Conclusion: Phong Shading is one of the most realistic polygon rendering methods because it computes lighting at every pixel using interpolated normals, at the cost of higher computational requirements.

Short Notes (Any Two)

a. BSP Tree (Binary Space Partition Tree)

A Binary Space Partition (BSP) Tree is a data structure used in computer graphics to recursively subdivide a 3D scene into two sections at each step using a cutting plane that can be at any position and orientation.

Key Points:

• The scene is repeatedly divided into two sub-regions until the partitioning satisfies one or more requirements (e.g., each region contains a manageable number of objects).
• It is a way of grouping spatial data so that it can be processed faster during rendering.
• BSP trees provide more efficient partitioning compared to octrees because the cutting planes can be positioned and oriented to suit the actual spatial distribution of objects in the scene.
• This flexibility reduces the depth of the tree, which in turn reduces the time required to search the tree.

Applications:

• Visible surface identification (determining which surfaces are visible from a given viewpoint)
• Ray-tracing algorithms (organizing objects in virtual space so rays can be tested against objects efficiently)
• Used in many 3D modeling and rendering programs to make rendering faster

Advantage over Octree:

Unlike octrees (which always split along fixed axis-aligned planes), BSP trees allow arbitrary plane orientations, making them more adaptable to complex scene geometries.

c. Intensity Attenuation

Intensity Attenuation refers to the rate of decrease in light intensity with respect to the distance between a light source and an object surface. As distance increases, the light reaching the surface becomes weaker.

For a Point Light Source:

The intensity attenuation is given by the inverse square law:

$$f(d) = \frac{1}{d^2}$$

where d is the distance between the point light source and the object.

For a Distributed Light Source:

A more general attenuation function is used to avoid singularities (division by zero when d is very small) and to give artists more control:

$$f(d) = \frac{1}{a_0 + a_1 d + a_2 d^2}$$

where:

• a₀ = constant attenuation coefficient (surface parameter)
• a₁ = linear attenuation coefficient (surface parameter)
• a₂ = quadratic attenuation coefficient (surface parameter)
• d = distance between the object and the distributed light source

Significance:

• Intensity attenuation is an important factor in realistic illumination models.
• It ensures that objects farther from the light source appear darker, simulating real-world lighting behavior.
• The three coefficients (a₀, a₁, a₂) can be adjusted to control how quickly the light fades with distance, giving flexibility in rendering different lighting environments.