Talk:Polygon Rasterization (C)

From LiteratePrograms
Jump to: navigation, search

Alright, just wanted to document a few more stuff about this algorithm. I tried about 6 or 7 different versions, it would be nice to document what the previous iterations were. If someone wants to improve it, better to know in advance what will not work, or at least be very disappointing in terms of performance.

The very first version was just a basic non anti-alias polygon-fill algorithm. I wanted to check what will be the upper limit in terms of drawing per second. After some tweaking, I got something like 30,000 polygons/s. I also check the performance of the SDL_Gfx library, just do be sure I didn't do a piss poor job. Performance were roughly the same.

The second implementation used a full trapezoid surface tessellation approach. After way too many days trying to tweak the algorithm, the results were still quite poor: about 6000p./s, code was ugly and countless of graphical glitches. I gave up and decided to try a different approach.

The third version is the naive approach described in the first part of this article: monotonous increase of DDAs, sum of scanlines. Quality is very good, no particular constraints on the polygon shape, but, by far, it is the slowest approach: 4500p./s. I was quite disappointed. I tried to do some minor tweaks to the algorithm, but I got the feeling that up to 16 iterations per scanline were too much: you've got to reduce this number for any significant performance gain.

Next version used a hybrid between the two previous methods: the code for surface tessellation with partial line was way too complex and fragile, I decided to keep the simple iteration and sum for this case and use the surface tessellation only for complete lines (16 iterations). I was actually very pleased with the performances: almost 12000p./s, and no graphical glitches, although the code looks quite messy, due to all the edge cases there is to deal with.

I decided to try another approach for tessellating the surface of the trapezoid: kind of an hybrid between direct surface computation and summation through DDA. Sadly those inner loops (i: 0...VALUES-1) were real performance killer: with this code below, I got around 9500p./s (and still a few graphical glitches). This is where I decided to stop.

static int DrawTriangle(DATA16 p, Iter iter, int right)
{
	DATA16 s;
	int    i, t, x, xe, x0, inc;
	if (iter->sx < 0)
	{
		int ret = iter->x>>BPP;
		if (right < 0) t =  SURF-VALUES, inc = -VALUES;
		else           t = -SURF+VALUES, inc =  VALUES;
		for (i = 0, x0 = iter->x, x = x0 >> BPP, s = p + x; i < VALUES; i ++, t += inc)
		{
			if (right < 0) *s += VALUES - (x0 & MASK);
			else           *s -= VALUES - (x0 & MASK); IterDDA(iter);
			x0 = iter->x; xe = x0 >> BPP;
			while (x > xe) *s-- += t, x--;
		}
		if (right >= 0)
			for (x = ret - 1, s = p + x; x > right; x--, *s-- += SURF);
		return ret;
	}
	else
	{
		inc = right < 0 ? VALUES : -VALUES;
		for (i = t = 0, x0 = iter->x, x = x0 >> BPP, s = p + x; i < VALUES; i ++, t += inc)
		{
			if (right < 0) *s += VALUES - (x0 & MASK);
			else           *s -= VALUES - (x0 & MASK); IterDDA(iter);
			x0 = iter->x; xe = x0 >> BPP;
			while (x < xe) *++s += t, x++;
		}
		if (right >= 0)
			for (x0 = x; x0 > right; *s-- += SURF, x0--);
		return x;
	}
}

Tpierron (talk) 19:38, 21 December 2012 (UTC)

hijacker
hijacker
hijacker
hijacker