Computer Graphics: Clipping, 3D Modeling, and Projections

Cohen-Sutherland Line Clipping Algorithm

As covered briefly in our previous discussion, the Cohen-Sutherland algorithm is a highly efficient line-clipping method that uses a 4-bit binary region code (Outcode) to categorize where the endpoints of a line lie relative to a rectangular window.

The 9-Region Outcode Breakdown

The clipping window boundaries (x_min, x_max, y_min, y_max) divide the 2D world space into 9 distinct regions. Each region is assigned a 4-bit code [Bit 1, Bit 2, Bit 3, Bit 4] defined by coordinate comparisons:

• Bit 1 (Top): Set to 1 if y > y_max
• Bit 2 (Bottom): Set to 1 if y < y_min
• Bit 3 (Right): Set to 1 if x > x_max
• Bit 4 (Left): Set to 1 if x < x_min

Mathematical Intersection Formulas

When a line cannot be trivially accepted or rejected, it intersects a boundary line. We use the slope-intercept formula to calculate the exact intersection coordinates. The slope is m = (y₂ - y₁) / (x₂ - x₁).

• Intersection with a Vertical Boundary (x_min or x_max):
  x_intersection = x_boundary
  y_intersection = y₁ + m(x_boundary - x₁)
• Intersection with a Horizontal Boundary (y_min or y_max):
  y_intersection = y_boundary
  x_intersection = x₁ + (1/m)(y_boundary - y₁)

Midpoint Subdivision Line Clipping Method

The Midpoint Subdivision Algorithm is an alternative to Cohen-Sutherland. It is specifically optimized for hardware systems where calculating the line slope (m) or executing floating-point divisions is computationally expensive. Instead of computing algebraic intersections, it uses a binary search strategy to locate where a line crosses a window boundary.

How the Midpoint Algorithm Works

1. Assign standard 4-bit Cohen-Sutherland region codes to both endpoints of the line, P₁ and P₂.
2. Check for Trivial Accept (both codes 0000) or Trivial Reject (Bitwise AND ≠ 0).
3. If the line is indeterminate (crosses a boundary), find the midpoint P_m of the segment:
   
   (In hardware, division by 2 is handled instantly via a simple bitwise right-shift operation).
4. The line segment is now split into two halves: P₁P_m and P_mP₂.
5. Apply the Trivial Accept/Reject tests to both halves:
   • Discard any half-segment that is trivially rejected.
   • Keep subdividing any half-segment that contains a boundary intersection.
6. Repeat this subdivision until the segment length reduces to a fraction matching the system's pixel resolution limit. The final remaining point marks the boundary intersection point.

Text Clipping Techniques

In computer graphics, Text Clipping determines how character strings are handled when they overlap a window boundary. Text is computationally heavier to clip than simple lines or polygons because characters are complex collections of lines, curves, or dense pixel arrays (fonts). Depending on your system's hardware performance constraints and rendering quality requirements, text clipping can be implemented at three distinct levels of precision:

All-or-None String-Level Clipping

• The Logic: The entire text string is treated as a single, large primitive enclosed within a rectangular bounding box.
• The Process: The system tests the bounding box against the clipping window.
  • If the entire box fits completely inside the window, the whole string is rendered.
  • If even a single pixel of the bounding box touches or crosses a boundary line, the entire string is discarded.
• Pros: Extremely fast and requires virtually no computational overhead.
• Cons: Very low precision; words disappear entirely even if 95% of the text is safely inside the viewing area.

All-or-None Character-Level Clipping

• The Logic: The text string is broken down into its individual characters, and each character is treated as an independent primitive with its own mini bounding box.
• The Process: The algorithm loops through each character's bounding box against the window frame.
  • Characters completely inside are kept.
  • Characters that overlap or fall outside the boundary line are rejected completely.
• Pros: Considerably better visual accuracy than string-level clipping; text strings are cleanly truncated right around the window edge.
• Cons: Characters on the immediate boundary are completely dropped rather than cut in half, leaving empty spaces at the edges of the display window.

Bitmapped and Pixel-Level Clipping

• The Logic: This method operates at the finest level of detail by analyzing text at the pixel level.
• The Process: Characters are converted into their raster representation (bitmaps or font outline paths). The graphics processor then applies standard point-clipping checks to every individual pixel coordinate forming the letter. Only the individual pixels that satisfy these inequalities are written to the frame buffer.
• Pros: Flawless visual accuracy. Characters are sharply and accurately sliced right down the middle at the pixel boundary, matching how modern operating systems and web browsers render text.
• Cons: The slowest and most computationally expensive method, as it requires processing every single pixel vector component of a font layout.

3D Object Representations

In computer graphics, representing a three-dimensional object requires translating physical geometry into data structures that a computer can store, transform, and render.

Polygon Surfaces and Boundary Representations

This is the most common method for representing 3D objects in real-time graphics (such as video games and CAD software). The object is simplified into a shell of flat, planar polygons—typically triangles or quadrilaterals.

• Data Structure: To avoid duplicate calculations, objects are stored using three connected tables:
  1. Vertex Table: Stores the exact spatial coordinates (X, Y, Z) of every corner.
  2. Edge Table: Lists which vertices connect to form lines.
  3. Polygon-Surface Table: Lists which edges or vertices bind together to form a closed face.

Quadratic and Quadric Surfaces

These are objects defined implicitly by second-degree algebraic equations. They provide mathematically perfect curvature without relying on thousands of tiny flat polygons.

• Examples: Spheres, ellipsoids, cylinders, and paraboloids.
• Equation of a Sphere at origin: X² + Y² + Z² = R²

Spline Representations

A spline is a smooth, continuous curve or surface constructed from a series of polynomial segments. The shape is guided by a set of control points. Instead of storing a complex mesh, the system stores a few control coordinates and calculates the smooth surface on the fly.

• Examples: Bézier Surfaces and NURBS (Non-Uniform Rational B-Splines), which are universally used in industrial manufacturing, CAD, and 3D modeling programs like Blender or Maya.

Solid Modeling: CSG and Voxels

• Constructive Solid Geometry (CSG): Builds complex 3D objects by combining simple primitives (cubes, spheres, cylinders) using Boolean operations like Union (fusing together), Intersection (keeping only where they overlap), and Difference (cutting one shape out of another).
• Voxel (Volume Pixel): The 3D equivalent of a 2D pixel. An object is represented as a giant 3D grid of tiny cubes. This is widely used in medical imaging (CT/MRI scans) and games like Minecraft.

3D Transformations

To manipulate objects in 3D space, we expand our 2D homogeneous coordinate system. A 3D point (X, Y, Z) is represented as a 4-element column vector where the fourth element h=1. This allows us to use 4 x 4 matrices to calculate positions.

Translation, Scaling, and Rotation

1. Translation: Moves an object from its current position to a new spatial location by adding displacement offsets t_x, t_y, and t_z:

2. Scaling: Alters the size of an object relative to the origin (0,0,0) using scale factors s_x, s_y, and s_z:

3. Rotation: 3D rotation is more complex than 2D because you must specify a rotational axis. Standard rotations occur around the principal coordinate axes, assuming a right-handed system looking down the positive axis toward the origin (counterclockwise):

• Rotation around the X-axis: Leaves X coordinates unchanged.
• Rotation around the Y-axis: Leaves Y coordinates unchanged.
• Rotation around the Z-axis: Leaves Z coordinates unchanged (identical to standard 2D rotation).

Projections in Computer Graphics

Because computer monitors are flat 2D surfaces, a 3D scene must be mathematically squashed into a 2D image plane. This mapping process is called Projection. Projections are divided into two primary categories:

Parallel and Perspective Projections

1. Parallel Projection: In parallel projection, coordinate positions are transformed to the view plane along parallel lines. The distance from the camera to the object does not affect its size on screen.

• Orthographic Projection: The projection lines are exactly perpendicular (at 90°) to the projection plane. This is widely used in engineering and architecture blueprints because it preserves exact relative dimensions.
• Oblique Projection: The parallel projection lines strike the projection view plane at an angle other than 90°. This keeps the front face clear while showing a stylized, offset view of the top and sides.

2. Perspective Projection: Perspective projection produces realistic images by converging projection lines to a single point in space called the Center of Projection (which mimics the human eye or a camera lens).

• The Foreshortening Effect: Objects that are farther away from the viewing plane appear smaller on screen than objects of the same size that are closer.
• Vanishing Points: Parallel lines that do not cross in 3D space appear to converge toward a single point on the horizon line. Perspective systems are categorized as 1-Point, 2-Point, or 3-Point perspective depending on how many coordinate axes intersect the projection plane.