How to interact spheres with random walls

I have a physics problem to deal with, I am asking here because a game developers often uses the efficient method. I have randomly distributed circles interacting to through Lennard-Jones potential or simply with a bounce back boundary condition to wall of random shape, as of know I am taking a V shaped wall. Please help me to understand an efficient algorithm the game developers uses for bounce back interaction.

• Presumably you started by doing research on the topics of collision-detection and collision-resolution before asking a new question, so that we don't need to re-hash material that can already be found elsewhere. Based on your research so far, what algorithm have you selected to try to implement? Where are you currently stuck in understanding or implementing it? Mar 31 '19 at 11:15
• Please see the video. "youtube.com/watch?v=-fq0Xpk1hoI&feature=youtu.be ".(simulation shown is for spheres, with little anomaly at 28 sec) So far I did the simulation of rods made up of spheres connected by springs and by bending force. When these rods hits the walls Bounce back pushes it back, I have done it. Now I am trying to place an arbitrary structure in simulation box , the rods are supposed to interact with the structure. Since the collision is head on, I will need perpendicular distance from structure but I don't understand to how to find it. Mar 31 '19 at 12:00
• So is your question "How to find the perpendicular distance between a circle and a line segment"? Mar 31 '19 at 12:07
• Not exactly sir. My doubt is to how to decide with which line segment of the object the sphere is going to interact with, as the blue object is made up of 6 line segments. Then the perpendicular is distance is fine. thanks Mar 31 '19 at 12:14
• Then it sounds like you're looking for a spatial partitioning strategy, that will help you narrow the list of possible closest objects to check against. What spatial partitions have you tried using so far? Where did you run into trouble putting them into practice here? Mar 31 '19 at 12:37

First off, your wall definition should use a consistent counter-clockwise or clockwise vertex ordering.

This will properly define for each edge which side is 'inside' and which is 'outside.'

Let's assume counter-clockwise ordering: 'inside' is always left of the edge.

To find particle/wall collisions, you just test all edges of the walls, and reflect velocities if the particle is too close to the wall, or on the wrong side of the wall.

For low wall counts, say in the hundreds or less, it is perfectly fine to test each particle against all edges.

If the wall definition becomes too complex, you want to reduce the number of tests. This is done via spatial indexing.

The simplest form of spatially indexed world, is a uniform grid. Just list all walls present in each grid cell.

If the walls are very sparse, or range in sizes, you could consider a quad-tree instead.

To calculate whether a point is on the left or the right side of an edge, I use a 2d cross product, like so:

/* tells if vec c lies on the left side of directed edge a->b
* 1 if left, -1 if right, 0 if colinear
*/
int left_of( cpVect a, cpVect b, cpVect c )
{
const cpVect tmp1 = cpvsub( b, a );
const cpVect tmp2 = cpvsub( c, b );
const float x = cpvcross( tmp1, tmp2 );
return x < 0 ? -1 : x > 0;
}


If you need to further accelerate the code, you should look into vectorized code via SIMD. You can test 8 particles against a single wall, or 8 walls against a single particle by using AVX vector instructions.

• There is this kind of worst case event where the sphere comes right into the mouth of a concave element - basically right into the mouth of a V. It could turn into a pretty messy series of rapid bounces and jitter I imagine if you don't watch out. Apr 1 '19 at 23:30