Bresenham's Line Drawing Algorithm

Part 1: Derivation

Concept

Bresenham's algorithm draws a line using only integer arithmetic (addition, subtraction, and multiplication by 2). It selects, at each step, the pixel nearest to the true line path.

Derivation (for slope $0 < m < 1$)

Assume we have plotted pixel $(x_k, y_k)$. The next pixel is either:

• E: $(x_k+1, y_k)$
• NE: $(x_k+1, y_k+1)$

True line at $x = x_k+1$: $$y = m(x_k+1) + b, \qquad m = \frac{\Delta y}{\Delta x}$$

Distances from true line to the two candidates: $$d_1 = y - y_k = m(x_k+1) + b - y_k$$ $$d_2 = (y_k+1) - y = y_k + 1 - m(x_k+1) - b$$

$$d_1 - d_2 = 2m(x_k+1) + 2b - 2y_k - 1$$

Define decision parameter $p_k = \Delta x (d_1 - d_2)$ (multiply by $\Delta x > 0$ to remove the fraction):

$$p_k = 2\Delta y \cdot x_k - 2\Delta x \cdot y_k + c, \quad c = 2\Delta y + \Delta x(2b-1)$$

Rule:

• If $p_k < 0$: choose E, plot $(x_k+1, y_k)$
• If $p_k \ge 0$: choose NE, plot $(x_k+1, y_k+1)$

Recurrence

$$p_{k+1} - p_k = 2\Delta y (x_{k+1}-x_k) - 2\Delta x (y_{k+1}-y_k)$$

Since $x_{k+1} = x_k + 1$:

Initial value: $$\boxed{p_0 = 2\Delta y - \Delta x}$$

Part 2: Tracing (6, 12) to (10, 5)

Parameters

$$x_1=6,\ y_1=12,\ x_2=10,\ y_2=5$$ $$\Delta x = |10-6| = 4, \qquad \Delta y = |5-12| = 7$$

Slope magnitude $= \frac{7}{4} = 1.75 > 1$ → steep line, so we step along the y-axis.

Since $x$ increases ($6 \to 10$) and $y$ decreases ($12 \to 5$), we step -1 in y each step and possibly +1 in x.

Adjusted rules (driving variable = y, $\Delta y = 7$ steps)

$$p_0 = 2\Delta x - \Delta y = 2(4) - 7 = 1$$

• $2\Delta x = 8$
• $2\Delta x - 2\Delta y = 8 - 14 = -6$

Rules (step $y \to y-1$ each iteration):

• If $p_k < 0$: $x$ stays, $p_{k+1} = p_k + 8$
• If $p_k \ge 0$: $x \to x+1$, $p_{k+1} = p_k - 6$

Trace Table

Start plotted: $(6, 12)$, $p_0 = 1$

Points Plotted

$$(6,12),\ (7,11),\ (7,10),\ (8,9),\ (8,8),\ (9,7),\ (9,6),\ (10,5)$$

The endpoint $(10, 5)$ is reached correctly after 7 steps.

Sutherland-Hodgman Polygon Clipping: Major Drawback + B-Spline Curves

Part 1: Major Drawback of Sutherland-Hodgman Algorithm

The Algorithm (Brief Recap)

The Sutherland-Hodgman algorithm clips a polygon against each edge of the rectangular clipping window one at a time. It processes the polygon vertex list against:

1. Left boundary
2. Right boundary
3. Bottom boundary
4. Top boundary

The four inside-outside cases for each edge are:

• Out → In: Add intersection point V' and Vi+1
• In → In: Add Vi+1
• In → Out: Add intersection point V' only
• Out → Out: Add nothing

Major Drawback: Incorrect Clipping of Concave (Non-Convex) Polygons

The Sutherland-Hodgman algorithm works correctly only for convex polygons. When applied to concave (non-convex) polygons, it produces incorrect results by generating spurious (extra, unwanted) edges that do not belong to the actual clipped polygon.

When a concave polygon is clipped, the algorithm may connect vertices that should not be connected, producing a polygon with extra edges crossing through the exterior region. The output polygon may appear distorted or have additional triangular/spurious regions.

Illustration with Example

Consider a concave (non-convex) polygon with vertices:

V1(10, 40), V2(40, 80), V3(70, 40), V4(40, 60)

This polygon is concave (the vertex V4 is indented inward, creating a "dent").

Clipping Window: Xmin=20, Ymin=30, Xmax=60, Ymax=70

        V2(40,80)
       /         \
V1(10,40)       V3(70,40)
       \         /
        V4(40,60)   <-- concave indentation

What should happen (correct result): The clipping should produce two separate polygon regions (two disjoint pieces) after clipping against the window boundaries, because the concave polygon, when clipped, naturally splits into two parts.

What Sutherland-Hodgman produces (incorrect result): Instead of two separate polygons, the algorithm connects the two separate pieces with a spurious edge along the clipping boundary, producing one single (incorrect) polygon with an extra edge that runs along the window boundary where no actual polygon edge exists.

Correct Output:          S-H Output (Incorrect):
  [Piece 1]  [Piece 2]     [Single polygon with
                            spurious connecting edge]

Diagram:

  ___________
 |    /\     |
 |   /  \    |   <-- Correct: two separate triangular regions
 |  /    \   |
 |_/______\__|

  ___________
 |    /\     |
 |   /  \    |   <-- S-H Output: spurious edge connects
 |  /____\   |       the two regions incorrectly
 |___________|

The spurious edge appears along the clipping boundary, connecting two intersection points that should not be connected. This creates a filled region that does not actually belong to the original polygon.

Summary of Drawback

Part 2: B-Spline Curve and Its Properties

Definition

A B-spline curve (Basis spline curve) is a piecewise polynomial curve defined by a set of control points (polygon vertices) and a set of basis functions called B-spline basis functions. Unlike Bezier curves, B-spline curves provide local control over the shape of the curve.

The general equation of a B-spline curve is:

$$P(t) = \sum_{i=0}^{n} P_i \cdot N_{i,k}(t)$$

Where:

• $P_i$ = control points (i = 0, 1, 2, ..., n)
• $N_{i,k}(t)$ = B-spline basis functions of order k
• $k$ = order of the curve (degree = k - 1)
• $t$ = parameter value

B-Spline Basis Functions (Cox-de Boor Recursion)

The basis functions are defined recursively:

Order 1 (k=1): $$N_{i,1}(t) = \begin{cases} 1 & \text{if } t_i \leq t < t_{i+1} \ 0 & \text{otherwise} \end{cases}$$

Higher orders: $$N_{i,k}(t) = \frac{t - t_i}{t_{i+k-1} - t_i} N_{i,k-1}(t) + \frac{t_{i+k} - t}{t_{i+k} - t_{i+1}} N_{i+1,k-1}(t)$$

Where $t_i$ are the knot values forming the knot vector.

Example from Notes

Construct a B-spline curve of order 4 with 4 polygon vertices:

• A(1,1), B(2,3), C(4,3), D(6,2)

Given: n = 3 (4 control points: P0, P1, P2, P3), k = 4 (order 4)

Knot vector for uniform B-spline with n=3, k=4: Number of knots = n + k + 1 = 3 + 4 + 1 = 8

Uniform knot vector: T = {0, 0, 0, 0, 1, 1, 1, 1}

The knot value 0 is repeated k = 4 times at the start and 1 is repeated k = 4 times at the end (a clamped/open uniform knot vector). Since n - k + 2 = 3 - 4 + 2 = 1, there are no interior knot spans, so the curve reduces to a single Bezier-like segment defined over t ∈ [0, 1] that passes through the first and last control points, A(1,1) and D(6,2).

Properties of B-Spline Curves

• Local Control: Moving one control point $P_i$ only affects the portion of the curve where its basis function $N_{i,k}(t)$ is non-zero, unlike a Bezier curve where every control point influences the entire curve.
• Degree Independent of Control Points: The degree of a B-spline curve (k - 1) can be chosen independently of the number of control points, whereas a Bezier curve's degree is always (n) for n+1 control points.
• Convex Hull Property: The curve lies within the union of the convex hulls of each successive group of k control points.
• Continuity: A B-spline curve is $C^{k-2}$ continuous at simple (non-repeated) interior knots, allowing smoother joins between segments.
• Variation Diminishing Property: The curve does not oscillate more than its defining control polygon.

Answer: RGB Color Model, VR vs AR, and BSP Trees

1. RGB Color Model

The RGB (Red, Green, Blue) color model is an additive color model used in computer graphics and display systems. It is based on the principle that a wide range of colors can be produced by combining three primary colors of light: Red, Green, and Blue.

Key Principles

• Additive Color Mixing: Colors are created by adding light. When all three primaries are combined at full intensity, white is produced. When all are absent, black is produced.
• Each color component has an intensity value typically ranging from 0 to 255 (in 8-bit representation) or 0.0 to 1.0 (normalized).
• The model is directly tied to how CRT monitors, LCD screens, and projectors emit light using red, green, and blue phosphors or sub-pixels.

Color Representation

A color is represented as a triplet: (R, G, B)

Advantages

• Directly maps to hardware display technology (raster scan monitors).
• Produces a much wider range of colors than older methods like the beam penetration method.
• Produces realistic images.

Disadvantages

• It is device-dependent (colors may vary across different monitors).
• Poor resolution in some hardware implementations (as noted in shadow mask systems).
• Difficult to align all three color beams precisely on the same hole in shadow mask CRTs.

Diagram

        Green (0,255,0)
           /    \
          /      \
  Cyan --+--Yellow
         |
  Blue --+-- Red
(0,0,255)    (255,0,0)
         \      /
          \    /
          Magenta
              |
           White (center)
           Black (origin)

2. Virtual Reality (VR) vs. Augmented Reality (AR)

Definitions

Virtual Reality (VR): Virtual Reality creates an entirely virtual world that replaces the real world. The user is fully immersed in a computer-generated environment. It is generally achieved by wearing a helmet or goggles having VR technology.

Augmented Reality (AR): Augmented Reality is the result of using technology to superimpose information such as sound, images, and text on the world we see. AR is a mix of the real world and the virtual world. It expands our physical world by adding layers of digital information on it. This is typically achieved by holding a smartphone in front of us.

Types of Augmented Reality

There are four types of AR today:

1. Markerless AR
2. Marker-based AR
3. Projection-based AR
4. Superimposition-based AR

Comparison Table

Examples

• VR Example: A user wearing an Oculus Rift headset is placed inside a fully simulated 3D game environment where everything they see is computer-generated. Medical students can practice surgery in a fully virtual operating room.

• AR Example: Pokemon GO is a popular AR game where virtual Pokemon characters are superimposed on the real-world camera view of a smartphone. Similarly, IKEA Place app lets users place virtual furniture in their real room using a phone camera.

3. Binary Space Partitioning (BSP) Trees

Definition

A Binary Space Partitioning (BSP) tree is a data structure used in computer graphics where a scene is recursively subdivided into two sections (FRONT and BACK) at each step using a plane that can be at any position and orientation.

From the notes: "It is a generic process of dividing a scene into two until the partitioning satisfies one or more requirements. It is a way of grouping data so it can be processed faster."

Key Characteristics

• The cutting planes can be positioned and oriented to suit the spatial distribution of objects, making BSP trees more efficient than octrees.
• BSP trees reduce the depth of the tree representation compared to octrees, thus reducing search time.
• They are useful for:
  • Identifying visible surfaces
  • Space partitioning in ray-tracing algorithms
• Many 3D modeling and rendering programs use BSP trees to make rendering faster.

Construction of a BSP Tree

The construction process (from the notes) is as follows:

1. A space containing a 3D scene is recursively divided into two parts: FRONT and BACK with respect to the viewport, by selecting any surface as a dividing plane.
2. The recursive subdivision is repeated until each half-space contains a manageable number of objects.
3. The subdivision process is represented as a binary tree with the initial partitioning plane as the root node.
4. The FRONT object is represented as the left node of the tree.
5. The BACK object is represented as the right node of the tree.
6. Each partitioning plane in a subspace becomes an internal node of the tree, and the recursion continues until every leaf holds a small, manageable set of surfaces.

Example

Consider a simple scene of three polygons A, B and C viewed from the position shown, where plane P1 is chosen along polygon A.

                 View position
                      |
        ----- P1 (plane of A) -----
         Front of P1      Back of P1
            B                 C

The construction proceeds as follows. Polygon A is selected as the first partitioning plane, so A becomes the root. Polygon B lies in the half space in front of P1, so it goes to the left subtree, and polygon C lies behind P1, so it goes to the right subtree. If a polygon straddles the plane, it is split along the plane and the two pieces are placed in the two subtrees.

            A  (root, plane P1)
           /   \
   front  B     C  back

To display the scene the tree is traversed back to front relative to the viewer, which for a viewer in front of P1 means the back subtree first, then the root polygon, then the front subtree, giving the drawing order C, A, B. Because nearer surfaces are painted after farther ones, hidden surfaces are removed correctly without any depth comparison per pixel, and the same tree gives a different but still correct order for any other viewing position.

Advantages and Limitations

4. Conclusion

The RGB model is an additive model based on the three primaries red, green and blue arranged along the axes of a unit cube, with black at the origin, white at the opposite corner and the greys along the main diagonal, and it is the model used by every emissive display. Virtual reality and augmented reality differ in how much of the real world survives: VR replaces it with a wholly synthetic environment seen through a headset, whereas AR keeps the real scene and overlays digital content on it, as Pokemon GO and IKEA Place do on a phone. BSP trees serve a different purpose again, organising the scene itself: by recursively splitting space into front and back half spaces about chosen planes, they store a scene in a form that yields a correct back to front drawing order for any viewpoint, which is why they underlie visible surface determination and ray tracing acceleration.

Refresh Rate and Vector Scan Display

Refresh Rate

The refresh rate is the number of times a screen's displayed image is repainted or refreshed per second. It is expressed in Hertz (Hz).

For example, a refresh rate of 75 Hz means the image is refreshed 75 times per second.

The refresh rate for each display depends on the video card used.

In vector displays, the refresh rate depends on the number of lines to be displayed for any image. Vector displays are designed to draw all component lines 30 to 60 times per second.

Vector Scan Display (Random Scan Display)

Vector scan display is also known as random scan display or calligraphic display.

Working Principle

• In this technique, the electron beam is directed only to the parts of the screen where the picture is to be drawn, rather than scanning from left to right and top to bottom (as in raster scan).
• Picture definition is stored as a set of line-drawing commands in a memory area called the refresh display file.
• The system reads these commands and draws each line one by one, then repeats the cycle to refresh the image.
• It is designed to draw all component lines 30 to 60 times each second to maintain a flicker-free image.

Characteristics

Aliasing is the jagged appearance of primitives as displayed on a raster device. Vector displays have the advantage of absence of aliasing.

Diagram

        Electron Gun
             |
             v
     +-------+-------+
     |   Deflection   |
     |    System      |
     +-------+-------+
             |
             |  (Beam directed to specific points)
             v
  +-------------------------+
  |                         |
  |    *---------*          |  <-- Line drawn directly
  |    |         |          |
  |    *----*    *          |  <-- Only required parts lit
  |         |               |
  |         *               |
  |                         |
  +-------------------------+
         CRT Screen

  Refresh Display File:
  [ Draw Line (x1,y1)-(x2,y2) ]
  [ Draw Line (x2,y2)-(x3,y3) ]
  [ ... repeat 30-60 times/sec ]

Summary

Vector scan display produces images by drawing lines directly between specified endpoints using electron beam deflection. It stores drawing commands in a refresh display file and redraws the entire picture 30 to 60 times per second, producing high-quality, smooth line drawings without aliasing. The plotter is the best real-world example of this system.

Bezier Curve Construction

STEP 1 - Given Data

Control points (4 points → cubic Bezier, degree $n = 3$):

• $P_0 = A(1, 1)$
• $P_1 = B(2, 3)$
• $P_2 = C(4, 3)$
• $P_3 = D(6, 4)$

STEP 2 - Solve

Bezier / Bernstein Blending Functions

$$P(u) = \sum_{k=0}^{3} P_k , BEZ_{k,3}(u), \quad 0 \le u \le 1$$

$$BEZ_{k,3}(u) = \binom{3}{k} u^k (1-u)^{3-k}$$

Parametric Equations

$$x(u) = 1(1-u)^3 + 6u(1-u)^2 + 12u^2(1-u) + 6u^3$$ $$y(u) = 1(1-u)^3 + 9u(1-u)^2 + 9u^2(1-u) + 4u^3$$

Point Computations

u = 0: $x = 1,; y = 1$

u = 0.2: $(1-u)=0.8$ $$x = 0.512 + 6(0.2)(0.64) + 12(0.04)(0.8) + 6(0.008)$$ $$= 0.512 + 0.768 + 0.384 + 0.048 = 1.712$$ $$y = 0.512 + 9(0.2)(0.64) + 9(0.04)(0.8) + 4(0.008)$$ $$= 0.512 + 1.152 + 0.288 + 0.032 = 1.984$$

u = 0.4: $(1-u)=0.6$ $$x = 0.216 + 6(0.4)(0.36) + 12(0.16)(0.6) + 6(0.064)$$ $$= 0.216 + 0.864 + 1.152 + 0.384 = 2.616$$ $$y = 0.216 + 9(0.4)(0.36) + 9(0.16)(0.6) + 4(0.064)$$ $$= 0.216 + 1.296 + 0.864 + 0.256 = 2.632$$

u = 0.5: $(1-u)=0.5$ (midpoint, useful check) $$x = 0.125 + 6(0.5)(0.25) + 12(0.25)(0.5) + 6(0.125)$$ $$= 0.125 + 0.75 + 1.5 + 0.75 = 3.125$$ $$y = 0.125 + 9(0.5)(0.25) + 9(0.25)(0.5) + 4(0.125)$$ $$= 0.125 + 1.125 + 1.125 + 0.5 = 2.875$$

u = 0.6: $(1-u)=0.4$ $$x = 0.064 + 6(0.6)(0.16) + 12(0.36)(0.4) + 6(0.216)$$ $$= 0.064 + 0.576 + 1.728 + 1.296 = 3.664$$ $$y = 0.064 + 9(0.6)(0.16) + 9(0.36)(0.4) + 4(0.216)$$ $$= 0.064 + 0.864 + 1.296 + 0.864 = 3.088$$

u = 0.8: $(1-u)=0.2$ $$x = 0.008 + 6(0.8)(0.04) + 12(0.64)(0.2) + 6(0.512)$$ $$= 0.008 + 0.192 + 1.536 + 3.072 = 4.808$$ $$y = 0.008 + 9(0.8)(0.04) + 9(0.64)(0.2) + 4(0.512)$$ $$= 0.008 + 0.288 + 1.152 + 2.048 = 3.496$$

u = 1.0: $x = 6,; y = 4$

Summary Table

The curve starts at $A(1,1)$, ends at $D(6,4)$, and remains within the convex hull of the control polygon, tangent to $AB$ at the start and to $CD$ at the end.