Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a set of vertices in 3D space, and for each I retain the following information:

  • Its 3D coordinates (x, y, z).
  • A list of pointers to some of the other vertices with which it's connected by edges.

Right now, I'm doing perspective projection with the projecting plane being XY and the eye placed somewhere at (0, 0, d), with d < 0. By doing Z-Buffering, I need to find the depth of the point of a polygon (they're all planar) which corresponds to a certain pixel on the screen so I can hide the surfaces that are not visible. My questions are the following:

  1. How do I determine to which polygon does a pixel belong to so I could use the formula of the plane which contains the polygon to find the Z-coordinate?

  2. Are my data structures correct? Do I need to store something else entirely in order for this to work?

I'm just projecting the vertices onto the projection plane and joining them with lines based on the pointer lists.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

You will need an active edge list, which contains a list of all polygon edges intersected by the current scanline. You will also need an in/out flag for each polygon on the scanline. The flags are toggled on/of as you cross an edge for a polygon.

The rules are drawing for each pixel along a scanline are;

  1. no polygon flags are 'in', then draw background
  2. only one polygon flag is 'in', the draw the colour of that polygon
  3. two or more polygon flags are 'in', use you plane equation to find out which is closest at that pixel position.
  4. as we move onto the next pixel check the AEL (see below) to see if we are crossing an edge. if so toggle the appropriate flag.

enter image description here

An important component in the data structure needed for this algorithm is the edge node. Each edge in the polygon is represented by an edge node. An edge node contains the following information;

  1. yupper , the y co-ordinate of the upper end-point of the edge.
  2. ylower , the y co-ordinate of the lower end-point of the edge.
  3. xint , initially the x co-ordinate of the lower end-point of the edge. As the algorithm progresses, this field will store the x co-ordinate of the point of intersection of the scan-line.
  4. ym , the reciprocal of the slope of the line ( 1/m ).
  5. link to the polygon which own the edge.

When constructing an edge node for the edges, the following must be taken into account;

  1. Horizontal Edges are ignored (an edge node is not generated for these), these edges will be drawn when the adjacent edges are processed.
  2. If two edges share a vertex AND the vertex is an upper end point for one edge and a lower end point for another edge, the yupper of the lower edge must be reduced by 1. this is to allow the in/out toggle to work correctly.

enter image description here

In the above image the very top scanline intersects to edges at the top of the triangle. the two edges cause it to toggle from "out" to "in" to "out", which is correct. However, the second line also intersects two edges and is toggled "out" which is incorrect. The solution is to lower the y-int of the lower edge in this case. Now teh scan line only intersects one edge at the vertex.

This adjustment will not have any effect on the shape of the triangle as the xint will be used to determine where to start drawing. The effect of lowering the vertex is to cause it to be removed one scanline earlier than it would otherwise. All this assuming you are scanning from bottom to top.

Most implementations maintain an Active edge list (AEL), a list of edges. which contains all the edges intersected by the current scan line. The AEL needs to be maintained as we move from on scan-line y to the next scan-line (y+1) ;

  1. Add any edges whose ylower is equal to y .
  2. Colour the pixels along the scanline as described above
  3. One or both of the edges in the AEL will no longer be intersected by (y+1) . Remove the edges from the AEL, where yupper is equal to y .
  4. The intersection point of the scan line with the remaining edges will change for the new scan-line. xint is updated to xint+ym . Note that xint must be stored as a real number to avoid round-off errors.
  5. increment y (to the next scan line)
  6. Repeat until the last scanline is drawn.
share|improve this answer
    
Thank you very much for your reply, but I still don't understand how to handle partially visible polys. For example, in the picture, the poly on the upper left (the light blue one) has most of its edges off-screen. How do I set its 'in' flag so I don't paint with the background color? –  Belgin Oct 19 '12 at 13:05
    
I should have mentioned that prior to applying the scanline HSR method. The polygons are usually y clipped using a clipping algorithm (en.wikipedia.org/wiki/Clipping_(computer_graphics)). So that all the polys lie INSIDE the viewport. –  Ken Oct 19 '12 at 13:33
    
One last thing, sorry if I'm annoying. I'm trying to render an icosahedron and at a certain scan line I get 5 edges with the same xInt so strange results arise. Decrementing yUpper by 1 does not work because then some polys never get out of the 'in' state. What do you suggest I do? –  Belgin Oct 31 '12 at 19:17
    
not sure about your icosahedron, but I updated the answer to include more detail about why we lower the y-upper of the lower edge. If you're still stuck, maybe you can ask a new question about your specific problem –  Ken Oct 31 '12 at 19:58
    
Just one small thing: in this picture, the scanline (red) intersects that vertex at the top. In an icosahedron each edge has 2 incident triangles. From edge a, only one incident triangle is visible, the other one is in the back. Same for edge d. Now, as we go from a to d, this happens: the poly behind poly 1 and poly 1 are set 'in', then 2 is set in and 1 is 'out', then 3 is set 'in', 2 is 'out' and finally 3 is 'out' and the one behind it is set 'in', which is not the desired behavior. How do process the edges in the AEL so the right polys are set 'in'? –  Belgin Nov 1 '12 at 18:48

Ken's addressed scanline rendering (well) but not the occlusion problem.

So... you are asking about partially visible polys. That is where the beauty of combining scanline rendering with the z-buffer comes in.

(Using the formula of a plane to determine the depth at a given coordinate, like raycasting through every individual pixel, is unnecessarily complex and costly. Avoid that.)

Instead:

  1. Determine a list of all onscreen triangles.

  2. Transform the vertex by multiplying it by the projection matrix. This gives you depth at that vertex, and store that value in your depth buffer (and in a separate "vertex depth" buffer -- see my answer to your other question).

  3. For each set (triangle) of 3 vertices, perform linear interpolation between the vertices to get the depth value for each intervening pixel, and store that value in your depth buffer.

Once you've done this z-buffer part, you will no longer need to concern yourself over edge sorting for potential occlusion. In essence, the output of what I have described above is what you will use as the input to the step that Ken describes. The z-buffer, existing as a maximum-resolution quantisation of the display surface (i.e. the screen), can accommodate for any full or partial occlusion with the highest accuracy possible -- this being resolution of the screen itself, leading to no possible depth discrepancies in the final output. PS. In software, continuous geometric approaches may be cheaper depending on scene complexity, with the z-buffer being more expensive (being a discrete / iterative approach) but still much easier to implement.

This is why hardware z-buffering is favoured: It is both conceptually simple and very fast when implemented in hardware.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.