Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!


a 3d visibility solution for s-buffer of mine won't work

I've developed a genial method of determining which polygons' color should be used to draw using the s-buffer algorithm.
The problem is that something is wrong - either in the algorithm or in my program.
Could someone skilled in this area reply? Then I could specify the algorithm.


  • PropellerManPropellerMan Member Posts: 12
    Code, please!!!

  • The UltramageThe Ultramage Member Posts: 10
    I'll just explain it:
    When doing the s_buffer, it can happen that two polygons intersect (like 2 sides of a cube). Calculating depth won't work, because the 2 polys have the same depth at the questioned point.
    My solution goes:
    Find the second intersection of each polygon and the scanned line.
    Then, check the z value of each of them.
    The polygon whose second intersector's depth is lower is the closer one.
    So draw the x(i) - x(i+1) segment with that polygon's color.

    Try to draw some examples of polygons whose sides are intersecting.
    You'll see that it works.

    I tried to calculate the z coordinate by iteration (I know the z-s of the starting and the ending point of each side of each polygon), but it didn't seem to work.
    I think I even tried to brute-calculate the z and it didn't work.
    Example: I'm looking at two polygons that intersect. The problem is that when I rotate the eye a little, the engine first shows the first polygon, then the second, and so on.
    It seems that at some points, the algorithm doesn't take the last side of the polygon into account. Then it does. Then it doesn't.

    Try to find an error in my algorithm. If you didn't find it, I could post a screenshot of the problem if you wish.

    The Ultramage
  • Karl007Karl007 Member Posts: 27
    [b][red]This message was edited by Karl007 at 2002-10-16 23:55:50[/red][/b][hr]
    1) You should not need to check any z when it's an adjacency problem between two polygons on an edge. IF the two polygones share the same vertex coordinates and use the same transformation pipeline. Because the left (thin) edge for P1 and right (thin) edge for P2 are the same. So this edge should clearly define which pixels project on P1 or P2. Like this :


    2) Even tho how do you compute z ?

    I suspect you do this 3D lamer approximation : you must not linearily interpolate z on your edge ! That's false. You have to consider the discrete position of the first pixel drawn.

    For instance :
    On the edge (infinitely thin) : x=0.1 y=0.5
    First pixel coordinate : x'=0.5 (first pixel) y=0.5
    Consider here that 0.5 0.5 is the coordinate of the top left pixel of the screen.

    As there is a 0.4 difference between x and x', z(x,y)<>z(x',y)

    That's so OBVIOUS !

    If you want compute an efficient 1/z (or 1/w) value for (inverse) depth comparison on the starting pixels of a Bresenham line, I have found a very nice trick. It looks like that in C.

    When persp correction is taken :
    1/w, u/w, v/w (w homogenous coordinate) are linear gradients in x,y :
    1/w = a*x + b*y + c;

    x_frac+=xinc_frac; // a 1.31 fixed point value
    bit = xfrac>>31; // bit is 0 or 1
    // in asm one could use a add adc sequence to get this overflow bit.

    oow += oowStep[bit]; // fixed point arithmetic
    uow += uowStep[bit];
    vow += vowStep[bit];

    // Only 1 addition (1 cycle) per line start and mapped coordinate used.

    3) Its maybe time for you to forget about s-buffers and so on. These techs were used 8 years ago, ... unless you absolutely need an optimized software 3D engine. Then I am a well of science about these questions if you need more and even some code samples.

Sign In or Register to comment.