I can't possibly cover everything, nor do I know every technique... in fact, I am unfamiliar with OpenGL 4.0 and newer. yet, I think I know enough to expand the way you think about this. However, have it clear thet there is much more to say about every technique, I am not going into technical detail, no code (it would be a lot) and very little math.
I suggest to make narrower questions, then answers can be deeper and less broad.
Before I go into shaders and what not, I want to mention that iterative algorithms in GPU are possible, and very useful. However I would recomend against walking an object hierarchy in GPU.
There are multiple types of shaders. The two more common are: vertex shaders and fragment shaders, which I will go into in more detail. I also want to mention geometry shaders and compute shaders.
As far as I can tell common GPU models out there has poor performance on geometry shaders, reason why I avoid using these.
About compute shaders, I am not the right person to ask. Although, you should probably look into them.
Know that you can send data to the GPU in at least these ways:
- Textures that you will be able to query on the GPU
- Vertex data, such as position, color, normal, etc...
- Uniform values that are not attached to a given vertex or texture
Also know that the shader program could be manipulated as a string before uploading to the GPU. Doing this to inline values that are not meant to change during the lifetime of the application - for example user settings - can improve performance. In fact, you could trim out entire portions of the shader program if the user has disabled visual effects.
Aside from that uniform values are useful to pass information that does not change during the frame and could affect all of it. The best use is passing time, allowing the GPU to know the time allows the GPU to do animations.
For instance, if I want to do morph target animations in GPU, I pass as vertex data the last position, the last time, the future position and the future time, and then as uniform I pass the current time and have code in the shader program to interpolate. Similar techniques can be used to animate a day/night cycle and stuff like that.
As per getting data out of the GPU to the CPU, that would require to draw to a texture. And of course the output texture can be the input for another GPU call.
Note: in some cases you can also do multi pass renders for a single frame (by not cleaning buffers between them), that is not what I mean by using a texture as input. We will see below.
You have send some vertex data to the GPU, and the vertex shader will run on each vertex and allow you to manipulate it. If you want to change the position of something in GPU, here is where you do it.
Let us say we want to have a tree swing in the wind. But... updating the position of each vertex in CPU is time consuming. No problem, we can offset each position in the vertex shader.
How much to offset the vertex by? Well, for a simple model, we can use the vertical position of the tree (so that the higher the more swing), which we would multiply with a sort of wave changing in time... that can be done with a 1D perlin noise and the time uniform as input, and perhaps a third parameter to tweak how stiff the tree is.
Alright, but... computing perlin noise on the GPU? We can do better. Generate a 1D texture (it is an array, ok?) with 1D perlin noise in CPU and upload it to the GPU.
A similar approach can be used for water. In 3D you can animate the high of water to make waves. That would also work in 2D... but, I will come back to that.
Gravity and particles
Things fall, right? We can pass starting position, starting velocity and starting time as vertex data, and gravitational acceleration and time as uniforms. Then the GPU can compute the displacement for the current time and offset the vertex by that amount. Simple.
In fact, if you want particle effect this a way to do it. You would have some buffer space dedicated to particles, then when you need to an explosion you write on vertex on the buffer the starting position and some velocities (which you can have pre computed, just copy them to the buffer) and have the GPU animate them.
You can do similarly for rain and snow. In fact, that wind effect will probably look good if you apply it to snow too. Or similarly for falling leaves.
Note: Since you will have some dedicated buffer space for particles, there will be a maximum number of particles on the game at any given moment (a particles budget if you like). And this will have a performance impact. Thus, I would like to encourage to let the user change it via configuration.
Orbit and pendulums
You got the idea by this point. You will be moving the vertex coordinates according to a circular path (you can also do elliptic path or similar), using the polar equation for the orbit you want.
To do it, you pass the start angle (or you compute it on GPU) and time as vertex data. If you need to, you can pass rotation speed as a uniform (or inline it as a literal in the shader program) and have the GPU compute the current position.
The same idea will work for pendulums, and thus for flapping things.
Go back to the idea of morph target animation. You can have multiple kinds of interpolations to do all sort of things. For example, if you need an object to fall to the ground and bounce lower and lower until it stops... well, guess what, that is a valid interpolation curve between the starting point and the ground※.
※: Which will be valid as long as the ground does not move and no obstacle gets in the way. You could check for obstacles, which will require the involment of the CPU, and update the animation if needed. That means that your CPU code changes from computing the position each frame to deciding a trajectory and checking if it is still valid... for which the code is basically continuous collision detection.
Addemdum: Flow fields
To make your flow field create a texture where each texel represents a vector (each color channel for a coordinate). You also need a position where the flow field is and a its size.
If you want to animate particles to follow the flow field you need to find where on the flow field the particle is. Apply the appropiate transformation to the position of the particle according to the size and position of the flow field and query it texture. Now you have a vector that tells you how to move the particle.
Remember, you are passing time as a uniform, so you can animate the movement. However, within the realm of my knowledge, getting the updated position of the particle to feedback in would be a hassle.
Addendum: Apparently Transform Feedback helps with this.
The fragment shader will run per output pixel. You will pass information from the vertex shader to the fragment shader, and - usually - these gets interpolated between the shaders.
This allows you to have - for example - the position of the pixel in 3D (it is the interpolation of the positions of the vertex of the primitive - triangle or squad - that define it), also interpolated normals, texture coordinates, etc.
Note: you also have access to uniforms here.
A common task in fragment shaders is to take these values and use them to look up in textures.
Fragment Shader 3D effects
Very simple: compute how close the normal matches the direction of the source of the light and use it to change the color of the pixel, for example by blending with the color of the light.
Also straight forward: compute the distance from the origin (the camera) and use it to blend the pixel color with the fog color.
Spotlights and shadows
We are getting somewhere...
I will describe an old school technique: we are going to make a source of light with a viewing volume. So, build a viewing volume you want, such that everyting in view is what will be light. For example, it can be a street lamp looking down.
Once you have your viewing volume, use it as camera and render the scene to a texture. However, only the depth buffer.
Place the camera where you need it, upload the depth buffer you extracted as a texture to the GPU, and pass the information of the light viewing volume as uniforms. In the fragment buffer, compute where it falls in the view from the source of light, with that position query the depth buffer texture you uploaded, and if the pixel position is futher away than what the depth buffer says... it means something else is closer to the light source, thus that pixel is in shadow. Otherwise it is in light. Adjust the color of the pixel accordingly.
Of course you could also change the position of the source of light from one frame to the other. And of course you could also have multiple sources of light. Note that with this approach each light is a render pass to extract the depth buffer, and you can only have a finite number of uniforms... so, you will be forced to pick what lights are relevant to the scene (which usually means the sun and whatever is close to player).
In fact, you can tell if the player is in light or in shadow by checking in the depth buffer for the sun the position of the camera. If you check this between frames, you can find the moment where the player steps to the light or to the shadow, allowing you to, for example, animate a gamma correction to mimic the eyes adjusting to light or dark, or you could add a light source near the camera to mimic a headlamp.
I'm not a hero, I'm not a savior, forget what you know.
We will only place a geometry that covers the view (a single quad can do), and then in the fragment shader we will be running once per pixel on this quad. Start by computing a ray director vector with the position of the vertex and the origin. That will be the ray. We will advance with it...
We will need the geometry of the environment, but not in vertex data (as I said, we are only covering the view with vertex), instead we want the geometry in textures.
First we need to find what is closer in the general direction of the ray. Using a cube skybox instead of a single quad can help, because then we can use the vertex data to save us some time. We have six general directions. We can then partition our geometry data accordingly and that will make the query easier. There are other approaches, of course.
Note: some medical imaging software use a similar approach to present a 3D view of volumetric scans of body parts (MRI and similar). They use a point cloud data loaded as a 3D texture to represent the object to render.
How do we represent the geometry? You have a lot of freedom for this. We are no longer constrained to triangles and quads. For example, we can describe actual curve surfaces.
One approach is to inch your way with the ray. You make a loop and each iteration you advance the ray, then you need to find the nearest object (you may for example use a 3D texture where each voxel tells you the nearest object to that coordinate with some resolution) and try to collide with it.
I want to suggest an alternative… I confess I haven't fully figured out the data-structures for 3D, however the following will work: start with an oct-tree, and dump it three times to a texture, one per axis. So that in the GPU we can traverse it in any of these axis. Knowing the position of the camera and the general direction of the ray we can pick on what axis to traverse the data, from where and in what direction.
You could have a colliding volume (I suggest a sphere) for each object described in a texture that we query in the fragment shader. Then we can intercept the ray with the colliding volume to find if it can collide with a given object, that is a potential hit.
Yes, this whole thing is a loop until we find a hit. Yes, iterative computation.
For each potential hit we would then check against the geometry of that object, described however you want to describe it (as long as we can check collision with our ray director vector). You would then go on to query the texture for the object, compute normals and apply lights.
Ray-casting will be bound by the number of pixels on screen instead of by the number of polygons, that can make performance better or worse depending on the scene you are rendering. It is great for indoor scenes where rays do not have to travel too far.
You can combine it with the traditional approach too. For example, you can render all the static stuff (floors, walls, stairs, etc...) with ray-casting, and then do another render pass to put in entities and particle effects. There are a few gotchas when trying to use this approach, such as transparency and shadows.
Fragment Shader 2D effects
I said I would go back to that 2D water. If you have a side view (as in most 2D platformers, at least the good ones) and you want to animate the edge of water... with polygons you need a lot and it can be a mess.
Do not fret. All you need to do is decide what fragments to drop. If you can describe the wave on the edge of the body of water with a math formula (with a time parameter to animate it, of course), it is trivial to check if a given pixel is above or below the curve and use this to decide if you will drop the fragment. By dropping all the fragments above the curve you are giving a curve edge to your triangle or quad.
We can go futher... let us say that you want to update the animation so that when an object falls into the water it changes the waves. Well, no problem. What you need is to have multiple parametric wave functions that you can combine. One will be the motion of water when nothing has dropped in (say for example ocean waves). The others you will have a center position, an intensity and a start time as parameters, such that changing the time will also make them fade out. Then combine them in GPU.
There will be a fixed number of these waves and you set them one by one each time something falls in water, when you get to the end, simply go back to the first and continue. Assuming there are enough waves and they fade out quickly enough, people should not notice.
One way to do them is with particles effects. Here is another way that works for 2D...
We can do fire with a very old school feedback loop.
You will be rendering to a texture that you will then use to represent the fire or smoke. This texture will be initialized empty, but with a seed texel (texture pixel) of another color. Each frame, you will apply a kind of kernel (think convolution) that will update the texture.
The rules for the update are basically that fire moves up, and fire cools down. You can add noise to make it more realistic.
However, the player will not see this texture, instead you will combine it with another texture to give it color.
I'll refer you to Playing with fire – WebGL fire simulation for more information.
If we are doing a 2d top view (as in most 2D RPGs, at least the good ones) you will want to render a lot of terrain, usually in the form of tiles.
Pass a quad for each tile? Nope. Pass a single quad for the whole thing, you can place it at the far plane. Then pass a texture where each texel represent a type of tile, and another texture that serve as atlas for all the tile textures, and the position of the camera as uniform.
In the GPU you will compute for each pixel of this quad, on what tile it is (by using the position of the camera), then query the first texture to get the kind of tile, and then query the second texture to get the color.
You can go a step further and pick a texture based not only on the texture of the current tile, but also consider the textures of the neighbor tiles.
A 2D fluid simulation for side view is possible. They are a cellular automata. Use similar ideas as the ones above: have a texture tell how much water is in each tile, and we will update this texture each frame.
Initialize the water texture with a pixel of water for each tile that has water and obstacle pixels to make the tank and floors.
The rules to update the texture are basically that water falls, has a maximum density, flows to the sides when it can't fall and does not go through obstacles.
And again, it is not this texture what you render. This texture has a resolution of tiles, and you will be deciding how to render it considering neighbor tiles...
For instance, if the current tile is 50% water and the pixel below is an obstacle, then it is a tile with the bottom half full. If it is 50% water, nothing on the sides or below, but water on top, then it is the tip of a stream of water falling down. If it is 50% water, nothing below, but there is water at the sides then it is part of a wide stream. Etc.
Again in a 2D top view, there are have lamps and we want to cast shadows. You can do this as line of side checks. However we want to do it on the GPU...
You can do ray-casting! In fact, since you only need 1D for each lamp, you can do them all at once.
Remember, we will be rendering to a texture first...
Have another squad that covers the view. Each row will be a light, each column will be an angle. Take the position of the pixel and figure out what lamb on what angle is that. With that you create a ray director vector that you can use to advance.
We can do something similar to what I was describing about the cube on ray-casting for 3D but for 2D. You would split the screen in four quads vertically. So that each quad correspond to one of the four cardinal directions...
Then you can have a texture with the objects data. In fact, two copies of the data of the objects, one has them arranged vertically and one have them arranged horizontally.
Take the position of the current light (which you pass uniform), and the cardinal direction (which you pass as vertex data), and that will tell you from where and in what order to go over the texture with the objects data. You iterate over the objects data until you find an obstacle. Output a color that represents how far did you have to iterate.
The resulting texture can be used to query if an object is illuminated by a given light by checking if the value in the texture represents a distance lower than the distance to the light. If it is lower, then that means another objects blocks the light.
Put all your collision detection in terms of ray-casts... many game engines has a ray-cast method for this kind of things, it usually works on CPU, we want GPU.
Then we can do all the ray-casts in one pass (or a few). Render to texture, use a quad covering the view, the data of each ray-cast will be in a texture you pass as input.
Take the current pixel position and use it to query the data for the ray that corresponds to it. Build the ray director vector, and proceed to do the ray-casting.
The output texture has the result of your ray-casts.
this is not a bad idea anyway. For instance, you have a 3D game where the avatar can jump. You will not check for collision between the avatar and the ground, instead you do a ray-cast to the ground.
Careful, if the source of the ray happens to be below the ground, it will not detect the ground and your avatar will just fall through it. I want to strongly suggest continuous physic simulation to avoid this kind of thing.
Continuous physics simulation with ray-casting
The geometry for collision detection is not the geometry the player sees.
As you know, we use collision volumes. We will do something similar. However, we will not use discrete collision detection, but continuous instead. That means that the approach is not move, check if collide, fix... instead it is check if it will collide then move accordingly.
To deal with moving objects we will create ghost collision volumes that cover the start position of the object and where it will be. Donnie Darko comes to mind.
We can figure out where an object will be next frame either by physics or by following animation (or both) depending what we are doing.
The ghost collision volume does not need to be perfect, it is a heuristic. And the easier to check in ray-casting the better. We can model it as cylinder. So we have start position and a director vector (of the motion) that describe a center line for the cylinder, and a thickness that should cover the size of the object. Do not worry of it extending beyond the movement of one frame. Now the ray-cast against the ghost volume reduces to distance line to line. If the distance is less than the width of the cylinder (the size of the object) we have a potential collision.
Next you need to figure out the point where the ray intercepts the cylinder. That is the point on the ray that has distance to the center line of the cylinder equal to the thickness of the cylinder. You can project this point to the center line to find the point on the cylinder. No, that is not the closest point, but it is the point we care about, because it is where the object would be on collision.
Since we know how fast the object moves, we know at what instant it would reach the position of collision, and we can check if it is in the future and before the next frame. If it is in the past, no collision. If it is beyond the next frame, no collision. If it is in the future and before the next frame... well, how good do you want the detection collection to be? You could check against the geometry of the object in that instant to refine the collision detection, or just call it a collision.
Once you have your collision, get the time of collision. There other objects to check and some of them could collide before, we want the earliest collision.
Yes, you can do all that in the GPU, in a fragment shader, rendering to texture.