Particle transformation too slow?

First of all, eliminate your divisions. Instead of dividing by 4, multiply by 0.25. Your compiler may be optimizing this anyway, however, I'm not sure.

Secondly, you're performing [color=#1C2837][font=CourierNew, monospace][size=2][color=#000000]cos[color=#666600](([color=#000088]float[color=#666600])[color=#000000]m_Time[color=#666600]/[color=#006666]4[color=#666600])[/font]multiple times. Trigonometric functions are expensive. Do it only once.

Thirdly, depending on your target platform, look into using SIMD (SSE2) operations for your matrix and vector transformations.

First of all, eliminate your divisions. Instead of dividing by 4, multiply by 0.25. Your compiler may be optimizing this anyway, however, I'm not sure.

Secondly, you're performing cos((float)m_Time/4)multiple times. Trigonometric functions are expensive. Do it only once. [/quote]

Thanks, I changed cos to only be used once, and it gave me a little boost of 1-2 FPS. talking about 15 FPS average, thats not bad.

Thirdly, depending on your target platform, look into using SIMD (SSE2) operations for your matrix and vector transformations. [/quote]

Thx, I'll try SIMD out. But what about SSE3+? Should I stick to SSE2 like you suggested or are there huge benefits in using newer SSE?

Honestly I don't know much about the details of SIMD implementations, I just know what they are and what they do. If you have SSE3+ available to you, I guess I don't see why you'd use it Maybe someone more knowledgeable can answer.

BTW, I don't know what your platform is, but if it's windows you have the XNA Math library available to you. That's set up to use SIMD operations.

Frankly, if you want a fast particle system then you are Doing It Wrong.

Class for a particle is bad for many reasons including;

• lack of ability to do SIMD transforms on multiple particles at once
• the cost of jumping into the 'update' function (made worse if you've made it virtual) to update one particle
• loading too much data for that update, most of it useless, thus trashing the cacheThat 'move' function looks very suspect... almost like you have one matrix per particle?!? If so... dear god... instead you'd want an 'emitter' which has a base position and everything moves relative to that and that is done via the GPU (frankly, if you have one matrix per particle I dread to see your drawing code...).
  
  If you are after performance then you'll want to go and read up on Data Orientated Design (aka DOD) for which particle systems are perfect for.
  
  And, to give you an idea, on a 2.6Ghz i7, using 8 threads and SIMD updates I managed to transform 1 million 2D particles in <4ms using DOD methods and code constructs, which is ~1ms for 250,000 particles (at which point I ran into problems uploading the data to the GPU to draw).
  
  
  

Link:
http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

Before hodgman links it. I'm sure he's probably starting to get bored about this ;-)

The D3DX stuff already uses SIMD internally if it's available on the PC.

Assuming that you're just billboarding particles you don't need to eval a full transform for each. At the most basic level, all that you need as per-instance data is a 3-float position and a colour. Then you can extract the forward, up and right (or left as appropriate) vectors from your view matrix, set them once to your shader for all particles, and perform billboarding in your vertex shader. Faaaaaast.

Note that with particles fillrate is also going to be a major bottleneck, so even the lowest overhead elsewhere won't do much to ameliorate that.

The D3DX stuff already uses SIMD internally if it's available on the PC.

While that is true there is two levels of SIMD;

1. Using a maths function which uses SIMD instructions internally to speed things up (D3DX and XNA Math for example) which would otherwise have taken longer via the FPU
2. Laying out your data in such a way as to process multiple pieces of data at once in each operation

The first is easy to do and with things like XNA Math around on the PC should be something people consider doing all the time. However while faster it doesn't really take advantage of the streaming nature as well as the second one can in certain cases, and a particle system is a good example of this.

Particle system updates are nicely seperatable, so what happens to the 'x' of it's position is independent to what happens to the 'y'. Using this knowledge if we make two buffers, one which holds all the 'x' components and one which holds all the 'y' then using SSE we can do a single cache friendly pass over the 'x' data and a single cache friendly pass over the 'y' data and update four particles per instruction.

So, your update loop becomes something like;

[source]
struct ParticleInfomation
{
float * __restrict x;
float * __restrict y;
float * __restrict scale;
float * __restrict momentumX;
float * __restrict momentumY;
float * __restrict velocityX;
float * __restrict velocityY;
float * __restrict age;
float * __restrict maxAge;
float * __restrict colourR;
float * __restrict colourG;
float * __restrict colourB;
float * __restrict colourA;
float * __restrict rotation;
// some functions for dealing with instances of this class
}

// i is the particle count which increments by 4, there is always a multiple of 4 particles alive in the world if any are alive

__m128 posX = _mm_load_ps(particleData.x + i);
__m128 posY = _mm_load_ps(particleData.y + i);
__m128 velX = _mm_load_ps(particleData.velocityX + i);
__m128 velY = _mm_load_ps(particleData.velocityY + i);


__m128 momentumsX = _mm_load_ps(particleData.momentumX + i);
__m128 momentumsY = _mm_load_ps(particleData.momentumY + i);

momentumsX = _mm_add_ps(momentumsX, velX);
momentumsY = _mm_add_ps(momentumsY, velY);
velX = _mm_setzero_ps();
velY = _mm_setzero_ps();

__m128 time = _mm_load1_ps(&deltaTime);
_mm_stream_ps(particleData.velocityX + i,velX);
_mm_stream_ps(particleData.velocityY + i,velY);
_mm_stream_ps(particleData.momentumX + i,momentumsX);
_mm_stream_ps(particleData.momentumY + i,momentumsY);

momentumsX = _mm_mul_ps(momentumsX, time);
momentumsY = _mm_mul_ps(momentumsY, time);

posX = _mm_add_ps(momentumsX, posX);
posY = _mm_add_ps(momentumsY, posY);

_mm_store_ps(particleData.x + i, posX);
_mm_store_ps(particleData.y + i, posY);
[/source]

Which processes both X and Y in groups of four particles at once.

Edit:

Oh, and I forgot to mention what makes this good;

- Firstly the source memory is cache aligned to that as soon as you touch the first block you read in a whole cache line of 'x' and 'y' values, which with an i7 and it's 64byte line size gets you 16 values or four loops over the data at a time
- Secondly, because the CPU will prefetch data based on expected access patterns chances are the next 8 values will also be in cache somewhere when you get to need them

I will say this much however, the routine above isn't completely finished and optimised and there is a chance that doing all the updates then doing all the position calcs would be faster and more cache friendly but I've not had a chance to look at it yet (nor get myself a decent profiler to find out for certain).

I personally let the GPU handle all particle transformations..

The post i a little ill-formatted (was posted on the old forum format) but I did a post early last year on another particle type where I include GPU transformation/scaling/rotating of particles (http://www.gamedev.net/topic/562581-billboarded-sprite-transform/page__p__4606417#entry4606417 for the reference)

The big downside is the Fat vertex data since I had to include position, scale and rotation (around Y axis) data. But it meant I could do one draw call per blend type for any number of particles and let the GPU transform, rotate and scale the particle.

The D3DX stuff already uses SIMD internally if it's available on the PC.

Assuming that you're just billboarding particles you don't need to eval a full transform for each. At the most basic level, all that you need as per-instance data is a 3-float position and a colour. Then you can extract the forward, up and right (or left as appropriate) vectors from your view matrix, set them once to your shader for all particles, and perform billboarding in your vertex shader. Faaaaaast.

Note that with particles fillrate is also going to be a major bottleneck, so even the lowest overhead elsewhere won't do much to ameliorate that.

XNAMath is what you want to use for SIMD. D3DXMath uses SIMD instructions but has to do a load/store conversion, while XNAMath explicitly uses optimally-aligned hardware register data types.

Again, like I said, you only need 3 vectors (you could get away with two) to billboard particles on the GPU, and these only need to be set once per frame irrespective of how many particles you're drawing. SIMD may be relevant for CPU work, but if you're (a) doing the stuff where SIMD is relevant only once per frame, and (b) doing the actual transforms on the GPU where SIMD doesn't apply, then optimizing for SIMD instructions will get you sweet zip.

Remember - a GPU is not a CPU and rules that apply to one don't necessarily apply to another. Also remember that it's the 21st century and we're in hardware T&L land these days. This is a whole different country and interleaving separate vertex streams in hardware may actually slow you down quite a bit. GPUs like to get all data for a vertex in one single chunk and will process multiple vertexes in parallel. You've got that capability - why waste time with optimizing for software T&L? Advice that seems targetted at 1990s techniques and software T&L seems dubious at best and misleading at worst. And finally there is what I said about fillrate - you can only get theoretically so far with all of this before fillrate becomes your bottleneck, especially with particle systems.

Well thanks for all the suggestions and explanations, I'll check it all out. DOD and GPU transform seems to be what I'm looking for (I'm quite aware my particle system is far from being perfect). My goal was being able to use 1.000.000 particles on my PC with a Core2Duo E8400 and 2xGeforce 260 Gtx. If I manage to get that, I won't spend much effort in improving any further, as I'm going to have less particles (I think 50.000 like I'm now able to do with 30 FPS is what will be used on average). I'll check out all the sources you posted and see how I can get it to work. Instancing did a great job, it gave me four times the performance, so I think with all this I should be fine for reaching my goal.

I'd definitely recommend GPU transforms then; I can manage 30 FPS with 60k particles on the Intel-equipped office PC I'm using at the moment (and that doesn't even support instancing) using GPU transforms. A real GPU will be getting a lot more. Here's the guts of the vertex shader I'm using to get you started:

float3 up = viewup * Input.Tex0.y;
float3 right = viewright * Input.Tex0.y;
float2 BasePosition;

if (Input.Tex0.x == 0)
{
BasePosition = float2 (-1, -1);
Output.Tex0 = float2 (0, 0);
}
else if (Input.Tex0.x == 1)
{
BasePosition = float2 (-1, 1);
Output.Tex0 = float2 (1, 0);
}
else if (Input.Tex0.x == 2)
{
BasePosition = float2 (1, 1);
Output.Tex0 = float2 (1, 1);
}
else
{
BasePosition = float2 (1, -1);
Output.Tex0 = float2 (0, 1);
}

float4 NewPosition = float4
(
float3 (Input.Position.xyz + right * BasePosition.x + up * BasePosition.y),
Input.Position.w
);

Output.Position = mul (NewPosition, WorldViewProjMatrix);