Improving the polygon routine...
Posted: Sun Sep 21, 2008 11:55 am
After turning around the problem in all directions, the only way I see that can lead to less flickering (due to the simulation of double buffering by drawing alternatively on odd and even lines) and better performance, is to draw all the pixels at the same time, without performing any overdraw (would flicker).
To do that, it means that I have to modify the polygon routine so the first phase just compute/collect all the data for each polygon, store that in some intermediate structure, and then draw it all in one go, from left to right, top to bottom.
The routine I'm using at the moment is very simple in it's principle. All I have is two tables, one called "min-x" and one called "max-x", which records the left and right extremities of each scanline in the triangle.
In BASIC this would be the equivalent of something like that:
Simple enough, isn't it ?
Now the problem is that when erasing and redrawing you just see an horrible clear/draw/clear/draw/clear/draw flickering effect, so a solution to that is to use the previous MIN/MAX values to erase only what needs to be erased, and draw only what needs to be drawn compared to what is already on the screen.
It works fine if you have only one polygon drawn. If you have many polygons, you still see them being drawn overlapped, so it's still ugly.
(and the fact that we are trying to achieve something visually nice, we have "dithering" on the polygons, used to simulate some shades of grey. And these values are different for each polygon because they depend of the orientation of the polygon toward the light source, etc... so just "completing the missing parts" is far from being trivial)
Assuming I can manage to find a way to store all the information necessary to display the next frame, it would be possible to have something like that:
The change here, is that instead of calling the drawing code for each triangle, we have all the information for all the triangles stored in the tables. And then we can draw from left to right and top to bottom, without any overlapping.
The issue here, is that if done correctly, the new code would be faster if there are more polygons, and many of them overlap, because the additional complexity would lead to less overdrawing (ie: less screen update), but it is very hard to achieve, mostly because of how to organize the data structure, and the memory consumption.
The existing code that draw triangle per triangle just uses the two 200 bytes tables minx and maxx (plus some additional tables that I use in all my graphic routines, so they don't count here as additional size).
The new code needs to be able to compute the information of each scanline of the triangle and insert that in some larger structure that contains the description of a complete scanline... and then it means that technically we may have to keep one segment for each triangle if they are all visible (up to 240 vertical triangles), and for each need to store the width of the segment, and the rendering pattern.
The big question is: How to store that so it fits the following criteria:
- Fits in memory
- Efficient to process when inserting segments
- Efficient to process when displaying
The most efficient speed-wise is to store a fixed structure with a pre-allocated amount of potential segments to draw. It also happens to be the less efficient memory wise.
I'm open to suggestions !
To do that, it means that I have to modify the polygon routine so the first phase just compute/collect all the data for each polygon, store that in some intermediate structure, and then draw it all in one go, from left to right, top to bottom.
The routine I'm using at the moment is very simple in it's principle. All I have is two tables, one called "min-x" and one called "max-x", which records the left and right extremities of each scanline in the triangle.
In BASIC this would be the equivalent of something like that:
Code: Select all
DIM MINX(200)
DIM MAXX(200)
FOR Y=0 TO 199 ' For each line
CURSET MINX(Y),Y,1
DRAW MAXX(Y)-MINX(Y),0,1
NEXT Y
Now the problem is that when erasing and redrawing you just see an horrible clear/draw/clear/draw/clear/draw flickering effect, so a solution to that is to use the previous MIN/MAX values to erase only what needs to be erased, and draw only what needs to be drawn compared to what is already on the screen.
It works fine if you have only one polygon drawn. If you have many polygons, you still see them being drawn overlapped, so it's still ugly.
(and the fact that we are trying to achieve something visually nice, we have "dithering" on the polygons, used to simulate some shades of grey. And these values are different for each polygon because they depend of the orientation of the polygon toward the light source, etc... so just "completing the missing parts" is far from being trivial)
Assuming I can manage to find a way to store all the information necessary to display the next frame, it would be possible to have something like that:
Code: Select all
DIM COUNT(200)
DIM MINX(200)
DIM WIDTH(200,999)
DIM STYLE(200,999)
FOR Y=0 TO 199 ' For each line
X=MINX(Y)
FOR I=0 TO COUNT(Y) ' For each segment
PATTERN STYLE(Y,I)
CURSET X,Y,1
W=WIDTH(Y,I)
DRAW W,0,1
X=X+W
NEXT I
NEXT Y
The issue here, is that if done correctly, the new code would be faster if there are more polygons, and many of them overlap, because the additional complexity would lead to less overdrawing (ie: less screen update), but it is very hard to achieve, mostly because of how to organize the data structure, and the memory consumption.
The existing code that draw triangle per triangle just uses the two 200 bytes tables minx and maxx (plus some additional tables that I use in all my graphic routines, so they don't count here as additional size).
The new code needs to be able to compute the information of each scanline of the triangle and insert that in some larger structure that contains the description of a complete scanline... and then it means that technically we may have to keep one segment for each triangle if they are all visible (up to 240 vertical triangles), and for each need to store the width of the segment, and the rendering pattern.
The big question is: How to store that so it fits the following criteria:
- Fits in memory
- Efficient to process when inserting segments
- Efficient to process when displaying
The most efficient speed-wise is to store a fixed structure with a pre-allocated amount of potential segments to draw. It also happens to be the less efficient memory wise.
I'm open to suggestions !