Introduction
This article is accompanied by some code which performs water motion simulation using several techniques and data structures.
Background
The original algorithm is by Don Pattee here and Christian Tratz. This version still maintains at the core though the original mathematical algorithm has been changed quite a bit. For one thing, it outperforms the previous versions and uses a class for FAST bitmap manipulation which uses UNSAFE C# and can be found here. I am not really using the FASTBitmap since it came up slower than using BUFFERED rendering, but I found it amusing and it could be helpful in other situations.
Using the Code
The code is ready to run if you are using Visual Studio .NET 2.0. There are some comments in the source code itself which you need to read to get an idea of what is going on, but basically I took the original VB source code from Don and imported to C# which is funny because he took the original algorithm from Tratz and imported to VB.NET. Anyway I did change the algorithm a bit as the original though quite good was running too many loops and I felt this could impact performance. Next I implemented the new algorithm using three different data structures JAGGED, RECTANGULAR and LINEAR arrays to see which one could yield the best performance, The JAGGED came on top, and the LINEAR the last with the RECTANGULAR somewhere in between. I also added code to be able to run the algorithm in two modes BUFFERED rendering and NON BUFFERED rendering. I was hoping the FAST bitmap would keep the lead but it didn't, the BUFFERED version outperformed it.
Here is some of the code which shows compiler directives to enable all three modes plus the buffered non buffered version. I suggest you download the source code and start playing with it. Finally I would like to mention the fact that we have come so far and today with C# and VB.NET, we can pretty much match speeds for algorithms which were previously only possible in C++. By the way, the managed version written in C++/CLI by me of these algorithms did not outperform the C# version. I have written a C version or an old native C++ version, they probably kick the C# badly.
#define _BUFFERED_RENDERING
#define _JAGGED_ARRAYS
#if _JAGGED_ARRAYS
_waveHeight = new int[_BITMAP_WIDTH][][];
for (int i = 0; i < _BITMAP_WIDTH; i++)
{
_waveHeight[i] = new int[_BITMAP_HEIGHT][];
for (int j = 0; j < _BITMAP_HEIGHT; j++)
{
_waveHeight[i][j] = new int[2];
}
}
#endif
#if _RECTANGULAR_ARRAYS
_waveHeight = new int[_BITMAP_WIDTH, _BITMAP_HEIGHT, 2];
#endif
#if _LINEAR_ARRAYS
_waveHeight = new int[_BITMAP_WIDTH * _BITMAP_HEIGHT * 2];
#endif
Points of Interest
I wrote the first algorithm using RECTANGULAR arrays and buffering. It yields pretty good performance but I wasn't sure if this was the best way to do this. I started thinking about which parts of the algorithm could be improved and after a while, I decided that the part which renders the new bitmap should be the one to concentrate on. I did a little research on the internet and found a class called FASTBitmap which ran unsafe C# code and which was able to bypass all the managed stuff and write to the bitmap directly. This class though quite powerful is very simple, since it runs unsafe it can actually get a pointer to the first byte of the bitmap. It does this by using the method LockBits() which returns a pointer to the first byte in Scan0. Here is the code:
(Byte*)bitmapData.Scan0.ToPointer();
It uses this pointer as the base so that later on it can Get and Set pixels directly.
After this, the code did in fact run a bit faster, but then I started remembering the different kinds of arrays we programmers use such as jagged, linear, etc. I decided to write the code so that it could run using any of the three types of arrays. I discovered that the jagged version was running faster. This really contradicted my expectations, but anyway as I see this it should not even matter since all dimensions are FULL and used.
I did change the FASTBitmap class a bit, because the way I planned to use it, I need to know if the bitmap was locked or not and I also added public properties for accessing some of its internal data, such as bitmapData and LockBits and Release.
I don't know who wrote the original math-algorithm, I think Don imported it from Tratz but I don't know where he got it from, either way it is quite simple, it involves Cos() and PI and the algebra part is all mainly Additions, Subtractions and Divisions which I implemented as Shift. The original VB version by Don did not have this luxury as it was written in an older version of .NET.
The algorithm is divided into two parts, the first part places DROPS of water in the array which is used to keep track of the height of a pixel at a given X,Y, the third dimension in the array is used to remember the previous heights. The new height is calculated using the old. Here is the code for the JAGGED array. The top part is calculating sort of an average height based on neighbouring pixels. The bottom part calculates the offsets for the pixel in question so as to simulate movement. So for example Pixel(x,y) may actually display Pixel(x+offset,y+offset). This gives the illusion of movement. Because it is based on Cos() (could as well use Sin() since they are the same separated by PI/2), you get a wave type of motion.
This is PART 1. This part places drops of water in the wave array, it calculates the height of pixels on the drop based on the distance from the center of the drop, the height from which the drop fell and other things. Once the drop is placed, then the motion part of the algorithm takes over.
private void DropWater(int x, int y,int radius, int height)
{
long _distance;
int _x;
int _y;
Single _ratio;
_ratio = (Single)((Math.PI / (Single)radius));
for (int i = -radius; i <= radius; i++)
{
for (int j = -radius; j <= radius; j++)
{
_x = x + i;
_y = y + j;
if ((_x >= 0) && (_x <= _BITMAP_WIDTH - 1) && (_y >= 0) &&
(_y <= _BITMAP_HEIGHT - 1))
{
_distance = (long)Math.Sqrt(i * i + j * j);
if (_distance <= radius)
{
#if _JAGGED_ARRAYS
_waveHeight[_x][_y][_currentHeightBuffer] =
(int)(height * Math.Cos((Single)_distance * _ratio));
#endif
#if _RECTANGULAR_ARRAYS
_waveHeight[_x,_y,_currentHeightBuffer] =
(int)(height * Math.Cos((Single)_distance * _ratio));
#endif
#if _LINEAR_ARRAYS
_waveHeight[INDEX3D(_x, _y, _currentHeightBuffer)] =
(int)(height * Math.Cos((Single)_distance * _ratio));
#endif
}
}
}
}
}
Here is PART 2 of the algorithm, this part simulates the wave motion. It also takes care of the dampening for a more realistic looks, imagine if the wave was always the same, uh no good.
unchecked
{
_waveHeight[_x][_y][_newHeightBuffer] = ((
_waveHeight[_x - 1][_y][_currentHeightBuffer] +
_waveHeight[_x - 1][_y - 1][_currentHeightBuffer] +
_waveHeight[_x][_y - 1][_currentHeightBuffer] +
_waveHeight[_x + 1][_y - 1][_currentHeightBuffer] +
_waveHeight[_x + 1][_y][_currentHeightBuffer] +
_waveHeight[_x + 1][_y + 1][_currentHeightBuffer] +
_waveHeight[_x][_y + 1][_currentHeightBuffer] +
_waveHeight[_x - 1][_y + 1][_currentHeightBuffer]) >> 2)
- _waveHeight[_x][_y][_newHeightBuffer];
}
_waveHeight[_x][_y][_newHeightBuffer] -= (_waveHeight[_x][_y][_newHeightBuffer] >> 5);
_offX = ((_waveHeight[_x - 1][_y][_newHeightBuffer] -
_waveHeight[_x + 1][_y][_newHeightBuffer])) >> 3;
_offY = ((_waveHeight[_x][_y - 1][_newHeightBuffer] -
_waveHeight[_x][_y + 1][_newHeightBuffer])) >> 3;
If you want to really learn, then I suggest you buy a good book. I am not a teacher, sorry. But this should give a feeling to what is going on.
I create the drops at the beginning so as to speed up a bit and not waste time later calculating positions and sizes for the drops. I fill an array of about 100 drops and later just drop them at random on the bitmap wave array. Here is the code:
private void dropsTime_Tick(object sender, EventArgs e)
{
this.dropsTime.Enabled = false;
int _percent = (int)(0.005 * (this.Width + this.Height));
int _dropsNumber = _r.Next(_percent);
int _drop = 0;
for (int i = 0; i < _dropsNumber; i++)
{
_drop = _r.Next(_drops.Length);
DropWater(_drops[_drop].x, _drops[_drop].y,
_drops[_drop].radius, _drops[_drop].height);
}
this.dropsTime.Interval = _r.Next(15*_percent)+1;
this.dropsTime.Enabled = true;
}
To learn more, download the project and play with it. That is how I learned it and it is the best way to learn anything.
I would like to get my hands on some code which simulates SMOKE. If any of you have seen something out there, please let me know. As you can see when you download it, I posted the code using the same conditions as Don and Tratz.
Enjoy!
History
I just added the C++/CLI managed project which is the same algorithm as the C# version for download for curious programmers.
I know in the C++ version I used RECT-Arrays and I know I implemented all in the header, but this demo is not to teach how to write C++ but to see if Managed CLI C++ can perform as good or better than C#. I know I could have used Internal pointers, Pinned Pointers and True Native pointers but that would defeat the purpose of the test.
