2D solid shape rendering

Introduction

One of 2d engine functions is drawing solid [single-color] primitives. The solid drawing functions use the usual 2D pipeline as described in graph/2d.txt and are available on all cards. The primitives supported are:

  • points [NV1:NV4 and G80+]
  • lines [NV1:NV4]
  • lins [half-open lines]
  • triangles
  • upright rectangles [edges parallel to X/Y axes]

The 2d engine is limitted to integer vertex coordinates [ie. all primitive vertices must lie in pixel centres].

On NV1:G84 cards, the solid drawing functions are exposed via separate source object types for each type of primitive. On G80+, all solid drawing functionality is exposed via the unified 2d object.

Source objects

Each supported primitive type has its own source object class family on NV1:G80. These families are:

  • POINT [NV1:NV4]
  • LINE [NV1:NV4]
  • LIN [NV1:G84]
  • TRI [NV1:G84]
  • RECT [NV1:NV40]

Common methods

The common methods accepted by all solid source objects are:

0100 NOP [NV4-] [graph/intro.txt] 0104 NOTIFY [graph/intro.txt] 010c PATCH [NV4:?] [graph/2d.txt] 0110 WAIT_FOR_IDLE [G80-] [graph/intro.txt] 0140 PM_TRIGGER [NV40-?] [graph/intro.txt] 0180 N DMA_NOTIFY [NV4-] [graph/intro.txt] 0184 N NV1_CLIP [NV5-] [graph/2d.txt] 0188 N NV1_PATTERN [NV5-] [NV1_*] [graph/2d.txt] 0188 N NV4_PATTERN [NV5-] [NV4_* and up] [graph/2d.txt] 018c N NV1_ROP [NV5-] [graph/2d.txt] 0190 N NV1_BETA [NV5-] [graph/2d.txt] 0194 N NV3_SURFACE [NV5-] [NV1_*] [graph/2d.txt] 0194 N NV4_BETA4 [NV5-] [NV4_* and up] [graph/2d.txt] 0198 N NV4_SURFACE [NV5-] [NV4_* and up] [graph/2d.txt] 02fc N OPERATION [NV5-] [graph/2d.txt] 0300 COLOR_FORMAT [NV4-] [graph/solid.txt] 0304 COLOR [graph/solid.txt]

Todo

PM_TRIGGER?

Todo

PATCH?

Todo

add the patchcord methods

Todo

document common methods

POINT

The POINT object family draws single points. The objects are:

  • objtype 0x08: NV1_POINT [NV1:NV4]

The methods are:

0100:0400 [common solid rendering methods] 0400+i*4, i<32 POINT_XY 0480+i*8, i<16 POINT32_X 0484+i*8, i<16 POINT32_Y 0500+i*8, i<16 CPOINT_COLOR 0504+i*8, i<16 CPOINT_XY

Todo

document point methods

LINE/LIN

The LINE/LIN object families draw lines/lins, respectively. The objects are:

  • objtype 0x09: NV1_LINE [NV1:NV4]
  • objtype 0x0a: NV1_LIN [NV1:NV4]
  • class 0x001c: NV1_LIN [NV4:NV40]
  • class 0x005c: NV4_LIN [NV4:G80]
  • class 0x035c: NV30_LIN [NV30:NV40]
  • class 0x305c: NV30_LIN [NV40:G84]

The methods are:

0100:0400 [common solid rendering methods] 0400+i*8, i<16 LINE_START_XY 0404+i*8, i<16 LINE_END_XY 0480+i*16, i<8 LINE32_START_X 0484+i*16, i<8 LINE32_START_Y 0488+i*16, i<8 LINE32_END_X 048c+i*16, i<8 LINE32_END_Y 0500+i*4, i<32 POLYLINE_XY 0580+i*8, i<16 POLYLINE32_X 0584+i*8, i<16 POLYLINE32_Y 0600+i*8, i<16 CPOLYLINE_COLOR 0604+i*8, i<16 CPOLYLINE_XY

Todo

document line methods

TRI

The TRI object family draws triangles. The objects are:

  • objtype 0x0b: NV1_TRI [NV1:NV4]
  • class 0x001d: NV1_TRI [NV4:NV40]
  • class 0x005d: NV4_TRI [NV4:G84]

The methods are:

0100:0400 [common solid rendering methods] 0310+j*4, j<3 TRIANGLE_XY 0320+j*8, j<3 TRIANGLE32_X 0324+j*8, j<3 TRIANGLE32_Y 0400+i*4, i<32 TRIMESH_XY 0480+i*8, i<16 TRIMESH32_X 0484+i*8, i<16 TRIMESH32_Y 0500+i*16 CTRIANGLE_COLOR 0504+i*16+j*4, j<3 CTRIANGLE_XY 0580+i*8, i<16 CTRIMESH_COLOR 0584+i*8, i<16 CTRIMESH_XY

Todo

document tri methods

RECT

The RECT object family draws upright rectangles. Another object family that can also draw solid rectangles and should be used instead of RECT on cards that don’t have RECT is GDI [graph/nv3-gdi.txt]. The objects are:

  • objtype 0x0c: NV1_RECT [NV1:NV3]
  • objtype 0x07: NV1_RECT [NV3:NV4]
  • class 0x001e: NV1_RECT [NV4:NV40]
  • class 0x005e: NV4_RECT [NV4:NV40]

The methods are:

0100:0400 [common solid rendering methods] 0400+i*8, i<16 RECT_POINT 0404+i*8, i<16 RECT_SIZE

Todo

document rect methods

Unified 2d object

Todo

document solid-related unified 2d object methods

Rasterization rules

This section describes exact rasterization rules for solids, ie. which pixels are considered to be part of a given solid. The common variables appearing in the pseudocodes are:

  • CLIP_MIN_X - the left bounduary of the final clipping rectangle. If user clipping rectangle [see graph/2d.txt] is enabled, this is max(UCLIP_MIN_X, CANVAS_MIN_X). Otherwise, this is CANVAS_MIN_X.
  • CLIP_MAX_X - the right bounduary of the final clipping rectangle. If user clipping rectangle is enabled, this is min(UCLIP_MAX_X, CANVAS_MAX_X). Otherwise, this is CANVAS_MAX_X.
  • CLIP_MIN_Y - the top bounduary of the final clipping rectangle, defined like CLIP_MIN_X
  • CLIP_MAX_Y - the bottom bounduary of the final clipping rectangle, defined like CLIP_MAX_X

A pixel is considered to be inside the clipping rectangle if:

  • CLIP_MIN_X <= x < CLIP_MAX_X and
  • CLIP_MIN_Y <= y < CLIP_MAX_Y

Points and rectangles

A rectangle is defined through the coordinates of its left-top corner [X, Y] and its width and height [W, H] in pixels. A rectangle covers pixels that have x in [X, X+W) and y in [Y, Y+H) ranges.

void SOLID_RECT(int X, int Y, int W, int H) {
    int L = max(X, CLIP_MIN_X);
    int R = min(X+W, CLIP_MAX_X);
    int T = max(Y, CLIP_MIN_Y);
    int B = min(Y+H, CLIP_MAX_Y);
    int x, y;
    for (y = T; y < B; y++)
        for (x = L; x < R; x++)
            DRAW_PIXEL(x, y, SOLID_COLOR);
}

A point is defined through its X, Y coordinates and is rasterized as if it was a rectangle with W=H=1.

void SOLID_POINT(int X, int Y) {
    SOLID_RECT(X, Y, 1, 1);
}

Lines and lins

Lines and lins are defined through the coordinates of two endpoints [X[2], Y[2]]. They are rasterized via a variant of Bresenham’s line algorithm, with the following characteristics:

  • rasterization proceeds in the direction of increasing x for y-major lines, and in the direction of increasing y for x-major lines [ie. in the direction of increasing minor component]
  • when presented with a tie in a decision whether to increase the minor coordinate or not, increase it.
  • if rasterizing a lin, the X[1], Y[1] pixel is not rasterized, but calculations are otherwise unaffected
  • pixels outside the clipping rectangle are not rasterized, but calculations are otherwise unaffected

Equivalently, the rasterized lines/lins match those constructed via the diamond-exit rule with the following characteristics:

  • a pixel is rasterized if the diamond inside it intersects the line/lin, unless it’s a lin and the diamond also contains the second endpoint

  • pixels outside the clipping rectangle are not rasterized, but calculations are otherwise unaffected

  • pixel centres are considered to be on integer coordinates

  • the following coordinates are considered to be contained in the diamond for pixel X, Y:

    • abs(x-X) + abs(x-Y) < 0.5 [ie. the inside of the diamond]
    • x = X-0.5, y = Y [ie. top vertex of the diamond]
    • x = X, y = Y-0.5 [ie. leftmost vertex of the diamond]

    [note that the edges don’t matter, other than at the vertices - it’s impossible to create a line touching them without intersecting them, due to integer endpoint coordinates]

void SOLID_LINE_LIN(int X[2], int Y[2], int is_lin) {
    /* determine minor/major direction */
    int xmajor = abs(X[0] - X[1]) > abs(Y[0] - Y[1]);
    int min0, min1, maj0, maj1;
    if (xmajor) {
        maj0 = X[0];
        maj1 = X[1];
        min0 = Y[0];
        min1 = Y[1];
    } else {
        maj0 = Y[0];
        maj1 = Y[1];
        min0 = X[0];
        min1 = X[1];
    }
    if (min1 < min0) {
        /* order by increasing minor */
        swap(min0, min1);
        swap(maj0, maj1);
    }
    /* deltas */
    int dmin = min1 - min0;
    int dmaj = abs(maj1 - maj0);
    /* major step direction */
    int step = maj1 > maj0 ? 1 : -1;
    int min, maj;
    /* scaled error - real error is err/(dmin * dmaj * 2) */
    int err = 0;
    for (min = min0, maj = maj0; maj != maj1 + step; maj += step) {
        if (err >= dmaj) { /* error >= 1/(dmin*2) */
            /* error too large, increase minor */
            min++;
            err -= dmaj * 2; /* error -= 1/dmin */
        }
        int x = xmajor?maj:min;
        int y = xmajor?min:maj;
        /* if not the final pixel of a lin and inside the clipping
           region, draw it */
        if ((!is_lin || x != X[1] || y != Y[1]) && in_clip(x, y))
            DRAW_PIXEL(x, y, SOLID_COLOR);
        error += dmin * 2; /* error += 1/dmaj */
    }
}

Triangles

Triangles are defined through the coordinates of three vertices [X[3], Y[3]]. A triangle is rasterized as an intersection of three half-planes, corresponding to the three edges. For the purpose of triangle rasterization, half-planes are defined as follows:

  • the edges are (0, 1), (1, 2) and (2, 0)
  • if the two vertices making an edge overlap, the triangle is degenerate and is not rasterized
  • a pixel is considered to be in a half-plane corresponding to a given edge if it’s on the same side of that edge as the third vertex of the triangle [the one not included in the edge]
  • if the third vertex lies on the edge, the triangle is degenerate and will not be rasterized
  • if the pixel being considered for rasterization lies on the edge, it’s considered included in the half-plane if the pixel immediately to its right is included in the half-plane
  • if that pixel also lies on the edge [ie. edge is exactly horizontal], the original pixel is instead considered included if the pixel immediately below it is included in the half-plane

Equivalently, a triangle will include exactly-horizontal top edges and left edges, but not exactly-horizontal bottom edges nor right edges.

void SOLID_TRI(int X[3], int Y[3]) {
    int cross = (X[1] - X[0]) * (Y[2] - Y[0]) - (X[2] - X[0]) * (Y[1] - Y[0]);
    if (cross == 0) /* degenerate triangle */
        return;
    /* coordinates in CW order */
    if (cross < 0) {
        swap(X[1], X[2]);
        swap(Y[1], Y[2]);
    }
    int x, y, e;
    for (y = CLIP_MIN_Y; y < CLIP_MAX_Y; y++)
        for (x = CLIP_MIN_X; x < CLIP_MAX_X; x++) {
            for (e = 0; e < 3; e++) {
                int x0 = X[e];
                int y0 = Y[e];
                int x1 = X[(e+1)%3];
                int y1 = Y[(e+1)%3];
                /* first attempt */
                cross = (x1 - x0) * (y - y0) - (x - x0) * (y1 - y0);
                /* second attempt - pixel to the right */
                if (cross == 0)
                    cross = (x1 - x0) * (y - y0) - (x + 1 - x0) * (y1 - y0);
                /* third attempt - pixel below */
                if (cross == 0)
                    cross = (x1 - x0) * (y + 1 - y0) - (x - x0) * (y1 - y0);
                if (cross < 0)
                    goto out;
            }
            DRAW_PIXEL(x, y, SOLID_COLOR);
out:
        }
}