Welcome, Guest. Please Login or Register.  • Help
SMF Underground
+ SHMUP-DEV » SHMUP DEV FORUMS » Assistance » Tutorials
|-+ Efficient bullet rendering using point-sprites and GLSL

Pages: [1]   Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  
Read February 04, 2009, 02:51:12 PM #0
Hornet600S

Efficient bullet rendering using point-sprites and GLSL

Efficient bullet rendering using point-sprites and GLSL

Hi shmup-friends!
Modern shmups need to render lots of stuff. Especially tons of bullets and eye-candy like smoke-trails etc.
There are many different ways to manage and display all this small objects, all of them having different positive and negative sides. Most of the negative aspects result of the requirement to rotate the objects. For example, rocket-like bullets must point in their flight-direction.

Two common techniques are:

1. A texture atlas containing prerendered rotated versions of a bullet.
Pro: no need to rotate vertices.
Cons: texture-coordinates must be modified whenever the bullet's direction changes. And there is only a limited amount of rotation frames.

2. Manually rotated quads.
Pro: very flexible.
Con: the vertices for all four corners of the quad need to be moved and rotated.


Both techniques suffer from wasting CPU-time with coordinate-recalculations (texture- or vertex-coordinates). Besides, both are inefficient, because most often you need an additional linear vertex- and texture-coordinate-buffer to draw them all with just one drawing call.

The typical update/render code looks as follows:

Code:
struct bullet {
  vec2 position_xy;
  vec2 direction_and_speed_xy;
  vec4 color;
  ... other info
};

bullet bullets_of_type_a[MAX_BULLETS];
int active_bullets;

for all active bullets {
  position_xy+=direction_and_speed_xy;
  recalculate rectangle vertices and/or UVs based on position, size and rotation
  append the resulting rectangle vertex-data to a vertex-buffer
}
activate vertex-buffer
draw vertex-buffer

Wouldn't it be nice if it could be this way instead?

Code:
for all active bullets {
  position_xy+=direction_and_speed_xy;
}
activate bullets-array
draw bullets-array

In the following I'll present a technique, using OpenGL, point-sprites and GLSL, that does exactly that.
The only restrictions are:

  • bullets are textured quads, not rectangles.
  • bullets of one type have the same size.
  • Z-coordinate is not used, only X and Y (though it can easily be extended to support 3D positions).
  • single bullet texture, no texture atlas (though it can be extended to support that too).



Point-sprites

Point-sprites are an OpenGL extension, available since OpenGL 1.5. Most of the time they are used in particle-systems. As the name suggests point-sprites are based on single points, they are defined by one single point. The GPU automatically generates a quad around this point. The edge-size of the quad is defined by a global OpenGL state setting (glPointSize(X)). The quad always faces the scene's beholder, so it behaves like a billboard or 2D sprite. The GPU also creates a texture-coordinate for each of the quad's corners (0,0) (0,1) (1,0) and (1,1). So, if texturing is enabled, the active texture is mapped completely on the quad.

Pros:
  • easy to use, because only one vertex needs to be managed.
  • low RAM- and bandwidth-usage.

Cons:
  • fixed texture coordinates.
  • no rotation. Well, rotating a point seems not very useful indeed...

These cons seem to make point-sprites pretty useless for our purpose. But, thanks god, there exists a remedy: GLSL.



GLSL

GLSL is standard OpenGL since version 2.0. It's a C-like programming language which allows us to totally modifiy the GPU's behaviour. In fact, on modern GPUs the "normal" OpenGL behaviour is not hard-wired anymore, but archieved by the driver which loads a "default" program to the GPU which acts like the standard OpenGL.

There exist two types of GLSL programs that are of interest for us, also called shaders (well, to be 100% correct they must be called shader programs, shaders are the hardware units, but who cares):

1. Vertex-shaders are processed for every vertex that we pass to the GPU. Inside such a vertex-program you can modify the vertex-coordinates and do other funny things. Standard-OpenGL does all the transformations here, and also the per-vertex lighting calculations.

2. Fragment-shaders are processed for every fragment that's to be rendered. Here you can modify the fragment's final color. Standard-OpenGL applies the interpolated vertex-colors and texture-information here.

To use such shaders you just pass the coresponding source-code to the driver which compiles and links it to a GPU program. In return you get an ID, similar to a texture-ID. And just like that you activate your shaders by binding this ID to the current OpenGL context. After that point the GPU forgets most of the standard OpenGL stuff and only uses your shaders to process the data you pass to it.



The texture matrix

Our goal is to compensate the cons of the point-sprites using GLSL. Well, let's start!

The main problem is that we cannot rotate point-sprites. But how about rotating the texture instead? Well, we won't rotate the texture itself but the way it is accessed.

OpenGL, like all 3D APIs, is based on matrix calculations. Texture access is no exception. Every texture-coordinate is multiplied with the texture-matrix. Normally this texture-matrix is an identity-matrix so the multiplication doesn't modifiy the original UVs.
But if you modify the texture-matrix to become a rotation-matrix the result is that the texture seems to rotate.

In "normal" OpenGL you can modify the texture-matrix as follows:

Code:
glMatrixMode(GL_TEXTURE_MATRIX);
glLoadIdentity();
glRotatef(ANGLE_DEG,0.0f,0.0f,1.0f);
glMatrixMode(GL_MODEL_VIEW);

Of course that's pretty useless in our case since we want to rotate all bullets independant and draw all in one rush. We would have to execute the above code-sequence (or something similar) for every bullet and draw all bullets one by one. That, of course, would be incredibly slow.

Luckily the texture-matrix can be modified inside a vertex-shader. But how does the shader know the rotation angle we want to apply? Somehow we need to pass it not only the position but also the angle or flight-direction of the bullets. How do we do that?



Passing the data

Fundamentally a vertex-shader can access all OpenGL data associated with one vertex. Basically this means it can access the position, texture-coordinates, color and normal-vector. You may also define additional per-vertex data but in our case that isn't necessary. Since we don't need the normal-vector we could pass our additional information through it.

But this isn't necessary either.
A OpenGL vertex position consists always of 4 components (internally): X,Y,Z and W. The W-coordinate is practically always equal to 1. Since OpenGL internally works with 4x4 matrices the W-coordinate influences the scaling of translations.
Out of this 4 components we only need 2, namely X and Y to represent our bullet positions. That leaves us 2 more components, Z and W, which we can "abuse" to store our bullet's direction-and-speed vector.

For this to work it is essential that the position and the direction-and-speed vector consecutively lie in memory. And they must be of the same type, of course (float).

Code:
struct {
  vec2 position_xy;
  vec2 direction_and_speed_xy;
  ... other info
};

By that we can pass both vectors as one 4D position vector to OpenGL.



The vertex-shader

Our vertex-shader now has to do the following:

  • Split the 4D vertex data into a XY position and a XY direction-and-speed vector.
  • Create a rotation-matrix based on the direction.
  • "Repair" the 4D position (set Z=0 and W=1).
  • Prepare additional info (vertex-color) for the fragment-shader.


All that does the following GLSL program:

Code:
varying mat4 v_tex_rot;
void main(void)
{
  vec4 l_position=gl_Vertex;
  vec2 l_direction=normalize(vec2(l_position.z,l_position.w));
  v_tex_rot=mat4(l_direction.x,l_direction.y,0.0,0.0,
                -l_direction.y,l_direction.x,0.0,0.0,
                0.0,0.0,1.0,0.0,
                0.0,0.0,0.0,1.0);
  l_position.z=0.0;
  l_position.w=1.0;
  gl_FrontColor=gl_Color;
  gl_Position=gl_ModelViewProjectionMatrix*l_position;
}

And now line by line:

Code:
varying mat4 v_tex_rot;
Here a 4x4 matrix variable is defined that will later contain our modified texture-matrix.
varying is a special GLSL keyword. It makes the variable visible in the fragment-shader (where it is actually used later on to access the texture). It also enables automatic interpolation for the variable, but that is not important for us.

Code:
void main(void)
Like in C there is a main-function in every shader. All what's inside is executed for every vertex.

Code:
vec4 l_position=gl_Vertex;
gl_Vertex is a predefined global variable which contains the vertex' position as you passed it to the GPU. In our case it contains actually two coordinates, the XY-position and XY-direction-and-speed. That's why we store it in the local variable l_position for further processing.

Code:
vec2 l_direction=normalize(vec2(l_position.z,l_position.w));
Now we extract the bullet's direction out of the 4D vertex-coordinate (Z and W) and store it into the 2D vector l_direction. Since this vector also contains the bullet's speed we have to normalize it to get the pure direction vector.  The built in function normalize does exactly that.

Code:
v_tex_rot=mat4(...);
Using the previously extracted direction vector we can now build a rotation-matrix, one that rotates around the Z-axis.

Code:
l_position.z=0.0;
l_position.w=1.0;
Now the position vector is repaired by setting Z=0 and W=1, the respective standard values.

Code:
gl_FrontColor=gl_Color;
En passant we retrieve the vertex-color and make it available in the fragment shader.

Code:
gl_Position=gl_ModelViewProjectionMatrix*l_position;
Finally we have to do what standard-OpenGL would do: transform the vertex to its final screen position. gl_ModelViewProjectionMatrix is a predefined global variable and gl_Position is quasi the main-functions return value.



The fragment-shader

Our fragment-shader now has to do the following:

  • Use the texture-matrix prepared in the vertex-shader to calculate the final texture-coordinates.
  • Retrieve the correct color out of the texture and mix it with the vertex-color.

All that does the following GLSL program:

Code:
varying mat4 v_tex_rot;
uniform sampler2D tex;
void main(void)
{
  vec2 l_uv=gl_PointCoord;
  const vec2 l_offset=vec2(0.5,0.5);
  l_uv-=l_offset;
  l_uv=vec2(v_tex_rot*vec4(l_uv,0.0,1.0));
  l_uv+=l_offset;
  gl_FragColor=vec4(texture2D(tex,l_uv))*gl_Color;
}

And again, line by line:

Code:
varying mat4 v_tex_rot;
By that we make the earlier used variable v_tex_rot accessible in the fragment shader. It contains the 4x4 texture-rotation-matrix we prepared in the vertex-shader. The name and type must of course match those used in the vertex-shader.

Code:
uniform sampler2D tex;
A texture-sampler is some kind of an interface to access texture-data and -units. Since modern GPUs have lots of texture-units we have to tell the shader which one to use.
This piece of information has to be passed to the shader from the host application. The GLSL keyword uniform exposes the variable to our application. Inside our app we have to set the value of this variable to 0, to tell the shader to use texture-unit 0. More on this later.

Code:
vec2 l_uv=gl_PointCoord;
gl_PointCoord is a predefined variable again. It contains the automatically generated texture-coordinates for point-sprites ranging vom 0,0 to 1,1. Since we have to rotate this coordinate we store it in the local 2D vector l_uv for further processing.

Code:
const vec2 l_offset=vec2(0.5,0.5);
As already mentioned the texture-coordinates range from 0,0 to 1,1. If we use this coordinates for our rotation it would look like we were rotating the texture around one of its corners instead of its mid-point.

Code:
l_uv-=l_offset;
That's why we transform the original texture-coordinate to values between -0.5 and 0.5.

Code:
l_uv=vec2(v_tex_rot*vec4(l_uv,0.0,1.0));
Now we can rotate this texture-coordinate by multiplying it with our rotation-matrix. The resulting coordinate is stored in our l_uv variable. Since the matrix-multiplication needs a 4D vector to work, we simply expand our source coordinate by filling in 0 and 1 (vec4(l_uv,0.0,1.0)). GLSL is very strict here.

Code:
l_uv+=l_offset;
The result of our rotation is now between -0.5 and 0.5. We have to undo our translation by adding the offset again. So we finally have our rotated texture-coordinates.

Code:
gl_FragColor=vec4(texture2D(tex,l_uv))*gl_Color;
We can now use the texture-coordinate to access the texture. To get bullets with different colors we mix in the vertex-color. The result is stored in gl_FragColor. Like gl_Position in the vertex-shader this is the return-value of the fragment-shader, the pixel's final color.



The host application

Fine, the shaders are prepared, but how do we initialize and actually use them?
Basically this code will do it:

Code:
// input: strings with our vertex- and fragment-shaders.
// return value: a handle to the coresponding GLSL program.
GLhandleARB InitShaders(const GLchar *p_vertex_shader_src,const GLchar *p_fragment_shader_src)
{
  GLint l_size;
  // create vertex-shader object
  GLhandleARB l_vertex_shader_handle=glCreateShaderObjectARB(GL_VERTEX_SHADER_ARB);
  // assign source code
  l_size=::strlen(p_vertex_shader_src);
  glShaderSourceARB(l_vertex_shader_handle,1,&p_vertex_shader_src,&l_size);
  // compile vertex shader
  glCompileShaderARB(l_vertex_shader_handle);

  // create fragment-shader object
  GLhandleARB l_fragment_shader_handle=glCreateShaderObjectARB(GL_FRAGMENT_SHADER_ARB);
  // assign source code
  l_size=::strlen(p_fragment_shader_src);
  glShaderSourceARB(l_fragment_shader_handle,1,&p_fragment_shader_src,&l_size);
  // compile fragment shader
  glCompileShaderARB(l_fragment_shader_handle);

  // create a GLSL program (a combination of vertex and fragment shader)
  GLhandleARB l_program_handle=glCreateProgramObjectARB();
  // attach the previously create vertex- and fragment-shaders
  glAttachObjectARB(l_program_handle,l_vertex_shader_handle);
  glAttachObjectARB(l_program_handle,l_fragment_shader_handle);
  // link to get a functional GPU program
  glLinkProgramARB(l_program_handle);
 
  // delete vertex- and fragment-shader objects.
  // They were only needed for setup.
  glDeleteObjectARB(l_fragment_shader_handle);
  glDeleteObjectARB(l_vertex_shader_handle);

  return l_program_handle;
}

The returned handle can be used like a texture-handle: to activate the shader-program it must be bound:
Code:
glUseProgramObjectARB(program_handle);

To restore the standard OpenGL behaviour just call
Code:
glUseProgramObjectARB(0);

There is still one thing missing to get the shaders to work: We need to tell the fragment-shader which texture unit to use, remember? We must set the uniform variable "tex" to 0:

Code:
glUseProgramObjectARB(program_handle);
// get the internal ID of the variable "tex"
GLint l_id=glGetUniformLocationARB(program_handle,"tex");
// set it to 0 (texture-unit 0)
glUniform1iARB(l_id,0);

That's it. We're done with GLSL. The only thing that's still missing is the actual drawing of some bullets via OpenGL.



Putting all together

1. First we need to define our bullet structure:
Code:
struct BulletA {
  vec4 color;
  vec2 position;
  vec2 direction_and_speed;
  bool alive;
  ...
};

Important: direction_and_speed must immediately follow position! They can be casted to a vec4.

2. Now we need an array of active bullets:
Code:
BulletA active_bullets[MAX_ACTIVE_BULLETS];

Of course you can use a vector<BulletA>, like motorherp did in his "Bullet Management" tutorial. The only thing of importance is that all bullets are managed linear in RAM.

3. And that's how to draw all at once:

Code:
// activate transparency
glEnable(GL_BLEND);
// activate texturing. Not a must, since our shader overrides this settings anyway.
// But don't forget to bind your texture!
glEnable(GL_TEXTURE_2D);
// no depth test, bullets should always be visible
glDisable(GL_DEPTH_TEST);
glDepthMask(GL_FALSE);

// activate point-sprites
glEnable(GL_POINT_SPRITE_ARB);

// setup the desired bullet size.
// this value should depend on your window-size.
glPointSize(15.0f);

// our bullets have coordinates and colors,
// let's activate both
glEnableClientState(GL_VERTEX_ARRAY);
glEnableClientState(GL_COLOR_ARRAY);

// tell OpenGL where our coordinates are.
// IMPORTANT: don't forget, we pass 4 components!
glVertexPointer(4,GL_FLOAT,sizeof(BulletA),active_bullets[0].position);

// and here is the RGBA float color info.
glColorPointer(4,GL_FLOAT,sizeof(BulletA),active_bullets[0].color);

// activate our shaders
glUseProgramObjectARB(program_handle);

// draw all bullets of class BulletA at once
glDrawArrays(GL_POINTS,0,number_of_active_bullets);

// deactivate our shaders
glUseProgramObjectARB(0);

And magically all bullets are rendered rotated and colored.

Some hints:

1. disable texture wrapping. Otherwise you'll get ugly artifacts.
Code:
glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_S,GL_CLAMP_TO_EDGE);
glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_T,GL_CLAMP_TO_EDGE);

2. The texture should contain a picture of your bullet directing to the right.

3. In this tutorial I used the old function names, ending with ARB. Depending on the OpenGL lib you're linking to they appear with or without that appendix.



Last words

Thanks to GLSL it is possible to compensate the negative aspects of OpenGL's point-sprites to build a very efficient and easy to use rendering system for shmup-bullets and eye-candy like smoke etc. The main program's code is simplified since there is no need for additional vertex-data setup. No additional buffers are required and the rotation calculations are moved to the GPU, where they belong.

I hope it was comprehensible. My english isn't the best, so if you find any mistakes please send me a message.
Let me know if it was of any use for you!
« Last Edit: March 08, 2009, 11:14:40 AM by Hornet600S »

"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read February 04, 2009, 02:54:12 PM #1
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

-------

2009-02-21:

- Fixed a typo in the InitShaders listing that would have caused a crash or other undesired behaviour (second strlen...).

- Note:
Normally you wouldn't pass a complete mat4 texture matrix to the fragment shader. I did this to make the source-code more easier to understand.
Normally you would pass just the absolutely necessary piece of information. And that would be a vec2 containing the normalized direction-and-speed vector. You can then do the matrix-multiplication manually in the fragment shader instead of using the built-in mat4 variant.
By that you'd just use 2 float registers instead of 16. Registers are a precious limited resource.

-------
« Last Edit: February 21, 2009, 09:20:19 AM by Hornet600S »

"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read February 04, 2009, 03:37:30 PM #2
the2bears

Re: Efficient bullet rendering using point-sprites and GLSL

This is excellent.  I'll be re-reading this quite a few times to digest and understand it all Smiley  Thanks!

Bill


the2bears - the indie shmup blog
Offline  
Read February 05, 2009, 05:49:18 AM #3
VilleK

Re: Efficient bullet rendering using point-sprites and GLSL

Yes, great article thanks! I like the clever and efficient technique of sending in all positions at once using glVertexPointer without a separate loop and copy to temporary-buffer.


ZGameEditor - Develop 64kb games for Windows.
Thrust for Vectrex - ROM-file and 6809 source code.
Offline  
Read February 05, 2009, 02:23:09 PM #4
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

Thanks guys!
Too bad that even on modern cards GLSL is so terribly supported.
All this bugs I encountered are really unbelievable (especially on ATI cards...).
The stuff I use for this bullet effects is really, really very basic GLSL. Nothing fancy at all. And nothing new.
The recent ATI drivers appear like early alpha-versions to me... Tongue


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read February 05, 2009, 07:44:20 PM #5
mpersano

Re: Efficient bullet rendering using point-sprites and GLSL

Very nice article. Thanks!
Offline  
Read February 08, 2009, 08:26:32 PM #6
failrate

Re: Efficient bullet rendering using point-sprites and GLSL

I think I finally understand shaders properly now.  Thanks!
Offline  
Read March 02, 2010, 02:07:53 PM #7
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

Good news to ATI owners:
After about one (!) year has passed since I reported various GLSL point-sprite bugs to AMD/ATI (of course with easy to understand and compact source-code plus demo-app) they finally managed to fix it!
Well, at least they say so here http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=252611&page=all
So in 2010 the above and similar point-sprite tricks should work even with ATI hardware, unbelievable but true Tongue
Didn't test it yet, because I don't want to polute my running system with a new driver...


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read March 02, 2010, 07:37:21 PM #8
Odessi

Re: Efficient bullet rendering using point-sprites and GLSL

That's good news.  Incidentally I just implemented your technique a few days ago, and it works really nicely.  I added to it a little to let it use texture atlases.

The only issue I have with it is that it requires an array of active bullets, and this can mess up efficient bullet management.  In the end, I did something ugly and just changed the positions of inactive bullets so they wouldn't be drawn (I assume they get culled after the vertex shader).  It seems to work ok.
Offline  
Read March 03, 2010, 06:13:11 AM #9
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

That's good news.  Incidentally I just implemented your technique a few days ago, and it works really nicely.  I added to it a little to let it use texture atlases.

Nice to hear somebody actually got inspired Smiley

In the end, I did something ugly and just changed the positions of inactive bullets so they wouldn't be drawn (I assume they get culled after the vertex shader).  It seems to work ok.

Yes, the the fragment shader shouldn't be executed for those.

The only issue I have with it is that it requires an array of active bullets, and this can mess up efficient bullet management.

But if I asume that you always loop over your bullet array anyway (to update position etc.) it's actually quite easy to remove dead bullets on the fly:

I asume your code looks more or less like this:

Code:
Bullet bullets[MAX_BULLETS];
unsigned int active_bullets;
...
void UpdateBullets(void)
{
  for(unsigned int t=0;t<active_bullets;++t) {
    ...
    if(bullet[t].IsDead()) {
      ...
    }
  }
}
...

1. if bullet draw order doesn't matter just do the following:

Code:
if(bullet[t].IsDead()) {
  bullet[t--]=bullet[--active_bullets];
}

This overwrites the dead bullet with the last active bullet and adjusts the loop and everything accordingly. But, as I said, the bullet order is changed. Depending on your rendering this may or may not be acceptable.

2. if order does matter then you can do it this way:

Code:
void UpdateBullets(void)
{
  unsigned int new_index=0;
  for(unsigned int t=0;t<active_bullets;++t) {
    ...
    if(bullet[t].IsDead()==false) {
      if(new_index!=t) bullet[new_index]=bullet[t];
      ++new_index;
    }
  }
  active_bullets=new_index;
}

By that you essentially do the required memmoves splitted during the update itself.

« Last Edit: March 03, 2010, 06:21:34 AM by Hornet600S »

"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read March 03, 2010, 07:07:07 PM #10
Odessi

Re: Efficient bullet rendering using point-sprites and GLSL

Yeah, the first approach was no good because of reordering and I thought the second one might cause an awful lot of copying in the worst case, but it seems to be ok, so thanks. Smiley

The second approach could possibly be sped up by batching memcpys, but it seems quick enough already so I'm not going to bother.
« Last Edit: March 03, 2010, 07:09:06 PM by Odessi »
Offline  
Read March 04, 2010, 06:18:15 AM #11
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

The current worst case is pretty easy to define and to profile:
only bullet[0] is dead.

But I doubt this will ever become even noticable performance-wise. Also don't forget that you'll have to use memMOVE, not memCOPY, which is much slower.

And considering the additional bookkeeping you'd have to do plus the overhead of memmove that would really only pay off if you got an unbelievable amount of bullets and / or if your bullet's life-cycle always results in bullet 0..n being dead without any survivor in between.

Of course you'll have to profile to be sure.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read March 04, 2010, 09:25:50 AM #12
Odessi

Re: Efficient bullet rendering using point-sprites and GLSL

Of course you'll have to profile to be sure.
Of course, always profile Smiley

Yeah, I forgot that memcpy wouldn't work, anyway all is ok.
Offline  
Read March 05, 2010, 08:55:37 AM #13
LorenzoGatti

Re: Efficient bullet rendering using point-sprites and GLSL

At least on a PC, there should be enough memory to keep two arrays of bullets and update them by writing from one to the other with free compacting rather than in-place.
Almost all data of a bullet (position, timers etc.) changes every frame: the whole record can be written once rather than written in the wrong array location and then possibly moved for compaction purposes.
Offline  
Read March 05, 2010, 09:13:08 AM #14
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

Maybe I don't get you right, but from my point of view a 2nd array just complicates things and is a waste of space without any benefit at all.
It all comes down to this:
If you use arrays and no linked list for your bullets (and I strongly suggest to use arrays) then you have to remove dead bullets out of the array. And this means copy operations, be it from one array to another or be it in place.
And it is not of any importance if you update the bullet first and then possibly move it, or vice versa.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read March 05, 2010, 11:28:09 AM #15
Odessi

Re: Efficient bullet rendering using point-sprites and GLSL

I just tried using two arrays and memcpying between them, it was a lot slower.
Offline  
Read March 08, 2010, 02:23:26 PM #16
LorenzoGatti

Re: Efficient bullet rendering using point-sprites and GLSL

And it is not of any importance if you update the bullet first and then possibly move it, or vice versa.
I meant that you can combine update and compaction by writing the updated values of live bullets into the second array, and nothing for dead bullets: the bullet array remains compacted and sorted. The old buffer is recycled as the new buffer of next iteration, hopefully without the need to call hundreds of destructors.
I think memory accesses cannot be fewer and more coherent than reading the old buffer once sequentially and writing the new buffer once sequentially.

There's a variant that should require less memory with marginal speed differences: iterating through a single array with two indexes, read and write, that both start at 0; the first few live bullets are updated in place and remain compacted, then the write index lags behind as the read index skips over dead bullets and updated bullets are written over skipped dead or already processed bullets. Of course this approach is unable to add new bullets at arbitrary places in the array during bullet updates because the gap might be filled.

I don't think memcpy or the like should be used for such operations; such functions have some overhead (checking for overlapping ranges etc.) and they would be called many times for one or a few records. If copies are needed (e.g. to resize an array) the memcpy/memmove should be a big one.
Offline  
Read March 08, 2010, 03:25:15 PM #17
Hornet600S

Re: Efficient bullet rendering using point-sprites and GLSL

I meant that you can combine update and compaction by writing the updated values of live bullets into the second array, and nothing for dead bullets...
Yes, it would work, but you still have the same problem of removing dead bullets, if you do it by copying living bullets to a 2nd buffer or if you do it by overwriting dead bullets. As far as I get it your method would require copying around even if there was no dead bullet at all. But maybe I still don't get you right Smiley If that's the case post some pseudo-code.

There's a variant that should require less memory with marginal speed differences: iterating through a single array with two indexes, read and write, that both start at 0...
That's exactly what the 2nd code snippet above does.

I don't think memcpy or the like should be used for such operations; such functions have some overhead (checking for overlapping ranges etc.) and they would be called many times for one or a few records. If copies are needed (e.g. to resize an array) the memcpy/memmove should be a big one.
Correct, that's why in-place update/remove like in that 2nd snippet is usually the fastest way to do it.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Pages: [1]   Go Up
Jump to:  

Page created in 0.271 seconds with 19 queries.