   Drawing lots of particles
  I am trying to draw a bunch of particles (represented by colored circles) to the screen in a pseudo-3d view using SDL/SGE.The process I came up with is:* Create a transformation matrix to convert from simulation space to the camera's point of view* For each particle, multiply the position vector by the transformation matrix, and store the results in a list, along with the radius and color of the particle.* Sort the list by z value* For each record in the list, draw a circle, scaling and translating appropriately to fit on the screen.Here is the code I came up with, but I feel like I am doing something horribly wrong. What is the correct way to do what I am trying to do? What do I need to change or redesign?display functionvoid PhySim::display(SDL_Surface* outputsurface,int xoffset, int yoffset){    std::vector<DrawOrder>::iterator it;    std::vector<DrawOrder> orders;    DrawOrder* tempDO;    V3<double> tempV;    double scale=0;    if (visible) //visible is inherited from gObject    {   scale = 0;   for ( p_it=gasp.begin() ; p_it < gasp.end(); p_it++ )   {  if (*p_it != NULL)  { tempV = cam_basis * ((*p_it)->P-Center); //width and height are also inherited from gObject if ( fabs(tempV.x) * scale > width/2) {scale = width/(2*fabs(tempV.x)); } if ( fabs(tempV.y) * scale > height/2) {scale = height/(2*fabs(tempV.y)); } *tempDO = DrawOrder( tempV.x, tempV.y, tempV.z, (*p_it)->r, (255<<16 | 255<<8 | 255)); //I'll just use white for all of them until I implement colored particles orders.push_back( *tempDO) ;  }   }   scale = scale * .97; //to leave a little margin at the sides   std::sort(orders.begin(), orders.end(), DrawOrderComparison);   for ( it=orders.begin() ; it != orders.end(); it++ )   {  Draw_FillCircle(screen, xoffset + width/2 + scale * it.x, yoffset + height/2 + scale * it.y  ,it.r * scale ,it.color);   }    }}bool DrawOrderComparison (DrawOrder a,DrawOrder b) { return (a.z<b.z); }particle.h#ifndef GASPARTICLE_H#define GASPARTICLE_H#include "guiclasses.h"#include "3vector.h"#include <vector>#include <string>///////////////////////////////////////////////////////////////*Mass and radius valuesHe: 4.002602    31Ne: 20.1797    38Ar: 39.948    71Kr: 83.798    88Xe: 131.293    108*/class Particle{    friend PhySim;    double mass,r; //r = radius    V3<double> P,V, newP; //P = position, V = velocity, newP is a temp vector used in movement calculations    std::vector<Wall*> bounds;    std::vector<Wall*>::iterator b_iter;    //gImage* myimg;    void wallCollision( Wall*, double);    public:    Particle();    ~Particle();    //void showInFrame( gFrame*);    void setType(int);    void setPos(double a, double b,double c)    {   P.set(a,b,c);   }    void setVel(double a, double b,double c)    {   V.set(a,b,c);   }    void Move(double);    void addBound (Wall* newbound)    {   bounds.push_back(newbound); }    bool checkCollision( Particle*);};class Wall{    friend Particle;    V3<double> N;    double c; //distances from origin    double speed; //rate at which c is changing    double target;    public:    Wall(double nx,double ny, double nz, double nc)    {   N=V3<double>(nx,ny,nz);   c=nc;   speed=0;   target=c;    }}class DrawOrder{    public:    double x;    double y;    double z;    double r;    int color;    DrawOrder(double ax, double ay, double az, double ar, int ac)    {   x=ax;   y=ay;   z=az;   r=ar;   color=ac;    }}class PhySim: public gObject{    std::vector<Particle*>::iterator p_it;    std::vector<Particle*> gasp; //the particles in the box    V3<V3<double>> cam_basis; //the transformation matrix of the camera    V3<double> Center; //the center of the box    double x1,x2,y1,y2,z1,z2;    double simspeed;    Wall* walls[6];    public:    PhySim(double,double,double,double,double,double);    void addParticle(int=0);    void update(double);    void display(SDL_Surface*,int=0,int=0);};#endif3vector.h#ifndef VECTOR3D_H#define VECTOR3D_Htemplate <class T>class V3{    public:    T x,y,z;    V3(){};    V3(T nx,T ny,T nz)    {   x=nx;   y=ny;   z=nz;    }    V3 operator + (V3 other)    {   return V3(x+other.x, y + other.y, z+other.z);    }    V3 operator - (V3 other)    {   return V3(x-other.x, y - other.y, z-other.z);    }    T operator * (V3 other)    {   return (x * other.x + y * other.y + z * other.z);    }    V3 operator * (T scalar)    {   return V3(x * scalar, y * scalar, z * scalar);    }    V3 operator / (T scalar)    {   return V3(x / scalar, y / scalar, z / scalar);    }    void set(T nx,T ny,T nz)    {   x=nx;   y=ny;   z=nz;    }};#endif[Edited by - Storyyeller on May 18, 2009 5:48:57 AM]
  Don't use linked lists for particles, keeping them allocated separately is also often not necessary. Use vector, and pre-size it to number of particles. Sorting and iterating that is an order of magnitude faster. There was some discussion regarding this this. This also simplifies concurrent merge or radix sort.For rendering itself, read this. The article isn't really beginner stuff, but at least it touches on many important points.   ;  What do you mean by keeping particles allocated separately? I'm confused.Also, I edited the post to change it to a vector like you suggested.[Edited by - Storyyeller on May 18, 2009 5:35:19 AM];  Ok, after a lot of debugging, I finally managed to get the code mostly working.The only major problem is thisV3<double> tempV;CamBasis = V3< V3<double> >(V3<double>(1,0,0),V3<double>(0,1,0),V3<double>(0,0,1));CamTarget = V3<double>(0,0,0);tempV = CamBasis * CamTarget;It won't work and I can't figure out why. Did I overload the operators incorrectly or what?One other concern I had was this if (tempDO != NULL) {delete tempDO; } tempDO = new DrawOrder( tempV.x, tempV.y, tempV.z, (*p_it)->r, (*p_it)->color); orders.push_back( *tempDO) ;Is this really how you are supposed to populate a vector with objects? I keep feeling like I am leaking memory somewhere.   ;  You are using a lot of pointers, and you are storing things as members that could be locals.Here is a quick pass over the header file.// I added these to the end of the vector header.// Typenames should be easy to read and understand.// I find Vector3 much more manageable than V3<double>, even just to type.typedef V3<double> Vector3;typedef V3<Vector3> Matrix33;#ifndef GASPARTICLE_H#define GASPARTICLE_H#include "guiclasses.h"#include "3vector.h"#include <vector>#include <string>//////////////////////////////////////////////////////////////class Wall{    // Don't abuse friendship    // friend Particle;    Vector3 normal;    double c; //distances from origin    double speed; //rate at which c is changing    double target;public:    // Prefer initialiser lists in constructors.    // Google the term "initalizer list C++" for more information.    Wall(double nx,double ny, double nz, double nc)    :   normal(nx,ny,nz),   c(nc),   speed(0),   target(c)    {    }};/*Mass and radius valuesHe: 4.002602    31Ne: 20.1797    38Ar: 39.948    71Kr: 83.798    88Xe: 131.293    108*/class Particle{    //friend PhySim;    // Don't say r = radius, P = position, V = velocity .    // Just call the members radius, position and velocity :)    double mass, radius;    Vector3 position, velocity;    // Hint: if something can be described as "temp"    //  then it should be a local.    // newP; // newP is a temp vector used in movement calculations  // Let the particle system handle the wall bounds.    // Just pass the walls you are interested to the particles    // This saves storage    //std::vector<Wall*> bounds;public:    Particle();    // Don't write destructors if you have no resources to release    // ~Particle();    // I have no idea what this function does.    void setType(int);    // Why "a, b, c"... Aren't "x, y, z" more obvious and intuitive?    void setPos(double a, double b,double c)    {   position.set(a,b,c);   }    void setVel(double a, double b,double c)    {   velocity.set(a,b,c);   }    void Move(double);    // Unless an argument is allowed to be NULL, use a (const) reference.    bool checkCollision(const Particle &);    bool checkCollision(const Wall &);};class DrawOrder{public:    // Could this x,y,z triplet be represented by a Vector3?    double x;    double y;    double z;    double r;    int color;    DrawOrder(double ax, double ay, double az, double ar, int ac)    :    x(ax), y(ay), z(az), r(ar), color(ac)    {    }};// What is a "g" Object? GameObject? Be explicit, especially with type names// Consider a better name for PhySim (PhysicsSimulator or whatever)class PhySim: public GameObject{    // store the particles by value    typedef std::vector<Particle> Particles;    // The typedef will come in handy when you want to define iterators.    // Just use Particles::const_iterator    // "gasp" is a terrible member name. I have no idea what it represents.    Particles particles;    Matrix33 cam_basis; //the transformation matrix of the camera    Vector3 Center; //the center of the box    // Can these be vectors?    // And can they be local?    double x1,x2,y1,y2,z1,z2;    double simspeed;    // Again, store by value if possible.    Wall walls[6];public:    // Try to put a little documentation in the header files    // I don't want to have to find the source file to tell me what order    // the constructor parameters are in.    PhySim(double,double,double,double,double,double);   // And I have no idea what addParticle(42) will do either.    void addParticle(int=0);    void update(double);    void display(SDL_Surface*,int=0,int=0);};#endifAnother thing, anywhere you are passing an x,y,z triplet to a constructor or function: ask youself why aren't you passing a Vector3?   ;Quote:Is this really how you are supposed to populate a vector with objects? I keep feeling like I am leaking memory somewhere.You probably are (too tired to make sure). You can just use a temporary instead:// Naming the iterated value can improve readabilityconst Particle &particle = **p_it;// This assumes you change the DrawOrder constructor to accept a vectororders.push_back(DrawOrder( tempV, particle.r, particle.color)) ;// Don't forget: p_it should be local!As for your overloading issue, look at the V3 class. It has two operator * implementations. In the case where T = V3, it actually has two functions with the same signature. That isn't going to work.I would recommend having a separate Matrix class.   ;  // Hint: if something can be described as "temp"    //  then it should be a local.    // newP; // newP is a temp vector used in movement calculationsI was going to make it local, but the Move function calls wallCollision, and I thought this would be better then just passing it by reference to every single timeI set it up to call wallCollision in the middle becuase it uses interpolated (exact) collision detection for the walls so it needed to know where it would move to before it could finish moving.// Let the particle system handle the wall bounds.    // Just pass the walls you are interested to the particles    // This saves storage    //std::vector<Wall*> bounds;I'm confused    // Don't write destructors if you have no resources to release    // ~Particle();Originally, each particle has a SDL_surface, but I got rid of that and never bothered to get rid of the destructor. I fixed it now.    // I have no idea what this function does.    void setType(int);It gives the particle a radius and mass of the associated element ( 0= Helium, 1 = Neon, 2 = Argon, 3= Krypton, 4 = Xenon)    // Unless an argument is allowed to be NULL, use a (const) reference.    bool checkCollision(const Particle &);    bool checkCollision(const Wall &);The problem is that it also mutates both particles in the case of a collision. I guess checkandprocessCollision would be a better name, but it is a bit long    // Could this x,y,z triplet be represented by a Vector3?    double x;    double y;    double z;Technically, it could be but there is no logical reason to, because all of the elements are meant to be accessed individually so it would just add an extra layer of indirection for no reason.// What is a "g" Object? GameObject? Be explicit, especially with type names// Consider a better name for PhySim (PhysicsSimulator or whatever)It stands for GUI Object, but you are right about me not being good at naming things.    // "gasp" is a terrible member name. I have no idea what it represents.    Particles particles;Why give two things the same name (not counting capatilization)? It seemes like a weird practice that might lead to confusion later on.    // Can these be vectors?    // And can they be local?    double x1,x2,y1,y2,z1,z2;They are the sides of the box. I don't think they can be local because they represent the state of the object. I guess if using vectors were important, the best way would be to create 8 vectors (one for each corner) and use those. But that seems a bit complicated.    // Try to put a little documentation in the header files    // I don't want to have to find the source file to tell me what order    // the constructor parameters are in.    PhySim(double,double,double,double,double,double);Good point// And I have no idea what addParticle(42) will do either.    void addParticle(int=0);It adds a particle at random position and velocity having the specified typeAs for the template thing,is there anyway to make it return a variable where the type depends on the behavior of T's operators?[Edited by - Storyyeller on May 18, 2009 8:46:05 PM];  This forum has "quote" tags, much like source tags. Using them makes it easier to read your post and figure out where you are responding to others.Quote:Original post by Storyyeller// Hint: if something can be described as "temp"//  then it should be a local.// newP; // newP is a temp vector used in movement calculationsI was going to make it local, but the Move function calls wallCollision, and I thought this would be better then just passing it by reference to every single time I set it up to call wallCollision in the middle becuase it uses interpolated (exact) collision detection for the walls so it needed to know where it would move to before it could finish moving.I'm not sure I understand. Keeping it as a member and passing it to wallCollision() are functionally equivalent, but the latter saves memory.Quote:// Let the particle system handle the wall bounds.// Just pass the walls you are interested to the particles// This saves storage//std::vector<Wall*> bounds;I'm confusedIts simple: individual particles don't store the walls. Instead, when you call collide() or move() or whatever, you can pass a reference to the wall container from the calling class.This saves on memory.Quote:// Don't write destructors if you have no resources to release// ~Particle();Originally, each particle has a SDL_surface, but I got rid of that and never bothered to get rid of the destructor. I fixed it now.That is fine.Quote:// I have no idea what this function does.void setType(int); It gives the particle a radius and mass of the associated element ( 0= Helium, 1 = Neon, 2 = Argon, 3= Krypton, 4 = Xenon)I would suggest you use an enumerated type, an "enum":enum ElementType{    HELIUM, NEON, ARGON, KYRPTON, XENON};I would also take the "ElementType" as a constructor parameter rather than using "setType".Quote:// Unless an argument is allowed to be NULL, use a (const) reference.bool checkCollision(const Particle &);bool checkCollision(const Wall &);The problem is that it also mutates both particles in the case of a collision. I guess checkandprocessCollision would be a better name, but it is a bit longIf it mutates the Particle, then just pass a non-const reference. I would probably call it "handleCollision".Quote:// Could this x,y,z triplet be represented by a Vector3?double x;double y;double z;Technically, it could be but there is no logical reason to, because all of the elements are meant to be accessed individually so it would just add an extra layer of indirection for no reason.This is incorrect, IMO. If the values are logically related, then they should be in a vector. There is only a minor syntactic indirection, but I would argue that is a good thing.Quote:// What is a "g" Object? GameObject? Be explicit, especially with type names// Consider a better name for PhySim (PhysicsSimulator or whatever)It stands for GUI Object, but you are right about me not being good at naming things.// "gasp" is a terrible member name. I have no idea what it represents.Particles particles;Why give two things the same name (not counting capatilization)? It seemes like a weird practice that might lead to confusion later on.Well, it is part of my coding style. I always start a type with an uppercase letter. An instance begins with a lowercase letter. This simplifies the naming, unless I need an explicit name I can just use "Type type". So, I have a Renderer called "renderer", anonymous Entities are called "entity" and so on.Quote:// Can these be vectors?// And can they be local?double x1,x2,y1,y2,z1,z2;They are the sides of the box. I don't think they can be local because they represent the state of the object. I guess if using vectors were important, the best way would be to create 8 vectors (one for each corner) and use those. But that seems a bit complicated.If they are part of the objects state then that is acceptable, but this wasn't clear from the names. A box can be represented by two vectors, max and min. So I would use:Vector3 boundsMax, boundsMin;Quote:// And I have no idea what addParticle(42) will do either.void addParticle(int=0);It adds a particle at random position and velocity having the specified typeI would again use the "ElementType" enum here, rather than a plain integer.Quote:As for the template thing,is there anyway to make it return a variable where the type depends on the behavior of T's operators?That sounds like a brittle approach.Here is a different approach: use non-member functions. These are both more explicit and E.g:/*   the V3 template, minus operator *() */typedef V3<double> Vector3;typedef V3<Vector3> Matrix33;double dot(const Vector3 &one, const Vector3 &two){    return one.x * two.x + one.y * two.y + one.z * two.z;}Vector3 mul(const Matrix33 &matrix, const Vector3 &vector){   // ...}Vector3 mul(const Vector3 &vector, double scalar){   // ...}I would be wary of making binary operator * stand for anything other than simple multiplication. The first issue is readability, someone reading your code has to keep in mind your definition of operator *. But there are other problems, for example operator precedence. I've seen people overload some rather odd operators for dot or cross product. The other issue is operator precedence.