* 개요
- Constraints는 joints, contact, and collision을 재현하기 위해 사용된다.
- 우리는 박스들을 쌓고, ragdoll limbs가 붙어있도록 하기 위해 contraints를 풀어야 한다.
- Constraint solvers는 impulse or forces를 계산하고, 그것들은 constrained bodies에 적용 하여 이것을 한다.
* 개관
- Constraint Formulas
- Deriving Constraints : Joints, Motors, Contact
- Building a Constraint Solver
* Constraint Types
- Contact and Friction
- Ragdolls
- Particles and Cloth
* Motivation
- Bead on a Rigid Wire (2D)
- Implicit Function C(x) = 0
- This is a constraint equation!
* Velocity
- The normal vector is perpendicular to the curve
- So this dot product is zero:
* Velocity Constraint
- Position Constraint : C(x) = 0
- 만약 C가 zero라면, 그러면 그것의 시간에 대한 미분은 0이여야 한다.
- Velocity Constraint :
- Velocity constraints는 허용되는 motion을 정의한다.
- Velocity constraints는 impulses를 적용하여 만족될 수 있다.
- 이후에 더 다룬다.
* The Jacobian
- 연쇄법칙에 의해, velocity constraint는 특별한 구조를 갖는다:
- J는 jacobian이다.
- 그 Jacobian은 velocity에 수직이다
* The Velocity Map
- V(Cartesian Space Velocity) -> J -> dot(C) (Constraint Space Velocity)
* Constraint Force
- Assume the wire is frictionless
- What is the force between the wire and the bead
* Lagrange Multiplier
- 직관적으로 그 constraint force F_c는 normal vector와 평행하다.
- 방향과 크기가 알려져 있다는 것은 다음을 암시한다
- Lambda는 constraint force의 signed magnitude이다.
- 우리는 lambda를 어떻게 계산하는가?
- 그것이 solver의 일이다.
- Solvers는 나중에 이야기 된다.
* The Force Map
- ƛ(Constraint Space Force) -> J^T -> F_c (Cartesian Space Force)
* Work, Energy, and Power
- Work = Force * Distance
- Work는 단위 에너지를 갖는다 (Joules)
- Power = Force * Velocity (Watts)
* Principle of Virtual Work
- Constraint forces는 do not work이다. 그래서 그것들은 허용된 velocity에 수직이여야 한다.
주장 :
증명 :
- 그래서 constraint force는 에너지에 영향을 미치지 않는다.
* Constraint Quantities
- Position Constraint : C
- Velocity Constraint : dot(C)
- Jacobian : J
- Lagrange Multiplier : ƛ
* Why all the Painful Abstraction?
- 모든 종류의 constraints를 solver를 위해 하나의 공통된 형태로 만들기 위해
- 우리가 효율적으로 다른 solution 기법들을 시도할 수 있게 하기 위해
* Time Dependence
- Some constraints, like motors, have prescribed motion.
- This is represented by time dependence
Position : C(x, t) = 0
Velocity: dot(C) = Jv + b(t) = 0 ; b(t) is velocity bias
* Example : Distance Constraint
- Position : C = ||x|| - L
- Velocity : dot(C) = x^T / ||x|| * v
- Jacobian : J = x^T / ||x||
- Velocity Bias : b = 0
- ƛ is the tension
* Gory Details
* Computing the Jacobian
- 처음에, Jacobian을 계산하는 것은 쉽지 않다.
- constraint equation을 처음에 갖는 것은 도움이 된다.
- 그것은 연습으로 더 쉬워진다
- 벡터의 관점에서 생각해보려고 해라.
* A Recipe for J
- C를 작성하기 위해 기하학을 사용해라
- 시간에 대해 C를 미분해라
- v를 고립시켜라(isolate).
- 검사해서 J를 확인해라 (그리고 b도)
- 편미분을 연산하지 말아라!
* Homework
- Angle Constraint : C = a1^Ta2 - cosθ
- Point Constraint : C = p2 - p1
- Line Constraint : C = (p2 - p1)^T * a1 = 0
* Newton's Law
- 우리는 적용된 forces와 constraint forces를 나눈다.
* Types of Forces
- 적용된 forces는 어떤 법칙에 따라 연산된다: F=mg, F=kx 등등
- Constraints는 kinematic (motion) conditions을 부과한다.
- Constraint forces는 implicit하다.
- 우리는 constraint forces에 대해 solve해야 한다.
* Constraint Potpourri(여러가지를 섞은 것)
- Joints
- Motors
- Contact
- Restitution
- Friction
* Joint : Distance Constraint
* Motors
- A motor는 limited force (torque)를 가진 constraint이다.
C = θ - sint (-10 <= ƛ <= 10)
바퀴
* Velocity Only Motors
- Example
- 사용법 : 일정한 비율로 spin 하는 한 바퀴. 우리는 각을 신경쓰지 않는다.
* Inequality Constraints
- 이제까지, 우리는 equality constraints 를 보았다 (왜냐하면 그것들이 간단하기 때문에)
- Inequality constraints (부등식 제약)은 contact, joint limits, rope 등을 위해 필요하다.
- What is the velocity constraint?
만약
enforce:
아니라면
constraint를 skip해라.
- Force Limits :
- Inequality constraints don't suck
* Contact Constraint
- Non-penetration
- Restitution : bounce
- Friction : sliding, sticking, and rolling
* Non-Penetration Constraint
-
J v
(이 행렬에 ^T 해야함 모르고 빼먹음)
- Handy Identities
* Restitution
- Relative Normal Velocity
- Velocity Reflection
- bounce를 velocity bias로 더하기
* Friction Constraint
- Friction은 velocity-only motor와 같다.
- target velocity는 zero이다.
J v
- friction force는 normal force에 의해 제한된다
- Coulomb's Law :
- Or :
- Where :
* What is a Solver?
- 모든 forces를 모으고, velocity와 position을 integrate한다.
- 새로운 상태(state)가 제약을 만족하도록 하기 위해 constraint forces를 적용
- constraint forces가 implicit이기 때문에, 그 constraint forces에 대해 solve해야만 한다.
* Solver Types
- Global Solvers (slow)
- Iterative Solvers (fast)
* Solving A Chain
- Global :
solve for ƛ1, ƛ2, ƛ3 simultaneously.
- Iterative:
while !done
solve for ƛ1
solve for ƛ2
solve for ƛ3
* Sequential Impulses (SI)
- An iterative solver
- SI는 velocity errors를 고치기 위해 각 constraint에 impulses를 적용
- Si는 빠르고 안정적이다 (보통).
- global solution에 수렴한다 (결국에)
* Why Impulses?
- friction과 collision을 다루기에 더 쉽다.
- Velocity는 가속도보다 더 직관적이다.
- time step을 고려한다면, impulse와 force는 상호교환가능하다.
* Sequential Impulses
- Step1 : applied forces를 Integrate하고, 새로운 velocities를 만듬.
- Step2 : velocity errors를 고치기 위해 모든 constraints에 대해 순차적으로 impulses 적용
- Step3 : positions를 업데이트하기 위해 그 새로운 velocities를 사용.
* Step1 : Integrate Applied Forces
- Euler's Method
- 이 새로운 velocity는 velocity constraints를 위반하는(violate) 경향이 있다.
* Step2 : Apply Corrective Impulses
- 각 constraint에 대해 다음을 solve:
Newton :
Virtual Work :
Velocity Constraint :
* Step 2 : Impulse Solution
- scalar m_c는 constraint impulse에 의해 seen되는 effective mass이다.
* Step2 : Velocity Update
- lambda에 대해서 풀었으니, 우리는 velocity를 업데이트 하기 위해 그것을 사용할 수 있다.
* Step2 : Iteration
- 해결될 때 까지 모든 constraints에 대해 Loop
- 고정된 수의 iterations
- Corrective impulses become small
- Velocity Errors become small
* Step3 : Integrate Positions
- Use the new velocity:
- 이것은 Symplectic Euler integrator이다.
* Extensions to Step 2
- Handle position drift
- Handle force limits
- Handle inequality constraints
* Handling Position Drift
- Velocity constraints는 정확히 obeyed되지 않는다.
- Joints는 떨어질 것이다.
* Baumgarte Stabilization
- position error를 velocity constraint에 다시 feed
- New velocity constraint
- Bias factor :
- What is the solution to :
- ??? ODE... First-order differential equation
- Answer
* Tuning the Bias Factor
- 만약 너의 시뮬레이션이 불안정성을 가진다면, bias factor를 zero로 설정하고, 안정성을 체크해라.
- simulation이 불안정해질 때 까지 느리게 bias factor를 증가시켜라
- 그 값의 절반을 사용해라.
* Handling Force Limits
- 처음에 force limits을 impulse limits으로 바꾸어라.
* Handling Impulse Limits
- corrective impulses를 clamping :
- 그것이 정말 이렇게 간단한가? 아니다.
* How to Clamp
- Each iteration은 corrective impulses를 연산한다.
- corrective impulses를 Clamping하는 것은 틀린 것이다!
- 너는 time step에 걸쳐 적용된 total impulse를 clamp해야만 한다.
- 그 다음의 예제는 왜 그런지 보여준다.
* Example : Inelastic Collision
- A Falling Box
- Global Solution
* iterative Solution
- Suppose the corrective impulses are too strong.
- What should the second iteration look like?
- To keep the box from bouncing, we need downward corrective impulses.
- In other words, the corrective impulses are negative!
- But clamping the negative corrective impulses wipes them out:
- 이것은 너의 시뮬레이션에 jitter를 도입하는 좋은 방법이다.
* Accumulated Impulses
- 각 constraint에 대해, 적용된 total impulse를 추적해라.
- 이것이 accumulated impulse이다.
- 그 accumulated impulse를 Clamp해라.
- 이것은 accumulated impulse가 여전히 positive일 때, corrective impulse가 negative(음수)가 되는 것을 허용한다.
* New Clamping Procedure
- Step A : Compute the corrective impulse, but don'y apply it.
- Step B : Add the corrective impulse to the accumulated impulse.
- Step C : Clamp the accumulated impulse.
- Step D : Compute the change in the accumulated impulse.
- Step E : Apply the impulse found in Step D.
* Handling Inequality Constraints
- Before iterations, determine if the inequality constraint is active.
- If it is inactive, then ignore it.
- Clamp accumulated impulses:
* Inequality Constraints
- A problem : active -> overshoot -> inactive -> gravity -> active
- Jitter is not nice!
* Preventing Overshoot
- Allot a little bit of penetration (slop).
if separation < slop factor
else
- Note : the slop factor will be negative (separation).
* Other Important Topics
- Warm Starting
- Split Impulses
* Warm Starting
- Iterative solvers use an initial guess for the lambdas.
- So save the lambdas from the previous time step.
- Use the stored lambdas as the initial guess for the new step.
- Benefit : Improved Stacking
* Step 1.5
- Apply the stored lambdas.
- Use the stored lambdas to initialize the accumulated impulses.
* Step 2.5
- Store the accumulated impulses
* Split Impulses
- Baumgarte stabilization affects momentum
- This is bad, bad, bad!
- Unwanted bounces
- Spongy contact
- Jet propulsion
- use different velocity vectors and impulses
Real : v ƛ
Pseudo : v_pseudo ƛ_pseudo
- Two parallel solvers
- The real velocity only sees pure velocity constraints
- The pseudo velocity sees position feedback (Baumgarte)
- The Jacobians are the same
* Pseudo Velocity
- The pseudo velocity is initialized to zero each time step.
- The pseudo accumulated impulses don't use warm starting (open issue)
* Step 3 (revised) : Integrate Positions
- Use the combined velocity :
======================================
더 이해해야 할 것들
- Constraint에 대한 이해, 체화
- Inequality Constraint
- How to Compute the Jacobians (Constraint를 만들고 거기에 대한 jacobians을 계산하는 것, 좀 더 예시가 필요하다)
- Handling Position Drift - Baumgarte Stabilization
======================================
Contact Manifolds
* Executive Summary
- Constraint solvers는 penetration을 방지하기 위해 contact points가 필요하다.
- 우리는 contact manifold를 한 번에 연산하기 위해 SAT를 사용할 수 있다.
- 우리는 point-by-point(점 마다) contact manifold를 구성하기 위해 GJK를 사용할 수 있다.
* Contact
- Contact는 두 개의 shapes가 닿을 때 발생한다.
- 우리는 penetration을 방지하고 friction을 재현하기 위해 contact를 모델링한다.
- contact를 모델링하는 것은 기하학과 많은 수완을 요구한다.
* Contact Manifolds
- convex polyhedra에 대해, contact manifold는 이상적으로 a single point, a line segment, or a convex polygon 이다.
- 일반적인 convex 3D shapes에 대해, contact manifold는 convex 2D shape 이다.
- 내가 overlap을 언급했었나?
* Overlap Happens
- What we want.
- What we get.
* Approximate Manifolds
- 우리는 contact manifold를 근사하기 위해 contact points의 모음을 사용한다.
- 우리의 목적은 빠르고, 안정되고, 그럴듯한 시뮬레이션이다.
- 이 의미에서, 좋은 manifolds를 연산하는 것은 art이다.
* Contact Points
- Position
- Normal
- Penetration
- Contact ID
* Example Manifold
- Two points and a common nomral
* Contact Manifold Quality
- 오브젝트들이 상당히 크게 관통할 때, 그 contact manifold는 fuzzy(애매)하다.
- Contact solvers는 coherence(일관성)을 좋아한다.
- 단계마다 일관성있게 하자.
* Exterme Fuzziness
- manifold 1
- manifold 2
* Using the SAT
- convex polyhedra (boxes, triangles, 등)에 대해 주로 유용하다.
- minimum penetration의 축을 찾아라.
- edge-edge contact에 대해, midpoint를 찾아라.
- face contact에 대해, Sutherland-Hodgeman clipping을 사용해라.
* Example: 2D Box-Box SAT
- 처음에 minimum penetration을 가진 separating axis를 찾아라.
- 2D 에서, separating axis는 face normal이다.
* Box-Box Clipping Setup
- reference face를 확인하고
- incident face를 확인해라.
* Box-Box Clipping
- reference face의 side planes에 대해 (reference face가 아닌) incident face를 clip해라
- 양수의(positive) penetration를 가진 clip points를 고려해라.
* Feature Flip-Flop
- 어떤 normal이 min separating axis인가?
- 다른 것에 대해 한 축을 선호하는 가중치를 적용해라
- 개선된 일관성을 준다.
* Coherence
- 그 step의 초기에 old force/impulse solution을 적용해라.
- 더 적은 반복으로 더 훌륭한 안정성을 준다.
- 우리는 old and new contact를 매치할 방법이 필요하다.
* Feature-Based Contact Points
- 각 contact point는 clipping의 결과이다.
- 그것은 두 개의 다른 edges의 결합이다.
- 한 edge는 둘 중 하나의 box로부터 올지도 모른다.
- 그 두 개의 edge numbers를 각 contact point와 저장해라 - 이것이 contact ID이다.
* Contact Point IDs
* GJK Contact Points
- 세 가지 경우 :
No Contact
Shallow Contact
Deep Contact
* GJK Shallow Contact
- support points는 contact를 탐지하기 위해 작은 margin으로 scaled up된다.
- 가장 가까운 점을 연산해라 (no margin).
- 이것은 position과 normal를 준다.
- penetration은 margin - 실제 거리 이다.
* GJK Contact Margins
* GJK Contact Point
* GJK Deep Contact
- 어떤 다른 알고리즘을 사용해라
- 그것은 GJK보다 더 느릴 것이지만, 그것은 오래 지속되지 않을 것이다.
- SAT, EPA, brute force.
- EPA를 배우기 위해 Gino의 북을 읽어라.
* GJK Manifolds
- GJK는 한 번에 한 개의 contact point만을 준다.
- 우리는 각 contact point를 유지하고 귀중히 여긴다.
- 몇 가지 time steps에 걸쳐 한 manifold를 구성해라.
- 이것은 자동적으로 coherence를 제공한다.
* Building the Manifold
* Manifold Persistence
- 각 body에 있는 points를 추적
- 만약 그 points가 너무 멀리 떨어져 움직인다면, 그것들을 해제
- 이것은 sliding에 나쁘다.
- Contact ID들을 사용?
* Adding New Points
- manifold마다 점들의 한 최소 집합을 유지 (예를들어, 4 개의 points)
- 오래된 점들과 가장 가까운 새로운 점들은 Reject
* Manifold Reduction
- 이것은 one-shot과 incremental manifolds에 적용된다.
- 우리는 안정된 재현을 위해 최소한의 수의 contact points를 유지하길 원한다.
- 이것은 성능을 급격히 개선한다.
댓글 없음:
댓글 쓰기