Introduction

Rasterization is the process of converting geometric shapes into a pixel-based format suitable for display on screens. While axis-aligned rectangles are common and straightforward to rasterize, rotated rectangles present additional challenges. The rotated rectangle rasterization algorithm addresses these challenges, enabling efficient and accurate rendering of rectangles that are not aligned with the coordinate axes.

Overview of the Algorithm

The rotated rectangle rasterization algorithm ensures that every pixel inside the rotated rectangle is accurately captured. This involves:

1. Determining Corner Coordinates: Identify the four corners of the rectangle.
2. Line Equation Calculation: Define the lines between each pair of adjacent corners.
3. Bounding Box Calculation: Compute the axis-aligned bounding box (AABB) for the rotated rectangle.
4. Scan Line Approach: Iterate over each scan line within the AABB and determine which pixels intersect with the rotated rectangle.
5. Pixel Filling: Fill the pixels that lie within the boundaries defined by the intersection points on each scan line.

Step 1: Determining Corner Coordinates

Given a rectangle defined by its center, width, height, and rotation angle, calculate the vertices of the rectangle as follows:

1. Calculate half of the diagonal length and the angle offset due to rotation.
2. Use the center, width, height, and rotation angle to compute each corner's position using rotation matrices.

Step 2: Line Equation Calculation

For each side of the rectangle, derive the line equation in the form:

$ax + by + c = 0$

Where `(a, b)` is the normal vector of the line and `c` is a constant. This equation helps in determining whether a pixel lies inside the rectangle.

Step 3: Bounding Box Calculation

Compute the axis-aligned bounding box by taking the minimum and maximum `x` and `y` coordinates among the rotated rectangle's vertices.

Step 4: Scan Line Approach

Within the bounding box:

• Iterate over each integer `y` value (representing scan lines).
• Compute intersection points of the rectangle edges with the current scan line.
• Sort the intersection points on the x-axis.

Step 5: Pixel Filling

For each scan line, iterate between pairs of intersection points and fill the pixels between them. Ensure each pixel's center falls within the defined boundary for accurate rasterization.

Technical Example

Let's implement a simple version of the algorithm in pseudo-code to illustrate the main steps.

• `computeVertices()` calculates the rectangle's corners.
• `computeEdges()` determines the equations of lines for the rectangle's edges.
• `computeAABB()` computes the axis-aligned bounding box.
• `computeIntersection()` finds where the scan line intersects with rectangle edges.
• `fillPixels()` marks pixels between the intersection pairs on the scan line.
• Antialiasing: To improve visual quality, implement an antialiasing technique such as supersampling or multisampling.
• Precision Loss: Be cautious of precision issues, especially for small or nearly vertical/horizontal rectangles.
• Edge Cases: Handle degenerate rectangles or very thin rectangles carefully to avoid missing pixels.