gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Graphics > Rendering semi transparent polygon scenes with z-buffering

#114348 - keldon - Sun Jan 07, 2007 12:45 am

Tagline: by rendering semi transparent polygon scene with z-buffering I mean a typical scene with many polygons where polygons (or even the textures) have variable transparency!

This is my understanding of how it is (or can be) achieved.
---
First draw the solid polygons and keep the z buffer. Any pixel drawn from a semi transparent polygon behind an already drawn pixel is ignored!

What I will describe first is how you render each pixel. You do it in this order:
- retrieve semi transparent texel
- sort texels by z,
- draw texels in order using semi transparency

Now at this stage it seems stupid to think of sorting your texels for every pixel, and you are too right. Unless you are drawing a mass intersection of semi transparent polygons you are rarely ever going to see more than two polygons cross each other in any one pixel, and you will not see many crosses per line! So your sort code can be very simple. [By the way] it is best to have an already sorted list and only fix the order when there is a problem.

Drawing each pixel
Code:
pixel.setColour ( getPixel(x,y));
for (Cell <Texel> tCell = drawingPolys.head.next; tCell != null; tCell = tCell.next ){
   Texel texel = tCell.element;
      
   boolean hasCollided;      
   if (hasCollided = pixel.add(texel.colour, texel.alpha, texel.z)){
      // swap two texels
      Cell <Texel>prevTexel = tCell.prev;
      tCell.element = prevTexel.element;
      prevTexel.element = texel;
      
      // will revert back to previous pixel state and previous cell
      pixel.undo();
      tCell = tCell.prev;
   };
               
               

}
setPixel(x,y,pixel.colour,pixel.z);


(*EDIT*)code has been altered

Now this might seem very costly; but consider pixel.add only returns false if the texel is found to be behind something drawn already (excluding the existing background). And since there is only one pixel object instantiated, you can have make use of one with multiple levels of undo! Also note that there are rarely a large number of pixels where intersections between polygons occur so it is best to write the method in a way

Drawing each line
Before reaching the stage where we are able to draw pixels we need the texels from each semi transparent polygon. Well each polygon has the following information stored that would be required:
- x/y s,u and 1/z deltas for polygon's texture map to update for next pixel
- s,u and 1/z for each polygon's texture map at current pixel
- (*EDIT*)minx and maxx for each row

Each semi transparent polygon records maxx andminx, s,u and 1/z for the beginning of each line. This can be maintained without memory allocation 'woes' through obvious costless memory management schemes.

Adding and removing semi transparent polygons to and from the pipeline
For adding and removing polygons you need only do the following:
- for each row store a boolean map of which polygons begin/end on this line
- do the same [independantly] for each column

This might seem cumbersome at first, but you can make use of storing the two boolean map inside an integer(or array of integers) and simply performing a bitwise AND. A non zero value tells you that an element needs to be examined. This will happen no more than two times for each polygon being drawn.
---
I am sure there are plenty of different ways that you can draw many semi transparent textured polygons in software, but I wonder if this method is any good and where it stands in comparison to the rest; and most importantly whether there has been a flaw in my thinking. I have been wondering how to do it efficiently for a while now, and for some reason this idea came to mind now!

EDIT: Changed title and added tagline

Last edited by keldon on Sun Jan 07, 2007 5:09 pm; edited 1 time in total

#114380 - keldon - Sun Jan 07, 2007 11:30 am

*UPDATE*
It I have a test version of this to work, only problems are overlapping pixels within the two 3side polygons from your 4side face. But when I get back from church I will look into handling the overlapping pixels and then load a scene to see it work on a proper model.

#114403 - keldon - Sun Jan 07, 2007 4:09 pm

It has become apparent that drawing edges twice is a problem for any object, but there is a 'fairly' low-cost solution. Store the following data for each edge (note I said edge):
- int drawnCount[screenWidth]
- int getX(y)

Again this array need not be created for every edge and instead is allocated once and each frame an edge sets its array to point to one of them. GetX need not be a function, the y could be stored for each row.

EDIT: The miny and maxy will also have to be stored

The array must be zeroed at the end of each line; this is my method for doing it:
Code:
// deciding whether texel is drawn
boolean isDrawingEdge = (x == minx[y] || x == maxx[y] || y == miny[x] || y == maxy[y]);
if ( isDrawingEdge ) {
   for-each ( Edge edge: texel.edges ) {
      if ( edge.getX(y) == x) edge.drawCount[x]++;
      if ( edge.drawCount[x] > 1 ) texel.drawPixel = false;
   }
}

// drawing texel
if ( texel.drawPixel ) drawPixel();

// clearing drawCount;
if ( isDrawingEdge ) {
   for-each ( Edge edge: texel.edges ) {
      if ( edge.getX(y) == x) edge.drawCount[x]--;
   }
}


One major concern is how to associate to the same edge. Many people will be using the vertexArray/vertexIndex method; but you can map one vertexIndex to another in many ways. An array [for example] could be created, and when drawing the polygons we need only consider the vertexIndex's of the two points.

An alternative arrangement is to keep track of the minx,miny,maxx,maxy for both pixels and Edges. So you would have int minx[]; and Edge minx[]. Each polygon that is being drawn already keeps track of minx and maxx, but this method reduces the need to look through the list of edges and instead allows Edge to only store the drawCount.
Code:
// deciding whether to draw
boolean isDrawingEdge = true;
if (minx[y] == x && minxEdge[y] != null ) {
   minxEdge[y].drawCount[x]++;
   if ( minxEdge[y].drawCount[x] > 1 ) texel.drawPixel = false;
}

if (maxx[y] == x ) {
   maxxEdge[y].drawCount[x]++;
   if ( maxxEdge[y].drawCount[x] > 1 ) texel.drawPixel = false;
}

if (miny[x] == y ) {
   minyEdge[x].drawCount[x]++;
   if ( minyEdge[x].drawCount[x] > 1 ) texel.drawPixel = false;
}

if (maxy[x] == y ) {
   maxyEdge[x].drawCount[x]++;
   if ( maxyEdge[x].drawCount[x] > 1 ) texel.drawPixel = false;
}

// drawing texel
if ( texel.drawPixel ) drawPixel();

// clearing drawCount
if (minx[y] == x )minxEdge[y].drawCount[x]--;
if (maxx[y] == x )maxxEdge[y].drawCount[x]--;
if (miny[x] == y )minyEdge[x].drawCount[x]--;
if (maxy[x] == y )maxyEdge[x].drawCount[x]--;


p.s. excuse the terminology with texel's, it is not correct but I cannot think of another viable name. And I will not deal with implementing semi transparent polygon without overdrawing edges just yet. And I wonder if anything interesting can be done on the GBA with this if it is not too slow.

#114897 - keldon - Thu Jan 11, 2007 11:42 am

Well it is all working.

From now on polyRef refers to an object containing the xDeltas, a reference to the next lineGradient and when to change. Line gradient is the line gradient, storing details so that we can draw the left and right of the line and also update the uv position of the texture map. insertList refers to the list the polyRef's wait in before being added to the drawingList, which are the polyRef's currently being drawn (and sorted).

First of all I have dealt with semi-transparenty polygons and a lot of the data can be reduced big time!
- min/max int/edge arrays can be removed
- no need for getX(y)
- drawnCount need not be an array as you will only ever visit this method once per pixel for each edge
- no need for pixel undo, store the current rgba value with the polyRef

In short it is nothing more than a typical texture mapper where the list of polyRef's are sorted each pixel at a low cost. The algorithm performs sorting while rendering pixels and only considers polygons projected on that particular pixel in an efficient manner.

Inserting polyRef's into the drawingList could be costly for two reasons. On each line we need to know when to add them, and the polygon will also need to be in the right rendering order. But there is a work around for this too to reduce the load of it. Consider first that for each pixel when we are adding a new polyRef we prepare for it in the previous pixel. So there will be a list of polyRefs that are to be added in the next pixel (called an insertList), if this list is ordered then when we are updating the deltas of the polyRef's being rendered this pixel (that are not to be removed as they have reached then end of their line) we also insert in the polyRef's for the next pixel.

When we add a polyRef to the list to be drawn, we also use its lineGradient to insert it into the correct insertList on the next line. This way we only need to keep two lists, one for the current line and one for the next. Now the insertLists can also be per pixel. There are two ways about this, one is to have it as an explicit list; second is to give a link to one polyRef and the polyRef could provide links to the next one.

If you hadn't noticed polyRef's are only being added to the insertList for the next line when they are being placed on the drawingList. Now we need to consider the first time that the polyRef is placed into this world. This method may be crucial. Consider first that no matter what we do we are going to have _x amount of polyRef's in this frame already. The number of polyRef's being loaded will be equal to the number of 3pointPolygons being rendered. Here are a number of approaches:
- 1: single array of the polyRef's followed by a boolean map of when they enter (one for x, one for y, and the two...)
- 2: a list stored for each line; at the beginning of each line we add them to the insertList for the corresponding pixel
- 3: just go straight for the pixel; which means we have a list of polyRef's the size of the screen! well it's a thought

Adding the polyRef's for the first time might take some thinking