Most efficient grid drawing algorithm

You could use a vertex array or something, and use a vertex shader to deform your mesh.

That should speed thing up.

This might improve the speed in general, but I would still want to find the most efficient way to initially draw the grid!

You can't in general draw a 3-D grid with only 1 line strip.

Consider a vertex on the face of the grid but not on the edge. It has 5 vertices adjacent to it. Since 5 is odd you need to either start or end the strip at this vertex. But if the grid is at least 3x3x3 then there are 6 such vertices. A line has only 2 endpoints. Contradiction.

Therefore you can't do it. It may be possible if you 3x2x2 or smaller. I didn't bother to try to check.

Consider a 2D grid:

 - - - - -| | | | | | - - - - -| | | | | | - - - - -| | | | | | - - - - -

The vertex on the edge has 3 vertex adjacent to it, but you can still draw it with one line like this:

 -   -   -| | | | | | - - - - - -  | | | | | | - - - - - -| | | | | | - - - - - -  | | | | | |   -   -   -

The equivalent in 3D might have bumpy edges but thats allowed :) .

I smell pre-mature optimization. Do you know that this is necessary?

I know it not optimised but just interested in the theory.

Quote:

Original post by guin Consider a 2D grid: - - - - -| | | | | | - - - - -| | | | | | - - - - -| | | | | | - - - - - The vertex on the edge has 3 vertex adjacent to it, but you can still draw it with one line like this: - - -| | | | | | - - - - - - | | | | | | - - - - - -| | | | | | - - - - - - | | | | | | - - - The equivalent in 3D might have bumpy edges but thats allowed :) .

This won't work in 3D. An even better example of what I said previously is to consider the corners of the 3D grid. Each corner vertex has 3 adjacent vertices and no matter what your grid looks like you will always have at least 8 corners (if you make it "bumpy" you could have more though). So again you can't have a single line covering all edges.

If you want to make the problem more intersting you could try to find either:
1. The minimum number of overlapping edges.
2. The minimum number of vertices placed when drawing the lines.

Might want to look into precompiled display lists if you're using OpenGL. Sometimes these can be more efficient than vertex arrays. However, vertex arrays should serve most purposes for grids measuring up to 256 * 256 vertices. Anything above that, in my experience, requires LOD of some sort to render at any decent frame rate.

EDIT: I'm fairly sure that arranging the grid into triangle strips may slightly improve the vertex arrays performance, depending on your graphics card's implementation of vertex arrays.

My advice would be to have all the vertices in a VBO, and then use indices in a GL_LINES. And if it's all static, have the indices in a VBO as well. Voila, speed and flexibility.

This sounds like a Hamilton Path graph problem
Hamiltonpath

You have a NxM grid. Now consider each edge of the grid(edge = connection of 2 grid vertices) as a vertex of a undirected graph G. Your linestrip would be a Hamilton Path in this undirected graph G. This is a NP complete problem so you might as well draw it column by column & row by row and forget about these optimizations.

[edit: updated with color to show the line direction, doesn't look like they overlap!]

I worked out the 2D algorithm and added an extra loop to scale it to 3 dimensions. I'm sure in 2D there are no overlapping lines but I only guess about the 3D version. It should be possible to scale this to 4 or more dimensions!

The only imperfection I know is 2 vertices will be duplicated at (0, 0, 0) and (n, n, n) (interesting, in 2D, only 1 vertex is duplicated at (n, n, n) ). You can see below.

0 0 0		    2 2 3		4 4 3		    2 0 2		0 1 0		    3 2 21 0 0		    2 2 4		3 4 3		    3 0 2		0 1 1		    4 2 21 1 0		    2 1 4		3 3 3		    3 1 2		1 1 1		    4 2 11 1 1		    2 1 3		3 2 3		    3 2 2		2 1 1		    3 2 11 1 2		    2 1 2		3 1 3		    3 3 2		3 1 1		    2 2 11 1 3		    2 1 1		3 0 3		    3 4 2		4 1 1		    1 2 11 1 4		    2 1 0		2 0 3		    4 4 2		4 1 2		    0 2 11 2 4		    2 0 0		2 1 3		    4 4 1		3 1 2		    0 2 01 2 3		    3 0 0		2 2 3		    3 4 1		2 1 2		    0 3 01 2 2		    3 1 0		2 3 3		    3 3 1		1 1 2		    0 3 11 2 1		    3 1 1		2 4 3		    3 2 1		0 1 2		    1 3 11 2 0		    3 1 2		1 4 3		    3 1 1		0 1 3		    2 3 11 3 0		    3 1 3		1 3 3		    3 0 1		1 1 3		    3 3 11 3 1		    3 1 4		1 2 3		    2 0 1		2 1 3		    4 3 11 3 2		    3 2 4		1 1 3		    2 1 1		3 1 3		    4 3 21 3 3		    3 2 3		1 0 3		    2 2 1		4 1 3		    3 3 21 3 4		    3 2 2		0 0 3		    2 3 1		4 1 4		    2 3 21 4 4		    3 2 1		0 0 2		    2 4 1		4 2 4		    1 3 22 4 4		    3 2 0		1 0 2		    1 4 1		4 2 3		    0 3 22 3 4		    3 3 0		1 1 2		    1 3 1		3 2 3		    0 3 32 3 3		    3 3 1		1 2 2		    1 2 1		2 2 3		    1 3 32 3 2		    3 3 2		1 3 2		    1 1 1		1 2 3		    2 3 32 3 1		    3 3 3		1 4 2		    1 0 1		0 2 3		    3 3 32 3 0		    3 3 4		2 4 2		    0 0 1		0 2 2		    4 3 32 2 0		    3 4 4		2 3 2		    0 0 0		1 2 2		    4 3 42 2 1		    4 4 4		2 2 2		    0 0 0 collision	2 2 2		    4 4 42 2 2		    4 4 4 collision	2 1 2

	float scale = 100.0f;	int n = 5;	int d = 0;	int i = 0;	int j = 0;	int k = 0;	int i_m = 1, i_z = 1, j_m = 1, j_z = 1, k_m = 1, k_z = 1;	int *pxa[3] = {&i, &j, &k};	int *pya[3] = {&j, &k, &i};	int *pza[3] = {&k, &i, &j}; 	int **ppx = pxa;	int **ppy = pya;	int **ppz = pza;	glBegin (GL_LINE_STRIP);	for (d = 0; d < 3; d ++)	{		glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);		i += i_m;		while (i*i_m < n*i_z -1 + (i_z + -i_m))		{			glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);			j += j_m;			while (j*j_m < n*j_z -1 + (j_z + -j_m))			{				glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);				k += k_m;				while (k*k_m < n*k_z -1 + (k_z + -k_m))				{					glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);					k += k_m;				}				glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);				k_m = -k_m;				k_z += k_m;				j += j_m;			}			glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);			j_m = -j_m;			j_z += j_m;			i += i_m;		}		glVertex3f ((float) **ppx * scale, (float) **ppy * scale, (float) **ppz * scale);		i_m = -i_m;		i_z += i_m;		ppx ++;		ppy ++;		ppz ++;	}	glEnd ();

[Edited by - guin on April 14, 2006 8:17:16 AM]

Quote:

Original post by Basiror This sounds like a Hamilton Path graph problem Hamiltonpath You have a NxM grid. Now consider each edge of the grid(edge = connection of 2 grid vertices) as a vertex of a undirected graph G. Your linestrip would be a Hamilton Path in this undirected graph G. This is a NP complete problem so you might as well draw it column by column & row by row and forget about these optimizations.

Intresting link.

Yes the 'core' is perfect grid. Interesting to see how math solves the edges problem by itself :) .