8 replies to this topic

[Kackurot]

Hey, I am doing sotfare rasterization and I was wondering if anyone here done triangle rasterization in software using fixpoint. I have a triangle rasterizer that is using fixed 16.16 and it tends to get tears in geometry from time to time. If I render something simple as a cube, it renders ok, very little tearing, but.. if I render something big as like a game level that has a lot of curves or any object that has curves in it, I get tears. SO I was wondering if anyone knew a solution or has come this problem using fixed. I have searched the internet and the most software triangle rasterizers I have found are using floating point, so if anyone knows a solution, has come to this problem or has a hint of a solution, please let me know. Also, Nick if you veiwing this, I would love to have your help on this.

[Nils Pipenbrinck]

Could you please send a screenshot? I wonder how your tearing problem looks like.. (I associate tearing with the effect that you'll see if your display rate does not match the monitor refresh rate). However, I don't think that's the problem you have.

Regarding fixed point: No problem at all - I can help you with that. Programmers just have become lazy and don't do fixed point rasterizers anymore also they are still more precise than float rasterizers.

[Kackurot]

Ok heres the pick of a 9000 poly level:




uses my smiley image as texture ^~

As you can see,it has alot of cracks. If you want I can send you my source and you can take a look at it. I use 16:16 fixed. I use the http://www.exaflop.o...ixel%20accuracy to implement my renderer, well I use it as a reference. So if you no something that must be done in fixed point math that prevents this or maybe something I might be missing, it would be a bifg help. Thanks

[Nick]

If you mean there are cracks between the polygon, like this, you should read my Advanced Rasterization article. Chris Hecker's Perspective Texture Mapping articles also feature a very accurate rasterizer.

[Nils Pipenbrinck]

As far as I can see, the background has been filled with a cyan color, and the cracks you'll see are cyan and mostly horizontal edges. I bet these are the edges that have a height less than one (fixed point wise). If so you have messed up an important special case. Easy to fix.

Anyways, let's take a shortcut. Take a look at my code and cut'n'paste it into your engine (shouldn't be much of a problem). It will do pixel perfect filling (you can trust me on this. If this code generate seams your geometry is broken). Tell me if it fixes your problem. If so - well - you have a reference to derive your polyfiller from (or be my guest and use my code).

To see some results you have to adjust the function "Section" to your bitmap format and change the blendmode from "overwrite color it with -1" to "add some constant like 16 to the pixel". This will give you a overdraw indicator. Pixels that are drawn more than once are brighter than those who are drawn just once. An important test feature that you should use frequently!

You should not see any of these double drawn pixels between edges, and you should not see untouched horizontal edges as well.

Let me know how it works out. Adding Texturing and Gouraud is easy. Getting the edges right everytime is not It took me over a year to finally get a perfect fill-rule.

Btw, every coordinate is 16:16 (as usual) and I don't do clipping. If you need it inside the polyfiller hack it into the section function.


Headerfile:

#ifndef __polyfill_hpp
#define __polyfill_hpp

typedef signed long             sS32;
typedef unsigned long           sU32;
typedef unsigned short          sU16;
typedef unsigned __int64        sU64;
typedef signed __int64          sS64;

struct Vertex
{
  sS32   x;   // 16:16
  sS32   y;   // 16:16
  sS32   yceiled; // 0.32
};

void MyPolygon (Vertex *vtx);

#endif

Source:

#include "polyfill.h"

// globals:
sU16 * ScreenBuffer;
int    ScreenPitch;

// statics:
static sS32 xLeft;
static sS32 xRight;
static sS32 dxdy_left;
static sS32 dxdy_right;


sS32 sDiv64Save(sS32 a,sS32 b)
//////////////////////////////
{
  if (b <=65536)
  {
    __int64 cc = 0x40000000/b;
	cc = (cc * a)>>14;
	int ret = (int)(cc&0xffffffff);
	return ret;
  } 
  __int64 aa = a;
  __int64 bb = b;
  aa<<=16;
  aa/=bb;
  int ret = (int)(aa&0xffffffff);
  return ret;
}

sS32  sMul64 (int a, int b)
////////////////////////////////////////
{
  __int64 aa = a;
  __int64 bb = b;
  __int64 cc = aa*bb;
  cc>>=16;
  return (int)(cc&0xffffffff);
}

void Section (int y1, int y2)
/////////////////////////////////
{
  for ( int y=y1; y<y2; y++)
  {
    int x1 = (xLeft  + 0xffff)>>16;
 	int x2 = (xRight + 0xffff)>>16;
	int fract = (x1<<16)-xLeft;
	for ( int x=x1; x<x2; x++)
	{
      ScreenBuffer[ScreenPitch*y+x] = -1;
	};
    xLeft  += dxdy_left;
    xRight += dxdy_right;
  }
}

void Setup_Left (const Vertex *a, const Vertex *b)
//////////////////////////////////////////////////
{
  int height  = b->y-a->y;
  if(height == 0) return;
  int  frac  = (a->yceiled<<16) - a->y;
  dxdy_left  = sDiv64Save (b->x-a->x, height);
  xLeft      = a->x+sMul64 (dxdy_left, frac);
}


void Setup_Right (const Vertex *a, const Vertex *b)
///////////////////////////////////////////////////
{
  int height  = b->y-a->y;
  if(height == 0) return;
  dxdy_right = sDiv64Save (b->x-a->x, height);
  xRight = a->x + sMul64 (dxdy_right, (a->yceiled<<16) - a->y);
}

void MyPolygon (Vertex *vtx)
////////////////////////////
{
  int top  = 0;
  int bottom = 0;
  int left  = 1;
  int right = 2;

  if (vtx[1].y < vtx[0].y)  
  { 
    if (vtx[2].y < vtx[1].y)  
      { top  = 2; left  = 0; right = 1; } 
	else 
      { top  = 1; left  = 2; right = 0; }
  } else {
    if (vtx[2].y < vtx[0].y)  
      { top  = 2; left  = 0; right = 1; } 
    else 
      { top  = 0; left  = 1; right = 2; }
  }
  if (vtx[1].y > vtx[bottom].y) bottom = 1;
  if (vtx[2].y > vtx[bottom].y) bottom = 2;
  vtx[0].yceiled = (vtx[0].y + 0xffff)>>16;
  vtx[1].yceiled = (vtx[1].y + 0xffff)>>16;
  vtx[2].yceiled = (vtx[2].y + 0xffff)>>16;
  if (vtx[top].yceiled == vtx[bottom].yceiled) return;
  Setup_Left  (&vtx[top], &vtx[left]);
  Setup_Right (&vtx[top], &vtx[right]);
  int middle = vtx[left].yceiled;
  if (middle > vtx[right].yceiled) middle = vtx[right].yceiled;
  Section (vtx[top].yceiled, middle);
  if (left == bottom) Setup_Right (&vtx[right], &vtx[bottom]);
  else Setup_Left  (&vtx[left], &vtx[bottom]);
  Section (middle, vtx[bottom].yceiled);
}

Btw, this code is the result of over 5 years of polyfiller tweaking and simplification. For me it's the mother of all trapezoid based triangle renderers.

Nils

Btw, the poly-filler above has drawn this (more than 30k polygons, with tons of degenrated and horizontal edges)

[Kackurot]

Hey Nils, Im pretty much doing the same thing... I quite don't understand why Im still getting cracks... It would be nice if some one else can take a look at my code, I ve been at this for 3 weeks now. So Nils, if you can help look at my code and maybe get a hint of what im doing wrong, Ill a preciate it. Maybe if you have aim/msn or send by e-mail or something?

[Nils Pipenbrinck]

feel free to send me the code. you'll get my email via p-mail.

[Nils Pipenbrinck]

Hi.

I tried to compile your code. My VS.NET crashes with an internal compiler error inside your fixed point template classes.

So I tried to get the new vs.net express, but that does not work either (blame my computer for that).

I've written a makefile for gcc/cygwin. That usually works out of the box. But it gives several hundrets of errors for your fixed point class as well *sigh*

So I'd say - first you'll fix your fixed point *g*, then I'll give it another try and take a serious look at it.

However, I did reviewed your poly-renderer, and as I've expected you don't have the special workaround for edges that are less than a pixel in height. This stuff *is* important.

To me, it seems it's sufficent if you just replace the calls to fixDiv by the sDiv64Save routine I've posted above. Do this inside the polyfiller, everytime you divide dx by dy (e.g. when you calculate the polygons edge-slope).

This should fix all those errors.

[Kackurot]

Hey, the reason why you can't compile is that you need vs 2003 - 2005 net, the lower versions of vs don't support the way I have my template set up. Its probably complaining about the missing of template arguments etc... In 2005 you don't have to specify template arguments in a template function that is inside of
the class name space. Anyway, I found out that my renderer was ok and could render high poly models with no cracks, it was actually my cull vertices's function that was making triangles cull out. I was capping the fractional part in the determinant of the computation of the edges. So I just made the final result in to 16.16 , but that lead into a problem of over flow when the triangle got to close to the near plane and got big, so the numbers over flowed, so I just shifted the delta of the edges over by 8 and then did the multiply and it got rid of that. Heres the results:




Take note that none of these models are using any z sorting. Yeah, so my renderer really rocks multiple bags of socks :P. So thank you Nils and Nick, you guys helped me a lot!