Rasterization using half-space functions

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 10, 2004 at 11:08

Hi all,

I have a little problem with a new rasterization algorithm…

Rasterization of triangles is usually done using scan conversion, but I recently discovered a more advanced approach: Triangle Scan Conversion using 2D Homogeneous Coordinates. I actually knew that paper for quite some time, but never really understood the advantages. What they do is simply scan through the bounding rectangle of a triangle, and for each pixel determine whether it is inside the triangle. For each edge of the triangle, a ‘half-space’ function is computed, which is positive on the inside of the triangle and negative on the other side. So when all three are positive, the point can be drawn. The implementation is surprisingly efficient, because the formula can be evaluated incrementally for every pixel. It’s also easy to determine whether a block of pixels is (partially) covered by the triangle or not.

So it turned out to be really useful for processing pixels in parallel. More specifically, I can now have ‘quad’ pipelines. They process 2x2 pixels using MMX and SSE instructions. The half-space functions very conveniently provide a mask that can be used to determine which of the four pixels has to be written to the screen.

Now the problem… When a pixel is on the edge of a polygon, the half-space functions are neither positive or negative, they are zero. But there are quite strict rules to determine whether such a pixel should be drawn or not. DirectX and OpeGL have the top-left convention: Rasterization Rules. These rules are very important to avoid gaps between triangles and drawing pixels on the edges twice.

So, does anyone have an idea how to implement the fill convention for the half-space functions algorithm? It’s obviously inefficient (and quite complex) to check whether to use > or >= for every edge, for every pixel. Ideally I would like to handle this in the setup stage, like shifting the edges slightly. But this does not work correctly either. I don’t think it’s easy to solve, but all ideas are welcome!

11 Replies

Please log in or register to post a reply.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 10, 2004 at 12:11

Here’s another (simpler) page explaining the half-space functions: Rasterizing Triangles. Unfortunately it doesn’t deal with correctly implementing the fill convention. I also found this: Implementing Top-Left Fill Convention in Direct3D Drivers. But as you can see the page is empty, and I can’t seem to find the original…

6ad5f8c742f1e8ec61000e2b0900fc76
0
davepermen 101 Sep 10, 2004 at 12:25

interesting algorithm.. i’d guess you can quickly cull out large blocks of invisible pixels with some sort of subdivision, or something..

about the edge-convention.. dunno, would shift all of them half a pixel up left be enough to hit the right ones? i guess no.

subdivision would help again, as you’d determine the edge bether..

but i have no clue for now else.. sorry. i’ll think about it.

3c6597370b476903ed475f70b4b3ce31
0
john 102 Sep 10, 2004 at 13:49

I believe the method you’re trying to use (half-space functions) is efficient, but in terms of fill-rate, it’s an overkill (Correct me if I’m wrong).

So you have successfully implemented rasterization using half-space functions? I’m interested in knowing (in detail) the approach you took and how efficient your algorithm is.

The way I see it is, what you do in hardware doesn’t mean you can do in software; so the approach you took is very good (i.e. you seem to take a different approach to hardware).

As for the problem you’re having, have you considered trying to apply for simple intersection calculation to determine that?

You have really got me interested in this now. I’m eager to test some things with my s/w renderer related to your problem.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 10, 2004 at 14:19

@davepermen

interesting algorithm.. i’d guess you can quickly cull out large blocks of invisible pixels with some sort of subdivision, or something..

Exactly. With this approach I can finally implement an advanced overdraw reductuction algorithm!

about the edge-convention.. dunno, would shift all of them half a pixel up left be enough to hit the right ones? i guess no.

Indeed that won’t work, as there are now other pixels that will hit the edge. Fundamentally it just has to determine whether a pixel on the edge has to be drawn or not. If that decision could be made by adjusting the half-space functions that would be excellent, but I’m afraid it won’t work…

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 10, 2004 at 14:44

@john

I believe the method you’re trying to use (half-space functions) is efficient, but in terms of fill-rate, it’s an overkill (Correct me if I’m wrong).

Overkill? In what sense?

So you have successfully implemented rasterization using half-space functions? I’m interested in knowing (in detail) the approach you took and how efficient your algorithm is.

I first determine coverage per 8x8 block. If it is not covered, it is simply skipped. If it is fully covered, it gets passed to the pixel pipeline in whole. If it is partially covered, an unrolled loop computes an 8x8 mask.

Performance is really good. The half-space functions are easy to compute so the setup cost is low. This benefits small polygons. Big polygons are efficient as well, because they have a lot of 8x8 blocks that are totally not and fully covered. My half-space functions use fixed-point calculations because this is faster. The current C++ implementation is slightly faster than the C++ implementation of the classical scanline algorithm for small polygons, but a bit slower for big ones (unless I use 16x16 blocks). I expect this situation to change when I implement it in assembly, because the compiler misses a lot of optimization opportunities and these operations are ideal for MMX and SSE.

When I got this issue fixed, I will post the C++ version here on DevMaster…

As for the problem you’re having, have you considered trying to apply for simple intersection calculation to determine that?

Intersection calculation? :huh: I can’t see how that would solve things.

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 10, 2004 at 22:11

I solved it.

One small observation I made is that for the top-left fill convention there is either one or two top-left edges. These edges would use the >= comparator to test whether pixels are on the inside of the half-space. The other edge(s) use the > comparator. Another observation is that the order of the edge functions doesn’t matter. The point has to be on the (strictly) positive side of each edge individually to be in the triangle, it’s that simple.

So there can only be two situations:

if(half-edge1 >= 0 && half-edge2 >= 0 && half-edge3 > 0) {pixel inside}

or

if(half-edge1 >= 0 && half-edge2 > 0 && half-edge3 > 0) {pixel inside}

By swapping edge equations, we can make sure the top-left ones use the >= comparators and the other one(s) use the > comparator. It’s that simple. It requires a bit of extra work to detect the top-left edges, and to use the correct inner loop for partially covered 8x8 blocks, but that’s it. Perfectly implemented fill convention, with nearly no overhead.

I’m going to perfect this algorithm and then post it here…

3c6597370b476903ed475f70b4b3ce31
0
john 102 Sep 11, 2004 at 03:39

wow, impressive work. It’s nice to see such an advanced topic getting discussed here as well as having advanced members such as you Nick. All what devmaster needs is more Nicks :)
Please do post your algorithm after you perfect it; you got me interested in this.

254754b37f468a2926bffcd83bbbf1fa
0
z80 101 Sep 11, 2004 at 08:20

Inspires me as well, I must say. I have recently been thinking about writing a software renderer (its been a few years since last time – or more like 5 years). Perhaps for GBA or something like that and this algorithm comes handy. I had been thinking about how to raster triangles for a few days when this thread came up. Perfect timing Nick :-)

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 11, 2004 at 09:54

I’m a moron. :D

There’s a much simpler solution. The statement x > 0 is true for strickly positive x. To make it true for zero as well, it suffices to just add 1 to x beforehand. This is then equivalent to x >= 0. It’s so trivial that I feel stupid I didn’t see this before.

What I tried before starting this thread was slightly shifting the edge. But this caused more pixels to be drawn than just the ones on the edge (where the half-edge equation is zero). So to do it correctly, I have to adjust the half-space function itself, simply by adding 1.

This is so damn elegant and fast, I’m starting to wonder why I ever used scanlines…

99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Sep 11, 2004 at 18:09

I submitted the final code as a Code Spotlight…