Resolving cloth self-intersections on the CPU

Intersection Contour Minimization Cloth that already intersects itself cannot be repaired by pushing points apart: nobody knows which side is 'outside'. Volino and Magnenat-Thalmann (2006) look at the intersection contour instead, the curve where the cloth cuts through itself. They move the cloth so that this curve gets shorter until it vanishes. The method needs no history of earlier frames. ACM

BVH with normal-cone culling Testing every triangle against every other one is far too slow. A tree of bounding volumes (here 18-DOPs, a box with cut corners) finds the pairs that are close. A region whose normals all point roughly the same way (a cone narrower than 90 degrees) and whose border does not overlap itself when seen along that direction cannot intersect itself. The tree skips such a region completely (Volino 1994). Wikipedia

Proximity constraints Cloth that does not intersect yet is kept apart by a small thickness: point-triangle and edge-edge constraints inside the XPBD loop push close parts away from each other. With ICM, next to a contour a push that works against the ICM displacement is dropped (diploma, section 5.3), otherwise it would widen the intersection. The Kikuchi method has no such rule and keeps the push. Ye and Buffet use the ICM rule. XPBD

Original work

• Pascal Volino, Nadia Magnenat-Thalmann (2006): Resolving surface collisions through intersection contour minimization
• Tomoyo Kikuchi, Takashi Kanai (2025): A Unified Discrete Collision Framework for Triangle Primitives
• Juntao Ye, Guanghui Ma, Liguo Jiang, Lan Chen, Jituo Li, Gang Xiong, Xiaopeng Zhang, Min Tang (2017): A Unified Cloth Untangling Framework Through Discrete Collision Detection
• Thomas Buffet, Damien Rohmer, Loïc Barthe, Laurence Boissieux, Marie-Paule Cani (2019): Implicit Untangling: A Robust Solution for Modeling Layered Clothing
• Miles Macklin, Matthias Müller, Nuttapong Chentanez (2016): XPBD: Position-Based Simulation of Compliant Constrained Dynamics

How it works

The cloth is a grid of particles (CPU, XPBD, 10 solver iterations per frame): 50 × 50 = 2,500 in the tangled start, 40 × 40 = 1,600 in the dropped cloth, two sheets: 2 × 22 × 22 = 968. Per frame: predict positions, refit the BVH, find all intersections, trace the contours, compute the ICM displacement, then run the solver iterations and apply the displacement in small parts. In the dropped cloth the gap between the layers is twice as large (0.02 instead of 0.01) and the particles are spaced wider (0.145 instead of 0.1), so the dropped cloth is 5.7 m wide. It starts with a small spin around the vertical axis, so that more folds cross each other. The close pairs are found again in the middle of the iterations (after 5 of 10), because the falling cloth moves a lot within one frame. After the solver, each velocity is replaced by the mean of its neighbours and the momentum of the proximity push is dropped, so folds that rest on the ground stop chattering.

• BVH: one leaf per grid quad (2 triangles). Every node stores an 18-DOP and a normal cone. The tree keeps its shape and is refit bottom-up every frame. Node pairs with overlapping volumes are walked down to leaf pairs.
• Narrow phase: the 3 edges of each triangle are tested against the other triangle (Möller-Trumbore). Two hits of one triangle pair form one segment of the intersection contour. Triangles that share a vertex are skipped.
• Contours: the segments are joined into closed loops or into open paths that end at the cloth border. The green lines show them. With the BVH shown, culled boxes are cyan.
• ICM: per contour, every segment end gets a gradient (the direction in which its edge must move relative to the triangle to shorten the contour). The gradients are summed with a sign for the two sides of the cloth and scaled to H = h0 · D / sqrt(|D|² + g0²), with h0 = response strength · spacing and g0 = 4. The edge side moves by +H, the triangle side by −H. The displacement is spread over the particles by inverse mass and by distance to the hit point, and averaged per particle.
• Tangled start: no gravity, the top row is pinned, the lower half is folded back and a ridge across it pokes through the front half. Dropped cloth: the cloth falls on a small sphere on the ground. All three scenes share the same solver. Switch untangling off to see the difference: in the dropped cloth the intersections then stay (about ten per frame instead of about one). Two sheets: a second sheet, turned by 45° and 0.1 m above the first, falls on the same sphere. Intersections between the two sheets are handled like self-intersections: the two sides of a contour are the two sheets. Untangling off: about 20 hits per frame instead of about one.
• Grab: a ray pick finds the nearest free particle. It and its 8 neighbours are pulled toward the pointer in every solver iteration (neighbours with half strength), in a plane that faces the camera. On release the drag velocity stays and the cloth falls.
• Kikuchi 2025: per intersecting triangle pair, depth = deepest corner of the projected overlap (vertices inside the other triangle, projected vertices, edge crossings), f = min of both depths, direction = the normal of the other triangle (the one the smaller depth was measured against). PBD projection with inverse masses, each triangle moves as a whole. The response strength caps the move of one pair per frame at strength · spacing; at high values the cap is above any depth and the method runs as in the paper.
• Ye 2017: contour type from the two ends (border edge = boundary, no border = crease). Boundary: the hit edges cut the mesh, the smaller region moves within 3 rings of one end of the contour (fading with the distance) along the mean normal of the pierced triangles, the pierced triangles the other way. Crease: H = h0 · D / |D|. Loop: as ICM. h0 = response strength · spacing, as for ICM.
• Buffet 2019: per frame every vertex finds the closest triangle of the other sheet; field value = signed distance to its plane, the thickness is added as an offset (eq. 13), a sheet counts only where the foot point lies on it (within one spacing). A vertex on the wrong side is moved onto the mean surface of the two layers (eq. 5, 7) with Newton steps of length 0.3 (section 6.3), at most response strength · spacing per frame, without momentum like the proximity push. One sheet: nothing to order, no response.

Source code:icm-response.tskikuchi-response.tsye-response.tsbuffet-response.tscloth-bvh.tsintersection-contours.ts

Note Limits of this demo:

• Contours can end in a dead end: a local minimum where the contour cannot get shorter without another pull. ICM cannot untangle such a state. The two scenes do not build one on purpose.
• Hits exactly through a vertex or an edge are dropped for one frame. A contour can split into two pieces for a moment.
• Contact friction (sphere and ground) and a speed limit keep the cloth calm. Without them the cloth slides into a pile that the detection can no longer sort out.
• Kikuchi: the paper has no rule for the valid side within one cloth. Here a pair remembers its side from before the crossing; the tangled start has no such history and uses a fixed side (the back faces touch), so another tangle may be pushed the wrong way.