special case polygon rasterizing problem

[peterbone]

My software renderer has a problem sometimes rasterizing polygons and missing pixels - creating holes. It happens when the polygon is edge on to the viewpoint but part of a continuous surface. Here's a visual example

http://img.photobucket.com/albums/v424/peterbone/raster_problem.gif

It only happens when the polygon is edge on because if it was slightly facing the camera it would be rendered and if it was slightly facing away then the faces behind that are part of the surface would cover up the holes.

Has anyone else experienced this problem? Can it be fixed with a simple correction to my rasterizing algorithm or do I need to write extra code for this special case?

Thanks

Peter Bone

[jirzynek]

rounding errors? (try subpixel accuracy maybe it will help you)


j

[peterbone]

I have sub-pixel accuracy. There are no rounding errors. Elsewhere the triangles join up perfectly with no overlaps and no holes. This is just a problem with faces edge on to the camera.

[Nick]

When backface culling, don't compare to zero but use a tiny value (commonly called 'epsilon'), like 0.001. So triangles facing away from the camera only very slightly (that actually do face the camera because of floating-point inprecision) do get passed to the rasterizer. It's then the rasterizer's responsability to cull away the falsly accepted triangles (most rasterization algorithms don't render anything with a negative winding order, like the half-space method (http://www.devmaster.net/codespotlight/show.php?id=17)).

[peterbone]

Thanks but that didn't seem to make any difference. It still happens even if I turn backface culling off. The polygon is being sent to be rasterized but no pixels are being drawn because it has such a low thickness. I suppose this is just something wrong with my rasterizing algorithm that needs fixing.
I may just re-write my rasterizers using that half-space method you wrote. I wish I knew about that when I was writing my rasterizer.
Thanks

[karligula]

Are you using an inclusive fill on the edges? If you use an exclusive fill that can sometimes miss the odd pixel here an there.

[peterbone]

Thanks karligula but I havn't come across that term before. Can you please describe what exclusive fill is or point me somewhere on the net.

[Nick]

Thanks karligula but I havn't come across that term before. Can you please describe what exclusive fill is or point me somewhere on the net.
What he means is what should happen when a pixel is on an edge. Inclusive fill will render them all, exclusive fill rejects them. Exclusive fill can result in gaps between polygons, while inclusive fill won't.

But inclusive fill isn't the answer, because when you do transparency you want the pixels on edges shared between polygons to be rendered exactly once. One way to do this is to use the top-left fill convention also used by Direct3D and OpenGL. It's all in my advanced rasterization (http://www.devmaster.net/codespotlight/show.php?id=17) article how to implement this.

[peterbone]

ok, I have exclusinve fill. I'm not doing transparency but I think it's better to render the edge pixels once if only to make it slightly quicker. So are missed pixels unavoidable with exclusive filll?

[Reedbeta]

Just use the top-left fill convention (or you can use a bottom-right fill convention if you choose...) and the edge pixels will be rendered exactly once no matter what.

[peterbone]

But Karligular said

Are you using an inclusive fill on the edges? If you use an exclusive fill that can sometimes miss the odd pixel here an there.

Using a top left fill conversion is an exclusive fill.

Does anyone know where I can find source code for the basic scanline conversion algorithm for a triangle? It's amazing that I can't find any on the internet.

[Mattias Gustavsson]

have a read through chris heckers rasterization articles, they explain it all.

http://www.d6.com/users/checker/misctech.htm

[jirzynek]

try to find two text files fatmap.txt and fatmap2.txt (fast affine texture mapping), and maybe some articles by Tom Hammersley could help you http://tfpsly.free.fr/Docs/TomHammersley/

[Nick]

Using a top left fill conversion is an exclusive fill.
No it's not. And it's neither an inclusive fill.

The top-left fill convention will render pixels that are on a left or top edge, and skip pixels that are on a right or bottom edge. This way whatever mesh you render the pixels between polygons will be rendered exactly once.

Top-left fill convention is the accepted standard and used by Direct3D and OpenGL. Chris Hecker's articles also use a strict top-left fill convention.

Subpixel accuracy, subtexel accuracy and the fill convention are the first things that separate a sOftWarE rEndeRER from a Software Renderer.

[peterbone]

oh right. I see now. Exclusive fill doesn't render any edge pixels.
I think mine is still a sOftWarE rEndeRER despite having subpixel accuracy and a top left fill convention.
Here it is in it's simplest form http://atlas.walagata.com/w/peterbone/triangle_raster.txt

[Nick]

oh right. I see now. Exclusive fill doesn't render any edge pixels.
I think mine is still a sOftWarE rEndeRER despite having subpixel accuracy and a top left fill convention.
Here it is in it's simplest form http://atlas.walagata.com/w/peterbone/triangle_raster.txt
I see you're using the floating-point vertex coordinates directly. This causes some precision problems because subtraction and multiplication unavoidably loose precision. The only solution is to use integer fixed-point numbers. Both my rasterization article and Hecker's articles use fixed-point.

[peterbone]

ok, I don't think that's what's causing the problem because it's only happening on these single pixel thickness polygons but I was intending on doing that anyway for speed up so I'll see it it helps.