Тридцать лет. Именно столько индустрия анимации и геймдева мучительно искала способ симулировать ткань так, чтобы она не проваливалась сквозь себя, не взрывалась при малейшем трении и не требовала сутёрного счета на ферме из 1000 GPU. Проблема контактов в симуляции ткани — это проклятие, которое заставляло художников вручную править каждую сцену с платьем или флагом.
В 2025 году вышла работа ZOZO: Fast and Accurate Cloth Simulation using Cubic Polynomial Contact Model (SIGGRAPH 2025 / ACM Transactions on Graphics). Авторы предложили не очередной хак, а математически элегантное решение, основанное на кубическом полиноме. Результат: 184 миллиона контактов обрабатываются за разумное время без единого проникновения. Никаких penalty forces, никаких итеративных проекций — только один полином, который гарантирует, что ткань остаётся непроницаемой.
Разберёмся, как это работает, и реализуем ключевой компонент на Python. Спойлер: весь код уместится в 200 строк. Да, вы не ослышались.
Проклятие контактной задачи: почему тридцать лет боли
Классическая физическая симуляция ткани использует метод конечных разностей или FEM на сетке треугольников. Проблема возникает, когда два слоя ткани соприкасаются. Если просто отталкивать вершины при пересечении — ткань просачивается наружу, создавая артефакты. Если же решать задачу как систему неравенств (incremental potential contact, IPC), получаем взрыв размерности: для каждого треугольника нужно найти расстояние до каждого другого.
Инженеры пытались обмануть физику: penalty forces (штрафные силы) слишком жёсткие и приводят к расходящимся колебаниям; barrier methods с логарифмическими барьерами (IPC) требуют глобального решателя, который жрёт часы вычислений. За 30 лет индустрия смирилась с тем, что контактная задача — это дорого.
Типичный трейд-офф: хочешь без проникновений — плати временем. Хочешь быстро — получай артефакты и «дрожащую» ткань. ZOZO ломает этот стереотип.
ZOZO: кубический полином как философский камень
Идея авторов пугающе проста. Вместо того чтобы вычислять точное расстояние между треугольниками (дорого) или аппроксимировать его линейной функцией (неточно), они предлагают кубический полином, который аппроксимирует знак расстояния между двумя треугольниками в локальной области.
Пусть у нас есть два треугольника, движущихся друг к другу. Мы параметризуем их положение через время t в рамках одного шага симуляции. Расстояние между ними — гладкая функция d(t). Если её разложить в ряд Тейлора до третьего порядка, то кубическая аппроксимация позволяет с высокой точностью предсказать момент контакта и корректно вычислить импульс отталкивания.
Математика выглядит так. Для пары вершин (или ребро-вершина, или треугольник-треугольник) мы вычисляем знаковое расстояние d(t) в начале шага. Затем находим его кубическую аппроксимацию с помощью конечных разностей по времени (или аналитически). Далее мы приравниваем полином к нулю — получаем корни. Самый маленький положительный корень — момент контакта. Если корень меньше шага по времени, мы останавливаемся в этом моменте, применяем импульс отталкивания и продолжаем. Звучит как обычный collision response, но отличие в том, что кубическая модель позволяет обрабатывать взаимодействие многих слоёв одновременно без дополнительных проекций.
184 миллиона контактов: как им это удалось?
Авторы опубликовали бенчмарк: симуляция флага из 10 000 треугольников, который падает на сложный рельеф и одновременно провисает через себя — типичный сценарий self-collision. В процессе симуляции за 100 кадров было зафиксировано 184 миллиона пар контактов (каждая пара треугольник-треугольник хотя бы раз рассматривалась). ZOZO обработал их все за 0.85 секунды на одном GPU (NVIDIA RTX 4090). Для сравнения: классический IPC на CPU тратил на ту же задачу 47 секунд.
Как? Первое — кубический полином позволяет отбрасывать далёкие пары с помощью bounding volume hierarchy (BVH), но даже когда пары близки, обработка пары стоит всего несколько арифметических операций. Второе — вся математика легко векторизуется. Авторы реализовали решатель на CUDA и PyTorch, что дало ускорение.
Пишем свой ZOZO-лайт на Python
Мы не будем воспроизводить всю систему (там есть нюансы с геометрией треугольников). Но сфокусируемся на главном: как аппроксимировать знаковое расстояние между двумя вершинами кубическим полиномом и определить момент контакта. Это сердце метода.
1 Собираем данные о движении
На каждом шаге симуляции у нас есть текущие позиции вершин и скорости. Мы можем оценить положение через малый интервал dt. Для аппроксимации нам нужно знаковое расстояние d(t) в трёх точках: t=0 (текущий), t=dt (экстраполяция), t=-dt (назад). Это даст три точки, через которые проводим кубический сплайн (на самом деле квадратичный, но для кубического нужна ещё производная). Авторы используют конечные разности для получения второй производной.
import numpy as np
def cubic_contact_detection(p0, p1, v0, v1, dt, threshold=1e-6):
"""p0, p1 - текущие позиции двух вершин; v0, v1 - скорости."""
# Функция расстояния d(t) = ||(p0 + v0*t) - (p1 + v1*t)||
# Для упрощения рассматриваем 1D проекцию, но в общем случае нужно знаковое расстояние
# Здесь мы предполагаем, что вектора уже спроецированы на нормаль контакта
x0 = p0 - p1
v_rel = v0 - v1
# Знаковое расстояние в t=0
d0 = np.linalg.norm(x0)
# Экстраполируем на dt
x1 = x0 + v_rel * dt
d1 = np.linalg.norm(x1)
# Назад
x_neg = x0 - v_rel * dt
d_neg = np.linalg.norm(x_neg)
# Аппроксимируем d(t) кубическим полиномом: a*t^3 + b*t^2 + c*t + d0
# Используем метод наименьших квадратов для трёх точек
# Составляем матрицу Вандермонда для t = {-dt, 0, dt}
t_vals = np.array([-dt, 0, dt])
d_vals = np.array([d_neg, d0, d1])
A = np.vander(t_vals, 4) # степени 0,1,2,3
# Решаем систему (три уравнения, четыре неизвестных - нужно регуляризовать или использовать псевдообратную)
# В оригинале используются конечные разности, поэтому возьмём производные напрямую
# Упростим: будем считать, что полином второй степени (парабола) - это тоже даёт результат
# Для кубического нужно 4 точки, но мы можем использовать скорость изменения производной
# Реализуем вариант из статьи: Use finite differences for first and second derivatives
d_prime = (d1 - d_neg) / (2 * dt)
d_double = (d1 - 2*d0 + d_neg) / (dt**2)
# Кубический член приближаем нулём, так как симметрия слабая
# Или можно вычислить третью производную через дополнительную точку
# Но для демонстрации хватит квадратичной аппроксимации
# Найдём корень d(t)=0: a2*t^2 + a1*t + a0 = 0, где a2 = 0.5*d_double, a1 = d_prime, a0 = d0
a = 0.5 * d_double
b = d_prime
c = d0 - threshold
if abs(a) < 1e-12:
# линейный случай
if abs(b) < 1e-12:
return None
t_coll = -c / b
else:
disc = b*b - 4*a*c
if disc < 0:
return None
t1 = (-b - np.sqrt(disc)) / (2*a)
t2 = (-b + np.sqrt(disc)) / (2*a)
# выбираем наименьший положительный корень
t_coll = None
for t in [t1, t2]:
if 0 < t < dt and (t_coll is None or t < t_coll):
t_coll = t
if t_coll is not None and 0 < t_coll < dt:
# Возвращаем момент контакта
return t_coll
return None
Этот фрагмент — игрушечная версия. В реальной ZOZO берут знаковое расстояние между треугольниками, а не вершинами, и используют кубический сплайн с контролем ошибки. Но принцип тот же.
2 Интеграция с симуляцией
Когда мы нашли t_coll, мы можем вернуть симуляцию в этот момент, применить импульс (изменить скорости) и продолжить с оставшегося времени dt - t_coll. Импульс считается через коэффициент восстановления и массу вершин. Важно обрабатывать контакты в порядке возрастания t_coll.
def handle_collision(p0, p1, v0, v1, t_coll, restitution=0.0):
# Перемещаем вершины в момент контакта
x0_coll = p0 + v0 * t_coll
x1_coll = p1 + v1 * t_coll
# Нормаль контакта
n = (x0_coll - x1_coll) / np.linalg.norm(x0_coll - x1_coll)
# Относительная скорость по нормали
v_rel = np.dot(v0 - v1, n)
if v_rel > 0: # расходятся
return v0, v1
# Импульс (предполагаем равные массы)
j = -(1 + restitution) * v_rel / 2.0
v0_new = v0 + j * n
v1_new = v1 - j * n
return v0_new, v1_new
Для полноценной симуляции нужно ещё определять, какие пары треугольников проверять. Используется BVH (например, на основе AABB). Это стандартная практика, о которой можно почитать в статьях по SplineTransformer — там тоже про полиномиальную аппроксимацию, но в контексте регрессии.
Типичные ошибки и как их избежать
| Ошибка | Последствие | Решение |
|---|---|---|
| Линейная аппроксимация расстояния | Пропускаем контакты, когда относительное ускорение велико | Использовать кубический полином или хотя бы квадратичный |
| Не обновлять BVH после коллапса | Пропущенные столкновения | Перестраивать BVH каждый шаг (или через n шагов) |
| Жёсткий импульс с большим шагом dt | Взрыв энергии | Уменьшать dt, если обнаружено много контактов, или использовать демпфирование |
| Игнорировать трение | Ткань скользит как по льду | Добавить касательную составляющую импульса с коэффициентом трения |
Почему кубический полином — это не магия, а математика
У кого-то мог возникнуть вопрос: чем кубический полином лучше, чем, скажем, квадратичный? Ответ кроется в гладкости траектории. При типичном движении ткань испытывает ускорения (гравитация, силы растяжения). Квадратичная аппроксимация может не уловить точку перегиба, когда два треугольника сначала сближаются, а потом начинают расходиться из-за упругости. Кубический полином захватывает вторую производную (кривизну) и позволяет точнее предсказать момент касания.
В исходной работе авторы также добавили адаптивный выбор степени: если кубическая аппроксимация даёт слишком большую ошибку (проверяется по остатку), они дробят шаг. Это напоминает адаптивные решатели ОДУ, но для контактов.
Связь с другими технологиями
Кубический полином ZOZO — частный случай более общего подхода: использование полиномиальных surrogate-моделей для дорогих геометрических вычислений. Аналогичные идеи применяются в байесовском выводе с JAX, где полиномиальные аппроксимации ускоряют расчёт правдоподобия. А если вы профилируете производительность симуляции, советую освоить Py-Spy — он поможет найти узкие места.
Для тех, кто хочет собрать полноценный физический движок на Python, полезно будет почитать про решатель Навье-Стокса — там показано, как строить численные схемы с контролем ошибки. И, конечно, не обойтись без оптимизации памяти: если вы тренируете большие модели параллельно, ZAGORA подскажет, как не вылететь по OOM.
Неочевидный совет: сначала проверьте, есть ли у вас проблема
Прежде чем внедрять ZOZO в свой пайплайн, спросите себя: а нужна ли вам симуляция контактов с точностью до микрона? В 80% случаев геймдева можно обойтись более грубыми методами. Но если вы делаете симуляцию для кино или CAD-верификацию, где каждый миллиметр на счету, — кубический полином ZOZO даст вам и точность, и скорость. Главное — не забудьте про трение. Без него ткань будет вести себя как мыльный пузырь.
Полный код референсной реализации доступен в репозитории авторов на GitHub (ищите ZOZO-cloth). Но если хотите написать свою — начните с маленького теста: два падающих треугольника. Убедитесь, что кубический полином правильно предсказывает момент касания. Затем добавляйте слои. И помните: 184 миллиона контактов — это впечатляющий бенчмарк, но для вашей сцены может хватить и тысяч. Не оптимизируйте преждевременно.
