Edge Equation

The edge equation (or half-plane test) determines which side of a line a point lies on. Given a directed line from point P₀ to P₁, the edge equation for any point P is:

E(P) = (P₁.x - P₀.x)(P.y - P₀.y) - (P₁.y - P₀.y)(P.x - P₀.x)

This is equivalent to the 2D cross product of vectors (P₁ - P₀) and (P - P₀).

The result tells us:

E > 0: Point is to the left of the line (positive half-plane)
E = 0: Point is on the line
E < 0: Point is to the right of the line (negative half-plane)

This is fundamental to rasterization - a point is inside a triangle if it's on the correct side of all three edges.

Interactive Demo

Drag the points to move the line. The grid shows the edge equation value at each cell - blue for positive (left side), orange for negative (right side). The arrow shows the line direction.

/graphics/edge_equation.js

SIMD Optimization

The edge equation is linear, which makes it perfect for SIMD (Single Instruction Multiple Data) optimization. If we expand the equation:

E(x, y) = A · x + B · y + C

Where:

A = P₁.y - P₀.y (the y-component of the edge direction)
B = -(P₁.x - P₀.x) (negated x-component)
C = (P₁.x - P₀.x) · P₀.y - (P₁.y - P₀.y) · P₀.x (constant offset)

Incremental Evaluation

Since the equation is linear, moving one pixel right just adds A:

E(x+1, y) = E(x, y) + A

And moving one pixel down adds B:

E(x, y+1) = E(x, y) + B

x86 SSE/AVX Implementation

With SSE/AVX, we can evaluate 4 or 8 pixels simultaneously:

// Evaluate 4 pixels at once (SSE)
__m128 edge_x4(__m128 x, __m128 y, float A, float B, float C) {
    __m128 vA = _mm_set1_ps(A);
    __m128 vB = _mm_set1_ps(B);
    __m128 vC = _mm_set1_ps(C);
    
    // E = A*x + B*y + C
    __m128 result = _mm_add_ps(
        _mm_add_ps(_mm_mul_ps(vA, x), _mm_mul_ps(vB, y)),
        vC
    );
    return result;
}

// Process a row of 4 pixels at a time
void rasterize_row(float* edges, int y, float A, float B, float C, int width) {
    __m128 vA = _mm_set1_ps(A);
    __m128 step = _mm_set_ps(3, 2, 1, 0);  // x offsets
    __m128 x = _mm_mul_ps(step, _mm_set1_ps(1.0f));
    
    // Initial E value for this row
    float E0 = B * y + C;
    __m128 E = _mm_add_ps(_mm_set1_ps(E0), _mm_mul_ps(vA, x));
    __m128 A4 = _mm_set1_ps(A * 4);  // step by 4 pixels
    
    for (int i = 0; i < width; i += 4) {
        _mm_store_ps(&edges[i], E);
        E = _mm_add_ps(E, A4);  // increment by 4*A
    }
}

RISC-V Vector (RVV) Implementation

RISC-V's vector extension provides scalable SIMD with variable vector lengths:

riscv

# Edge equation: E = A*x + B*y + C
# Inputs: a0=edges ptr, a1=width, fa0=A, fa1=B, fa2=C, fa3=y, fa4=A*VLEN
# Process VLEN pixels per iteration (hardware-determined)

edge_row_rvv:
    # Compute initial E0 = B*y + C
    fmadd.s     fa5, fa1, fa3, fa2      # fa5 = B*y + C
    
    # Create x coordinate vector [0, 1, 2, 3, ...]
    vsetvli     t0, a1, e32, m1         # set vector length, 32-bit floats
    vid.v       v0                       # v0 = [0, 1, 2, ..., VLEN-1]
    vfcvt.f.x.v v0, v0                  # convert to float
    
    # Initial E = E0 + A*x
    vfmv.v.f    v1, fa5                 # v1 = broadcast E0
    vfmacc.vf   v1, fa0, v0             # v1 += A * v0

.loop:
    vsetvli     t0, a1, e32, m1         # set VL for remaining elements
    beqz        t0, .done
    
    vse32.v     v1, (a0)                # store E values
    
    # Advance: E += A * VLEN
    vfadd.vf    v1, v1, fa4             # v1 += A*VLEN
    
    slli        t1, t0, 2               # t1 = VL * 4 (bytes)
    add         a0, a0, t1              # advance pointer
    sub         a1, a1, t0              # remaining -= VL
    j           .loop

.done:
    ret

riscv

# Triangle inside test: check all 3 edges >= 0
# Inputs: v0=e0, v1=e1, v2=e2 (edge values for VLEN pixels)
# Output: v0 = mask (all 1s if inside, all 0s if outside)

triangle_inside_rvv:
    vsetvli     t0, a0, e32, m1
    
    # Compare each edge >= 0
    vmfge.vf    v4, v0, f0              # v4 = (e0 >= 0) mask
    vmfge.vf    v5, v1, f0              # v5 = (e1 >= 0) mask  
    vmfge.vf    v6, v2, f0              # v6 = (e2 >= 0) mask
    
    # Combine masks: inside = e0>=0 && e1>=0 && e2>=0
    vmand.mm    v0, v4, v5              # v0 = v4 & v5
    vmand.mm    v0, v0, v6              # v0 = v0 & v6
    
    ret

Triangle Rasterization

For a triangle, we evaluate all three edge equations and combine with bitwise AND:

// Check if 4 pixels are inside triangle (all edges positive)
__m128i inside_triangle_x4(__m128 e0, __m128 e1, __m128 e2) {
    __m128 zero = _mm_setzero_ps();
    __m128 m0 = _mm_cmpge_ps(e0, zero);  // e0 >= 0
    __m128 m1 = _mm_cmpge_ps(e1, zero);  // e1 >= 0
    __m128 m2 = _mm_cmpge_ps(e2, zero);  // e2 >= 0
    
    // inside = (e0 >= 0) && (e1 >= 0) && (e2 >= 0)
    __m128 inside = _mm_and_ps(_mm_and_ps(m0, m1), m2);
    return _mm_castps_si128(inside);
}

This approach processes 4-8 pixels per cycle (x86) or VLEN pixels (RISC-V) instead of 1, giving near-linear speedup for triangle rasterization. RVV's advantage is its scalability—the same code runs on hardware with different vector widths without recompilation.