移动端或游戏布料的解算

衣料模拟实现方案

衣料模拟方面，像 里面有三种对布料的仿真，一种是物理骨骼，一种是物理骨骼的布料，一种是最好效果的布料。市面上已有的游戏：对于移动端unity magica cloth 说是性能更优长裙说是现在都难的，一般的衣服会好一些，（市场上有做的不太好的做法，就是为了衣服居然添加不少约束来限制人的运动）看了一下现在的基本上都是飘飘然的感觉是有，但是要能容忍一定程度的穿模。这里通过unity的Magica Cloth插件简述游戏开发发展过程中出现过三个经典方法：

1、基于动画的衣料模拟 — Animation bone

把衣服当身体一样进行动画处理，在衣服上设置joint和骨骼，并进行相应的插值处理。优点在于便宜和可控（移动端），缺点在于不够真实、和环境没有交互以及设计上受限。
maya衣服碰撞绑定裙摆碰撞Maya人体绑定Maya加AdvancedSkeleton蒙皮绑定教程

2、基于刚体的衣料模拟 — kinematic bone
像布娃娃系统一文搞懂 Unity 布娃娃（Ragdoll）系统 让角色更加真实 （附实用Ragdoll插件详解）一样设置一些骨骼joint，利用物理系统去进行计算处理。优点在于便宜和可交互，缺点在于质量不可控、动画师的工作量大、不鲁棒以及需要高质量物理系统参与。或者使用动态骨骼来实现类似的衣服模拟，
iBlender中文版插件 Gravity Collider Bone Physics Plugin 重力碰撞骨骼物理 Blender 插件 教程
动态骨骼实现方案：就是把DynamicBone的每个节点都当成一个球，然后用一些固定的碰撞体定位在模型空间上的一些位置，然后去碰撞（优点是实现相对简单，性能消耗低。缺点是不够真实，有时穿模是不可避免的！）。

3、基于mesh的物理衣料模拟
简单讲就是获得物体的mesh，并对每一个顶点进行计算处理。而由于物理系统计算的昂贵，所以一般不会像渲染时一样对每个顶点计算，而是相对稀疏。（少几倍到十倍）具体做法上细节如下（以人物身上的衣料为例（披风））：首先，对每一个顶点要设置最大的移动半径。一般来说，对离人物越近的顶点，最大移动半径越小（比如脖子处基本不动），一方面更符合物理实际，另一方面可以减少穿模概率在游戏开发者角度来说，需要设置衣料的物理属性。引擎当中的布料设置 中文字幕 UE4 Character Cloth Simulation

现在最常用的是处理弹簧算法的方法是：Position Based Dynamics（PBD），其简单思想是用拉格朗日力学替代传统力学那一套，放弃“约束 - 力 - 速度 - 位置”的逻辑而把所有的力学关系描述成一套约束，并直接解出最后的位置，而不关心速度。

在讲PBD算法之前先了解一些前置的知识：

弹簧质点系统（Mass-Spring System）

弹簧质点系统是一个理想化的物理模型，主要用来描述线性弹性力学问题；适用场景可用于模拟绳索、布料、头发等弹性物体。这个模型由两个基本组件构成：一个具有质量的质点（mass）和一个理想化的弹簧（spring)。弹簧质点系统中，弹簧根据胡克定律（Hooke’s Law）来对物体施加力，该定律说明弹簧施加的力与其伸长或压缩的距离成正比！胡克定律的表达如下：
F = -kx 其中， F 是弹簧所施加的力，k 是弹簧的弹性常数（或称为刚度系数），而 x 是弹簧从其平衡位置移动的距离。
在没有其他外部力（如重力、摩擦力等）作用的理想条件下，弹簧质点系统可以做简谐运动（Simple Harmonic Motion）当然这不太符合没有耗散就会永远的震动下去现实所以有阻尼力：F阻 = -C*V ，其中C是阻尼系数，V是速度；除了阻尼力还要有重力Fg = mg ;根据中学时期的物理受力分析，其运动方程可以根据牛顿第二定律F=ma，匀变速运动等。

衣服物理建模：

质点弹簧系统作用于结构化的弹簧网格

我们需要在上面添加三种弹簧：

1. 结构弹簧(Struct spring)：在网格原本的边上添加弹簧，抵抗布料产生横向和纵向的的小皱褶。
2. 剪切弹簧(Shear spring)：在每个小格子的两个对角线上加两根弹簧，抵抗布料在对角方向上的皱褶。
3. 弯曲弹簧(Bend spring)：跳过一个顶点连接的弹簧，抵抗布料沿中间的长边产生大的翻折（即Bending，后面可能翻译为弯曲、弯折，都是一个意思）

实际应用中可以简化一些，只在一个小格子的其中一个对角线上添加弹簧。

对于不规则形状的三角形 Mesh 布料，同样在三角网格的每个边上都加一根弹簧，然后跨过所有内部边添加弹簧（称任意两个相邻三角形的公共边为内部边，两个相邻三角形组成一个四边形，新添加的弹簧为这个四边形的对角线）来抵抗弯曲。

时间离散化：

在经典力学/动力学里，我们认为时间是连续的。然而，计算机并不能处理连续的数据，对此的办法一般是将连续数据离散化！时间离散化是将连续时间转化为一系列离散时间步骤（或时间点）的过程，该过程使得我们可以在计算机上模拟动态系统的行为。以下是几种常见的时间离散化计算方法：

1.欧拉方法（Euler Method）:最简单的时间积分方法是显示欧拉欧拉方法。它通过当前状态值和在此状态下评估的导数来估算下一个状态值。
2. 龙格-库塔方法（Runge-Kutta Methods）:为了提高欧拉方法的准确性和稳定性，更高阶的时间积分方法被开发出来，比如四阶龙格-库塔方法，它通过结合多个中间步骤的估计来提高对下一个状态值的预测。这是一种非常流行的方法，因为它既准确又稳定。
3. 莱普索方法（Leapfrog Method）:莱普索方法用于第二阶动力学系统，如物理中的力学系统。在该方法中，位置和速度分开计算，并且交错半个时间步。
4. 有限差分方法（Finite Difference Methods）:通过将微分方程中的连续导数替换为离散近似，有限差分方法解决了微分方程。这项技术常用于模拟海洋或大气科学中的流体流动，以及在结构分析和热传递问题中（计算机图形学物理与动画主要用作流体力学等的模拟）。
5. 有限元方法（Finite Element Methods, FEM）:有限元方法通过创建元素网格和相应的基函数来离散化区域。这种方法在工程和物理的许多领域都很流行，用于处理复杂几何形状和边界条件的问题（物理引擎CAD/CAE 中模拟与仿真内部结构分析常用）。
6. 蒙特卡罗方法（Monte Carlo Methods）:虽然蒙特卡罗方法主要用于统计抽样，但它也可以用于时间离散化，特别是对于随机过程和概率系统（图形学渲染常用）。
7. 差分方程:对于许多离散时间系统，连续时间微分方程可被转化为差分方程来解。这在控制理论和信号处理中非常有用。

下面我将重点介绍欧拉法来实现布料的模拟：

显示欧拉法：
时刻的速度V和位移X完全由上一个时刻得出:

半隐士欧拉法：
即速度由上一个时刻得出，计算位移X时，速度V用当前的速度。实际上这也是一种显式方法。

隐式欧拉法
隐式欧拉法的误差会比显式的更小一些，隐式的方法相比前两种难算的多：因为它用的是下一时刻的加速度。

需要我们经过数学推导和近似，消去未知项，来达到递推的目的（比如牛顿法迭代法 Newton法（Newton法（牛顿法 Newton Method））。

欧拉法的优点在于易于实现，缺点是误差大，不稳定。通过泰勒展开可以分析它的误差（线性拟合可以推导）为什么说隐式误差低：隐式积分法更新速度时用的是新的位置受到的力，也就是说当弹簧缩小时，显式积分用的弹力一定大于这个时间步内的平均弹力，而隐式积分用的力小于一个时间步内的平均弹力，因此隐式积分法在数值上更稳定一些。

Verlet积分法
Verlet 方法是另一种求解离散时间上的积分方法 如果要求同一时刻的位移和速度，采用 Velocity Verlet 方法，公式如下：

具体推导请看：韦尔莱积分法 - 维基百科，自由的百科全书 (
NvCloth使用了Verlet 积分法，每次迭代计算粒子位置 Pos(i) = Pos(i-1) + (Pos(i-1) - Pos(i-2)) * (1 - damping) + Force/mass * dt * dt; （i为第i次迭代；force为力；mass为粒子的质量；dt是迭代的间隔时间；damping是阻尼），每次迭代的间隔时间dt相等。
1、当damping == 0 ，force == 0 时变现为“惯性定律”。要么保持静止，要么保持之前的速度运动；
2、 当damping >0 ，force == 0 时damping模拟了现实中总会存在的阻力，比如空气阻力等，使得粒子的运动受阻。这样更符合人对于布料运动表现的期待。

碰撞：

碰撞处理是确保物体不穿透其他物体或自身的关键部分。碰撞处理通常包括两个阶段：碰撞检测（collision detection）和碰撞响应（collision response），自碰撞。即对象的部分与它自身的其他部分发生接触，处理起来比处理两个不同对象之间的碰撞要复杂得多，因为需要考虑对象本身的连续性和弹性。布料的碰撞问题：其中主要难点在于如何处理碰撞，一方面是碰撞检测，另一方面是碰撞响应。
碰撞检测阶段：PBD系统必须识别出所有潜在的碰撞和自碰撞。有多种空间数据结构可以用来提高碰撞检测的效率，比如空间分割（四叉树、八叉树）BVH等在我以往的文章中有写到 空间数据结构

碰撞响应：
一旦检测到碰撞，PBD系统要计算碰撞响应，以调整粒子的位置，保证它们不会相互穿透。在PBD算法内，不需要考虑粒子间的力，而是直接修改它们的位置。碰撞响应的基本步骤包括：

1. 计算交点：对于每个发现的碰撞对，计算接触点或交点的位置。
2. 解决穿透： 对于穿透的粒子，PBD通过计算响应来消除穿透情况。这通常通过将粒子沿着碰撞法线移出来实现。每个粒子的移动量与其质量成反比——更重的粒子移动得较少。
3. 更新位置：使用计算得到的修正向量，更新粒子的位置，使它们不再相互穿透。
4. 重复迭代：程序可能需要多次迭代碰撞响应，以解决多个粒子同时碰撞或复杂几何体之间的相互作用。
   自碰撞：
   自碰撞处理更具挑战性（我也没做没搞明白逃！！！），因为需要检测由同一个对象构成的不同部分之间的接触。尤其是当模拟像布料这样的薄膜物体时，越是逼真的动态特性，自碰撞的可能性就越高。
5. 忽略近邻：在检测自碰撞时，忽略靠得非常近的面片或粒子（即面片之间共用顶点或边的相邻面片），因为它们很可能是已知的连续部分，不应该视为碰撞。
6. 优化检测：对于布料自碰撞，可以使用空间分割策略或者通过考虑布料的运动趋势（动态BVH）优化检测算法。
7. 响应处理：类似于普通的碰撞响应，基于位置的碰撞处理方法也适用于自碰撞。这通常包括识别穿透并调整位置，使布料片段之间不会相互穿透。
   GDC分享：具有预测性接触的布料自碰撞

约束：

布料的弯曲问题： 用上面的弹簧模型来对布料建模时，如果布料只发生了非常轻微的弯曲，弹簧只发生微小的形变，弹簧产生的抵抗力也非常小这个不正常。 解决办法：在弹簧质点系统中，加上一条对角边弹簧。下图

PBD算法中模拟布料、软体组成材料的弯曲行为时，常会用到"二面角模型"（Bending Models），以处理连续面之间的弯曲约束。**二面角是指两个相邻面片间的夹角，也称为折叠角或弯曲角。通过控制这个角度，在模拟布料或其他薄膜物体时可以处理物体的弯曲及折叠行为。**在三维模型中，它通常是由四个连接的顶点定义，其中两个顶点为公共边上的粒子，另外两个分别属于两个不同平面。计算这四个顶点的位置可以得到两个相交面片的法线向量，进而算出它们之间的夹角。
原理简单来说就是先算出二面角，应用弯曲约束:1、 判断当前二面角与目标二面角（布料原始状态或设计状态）的差异。如果二者不相等，需要根据差异来计算出顶点位置的修正量。
2、 一般会通过能量最小化方法来求解这个修正量，即找出顶点位置修正值，使得当前二面角尽可能接近目标二面角。求解约束的过程可以是迭代的，依赖于约束的强度以及相关顶点的质量。（ 详细请看：A Triangle Bending Constraint Model
for Position-Based Dynamics），

PBD 移动端布料模拟

官方文档：NvCloth官方文档
项目代码：NvCloth
布料仿真大佬王华民聊移动端布料模拟PBD图形学的未来：投身业界、布料仿真大牛王华民谈实时模拟的前世今生

position-based dynamics （PBD ）算法：

算法的步骤：
(1)-(3) 初始化所有粒子的位置，速度，和质量
(5) 施加外力，包括重力和玩家施加的力
(6) 对速度阻尼
(7) 预测新的位置Pi
(8) 动态生成碰撞约束
(10) 使用约束 对(7)中预测的位置进行矫正
(13)-(14) 将矫正后的位置，更新到最新的粒子位置和速度上
(16) 更新速度，主要是防止小速度震荡。

优点：计算量较低能在移动端运行，PBD算法相较于基于力的动力学算法来说更为直观和相对于其他复杂的布料模拟算法易于实现，PBD是迭代算法，可以根据应用的性能需求来调整迭代次数，以平衡速度和精度。

缺陷：PBD算法实际上有一个比较大的缺陷即其约束求解不那么物理，这导致的一个问题是，模拟的时间间隔(time step)和约束求解迭代次数(iteration count)会对物体的刚性度（stiffness）产生影响。可能迭代次数都要重新调整。调不好迭代次数导致求解出数值不稳定的结果，可能还有数值爆炸的危险！所以PBD作者数年后推出了新的X-PBD，即使这样PBD的优势是计算量不大，甚至可以实时高分辨率模拟，所以游戏或者VR/AR上够用了就是调参麻烦。

结论：PBD算法适用于：布料模拟,软体动力学比如凝胶、橡胶或其他非刚性物体,在粒子系统中模拟液体、烟雾、颗粒系统通过一定的约束可以达到模拟流体，绳索、线条和发丝的仿真。能量守恒并非是PBD的主要目标，我们更关注计算的稳定性和实时可交互性。移动端布料模拟仿真NvCloth 可行，可实现轻量化集成，并极具扩展性，nvcloth在移动端跑的neon在CPU上（就是SIMD，只要是ARM平台都支持中低端都可以，安卓、Iphone等），同时并不是所有的跑在Computer Shader上就更快在Windows中编译NvCloth 才3M大小，ios是2M。

基于GPU的PBD布料模拟

相对于Nv cloth与bullet3来说该方法使用的算法还是基于PBD，nvcloth是使用Verlet 积分法，的弹簧质子模型。移动端在图形AP I支持上对于安卓。安卓5.0以上都支持computer shader，这一块没问题。但是对于IOS只支持到es3.0所以不支持computer shader，metal所有功能都能支持。
基于GPU的PBD工程化可能存在到问题：

1. 碰撞体的碰撞需要自己实现。
2. 布料本身的自碰撞。
3. 布料GPU的模拟仿真还是很前沿开源或能参考的资料还是太少！

虽然存在问题，但是现在的GPU布料解算cs 手机性能上能操作百万顶点，如下资料：
GPU模拟布料
对应的代码
GPU布料物理模拟入门述
Unity GPU布料物理模拟入门
添使用AABB层次结构和GPU并行性的Cloth模拟
GPU Cloth Simulation in Unity (PBD)
GPU并行实现PBD算法的碰撞

参考资料：

PBD原始论文
布料模拟之基本原理
PBD教程
position based dynamics笔记
Magica Cloth 布料模拟使用心得，以及插件功能介绍