# DX12 My Software Triangle Rasterizer

## Recommended Posts

Hi all! Last weekend I took the time to code a class which can rasterize triangles basing my work on some code I could find on the net, particularly this one over at devmaster. Over the course of this week I extended it and now I would say it is a complete solution. Features:
• The rasterizer can support an arbitrary number of render targets (you will most likely use two, a color buffer and a depth buffer)
• The rasterization is completely decoupled from the actual shading of the visible pixels. You can configure the rasterizer with a pixel shader which does the actual work of computing and assigning a color value.
• It does only use integer math because i intend to use it on the GP2X which does not have an FPU.
• The rasterizer is tile based. Currently it uses blocks of 8x8 pixels.
• It interpolates an arbitrary number of integer varyings across the triangle (so you can use fixed point here). This is done perspectively correct for the corners of each 8x8 block and affine within each block to avoid the costly per pixel divide.
• It supports a clipping rectangle.
• It provides a means for the pixel shader to compute the derivative of the interpolated varyings. This is needed for example to compute the texture mimmap level from the texture coordinates.
• It allows for an early depth test. For example the shader could store the minimum depth value for each 8x8 block and than discad a whole block if the minimum expected depth value for this block is greater than the one stored.
• The source code is actually quite short ~600 lines with a lot of comments.
The only problem I can see right now is with small or large but thin triangles. Because the rasterizer is tile based it must at least scan a whole 8x8 block and test each pixel if it is inside the triangle or not. Large triangles are handled quite efficiently since for the inner part only the corners are tested for inout. What do you think about this. How big a performance problem might this be when targeting the GP2X? I include the code here for everyoune to look at. I would be very thankful for any input of possible improvements.
Header file:
/*

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.

* Neither the name of the <ORGANIZATION> nor the names of its contributors
may be used to endorse or promote products derived from this software
without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef RASTERIZER_EE4F8987_BDA2_434d_A01F_BB3446E535C3
#define RASTERIZER_EE4F8987_BDA2_434d_A01F_BB3446E535C3

class Rasterizer {
public:
// some constants
static const int MAX_RENDER_TARGETS = 2;
static const int MAX_VARYING = 8;
static const int BLOCK_SIZE = 8;

public:
// Type definitions
struct Vertex {
int x, y; // in 28.4 fixed point
int z; // range from 0 to 0x7fffffff
int w; // in 16.16 fixed point
int varyings[MAX_VARYING];
};

// holds the pointers to each render target.
// These will be passed to the fragment shader which then can write to
// the pointed to location. Note: Only the first n pointers will be
// valid where n is the current number of render targets
struct BufferPointers {
void* ptr[MAX_RENDER_TARGETS];
};

// This is the data the fragment shader gets
struct FragmentData {
int z;
int varying[MAX_VARYING];
};

typedef FragmentData PixelBlock[BLOCK_SIZE][BLOCK_SIZE] ;

class RenderTarget {
public:
virtual int width() = 0;
virtual int height() = 0;
virtual int stride() = 0;
virtual void *buffer_pointer() = 0;
virtual int element_size() = 0;
virtual void clear(int x, int y, int w, int h) = 0;
};

public:
// This provides a means for an early depth test.
// x and y are the coordinates of the upper left corner of the current block.
// If the shader somewhere stores the minimum z of each block that value
// can be compared to the parameter z.
// returns false when the depth test failed. In this case the whole block
// can be culled.
virtual bool early_depth_test(int x, int y, int z) { return true; }

// This notifies the shader of any render target clears.
// This is meant to be used in conjunction with the early depth test to update
// any buffers used
virtual void clear(int target, int x, int y, int w, int h) {}

// To compute the mipmap level of detail one needs the derivativs in x and y of
// the texture coordinates. These can be computed from the values in the pixel
// block since all the fragment values have alredy been computed for this block
// when this is called
virtual void prepare_for_block(int x, int y, PixelBlock b) {}

// This tells the rasterizer how many varyings this fragment shader needs
virtual int  varying_count() = 0;

// This is called once for each visible fragment inside the triangle
// x and y are the coordinates within the block [0, BLOCK_SIZE[
// the pixel block is indexed with p[y][x] !!!
virtual void shade(const BufferPointers&, const PixelBlock& b, int x, int y) = 0;
};

private:
// Variables
struct RenderTargetParams {
int count;
int minwidth, minheight;

// cache these params to avoid too
// many virtual function calls
int stride[MAX_RENDER_TARGETS];
int element_size[MAX_RENDER_TARGETS];
} rendertarget_params_;

RenderTarget *rendertargets_[MAX_RENDER_TARGETS];

struct {
int x0, y0, x1, y1;
} clip_rect_;

private:
bool setup_valid();

public:
// constructor
Rasterizer();

public:
// main interface

// Set the render targets.
// This resets the clipping rectangle
void rendertargets(int n, RenderTarget* rt[]);

void clear();
void clear(int target);

void clip_rect(int x, int y, int w, int h);

// The triangle must be counter clockwise in screen space in order to be
// drawn.
void draw_triangle(const Vertex &v1, const Vertex &v2, const Vertex &v3);
};

#endif


Implementation file:
/*

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.

* Neither the name of the <ORGANIZATION> nor the names of its contributors
may be used to endorse or promote products derived from this software
without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include "rasterizer.h"

#include <cmath>
#include <cassert>
#include <algorithm>

#ifndef _MSC_VER
#include <stdint.h>
#else
#include "stdint.h"
#endif

////////////////////////////////////////////////////////////////////////////////
// utility functions

namespace {
inline int min(int a, int b, int c)
{
return std::min(std::min(a,b), c);
}

inline int max(int a, int b, int c)
{
return std::max(std::max(a,b), c);
}

inline void compute_plane(
int v0x, int v0y,
int v1x, int v1y,
int v2x, int v2y,
int z0, int z1, int z2, int64_t plane[4])
{
const int px = v1x - v0x;
const int py = v1y - v0y;
const int pz = z1 - z0;

const int qx = v2x - v0x;
const int qy = v2y - v0y;
const int qz = z2 - z0;

/* Crossproduct "(a,b,c):= dv1 x dv2" is orthogonal to plane. */
const int64_t a = (int64_t)py * qz - (int64_t)pz * qy;
const int64_t b = (int64_t)pz * qx - (int64_t)px * qz;
const int64_t c = (int64_t)px * qy - (int64_t)py * qx;
/* Point on the plane = "r*(a,b,c) + w", with fixed "r" depending
on the distance of plane from origin and arbitrary "w" parallel
to the plane. */
/* The scalar product "(r*(a,b,c)+w)*(a,b,c)" is "r*(a^2+b^2+c^2)",
which is equal to "-d" below. */
const int64_t d = -(a * v0x + b * v0y + c * z0);

plane[0] = a;
plane[1] = b;
plane[2] = c;
plane[3] = d;
}

inline int solve_plane(int x, int y, const int64_t plane[4])
{
assert(plane[2] != 0);
return (int)((plane[3] + plane[0] * x + plane[1] * y) / -plane[2]);
}

template <int denominator>
inline void floor_divmod(int numerator, int &floor, int &mod)
{
assert(denominator > 0);
if(numerator >= 0) {
// positive case, C is okay
floor = numerator / denominator;
mod = numerator % denominator;
} else {
// Numerator is negative, do the right thing
floor = -((-numerator) / denominator);
mod = (-numerator) % denominator;
if(mod) {
// there is a remainder
floor--; mod = denominator - mod;
}
}
}

// Fixed point division
template <int p>
inline int32_t fixdiv(int32_t a, int32_t b)
{
#if 0
return (int32_t)((((int64_t)a) << p) / b);
#else
// The following produces the same results as the above but gcc 4.0.3
// generates fewer instructions (at least on the ARM processor).
union {
int64_t a;
struct {
int32_t l;
int32_t h;
};
} x;

x.l = a << p;
x.h = a >> (sizeof(int32_t) * 8 - p);
return (int32_t)(x.a / b);
#endif
}

// Perform a fixed point multiplication using a 64-bit intermediate result to
// prevent overflow problems.
template <int p>
inline int32_t fixmul(int32_t a, int32_t b)
{
return (int32_t)(((int64_t)a * b) >> p);
}
} // end anonymous namespace

////////////////////////////////////////////////////////////////////////////////

Rasterizer::Rasterizer() :
{
rendertarget_params_.count = 0;
}

bool Rasterizer::setup_valid()
{
return rendertarget_params_.count >= 1 &&
}

void Rasterizer::clear()
{
for (int i = 0; i < rendertarget_params_.count; ++i)
clear(i);
}

void Rasterizer::clear(int target)
{
assert(target <= rendertarget_params_.count);
rendertargets_[target]->clear(0, 0,
rendertarget_params_.minwidth, rendertarget_params_.minheight);

// notify shader about clear (might want to update internal data structutes)
rendertarget_params_.minwidth, rendertarget_params_.minheight);
}

void Rasterizer::clip_rect(int x, int y, int w, int h)
{
if (rendertarget_params_.count == 0) return;

clip_rect_.x0 = std::max(0, x);
clip_rect_.y0 = std::max(0, y);
clip_rect_.x1 = std::min(x + w, rendertarget_params_.minwidth);
clip_rect_.y1 = std::min(y + h, rendertarget_params_.minheight);
}

////////////////////////////////////////////////////////////////////////////////
// main interface

void Rasterizer::rendertargets(int n, RenderTarget* rt[])
{
assert(n <= MAX_RENDER_TARGETS);
RenderTargetParams &rtp = rendertarget_params_;
rtp.count = n;

if (n == 0) return;

rtp.minwidth = rt[0]->width();
rtp.minheight = rt[0]->height();
for (int i = 0; i < n; ++i) {
rendertargets_[i] = rt[i];
rtp.minwidth = std::min(rtp.minwidth, rt[i]->width());
rtp.minheight = std::min(rtp.minheight, rt[i]->height());

// cache these to avoid too many virtual function calls later
rtp.element_size[i] = rt[i]->element_size();
rtp.stride[i] = rt[i]->stride();
}

clip_rect_.x0 = 0;
clip_rect_.y0 = 0;
clip_rect_.x1 = rtp.minwidth;
clip_rect_.y1 = rtp.minheight;
}

{
assert(fs != 0);
}

void Rasterizer::draw_triangle(const Vertex &v1, const Vertex &v2, const Vertex &v3)
{
if (!setup_valid()) return;

int64_t zPlane[4];
int64_t wPlane[4];
int64_t vPlane[MAX_VARYING][4];
compute_plane(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, v1.z, v2.z, v3.z, zPlane);
compute_plane(v1.x, v1.y, v2.x, v2.y, v3.x, v3.y, // interpolate 1/w across triangle
fixdiv<16>(1 << 16, v1.w),
fixdiv<16>(1 << 16, v2.w),
fixdiv<16>(1 << 16, v3.w),
wPlane);
for (int i = 0; i < varying_count; ++i)
compute_plane(
v1.x, v1.y, v2.x, v2.y, v3.x, v3.y,
fixdiv<16>(v1.varyings[i], v1.w),
fixdiv<16>(v2.varyings[i], v2.w),
fixdiv<16>(v3.varyings[i], v3.w),
vPlane[i]
);

// Deltas
const int DX12 = v1.x - v2.x;
const int DX23 = v2.x - v3.x;
const int DX31 = v3.x - v1.x;

const int DY12 = v1.y - v2.y;
const int DY23 = v2.y - v3.y;
const int DY31 = v3.y - v1.y;

// Fixed-point deltas
const int FDX12 = DX12 << 4;
const int FDX23 = DX23 << 4;
const int FDX31 = DX31 << 4;

const int FDY12 = DY12 << 4;
const int FDY23 = DY23 << 4;
const int FDY31 = DY31 << 4;

// Bounding rectangle
int minx = (min(v1.x, v2.x, v3.x) + 0xF) >> 4;
int maxx = (max(v1.x, v2.x, v3.x) + 0xF) >> 4;
int miny = (min(v1.y, v2.y, v3.y) + 0xF) >> 4;
int maxy = (max(v1.y, v2.y, v3.y) + 0xF) >> 4;

// consider clipping rectangle
minx = std::max(minx, clip_rect_.x0);
maxx = std::min(maxx, clip_rect_.x1);
miny = std::max(miny, clip_rect_.y0);
maxy = std::min(maxy, clip_rect_.y1);

// Start in corner of 8x8 block
minx &= ~(BLOCK_SIZE - 1);
miny &= ~(BLOCK_SIZE - 1);

BufferPointers buffers;

for (int i = 0; i < rendertarget_params_.count; ++i)
buffers.ptr[i] = (char*)rendertargets_[i]->buffer_pointer() + miny * rendertargets_[i]->stride();

// Half-edge constants
int C1 = DY12 * v1.x - DX12 * v1.y;
int C2 = DY23 * v2.x - DX23 * v2.y;
int C3 = DY31 * v3.x - DX31 * v3.y;

// Correct for fill convention
if(DY12 < 0 || (DY12 == 0 && DX12 > 0)) C1++;
if(DY23 < 0 || (DY23 == 0 && DX23 > 0)) C2++;
if(DY31 < 0 || (DY31 == 0 && DX31 > 0)) C3++;

// Loop through blocks
for(int y = miny; y < maxy; y += BLOCK_SIZE)
{
for(int x = minx; x < maxx; x += BLOCK_SIZE)
{
// Corners of block
int x0 = x << 4;
int x1 = (x + BLOCK_SIZE - 1) << 4;
int y0 = y << 4;
int y1 = (y + BLOCK_SIZE - 1) << 4;

// Evaluate half-space functions
bool a00 = C1 + DX12 * y0 - DY12 * x0 > 0;
bool a10 = C1 + DX12 * y0 - DY12 * x1 > 0;
bool a01 = C1 + DX12 * y1 - DY12 * x0 > 0;
bool a11 = C1 + DX12 * y1 - DY12 * x1 > 0;
int a = (a00 << 0) | (a10 << 1) | (a01 << 2) | (a11 << 3);

bool b00 = C2 + DX23 * y0 - DY23 * x0 > 0;
bool b10 = C2 + DX23 * y0 - DY23 * x1 > 0;
bool b01 = C2 + DX23 * y1 - DY23 * x0 > 0;
bool b11 = C2 + DX23 * y1 - DY23 * x1 > 0;
int b = (b00 << 0) | (b10 << 1) | (b01 << 2) | (b11 << 3);

bool c00 = C3 + DX31 * y0 - DY31 * x0 > 0;
bool c10 = C3 + DX31 * y0 - DY31 * x1 > 0;
bool c01 = C3 + DX31 * y1 - DY31 * x0 > 0;
bool c11 = C3 + DX31 * y1 - DY31 * x1 > 0;
int c = (c00 << 0) | (c10 << 1) | (c01 << 2) | (c11 << 3);

// Skip block when outside an edge
if(a == 0x0 || b == 0x0 || c == 0x0) continue;

#define CLIP_TEST(X, Y) 				((X) >= clip_rect_.x0 && (X) < clip_rect_.x1 && 				(Y) >= clip_rect_.y0 && (Y) < clip_rect_.y1)

// test for the clipping rectangle
bool clip00 = CLIP_TEST(x, y);
bool clip10 = CLIP_TEST(x + 7, y);
bool clip01 = CLIP_TEST(x, y + 7);
bool clip11 = CLIP_TEST(x + 7, y + 7);

// skip block if all is clippled
if (!clip00 && !clip10 && !clip01 && !clip11) continue;
bool clip_all_in = clip00 && clip10 && clip01 && clip11;

//! compute attribute interpolants at corners
FragmentData f00;
FragmentData f10;
FragmentData f01;
FragmentData f11;

int xx1 = (x + BLOCK_SIZE) << 4;
int yy1 = (y + BLOCK_SIZE) << 4;
f00.z = solve_plane(x0, y0, zPlane);
f10.z = solve_plane(xx1, y0, zPlane);
f01.z = solve_plane(x0, yy1, zPlane);
f11.z = solve_plane(xx1, yy1, zPlane);

if (!fragment_shader_->early_depth_test(x, y, std::min(std::min(std::min(f00.z, f10.z), f01.z), f11.z)))
continue;

int w00 = fixdiv<16>(1 << 16, solve_plane(x0, y0, wPlane));
int w10 = fixdiv<16>(1 << 16, solve_plane(xx1, y0, wPlane));
int w01 = fixdiv<16>(1 << 16, solve_plane(x0, yy1, wPlane));
int w11 = fixdiv<16>(1 << 16, solve_plane(xx1, yy1, wPlane));
for (int i = 0; i < varying_count; ++i) {
f00.varying[i] = fixmul<16>(solve_plane(x0, y0, vPlane[i]), w00);
f10.varying[i] = fixmul<16>(solve_plane(xx1, y0, vPlane[i]), w10);
f01.varying[i] = fixmul<16>(solve_plane(x0, yy1, vPlane[i]), w01);
f11.varying[i] = fixmul<16>(solve_plane(xx1, yy1, vPlane[i]), w11);
}

//! compute attribute step y left and right
struct varying_step_t {
struct step_info_t {
int step;
int rem;
int error_term;
step_info_t():error_term(0){}

int dostep() {
int r = step;
error_term += rem;
if (error_term >= BLOCK_SIZE) {
error_term -= BLOCK_SIZE;
r++;
}
return r;
}
};

step_info_t z;
step_info_t varying[MAX_VARYING];

varying_step_t(FragmentData& p1, FragmentData& p2, int vc)
{
floor_divmod<BLOCK_SIZE>(p2.z - p1.z, z.step, z.rem);
for (int i = 0; i < vc; ++i) {
floor_divmod<BLOCK_SIZE>(p2.varying[i] - p1.varying[i], varying[i].step, varying[i].rem);
}
}
};

varying_step_t step_left(f00, f01, varying_count);
varying_step_t step_right(f10, f11, varying_count);

BufferPointers block_buffers = buffers;

#define RENDER_TARGET_LOOP 				for (int i = 0; i < rendertarget_params_.count; ++i)

#define STEP_POINTERS_BY_ELEMENTSIZE(VAR, FACTOR) 				{ 					RENDER_TARGET_LOOP 					(char*&)VAR.ptr[i] += FACTOR * rendertarget_params_.element_size[i]; 				}

#define	STEP_POINTERS_BY_STRIDE(VAR) 				{ 					RENDER_TARGET_LOOP 					(char*&)VAR.ptr[i] += rendertarget_params_.stride[i]; 				}

#define STEP_FRAGMENTDATA(FDVAR, STEPVAR) 				{ 					FDVAR.z += STEPVAR.z.dostep(); 					for (int i = 0; i < varying_count; ++i) 						FDVAR.varying[i] += STEPVAR.varying[i].dostep(); 				}

// only copy the neccessary varyings
#define EFFICIENT_COPY(SRC, DST) 				{ 					DST.z = SRC.z; 					for (int i = 0; i < varying_count; ++i) 						DST.varying[i] = SRC.varying[i]; 				}

#define BLOCK_BEGIN 				fragment_shader_->prepare_for_block(x, y, pixel_block); 				for (int iy = 0; iy < BLOCK_SIZE; ++iy) { 					BufferPointers inner = block_buffers; 					STEP_POINTERS_BY_ELEMENTSIZE(inner, x); 					for (int ix = 0; ix < BLOCK_SIZE; ++ix) {

#define BLOCK_END 						STEP_POINTERS_BY_ELEMENTSIZE(inner, 1); 					} 					STEP_POINTERS_BY_STRIDE(block_buffers); 				}

PixelBlock pixel_block;

bool skip_flag[BLOCK_SIZE][BLOCK_SIZE];
memset(skip_flag, 0, sizeof(skip_flag));

if (!clip_all_in) {
for (int iy = 0; iy < BLOCK_SIZE; ++iy)
for (int ix = 0; ix < BLOCK_SIZE; ++ix)
if (!CLIP_TEST(ix + x, iy + y))
skip_flag[iy][ix] = true;
}

// Accept whole block when totally covered
if(a == 0xF && b == 0xF && c == 0xF)
{
// first compute all fragment data
for(int iy = 0; iy < BLOCK_SIZE; iy++)
{
//! compute attribute step x for this scanline
varying_step_t stepx(f00, f10, varying_count);
FragmentData fragment_data = f00;

for(int ix = 0; ix < BLOCK_SIZE; ix++)
{
EFFICIENT_COPY(fragment_data, pixel_block[iy][ix]);
STEP_FRAGMENTDATA(fragment_data, stepx);
}

//! step left and right attrib y
STEP_FRAGMENTDATA(f00, step_left);
STEP_FRAGMENTDATA(f10, step_right);
}

//! fragment_shader_block (can now use derivatives of attributes)
if (clip_all_in) {
BLOCK_BEGIN
BLOCK_END
} else {
BLOCK_BEGIN
if (!skip_flag[iy][ix])
BLOCK_END
}
}
else // Partially covered block
{
int CY1 = C1 + DX12 * y0 - DY12 * x0;
int CY2 = C2 + DX23 * y0 - DY23 * x0;
int CY3 = C3 + DX31 * y0 - DY31 * x0;

for(int iy = 0; iy < BLOCK_SIZE; iy++)
{
int CX1 = CY1;
int CX2 = CY2;
int CX3 = CY3;

//! compute attribute step x for this scanline
varying_step_t stepx(f00, f10, varying_count);

FragmentData fragment_data = f00;

for(int ix = 0; ix < BLOCK_SIZE; ix++)
{
if(!(CX1 > 0 && CX2 > 0 && CX3 > 0))
skip_flag[iy][ix] = true;

// we still need to do this since the fragment shader might want
// to compute the derivative of attibutes
EFFICIENT_COPY(fragment_data, pixel_block[iy][ix]);

CX1 -= FDY12;
CX2 -= FDY23;
CX3 -= FDY31;

STEP_FRAGMENTDATA(fragment_data, stepx);
}

CY1 += FDX12;
CY2 += FDX23;
CY3 += FDX31;

//! step left and right attrib y
STEP_FRAGMENTDATA(f00, step_left);
STEP_FRAGMENTDATA(f10, step_right);
}

//! fragment_shader_block (can now use derivatives of attributes)
BLOCK_BEGIN
if (!skip_flag[iy][ix])
BLOCK_END
}
}

for (int i = 0; i < rendertarget_params_.count; ++i)
(char*&)buffers.ptr[i] += BLOCK_SIZE * rendertargets_[i]->stride();

}
}


Test program:
/*

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.

* Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.

* Neither the name of the <ORGANIZATION> nor the names of its contributors
may be used to endorse or promote products derived from this software
without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include "SDL.h"
#include "rasterizer.h"

#include <cmath>
#include <algorithm>

class SDL_SurfaceRenderTarget : public Rasterizer::RenderTarget {
SDL_Surface *surface;
public:
SDL_SurfaceRenderTarget(SDL_Surface *s):surface(s) {}
virtual int width() { return surface->w; }
virtual int height() { return surface->h; }
virtual int stride() { return surface->pitch; }
virtual int element_size() { return sizeof(int); }
virtual void* buffer_pointer() { return surface->pixels; }
virtual void clear(int x, int y, int w, int h) {}
};

public:
virtual int varying_count() { return 3; }
virtual void shade(const Rasterizer::BufferPointers& ptrs, const Rasterizer::PixelBlock& block, int x, int y)
{
unsigned int* color_buffer = (unsigned int*)ptrs.ptr[0];

// unfortunaltely at the corners of the triangle we can get negative
// values for the interpolants -> std::max
int r = std::max(0, block[y][x].varying[0]);
int g = std::max(0, block[y][x].varying[1]);
int b = std::max(0, block[y][x].varying[2]);
int color = r << 16 | g << 8 | b;
*color_buffer = color;
}
};

int main(int ac, char *av[])
{
SDL_Init(SDL_INIT_VIDEO);
SDL_Surface *screen = SDL_SetVideoMode(320, 240, 32, SDL_SWSURFACE);

Rasterizer r;
SDL_SurfaceRenderTarget color_target(screen);

Rasterizer::RenderTarget* rendertargets[] = { &color_target};
r.rendertargets(1, rendertargets);
r.clip_rect(45, 70, 100, 100);

Rasterizer::Vertex v[3];

v[0].x = (int)(120.0f * 16.0f);
v[0].y = (int)(50.0f * 16.0f);
v[0].z = 0;
v[0].w = 1 << 16;
v[0].varyings[0] = 255;
v[0].varyings[1] = 0;
v[0].varyings[2] = 0;

v[1].x = (int)(20.0f  * 16.0f);
v[1].y = (int)(100.0f * 16.0f);
v[1].z = 0x7fffffff;
v[1].w = 1 << 16;
v[1].varyings[0] = 0;
v[1].varyings[1] = 255;
v[1].varyings[2] = 0;

v[2].x = (int)(150.0f * 16.0f);
v[2].y = (int)(220.0f * 16.0f);
v[2].z = 0x7fffffff >> 1;
v[2].w = 1 << 16;
v[2].varyings[0] = 0;
v[2].varyings[1] = 0;
v[2].varyings[2] = 255;

SDL_Rect rect;
rect.x = 45;
rect.y = 70;
rect.w = 100;
rect.h = 100;
SDL_FillRect(screen, &rect, 0xffffffff);

r.draw_triangle(v[0], v[1], v[2]);

SDL_Flip(screen);

SDL_Event e;
while (SDL_WaitEvent(&e) && e.type != SDL_QUIT);

SDL_Quit();
return 0;
}


I don't include the stdint.h file. You can get it yourself if needed. OK, i now have a domain www.trenki.net where I uploaded a vastly improved version of the renderer. The above code is obsolete, the features are retained. [Edited by - Trenki on August 22, 2007 5:11:28 AM]

##### Share on other sites
Quote:
 Original post by TrenkiThis is done perspectively correct for the corners of each 8x8 block and affine within each block to avoid the costly per pixel divide.

Doesn't this cause errors near the edges of the triangles?

##### Share on other sites
Quote:
Original post by C0D1F1ED
Quote:
 Original post by TrenkiThis is done perspectively correct for the corners of each 8x8 block and affine within each block to avoid the costly per pixel divide.

Doesn't this cause errors near the edges of the triangles?

In the test program I interpolate three colors over the triangle. In the fragment shader it could happen that one of the interpolated rgb components became nagative at the edges of the triangle so I had to clamp them to zero.
But I also looked at the mesa source code and they have the same problem at the edges and AFAIK they are doing the perspective correction per pixel. They have extra code to clamp the colors at the edges of the triangle.

##### Share on other sites
for me the devmaster link doesn't work. could you tell us what article you mean?
thanks

##### Share on other sites
Quote:
 Original post by TrenkiIn the test program I interpolate three colors over the triangle. In the fragment shader it could happen that one of the interpolated rgb components became nagative at the edges of the triangle so I had to clamp them to zero.

Clamping helps for colors, but texture coordinates are unbounded. So at the edges of triangle you could get unwanted wrapping.
Quote:
 But I also looked at the mesa source code and they have the same problem at the edges and AFAIK they are doing the perspective correction per pixel. They have extra code to clamp the colors at the edges of the triangle.

Interesting. Is that just to prevent the components from becoming negative due to rounding error then?

##### Share on other sites
Quote:
 Original post by Eitschfor me the devmaster link doesn't work. could you tell us what article you mean? thanks

Advanced Rasterization by Nicolas Capens, also known as c0d1f1ed. [wink]

##### Share on other sites
Quote:
Original post by C0D1F1ED
Quote:
 Original post by TrenkiIn the test program I interpolate three colors over the triangle. In the fragment shader it could happen that one of the interpolated rgb components became nagative at the edges of the triangle so I had to clamp them to zero.

Clamping helps for colors, but texture coordinates are unbounded. So at the edges of triangle you could get unwanted wrapping.

Yes, this might happen. In December I tried to code a triangle rasterizer following Chris Heckers series on perspective texture mapping. There the varyings are interpolated along the edges but I still got the wrapping effect with the texture coordinates. Maybe I did something wrong... In the end I stopped working on it because I didn't like the code at all and it also was quite involved and not as general as the one above.

##### Share on other sites
Quote:
Original post by C0D1F1ED
Quote:
 Original post by Eitschfor me the devmaster link doesn't work. could you tell us what article you mean? thanks

Advanced Rasterization by Nicolas Capens, also known as c0d1f1ed. [wink]
Huh, that's you?

I'm coding up a softrast based on what you wrote -- though I'm also doing a bit of C++ voodoo with it. That way I don't suffer from the heavy penalty of doing multiple virtual calls for every single fragment (which is what the OP is doing), along with a few other niceties.

##### Share on other sites
Quote:
 That way I don't suffer from the heavy penalty of doing multiple virtual calls for every single fragment (which is what the OP is doing), along with a few other niceties.

There should be only one virtual function call per fragment and I don't believe this virtual function call is a heavy penalty. I could be using a function pointer instead but do you really believe that would be faster?

Quote:
 along with a few other niceties.

Could you please elaborate on this and point out what exacly you mean.

[Edited by - Trenki on May 27, 2007 1:06:21 PM]

##### Share on other sites
Have you looked at this paper:
Triangle Scan Conversion using 2D Homogenous Coordinates

It dodges quite nicely many problems related to projection of 3D triangles to 2D, such as, w component being 0. Basicly, you don't need frustum clipping if you use homogenous rasterizer. I definitely recommend you to at least read the paper.

Also one idea worth investigating is using hierarchical z-buffer, which may improve performance especially in case of high depth complexity scenes.

##### Share on other sites
Quote:
 Original post by WinogradHave you looked at this paper:Triangle Scan Conversion using 2D Homogenous CoordinatesIt dodges quite nicely many problems related to projection of 3D triangles to 2D, such as, w component being 0. Basicly, you don't need frustum clipping if you use homogenous rasterizer. I definitely recommend you to at least read the paper.Also one idea worth investigating is using hierarchical z-buffer, which may improve performance especially in case of high depth complexity scenes.

I know of the paper you mentioned and I took a quit look at it but didn't read it all. I didn't understand everything and I also din't get how to actually draw the triangle to the 2d screen at the end + perspective divide for each pixel is too expensive.

Regarding the hierachical z-buffer: I already thought about this and provided a way for the shader to do it. Basically the shader can remember the minimum z of each 8x8 block and than let the rasterizer reject the whole block if it determins that the minimum expected z value for this block is larger.

##### Share on other sites
Quote:
 Original post by TrenkiThere should be only one virtual function call per fragment and I don't believe this virtual function call is a heavy penalty. I could be using a function pointer instead but do you really believe that would be faster?
I do, yes. It's small, but when you're handling things per fragment, that's a lot of calls. (About 29 mil at 800 x 600 at 60fps, and that's with zero overdraw.) Plus I have a few low level ideas I want to play with...
Quote:
Quote:
 along with a few other niceties.

Could you please elaborate on this and point out what exacly you mean.
Sorry, it's strictly experimental R&D right now and I would prefer not to say too much until I know for sure what works and what doesn't. Here's a teaser though.
VERTEX_SHADER( Shader ){	VS_INPUTS (		((Float4, Position, Position))		((Float4, Diffuse, Color))	);	VS_OUTPUTS (		((Float4, Position, Position))		((Float4, Diffuse, Color))	);	VS_Output SimpleVS( const VS_Input& in )	{		VS_Output out;				out.Position = in.Position;		out.Diffuse = in.Diffuse;				return out;	}} END_VS( Shader );
That's pure C++ code. It should generate vectorized SSE when I'm done.

[Edited by - Promit on May 27, 2007 4:49:07 PM]

##### Share on other sites
Quote:
 Original post by TrenkiThere should be only one virtual function call per fragment and I don't believe this virtual function call is a heavy penalty. I could be using a function pointer instead but do you really believe that would be faster?

Virtual functions are just an abstraction of function pointers. So it wouldn't be faster to use a function pointer explicitely. However, argument passing is quite expensive. You might be able to speed things up a little by making the arguments class members and sharing them with the shader routine. Beware of turning things into spaghettic code though...

##### Share on other sites
Quote:
 Original post by WinogradBasicly, you don't need frustum clipping if you use homogenous rasterizer.

That's a nice property for a hardware implementation, but in software clipping is quite simple and fast. The homogenous rasterizer needs extra work per pixel, which makes it less attractive for software.
Quote:
 Also one idea worth investigating is using hierarchical z-buffer, which may improve performance especially in case of high depth complexity scenes.

Yeah, my implementation with 8x8 blocks can be used directly with a hierarchical z-buffer. In my experience it's not worth it when working with low resolutions though (typically the case for a software renderer), but your mileage may vary.

##### Share on other sites
Quote:
 Original post by PromitSorry, it's strictly experimental R&D right now and I would prefer not to say too much until I know for sure what works and what doesn't. Here's a teaser though.*** Source Snippet Removed ***That's pure C++ code. It should generate vectorized SSE when I'm done.

Have you looked at Sh yet? It's capable of writing out C code that can be compiled at run-time with GCC or ICC.

What back-end are you using to generate SSE code?

##### Share on other sites
Question to C0D1F1ED: As you pointed out I could get an undesired wrapping effect for the texture coordinates at the edges of the triangles. I have given it some thought but could not come up with a satisfactory solution. What would you suggest without requiring the expensive perspective correction and retaining the overall design?

##### Share on other sites
Quote:
 Original post by TrenkiAs you pointed out I could get an undesired wrapping effect for the texture coordinates at the edges of the triangles. I have given it some thought but could not come up with a satisfactory solution. What would you suggest without requiring the expensive perspective correction and retaining the overall design?

For fully covered tiles, keep using linear interpolation. For partially covered tiles, use per-pixel perspective correction.

To avoid even more perspective correction, you can detect which triangles are either small enough or 'flat' enough not to require perspective correction at all...

But beware of the law of premature optimization! This is going to complicate your design, and could make it quite complicated to maintain the code. So only do it if you really need it and everything else is functional.

The wrapping is not that terrible, so depending on the needs of your projects you might not need to solve it at all.

##### Share on other sites
Quote:
Original post by C0D1F1ED
Quote:
 Original post by WinogradBasicly, you don't need frustum clipping if you use homogenous rasterizer.

That's a nice property for a hardware implementation, but in software clipping is quite simple and fast. The homogenous rasterizer needs extra work per pixel, which makes it less attractive for software.

Clipping is quite fast on hardware also ;) Well I guess your point is that on hardware there is no extra per pixel cost except in the number of gates. I haven't implemented such rasterizer but at quick glance it seems one could apply "DDA"-like algorithm which would account to basicly 4 additions per pixel of which one is used for perspective division.

##### Share on other sites
I've now coded up a vertex transformation and clipping pipeline and tested the whole stuff with a cube. It runs fine for five seconds and then I get an integer division by 0 in the rasterizer.

I could trace it to this line
int w10 = fixdiv<16>(1 << 16, solve_plane(xx1, y0, wPlane));

Apparently solve_plane returns 0 here. I checked with my calculator using the values VS studio gave me but if I did the calculations correctly it should really ba returning 1. Still this is a problem since such things should not happen.

The problems with the triangles at the top of the cube when it is viewed at a shallow angle (y coordinates of the corners: 243 244 246).

Does anyone have suggestions on how to counter this problem?

##### Share on other sites
Quote:
 Original post by TrenkiI checked with my calculator using the values VS studio gave me but if I did the calculations correctly it should really ba returning 1.

Did you enable break on exceptions in the Debug > Exceptions... menu? When the exception occurs, break, and then place the 'yellow arrow' at the start of the calculation (you might need to first step out of the function, then move the arrow). This way you can interactively follow the calculations. Pressing Alt+F8 will show the disassembly so you can follow one instruction at a time. Or you can split your C++ calculation up into elemental computations so you can follow line by line.

That should quickly reveal the cause of the error...

##### Share on other sites
The division by zero exception occurred and visual studio pointed me right at the location where that happend. The value solve_plane returned really was zero, so that resulted in the following division by 0.

The thing is that I compute 1/w for the corners of each 8x8 block using the plane equation calculated earlier. From this i compute W by taking the reciprocal. Since the corners of the block can lie outside the triangle I also can get values that I would not get if I stayed inside the triangle all the time.

I fixed it by simply setting the value to 1 if it was 0. Now the demo program which animates a simple cube runs.

Do you know where the profiler in Visual Studio is? Currently I use Orcas Beta 1.

##### Share on other sites
Hi!

I have finished my vertex and clipping pipeline, so I could do some speed tests with my rasterizer. I get 600fps at 320x240 and ~60fps at 1024x768 on my AMD Athlon64 3500+ (2.2 Ghz) for a scene with a single gouraud shaded cube. The cube constanly fills ~1/9 of the screen area. As I don't have any numbers to compare this to I don't know how good/bad this is.

Thinking back to the days of DOS where I played Fatal Racing at 640x480 on my Pentium 166 which ran at ~20-30fps and filled the whole screen and also had texture mapping my rasterizer seems slow. What do you guys think?

I also did some profiling with gprof:
   %   cumulative   self             time   seconds   seconds    calls  name     72.20      4.26     4.26    31899  Rasterizer::draw_triangle 14.07      5.09     0.83           __divdi3 12.54      5.83     0.74 47792689  TestFragmentShader::shade

Even though shade is called 47 million times it requires less time than draw_triangle. Probably because the interpolation of the varyings happens in draw_triangle. I don't know how much the virtual function call per pixel affects the performance and wether the time spent on the call is added to the draw_triangle total time or to the shade time. I will try to remove the parameters from the shade function and find anonther way to let the shader know about the required values. Maybe that speeds things up a little.

[Edited by - Trenki on May 29, 2007 12:56:49 PM]

##### Share on other sites
Quote:
Original post by C0D1F1ED
Quote:
 Original post by Eitschfor me the devmaster link doesn't work. could you tell us what article you mean? thanks

Advanced Rasterization by Nicolas Capens, also known as c0d1f1ed. [wink]

You know this guy? Seems to be cool... [smile]

##### Share on other sites
Quote:
 Original post by TrenkiI have finished my vertex and clipping pipeline, so I could do some speed tests with my rasterizer.

I recommend you to run some simple sweep tests. For example, keep the total rasterized pixels constant by rectangular area with strip of triangles. Vary the number of triangles per frame linearly, starting from 1 or 2 and going up. Notice that you will first be fill limited, and thus increasing triangle count does not have much effect. When the graph starts to climb linearly you are geometry limited and the slope gives you your peak triangle rate.

In second test, keep the triangle count constant, but vary the number of rasterized pixels. The slope will give you the peak pixel rate.

You can calculate the approximate number clks used per pixel basis and overhead caused by geometry processing. Ideally geometry would be processed in parallel with rasterization.

##### Share on other sites
Quote:
 Original post by TrenkiI get 600fps at 320x240 and ~60fps at 1024x768 on my AMD Athlon64 3500+ (2.2 Ghz) for a scene with a single gouraud shaded cube. The cube constanly fills ~1/9 of the screen area. As I don't have any numbers to compare this to I don't know how good/bad this is.

What you really should be questioning is what are your own goals? Increasing performance at this point is without a doubt going to make your software hard to maintain. So if you want to add texture mapping and things like that, add it first. As long as things are interactive enough to test, performance is really fine. Once all functionality you need is implemented you can concentrate on the real bottlenecks. It's very likely that texturing will be a major new bottneck, so much of the work you'd currenly do on the gouraud shading would be largely pointless.

Also, if you really target the GP2X then you should only look at how it performs on that. At the resolution of 320x240 it might not even be worth it to use 8x8 pixel tiles. Different architectures have different needs. Maybe it's bandwidth limited and you should really concentrate on addressing that first...

So the best advice I can give you is to stop programming and start developing. Write down your goals so you have something to concentrate on. That way we also know what advice to give you, instead of sending you in the wrong directions. Trust me, pinpointing your goals is an extremely crucial step towards a succesful project.

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627658
• Total Posts
2978474
• ### Similar Content

• By Mr_Fox
Hi Guys,
Does anyone know how to grab a video frame on to DX texture easily just using Windows SDK? or just play video on DX texture easily without using 3rd party library?  I know during DX9 ages, there is a DirectShow library to use (though very hard to use). After a brief search, it seems most game dev settled down with Bink and leave all hobbyist dx programmer struggling....
Having so much fun play with Metal video playback (super easy setup just with AVKit, and you can grab movie frame to your metal texture), I feel there must be a similar easy path for video playback on dx12 but I failed to find it.
Maybe I missed something? Thanks in advance for anyone who could give me some path to follow
• By _void_
Hello guys,
I have a texture of format DXGI_FORMAT_B8G8R8A8_UNORM_SRGB.
Is there a way to create shader resource view for the texture so that I could read it as RGBA from the shader instead of reading it specifically as BGRA?
I would like all the textures to be read as RGBA.

Tx
• By _void_
Hello guys,
I am wondering why D3D12 resource size has type UINT64 while resource view size is limited to UINT32.
typedef struct D3D12_RESOURCE_DESC { … UINT64                   Width; … } D3D12_RESOURCE_DESC; Vertex buffer view can be described in UINT32 types.
typedef struct D3D12_VERTEX_BUFFER_VIEW { D3D12_GPU_VIRTUAL_ADDRESS BufferLocation; UINT                      SizeInBytes; UINT                      StrideInBytes; } D3D12_VERTEX_BUFFER_VIEW; For the buffer we can specify offset for the first element as UINT64 but the buffer view should still be defined in UINT32 terms.
typedef struct D3D12_BUFFER_SRV { UINT64                 FirstElement; UINT                   NumElements; UINT                   StructureByteStride; D3D12_BUFFER_SRV_FLAGS Flags; } D3D12_BUFFER_SRV; Does it really mean that we can create, for instance, structured buffer of floats having MAX_UNIT64 elements (MAX_UNIT64 * sizeof(float) in byte size) but are not be able to create shader resource view which will enclose it completely since we are limited by UINT range?
Is there a specific reason for this? HLSL is restricted to UINT32 values. Calling function GetDimensions() on the resource of UINT64 size will not be able to produce valid values. I guess, it could be one of the reasons.

Thanks!
• By pcmaster
Hello!
Is it possible to mix ranges of samplers and ranges of SRVs and ranges of UAVs in one root parameter descriptor table? Like so:
D3D12_DESCRIPTOR_RANGE ranges[3]; D3D12_ROOT_PARAMETER param; param.ParameterType = D3D12_ROOT_PARAMETER_TYPE_DESCRIPTOR_TABLE; param.DescriptorTable.NumDescriptorRanges = 3; param.DescriptorTable.pDescriptorRanges = ranges; range[0].RangeType = D3D12_DESCRIPTOR_RANGE_TYPE_SRV; .. range[1].RangeType = D3D12_DESCRIPTOR_RANGE_TYPE_UAV; .. range[2].RangeType = D3D12_DESCRIPTOR_RANGE_TYPE_SAMPLER; .. I wonder especially about CopyDescriptors, that will need to copy a range of D3D12_DESCRIPTOR_HEAP_TYPE_SAMPLER and a range of D3D12_DESCRIPTOR_HEAP_TYPE_CBV_SRV_UAV.
Thanks if anyone knows (while I try it :))
.P

• So I was reading the presentation Practical DirectX 12 - Programming Model and Hardware Capabilities again and finally decided to tackle proper command list submission.  Things mentioned in the document regarding this subject:
Aim for (per-frame): ● 15-30 Command Lists ● 5-10 ‘ExecuteCommandLists’ calls
Each ‘ ExecuteCommandLists’ has a fixed CPU overhead ● Underneath this call triggers a flush ● So batch up command lists
Try to put at least 200μs of GPU work in each ‘ExecuteCommandLists’, preferably 500μs
Small calls to ‘ExecuteCommandLists’ complete faster than the OS scheduler can submit new ones
OS takes ~60μs to schedule upcoming work
So basically I want to estimate how long my draw calls take.  Benchmarking for a particular piece of hardware seems impractical.  So given the stats primitive count, pixel count(approximately how many screen space pixels the call will be rendered to), and some precomputed metric associated with shader ALU complexity(like # of alu ops) do you think that I can get a reasonable estimation of how much time a draw call will take?
What do you do to take this into account?
What about other things like transitions?  I can only think of actual measurement in this case.

• 10
• 12
• 22
• 13
• 33