CGR All IMP Algorithms Easy to Learn | Computer Graphics IMP Algorithms | Mumbai University

Computer Graphics Quick Level IMP Algorithms Engineering 3rd Semester | CGR All Important Algorithms Easy Level | Mumbai University

Today, we're providing Material on Computer Graphics for engineering students under the Mumbai University syllabus. This guide focuses on the MOST IMP Algorithms of Computer Graphics in Simplest Ways and Easy to Learn or Understand which can be asked in exams, helping you understand patterns for efficient preparation. This syllabus aligns with the Mumbai University standards and can help you achieve good marks with practice.

1. DDA Line Drawing Algorithm

Step 1: Input the two endpoints of the line.
Let the endpoints be $(x_1, y_1)$ and $(x_2, y_2)$ .

Step 2: Calculate the difference.

d x = x_{2} - x_{1}, d y = y_{2} - y_{1}

Step 3: Determine the number of steps.

steps = max (∣ d x ∣, ∣ d y ∣)

Step 4: Calculate the increment for each step.

X_{inc} = \frac{d x}{steps}, Y_{inc} = \frac{d y}{steps}

Step 5: Start drawing the line.
Set initial points:

X = x_{1}, Y = y_{1}

Step 6: Repeat for the number of steps.
For each step:

Plot the point: $(\text{round}(X), \text{round}(Y))$
Update $X$ and $Y$ : $X = X + X_{inc}, Y = Y + Y_{inc}$

Step 7: Stop when all points are plotted.

Algorithm in Short Form

Input $(x_1, y_1)$ and $(x_2, y_2)$ .
Compute $dx = x_2 - x_1$ , $dy = y_2 - y_1$ .
Find $\text{steps} = \text{max}(|dx|, |dy|)$ .
Compute increments: $X_{\text{inc}} = \frac{dx}{\text{steps}}, \quad Y_{\text{inc}} = \frac{dy}{\text{steps}}$
Initialize $X = x_1$ , $Y = y_1$ .
For $i = 1$ to $\text{steps}$ :
- Plot $(\text{round}(X), \text{round}(Y))$ .
- Update $X = X + X_{\text{inc}}, Y = Y + Y_{\text{inc}}$ .
End.

Key Points for Full Marks

Include a small diagram illustrating the line and increments.
Write clearly in steps with mathematical notation.
Draw a flowchart if time permits for bonus clarity.

2. Bresenham Line Drawing Algorithm

Step 1: Input the two endpoints of the line.
Let the endpoints be $(x_1, y_1)$ and $(x_2, y_2)$ .

Step 2: Calculate differences.

d x = x_{2} - x_{1}, d y = y_{2} - y_{1}

Step 3: Initialize decision parameter.

P = 2 d y - d x

Step 4: Initialize starting point.
Set:

X = x_{1}, Y = y_{1}

Step 5: Plot the first point.
Plot $(X, Y)$ .

Step 6: Repeat for $dx$ steps.
For each step:

If $P < 0$ :
- Next point is $(X + 1, Y)$ .
- Update $P = P + 2dy$ .
If $P \geq 0$ :
- Next point is $(X + 1, Y + 1)$ .
- Update $P = P + 2dy - 2dx$ .
Plot the new point.

Step 7: Stop when the endpoint is reached.

Algorithm in Short Form

Input $(x_1, y_1)$ and $(x_2, y_2)$ .
Compute: $dx = x_2 - x_1, \quad dy = y_2 - y_1$
Initialize: $P = 2dy - dx, \quad X = x_1, \quad Y = y_1$
Plot $(X, Y)$ .
For each step until $X = x_2$ :
- If $P < 0$ : $X = X + 1, \quad P = P + 2dy$
- If $P \geq 0$ : $X = X + 1, \quad Y = Y + 1, \quad P = P + 2dy - 2dx$
- Plot $(X, Y)$ .
End.

Key Points for Full Marks

Mention that this algorithm works best for lines with a slope between $0$ and $1$ (for other slopes, modify the algorithm).
Include a small diagram to show how the decision parameter works.
Write the steps clearly and concisely. Add a flowchart if possible for better clarity.

3. Midpoint Circle Algorithm

Step 1: Input the circle's radius and center coordinates.
Let the radius be $r$ and the center be $(x_c, y_c)$ .

Step 2: Initialize starting point.
Set:

x = 0, y = r

Step 3: Calculate the initial decision parameter.

P = 1 - r

Step 4: Plot the first point.
Plot the points for all 8 symmetric parts:

(x_c + x, y_c + y), \quad (x_c - x, y_c + y), \quad (x_c + x, y_c - y), \quad (x_c - x, y_c - y)

(x_{c} + y, y_{c} + x), (x_{c} - y, y_{c} + x), (x_{c} + y, y_{c} - x), (x_{c} - y, y_{c} - x)

Step 5: Repeat until $x < y$ .
For each step:

If $P < 0$ :
- $P = P + 2x + 3$ .
If $P \geq 0$ :
- $P = P + 2x - 2y + 5$ .
- Decrease $y = y - 1$ .
Increment $x = x + 1$ .
Plot the new symmetric points.

Step 6: Stop when $x \geq y$ .

Algorithm in Short Form

Input radius $r$ and center $(x_c, y_c)$ .
Initialize: $x = 0, \, y = r, \, P = 1 - r$
Plot the initial 8 symmetric points.
While $x < y$ :
- If $P < 0$ : $P = P + 2x + 3$
- If $P \geq 0$ : $P = P + 2x - 2y + 5, \quad y = y - 1$
- Increment $x = x + 1$ .
- Plot the new 8 symmetric points.
End.

Key Points for Full Marks

Explain symmetry: The algorithm reduces computations by plotting 8 points at once.
Draw a diagram of a circle with symmetric points labeled.
Write the steps clearly and include a table of calculations (optional).
Mention that this algorithm avoids floating-point arithmetic, making it efficient.

4. Flood Fill Algorithm

Flood fill is used to fill connected regions of a 2D screen with a given color.

   Steps for the Algorithm
Input:
Starting pixel coordinates (x,y)(x, y).
The color to fill, newColor.
The color of the region to be replaced, oldColor.

Check the base condition:

If the pixel at (x,y)(x, y) is not the oldColor or it is already newColor, return.

Replace the color:

Change the color of the pixel at (x,y)(x, y) to newColor.

Recursive filling:

Call the algorithm recursively for all 4-connected pixels:
Left: (x−1,y)(x-1, y)
Right: (x+1,y)(x+1, y)
Top: (x,y−1)(x, y-1)
Bottom: (x,y+1)

Repeat until all connected pixels are filled.

  

Algorithm in Short Form

Input $(x, y)$ , oldColor, and newColor.
If the pixel at $(x, y)$ is not oldColor or is already newColor, return.
Replace the color of the pixel at $(x, y)$ with newColor.
Recursively call the algorithm for:
- $(x-1, y)$
- $(x+1, y)$
- $(x, y-1)$
- $(x, y+1)$
End when no more connected pixels of oldColor remain.

Pseudo Code

FloodFill(x, y, oldColor, newColor):
    if Screen[x][y] ≠ oldColor OR Screen[x][y] = newColor:
        return

    Screen[x][y] = newColor

    FloodFill(x-1, y, oldColor, newColor)  // Left
    FloodFill(x+1, y, oldColor, newColor)  // Right
    FloodFill(x, y-1, oldColor, newColor)  // Top
    FloodFill(x, y+1, oldColor, newColor)  // Bottom

Key Points for Full Marks

Mention that Flood Fill works for 4-connected pixels or 8-connected pixels (if extended).
Add a small diagram showing an example of how the algorithm fills the region.
Clearly explain the recursive nature of the algorithm.
Optionally, mention that iterative implementations can avoid stack overflow for large regions.

5. Boundary Fill Algorithm

Boundary Fill is used to fill a closed region with a specified color, stopping at a defined boundary.

Steps for the Algorithm
Input:
Starting pixel coordinates (x,y)(x, y).
Fill color (fillColor).
Boundary color (boundaryColor).

Check the base condition:

If the pixel at (x,y)(x, y) is already boundaryColor or fillColor, return.

Replace the color:

Change the color of the pixel at (x,y)(x, y) to fillColor.

Recursive filling:

Call the algorithm recursively for all 4-connected or 8-connected neighbors:
For 4-connected:
Left: (x−1,y)(x-1, y)
Right: (x+1,y)(x+1, y)
Top: (x,y−1)(x, y-1)
Bottom: (x,y+1)(x, y+1)

For 8-connected, include diagonals:
Top-left: (x−1,y−1)(x-1, y-1)
Top-right: (x+1,y−1)(x+1, y-1)
Bottom-left: (x−1,y+1)(x-1, y+1)
Bottom-right: (x+1,y+1)

Repeat until all pixels are filled.
  

Algorithm in Short Form

Input $(x, y)$ , fillColor, and boundaryColor.
If the pixel at $(x, y)$ is boundaryColor or fillColor, return.
Replace the pixel at $(x, y)$ with fillColor.
Recursively call the algorithm for neighbors (4-connected or 8-connected):
- $(x-1, y)$ , $(x+1, y)$ , $(x, y-1)$ , $(x, y+1)$ (for 4-connected).
- Add diagonal neighbors for 8-connected.
End when all reachable pixels within the boundary are filled.

Pseudo Code

BoundaryFill(x, y, fillColor, boundaryColor):
    if Screen[x][y] = boundaryColor OR Screen[x][y] = fillColor:
        return

    Screen[x][y] = fillColor

    // 4-connected neighbors
    BoundaryFill(x-1, y, fillColor, boundaryColor)  // Left
    BoundaryFill(x+1, y, fillColor, boundaryColor)  // Right
    BoundaryFill(x, y-1, fillColor, boundaryColor)  // Top
    BoundaryFill(x, y+1, fillColor, boundaryColor)  // Bottom

    // Uncomment below for 8-connected neighbors
    // BoundaryFill(x-1, y-1, fillColor, boundaryColor)  // Top-left
    // BoundaryFill(x+1, y-1, fillColor, boundaryColor)  // Top-right
    // BoundaryFill(x-1, y+1, fillColor, boundaryColor)  // Bottom-left
    // BoundaryFill(x+1, y+1, fillColor, boundaryColor)  // Bottom-right

Key Points for Full Marks

Explain that Boundary Fill stops when it encounters the boundaryColor.
Mention 4-connected vs. 8-connected filling, depending on requirements.
Draw a small diagram illustrating a region with a boundary and how it is filled step-by-step.
Note that this algorithm is recursive and may face stack overflow for large areas. Iterative solutions can be used in such cases.

6. Cohen-Sutherland Line Clipping Algorithm

This algorithm clips a line segment to a rectangular clipping window using region codes.

Steps of the Algorithm

Step 1: Define the rectangular clipping window.

Let the boundaries of the window be:

Left: $x_{\text{min}}$
Right: $x_{\text{max}}$
Bottom: $y_{\text{min}}$
Top: $y_{\text{max}}$

Step 2: Assign region codes.

Each endpoint of the line segment is assigned a 4-bit region code:

\text{Code} = \text{(Top, Bottom, Right, Left)}

Bit positions:
- Top: $1$ if $y > y_{\text{max}}$ , otherwise $0$ .
- Bottom: $1$ if $y < y_{\text{min}}$ , otherwise $0$ .
- Right: $1$ if $x > x_{\text{max}}$ , otherwise $0$ .
- Left: $1$ if $x < x_{\text{min}}$ , otherwise $0$ .

Step 3: Perform the following tests:

Trivial Acceptance:
If both endpoints have a region code of 0000, the line is completely inside the clipping window. Accept the line.
Trivial Rejection:
If the logical AND of the region codes for both endpoints is not 0000 (non-zero), the line is completely outside the clipping window. Reject the line.
Partial Clipping:
If the line cannot be trivially accepted or rejected, proceed with clipping:
- Select an endpoint outside the window.
- Find the intersection point of the line with one of the window boundaries based on the region code:
  - Top boundary: $y = y_{\text{max}}, x = x_1 + (x_2 - x_1) \times \frac{(y_{\text{max}} - y_1)}{(y_2 - y_1)}$
  - Bottom boundary: $y = y_{\text{min}}, x = x_1 + (x_2 - x_1) \times \frac{(y_{\text{min}} - y_1)}{(y_2 - y_1)}$
  - Right boundary: $x = x_{\text{max}}, y = y_1 + (y_2 - y_1) \times \frac{(x_{\text{max}} - x_1)}{(x_2 - x_1)}$
  - Left boundary: $x = x_{\text{min}}, y = y_1 + (y_2 - y_1) \times \frac{(x_{\text{min}} - x_1)}{(x_2 - x_1)}$
- Replace the endpoint outside the window with the calculated intersection point.
- Recalculate the region codes and repeat the tests.

Repeat until all pixels are filled.

Algorithm in Short Form

Input the clipping window $(x_{\text{min}}, y_{\text{min}}, x_{\text{max}}, y_{\text{max}})$ and the line endpoints $(x_1, y_1)$ , $(x_2, y_2)$ .
Compute the region codes for both endpoints.
If both region codes are 0000, accept the line.
If the logical AND of the region codes is non-zero, reject the line.
Otherwise:
- Select an endpoint outside the window.
- Compute the intersection with the appropriate window boundary.
- Update the endpoint and repeat.
Stop when the line is fully accepted or rejected.

Pseudo Code

CohenSutherlandClip(x1, y1, x2, y2):
    Compute region codes for (x1, y1) and (x2, y2)

    while True:
        if both codes are 0000:
            Accept the line and stop
        elif logical AND of both codes ≠ 0000:
            Reject the line and stop
        else:
            Choose an endpoint outside the window
            Find intersection with window boundary
            Replace the endpoint with the intersection point
            Recompute region code

Key Points for Full Marks

Explain the use of region codes (e.g., binary representation for each side).
Draw a small diagram of the clipping window with region codes labeled.
Clearly describe the intersection calculations for each boundary.
Highlight the efficiency of trivial acceptance/rejection.

7. Sutherland-Hodgman Polygon Clipping Algorithm

The algorithm clips a polygon against a rectangular clipping window. It processes the polygon's vertices edge by edge and creates a new clipped polygon.

Steps of the Algorithm

Step 1: Define the clipping window

The clipping window is defined by its boundaries:

Left: $x_{\text{min}}$
Right: $x_{\text{max}}$
Bottom: $y_{\text{min}}$
Top: $y_{max}$

Step 2: Start with the original polygon

List all vertices of the polygon as a sequence.

Step 3: Clip the polygon edge by edge

For each edge of the clipping window (left, right, bottom, top):

Take each vertex pair (current vertex and the next vertex) of the polygon.
Apply the following rules:
- Case 1: Both vertices are inside the clipping boundary
  - Add the second vertex to the output list.
- Case 2: First vertex is inside, second vertex is outside
  - Add the intersection point with the boundary to the output list.
- Case 3: First vertex is outside, second vertex is inside
  - Add the intersection point with the boundary, followed by the second vertex, to the output list.
- Case 4: Both vertices are outside the boundary
  - Do not add anything to the output list.
Repeat for all edges of the clipping window.

Step 4: Repeat until all boundaries are processed

After processing all edges of the clipping window, the remaining vertices form the clipped polygon.

Algorithm in Short Form

Input the clipping window boundaries $(x_{\text{min}}, x_{\text{max}}, y_{\text{min}}, y_{\text{max}})$ and the polygon vertices.
For each edge of the clipping window:
- For each vertex pair of the polygon:
  - Apply the four cases based on the positions of the vertices relative to the clipping edge.
  - Generate the new list of vertices for the clipped polygon.
After all edges are processed, the final list of vertices forms the clipped polygon.

Pseudo Code

SutherlandHodgmanClip(polygon, clipEdge):
    outputList = []
    for each vertex pair (currentVertex, nextVertex) in polygon:
        if currentVertex is inside AND nextVertex is inside:
            Add nextVertex to outputList
        elif currentVertex is inside AND nextVertex is outside:
            Add intersection point to outputList
        elif currentVertex is outside AND nextVertex is inside:
            Add intersection point and nextVertex to outputList
        else:
            Do nothing
    return outputList

Repeat this process for each boundary (Left, Right, Bottom, Top).

Key Points for Full Marks

Clipping Boundaries: Describe how each polygon vertex is tested against the boundaries.
Intersection Calculation:
- For vertical boundary (e.g., left or right): $y = y_1 + (y_2 - y_1) \times \frac{(x_{\text{boundary}} - x_1)}{(x_2 - x_1)}$
- For horizontal boundary (e.g., top or bottom): $x = x_1 + (x_2 - x_1) \times \frac{(y_{\text{boundary}} - y_1)}{(y_2 - y_1)}$
Draw a diagram showing a polygon being clipped step by step against a window.
Mention that this algorithm preserves the shape of the polygon as much as possible.
Highlight its use in computer graphics for viewport clipping.

With this guide and Campusify’s resources, you can confidently approach your CGR exam and achieve excellent results. Don’t forget to join our Telegram Channel for Latest Updates.

Happy studying, and good luck!

Campusify – Your Ultimate Study Resource for MSBTE Diploma And Engineering Students!

It's Free! Join Now

Keywords:

Campusify! Is a place where Students can find their Books, Notes, Projects, Total Study Material and many more!

CGR All IMP Algorithms Easy to Learn | Computer Graphics IMP Algorithms | Mumbai University

1. DDA Line Drawing Algorithm

Algorithm in Short Form

Key Points for Full Marks

2. Bresenham Line Drawing Algorithm

Algorithm in Short Form

Key Points for Full Marks

3. Midpoint Circle Algorithm

Algorithm in Short Form

Key Points for Full Marks

4. Flood Fill Algorithm

Steps for the Algorithm

Algorithm in Short Form

Pseudo Code

Key Points for Full Marks

5. Boundary Fill Algorithm

Steps for the Algorithm

Algorithm in Short Form

Pseudo Code

Key Points for Full Marks

6. Cohen-Sutherland Line Clipping Algorithm

Steps of the Algorithm

Step 1: Define the rectangular clipping window.

Step 2: Assign region codes.

Step 3: Perform the following tests:

Algorithm in Short Form

Pseudo Code

Key Points for Full Marks

7. Sutherland-Hodgman Polygon Clipping Algorithm

Steps of the Algorithm

Step 1: Define the clipping window

Step 2: Start with the original polygon

Step 3: Clip the polygon edge by edge

Step 4: Repeat until all boundaries are processed

Algorithm in Short Form

Pseudo Code

Key Points for Full Marks

Join the conversation