   Circular particle system optimization
  For a little background.  My particle system has one purpose and that is to simulate particles moving around in a circle with the ability to apply electromagnetic forces to them.  Because of the math involved and possibly the way I'm doing things, i can only render about 1500 particles at a time with 60+ fps.  As far as I can tell, the major hit to performance is when I'm applying the magnetic forces as it can add a lot of extra computation with 1 or more forces.  I will be updating the rendering to VBOs soon enough (i hope :P) but rendering tiny particles isn't that demanding.In a nutshell, I'm wondering if there is a better way of doing things.  I've done as much optimizing as I know; reducing computations to as little as possible and whatnot.Here's the source://Particle variablestypedef struct{float cprf_X_C;float cprf_Y_C;int cpri_Width_C;int cpri_Height_C;float cprf_Velocity_I;float cprf_rVelocity_I;float cprf_Angle_I;int cpri_Type_I;int TexNum;int ExpNum;} PParticle;f180_PI = 180 / PI;fPI_180 = PI / 180;fPI_360 = 360 * fPI_180;// cirlce(x, y, radius)float cprf_cX_C;float cprf_cY_C;float cprf_Radius_I;    do{pAngle = Particle.cprf_Angle_I;pX = Particle.cprf_X_C;pY = Particle.cprf_Y_C;// Apply all magnetic forcesfor (a = 0; a < Magnet.size(); ++a){// Get the range between the magnet and the particlemX = Magnet[a].cprf_X_C - pX;mY = Magnet[a].cprf_Y_C - pY;mRange = (mX * mX) + (mY * mY);// Check to see if the particle is within the radius of the magnetif (mRange <= Magnet[a].cprf_sRadius_I){// Apply force to particlerfast_inv_sqrt(mRange);mVel = Magnet[a].cprf_Magnitude_I * mRange;pX += (mX * mRange) * mVel;pY += (mY * mRange) * mVel;}}// Find objective x and y coordinates or where the particle wants to gomX = ((cprf_Radius_I * cos(pAngle)) + cprf_cX_C) - pX;mY = ((cprf_Radius_I * sin(pAngle)) + cprf_cY_C) - pY;// Apply the circular force to the particle trying to keep it in a ringmag = fast_inv_sqrt(sqrt((mX * mX) + (mY * mY)));mVel = Particle.cprf_Velocity_I;Particle.cprf_X_C = pX + ((mX * mag) * mVel);Particle.cprf_Y_C = pY + ((mY * mag) * mVel);Particle.cprf_Angle_I += Particle.cprf_rVelocity_I;if (pAngle > PI2){Particle.cprf_Angle_I -= fPI_360;}else if (pAngle < 0){Particle.cprf_Angle_I += fPI_360;}wX = pX + Particle.cpri_Width_C;wY = pY + Particle.cpri_Height_C;glTexCoord2f(0.0f, 1.0f); glVertex2f (pX, pY);glTexCoord2f(0.0f, 0.0f); glVertex2f (pX, wY);glTexCoord2f(1.0f, 1.0f); glVertex2f (wX, pY);glTexCoord2f(1.0f, 0.0f); glVertex2f (wX, wY);++i;} while (i < pSize);*updated the sourceThanks in advanceJake[Edited by - jake_Ghost on June 1, 2008 6:18:04 AM]
  Probably the horrid framerates are because you're rendering each one singularly and with severely unoptimized fashion. You should treat glBegin()/glEnd() as expensive operations (mostly because they are), and call them as little as possible.Try using the point sprite extension, or using a vertex buffer that you update during the particle pass and then draw in a single call. If the latter, try using a single triangle for each particle and use "triangle list" as the vertex buffer mode, to save you also needing an index buffer or using two triangles per particle  in a triangle list.   ;  Thanks for some info on rendering, that's my next step.  But here are some of the numbers I have.Rendering and doing positional computations I can get 60fps at 1500 particles.Doing just the calculations i can have 1800 particles at 60fpsWith just rendering i have about 9400 particles at 60fps.  With VBOs or maybe instancing? i could probably push that to maybe 20 000 or so, maybe higher.  I dont know much about instancing though.My big problem is with applying the positional calculations.  It just totally kills my fps.   ;http://www.nvidia.com/object/cuda_home.html   GPU  parallel programming  nvidia stuffI found this the other day and am still looking at what class of problems it can be applied to.   Your type of particle processing  sound like one type it would work well with (especially if you can do it all in the GPU -- many of the example uses require constant loading/unloading data from the GPU);  Eliminate unnecessary / redundant sqrt calls and multiplications.Consider adding an additional attribute to your Magnet struct holding the squared radius.Consider adding another attribute for precomputing Magnet::vVelI assume there are much less magnets than particles in your system. Consider making the Magnet-for-loop the outer loop (by that you could also precompute the Magnet stuff mentioned above without adding attributes to the struct).Consider making the particle-do-while-loop running forward.Depending on your compiler it's worth to remove some indirections (e.g. PParticle &l_particle=Particle;)By the way: this one is definitely a candidate for parallel computingif your target platform supports multiple cores.[Edited by - Last_Inquisitor on May 31, 2008 4:47:51 AM];  Thanks a lot guys.  It's getting really late so I'm gonna look at that nvidia thing tomorrow.  I really missed some simple things with the sqrt lol.  Time to take a break :D   ;  In addition to removing redundant sqrts you might want take a look at fast inverse sqrt and changemag = sqrt((mX * mX) + (mY * mY));mX /= sqrt(mag);mY /= sqrt(mag);tomag = fast_inv_sqrt(sqrt((mX * mX) + (mY * mY)));mX *= mag;mY *= mag;;  As mentioned, the first sqrt is not required for comparing it's distance.  Simply store th radius squared and use that to compare (sqrt's are very slow).  Also, rather than /= sqrt(mag) twice, why not just do...mag = 1/(sqrt(sqrt(mX*mX + mY*mY));mX *= mag;mY *= mag;Also, for quick testing of your drawing code, rather than doing a triangle strip, do a GL_QUAD, and only call glBegin and glEnd once per frame (begin before your loop, and end after the loop), this will cut your gl function calls down quite a bit without going to in depth about buffers and such.Also probably mentioned already,  you can pre-calculateMagnet[a].cprf_Magnitude_I * Magnet[a].cpri_Force_I;So it would change to:mVel = Magnet[a].cprf_Magnitude_X_Force_I / mRange;I haven't put to much thought forth yet, but there should be a way to apply all the forces before doing your sqrt's on mX & mY.  Rather than doing them once per magnet and once per particle.  Something like this:mVelQuad = mVel*mVel*mVel*mVel;  //since it gets sqrt'd twice ;)TotalmX += vPos.x * mVelQuad;TotalmY += vPos.y * mVelQuad;Then you would have Particle.cprf_Velocity_Quad_I precaulculated, so you can use it after the magnet loop, then in your final step...TotalmX += (oX - Particle.cprf_X_C)*Particle.cprf_Velocity_Quad_I;TotalmY += (oY - Particle.cprf_Y_C)*Particle.cprf_Velocity_Quad_I;mag = 1/(sqrt(sqrt(TotalmX*TotalmX + TotalmY*TotalmY));TotalmX *= mag;TotalmY *= mag;Particle.cprf_X_C += TotalmX;Particle.cprf_Y_C += TotalmY;This would make it a maximum of 2 sqrt's per particle, rather than 2 per magnet per affected particle + 2 per particle + one for each particle compare!  That is a LOT of cut-backs even with 1 or 2 magnets.;  You could use SSE, you would need to change your data structures but you would see a significant speed increase.   ;  Thanks a lot guys.  Tremendous help :D!  So far I've changed a few things and I'm working on the all in one magnetic force :P.I do like my sqrt lol, but unfortunately some of them i need to do : (.  The one on the range i have changed a bit but w/o the sqrt(mRange) the particles dont reactor properly to the forces.  But so far, i am now running about 2200 particles at 60fps, so thats a 700 particle increase :D.  Not toooo shabby if you ask me.My goal is 4000 particles total which will be sufficient for what i need.  I am well on my way now.Moomin would you be able to explain a little what SSE is?