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를 적용한다.
- 또 다시, 세부사항에 대해서는 데모 코드를 보아라.