Post Lists

2019년 3월 13일 수요일

GDC 2010 Erin Catto - Computing Distance (GJK Algorithm)

Computing Distance

* Convex polygons
- 우리가 한 쌍의 convex polygons(볼록 다각형)을 가지고 있다고 가정하자.

* Closest points
- 우리는 가장 가까운 점을 어떻게 연산하는가?
- 가장 가까운 점을 아는 것은 우리에게 거리를 준다.

* Overlap
- 우리는 overlap을 어떻게 탐지하는가?
- 이 경우에 그 거리는 0이다.

* Goal
- convex polygons 사이의 distance를 연산하자
- 이 발표의 목표는 convex polygons 사이의 거리를 연산하는 한 알고리즘을 설명하는 것이다.

* Keep in mind
- 2D이다.
- 최적화되지 않은 코드이다.
- 나는 이 발표에서 오직 2D만을 다룰 것이다. 그러나 대부분의 개념들은 3D로 확장된다.
- 너는 최적화되지 않은 알고리즘들과 코드를 볼지도 모른다. 이것은 좋은 신호인데, 너가 그 재료들을 이해한다는 의미이다.

* Approach
- 이 발표에서 bottom-up 접근법을 사용할 것이다.
- 나는 간단한 솔루션을 가진 간단한 문제로 시작할 것이고, 그러고나서 좀 더 복잡한 문제들과 솔루션 쪽으로 이동할 것이다.
- 각 level은 이전의 levels로부터 구성된다.

* Geometry
- 나는 그 알고리즘들을 위해 너의 geometric intuition(기하학적 직관)을 구성하려고 할 것이다.
- 결국, 우리는 한 기하학적 문제를 해결하려고 할 것이다.
- 추가 보너스로, 너는 많은 좋은 파스텔 컬러들을 보게 될 것이다.

* If all else fails ...
- 발표를 보충하기 위해, 나는 소스코드가 있는 알고리즘의 데모를 만들었다.
- 나는 나중에 링크를 올릴 것이다.

* Outline
1. Point to line segment
2. Point to triangle
3. Point to convex polygon
4. Convex polygon to convex polygon
- 이 발표의 나머지의 개요이다.
- 각 주제는 이전의 것으로부터 구성되고, 연산의 대부분은 재활용 될 것이다. 

* Concepts
1. Voronoi regions
2. Barycentric coordinates
3. GJK distance algorithm
4. Minkowski Difference
- 그 과정에서, 나는 몇 가지 중요한 개념들을 소개할 것이다.
- 그 첫 번째 개념은 Voronoi regions인데, 이것은 우리가 그 평면을 가장 가까운 feature regions으로 분할하게 해준다.
- 그 두 번째 개념은 barycentric coordinates이고, 이것은 점들의 가중치 합을 기반으로 오브젝트 기반의 좌표 체계를 제공한다.
- 세 번째 개념은 GJK 알고리즘이고, 점과 convex polygon problem에 대해 반복적으로 sovle하기 위해 사용할 것이다.
- 그 네 번째 개념은 Minkowski difference인데, polygon to polygon의 문제를 point to polygon으로 바꾸게 해준다.

* Section 1 : Point to Line Segment
- point to line segment를 다루는 첫 번째 주제로 시작해보자.

* A line segment
- 우리가 정점 A와 B를 가진 선분을 가지고 있다고 하자.

* Query point
- 이제 우리가 query point Q를 가지고 있다고 하자.

* Closest Point
- 우리는 선분 위에 있는 가장 가까운 점 P를 찾길 원한다.

* Proejction : region A
- 우리는 Q를 A와 B를 지나는 직선에 사영하여 가장 가까운 점을 찾을 수 있다.
- Q가 그 직선에 사영될 수 있는 3 개의 영역이 있다.
- 이 슬라이드에서, Q는 side A의 선분 바깥으로 사영된다.

*  Projection : region AB
- 이 슬라이드에서, Q는 그 선분 안으로 사영된다.

* Projection : region B
- 마지막으로, 이 경우에 Q는 side B에 선분 밖으로 상여된다.
- 그래서 그것은 3 개의 경우들을 보여준다.

* Voronoi regions
- 그래서 이것은 Voronoi regions의 개념을 꺼내게 한다.
- 우리는 그 평면을 closest feature regions으로 나눌 수 있다.
- region A에 있는 모든 점들은 정점 A와 가장 가깝다.
- region B에 있는 모든 점들은 정점 B와 가장 가깝다.
- region AB에 있는 모든 점들은 AB의 내부와 가장 가깝다.
- 이러한 것들이 Voronoi regions이라고 불려진다.
- 가장 가까운 점을 연산하는 것은 Q의 Voronoi region을 결정하는 것의 문제이다.

* Barycentric coordinates
- 우리는 선분 AB를 지나는 직선에 대해 Q의 사영을 연산하기 위해 barycentric coordinates를 사용할 것이다.
- barycentric coordinates가 무엇인가?
- AB를 지나는 직선 위에 있는 어떤 점 G는 A와 B의 가중치 합으로 나타내어질 수 있다.
- 여기에서 우리는 그 가중치를 u와 v로 이름을 붙인다.
- 이러한 가중치는 합해서 1이 되어야 한다.
- 이러한 가중치들은 선분 AB와 관련하여 G의 barycentric coordinates이다.

* Fractional lengths
- 우리는 barycentric coordinates를 partial segments의 fractional lengths로 볼 수 있다.
- 이 슬라이드에서 partial segments는 균형을 이룬다. 그래서 u와 v는 0.5이다.
- 이 슬라이드에서 partial segments는 균형을 이루지 않는다. G가 A에 다가갈 때, u는 더 커지고, v는 균등하게 더 작아진다.

{
(1) u = 0.5, v = 0.5
(2) u = 0.75, v = 0.25
(3) u = 1.25, v = -0.25
A와 B가 일차원에 있는 값이라고 하자.
10과 100으로
그리고 각 케이스에 대해 G(u,v) 에 대한 값은, 즉 G의 위치는
(1) 0.5 * 10 + 100 * 0.5 = 5 + 50 = 55
(2) 0.75 * 10 + 0.25 * 100 = 7.5 + 25 = 32.5
(3) 1.25 * 10 - 0.25 * 100 = 12.5 - 25 = -12.5
}

* Unit Vector
- A에서 B로 향하는 단위 벡터 n을 정의하자.

* (u,v) from G
- 이제 우리는 G의 위치를 기반으로 (u, v)를 결정할 수 있다.
- (u, v)는 적절한 n에 대해 sub-segment를 내적하고, 그러고나서 AB의 전체 길이로 나누어서 결정된다.
- u와 v가 개별적으로 음수가 될 수 있다는 것에 주의해라.
- 또한 u와 v가 합해서 1이 된다는 것에 주의해라.
 
- 우리는 query point Q로부터 직접 (u, v)를 얻을 수 있다.
- 우리가 G 대신에 Q를 사용한다면 그 내적이 변하지 않는다는 것에 주의해라.
- 이것은 내적의 사영 특성에 의한 것이다.

* Voronoi region from (u, v)
- AB를 지나는 어떤 점 G는 A와 B의 가중치로 나타내어질 수 있다.
- 그 가중치는 합해서 1이 되어야 한다.
- 이러한 가중치는 선분 AB와 관련하여 G의 barycentric coordinates이다.

u > 0 && v > 0 : region AB
v <= 0 : region A
u <= 0 : region B

* Closest Point Algorithm
- 이제 우리는 우리의 closest point algorithm을 쓸 수 있다.
- 우리는 line segment AB와 query point Q가 주어진다.
- 처음에 우리는 barycentric coordinates를 계산한다.
- 그것으로 부터, 우리는 Voronoi region을 결정하고, 가장 가까운 점 P를 결정한다.
input : A, B, Q
compute u and v

if (u <= 0)
   P = B
else if( v <= 0)
   P = A
else
   P = u * A + v * B

* Section 2 : Point to Triangle
- 우리는 상세히 point to line segment를 다루었다.
- 이제 우리가 좀 더 어려운 문제로 이동하도록 하자 : point to triangle.

* Triangle
- 여기에 2D의 삼각형이 있다.
- 선분들 처럼, 우리는 주어진 query point에 대해 Voronoi regions을 확인할 수 있다.

* Closest feature : vertex
- 여기에서 closest feature는 vertex B이다.

* Closeset feature : edge
- 여기에서 closest feature는 edge BC이다.

* Closest feature : interior
- 이 경우에, closest feature는 triangle's interior이다.

* Voronoi regions
- 그 평면을 다시 Voronoi regions으로 나누자.
- 이러한 것들이 closest feature regions이라는 것을 기억해라.
- 예를들어, region AB에 있는 한 점은 edge AB의 내부와 가장 가깝다.
- dashed lines이 인접한 edges와 수직이라는 것을 주목해라.
- 우리는 3개의 vertex regions, 3개의 edge regions, 그리고 1개의 내부 region을 갖는다.

* 3 line segments
- 우리는 그 삼각형의 3개의 edges를 3개의 line segments로 다룰 수 있다.
- 우리는 각 선분과 관련하여 Q의 uv들을 결정할 수 있다.
- 우리는 우리가 triangle의 Voronoi regions을 결정하는 것을 돕기 위해 line segment barycentric coordinates를 결합할 수 있다.

* Vertex regions
- 선분 uv들을 결합하여, 우리는 Q가 vertex region에 있는지를 결정할 수 있다.
- 예를들어, region A는 선분 CA의 u와 선분 AB의 v로부터 결정된다.
- 그것은 subscripts가 가리키는 것이다.

region A : u_CA <= 0 && v_AB <= 0
region B : u_AB <= 0 && v_BC <= 0
region C : u_BC <= 0 && v_CA <= 0

* Edge regions
- 우리는 the line segment barycentric coordinates를 사용하여 한 점이 edge region에 있는지를 부분적으로(partially) 결정할 수 있다.
- 그러나 그것들이 우리에게 한 점이 AB의 위 또는 아래에 있는지를 말해주지 않기 때문에 어떤 정보를 놓치는 중이다.

ex) u_AB > 0 && v_AB >0 인데, 그 점이 edge 위에 있는지 아래에 있는지 모른다.
Line segment uv가 충분하지 않다는 것이다.

* Interior region
- 또한, 우리는 한 점이 내부에 있는지를 결정할 방법을 가지고 있지 않다.

* Triangle barycentric coordinates
- 우리는 삼각형에 대해 Q의 barycentric coordinates를 연산하여 우리가 필요한 추가 정보를 얻을 수 있다.
- 우리가 Q를 그 삼각형들의 정점의 가중된 합으로 표현하자.
- 선분에서 처럼, 우리는 barycentric coordinates가 더해서 1이 되기를 요구한다. 이제는 2개 대신에 3개의 좌표를 요구하는 것을 제외하고.
- 우리는 여전히 부호에 어떠한 제한을 두고있지 않다. 그래서 그 좌표들은 개별적으로 음수가 될 수 있다.
- 이러한 새로운 barycentric coordinates는 (u,v,w)의 관점에서 평면위의 어떤 점을 나타내게 해준다.

* Linear algebra solution
- 만약 우리가 이전의 방정식을 결합한다면, 우리는 선형대수를 사용하여 Q의 barycentric coordinates를 연산할 수 있다.
- 우리는 이 방식으로 그것들을 연산하지 않을 것이다. 왜냐하면 그것은 우리의 기하학적 이해를 줄이기 때문이다.

* Fractional areas
- 우리가 삼각형에 대해 barycentric coordinates를 기하학적으로 이해하게 해보자. 이제, 우리는 Q가 내부에 있다고 가정한다.
- 그 point to line segment problem을 다시 떠올리자.
- 그 경우에, 우리는 barycentric coordinates를 partial segments의 fractional lengths에 연관시켰었다.
- 비슷한 방식으로, 우리는 그 삼각형의 barycentric coordinates를 partial triangles의 fractional areas에 연관시킬 수 있다.
- 이것은 barycentric coordinates가 안에 들어있는(insribed) 삼각형들의 면적에(areas) 비례하다는 것을 가리킨다.

* The barycentric coordinates are the fractional areas
- 그래서 u는 BCQ의 면적에 비례한다.
- u가 A에 대한 barycentric coordinate 이지만, 그것이 오직 A를 포함하지 않는 sub-triangle 만의 area에 비례한다는 것에 주의해라.
- 비슷한 규칙들이 v와 w에 적용된다.

u ~ Area(BCQ)
v ~ Area(CAQ)
w ~ Area(ABQ)

* Barycentric coordinates
- 만약 우리가 Q를 A 쪽으로 움직인다고 상상해라
- 그러고나서, u는 전체 삼각형을 덮게 되고, 반면에 v와 w는 사라진다.
- 그러므로, u는 명백히 A에 대한 가중치이다.
- 안에있는 삼각형들을 기반으로, 우리는 u,v,w에 대한 이러한 공식들에 도달하게 된다.

* Barycentric coordinates are fractional
- 너는 여기에서 한 경향성을 알아차렸을지도 모른다.
- line segments에 대해 우리는 barycentric coordinates는 fractional lengths이다.
- triangles에 대해, barycentric coordinates는 fractional areas 이다.
- tetrahedrons에 대해 너는 barycentric coordinates가 fractional volumes이라는 것을 추측할지도 모른다. 그리고 그게 맞다.

line segment : fractional length
triangles : fractional area
tetrahedrons : fractional volume

* Computing Area
- 그래서 우리는 어떻게 한 삼각형의 면적을 연산하는가?
- 평행사변형의 넓이가 그 삼각형의 두 개의 변의 외적으로부터 구해진다는 것을 상기해라.
- 2D에서 cross product는 scalar이다.
- 삼각형 ABC의 넓이는 관련된 평행사변형의 넓이의 절반이다.
- ABC의 감기는 순서(winding order)에 따라서, 그 area가 음수일 수 있다는 것에 주의해라.

* Q outside the triangle
- 우리가 삼각형에 대해 signed areas를 쓰기 때문에, 우리는 Q가 ABC의 밖에 있는 경우를 처리할 수 있다.
- Q가 edge BC의 밖에 있을 때, v와 w는 양수이고, 그것들의 합은 1보다 더 크다.
- 반면에, BCQ의 감기는 순서는 반대가 된다. 그래서 U는 음수가 된다.
- 그럼에도 불구하고, 그 합은 u + v + w == 1이 된다.

* Voronoi versus Barycentric
- Voronoi regios != barycentric coordinate regions
- The barycentric regions는 여전히 유용하다.
- 우리가 계속하기전에, 나는 중요한 구분을 할 필요가 있다.
- 우리의 접근법은 Voronoi regions을 사용하여 가장 가까운 점을 연산하는 것이다.
- 우리는 그러한 영역을 찾는 것을 돕기 위해 barycentric coordinates를 연산한다.
- line segment의 경우에, 우리는 barycentric coordinates가 즉시 우리에게 Voronoi regions을 준다는 것을 알았다.
- 그러나 삼각형에 대해서, Voronoi regions는 barycentric coordinates에 의해 결정되는 regions과 같지 않다.
- 우리는 이것을 다룰 수 있지만, 처음에 한 삼각혀에 대해 barycentric regions에 대해 보자.

* Barycentric regions of a triangle
- 여기에 우리의 삼각혀이 있다.
- barycentric regions가 무엇인가?

* Interior
- 우리는 모든 좌표들이 양수일 때, interior region을 갖는다.
u > 0 && v >0 && w> 0

* Negative u
- 만약 u가 음수라면 (u <= 0), 그러면 Q는 edge BC 밖에 있다.

* Negative v
- 만약 v가 음수라면, 그러면 Q는 edge CA 밖에 있다.

* Negative w
- 마지막으로, 만약 w가 음수라면, 그러면 Q는 edge AB 밖에 있다.

* The uv regions are not exclusive
- barycentric regions는 상호배제하지 않는다.
- 두 개의 barycentric coordinates가 동시에 음수일 수 있다.
- 이 경우에, 그 query point는 동시에 두 개의 edges의 밖에 있다.
- 일반적으로, 이것은 Q가 vertex region에 있다는 것을 가리키지 않는다.
- 이 슬라이드에서, 우리는 Q가 BC와 CA 밖에 있는 것을 보지만, BC에 가장 가깝다.

* Finding the Voronoi region
- Voronoi region을 인식하기 위해 barycentric coordinates를 사용해라
- 3개의 line segments와 그 삼각형에 대한 Coordinates
- Regions는 올바른 순서로 고려되어야 한다.

- 우리는 이제 triangle의 Voronoi regions을 결정할 충분한 정보를 가지고 있다.
- 한 query point P는 삼각형과 그리고 3개의 선분들 독립적으로 barycentric coodinates를 가질 수 있다.
- 이것은 총 9개의 barycentric coordinates를 준다. 
- 각 line segment에 대해 두 개 그리고 그 삼각형에 대해 3개
- 우리는 Voronoi region을 결정하기 위해 이러한 9개의 스칼라값을 사용할 수 있다.
- 우리는 우리의 logic을 올바르게 구성하기 위해 주의해야만 한다.
-  올바른 접근법은 처음에 가장 낮은 차원의 features를 고려하는 것이다: vertices, 그러고나서 edges, 그러고나서 triangle's interior

* First : vertex regions
- 우리는 처음에 vertex regions을 테스트한다.
- 여기에 우리는 3개의 line segments로부터 6개의 coordinates를 사용한다.

region vertex A : u_CA <= 0 && v_AB <= 0
region vertex B : u_AB <= 0 && v_BC <= 0
region vertex C : u_BC <= 0 && v_CA <= 0

* Second : edge regions
- line segment uv들이 query point가 edge Voronoi region 안에 있는지를 결정하는데 충분하지 않다는 것을 상기해라.
- 편리하게도, 삼각형의 uv는 놓친 정보를 제공한다.

* Second : edge regions solved
- 우리는 line segment uv들을 triangle uv와 결합할 수 있는데, query point가 edge region 안에 있는지를 결정하기 위해서이다.
- 우리는 그 query point가 A와 B 사이에 있는지를 가리키기 위해 두 개의 line segment uv를 갖는다.
- 우리는 이제 그 query point가 AB 위에 있는지를 가리키기 위해 triangle w coordinate를 가진다.

region edge AB : u_AB > 0 && v_AB > 0 && w_ABC <= 0
region edge BC : u_BC > 0 && v_BC > 0 && u_ABC <= 0
region edge CA : u_CA > 0 && v_CA > 0 && v_ABC <= 0

* Third : interior region
- 모든 다른 테스트들이 실패한 후에, 우리는 Q가 interior region에 있다고 결정한다.
- 어떠한 다른 경우가 없기 때문에, 우리는 삼각형 uv들이 모두 양수라고 주장한다.
region interior ABC : u_ABC > 0 && v_ABC > 0 && w_ABC > 0

* Closest point 
- Find the Voronoi region for point Q
- Use the barycentric coordinates to compute the closest point P
- 마침내 우리는 삼각형에서 가장 가까운 점을 연산할 준비가 되었다.
- 처음에, 우리는 점 Q에 대해 Voronoi region을 찾는다.
- 그러고나서, 우리는 가장 가까운 점을 연산하기 위해 적절한 barycentric coordinates를 사용한다.

* Example 1
- 여기에 가장 가까운 점을 어떻게 연산하는지에 대한 예제가 있다.
- 우리는 삼각형 ABC와 query point Q로 시작한다.
- 우리는 u_AB가 음수라는 것을 결정한다.
- 우리는 v_BC가 또한 음수라는 것을 결정한다.
- 우리는 Q가 vertex region B에 있다고 결론짓는다.
- 그래서 P = B이다.
- A와 C는 P에 기여하지 않는다.

* Example 2
- 여기에 다른 위치를 가진 Q의 또 다른 예시이다.
- 처음에, Q는 어떠한 vertex region에 들어있지 않다고 결정한다.
- 우리는 Q가 B의 오른쪽에 있다는 것을 결정한다 (u_AB > 0)
- 그리고 A의 왼쪽에 있다는 것을 결정한다. (v_AB > 0)
- 그래서 Q는 A와 B 사이에 있다.
- 우리는 Q가 AB의 밖에 있는지를 결정하기 위해 삼각형의 barycentric coordinate를 사용한다.
- Q는 edge region AB에 있다. (u_AB > 0 && v_AB > 0 && w_ABC <= 0)
- 가장 가까운 점 P는 AB 위에 있다.
- 그래서 우리는 P를 결정하기 위해 AB의 barycentric coordinates를 사용한다
   P = u_AB * A + v_AB * B

* Implementation
input: A, B, C, Q
compute uAB, vAB, uBC, vBC, uCA, vCA
compute uABC, vABC, wABC

// Test vertex regions
...

// Test edge regions
...

// Else interior region
...

- 우리는 입력으로 삼각형의 정점들과 query point Q를 갖는다.
- 모든 line segment barycentric coordinates를 연산해라.
- 그러고나서 triangular barycentric coordinates를 연산해라.
- 그러고나서 우리는 Voronoi regions을 연산하기 시작한다.

* Testing the vertex regions
// Region A
if ( vAB <= 0 && uCA <= 0)
     P = A
     return

// Similar tests for Region B and C

- 처음에 3 개의 vertex regions을 테스트한다.
- 우리는 여기에서 early return을 얻을 수 있다.

* Testing the edge regions
// Region AB
if (uAB > 0 && vAB > 0 && wABC <= 0)
    P = uAB * A + vAB * B
    return

// Similar for Regions BC and CA

- 다음에 우리는 edge regions를 테스트한다.

* Testing the interior region
// Region ABC
assert(uABC > 0 && vABC > 0 && wABC > 0)
P = Q
return

이 점에서, Q는 그 삼각형의 내부에 있음에 틀림없다. 그래서 우리는 이것이 사실이라고 주장한다.
- 그러고나서 barycentric coordinates는 triangular barycentric coordinates이고, 모든 삼각형 정점들은 P에 기여한다.

* Section 3 : Point to Convex Polygon
- 그래서 우리는 point vs triangle을 정복했다.
- 이제, point to convex polygon을 봐서 우리의 목표에 더 가까이 가자.

* Convex polygon
- 여기에 임의의 convex polygon (볼록 다각형) ABCDE가 있다.
- 우리는 그 다각형이 한 변(edge)를 가로지르는 내부의 점들 사이의 선분이 존재하지 않기 때문에 convex라고 말한다.

* Polygon structure
struct Polygon
{
     Vec2* points;
     int count;
};

- 여기에 polygon structure 코드가 있다.
- 이것은 2D points의 배열이다.

* Convex polygon : closest point
- 그래서 이제 우리는 query point Q를 가지고 있다.
- 우리는 가장 가까운 점 P를 결정하기를 원한다.
- 우리는 이것을 쉽게 시각화할 수 있다. 그러나, 컴퓨터가 이것을 정확하고 효율적으로 하게 하는 것은 또 다른 문제이다.
- How do we compute P?

* What do we know?
- Closest point to point
- Closest point to line segment
- Closest point to triangle
- 우리가 이미 어떻게 할 지를 아는 것들이 위의 것이다.

* Simplex
- 편리성을 위해서, 우리는 points, line segments, triangles를 하나의 공통된 주제 아래에서 그룹화 한다.
- A simplex is a point, a line segment, a triangle, or a tetrahedron 이다.
- 우리는 0차원 simplex에 대해 0-simplex라고 말한다 (a point), 1차원 simplex에 대해 1-simplex(a line segment), 등등

* Idea : inscribe a simplex
- 그래서 여기에 P를 연산하는 것에 대한 아이디어가 있다.
- 우리는 그 polygon에 triangle을 inscribe한다.
- 왜 그렇게 하는가?
- 왜냐하면 우리는 한 삼각형에서 가장 가까운 점을 어떻게 연산할지를 알고 있기 때문이다.

* Idea : closest point on simplex
- Vertex C가 Q에 대한 simplex에서 가장 가까운 점이다.

* Idea : evolve the simplex
- 이제 Q에 대해 simplex를 어느정도 진화시키기 위해 그 simplex에서 가장 가까운 점을 사용한다.

* Simplex vertex
struct SimplexVertex
{
     Vec2 point;
     int index;
     float u;
};

- 여기에 simplex vertex structure가 있다.
- 그 점은 한 polygon vertex로부터 복사된다.
- 우리는 또한 그 index를 저장한다.
- 우리 closest point calculations를 위해 barycentric coordinate u를 포함한다.

* Simplex
struct Simplex
{
     SimplexVertex vertexA;
     SimplexVertex vertexB;
     SimplexVertex vertexC;
     int count;
};

- 여기에 simplex data structure가 있다.
- 그것은 a point, a line segment, or a triangle를 나타낼 수 있다.

* We are onto a winner!
- 그래서 나는 우리가 성공가능한 것을 찾아냈다고 생각한다.
- 우리는 처리할 어떤 세부사항을 가진다.
- 주로, 우리는 그 simplex를 어떻게 진화시킬지를 이해할 필요가 있다.

* GJK distance algorithm
- Computes the closest point on a convex polygon
- Invented by Gilbert, Johnson, and Keerthi
- 운 좋게도, Gilbert, Johnson, and Keerthi가 우리를 위해 GJK라고 불려지는 한 알고리즘의 세부사항을 작업했다.
- Gilbert와 회사는 1980년대 후반에 알고리즘에 대한 몇 가지 논문들을 썼었다.
- 그것들은 모두 매우 수학적이고 이해하기에 어렵다.
- 그것들은 또한 좋은 pastel colors가 부족하다.

* The GJK distance algorithm
- Inscribed simplexes
- Simplex evolution
- 그것의 깊은 수학적 뿌리에도 불구하고, GJK는 직관적 기하학 해석이다.
- GJK는 iterative algorithm이다.
- 우리는 우리의 convex polygon에 새겨진 한 임의의 simplex로 시작한다.
- 우리는 그 simplex에서 가장 가까운 점을 연산하고, 그 polygon에서 가장 가까운 점 쪽으로 simplex를 진화시키기위해 그 결과를 사용한다.
- 원리적으로, 우리는 유한한 개수의 반복으로 정확한 솔루션을 얻는다. 현실적으로, 우리가 처리해야 할 numerical problems가 있다.
- GJK 알고리즘을 더 섦여하기 보다, 이 시점에서, 그것이 어떻게 작동하는지에 대한 예제를 보는 것이 더 좋다.

* Starting simplex
- Start with arbitrary vertex. Pick E.
- This is our starting simplex
- 우리는 우리의 convex polygon과 query point Q를 가지고 있다.
- 우리는 한 임의의 simplex를 골라서 GJK 알고리즘을 시작한다.
- 이 경우에, 우리는 vertex E를 가진 0-simplex를 선택한다.

* Closest point on simplex
- P is the closest point
- 다음으로 우리는 Q에 대해 우리의 simplex에서 가장 가까운 점을 결정한다.
- 이 경우에 P = E이다.

* Search vector
- Draw a vector from P to Q. And call this vector d.
- 이제 우리는 search vector를 구성한다.
- 이 벡터는 우리의 simplex에 있는 가장 가까운점에서 Q를 가리킨다.
- 우리가 0-simplex를 가지고 있기 때문에, 그 가장 가까운 점은 E이다.

* Find the support point
- Find the vertex on polygon furthest in direction d.
- This is the support point.
- 우리는 이제 search direction에서 가장 멀리있는 정점을 결정한다.
- 이것은 support point라고 불려진다.

* Support point code

int Support(const Polygon& poly, const Vec2& d)
{
   int index = 0;
   float maxValue = Dot(d, poly.points[index]);
   for (int i = 1; i < poly.count; ++i)
   {
      float value = Dot(d, poly.points[i]);
      if(value > maxValue)
      {
         index = i;
         maxValue = value;
      }
   }
   return index;
}

- 여기에 그 support point를 연산하는 코드가 있다.
- 그 거리는 간단한 dot product로 결정된다.
- 그 코드는 모든 polygon vertices에 대해 반복하고, 가장 큰 내적 값을 추적한다.
- 그 비교가 모두 상대적이기 때문에, search direction d는 표준화 될 필요가 없다.

* Support point found
- C is the support point.
- 이 경우에, 시각적으로 C가 명백히 support point이다.
- 그래서 우리는 C로 무엇을 하는가?

* Evolve the simplex
- Create a line segment CE
- We now have a 1-simplex.
- 우리는 C를 현재의 simplex와 합친다.
- 우리가 E를 가진 0-simplex를 가졌기 때문에, 우리는 이제 CE를가진 1-simplex를 가진다.

* Repeat the process
- Find closest point P on CE
- 우리는 그 프로세스를 이제 반복한다.
- 우리는 우리의 현재 simplex CE에서 가장 가까운 점을 찾는다.

* New search direction
- Build d as a line pointing from P to Q
- 우리는 P에서 Q를 가리키는 새로운 search direction을 구성한다.

* New support point
- D is the support point
- 다음으로, 우리는 방향 d에서 새로운 support point를 연산한다.
- 우리는 support point로서 D를 찾는다.

* Evolve the simplex
- Create triangle CDE.
- This is a 2-simplex.
- 우리는 우리의 simplex에 D를 합치고, 2-simplex CDE를 만든다.

* Closest point
- Compute closest point on CDE to Q
- 우리는 그 simplex에 대해 가장 가까운 점으로서 P를 연산한다.

* E is worthless
- Closest point is on CD
- E does not contribute
- 우리는 E가 P에 기여하지 않는 다는 것을 알게 된다.
- 그래서 우리는 simplex에서 E를 제외한다.
- 우리는 simplex가 결코 3개 이상의 정점을 갖지 않도록 기여하지 않는 정점을 cull해야한다.

* Reduced simplex
- We dropped E, so we now have a 1-simplex
- 현재 simplex는 이제 CD 이다.
- 우리가 2-simplex에서 1 or 0-simplex로 갈 수 있다는 것을 주목해라.
- 그래서 우리는 동시에 두 개 까지의 simplex vertices를 제거할 수 있다.

* Termination
- Compute support point in direction d.
- We find either C or D. Since this is a repeat, we are done.
- 우리는 P에서 Q를 가리키는 새로운 search vector를 형성한다.
- 이제 그 새로운 support point는 C 또는 D 둘 중 하나이다.
- 우리는 그 점을 유일하게 결정할 수 없다.
- 그러나 그것은 중요하지 않다.
- 이러한 정점들은 이미 simplex에 있기 때문에, 우리는 어떠한 진행을 할 수 없다.
- 그러므로, 우리는 P가 가장 가까운 점으로 그 알고리즘을 종료시킨다.

* GJK algorithm
Input : polygon and point Q
pick arbitrary initial simplex S
loop
   compute closest point P on S
   cull non-contributing vertices from S
   build vector d pointing from P to Q
   compute support point in direction d
   add support point to S
end
- 여기에 GJK 알고리즘에 대한 pseudo code가 있다.
- 이것은 iterative algorithm이고, 그래서 우리는 loop해야만 한다.
- 이 코드는 종료 조건을 포함하지 않는다.
- 나는 이것을 잠시 뒤에 다룰 것이다.

* Numerical Issues
- Search Direction
- Termination
- Poorly formed polygons
- 내가 너에게 경고했었듯이, 우리가 다룰 필요가 있는 많은 numerical problems가 있다.
- 내 경험에서, 이러한 문제들은 search direction과 loop termination에 영향을 미친다.

* A bad direction
- d can be built from PQ
- Due to round-off : dot(Q - P, C- E) != 0
- 이제까지, 우리는 P에서 Q로가는 벡터로서 search direction을 연산했었다.
- 이것은 항상 가장 좋은 접근법이 아니다.
- 이 예제에서, P는 the line segment CE에서 barycentric coordinates로부터 연산된다.
- Barycentric coordinates는 round off error를 겪는다. 그래서 PQ는 segment CE에 대해 수직이 아닐지도 모른다.

* A real example in single precision
Line Segment
A = [0.021119118, 79.584320]
B = [0.020964622, -31.515678]

Query Point
Q = [0.0 0.0]

Barycentric Coordinates
(u, v) = (0.28366947, 0.71633047)

Search Direction
d = Q - P = [-0.021008447, 0.0]

dot(d, B - A) = 3.2457051e-006

- 여기에 내가 겪었던 실제 세계 예제가 있다.
- 나는 선분 AB와 query point Q를 가지고있다.
- 나는 가장 가까운 점 P를 연산하고, search direction d를 만들기 위해 그것을 사용한다.
- 내가 segment direction과 search direction을 내적을 연산했을때, 0이 아닌 값을 얻는다.
- 그렇다, 그것은 작언 에러지만, search direction에서 작은에러들은 커질 수 있다.

* Small errors matter
- 부정확한 search directions는 나쁘다. 왜냐하면 그것들은 부정확한 support points를 이끌 수 있기 때문이다.
- 이것은 괃환 반복 또는 심지어 부정확한 결과를 이끌지도 모른다.

* An accurate search direction
- Directly compute a vector perpendicular to CE
- d = cross(C - E, z)
- where z is normal to the plane.
- 우리가 어려움없이 정확한 search direction을 얻을 수 있다는 것이 밝혀졌다.
- 가장 가까운 점이 한 edge위에 있을 때, 너는 search direction을 연산하기 위해 closest point를 사용해선 안된다.
- 대신에, 그 edge에 수직인 벡터를 형성하여 search direction을 연산하는게 더 좋다.
- 우리는 edge vector와 plane normal를 외적하여 perpendicular vector를 얻을 수 있다.

* The dot product is exactly zero
- edge direction : e = (x y)
- search direction : d = (-y x)
- dot product : dot(e, d) = -xy+ xy = 0
- 이것은 search direction이 그 edge에 수직이라는 것을 의미한다.
- 그 내적은 numerically하게 zero이다. 심지어 floating point arithmetic으로 할지라도.

* Fixing the sign
- Flip the sign of d so that : dot(d, Q - C) > 0
- Perk : no divides
- 그러고나서 우리는 그것이 Q를 가리키도록하기 위해 d의 부호를 바꿀 필요가 있다.

* Termination conditions
- 부정확한 search directions으로, termination conditions는 많은 슬픔을 만들어 낼 수 있다.
- 우리는 너무 일찍 종료하길 원하지 않고, 전혀 종료하지 않길 원하지 않는다.
- infinite loop는 너의 frame-rate를 죽일 모든 것이다.
- 그래서 우리는 termination conditions에 좋은 일들을 하려고 해야 한다.

* Case 1 : repeated support point
- 우리의 첫 번째 케이스는 반복된 support point이다.
- 이 경우에, 우리는 우리의 현재 simplex에 속하는 support point를 연산한다.
- 이것은 우리가 어떠한 진행을 할 수 없다는 것을 가리킨다.그래서, 우리는 가장 가까운 점 P로 종료해야 한다.

* Case 2 : containment
- We find a 2-simplex and all vertices contribute
- 우리의 GJK 반복에서 어떤 시점에서, 우리는 2-simplex를 발견할지도 모르는데, 거기에서 Q에 대한 모든 triangular barycentric coordinates가 양수일 수 있다.
- 이것은 Q가 2-simplex 안에 있다는 것을 의미한다. 그러므로, parent polygon 안에 있다는 것이다.

* Case 3a : vertex overlap
- We will compute d = Q - P as zero
- So we terminate if d = 0
- 만약 Q가 한 정점과 중첩된다면, 그러면 P = Q이고, 우리는 zero search direction을 연산하게 될 것이다.
- 그래서 우리는 d가 zero라면 종료해야 한다.

* Case 3b : edge overlap
- d will have an arbitrary sign
- Q가 edge와 중첩되는 것이 가능하다.
- 우리는 d를 perpendicular vector로서 연산할 수 있다.
- 그러나, 우리는 그것의 부호를 결정할 수 없다.
- d의 부호가 임의로 될 것이기 때문에, 우리는 두 경우를 조사해야 한다.

* Case 3b : d points left
- If we search left, we get a duplicate support point. In this case we terminate.
- 만약 d가 왼쪽을 가리킨다면, 우리는 Case 1 : a duplicate support point를 얻는다.

* Case 3b : d points right
- If we search right, we get a new support point (A).
- 만약 d가 오른쪽을 가리킨다면, 그러면 우리는 새로운 support point를 얻는다.

- But then we get back the same P, and then the same d.
- Soon, we detect a repeated support point or detect containment.
- round-off error에 따라, 우리는 P가 edge CD 위에 있거나 P가 triangle ACD안에 있다는 것을 알게 될 것이다.
- 그래서 우리는 duplicate vertex를 얻거나 또는 containment를 탐지할 것이다.

* Case 4 : interior edge
- d will have an arbitrary sign
- 우리가 고려하는 마지막 경우는 Q가 우리의 simplex의 interior edge와 중첩될 때 이다.
- 이 경우에, 우리의 simplex는 an interior line segment이다.
- Q가 그 line segment와 중첩되기 때문에, 우리는 d를 유일하게 결정할 수 없다.

- Similar to Case 3b
- 이것은 궁극적으로 Case 3b와 같다.
- 우리가 어떤 d의 부호를 결정하든, 우리는 repeated vertex를 탐지할 수 있을것이다.

* Termination in 3D
- May require new/different conditions
- Check for distance progression
- 3D에서 GJK는 다른 termination conditions이 필요하다.
- 예를들어, 너는 P에서 Q로 가는 거리가 매 반복마다 줄어드는지를 테스트 할 필요가 있을지도 모른다.

* Non-convex polygon
- Vertex B is non-convex
- 만약 우리가 non-convex polygon을 만난다면 무슨일이 발생하는가?

* Non-convex polygon
- B is never a support point
- GJK는 non-convex vertex는 보지 않을 것이다. 왜냐하면 , 그것은 결코 support point로서 나타나지 않을 것이기 때문이다.

* Collinear vertices
- B, C, and D are collinear
- collinear points로는 무엇이 발생하는가?

- 2-simplex BCD
- 우리는 degenerate triangular simplex로 끝날 수 있다.

- area(BCD) = 0
- 그 삼각형 넓이는 zero이다. 그래서 그 triangular barycentric coordinates는 무한이다.
- 너는 area로 나누는 것을 피할 수 있다.
- 너는 너의 triangle solver가 이 경우에 vertex or edge region을 선택하도록 보장해야만 한다.
- 세부사항에 대해 데모코드를 보아라.

* Section 4 : Convex Polygon to Convex Polygon
- 그래서 그것이 GJK를 위한 것이다.
- 우리는 이제 우리의 최종 목표를 다룰 준비가 되어있다: 한 쌍의 convex polygons 사이의 closest point.

* Closest point between convex polygons
- 그래서 우리는 두 개의 convex polygons 사이의 가장 가까운 점을 연산하기를 원한다.
- 이것은 a single polygon에서 가장 가까운 점 보다 더 복잡한 것처럼 보일지도 모른다.
- 그러나, 그 두 문제를 연관짓는 방법이 있다.

* What do we know?
- 우리는 GJK 반복을 사용하여 point to polygon을 풀기위해 point to simplex problem에 대한 지식을 적용했었다.

* What do we need to know?
- 이제, 우리는 어떻게 point to polygon의 지식을 polygon to polygon에 적용할 수 있는가?

* Idea
- Convert polygon to polygon into point to polygon
- Use GJK to solve point to polygon
- 그 기본 아이디어는 우리는 polygon to polygon을 point to polygon으로 바꾼다.
- 그러고나서 우리는 point to polygon problem을 풀기위해 GJK를 사용할 수 있다.

* Minkowski difference
- 우리에게 정확히 우리가 필요한 것을 주는 Minkowski difference라고 불려지는 geometrical construction이 있다고 밝혀졌다.
- Minkowski difference는 우리가 두 개의 polygons을 단일의 convex polygon으로 합치도록 해준다.

* Minkowski difference definition

- 여기에, Minkowski difference에 대한 수학적 정의가 있다.

* Building the Minkowski difference
Input : polygon X and Y
array points
for all xi in X
    for all yj in Y
        points.push_back(yj - xi)
    end
end

polygon Z = ConvexHull(points)

- 우리는 단순한 기법을 사용하여 super polygon을 구성 할 수 있다.
- 우리는 두 폴리곤의 점들 사이의 차를 연산하기 위해 두 개의 nested loops를 사용한다.
- 그러고나서 우리는 그 point cloud의 convex hull를 연산한다.
- 물론,이것은 하기에 싸지 않지만, 인내심을 가져라
- 무지개 끝에 황금이 있다.

* Example point cloud
- 여기에 그 point cloud가 이 삼각형과 사각형에 대해 어떻게 보이는지가 있다.
- 그렇다, 나는 실제로 그러한 점들을 연산한다.

* Building the convex hull
- 나는 convex hull algorithms을 다루지 않을 것이지만, 개념적으로 우리는 convex hull algorithm을 a shrink wrapping process로서 상상할 수 있다.

- 우리는 extreme point로 시작하고, 둘레를 따라 우리의 길을 만든다.

* The final polygon
- 우리는 이제 Minkowski difference polygon에 도착했다.

* Property 1 : distances are equal
- distance(X, Y) == distance(O, Y - X)
- Minkowski difference는 몇 가지 놀랄만한 특성들을 가지고 있다. (유레카적)
- 처음에, X와 Y 사이의 거리는 원점과 super polygon 사이의 거리와 가탇.

* Property 2 : support points
- support(Z, d) = support(Y, d) - support(X, -d)
- 둘 째로, 우리는 X와 Y의 support points를 결합하여 Z의 한 support point를 결정할 수 있다.
- 우리는 Y에서 d 방향에 있는 support point와 X에서 -d방향의 support point를 사용한다.
- 이러한 두 개의 support points의 차는 Z에서의 support point와 동일하다.
- 우리는 explicitly하게 Z를 구성하지 않고 Z의 support point를 연산할 방법을 안다.

- 이것은 우리가 Z를 explicitly하게 구성할 필요가 없다는 것을 의미한다.
- 그래서 우리는 convex hull을 연산할 필요가 없다.
- 이것은 우리의 어플리케이션에서 많은 양의 시간과 공간을 절약시킨다.

* Modifying GJK
- Change the support function
- Simplex vertices hold two indices
- 우리는 Minkowski difference를 다루기 위 쉽게 GJK를 수정할 수 있다.
- 우리는 그냥 support function을 바꾸고 좀 더 bookkeeping을 추가할 필요가 있다.
- 세부사항을 위해 데모 코드를 보아라.

* Closest point on polygons
- Use the barycentric coordinates to compute the closest point on X and Y
- See the demo code for details
- 우리는 또한 원래의 폴리곤에 대해 closest points를연산하기 위해 GJK를 수정할 수 있다.
- 그러고나서 우리는 the closest points를 결정하기위해 original vertices에 대해 barycentric coordinates를 적용한다.
- 또 다시, 세부사항에 대해서는 데모 코드를 보아라.

2019년 3월 12일 화요일

지금까지 만든 것 (2019년 1월 기준)

1월에 프로젝트를 끝내고 이것저것 하다보니 업데이트를 해놓지 않았다.
이런 기록을 남겨두는 것은 이전으로부터 어떻게 발전해왔는지를 보여주기 때문에
종종 남겨놓는 것이 좋다고 생각한다.

1. 현재 만들어놓은 3D 게임 엔진의 최종 상황이다.
Sponza 모델과 Nanosuit를 통해 렌더링 했다.
영상은 최종 Scene을 만들기 위해 Light의 여러 Property를 수정하는 것을 보여준다.
아직 Culling 기능을 개발하지 않고 최적화가 이루어지지 않아 한 프레임 연산 속도는 느리다. Object Picking With Broad Phase(Dynamic AABB Tree), Model Loading (using Assimp) and Rendering + Model Diffuse/Specular/Emissive/Normal/Height Map (Normal Mapping, Parallax Occlusion Mapping), Light Property 편집, Light Shadow 설정 등이 들어갔다. learnopengl.com에서 배웠던 것을 Deferred Rendering 기반으로 바꾸면서 나의 이해를 증진시켰다. Post-Processing으로 Gamma Correction, Bloom, SSAO가 들어갔다.

2. 물리엔진 기반을 Box2D로 바꾸기로 결심하면서 Box2D-lite 코드를 이해하고 DirectX11 로 포팅해서 시뮬레이션 세팅하여 찍은 영상이다. 현재 Box2D 관련 자료들을 공부하며 이 기반을 다시 철저히 이해하기 위해 공부중이다. 2D를 이해하고 3D로 넘어갈 예정이다.

3. Terrain Rendering + Physics
Terrain을 Triangle Strip으로 한 번의 draw call로 렌더링했다.
그리고 Mesh vs Sphere의 Collision Detection and Response를 특히, Collision Detection 부분을 Bullet Physics를 참고해서 따라했다. 그 Bullet Physics의 코드를 이해하고 내 엔진에 적용할 수 있어서 매우 도전적이고 재미있는 경험이였다.
여기에서 BroadPhase(Dynamic AABB Tree) -> Mesh Quantization -> Early Exit (AABB vs AABB(of sphere) -> Narrow Phase(Triangle vs Sphere, Closest point on triangle using barycentric coordinate from Real Time Collision Detection book). 등의 많은 것들이 적용되었다. Mesh vs Box를 구현하려다 포기하고 Box2D로 돌아가게 되는 계기였는데, 어쨋든 가치있는 작업이였다.

2019년 3월 9일 토요일

GDC2007 Erin Catto 발표

Modeling and Solving Constraints

* 개요
- 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
 (separation)

                       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를 유지하길 원한다.
- 이것은 성능을 급격히 개선한다.