Global Intersection Analysis

Introduction

Simulations often become unstable as a result of self-intersection or intersection between two meshes. This instability can lead to wrong simulation results and incorrect outputs. At the same time, self and inter collisions of meshes are a necessity for artistic purposes in cases such as 3D animation. To resolve this issue, Baraff et al. (2003) reveals a method known as global intersection analysis, which specifies how to resolve these mesh intersections while allowing the simulation to run as it normally would. This ensures that we obtain simulation stability while also allowing for mesh intersections when required.

The goal

For the sake of our one week project time period, our project focussed on creating a simple implementation of the global intersection analysis algorithm along with a simple resolution method between two different meshes.

The global intersection analysis algorithm required a few steps:

1. Identify a contour along which both meshes intersect each other
2. Identify the points inside and outside this contour for both mesh
3. Use these points to resolve the intersections by adding a constraint that “pulls” them out of each other (subsequently resolving the intersection)
4. Allow the physics solver to run as it normally would after resolution of intersection.

Our entire implementation can be found here.

Development

We implemented this project in 3 parts.

1. The global intersection analysis algorithm, which would perform the steps above
2. Our physics solver, which would run an XPBD algorithm for the cloth to follow
3. Integrating both these systems together in terms of the constraints needed for the cloth XPBD to take intersection resolution into account.

For our demo scene, we used a simple rigid ball and a tesselated plane to act as a cloth mesh.

Contour Identification and Flood Filling

For our GIA implementation, we created a scene which identifies a contour, identifies the points inside and outside and provides this data as output for further processing.

Our identification of points is done through a flood fill algorithm.

The original method mentioned by Baraff et al. (2003) discusses selecting the region with lesser area, determining that to be the area inside the contour and then flood filling from inside this smaller area and larger area with two separate colors to identify both regions on the mesh. It isn’t entirely clear how to choose a point in this area or how to determine this area solely from the contour. As a result, we created and implemented our own method for the flood fill which works well in our current test cases.

Our method follows standard flood filling techniques, where we identify a point on the surface with one color, then recursively repeat the coloring process to all points connected to the last one. To identify if a point is across the contour, we change the color if the edge that connects two points is identified as one that intersects with the edges on the contour.

To make this more efficient, we identify contour intersecting edges beforehand. We also colored any points along the contour beforehand to ensure the flood fill would not overwrite or mistake those points. As a heuristic, we also begin the flood fill along any identified points along the contour since pre-coloring a point means the flood fill algorithm will not continue if all points adjacent to a point are colored.

We utilised the IPC Toolkit [3] to perform intersection operations between the surface and contour edges.

XPBD Implementation

Using Matthias Müller’s implementation[2] as reference, we also implemented an XPBD cloth simulator.

We provide various parameters to change as well, such as the simulation time step and cloth properties.

Integration

To integrate both systems, the most important part was integrating the GIA collision resolution into the cloth mesh’s XPBD constraint formulation. For simplicity, we push away the cloth in a force whose direction is the vector from center of the cloth contour points and the ball mesh contour points. This way, we would have a close-enough approximation to push the cloth away. We then integrate this constraint into the system, where we identify and assign this force direction for the cloth after performing a GIA call. One GIA call would perform a contouring, vertex identification and force direction identification before assigning it to the cloth’s constraint. The cloth’s XPBD solver would then take this into account when determining the next position of points on the cloth.

Result

The results of our integration can be seen here.

The UI also allows user to play around with different simulation settings and options.

To get a look into the source code, our GitHub repository can be found here.

Scope for improvement

Given our 1 week period, there are some areas for improvement.

1. Our current GIA implementation is too slow to be used in realtime and can be made faster.
2. Our intersection resolution method is not what is exactly outlined in the original “Untangling cloth” paper but a rough approximation. Baraff et al. (2003) provide a much more precise method to determine per vertex resolution along the meshes.
3. XPBD may not be the most accurate simulator of cloth (though for an application such as animation, it works well enough visually).
4. Our GIA flood fill can sometimes identify vertices incorrectly, leading to inaccuracies in the mesh-intersection resolution.

References

[1] Baraff, D., Witkin, A., & Kass, M. (2003). Untangling cloth. ACM Transactions on Graphics, 22(3), 862–870. https://doi.org/10.1145/882262.882357

[2] Matthias Müller. pages/tenMinutePhysics/15-selfCollision.html at master · matthias-research/pages. GitHub. https://github.com/matthias-research/pages/blob/master/tenMinutePhysics/15-selfCollision.html

[3] IPC Toolkit. https://ipctk.xyz/

This blog was written by Sachin Kishan as one of the outcomes of a project during the SGI 2024 Fellowship under the mentorship of Zachary Ferguson.