This project is based on the simulation of Rigid bodies and Soft bodies using techniques of concurrency involving the usage of threads and networking.

Simulation Algorithms

Rigid Body Physics

The rigid body simulation in the system is based on the Runge-Kutta (RK4) Integration methodology. This allows an accurate numerical integration with error O(5). It works by evaluating derivatives at multiple points in the time-step.

The linear and rotational parts of an object’s motion are separate in a rigid body motion: a linear component (position, velocity, momentum and mass) and a rotational component rotating about the center of mass (using angular momentum, inertial tensor and torque). The center of mass of the sphere is the weighted average of all points making up the body by their mass. Just as we integrate linear momentum from force, we integrate angular momentum directly from the rotational equivalent of force called torque. (Fiedler)

dp/dt = F (the derivative of momentum is force)

v = p/m (velocity equals momentum divided by mass)

dx/dt = v (the derivative of position is velocity)

dq/dt = spin = 0.5 w q (integration of orientation)

Where q is the current orientation quaternion, and w is the current angular velocity in quaternion form (0,x,y,z) such that x, y, z are the components of the angular velocity vector. Note that the multiplication done between w and q is quaternion multiplication. The liner force and torque hence applied is as follows: (Fiedler)

Flinear = F

Ftorque = F x (P - X)

Where F is the force being applied at point P in world coordinates, and X is the center of mass of the object. Torque is generated based on the cross product of the force vector and the point on the object relative to the center of mass of the object. A frictional force is also added to the forces based on the surface friction coefficient.

Collision Detection/Response

A simple Sphere-Sphere test is done to check if a sphere is inside another. The penetration value and the collision point are calculated. If the point is inside the plane then a penalty force is applied to push the point out. A damping force is also applied to make the collision inelastic otherwise the cube would bounce off plane without losing any energy. Velocity constraint forces are also applied when the point is inside the plane and the point is moving further into the plane. This tightens up the collision response from what would be achieved using penetration depth penalty forces alone giving a more realistic result. An approximation of tangential friction force is also applied.

Collision with ball-to-wall and ball-to-floor is made using plane to point collision detection techniques and then response is based on the penetration amount and the exact collision point (same as ball-to-ball collisions).

Soft Body Physics

The method used to simulate soft bodies is the Pressure Model of Soft Body Simulation (Matyka).

We weave the object using the mass-spring model and then put the source of a wind (gas pressure) force inside it as shown in the figures

Figure 1: Closed shapes woven with spring-mass model (Left). Body filled with Gas (middle). Pressure force inside (Right) (Matyka)

We assume that the body is filled with a gas under pressure P higher than atmospheric pressure P₀. Due to pressure difference an additional pressure force, that keeps the body shape, exists.

In order to approximate the pressure force, we assume that the body is large in comparison to gas particles and utilize the ideal gas law that balances pressure P and volume of the body V:

PV = nRT,

where R is the gas constant. An amount of the gas (n moles) and its temperature T is assumed to be constant too. Simple relation holds: P α 1/V which shows that in order to calculate pressure, one has to calculate volume of the body which is done utilizing Gauss theorem (Hughes, 1996)

The pressure force acting on i-th triangular surface can be calculated as follows:

where P is pressure calculated from the ideal gas law, ˆn is normal to the face and dS is an area of the face.

Collision Detection/Response

SoftBall-to-SoftBall collisions are done by first checking bounding spheres and then checking each point with other’s bounding ellipsoid and calculating a response from that.

SoftBall-to-RigidBall collisions are done by checking bounding spheres of SoftBalls with spheres of RigidBalls.

SoftBall-to-Wall and SoftBall-to-Floor collisions are done by checking each point in the soft body with point-plane collision detection/responses.

System Architecture

The system architecture is distributed and parallel in nature. This means that it balances and divides the load of handling/managing balls in a distributed manner and utilizes threads to increase system efficiency. Each module is further described in detail below. For more information on the system architecture please see the UML diagrams attached with this report. For the way the ownership is transferred from one peer to another please see the flow diagram labeled “Ownership Flowchart”.

Network

The system design utilizes a peer-to-peer architecture for the networking where each peer is capable of initiating and accepting a connection to another peer. Each peer consists of a UDP server socket (for initial connection request) and a TCP server socket (for the actual communication). They also have a UDP client socket and a TCP client socket to talk to the server sockets.

Each peer starts off with sending a UDP broadcast on its network to tell other prospective peers that they are online. If any other peers are online and they receive this specific message they initiate a TCP connection request to the sender’s IP address.

Figure 2

The Network Manager is responsible for handling all communication to and from a peer. It also maintains a list of all connected peers and saves the communication sockets in that list for each peer. As this is a peer-to-peer architecture, the Network Manager is responsible for both receiving/processing data packets and also for sending them to relevant peers.

The Network Manager is implemented as a singleton class and is used by the BallManager class and the Scene class whenever ball data or Gravity Well data is to be sent across the network. It is also used by the TCPClientSocket class to handle and process incoming data packets and act accordingly by passing requests to BallManager.

Threads

In order to improve system performance, threads have been used in the system to run certain functionality in parallel. A ThreadList class is implemented such that when derived from this class a class can initiate one or more threads and assign them certain tasks. Classes that take advantage of this functionality include all TCP and UDP socket classes (servers and clients) and the BallManager class.

In the Network classes (see figure 2 and UML class diagrams), the TCP and the UDP Server run as listening (blocking) sockets on their own separate threads. Similarly, the TCP client has two threads running one for ‘receive’ and one for ‘send’. If a peer has to send information to another peer it adds the message to the send message queue and the send thread automatically takes care of sending it. Similarly the receive thread checks for a complete message and when it gets it, passes it on to the network manager for processing.

In the BallManager class, a thread is used to run physics separately. This thread does numerical integration of the rigid body simulation and also does collision detection and response simultaneously to the main thread which draws the current state of the physics on screen.

Another thread of the BallManager is used to run the ‘Load Balancing’ algorithm in parallel to all other tasks. This checks the amount of balls owned and checks the total number of online peers to calculate the average number of balls a peer should have. If current ownership number is more, it sends a ball ownership to each peer per frame.