PDA

View Full Version : Efficient drawing of a staggered grid

dovkruger
10-19-2006, 07: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 |
| \|/ | \|/ |
+--------+--------+--------+--------+

ZbuffeR
10-19-2006, 08:05 AM
If you want true bilinear interpolation instead of gouraud, why don't you sample your colors from a texture instead ? that way you simply draw your strips as you want, and interpolation will be much better.

dovkruger
10-19-2006, 08:31 AM
Can you elaborate? I don't understand what you're proposing.

ZbuffeR
10-19-2006, 01:12 PM
Instead of settting color on each vertex, draw a simple white quad, but with an appropriate texture that will hold your color information.
One texel for one cube value.

dovkruger
10-19-2006, 04:06 PM
Zbuffer, I think you are oversimplifying. I know what a texture is. But I have to apply the texture at the center where there is data, and at the edges. This either calls for very messy code with a lot of special cases, or some clever trick which I don't think you have provided.

However, given that texturing uses bilinear interpolation, that does seem like a cool partial solution, thanks.

Consider the following map, in which the numbers are the value of the cell, except for the cells marked N which do not exist. In those spots, the interpolation cannot happen.

N1223433NNN
NN1233441NN
N433122344N
13455112344
1223NN23444
11233N44444
NN122233333
NNNNN12232N
N111123333N
NNNNNNNNNNN

ZbuffeR
10-19-2006, 09:44 PM
1) oversimplfying ? no : you did not mentionned you had such a big problem with "no solution" boxes on the previous posts.
2) "at the center where there is data, and at the edges" that is a good job for playing with texture clamp modes (hint : use GL_CLAMP_TO_EDGE_EXT if you don't have border values). If that is not what you want, sorry but you must describe better what you need.
3) no values : set them to black, with alpha, so that with a simple alpha test you can discard such values (keep the threshold high, so you don't see interpolation to black)

If you need more precise details on one of these points, please ask. I assume it is enough though, as you "know what a texture is" ... :p

k_szczech
10-19-2006, 10:10 PM
Just use texture with size of 2 texels per box + 1 texel:

Grid: Texture:
+--+--+--+ 1234567
| | | | 1234567
+--+--+--+ 1234567
| | | 12345
+--+--+ 12345 So now you can specify colors at center of each box and at it's corners. Each one of grid's vertices should lay exactly at center of a texel. Also, center of box should be exactly at center of texel.
The side effect is that you have to compute colors at center of every edge since there will be texels there, too.

dovkruger
10-20-2006, 04:59 AM
Zbuffer, if you would read my carefully diagrammed scenarios, that is EXACTLY what my original post said.

>The problem with doing it the other way is all >the edge conditions where the grid does not exist:

I do not know how to clamp the way you said, but I will look up the option GL_CLAMP_TO_EDGE_EXT.

k_szczech suggestion is exactly what I currently do, albeit with triangles and Gouraud shading.

If I take k_szczech's suggestion I would have to do quads, one by one, omitting the one that is missing because that is the only way of skipping the texture. Zbuffer is suggesting that I can use alpha to remove the box?

ZbuffeR
10-20-2006, 05:54 AM
k_szczech explained how to convert your data grid to a texture, not the geometry.
You can easily test with a single quad and [0-1] texcoords for the complete grid. The texture will provide both color and alpha (for skipping parts).
Then after if you need fancy geometry you will be able to do it too.

Zbuffer, if you would read my carefully diagrammed scenarios, that is EXACTLY what my original post said.Ok ok ok relax :) I don't anwser your questions for a living you know. You post was very long.

And please don't forget I do provide a good solution. You did not tried it yet ?

k_szczech
10-20-2006, 10:48 PM
k_szczech suggestion is exactly what I currently do, albeit with triangles and Gouraud shading.No, it's not. This time you didn't read my post carefully and it wasn't that long, wasn't it? :]

k_szczech explained how to convert your data grid to a texture, not the geometryExactly, you can use just simple grd of quads with texture I suggested.

Yes, my solution is to skip rendering of the boxes that you don't want to see, so you wouldn,t waste GPU time for 'rendering' invisible quads.
Still, if you prefer to have full grid of quads (for triangle strips), then you can use the same solution - just make visible texels have alpha=1.0f and invisible have alpha=0.0f and use glAlphaFunc(GL_EQUAL, 1.0f);

Or, you could create second texture with alpha channel - this one would map exactly one texel to one box. If this texture will be unfiltered, then it will cut out nice boxes with alpha test.

If you also want to draw entire grid with just one triangle strip, then just enable GL_CULL_FACE - polygons 'returning' from right ende to the left edge will be invisible.