2

I'm writing a code for the Discrete Element Method where I have balls (spheres) and walls (planes) interacting with each other.

Those simulations are run for billions of time steps, so performance here really matters. Right now, I'm considering different designs and am not sure which one is the best.

I'll try to explain them and my doubts.


Alternative 1 - probably the best for maintainability

One class for the balls:

class Balls:
   /* contains:
  geometry
  forces
  positions
  velocities
  etc.
  of balls */

One class for the walls:

class Walls:
   /* contains:
  geometry
  forces
  positions
  velocities
  etc.
  of Walls */

An assembly which also contains the solver:

class Assembly:
  /* contains:
  balls object
  walls object
  other parameters for the assembly

  Solver:
   method to compute interactions balls-balls and walls-balls
   method to advance time (time integration)

The question here is, how do I get the less overhead? The solver has to access almost all attributes of the other two classes. Shall I write getters or declare the World class as friend of the other two?

Alternative 2 - could become a mess

A solver class:

class Solver:
  /* Contains:
  some solver related parameters (e.g., step size)
  Two methods:
   method to compute interactions balls-balls and walls-balls
   method to advance time (time integration)

An assembly class which contains all the definitions of the walls and balls

class Assembly:
  /* contains basically all attributes of the two 
  classes Walls and Balls shown in the alternative 1 and 
  a method which calls the two methods of the class solver
  by passing the balls/walls attributes by reference */

Also here, is it then better to pass the attributes by reference, to declare the World class as friend of the Solver class, or to use getters?

Alternative 3 - the less maintainable

Combine everything in just one class (not really considered).


Finally, what's the design that reduce the most the overhead? Can you suggest any better design than mine?


EDIT: to be noted is that in the classes Balls and Walls I would store everything in one object. So an object Balls balls will contain for example (if the whole assembly only contains 2 balls):

vector<Eigen::Vector3d> ball_positions = {Eigen::Vector3d(x1,y1,z1),
                                          Eigen::Vector3d(x2,y2,z2)}
vector<double> ball_radii = {r1,r2}
  • 1
    First idea to come to mind: Ball and Walls as structs instead of classes, stored contiguously so they stay in cache. Also, can you do computations in GPU (pass data as a uniform array or texture, and write a fragment or compute shader, for example)? You could aks people on gamedev, that sounds right up their alley. – Theraot Nov 29 at 18:45
  • I found an open source C++ project that could be of use: cryphous. Description: "Fluid simulation engine and fluid rendering engine for real-time applications." Demo video. – Theraot Nov 29 at 19:10
  • You may also be interested in: NVIDIA CUDA realtime particles demo. – Theraot Nov 29 at 19:14
  • 2
    Yes, you should not crosspost. However, first thing gamedev people will ask is what have you tried, thus, it would not be exactly the same question. Second thing is that they will tell you that you do not need to check every ball against every ball for collisions, have a search: optimize collision detection (you only need to check balls that are close enough). If you really need forces applied from all balls, compute use a vector field from them (O(n), well O(n*m), m is resolution), then use it to update them (O(n)). – Theraot Nov 29 at 22:12
  • 1
3

If performance is at stake, the only way to know for sure is to benchmark.

Alternative 1 has the advantage of being easily extensible, if you would use polymorphism:

class SimulationObject {
    // common properties 
    // virtual functions for anything that changes according to real objects
}; 

class Sphere: public SimulationObject {
    ...
};
class Wall: public SimulationObject {
    ...
};

Virtual functions have a minor overhead since there is an extra indirection (not a big deal for modern CPUs). But this can be neglected compared to additional conditional statement needed to vary behavior depending on type.

You may use double dispatch to cope very effectively with the combinatorial explosion of possible interactions between different kind of objects. Today it's only spheres and balls; but what when you have spheres, cubes and walls? where spheres could bounce on other spheres or cubes before hitting the wall?

The other alternatives do not really seem sustainable to me. And I'm not sure that the performance would be higher, if you have to go through long chains of conditionals to figure out what specific case in which specific interaction/combination.

  • 1
    Thanks. You're indeed right. Thanks for your interesting inputs. I think double dispatch is more useful in event driven simulations. In my case I have (unfortunately) a situation where I have to check contact of every balls with every other simulation object, so I have O(n^2) time complexity (the only solution to reduce the cost a little bit is to use so called Verlet Lists) – David Nov 29 at 21:49
  • @David thanks for the interesting feedback. If I understand this data structure, it keeps a reduced list of objects in range. I could imagine that if you have more than 2 kind of objects, double dispatch could still help on the reduced set. – Christophe Nov 29 at 22:15
  • still a last question before accepting your answer. Would you then use getters to access attributes from the solver, or declare the Assembly class as friend? – David Dec 2 at 7:53
  • 1
    @David I'd use getters and setters, since those enable the polymorphism and will facilitate maintenance. Having assembly as friend is in reality a disguised variant of alternative 3. – Christophe Dec 2 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.