Project 4 Part 4: Handling self-collisions

One thing that our implementation currently fails to handle is cloth self-collision. As a result, if we have a scene in which the cloth falls on itself or otherwise folds on itself, the cloth will clip through and behave strangely. You may have seen this type of issue before in video games.

Try it for yourself without any self-collision code:

./clothsim -f ../scene/selfCollision.json

The cloth ignores itself and falls onto the plane!

To solve this, we will implement cloth self-collision. The naive method of doing this is to loop through all pairs of point masses, compute the distance between them, and then apply a modifying force to the two point masses if they are within some threshold distance apart. However, this $O(n^2)$ solution is too inefficient for real-time simulations, especially as the cloth gets more complex and larger.

Instead, we will implement spatial hashing. At each time step, we build a hash table that maps a float to a vector<PointMass *>, which is stored as map in the Cloth struct. The float uniquely represents a 3D box volume in the scene and the vector<PointMass *> contains all of the point masses that are in that 3D box volume. Once the map is built, we simply have to loop through the point masses, look up (using the hash table) the point masses that it shares the same 3D volume with, and then apply a repulsive collision force if any pair of point masses are too close to each other.

Complete the Cloth::hash_position, Cloth::build_spatial_map, and Cloth::self_collide methods.

4.1: Cloth::hash_position

Cloth::hash_position takes a point mass's position and uniquely map it to a float that represents a specific 3D box volume. One way to do this is effectively partition the 3D space into 3D boxes with dimensions $w * h * t$ where $w$ = 3 * width / num_width_points, $h$ = 3 * height / num_height_points, and $t = max(w, h)$. (Side note: The constant 3 here is somewhat empirically chosen to improve the accuracy of the spatial hashing algorithm.) Then, take the position and truncate its coordinates to the closest 3D box (hint: think modulo). Using these new coordinates, compute a unique number that corresponds to those 3D coordinates and return it. This will be used as the unique key in our hash table. You may find the fmod function useful.

4.2: Cloth::build_spatial_map

Cloth::build_spatial_map should loop over all point masses and use the Cloth::hash_position method to populate the map as described above.

4.3: Cloth::self_collide

Cloth::self_collide takes in a point mass and looks up potential candidates for collision using the hash table. For each pair between the point mass and a candidate point mass, determine whether they are within $2 * thickness$ distance apart. If so, compute a correction vector that can be applied to the point mass (not the candidate one) such that the pair would be $2 * thickness$ distance apart. The final correction vector to the point mass's position is the average of all of these pairwise correction vectors, scaled down by simulation_steps (this helps improve accuracy by reducing the potential number of sudden position corrections). Make sure to not collide a point mass with itself!

As in Part 3, you will also need to update Cloth::simulate to account for potential self-collisions, similarly accomplished by calling self_collide on each PointMass.

Test your implementation

./clothsim -f ../scene/selfCollision.json

You should see your cloth folding on itself rather than clipping through itself as it falls to the ground. Yay!

However, you may notice that your cloth will continue to flatten itself out over time rather than coming to a more natural, realistic stop. (In real life, damping factors like friction, heat loss, etc. all contribute to net energy loss in the cloth system.) This is because even in a "resting state" on the ground plane, the cloth's point masses will continue to repel each other due to lack of damping spring forces in our model (which is more difficult to do physically accurately using Verlet integration). Don't worry if your cloth is exhibiting this behavior! What's important is that your cloth does not clip through itself and exhibits folding on itself.

Part 4 Deliverables

• Show us at least 3 screenshots that document how your cloth falls and folds on itself, starting with an early, initial self-collision and ending with the cloth at a more restful state (even if it is still slightly bouncy on the ground).
• Vary the density as well as ks and describe with words and screenshots how they affect the behavior of the cloth as it falls on itself.