[Graphics] Separating Axis Theorem(SAT)
예전에 회사 분의 소개로 Separating Axis Theorem(SAT)에 대해 알게 되어, 이를 스터디해서 Playground라는 개인용 공간에 SAT라는 예제로 만들었습니다. 이때 나름 정리를 해두었다고 생각했는데, 이제 와서 보니 한 줄로만 정리해두어 다시 보니 전혀 도움이 되지 않아, 이 예제를 Labs로 옮기면서 간단하게나마 기억해두고 싶은 부분을 정리해두고자 합니다.
SAT란?
SAT는 볼록한(Convex) 물체가 충돌하는지 판단하고, 충돌에서 벗어나기 위해 사용할 수 있는 벡터(Minimum Translation Vector, MTV)를 얻는 데 사용할 수 있습니다. SAT는 볼록한 물체에만 적용이 가능하므로 볼록하지 않은 물체는 쪼개어 적용해야 합니다.
Projection
SAT는 두 물체의 충돌을 판단하는데 두 물체 사이에 간격이 존재하는지를 기준으로 확인하게 됩니다. 이때 사용하는 개념은 투영인데, 평행한 광원을 물체에 비출 때 그림자가 생기게 되며, 이를 통해 한 차원 위의 물체를 아래 차원으로 옮길 수 있게 됩니다. 3차원 물체를 투영하면 그 그림자는 2차원이며, 2차원 물체를 투영하면 1차원 그림자를 얻게 됩니다.
3차원 투영
SAT는 마치 손전등을 가지고 두 물체가 겹쳐있는지 확인하고자 모든 면을 벽에 비춰보는 것과 동일하게 동작합니다. 만약 두 물체의 모든 면을 다 비춰보았을 때, 어디에서도 두 물체의 그림자 사이에 간격을 발견할 수 없다면 두 물체는 접하고 있는 것입니다. 반대로 단 하나의 간격이 있다고 한다면 그 물체는 접하지 않은 상태가 됩니다.
SAT
이를 구현한 코드는 다음과 같습니다.
export default class SAT {
static getMTV(shape1: Shape, shape2: Shape): MinimumTranslationVector {
let overlap = Number.POSITIVE_INFINITY;
let smallest: Vector = null;
let shape: Shape = null;
const axes1 = shape1.getAxes();
const axes2 = shape2.getAxes();
for (let i = 0; i < axes1.length; i++) {
const axis = axes1[i];
const p1 = shape1.project(axis);
const p2 = shape2.project(axis);
if (!p1.overlap(p2)) {
return null;
} else {
let o = p1.getOverlap(p2);
if (o < overlap) {
overlap = o;
smallest = axis;
shape = shape1;
}
}
}
for (let i = 0; i < axes2.length; i++) {
const axis = axes2[i];
const p1 = shape1.project(axis);
const p2 = shape2.project(axis);
if (!p1.overlap(p2)) {
return null;
} else {
let o = p1.getOverlap(p2);
if (o < overlap) {
overlap = o;
smallest = axis;
shape = shape2;
}
}
}
return new MinimumTranslationVector(shape, smallest, overlap);
}
}Perpendicular Vector & Normal Vector
어떤 물체의 한 면이 다른 물체와 붙어있는지 살펴보고 싶다면, 해당 면을 비추어 확인할 벽이 필요하고 이는 이 면의 수직인 벽이어야 합니다.
이를 위해 판단하고자 하는 면의 수직인 벡터를 구하고 이를 normalize 한 노말 벡터를 구하여 축으로 사용하게 됩니다. 이를 위해 다음과 같은 Vector 클래스를 정의하여 사용하였습니다.
export default class Vector {
get length(): number {
return Math.sqrt(this.x * this.x + this.y * this.y);
}
constructor(public readonly x: number, public readonly y: number) {}
subtract(other: Vector) {
return new Vector(this.x - other.x, this.y - other.y);
}
perpendicular(): Vector { return new Vector(-this.y, this.x); }
dot(other: Vector): number {
return this.x * other.x + this.y * other.y;
}
normalize(): Vector {
const length = this.length;
return new Vector(this.x / length, this.y / length);
}
}다른 부분은 다 어렵지 않게 이해가 되었지만, 필자가 처음 접했을 시 perpendicular 부분은 잘 이해가 되지 않았습니다만, 이에 대해 찾아보니 다음과 같이 90도 회전을 통해 간단하게 도출됨을 알 수 있었습니다.
Step
앞서 살펴본 개념을 바탕으로 SAT 코드를 단계별로 쫒아가 보고자 합니다.
Step 1
우선 첫 단계는 다음과 같이 두 물체의 수직인 축들을 모두 구합니다.
export default class SAT {
static getMTV(shape1: Shape, shape2: Shape): MinimumTranslationVector {
let overlap = Number.POSITIVE_INFINITY;
let smallest: Vector = null;
let shape: Shape = null;
const axes1 = shape1.getAxes(); const axes2 = shape2.getAxes();
// ...
}
}
이때 사용한 Shape의 getAxes 메서드는 앞서 살펴본 것과 같이, 각 면에 해당하는 벡터를 구하고 이에 대한 수직인 노말 벡터를 구하여 반환합니다.
export default class Shape {
// ...
getAxes(): Vector[] {
const axes: Vector[] = [];
const length = this.vertices.length;
for (let i = 0; i < length; i++) {
const p1 = this.vertices[i];
const p2 = this.vertices[i + 1 === length ? 0 : i + 1];
const edge = p1.subtract(p2);
const normal = edge.perpendicular().normalize();
axes.push(normal);
}
return axes;
}
// ...
}Step 2
Step 1에서 얻은 축 중 첫 번째 물체에 해당하는 축들에 대하여 각각 두 물체의 면을 투영합니다.
export default class SAT {
static getMTV(shape1: Shape, shape2: Shape): MinimumTranslationVector {
// ...
for (let i = 0; i < axes1.length; i++) {
const axis = axes1[i]; const p1 = shape1.project(axis); const p2 = shape2.project(axis); // ....
}
// ...
}
}
이때 Projection은 축과 면의 내적을 사용하여 가장 작은 값과 큰 값을 가지고 구합니다.
export default class Shape {
// ...
project(axis: Vector): Projection {
let min = axis.dot(this.vertices[0]);
let max = min;
this.vertices.forEach(vector => {
const p = axis.dot(vector);
if (p < min) {
min = p;
} else if (p > max) {
max = p;
}
});
return new Projection(min, max);
}
// ...
}Step 3
Step 2에서 구한 두 물체의 투영을 가지고 두 물체가 겹치는지 여부를 확인합니다. 두 물체가 겹치지 않았다면 충돌하지 않았기 때문에 작업을 종료하며, 두 물체가 겹쳤다면 MTV를 구하기 위한 값을 처리합니다.
export default class SAT {
static getMTV(shape1: Shape, shape2: Shape): MinimumTranslationVector {
// ...
for (let i = 0; i < axes1.length; i++) {
// ...
if (!p1.overlap(p2)) { return null; } else { let o = p1.getOverlap(p2); if (o < overlap) { overlap = o; smallest = axis; shape = shape1; } } }
// ...
}
}
Projection 클래스에서 두 물체가 겹치는지 여부에 대한 판단은 다음과 같이 Step 2에서 구한 최대 최솟값이 겹치는지 여부로 판단하게 됩니다.
export default class Projection {
// ...
overlap(other: Projection): boolean {
return this.max > other.min && other.max > this.min;
}
// ...Step 4
나머지 물체에 대해서도 Step 2와 Step 3에서 수행한 작업을 동일하게 수행하여 겹치는지 확인합니다.
export default class SAT {
static getMTV(shape1: Shape, shape2: Shape): MinimumTranslationVector {
// ...
for (let i = 0; i < axes2.length; i++) {
const axis = axes2[i];
const p1 = shape1.project(axis);
const p2 = shape2.project(axis);
if (!p1.overlap(p2)) {
return null;
} else {
let o = p1.getOverlap(p2);
if (o < overlap) {
overlap = o;
smallest = axis;
shape = shape2;
}
}
}
// ...
}
}Step 5
Step 3에서 두 물체가 겹쳤을 때, 두 물체가 겹친 정도를 바탕으로 가장 적게 이동할 수 있는 벡터를 저장하여 MTV로 만들어 반환합니다.
export default class SAT {
static getMTV(shape1: Shape, shape2: Shape): MinimumTranslationVector {
// ...
return new MinimumTranslationVector(shape, smallest, overlap);
}
}마치며
SAT는 충돌 감지만을 목적으로 하는 경우에, 간단한 Vector 연산과 두 물체 사이의 하나의 간격만으로 마칠 수 있기 때문에 빠르다고 합니다. 다만, 판단해야 하는 면이 많거나 하는 경우에는 동일한 노말 벡터는 제외하는 등의 최적화가 필요할 것 같습니다.
추가로 SAT는 물체의 충돌 및 이를 해결하기 위한 MTV만 제공할 뿐, 어떤 면과 충돌하는지에 대해서 제공하지 않습니다.
앞서 설명한 내용을 바탕으로 작성한 예제는 Labs의 Separating Axis Theorem(SAT)에서 확인하실 수 있습니다.