dovkruger

10-19-2006, 08:10 AM

In a previous posting, I asked how to efficiently draw a grid where x,y are constant, and some boxes are missing. This post is similar in purpose, but for a different algorithm.

I have an Arakawa C-grid that I wish to plot. The x,y is known at each corner, and from that the center can be computed. The value of the box is given at the center:

+-----+

| |

| 5 |

| |

+-----+In order to smoothly shade the surface, there are two choices: Gouraud shade from the centers, or from the corners. I elected to do it from the corners because it was simpler:

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+this turns into:

+-----+-----+-----+

| | | |

| | | |

| | | |

+----7.5---7.5----+

| | | |

| | | |

| | | |

+----7.5---7.5----+

| | | |

| | | |

| | | |

+-----+-----+-----+Which is ugly, ie features of size 1 box get smoothed away. The problem with doing it the other way is all the edge conditions where the grid does not exist:

+-----+-----+-----+

| | |*****|

| 5 | 10 |*****|

| | |*****|

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+

| | | |

| | | |

| | | |

+-----+-----+-----+Gouraud shading the quads that all exist are easy, but then around the missing corner, I would need more quads with an irregular algorithm, where I have to interpolate to centers and corners, and construct half and quarter-sized boxes:

+-----+---10--10

| | |

| | 10 10

| | |

+-----+---10--7.5--5--5

| | | |

| | 10 7.5 5 5

| | | |What I do instead currently is split each cell that does exist into 8 pieces, draw 8 gouraud-shaded triangles, which not only preserves the centers, it is a better interpolation that Gouraud, and therefore looks better. However, I would like to draw the triangles in a single draw command. I am currently drawing them one by one which is obviously slow. Given that some boxes are to be drawn, and some are not, could anyone identify both with and without shaders, how I can efficiently draw them? With shaders, of course I can send a vector of x,y,z,color, and mask, and let the shader sort it out, but not everyone has that capability, so I would like to have a fast solution for those with older card/driver combinations as well.

Here's a diagram of the current scheme for drawing one box:

+--------|--------+

|\ | /|

| \ | / |

| \ | / |

| \ | / |

| \ | / |

| \ | / |

| \ | / |

| \|/ |

+--------+--------+

| /|\ |

| / | \ |

| / | \ |

| / | \ |

| / | \ |

| / | \ |

| / | \ |

|/ | \|

+--------|--------+The problem is that I cannot think of an efficient way to lay out the points. If I use a triangle fan, then each box has to be an individual fan. A triangle strip has the problem that I always seem to end up in the wrong place. Perhaps this is some kind of Hamiltonian path problem to which there is no solution, but surely someone out there has a better way of doing this?

See below, that at 7/11 or 8, for a strip of boxes (in this case 2), I run into a problem that the next triangle I want is going to be non-adjacent.

+--------|--------+--------|--------+

|\ | /|\ | /|

| \ | / | \ 8 | 9 / |

| \ 4 | 5 / | \ | / |

| \ | / | \ | / |

| \ | / | \ | / |

| \ | / | 7 \ | / |

| 3 \ | / 6 | \ | / 10 |

| \|/ | \|/ |

+--------+--------+--------+--------+

|\ | /|\ | /|

| \ 2 | 3 / | \ 6 | 7/11/ |

| \ | / | \ | / |

| \ | / | \ | / |

| \ | / | \ | / |

| 1 \ | / 4 | 5 \ | / |

| \ | / | \ | / 8 |

| \|/ | \|/ |

+--------+--------+--------+--------+

I have an Arakawa C-grid that I wish to plot. The x,y is known at each corner, and from that the center can be computed. The value of the box is given at the center:

+-----+

| |

| 5 |

| |

+-----+In order to smoothly shade the surface, there are two choices: Gouraud shade from the centers, or from the corners. I elected to do it from the corners because it was simpler:

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+this turns into:

+-----+-----+-----+

| | | |

| | | |

| | | |

+----7.5---7.5----+

| | | |

| | | |

| | | |

+----7.5---7.5----+

| | | |

| | | |

| | | |

+-----+-----+-----+Which is ugly, ie features of size 1 box get smoothed away. The problem with doing it the other way is all the edge conditions where the grid does not exist:

+-----+-----+-----+

| | |*****|

| 5 | 10 |*****|

| | |*****|

+-----+-----+-----+

| | | |

| 5 | 10 | 5 |

| | | |

+-----+-----+-----+

| | | |

| | | |

| | | |

+-----+-----+-----+Gouraud shading the quads that all exist are easy, but then around the missing corner, I would need more quads with an irregular algorithm, where I have to interpolate to centers and corners, and construct half and quarter-sized boxes:

+-----+---10--10

| | |

| | 10 10

| | |

+-----+---10--7.5--5--5

| | | |

| | 10 7.5 5 5

| | | |What I do instead currently is split each cell that does exist into 8 pieces, draw 8 gouraud-shaded triangles, which not only preserves the centers, it is a better interpolation that Gouraud, and therefore looks better. However, I would like to draw the triangles in a single draw command. I am currently drawing them one by one which is obviously slow. Given that some boxes are to be drawn, and some are not, could anyone identify both with and without shaders, how I can efficiently draw them? With shaders, of course I can send a vector of x,y,z,color, and mask, and let the shader sort it out, but not everyone has that capability, so I would like to have a fast solution for those with older card/driver combinations as well.

Here's a diagram of the current scheme for drawing one box:

+--------|--------+

|\ | /|

| \ | / |

| \ | / |

| \ | / |

| \ | / |

| \ | / |

| \ | / |

| \|/ |

+--------+--------+

| /|\ |

| / | \ |

| / | \ |

| / | \ |

| / | \ |

| / | \ |

| / | \ |

|/ | \|

+--------|--------+The problem is that I cannot think of an efficient way to lay out the points. If I use a triangle fan, then each box has to be an individual fan. A triangle strip has the problem that I always seem to end up in the wrong place. Perhaps this is some kind of Hamiltonian path problem to which there is no solution, but surely someone out there has a better way of doing this?

See below, that at 7/11 or 8, for a strip of boxes (in this case 2), I run into a problem that the next triangle I want is going to be non-adjacent.

+--------|--------+--------|--------+

|\ | /|\ | /|

| \ | / | \ 8 | 9 / |

| \ 4 | 5 / | \ | / |

| \ | / | \ | / |

| \ | / | \ | / |

| \ | / | 7 \ | / |

| 3 \ | / 6 | \ | / 10 |

| \|/ | \|/ |

+--------+--------+--------+--------+

|\ | /|\ | /|

| \ 2 | 3 / | \ 6 | 7/11/ |

| \ | / | \ | / |

| \ | / | \ | / |

| \ | / | \ | / |

| 1 \ | / 4 | 5 \ | / |

| \ | / | \ | / 8 |

| \|/ | \|/ |

+--------+--------+--------+--------+