본 논문에서는 물리 시스템의 암시적 시간 적분(implicit time integration)을 위한 새로운 방법을 제시합니다. 저희의 접근법은 절점 기반 유한 요소법(nodal Finite Element methods)과 위치 기반 동역학(Position Based Dynamics) 사이의 간극을 메우며, 단순하고, 효율적이며, 강건하고, 정확하면서도 다양한 유형의 제약 조건을 지원하는 솔버로 이어집니다. 저희는 교대 최적화(alternating optimization) 접근법을 사용하여 효율적으로 풀 수 있는 특별히 설계된 에너지 포텐셜을 제안합니다. 연속체 역학(continuum mechanics)에서 영감을 받아, 저희 솔버에 효율적으로 통합될 수 있는 일련의 연속체 기반 포텐셜을 유도합니다. 고체, 천, 쉘 시뮬레이션부터 예제 기반 시뮬레이션에 이르기까지 다양한 응용 분야에서 저희 접근법의 일반성과 강건함을 입증합니다. 뉴턴 기반(Newton-based) 솔버 및 위치 기반 동역학 솔버와의 비교를 통해 저희 공식의 이점을 강조합니다.

변형 가능한 재료의 물리 기반 시뮬레이션은 컴퓨터 그래픽스의 여러 분야에서 필수적인 도구가 되었습니다. 가상 세계, 그리고 최근에는 캐릭터 애니메이션에서 근육, 지방, 머리카락, 의상, 또는 식생을 시뮬레이션하는 등 정교한 시뮬레이션을 통합하여 시각적 경험을 크게 향상시킵니다. 이러한 모델들은 종종 연속체 역학 공식의 유한 요소 이산화에 기반하며, 복잡한 비선형 재료의 매우 정확한 시뮬레이션을 가능하게 합니다.

사실성과 정확성 외에도, 컴퓨터 그래픽스 응용 분야에서는 여러 다른 기준들도 중요합니다. 일반성이란 고체, 쉘, 막대와 같은 다양한 유형의 기하학적 구조, 다양한 재료 특성, 또는 고전적인 물리 기반 시뮬레이션에 대한 아트 디렉팅이 가능한 확장 기능과 같이 광범위한 동작을 시뮬레이션할 수 있는 능력을 의미합니다. 견고성은 큰 변형, 퇴화된 기하학적 구조, 그리고 큰 타임 스텝을 포함한 어려운 구성을 적절하게 처리하는 능력을 말합니다. 견고성은 컴퓨터 게임이나 의료 훈련 시뮬레이터와 같이 시뮬레이션을 다시 실행할 '두 번째 기회'가 없는 실시간 응용 분야에서 특히 중요합니다. 솔버의 단순성은 종종 실제적인 관련성에서 중요합니다. 단순하고 이해하기 쉬운 개념을 기반으로 구축하고, 그 결과로 가벼운 코드베이스를 만드는 것은 시뮬레이터의 유지보수를 용이하게 하고 특정 응용 프로그램의 요구에 맞게 조정할 수 있도록 합니다. 성능은 실시간 응용 분야를 위한 중요한 가능 조건입니다. 그러나 성능은 새로운 장면과 시뮬레이션 파라미터를 테스트하는 데 걸리는 시간을 최소화해야 하는 오프라인 시뮬레이션에서도 마찬가지로 중요합니다.

현재의 연속체 역학 접근법은 특정 컴퓨터 그래픽스 응용 분야에서 이러한 기준들 사이에 종종 불리한 트레이드오프를 가지며, 이는 Position Based Dynamics (PBD)와 같은 대안적인 방법의 개발로 이어졌습니다. 그 일반성, 단순성, 견고성, 그리고 효율성 덕분에, PBD는 현재 PhysX, Havok Cloth, Maya nCloth, 그리고 Bullet을 포함한 광범위한 고급 제품에 구현되어 있습니다. 주로 실시간 응용 분야에서 사용되지만, PBD는 오프라인 시뮬레이션에서도 종종 사용됩니다. 그러나 PBD의 바람직한 특성들은 제한된 정확성이라는 대가를 치르는데, 이는 PBD가 연속체 역학 원리로부터 엄밀하게 유도되지 않았기 때문입니다.

우리는 연속체 역학과 PBD 사이의 간극을 메우는 새로운 암시적 통합 솔버를 제안합니다. 핵심 아이디어는 특정 구조를 가진 에너지 포텐셜을 도입하는 것입니다. 더 정확하게 말하면, 우리의 포텐셜은 제약 조건으로부터의 볼록 이차 거리 측정으로 구성됩니다. 제약 조건은 요소의 원하는 상태를 표현하는 일반적인 비선형 함수이며, 예를 들어 사면체의 부피가 주어진 범위 내에 유지되어야 한다는 것과 같습니다. 거리 측정은 주어진 변형된 구성에서 개별 제약 조건이 얼마나 위반되었는지를 정량화합니다. 우리의 솔버는 임의의 기하학적 제약 조건을 처리할 수 있지만, 우리는 연속 변형 에너지로부터 유도된 특정 제약 조건 집합을 제안합니다. 이러한 연속체 기반 제약 조건은 특히 해상도가 다르거나 균일하지 않은 테셀레이션의 메시를 다룰 때 파라미터 튜닝을 상당히 단순화하기 때문에 매우 실용적입니다.

우리 제약 기반 포텐셜의 주요 장점은 그 구조가 효율적인 지역/전역 최적화(블록 좌표 하강법)를 가능하게 한다는 것입니다. 구체적으로, 지역 단계는 모든 요소를 제약 매니폴드에 투영하는 것으로 구성됩니다. 즉, 요소별로 작은 비선형 문제를 푸는 것입니다. 전역 단계는 개별 투영의 결과들을 결합하여, 관성 및 외력과 같은 전역적 효과를 고려하면서 모든 개별 제약 조건들 사이의 절충안을 찾습니다.

지역/전역 접근법을 통해 우리는 어떠한 특별한 예방 조치 없이도 매 반복마다 에너지를 약하게 감소시키는 것이 보장되는 암시적 통합 솔버를 공식화할 수 있습니다. 이는 강건성을 보장하기 위해 라인 서치 전략과 특이하거나 비한정적인 헤시안에 대한 안전장치를 요구하는 고전적인 뉴턴 방법과 대조됩니다. 더욱이, 고정된 제약 조건 집합을 사용하면, 전역 단계의 선형 시스템을 미리 인수분해할 수 있어 계산 시간을 크게 줄일 수 있습니다. 지역 단계는 작고 독립적인 최적화 문제들로 구성되어 있어, 모두 병렬로 실행될 수 있습니다.

우리가 아는 한, 우리 방법은 일반적인 동역학 시스템을 시뮬레이션하기 위해 지역/전역 최적화를 적용한 최초의 사례입니다. 우리는 이 해법이 암시적 통합에 대한 강건하고 효율적인 접근법을 제공하며, 종종 고전적인 뉴턴 방법을 상당히 능가함을 보여줍니다. PBD와 우리 솔버 간의 연결은 PBD가 유한 요소법과 뉴턴 역학에 기반한 전통적인 접근법과 어떻게 관련되는지에 대한 새로운 통찰을 드러냅니다.

Terzopulous et al./1987/Continuum Models의 선구적인 연구 이래로, 연속체 역학에서 파생된 모델들은 물리 기반 애니메이션에서 중요한 역할을 해왔습니다. 기본 원리는 탄성 물체의 변형에 대한 저항을 탄성 위치 에너지를 사용하여 정량화하는 것입니다. 이는 변분 도함수가 탄성력을 유도하는 스칼라 함수입니다 [Sifakis and Barbic/2012/FEM Simulation]. 불행히도, 탄성력은 기본적인 재료 모델에 대해서도 보통 비선형적이어서, 결과적인 운동 방정식의 시간 적분을 복잡하게 만듭니다.

컴퓨터 그래픽스에서 사용되는 가장 간단한 시간 적분 기법은 명시적 방법이며 큰 타임 스텝에 매우 취약합니다 [Press et al./2007/Numerical Recipes]. 암시적 오일러 방법은 안정성을 크게 향상시키지만 [Baraff and Witkin/1998/Large Steps], 매 스텝마다 비선형 방정식 시스템을 풀어야 하는 비용이 따릅니다. Martin et al./2011/Example-Based Elasticity에서 보여주었듯이, 이는 힘 대신 탄성 위치 에너지에 직접 작용하는 비볼록 최적화 문제로 동등하게 공식화될 수 있습니다. 암시적 오일러 적분의 주요 단점 중 하나는 인위적인 수치적 감쇠입니다. 이는 더 나은 에너지 보존 특성을 특징으로 하는 심플렉틱 적분기 [Hairer et al./2002/Geometric Numerical Integration, Kharevych et al./2006/Symplectic Integrators]와 혼합 암시적-명시적 방법(IMEX) [Bridson et al./2003/IMEX for Cloth, Stern and Grinspun/2009/IMEX for Thin Shells]의 개발을 동기 부여했습니다. 또 다른 접근법은 에너지를 명시적으로 보존시키는 에너지 버짓팅 [Su et al./2013/Energy Budgeting]입니다. 그러나 암시적 오일러 적분은 안정성이 중요한 기준이고 수치적 감쇠가 주요 관심사가 아닌 물리 기반 애니메이션 응용 분야에서 계속해서 널리 사용되는 선택지 중 하나입니다. 저희 솔버는 암시적 오일러 적분의 변분 형태 [Martin et al./2011/Example-Based Elasticity]에서 파생되었는데, 이는 저희 프레임워크에서 시간 적분에 대해 직관적인 사고방식을 제공하기 때문입니다 – 단순히 시스템에 또 다른 제약 조건을 추가하는 것입니다. 이는 더 나아가 PBD와 암시적 오일러 적분 기법 사이의 연관성을 도출하게 하고, 큰 타임 스텝에서도 안정적인 견고하고 효율적인 접근법으로 이어집니다.

특정한 암시적 적분의 방식이나 공식화에 관계없이, 뉴턴 방법은 비선형 방정식 시스템을 푸는 데 있어 계산의 핵심 도구로 남아있습니다. 그러나 이의 견고한 구현은 보수적인 선 탐색 절차와 불확정 헤시안에 대한 안전장치와 같은 예방 조치를 필요로 합니다 [Boyd and Vandenberghe/2004/Convex Optimization]. 성능 관점에서 뉴턴 방법의 심각한 단점은 헤시안 행렬과 그래디언트가 매 반복마다 바뀐다는 사실입니다. 따라서 준-뉴턴 방법은 근사 헤시안을 사용하여, Desbrun et al./1999/Implicit Animation과 Hahn et al./2012/Fast FEM에서 보여주듯이, 더 빠른 선형 시스템 해결을 위해 차선의 하강 방향(따라서 더 느린 수렴)을 감수합니다. 유사한 전략으로, 공회전 탄성(co-rotated elasticity)의 맥락에서 탐구된 것은 희소 콜레스키 분해의 신중하게 계획된 업데이트를 사용하는 것입니다 [Hecht et al./2012/Co-rotated Elasticity]. 최근에 Liu et al./2013/Fast Mass-Spring은 교대 지역/전역 최적화를 가능하게 하는 보조 변수를 도입하여 질량-스프링 시스템의 효율적인 암시적 시간 적분 방법을 제시했습니다. 블록 좌표 하강법으로도 알려진 이 접근법은 이전에 기하학 처리 분야에서 큰 성공을 거두며 사용되었습니다 [Sorkine and Alexa/2007/Laplacian Surface Editing, Bouaziz et al./2012/Shape-Up]. 저희도 접근법에서 지역/전역 교대를 사용하지만, 질량-스프링 시스템에 국한되고 선형 스프링(훅의 법칙)만을 가정하는 Liu et al./2013/Fast Mass-Spring과는 달리, 저희는 제약 조건 집합으로의 프로젝션을 사용하여 일반적인 절점 동역학 시스템을 시뮬레이션하도록 이 개념을 일반화하는 방법을 보여줍니다.

저희의 제약 조건 기반 공식화는 제약 조건 프로젝션에 기반한 최근의 비전통적인 접근법들과 일부 유사점을 가집니다. 제약 조건 프로젝션의 아이디어는 Nucleus 시스템 [Stam/2009/Nucleus]과 Position Based Dynamics [Müller et al./2007/PBD, Bender et al./2013/PBD Survey]의 핵심입니다. 저희의 해결책과 대조적으로, 이 방법들은 제약 조건을 전역적인 방식으로 다루지 않고, (비선형적인) 가우스-자이델과 유사한 방식으로 반복적으로 제약 조건에 프로젝션합니다 [Müller et al./2007/PBD]. 결과적인 알고리즘은 구현이 매우 쉽지만, 이 접근법은 여러 단점을 가집니다: 가우스-자이델 최적화는 매우 빠르게 수렴하지 않고, 재료 강성이 반복 횟수에 의존하며, 결과가 순회 순서에 따라 달라집니다. 반면, 저희 방법은 제약 조건을 사용하여 뉴턴의 운동 법칙에 따라 관성 항과 엄격하게 결합되는 탄성 위치 에너지를 공식화합니다. 저희 솔버는 먼저 모든 제약 조건 프로젝션을 개별적으로 계산한 다음 그들 사이의 최상의 타협점을 찾아내어, 해가 제약 조건의 순서에 독립적이게 만듭니다. 더 빠른 수렴을 얻기 위해, 제약 조건은 미분 좌표를 사용하여 표현되며, 이는 종종 단 몇 번의 반복만으로 만족스러운 결과를 낳습니다. 더욱이, 저희 솔버는 저희의 탄성 에너지로 진정한 암시적 오일러 해로 수렴하는 반면, Position Based Dynamics는 완전히 비탄성적인 거동으로 수렴합니다.

또 다른 밀접하게 관련된 개념은 형상 매칭(shape matching) [Müller et al./2005/Shape Matching, Rivers and James/2007/FastLSM]인데, 저희 방법과 대조적으로 변형 가능한 객체를 시뮬레이션하기 위해 위치 에너지 대신 탄성력을 직접 구축하는 데 제약 조건 프로젝션을 사용합니다. 제약 조건 프로젝션은 또한 독립적인 시뮬레이션 기법으로서가 아니라 표준 시간 적분 방법으로 뻣뻣한 시스템의 처리를 개선하는 방법으로서 변형률 제한(strain limiting) [Provot/1995/Strain Limiting, Goldenthal et al./2007/Efficient Simulation, Thomaszewski et al./2009/Stretching and Bending, Wang et al./2010/Strain Limiting, Narain et al./2012/Adaptive Tearing]에 사용되었습니다. 저희 접근법에서도 변형률 제한을 수행할 수 있지만, 이는 암시적 솔버에 직접 포함됩니다.

이 섹션에서는 우리 방법의 기초를 형성하는 포텐셜의 특별한 구조를 소개합니다. 우리는 FEM으로 이산화된 탄성 모델의 암시적 시간 적분부터 시작하겠습니다.

이제

먼저, 위치를 고정한 채로 보조 변수들에 대해 수식 8을 최소화합니다. 각 제약조건은 자신만의 보조 변수 집합 $p_i$를 가지므로, 최소화는 각 제약조건에 대해 독립적으로 수행될 수 있습니다.

이는 지역 단계의 대규모 병렬화를 가능하게 합니다. 구체적인 제약조건 유형은 섹션 5에서 논의할 것입니다.

두 번째로, 보조 변수들을 고정한 채로 위치에 대해 수식 8을 최소화합니다. 수식 8은 미지수 $q$에 대해 이차식이므로, 단일 선형 풀이로 최소화할 수 있습니다. 임계점에서 그래디언트가 0이 되어야 한다는 조건을 요구하면 다음과 같은 선형 시스템이 도출됩니다.

시스템 행렬은 제약조건이 변하지 않는 한 일정하므로 초기화 시점에 미리 분해(prefactor)할 수 있어 매우 효율적인 전역 풀이를 가능하게 합니다. 우변은 지역 단계에서 투영 변수들이 업데이트된 후 각 반복마다 재계산이 필요합니다. 목적 함수는 아래로 유계이고, 지역 및 전역 단계 모두 비볼록 집합에 대해서도 에너지를 약하게 감소시키는 것이 보장됩니다. 결과적으로 최적화는 수렴하며, 안전장치가 불필요해집니다.

우리의 최적화 절차를 알고리즘 1에 요약했습니다. 2행에서 우리는 운동량 추정치 $s_n$을 사용하여 최적화를 웜 스타트(warm start)합니다. 우리는 이것이 단지 몇 번의 솔버 반복만 사용할 때 유리하며, 이전 타임스텝의 해를 시작점으로 사용하는 것보다 감쇠가 덜한 시스템으로 이어진다는 것을 관찰했습니다. 여러 번의 지역/전역 반복을 푼 후, 9행에서 속도가 업데이트됩니다.

만약 $A_i = B_i = I$를 선택하면, 수식 7은 $S_iq$로부터 제약조건 집합 위의 가장 가까운 점까지의 유클리드 거리 제곱을 측정합니다. 대각 행렬을 사용하면, 전역 풀이의 헤시안 행렬도 대각 행렬이 되어 풀어야 할 선형 시스템이 자명해집니다. 하지만 이 선택은 절대 위치를 직접 다루는 것에 해당하며, 이는 (일반적으로 지역적으로) 결합된 점들을 통해 변화가 느리게 전파되기 때문에 형편없는 수렴 속도를 초래합니다 (Bouaziz et al. 2012).

내부 물리적 제약조건이 병진 불변(translation invariant)이라는 사실을 활용하면 수렴 속도를 크게 향상시킬 수 있습니다 (즉, 제약조건에 포함된 모든 점에 공통된 병진을 적용해도 제약조건의 값은 변하지 않습니다). 이 경우, 우리는 $A_i = B_i$를 미분 좌표 행렬(널 스페이스에 전역 병진을 가짐)로 선택할 수 있습니다. 예를 들어 평균을 빼거나(Bouaziz et al. 2012) 제약조건에 포함된 정점 중 하나를 단순히 빼는(Liu et al. 2013) 등 다양한 행렬을 사용할 수 있습니다. $A_i$와 $B_i$의 선택은 수치적 해결 절차에만 영향을 미치며 운동량 보존에는 영향을 주지 않는다는 점에 유의해야 합니다.

이러한 미분 좌표를 사용하면 결과적인 지역/전역 솔버의 수렴 속도가 크게 향상됩니다(Bouaziz et al. 2012). 하지만, 별도의 예방 조치 없이는 결과적인 동작이 테셀레이션과 해상도에 의존적이게 됩니다. 섹션 5에서는 특정 경우에 이러한 단점을 피하기 위해 연속체 공식으로부터 $A_i$와 $B_i$ 행렬을 유도할 수 있음을 보여줄 것입니다.

Liu et al./2013/Fast Simulation에서는 일반적인 변분적 암시적 오일러와 PBD 사이의 유사성을 암시했지만, 본 섹션에서는 암시적 오일러와 PBD 사이뿐만 아니라, 일반적인 제약 조건에 대해 지역/전역 공식화와 PBD 사이의 정확한 관계를 유도합니다. 이 분석은 PBD와 저희 솔버의 긴밀한 연관성을 강조하지만, 저희 접근법으로 얻은 결과의 더 높은 정확도를 설명하는 근본적인 차이점 또한 식별합니다.

고전적인 PBD 솔버[Müller/2007/PBD]는 세 단계를 수행합니다. 첫 번째 단계에서는 내부 힘을 무시하고 명시적 오일러 단계(explicit Euler step)로 위치를 초기화합니다. 두 번째 단계에서는 질량 가중치를 고려하여 현재 구성을 각 제약 조건 집합에 순차적으로 투영하여 위치를 업데이트합니다. 마지막 단계에서는 속도를 $v_{n+1} = (q_{n+1} - q_n)/h$로 업데이트합니다.

우리는 PBD의 제약 조건 해결 전략이 실제로는 다음 에너지에 대한 가우스-자이델(Gauss-Seidel) 유형의 최소화를 구현한다는 것을 보일 수 있습니다.

여기서 제약 조건의 점들만 포함하는 집중 질량 행렬(lumped mass matrix) $M_i$를 사용합니다. 가우스-자이델 접근법은 각 항을 순차적으로 최적화하여 이 에너지를 최소화합니다. 즉, 유도를 단순화하기 위해 수정량 $\Delta q = p - q$를 도입하여 $\frac{1}{2}\|M^{\frac{1}{2}} \Delta q\|_F^2 + \delta_C(q + \Delta q)$ 형태의 포텐셜을 최소화합니다. 선형화된 제약 조건 $C(q) + \text{tr}(\nabla C(q)^T \Delta q) = 0$에 대해 라그랑주 승수(Lagrange multipliers)를 사용하여 라그랑지안을 정의할 수 있습니다.

$\Delta q$에 대한 임계점 조건을 사용하여 최적 방향 $\Delta q = -\lambda M^{-1} \nabla C(q)$를 찾습니다. 그 다음, 이 방향에서 선형화된 제약 조건이 0이 되도록 요구하여 라그랑주 승수 $\lambda$를 찾을 수 있습니다. 즉, $C(q) - \lambda \|M^{-\frac{1}{2}} \nabla C(q)\|_F^2 = 0$이며, 이는 최종 업데이트로 이어집니다.

이는 PBD의 질량 가중 업데이트 규칙과 정확히 일치합니다 [Bender/2013/Interactive Simulation of Elastic Deformable Bodies].

이론적으로 가우스-자이델은 좋은 수렴성을 가지지만, 실행 가능한(feasible) 제약 조건 집합에 대해서만 그렇습니다. 실행 불가능한 집합에 대해서는, 최적화 문제에 대한 전역적인 시각이 부족하여 가우스-자이델은 호환되지 않는 집합들 사이에서 진동할 것입니다 (Fig. 3 참조). 예를 들어, 늘이기 제약 조건과 경계 조건 또는 충돌이 있는 탄성 재료의 압축을 시뮬레이션할 때, 제약 조건이 실행 불가능해질 수 있으며 따라서 해는 진동하고 수렴하지 않을 것입니다.

더 심각하게는, 첫 번째 단계에서 수행되는 운동량 추정에도 동일한 문제가 적용되는데, 이는 수식 5에 주어진 제약 조건을 먼저 푸는 것으로 구성됩니다. 만약 이것이 최적화에 실제 제약 조건으로 추가된다면, 완전히 호환되지 않는 제약 조건 집합을 초래하고 수렴을 더욱 악화시킬 수 있습니다. 초기 명시적 오일러 단계로 운동량 제약 조건을 먼저 해결함으로써 전체 객체의 선형 운동량을 유지하는 것은 가능하지만, 최적화 반복이 길어질수록 각 점의 개별 운동량은 사라지게 됩니다 – 이는 우리가 제안하는 암시적 오일러 솔버가 제안하는 것처럼 운동량과 내부 탄성 사이의 절충안을 찾는 것과는 대조적입니다 (Fig. 4 참조).

수식 11의 관점에서, 우리는 두 단계를 수행함으로써 이러한 문제들을 간단한 방식으로 해결할 수 있습니다.

첫째, 우리는 Gauss-Seidel을 양립 불가능한 제약 조건들을 처리할 수 있는 Jacobi 솔버(그림 3 참조)로 대체합니다.

Jacobi 솔버는 일반적으로 Gauss-Seidel 솔버보다 수렴 속도가 느립니다 Thomaszewski/2009/Fast Simulation.

하지만, 이들은 더 빠른 수렴을 위한 미분 좌표 표현의 사용과 이 단점을 해결하는 제약 조건 프로젝션의 효율적인 병렬화를 가능하게 합니다.

둘째, 우리는 각 점의 관성을 고려하기 위해 최적화에 운동량 제약 조건을 도입합니다.

연속체 역학 관점에서 보았듯이, 올바른 거동을 달성하기 위해서는 수식 5에 정의된 운동량 제약 조건 항을 통합하여 각 점의 관성을 다시 더해주어야 합니다.

Jacobi 솔버는 두 단계 최적화가 됩니다: 로컬 단계에서는 현재 해 $q$가 먼저 모든 $p_i$에 대해 수식 11을 풀어 제약 조건에 독립적으로 투영됩니다.

그 다음, $q$에 대한 글로벌 단계를 해결함으로써 다른 해들 사이의 합의에 도달할 수 있습니다.

이 단계에서, 우리는 이 Jacobi 솔버가 지난 섹션에서 제시된 우리의 투영 기반 암시적 솔버 절차와 얼마나 가까운지 알 수 있습니다 – 우리는 $A_i = B_i = M_i^{1/2}$를 선택함으로써 이 솔버를 복원할 수 있습니다.

다음 섹션에서 연속체 원리로부터 제약 조건을 유도함으로써, 우리는 더 나아가 PBD에서 사용되는 더 간단한 질량 기반 가중치 부여 방식보다 메시 테셀레이션 및 수렴에 대한 더 나은 독립성을 달성합니다 (그림 5 참조).

미분 표현(Differential representations)은 우리의 지역/전역 솔버(local/global solver)의 수렴성을 개선하는 데 중요합니다.

기하학 처리(Geometry processing)에서 그래디언트(gradient)와 라플라스-벨트라미 연산자(Laplace-Beltrami operators)는 효율적이고 강건한 모델을 설계하는 데 필수적인 역할을 합니다.

이 섹션에서는 변형 중인 재료의 미분 속성을 제어할 수 있게 해주는, 이러한 연산자들을 기반으로 한 연속 에너지(continuous energies) 세트를 제시할 것입니다.

우리는 그것들의 이산화(discretizations)가 메쉬 세분화 및 비균일 이산화 하에서도 올바른 동작을 가능하게 하는, 수식 7과 유사한 형태를 가질 것임을 보일 것입니다.

이산 포텐셜(discrete potentials)의 지역 최적화(local optimization)는 부록 A에서 논의될 것입니다.

변형률 에너지는 늘어날 수 있는 재료를 시뮬레이션하는 데 중요합니다.

먼저 2-매니폴드 표면을 논의한 다음, 그 결과를 부피와 곡선으로 확장합니다.

변형되지 않은 표면을 $\mathbb{R}^3$에 포함된 미분 가능한 2-매니폴드 표면 $S$라고 가정합시다.

변형되지 않은 표면의 조각별 선형 좌표 함수를 $g : S \rightarrow \mathbb{R}^3$로, 변형된 표면의 좌표 함수를 $f : S \rightarrow \mathbb{R}^3$로 정의합니다.

원하는 점별 변환 $T$의 집합 $M$을 도입하여, 변형된 표면과 변형되지 않은 표면 사이의 국소적 변화량을 측정하는 에너지를 다음과 같이 공식화합니다.

여기서 $\nabla_S$는 매니폴드 표면 $S$에 정의된 그래디언트 연산자입니다.

$M$의 선택은 허용되는 모든 정지 상태 구성 $T\nabla_S g$를 결정합니다.

만약 $M$이 회전 행렬의 집합 $SO(3)$이라면, 우리는 강체 운동으로부터의 국소적 편차를 간단히 측정하는 것입니다.

이 경우 이 에너지는 Chao et al./2010/Deformation Model에서 제시된 변형 모델과 동일합니다.

만약 $M$이 제한된 특이값 $\sigma_{min} < \sigma < \sigma_{max}$를 갖는 행렬의 집합이라면, Wang et al./2010/Strain Limiting과 유사하게 등방성 변형률 제한을 달성할 수도 있습니다.

이는 Hernandez et al./2013/Anisotropic Material을 따라 참조 프레임을 사용하여 이방성 재료로 더욱 확장될 수 있습니다.

S가 2-매니폴드 단체 복합체(simplicial complex)인 경우, 이 에너지는 Botsch et al./2010/Polygon Mesh Processing의 조각별 선형 햇 기저(hat basis)를 사용하여 삼각형에 대해 이산화될 수 있습니다.

그러면 적분은 삼각형별 포텐셜의 합으로 변환되며, 그 형태는 다음과 같습니다.

여기서 $A$는 삼각형의 면적이고, $X_f = [q_j - q_i, q_k - q_i] \in \mathbb{R}^{2\times2}$는 현재 구성의 삼각형 모서리들을 2D에 등거리로 임베딩한 것을 포함하며, 유사하게 $X_g$는 정지 상태 구성의 삼각형 모서리들을 포함합니다.

이 이산 포텐셜은 수식 7과 동일한 형태를 가지며, 여기서 $A$는 정지 상태 모서리와 면적의 함수이고 $B$는 정지 상태 면적에만 의존한다는 점에 유의하십시오.

Fig. 6은 커튼 예제에 변형률 제한 제약조건이 적용된 것을 보여줍니다.

이 포텐셜은 부피에 대해서도 유사한 방식으로 정의될 수 있습니다: 만약 $S$가 3-매니폴드 단체 복합체라면, 에너지는 삼각형의 면적을 사면체의 부피로 대체하고 $3 \times 3$ 모서리 행렬을 사용하여 사면체에 대해 이산화될 수 있습니다.

만약 이 에너지를 1D 이산화를 수행하면, Liu et al./2013/Fast Mass-Spring의 질량-스프링 모델의 빠른 시뮬레이션과 유사한 모델에 도달하게 되는데, 추가적으로 모서리 포텐셜이 이제 모서리 길이에 의해 적절히 가중치가 부여된다는 점에 유의하십시오.

면적 및 부피 보존은 비압축성 재료를 시뮬레이션하는 데 중요합니다.

수식 15의 연속 에너지를 사용하여, 우리는 M을 행렬식의 경계가 정해진 행렬들의 집합, 즉 $\sigma_{min} < \det(T) < \sigma_{max}$로 정의할 수 있으며, 이를 통해 부피 변화량을 효과적으로 제어할 수 있습니다.

만약 $\sigma_{min} < 1$이면 모델링된 재료는 압축을 허용하고, 유사하게 $\sigma_{max} > 1$이면 재료는 팽창을 허용합니다.

그림 7은 부피 보존 제약과 변형률 제약의 조합을 보여줍니다.

예제 기반 시뮬레이션은 재질이 따라야 할 몇 가지 변형 예제를 제공함으로써 예술적인 탄성 재질의 거동을 모델링할 수 있게 해줍니다 Martin/2011/Example-Based Deformations, Koyama/2012/Subspace-based Twist, Jones/2013/Art-directed Wrinkles. 저희는 3-매니폴드 표면에 정의된, 수식 15와 유사한 에너지를 다음과 같이 사용합니다.

여기서 $h(w)$는 예제들에 의해 정의된 파라미터화된 정지 형상입니다. 저희는 정지 형상을 $h(w) = g + \sum_i w_i(R_i g_i - g)$로 공식화합니다. 여기서 $g_i$는 예제들의 조각별 선형 좌표 함수를 정의하고, $R_i$는 변형되지 않은 구성 $g$와 가장 잘 정렬되도록 $g_i$를 국소적으로 회전시키는, 점별로 정의된 사전 계산된 회전 행렬이며, 이는 Koyama/2012/Subspace-based Twist의 정신과 유사합니다.

이 연속 에너지를 조각별 선형 햇 기저(hat basis)를 사용하여 이산화하면, 각 사면체에 대한 포텐셜의 합으로 이어집니다.

여기서 $X_{h(w)} = X_g + \sum_i w_i(R_i X_{g_i} - X_g)$입니다. 예제 가중치 $w$는 각 요소별로 국소적으로 정의되거나 전역적으로 정의될 수 있으며, 이는 각각 변형의 국소적 또는 전역적 커플링을 초래한다는 점에 유의해야 합니다. 이 제약 조건을 사용하는 세 대의 충돌하는 자동차 예시는 Fig. 8에서 찾아볼 수 있습니다.

얇은 쉘과 얇은 판은 일반적으로 모서리를 가로지르는 이시면 각(dihedral angles)에 기반한 굽힘 에너지(bending energy)를 사용하여 시뮬레이션됩니다 Grinspun et al./2003/Discrete Shells. 더 최근에는, 라플라스-벨트라미 연산자(Laplace-Beltrami operator)를 평균 곡률 법선(mean curvature normal)에 연관시키는 비신축성 표면의 굽힘에 대한 효율적인 모델들이 제시되었습니다 Bergou et al./2006/Discrete Elastic Rods, Garg et al./2007/Mean Curvature Skeletons. 우리는 절대 평균 곡률의 제곱 차이를 측정하는 굽힘 에너지를 도입합니다.

여기서 $H_f$와 $H_g$는 각각 변형된 표면과 변형되지 않은 표면의 평균 곡률 함수입니다. 등거리 변형(비신축성 표면)의 경우, 우리는 보조 회전 행렬을 사용하여 에너지를 다음과 같이 다시 쓸 수 있습니다.

여기서 $\Delta_S$는 매니폴드 표면 $S$에 정의된 라플라스-벨트라미 연산자입니다. 이는 평균 곡률 벡터가 좌표 함수에 적용된 표면의 라플라스-벨트라미 연산자와 같기 때문입니다. 등거리 변형의 경우 라플라스-벨트라미 연산자는 변하지 않으므로 변형되지 않은 표면에 정의될 수 있습니다. 수식 20이 그래디언트를 라플라스-벨트라미로 대체하여 수식 15와 얼마나 유사한지 주목해 주십시오. 따라서 스트레인 제한 및 예제 기반 개념을 굽힘 에너지에도 적용하는 것이 흥미로울 수 있습니다.

그림 9: 왼쪽에서 오른쪽으로 굽힘 가중치를 증가시키며 얇은 쉘 실린더를 시뮬레이션합니다. 실린더가 압축될 때, 다른 주파수의 좌굴 패턴이 나타납니다.

만약 $S$가 2-매니폴드 단체 복합체(simplicial complex)라면, 수식 20은 조각별 선형 햇 기저(hat basis)를 사용하여 이산화될 수 있으며, 이는 다음과 같은 형태의 정점별 포텐셜의 합으로 이어집니다.

여기서 $A$는 정점의 보로노이 영역(Voronoi area)이고, $X_f$와 $X_g$는 각각 현재 구성과 나머지 구성에 대한 정점의 1-링(one-ring) 간선을 포함합니다. 벡터 $c$는 보로노이 영역으로 나눈 공통 코탄젠트 가중치(cotangent weights)를 저장합니다 Botsch et al./2010/Polygon Mesh Processing. 굽힘 제약조건의 예는 그림 9에서 찾을 수 있습니다. 부록에서 볼 수 있듯이, 이 굽힘 제약조건은 변형된 구성의 평균 곡률 벡터의 단순한 정규화로 구현될 수 있으므로 매우 효율적인 지역적 해결(local solve)이 가능합니다.

이전 섹션에서 제시된 연속 에너지로부터 파생된 제약조건들은 다양한 탄성체를 모델링할 수 있게 해줍니다. 실용적인 애니메이션 시스템에서는 추가적인 제약조건들도 똑같이 중요합니다. 우리는 이러한 것들을 직접 이산 제약조건(discrete constraints)으로 모델링합니다.

앞서 보았듯이, 개별 자유도(DoF)는 수식 7에서 단순히 $A_i = B_i = I$를 선택함으로써 직접 제약될 수 있습니다. 그러면 디리클레 경계 조건(Dirichlet boundary conditions)은 제약조건 집합을 원하는 목표 위치로 정의함으로써 구현될 수 있으며, 이를 통해 객체를 고정하거나 상호작용 핸들을 만들 수 있습니다.

충돌을 암시적(implicit) 방식으로 처리하는 것은 우리의 일반적인 솔버에 자연스럽게 들어맞으며, 충돌 해결 중에 운동량과 내부 제약조건의 평형을 존중할 수 있게 합니다. 충돌을 감지하면, 우리는 동적으로 새로운 단측 평면 제약조건(unilateral plane constraints)을 추가합니다. 위치 제약조건과 마찬가지로, 우리는 다시 수식 7에서 $A_i = B_i = I$를 선택합니다. 충돌하는 점 $q_c$에 대해, 우리는 먼저 법선 $n$을 가진 가장 가까운 표면 점 $b$를 찾아 충돌 평면을 정의하고, 제약조건 집합 $C$는 반공간 $n^T (q - b) \geq 0$에 의해 정의됩니다. 지역적 단계에서 이 반공간으로의 투영은 평면 투영이거나 항등 사상이므로 간단합니다. 충돌 제약조건을 단측으로 정의하면 암시적 충돌 처리에서 흔히 알려진 고착 문제(sticking problems)를 극복할 수 있다는 점에 유의하십시오. PBD와 유사하게, 우리는 속도를 업데이트할 때 충돌하는 정점의 속도를 변경하여 마찰과 반발을 처리합니다. 간단한 감쇠 모델은 속도를 필터링하여 구현할 수도 있습니다 Müller et al./2007/Position Based Dynamics.

예를 들어 Bender et al./2013/Position-Based Simulation Methods의 힌지 각도(hinge angles)를 사용하는 굽힘 제약조건과 같은 일반적인 유형의 기하학적 제약조건(geometric constraints)은 우리 솔버에 쉽게 통합될 수 있습니다. 지역적 해결은 보조 변수에 대해 수식 7을 최소화함으로써 일반적인 방식으로 수행될 수 있습니다. 많은 기하학적 제약조건에 대해 이 최소화를 위한 닫힌 형태의 해를 찾을 수 있습니다 Bouaziz et al./2012/Interactive editing of deforming meshes. 닫힌 형태의 해가 존재하지 않는 경우, 최적화는 순차적 2차 계획법(SQP)을 사용하여 해결할 수 있습니다 Nocedal and Wright/2006/Numerical Optimization. 섹션 4.1에서 보았듯이, $A = B = M^{1/2}$의 경우 SQP의 한 단계는 PBD 업데이트와 유사합니다 Bender et al./2013/Position-Based Simulation Methods.

이전 섹션에서 제시된 연속 에너지로부터 파생된 제약 조건들은 다양한 탄성체를 모델링할 수 있게 해줍니다.

실용적인 애니메이션 시스템에서는 추가적인 제약 조건들도 똑같이 중요합니다.

우리는 이것들을 직접 이산 제약 조건으로 모델링합니다.

앞서 보았듯이, 개별 자유도(DoF)는 수식 7에서 단순히 $A_i = B_i = I$로 선택함으로써 직접적으로 제약될 수 있습니다.

디리클레 경계 조건은 그러면 제약 집합을 원하는 목표 위치로 정의하여 물체를 고정하거나 상호작용 가능한 핸들을 만드는 방식으로 구현될 수 있습니다.

충돌을 암시적(implicit) 방식으로 처리하는 것은 우리의 일반적인 솔버에 자연스럽게 들어맞으며, 충돌 해결 과정에서 운동량과 내부 제약 조건의 평형을 존중할 수 있게 해줍니다.

충돌을 감지하면, 우리는 동적으로 새로운 단방향 평면 제약 조건을 추가합니다.

위치 제약 조건과 마찬가지로, 우리는 다시 수식 7에서 $A_i = B_i = I$를 선택합니다.

충돌하는 점 $q_c$에 대해, 우리는 먼저 가장 가까운 표면 점 $b$와 법선 벡터 $n$을 찾아 충돌 평면을 정의하고, 이를 통해 제약 집합 $C$가 반공간(half space) $n^T(q-b) \ge 0$으로 정의되도록 합니다.

지역(local) 단계에서 이 반공간으로의 프로젝션은 평면 프로젝션이거나 항등 변환이므로 매우 간단합니다.

충돌 제약 조건을 단방향으로 정의하면 암시적 충돌 처리에서 흔히 발생하는 달라붙는(sticking) 문제를 극복할 수 있다는 점에 주목할 필요가 있습니다.

PBD와 유사하게, 우리는 속도를 업데이트할 때 충돌하는 정점의 속도를 변경하여 마찰과 반발을 처리합니다.

간단한 감쇠 모델 또한 속도를 필터링함으로써 구현될 수 있습니다 (Müller/2007/PBD).

예를 들어 힌지 각도를 사용하는 굽힘 제약 조건(Bender/2013/Interactive Simulation)과 같은 일반적인 유형의 기하학적 제약 조건들은 우리 솔버에 쉽게 통합될 수 있습니다.

지역(local) 해결은 보조 변수에 대해 수식 7을 최소화함으로써 일반적인 방식으로 수행될 수 있습니다.

많은 기하학적 제약 조건에 대해 이 최소화를 위한 닫힌 형태의 해(closed-form solution)를 찾을 수 있습니다 (Bouaziz/2012/Interactive Editing).

만약 닫힌 형태의 해가 존재하지 않는다면, 최적화는 순차적 이차 계획법(SQP)을 사용하여 해결될 수 있습니다 (Nocedal/2006/Numerical Optimization).

섹션 4.1에서 보았듯이, $A = B = M^{1/2}$인 경우 SQP의 한 단계는 PBD 업데이트와 유사합니다 (Bender/2013/Interactive Simulation).

저희 솔버는 특정 유형의 제약 조건에 의존하지 않으며, 동일한 설정 내에서 다양한 기하학적 제약 조건을 처리할 수 있습니다. 이를 통해 단일 솔버를 사용하여 복잡한 장면을 시뮬레이션하고, 또한 객체 상호작용을 암시적 방식으로 견고하게 처리하는 것이 가능해집니다. 그림 1에서는 서로 다른 제약 조건 유형을 가진 복잡한 장면을 보여주며, 객체들이 서로 결합되어 있기도 합니다. 예를 들어, 나무와 집은 부피 변형률 제약 조건(volumetric strain constraints)으로 모델링되었고, 빨랫줄, 옷, 풀, 나뭇잎은 가장자리 변형률(edge strain) 및 굽힘 제약 조건(bending constraints)을 사용합니다.

옷과 쉘. 그림 10에서는 해적 깃발의 동작을 모델링하기 위해 단순히 가장자리 변형률 제약 조건을 사용합니다. 바람의 힘은 바람의 방향과 삼각형 법선의 함수로 추가됩니다. 바람의 힘이 너무 강하면 해적 깃발이 찢어집니다. 이는 변형률이 특정 임계값을 초과할 때 가장자리 제약 조건을 제거함으로써 구현됩니다. 작거나 중간 정도의 늘어남을 겪을 수 있는 더 복잡한 옷은 삼각형 변형률에 제한을 두는 것과 굽힘 제약 조건을 조합하여 모델링할 수 있습니다 (그림 6 참조). 변형률과 굽힘 제약 조건의 가중치를 변경함으로써 얇은 판이나 얇은 쉘과 같은 다른 유형의 재질도 시뮬레이션할 수 있습니다. 그림 9에서는 위에서 압축된 얇은 원통이 변형률과 굽힘 제약 조건 강성의 다른 비율로 인해 다른 주파수의 좌굴 패턴을 보이는 예를 볼 수 있습니다.

고체 및 예제 기반 시뮬레이션. 저희는 사면체 메시에 적용된 변형률 및 부피 제약 조건의 조합을 사용하여 고체를 시뮬레이션합니다. 그림 7에서 볼 수 있듯이, 이러한 제약 조건을 결합하는 가중치를 변경함으로써 다른 유형의 재질을 모델링할 수 있습니다. 임의의 비선형 재질을 모델링할 수는 없지만, 약한 변형률 제약 조건과 더 강한 변형률 제한 제약 조건을 결합하여 일부 비선형 동작을 근사할 수 있습니다. 그러면 재질은 작은 변형에 대해서는 부드럽지만, 변형이 변형률 한계에 도달하고 두 번째 제약 조건이 활성화되면 더 단단해집니다 (첨부 비디오 참조) – 이는 비선형 재질 모델에서 흔히 모델링되는 동작입니다. 서로 다른 이차 포텐셜을 결합하는 것은 이전에 Harmon et al. 2009에서 충돌 처리에 사용되었지만, 비선형 재질 동작을 모델링하기 위한 저희 프레임워크에도 매우 잘 맞습니다.

부피 메시의 예제 기반 시뮬레이션도 저희 공식화에서 가능합니다. 이는 물리 시뮬레이션에 대한 예술적 제어를 가능하게 합니다. 그림 8에서는 세 대의 자동차가 충돌 후 입력 예제를 따라 만화처럼 변형됩니다. Martin et al. 2011과 유사하게, 자동차 표면은 부피 메시에 내장된 후 저희 솔버를 사용하여 변형됩니다.

저희 접근법의 한 가지 중요한 장점은 수치적 안정성입니다. 그림 10에서는 극한의 힘 아래에서도 저희 솔버가 견고함을 유지하는 것을 보여줍니다. 유사하게, 저희 방법은 메시 요소가 퇴화되는 상황에서도 신뢰성을 유지합니다. 이는 두 평면 사이에 압축된 공들을 시뮬레이션하는 동안 볼 수 있습니다 (첨부 비디오 참조). 저희 접근법의 유일한 요구 사항은 원본 매니폴드의 그래디언트 및 라플라스-벨트라미 연산자의 이산화를 계산하기 위해 입력 모델의 메시 요소가 잘 정의되어 있어야 한다는 것입니다.

저희는 알고리즘 1에 최적화 절차를 설명함으로써 저희 접근법의 단순성을 보여줍니다. 7번 줄을 제거하고 5번 줄에서 $p_i$를 $q_{n+1}$로 변경함으로써, 저희는 원본 PBD 알고리즘(Müller et al. 2007)의 구조를 완전히 복원할 수 있습니다. 더욱이, 새로운 제약 조건을 도입하는 것은 로컬 솔브에서 사용되는 제약 조건 투영(알려진 경우 정확한 것, 그렇지 않은 경우 Müller et al. 2007에 주어진 일반적인 근사 투영 방식)과 적절한 이차 거리 측정 기준(행렬 $A_i$ 및 $B_i$)의 정의만 필요하다는 점에 주목하십시오.

뉴턴 방법과의 비교. 그림 12에서는 Chao et al. 2010과 유사하게 $M = SO(3)$에 대해 식 15의 이산화를 풀 때 저희의 로컬/글로벌 솔버의 성능을 뉴턴 방법과 비교합니다. 그림 12에서 볼 수 있듯이, 로컬/글로벌 접근법은 반복 횟수 측면에서 더 느리게 수렴합니다. 이는 뉴턴 방법이 이차 수렴을 보이는 반면 로컬/글로벌 솔버(블록 좌표 하강법)는 선형 수렴을 가지기 때문에 완벽하게 논리적입니다. 그러나 계산 시간 측면에서 수렴을 살펴보면, 저희 접근법이 대화형 애플리케이션에서 뉴턴 방법보다 빠르다는 것을 알 수 있습니다. 1번의 뉴턴 반복에 대해 대략 30번의 로컬/글로벌 반복을 수행할 수 있습니다. 이는 각 뉴턴 반복에서 헤시안을 재계산해야 하고 따라서 새로운 선형 시스템을 풀어야 하기 때문입니다.

더욱이, 그림 11과 첨부 비디오에서 우리는 대략 10번의 반복으로 시뮬레이션이 뉴턴 방법을 사용하여 수렴된 것과 시각적으로 유사해 보이며, 이는 저희 방식이 높은 정확도가 주된 초점이 아닌 실시간 애플리케이션에 더 나은 선택이 되게 합니다. 이러한 유형의 동작은 이전에 지오메트리 처리 및 시뮬레이션에 사용된 일부 로컬/글로벌 솔버에서 이미 관찰되었습니다 (Myles and Zorin 2012; Liu et al. 2013). 5절에서 제시된 연속 에너지에 대해 뉴턴 방법을 구현하는 것은 SVD를 미분해야 하고(McAdams et al. 2011) 각 시간 단계마다 새로운 헤시안 행렬을 계산해야 하므로 사소하지 않다는 점에 유의하십시오. 또한, 헤시안 행렬이 부정부호가 될 수 있으므로 최적화에 일부 안전장치를 통합해야 하며 오버슈팅을 피하기 위해 라인 서치 절차도 필요합니다.

Position Based Dynamics와의 비교. 저희는 또한 PBD와 저희 접근법을 가장자리 변형률 제약 조건을 사용하여 비교했습니다. 4절에서 설명했듯이, PBD는 운동량 제약 조건을 포함하지 않아 재질 강성이 반복 횟수에 의존하게 만듭니다. 이는 첨부 비디오와 그림 4에서 볼 수 있으며, 다른 반복 횟수에 대해 PBD로 시뮬레이션된 재질의 강성이 급격하게 변합니다. 저희 접근법에서는 그렇지 않으며, 재질 강성이 반복 횟수에 훨씬 덜 의존적입니다.

메싱 독립성. 5절에서는 연속 에너지에서 파생된 새로운 제약 조건 세트를 제시했습니다. 그림 5에서 볼 수 있듯이, 이러한 새로운 제약 조건은 저희 솔버가 동일한 기본 표면의 다른 조각별 단순 근사 하에서도 변형 동작을 유지할 수 있게 합니다. 이는 개발 중에 메시 해상도가 자주 변경될 수 있고 성능 향상을 위해 기하학적 상세 수준(LOD)이 널리 사용되는 컴퓨터 그래픽스 애플리케이션 및 대화형 환경에서 중요한 속성입니다. PBD 접근법의 수렴성 부족은 기본 메싱과 반복 횟수에 대한 재질 동작의 의존성 때문에 기하학적 상세 수준을 적절하게 처리하기 어렵게 만듭니다 (Häggström 2009).

우리의 솔버는 특정 유형의 제약에 의존하지 않으며, 동일한 설정 내에서 다양한 기하학적 제약을 처리할 수 있어 단일 솔버를 사용하여 복잡한 장면을 시뮬레이션하고 객체 상호작용 또한 암시적 방식으로 견고하게 처리하는 것을 가능하게 합니다. 그림 1에서는 서로 다른 제약 유형을 가진 복잡한 장면을 보여주며, 객체들이 서로 결합되어 있기도 합니다. 예를 들어, 나무와 집은 부피 변형률 제약으로 모델링된 반면, 빨랫줄, 옷, 풀, 그리고 나뭇잎들은 엣지 변형률 및 굽힘 제약을 사용합니다.

그림 10에서는 해적 깃발의 거동을 모델링하기 위해 단순히 엣지 변형률 제약을 사용합니다. 바람의 힘은 바람의 방향과 삼각형 법선의 함수로 추가됩니다. 바람의 힘이 너무 강하면 해적 깃발이 찢어집니다. 이는 변형률이 특정 임계값을 초과할 때 엣지 제약을 제거함으로써 구현됩니다. 작거나 중간 정도의 늘어남을 겪을 수 있는 더 복잡한 옷은 굽힘 제약과 결합된 삼각형 변형률에 대한 한계를 사용하여 모델링할 수도 있습니다(그림 6 참조). 변형률 및 굽힘 제약의 가중치를 변경함으로써 얇은 판이나 얇은 쉘과 같은 다른 유형의 재료도 시뮬레이션할 수 있습니다. 그림 9에서는 위에서부터 압축되어 변형률과 굽힘 제약 강성의 다른 비율로 인해 다른 좌굴 패턴을 보이는 얇은 원통의 예를 볼 수 있습니다.

우리는 사면체 메쉬에 적용된 변형률 및 부피 제약의 조합을 사용하여 고체를 시뮬레이션합니다. 그림 7에서 볼 수 있듯이, 이러한 제약들을 결합하는 가중치를 변경함으로써 다른 유형의 재료를 모델링할 수 있습니다. 임의의 비선형 재료를 모델링할 수는 없지만, 약한 변형률 제약과 더 강한 변형률 제한 제약을 결합하여 일부 비선형 거동을 근사할 수 있습니다. 그러면 재료는 작은 변형에 대해서는 부드럽다가 변형이 변형률 한계에 도달하고 두 번째 제약이 활성화되면 더 단단해집니다. 이는 비선형 재료 모델에서 흔히 모델링되는 거동입니다(첨부 비디오 참조). 서로 다른 이차 포텐셜을 결합하는 것은 이전에 Harmon/2009/Collision Handling에서 충돌 처리를 위해 사용되었지만, 비선형 재료 거동을 모델링하기 위한 우리의 프레임워크에도 매우 잘 맞습니다.

부피 메쉬의 예제 기반 시뮬레이션 또한 우리의 공식에서 가능합니다. 이는 물리 시뮬레이션에 대한 예술적 제어를 가능하게 합니다. 그림 8에서는 세 대의 자동차가 충돌 후 입력 예제를 따라 만화처럼 변형됩니다. Martin/2011/Example-based과 유사하게, 자동차 표면은 부피 메쉬에 내장된 후 우리의 솔버를 사용하여 변형됩니다.

Figure 12에서는 Chao et al./2010과 유사하게 $M = SO(3)$에 대한 수식 15의 이산화를 풀 때, 우리의 local/global 솔버와 뉴턴 방법의 성능을 비교합니다. Figure 12에서 볼 수 있듯이, local/global 접근법은 반복 횟수 측면에서 더 느리게 수렴합니다. 이는 뉴턴 방법이 2차 수렴을 보이는 반면, local/global 솔버(블록 좌표 하강법)는 선형 수렴을 하기 때문에 완벽하게 논리적인 결과입니다. 하지만 계산 시간 측면에서 수렴성을 살펴보면, 우리의 접근법이 인터랙티브 애플리케이션에서는 뉴턴 방법보다 더 빠르다는 것을 알 수 있습니다. 뉴턴 반복 1회에 대략 30회의 local/global 반복을 수행할 수 있습니다. 이는 각 뉴턴 반복마다 헤시안 행렬을 다시 계산해야 하고 따라서 새로운 선형 시스템을 풀어야 하기 때문입니다.

더욱이, Figure 11과 첨부된 비디오에서 약 10회의 반복만으로도 시뮬레이션이 뉴턴 방법으로 수렴시킨 결과와 시각적으로 유사해 보이는 것을 관찰할 수 있으며, 이는 높은 정확도가 주된 초점이 아닌 실시간 애플리케이션에 우리 방식이 더 나은 선택이 되게 합니다. 이러한 유형의 동작은 기하학 처리 및 시뮬레이션에 사용된 이전의 일부 local/global 솔버에서도 이미 관찰된 바 있습니다 (Myles and Zorin/2012; Liu et al./2013). 참고로, 5절에서 제시된 연속 에너지에 대해 뉴턴 방법을 구현하는 것은 간단하지 않은데, 이는 SVD를 미분해야 하고(McAdams et al./2011) 매 타임 스텝마다 새로운 헤시안 행렬을 계산해야 하기 때문입니다. 또한, 헤시안 행렬이 비정부호(indefinite)가 될 수 있으므로 최적화에 일부 안전 장치를 통합해야 하며, 오버슈팅을 피하기 위해 선형 탐색 절차도 필요합니다.

우리는 또한 우리의 접근법을 에지 스트레인 제약조건을 사용하는 PBD와 비교했습니다. 4절에서 설명했듯이, PBD는 운동량 제약조건을 포함하지 않아 재료의 강성이 반복 횟수에 의존하게 만듭니다. 이는 첨부된 비디오와 Figure 4에서 볼 수 있는데, 반복 횟수가 달라짐에 따라 PBD로 시뮬레이션된 재료의 강성이 급격하게 변합니다. 우리의 접근법에서는 그렇지 않은데, 재료의 강성이 반복 횟수에 훨씬 덜 의존적입니다.

5절에서는 연속 에너지로부터 파생된 새로운 제약조건 세트를 제시했습니다. Figure 5에서 볼 수 있듯이, 이 새로운 제약조건들은 우리 솔버가 동일한 기저 표면의 서로 다른 조각별 단체 근사(piecewise simplicial approximations) 하에서도 변형 동작을 유지할 수 있게 해줍니다. 이는 개발 중에 메쉬 해상도가 자주 변경될 수 있고 성능 향상을 위해 기하학적 상세 수준(LOD)이 널리 사용되는 컴퓨터 그래픽스 애플리케이션 및 인터랙티브 환경에서 중요한 속성입니다. PBD 접근법의 수렴성 부족은 재료의 동작이 기저 메쉬와 반복 횟수에 의존하기 때문에 기하학적 상세 수준을 적절하게 처리하기 어렵게 만듭니다 (H¨aggstr¨om/2009).

본 논문에서 제시된 전체 프레임워크는 C++로 구현되었습니다. 우리는 OpenMP를 사용하여 local step을 병렬화하고, 희소 Cholesky 분해를 사용하여 선형 시스템을 미리 인수분해한 후 x, y, z 좌표에 대해 세 번의 후방 대입을 병렬로 수행하여 global step을 풉니다. 동적 제약 조건은 선형 시스템의 랭크 업데이트 및 다운데이트를 통해 처리됩니다. 고밀도 및 희소 선형 대수 연산을 위해 Eigen 라이브러리(eigen.tuxfamily.org)를 사용합니다. 우리는 질량 행렬을 계산하기 위해 표준 단체 질량 이산화(Hughes/2000/FEM) 또는 그 집중 질량 버전을 사용하며, 눈에 띄는 차이는 없습니다.

타이밍. 중간 크기 모델(3만 개 미만의 제약 조건과 3만 개 미만의 자유도)의 시뮬레이션에는 보통 5-10회의 반복으로 충분합니다. 반복당 1-6ms의 속도로, 이는 16GB 메모리를 장착한 MacBook Pro 2.7 GHz Intel Quad-core i7에서 실시간 시뮬레이션을 가능하게 합니다. 타이밍과 메시에 대한 통계는 첨부된 비디오에서 확인할 수 있습니다. 또한, 첨부된 애플리케이션은 여러 예제에서 성능을 보여줍니다.

우리의 암시적 오일러 솔버는 효율적이고 강건하지만, 내재적 감쇠를 보입니다.

가까운 미래에 우리는 더 나은 에너지 보존 특성을 제공하는 심플렉틱 적분기(Kharevych/2006/Symplectic Integrators)로 우리의 접근 방식을 확장할 계획입니다.

감쇠는 최적화가 조기에 종료될 때도 관찰될 수 있습니다.

이는 최적화가 충분한 반복 횟수 동안 실행되지 않으면 외부 힘이 메시 전체에 완전히 전파되지 못할 수 있기 때문입니다.

이 효과는 수렴에 더 많은 반복이 필요한 대규모 메시에서 두드러집니다.

향후 연구 과제로, 우리는 코드의 GPU 버전을 구현하여 솔버의 속도를 개선하고 위상학적 측면에 집중하고자 합니다.

Fig 1: 본 논문에서는 단일 물리 시뮬레이션 프레임워크 내에서 매우 다양한 기하학적 제약 조건을 지원하는 새로운 “투영 기반” 암시적 오일러 적분기를 제안합니다. 이 예시에서는 건물, 잔디, 나무, 옷을 포함한 모든 요소(자유도 49k, 제약 조건 43k)가 프레임당 10회의 반복을 사용하여 반복당 3.1ms의 속도로 시뮬레이션됩니다(함께 제공되는 비디오 참조).

Fig 2: 함수 Ψ(E(·))는 제약 매니폴드 E(·) = 0을 영 레벨 집합으로 정의함과 동시에 등위선으로 주어지는 탄성 포텐셜도 정의합니다. 매니폴드에 투영 변수 p를 도입함으로써, 거리 함수 d(q, p)로 모델링된 탄성 포텐셜로부터 매니폴드 정의를 분리할 수 있습니다.

Fig 3: 가우스-자이델 대 자코비. PBD에서 사용되는 가우스-자이델 알고리즘은 현재 추정치를 각 제약 집합(이 경우 Ci와 Cj)에 순차적으로 투영합니다. 만약 실행 가능한 해가 없다면, 즉 제약 집합들이 겹치지 않는다면, 가우스-자이델 알고리즘은 서로 다른 제약 조건들 사이에서 진동할 것입니다(두 개의 빨간 점 사이). 반대로, 자코비 알고리즘은 현재 추정치를 각 제약 집합에 병렬적으로 투영하고(초록색 점들) 두 번째 단계에서 합의에 도달합니다. 이는 자코비 알고리즘이 수렴(빨간 점)할 수 있게 합니다.

Fig 4: 19683개의 자유도와 19360개의 엣지 제약 조건을 가진 천 조각에 대해, PBD는 타임 스텝에 허용된 시간에 따라 다른 재질 강성을 보입니다(상단). 추가적인 운동량 항과 미분 좌표 공식 덕분에, 저희 시뮬레이션은 반복 횟수가 달라도 일관되게 동작합니다(하단).

Fig 5: 주어진 연속 표면에 대해, 저희의 연속체 기반 제약 조건을 해상도가 다른 조각별 단체 근사(piecewise simplicial approximation)에 이산화하면 매우 유사한 정성적 동작을 보입니다.

Fig 6: 동일한 메시에서 시작하여, 변형률 제한(strain limiting)을 통해 작거나 중간 정도의 늘어남을 겪을 수 있는 재질을 시뮬레이션할 수 있습니다. 왼쪽에서 오른쪽으로, [-10%, +10%], [-20%, +20%], [-30%, +30%]의 변형률 한계를 사용합니다. 한계가 증가함에 따라 천이 어떻게 늘어나고 주름이 어떻게 흡수되는지 주목하십시오.

Fig 7: 부피 보존과 변형률 제약 조건의 가중치 조합을 다양하게 하여 부피가 있는 객체에 대해 다양한 유형의 재질을 시뮬레이션할 수 있습니다.

Fig 8: 예제 기반 제약 조건을 사용하여 시뮬레이션에 변형 예제(상단)를 추가하면 복잡하고 예술적인 재질의 시뮬레이션이 가능합니다. 이 장면에서는 세 대의 자동차가 충돌하고 주어진 예제(하단)에 따라 만화처럼 반응합니다.

Fig 9: 왼쪽에서 오른쪽으로 갈수록 굽힘 가중치를 증가시키며 얇은 셸 실린더를 시뮬레이션합니다. 실린더가 압축될 때, 다양한 주파수의 좌굴 패턴이 나타납니다.

Fig 9: 부록에서 볼 수 있듯이, 이 굽힘 제약 조건은 변형된 구성의 평균 곡률 벡터의 단순한 정규화로 구현될 수 있으므로 매우 효율적인 로컬 풀이가 가능합니다.

Fig 10: 극심한 바람의 힘에도 저희의 투영 암시적 솔버는 안정적으로 유지됩니다. 솔버는 각 반복에서 에너지를 약하게 감소시켜 어떠한 안전장치도 불필요하게 만듭니다(상단). 해적 깃발은 제약 조건의 동적 업데이트를 사용하여 실시간으로 바람에 찢어집니다(하단).

Fig 11: 7161개의 자유도와 8406개의 변형률 제약 조건을 가진 이 부피 하마는 저희의 로컬/글로벌 솔버를 사용하여 1, 10, 20회 반복으로 시뮬레이션됩니다. 흥미롭게도, 10회 반복만으로도 저희 접근법은 뉴턴법으로 계산된 수렴 해와 매우 유사해 보이며, 계산 비용은 훨씬 적습니다.

Fig 12: 반복 횟수에 대한 상대 오차 감소를 비교해 보면, 뉴턴법이 저희의 로컬/글로벌 접근법보다 더 빠르게 수렴하는 것을 관찰할 수 있습니다. 그러나 이는 각 반복의 비용을 반영하지 않는데, 각 뉴턴 반복마다 변화하는 선형 시스템을 풀어야 하기 때문입니다. 계산 시간에 대한 상대 오차 감소를 보면, 저희의 로컬/글로벌 접근법은 10의 -10승의 상대 오차까지 더 나은 성능을 보여 상호작용 애플리케이션에 특히 매력적입니다. 이 곡선에서 상대 오차는 최적 해에 대한 정규화된 오차(ϵ(qi) −ϵ(q∗))/(ϵ(q0) −ϵ(q∗))로 정의되며, 4290개의 자유도와 4099개의 사면체 변형률 제약 조건을 가진 비틀림 막대 예제(왼쪽)에 대해 측정되었습니다.