2D 물리엔진을 만드는 방법 1편 번역

원문은

http://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-the-basics-and-impulse-resolution--gamedev-6331

초반에는 한줄한줄 정확히 번역하려고 했다가 영어 실력이 딸려서 번역도 힘들고 시간도 오래걸려서 초반부부터 그냥 대충 이해할 수 있는 정도로만 번역함(의역 + 개인 의견)

그냥 저 혼자 알아 볼 수 있을 번역한거라 오히려 영어가 보기 편할겁니다.

오역와 의역이 난무합니다.

---------------------------------------------------------------------------------------------------------------------------

여기 커스텀 물리엔진을 만드려는 많은 이유들이 있다: 먼저, 수학을 공부하고 연마하기 위해서 물리와 프로그래밍을 프로젝트에서 붙이는 것은 큰 이유이다; 두번째, 커스텀 물리엔진은 제작자가 제작 기술을 갖으며 다양한 종류의 기술적 효과를 얻을 수 있다. 이 기사에서 필자가 처음부터 완전히 어떻게 커스텀 물리엔진을 만드는지 알찬 소개를 할 것이다.

물리는 플레이어가 게임에 열중할 수 있도록 하는 멋진 수단을 제공한다. 물리엔진을 이해하는 것은 어떤 프로그래머이든지 처리할 일을 처리할 수 있는 파워풀한 자산이 될 것이다. 최적화와 특수화는 물리 엔진의 내부 동작에 대한 깊은 이해로 인해 언제든 이루어질 수 있다.

이 튜토리얼의 끝에는 2차원상의 다음의 내용이 있을것이다:

• 심플한 충돌 체크
• 심플한 다양체(manifold) 변환
• 충돌 해결

퀵 데모:

 

노트: 여기 튜토리얼은 C++으로 작성되었고, 너는 같은 기술과 컨셉을 거의 어떤 게임 환경에서도 활용할 수 있다.

---

전제 조건

이글은 상당한 양의 기하학과 수학, 그리고 낮은 실제 코딩 실력이 필요하다. 한 쌍의 전제 조건 :

• 기본적인 벡터 수학
• 대수학 능력

---

충돌 확인

여기 Tuts+를 포함해 인터넷에는 표면 충돌 확인에 대한 적은 수의 글과 튜토리얼들이 있다. Knowing this, I would like to run through the topic very quickly as this section is not the focus of this article.(이 글에서 이 부분을 너무 집중해서 보지 않았으면 좋겠다고...)

AABB충돌 (Axis Aligned Bounding Boxes)

An Axis Aligned Bounding Box (AABB) is a box that has its four axes aligned with the coordinate system in which it resides. This means it is a box that cannot rotate, and is always squared off at 90 degrees (usually aligned with the screen). In general it is referred to as a "bounding box" because AABBs are used to bound other more complex shapes.

(AABB박스의 특징은 사각형이 각 축을 기준으로 정렬되기 때문에 회전 할 수 없고 사각형의 각각의 각은 90도이다)

 

An example AABB.

The AABB of a complex shape can be used as a simple test to see if more complex shapes inside the AABBs can possibly be intersecting. However in the case of most games the AABB is used as a fundamental shape, and does not actually bound anything else. The structure of your AABB is important. There are a few different ways to represent an AABB, however this is my favorite:

(AABB박스를 표현하는 방법이 여러가지 있는데 자기는 이게 가장 좋다고 함... 근데 원래 이렇게 많이 쓰지 않나??)

1 2 3 4 5

struct AABB {   Vec2 min;   Vec2 max; };

This form allows an AABB to be represented by two points. The min point represents the lower bounds of the x and y axis, and max represents the higher bounds - in other words, they represent the top left and bottom right corners. (x의 최솟값과 y의 최솟값을 min에 넣고 x와 y의 최대값은 max에 넣음, 보통 화면 좌표계에서는 좌상단의 꼭지점이 min, 우하단의 꼭지점이 max값) In order to tell whether two AABB shapes are intersecting you will need to have a basic understanding of the Separating Axis Theorem (SAT).

Here's a quick test taken from Real-Time Collision Detection by Christer Ericson, which makes use of the SAT:

(Separating Axis Theorem(SAT)라는 것을 이해하고 있어야한다고 함, 그것으로 아래의 함수를 만들 수 있다고 함. AABB는 간단하기 때문에 별거 없음)

1 2 3 4 5 6 7 8 9

bool AABBvsAABB( AABB a, AABB b ) {   // Exit with no intersection if found separated along an axis   if(a.max.x < b.min.x or a.min.x > b.max.x) return false   if(a.max.y < b.min.y or a.min.y > b.max.y) return false     // No separating axis found, therefor there is at least one overlapping axis   return true }

원(Circles)

A circle is represented by a radius and point. Here is what your circle structure ought to look like:

(원을 구조체로 구현)

1 2 3 4 5

struct Circle {   float radius   Vec position };

Testing for whether or not two circles intersect is very simple: take the radii of the two circles and add them together, then check to see if this sum is greater than the distance between the two circles.

An important optimization to make here is get rid of any need to use the square root operator:

(원의 충돌체크 확인을 함수로 확인. 이것도 관련 자료가 많아서 생략)

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17

float Distance( Vec2 a, Vec2 b ) {   return sqrt( (a.x - b.x)^2 + (a.y - b.y)^2 ) }   bool CirclevsCircleUnoptimized( Circle a, Circle b ) {   float r = a.radius + b.radius   return r < Distance( a.position, b.position ) }   bool CirclevsCircleOptimized( Circle a, Circle b ) {   float r = a.radius + b.radius   r *= r   return r < (a.x + b.x)^2 + (a.y + b.y)^2 }

In general multiplication is a much cheaper operation than taking the square root of a value.

---

충격(충동) 해결(Impulse Resolution)

Impulse resolution is a particular type of collision resolution strategy. Collision resolution is the act of taking two objects who are found to be intersecting and modifying them in such a way as to not allow them to remain intersecting.

In general an object within a physics engine has three main degrees of freedom (in two dimensions): movement in the xy plane and rotation. (보통 일반적으로 물리엔진에는 3가지 degrees of freedom(자유도)가 있는데 xy평면에서의 움직임(각 축마다 1개씩임), 회전이 2차원상에서 표현됨) In this article we implicitly restrict rotation and use just AABBs and Circles, so the only degree of freedom we really need to consider is movement along the xy plane. (이 글에서는 회전을 제한하여 AABB와 원만을 사용하여 xy평면에서의 움직임만 구현 할 것임)

By resolving detected collisions we place a restriction upon movement such that objects cannot remain intersecting one another. The idea behind impulse resolution is to use an impulse (instantaneous change in velocity) to separate objects found colliding. In order to do this the mass, position, and velocity of each object must be taken into account somehow: we want large objects colliding with smaller ones to move a little bit during collision, and to send the small objects flying away. We also want objects with infinite mass to not move at all.

(위에까지는 그냥 충돌 체크만 했는데 이제 충돌로 인한 속도를 넣어줄 것이기 때문에 질량, 위치, 가속도를 각각의 오브젝트에 넣어줄 것임. 우리는 큰 물체와 작은 물체가 서로 부딪치면 작은 물체는 날아가고 큰 물체는 많이 움직이지 않는 것을 원함)

 

Simple example of what impulse resolution can achieve.

In order to achieve such effects and follow along with natural intuition of how objects behave we'll use rigid bodies and a fair bit of math. (자연스럽게 행동하도록 물체에 우리는 강체(rigidbody)들과 약간의 수학을 사용 할 것임) A rigid body is just a shape defined by the user (that is, by you, the developer) that is implicitly defined to be non-deformable. (강체(rigidbody)는 네가(개발자가) 정의한 형태(shape)로 무조건 변형할 수 없도록 정의되어 있어야 한다)  Both AABBs and Circles in this article are non-deformable, and will always be either an AABB or Circle. No squashing or stretching allowed. (이글에서 AABB와 원은 변형이 불가능하며 깨거나 늘이는 것도 하지 않을 것이다)

Working with rigid bodies allows for a lot of math and derivations to be heavily simplified. This is why rigid bodies are commonly used in game simulations, and why we'll be using them in this article.

(강체(rigidbody)는 많은 수학과 무겁고 단순화된 derivation?이고 이 글에서 왜 그것을 사용하는지 어떻게 사용하는지 배우겠다는 뜻)

물체가 충돌하면 - 이제 뭘하지?(Our Objects Collided - Now What?)

Assuming we have two shapes found to be intersecting, how does one actually separate the two? Lets assume our collision detection provided us with two important pieces of information: (우리의 충돌에 어떤 중요한 정보를 알아내고 제공해야하는지 추측해보자)

• Collision normal (충돌 노멀)
• Penetration depth (관통 깊이 or 침투 깊이)

In order to apply an impulse to both objects and move them apart, we need to know what direction to push them and by how much.

(두 물체가 부딪쳐서 어떤방향으로 밀려나는지 알아야 함) The collision normal is the direction in which the impulse will be applied.  (충돌 노멀은 충돌뒤 갱신되는 그 방향이다) The penetration depth (along with some other things) determine how large of an impulse will be used. (관통 깊이의 크기를 사용한다)  This means the only value that needs to be solved for is the magnitude of our impulse. (이것으로 충격 규모의 값을 구할 수 있는 방법이다) 

Now let's go on a long trek to discover how we can solve for this impulse magnitude. We'll start with our two objects that have been found to be intersecting:

(두 오브젝트의 교차(intersect)한 것을 구하자)

Equation 1

Note that in order to create a vector from position A to position B, you must do: endpoint - startpoint. (위치 A에서 위치 B까지의 벡터를 구한다 반드시 '도착지점 - 시작 지점'으로 구한다) is the relative velocity from A to B. (VAB는 A에서 B로의 상대 가속도이다) This equation ought to be expressed in terms of the collision normal n - that is, we would like to know the relative velocity from A to B along the collision normal's direction: (A에서 B로의 충돌 노멀의 방향을 구하는 공식)

 

Equation 2

 

We are now making use of the dot product. The dot product is simple; it is the sum of component-wise products:

(이제 내적 쓰면 된다. 내적은 다음과 같다)

Equation 3

The next step is to introduce what is called the coefficient of restitution.(다음 단계에서는 반발 계수(Coefficient of restitution)에 대해 소개하겠다.) Restitution is a term that means elasticity, or bounciness.(반발이란 탄성, 탄력을 이야기한다) Each object in your physics engine will have a restitution represented as a decimal value.(각각의 물체의 반발은 너의 물리 엔진에서는 소수로 표현 할 것이다) However only one decimal value will be used during the impulse calculation. (하지만 충격 계산 중에는 오직 하나의 숫자로만 사용한다) 

To decide what restitution to use (denoted by e for epsilon), you should always use the lowest restitution involved in the collision for intuitive results: (직관적인 결과를 위해 충돌에 관련된 최저 반발을 이용해야한다)

1 2	// Given two objects A and B e = min( A.restitution, B.restitution )

Once e is acquired we can place it into our equation solving for the impulse magnitude. (e는 우리는 이 공식으로 충격 규모를 구할 수 있다)

Newton's Law of Restitution states the following: (뉴턴의 반발 상태 법칙??? 한국어로 무엇을 표현하는지 모르겠음)

Equation 4

All this is saying is that the velocity after a collision is equal to the velocity before it, multiplied by some constant. This constant represents a "bounce factor". Knowing this, it becomes fairly simple to integrate restitution into our current derivation:

(충돌 후의 속도는 속도에 어떤 상수를 곱한 것이다. 이 상수는'bounce factor라고 부른다. 우리의 이러한 추론으로 이 반발을 간단하게 통합된다)

Equation 5

Notice how we introduced a negative sign here. In Newton's Law of Restitution, V' , the resulting vector after the bounce, is actually going in the opposite direction of V. So how do we represent opposite directions in our derivation? Introduce a negative sign.

(-기호가 붙는데  Newton's Law of Restitution에서 V'인 바운스 뒤에 얻는 결과 벡터는 V의 방향의 반대이다. 그래서 -기호를 붙여야 한다함.)

So far so good. Now we need to be able to express these velocities while under the influence of an impulse. Here's a simple equation for modify a vector by some impulse scalar j along a specific direction n :

(충격의 영향을 받은 속도를 표현해야한다. 여기 충격 스칼라는 j, 특정 방향을 n으로 표현한 간단한 공식이 있다)

Equation 6

 

Hopefully the above equation makes sense, as it is very important to understand. We have a unit vector n which represents a direction. We have a scalar j which represents how long our n vector will be. We then add our scaled n vector to V to result in V' . This is just adding one vector onto another, and we can use this small equation to apply an impulse of one vector to another.

(이 공식은 이해하는 것이 매우 중요하다. 우리는 방향을 가리키는 단위 벡터 n, 크기를 표현한 스칼라 j가 있다. 우리는 크기가 곱해진 n과 벡터 v를 더해 v'를 구한다. )

There's a little more work to be done here. Formally, an impulse is defined as a change in momentum. Momentum is mass * velocity. Knowing this, we can represent an impulse as it is formally defined like so:

(조금만 더 하면 된다. 충격은 운동량을 정한다. 운동량은 질량 * 속도이다.)

Equation 7

 

The three dots in a small triangle (∴) can be read as "therefore". It is used to show that the thing beforehand can be used to conclude that whatever comes next is true.

(∴는 '그러므로'라고 읽는다.(우리나라는 이거 중학교때 배우니까 다 아니까 다음 문장은 생략~))

Good progress has been made so far! However we need to be able to express an impulse using j in terms of two different objects. During a collision with object A and B, A will be pushed in the opposite direction of B:

(하지만 우리는 j가 두 개의 각각 다른 물체의 관점에서 표현할 수 있어야 한다. 물체 A와 B의 충돌 도중 A는 B의 반대방향으로 밀려날 것이다.)

Equation 8

 

 

These two equations will push A away from B along the direction unit vector n by impulse scalar (magnitude of n ) j .

All that is now required is to merge Equations 8 and 5. Our resulting equation will look something like this:

(2개의 공식은 충격 스칼라(규모) j에 의해서 방향을 나타내는 단위 벡터 n에따라 B로부터 A를 밀어낸다 . 공식 8과 5를 결합하는 것이 요구된다)

Equation 9

 

 

 

 

 

If you recall, the original goal was to isolate our magnitude. This is because we know what direction to resolve the collision in (assumed given by the collision detection), and only have left to solve the magnitude of this direction. The magnitude which is an unknown in our case is j ; we must isolate j and solve for it.

(만약 기억한다면 원래 목표는 규모를 구분하려고 한 것이다. 우리는 충돌에서 방향을 해결했고 오직 이 방향의 규모(크기)가 남았다. 그 규모는 J이다. 우리는 이것으로 J를 풀어내야 한다.)

Equation 10

Whew! That was a fair bit of math! It is all over for now though. It's important to notice that in the final version of Equation 10 we have j on the left (our magnitude) and everything on the right is all known. This means we can write a few lines of code to solve for our impulse scalar j . And boy is the code a lot more readable than mathematical notation!

(걍 마지막 공식이고 j값 구할수 있다고 함. 이것은 몇 줄의 코드로 충격 스칼라 j를 구할 수 있다느 뜻이다.)

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

void ResolveCollision( Object A, Object B ) {   // Calculate relative velocity   Vec2 rv = B.velocity - A.velocity     // Calculate relative velocity in terms of the normal direction   float velAlongNormal = DotProduct( rv, normal )     // Do not resolve if velocities are separating   if(velAlongNormal > 0)     return;     // Calculate restitution   float e = min( A.restitution, B.restitution)     // Calculate impulse scalar   float j = -(1 + e) * velAlongNormal   j /= 1 / A.mass + 1 / B.mass     // Apply impulse   Vec2 impulse = j * normal   A.velocity -= 1 / A.mass * impulse   B.velocity += 1 / B.mass * impulse }

There are a few key things to note in the above code sample. The first thing is the check on Line 10, if(VelAlongNormal > 0). This check is very important; it makes sure that you only resolve a collision if the objects are moving towards each other.

(10번쨰 줄에 if(VelAlongNormal > 0)는 매우 중요하다고 함. 이것을 확실히 해야 서로의 물체가 움직인다고 함)

 

Two objects collide, but velocity will separate them next frame. Do not resolve this type of collision.

If objects are moving away from one another we want to do nothing. This will prevent objects that shouldn't actually be considered colliding from resolving away from one another. This is important for creating a simulation that follows human intuition on what should happen during object interaction.

(물체들이 다른 것에서 움직여질 때 우리가 아무것도 하지 않기를 원하면. 이것은 물체들을 다른 것으로부터 해결하는 것에서 충돌을 실제로 고려하지 않도록 막아야한다. 이것은 사람의 직관에 따른 물체 상호작용 중에 시뮬레이션 제작에 중요하다)

(먼소리인지 모르겠다 ㅂㄷㅂㄷ)

The second thing to note is that inverse mass is computed multiple times for no reason. It is best to just store your inverse mass within each object and pre-compute it one time:

(여러번 질량의 역을 구하지 말고 변수로 한번 저장해놓으라는 것)

1	A.inv_mass = 1 / A.mass

Many physics engines do not actually store raw mass. Physics engines often times store inverse mass and inverse mass alone. It just so happens that most math involving mass is in the form of 1/mass.

(많은 물리엔진은 실제로 질량 그대로 저장하지 않는다. 보통 물리엔진은 질량의 역을 저장하거나 질량의 역만 저장한다. 거의 대부분 1/질량 형태로 진행된다는 듯)

The last thing to note is that we intelligently distribute our impulse scalar j over the two objects. We want small objects to bounce off of big objects with a large portion of j , and the big objects to have their velocities modified by a very small portion of j .

In order to do this you could do:

(마지막으로 주목해야할 것은 우리는 두 오브젝트에 충격 스칼라 j를 두 물체에 넣어줘야한다. 우리는 작은 물체들은 큰 물체들의 큰 J값으로 인해 팅겨나가야한다. 그리고 큰 물체는 그들의 속도들을 작은 물체들의 j값에 의해 수정되어야한다.) 

1 2 3 4 5 6

float mass_sum = A.mass + B.mass float ratio = A.mass / mass_sum A.velocity -= ratio * impulse   ratio = B.mass / mass_sum B.velocity += ratio * impulse

It is important to realize that the above code is equivalent to the ResolveCollision() sample function from before. Like stated before, inverse masses are quite useful in a physics engine.

(ResolveCollision() 샘플 함수와 동일하게 중요하다는듯? 질량의 역은 매우 유용하게 물리엔진에서 사용된다고 함)

내려가는(중력) 물체들(Sinking Objects)

If we go ahead and use the code we have so far, objects will run into each other and bounce off. This is great, although what happens if one of the objects has infinite mass? Well we need a good way to represent infinite mass within our simulation.

I suggest using zero as infinite mass - although if we try to compute inverse mass of an object with zero we will have a division by

zero. The workaround to this is to do the following when computing inverse mass:

(무한한 질량을 0으로 사용할 것을 제한한다 하지만 질량이 0인 값의의 역을 구하려고 하면 분모가 0이 되기때문에 아래처럼 쓰라는 말인듯)

1 2 3 4

if(A.mass == 0)   A.inv_mass = 0 else   A.inv_mass = 1 / A.mass

A value of zero will result in proper calculations during impulse resolution. This is still okay. The problem of sinking objects arises when something starts sinking into another object due to gravity. Perhaps something with low restitution hits a wall with infinite mass and begins to sink.

(0은 충돌 계산 할때 올바른 계산을 하여 결과를 보여줄 것이다. 문제는 무언가가 중력으로 내려갈 때 내려가는 또 다른 물체들에게 일어난다. 어쩌면 무언가가 작은 반발로 무한한 질량의 벽과 부딪쳐 내려가기 시작한다) 

This sinking is due to floating point errors. During each floating point calculation a small floating point error is introduced due to hardware. (For more information, Google [Floating point error IEEE754].) Over time this error accumulates in positional error, causing objects to sink into one another.

(이 가라앉음에는 부동소수점으로 인해 에러가 있다. 각각의 부동소수점 계산동안 하드웨어로 인해 작은 부동소수점 오류가 생긴다.(자세히 알고 싶으면 구글에 Floating point error IEEE754을 쳐보라고 한다.) 이 에러가 위치적인 에러가 축적되면서 다른 것에도 영향을 미친다.)

In order to correct this error it must be accounted for. To correct this positional error I will show you a method called linear projection. Linear projection reduces the penetration of two objects by a small percentage, and this is performed after the impulse is applied. Positional correction is very simple: move each object along the collision normal n by a percentage of the penetration depth:

(이 위치 에러를 보정하기 위해서 선형 투영(linear projection) 메소드를 하나 보여주겠다. 선형 투영(linear projection)은 충격을 적용한 뒤 두물체의 침투현상을 막아준다. 위치확인은 간단하다 침투 깊이의 퍼센트로 각각 물체의 충돌 노말 n에 따라 물체를 이동시킨다)

1 2 3 4 5 6 7

void PositionalCorrection( Object A, Object B ) {   const float percent = 0.2 // usually 20% to 80%   Vec2 correction = penetrationDepth / (A.inv_mass + B.inv_mass)) * percent * n   A.position -= A.inv_mass * correction   B.position += B.inv_mass * correction }

Note that we scale the penetrationDepth by the total mass of the system. This will give a positional correction proportional to how much mass we are dealing with. Small objects push away faster than heavier objects.

(penetrationDepth의 크기에 주목하라.이것은 정확한 위치를 얼마의 질량에 비례해서 구해야하는지 알려줄 것이다. 작은 물체들은 무거운 물체들보다 빠르게 움직인다.)

There is a slight problem with this implementation: if we are always resolving our positional error then objects will jitter back and forth while they rest upon one another. In order to prevent this some slack must be given. We only perform positional correction if the penetration is above some arbitrary threshold, referred to as "slop":

(여기에는 약간의 문제가 있다. 우리가 위치 오류를 해결할때 가만히 있는 또 다른 것들이 흔들릴 것이다. 우리는 임의의 값인 침투에 의한 위치 교정만을 해주고 있다. 이것을 slop이라고 부른다.)

1 2 3 4 5 6 7 8

void PositionalCorrection( Object A, Object B ) {   const float percent = 0.2 // usually 20% to 80%   const float slop = 0.01 // usually 0.01 to 0.1   Vec2 correction = max( penetration - k_slop, 0.0f ) / (A.inv_mass + B.inv_mass)) * percent * n   A.position -= A.inv_mass * correction   B.position += B.inv_mass * correction }

This allows objects to penetrate ever so slightly without the position correction kicking in.

(이것은 부딪칠때 약간의 관통을 허용해주는 것이다)

---

간단한 다양체 변환(Simple Manifold Generation)

The last topic to cover in this article is simple manifold generation. A manifold in mathematical terms is something along the lines of "a collection of points that represents an area in space". However, when I refer to the term manifold I am referring to a small object that contains information about a collision between two objects.

(마지막 주제는 간단한 다양체(manifold) 전환이다. 다양체는 수학에서 "공간에서 구역을 나타내는 점들의 집합"라고 할 수 있다.(잘 모르겠으면 '다양체'로 검색), 하지만 내가 다양체(manifold)라고 말할 때는 나는 두 물체 사이에 충돌 정보가 포함되어있는 작은 물체를 이야기한다.)

Here is a typical manifold setup:

(종합적인 다양체 셋업)

1 2 3 4 5 6 7

struct Manifold {   Object *A;   Object *B;   float penetration;   Vec2 normal; };

During collision detection, both penetration and the collision normal should be computed. In order to find this info the original collision detection algorithms from the top of this article must be extended.

(충돌 감지를 하는 동안 양 쪽 모두 침투와 충돌 노멀값은 계산되어 있어야 한다. 이것을 찾기 위해서는 이 글의 상단의 원래의 충돌 감지 알고리즘은 확장되어야 한다)

원 vs 원 (Circle vs Circle)

Lets start with the simplest collision algorithm: Circle vs Circle. This test is mostly trivial. Can you imagine what the direction to resolve the collision will be in? It is the vector from Circle A to Circle B. This can be obtained by subtracting B's position from A's.

Penetration depth is related to the Circles' radii and distance from one another. The overlap of the Circles can be computed by subtracting the summed radii by the distance from each object.

(간단한 충돌 알고리즘을 시작하자 : 원 대 원. 이 테스트는 매우 별거 아니다. 충돌일 때 어떤 방향으로 갈지 상상이 되는가? 원 A 에서 원 B로의 벡터이다. 이건은 B의 포지션을 A포지션으로 부터 빼는 것으로 얻을 수 있다.(글에서는 A-B하라고 되어있는데 말이 안됨) 침투 깊이는 원의 반지름과 서로의 거리에 관련되어 있다. 각 원의 반지름의 합을 두 원의 거리로 뺀다 (요약 : (두 원의 반지름의 합)-(A의 중심과 B 중심의 거리)))

Here is a full sample algorithm for generating the manifold of a Circle vs Circle collision:

(샘플 알고리즘, 원 vs 원 충돌)

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

bool CirclevsCircle( Manifold *m ) {   // Setup a couple pointers to each object   Object *A = m->A;   Object *B = m->B;     // Vector from A to B   Vec2 n = B->pos - A->pos     float r = A->radius + B->radius   r *= r     if(n.LengthSquared( ) > r)     return false     // Circles have collided, now compute manifold   float d = n.Length( ) // perform actual sqrt     // If distance between circles is not zero   if(d != 0)   {     // Distance is difference between radius and distance     m->penetration = r - d       // Utilize our d since we performed sqrt on it already within Length( )     // Points from A to B, and is a unit vector     c->normal = t / d     return true   }     // Circles are on same position   else   {     // Choose random (but consistent) values     c->penetration = A->radius     c->normal = Vec( 1, 0 )     return true   } }

The most notable things here are: we do not perform any square roots until necessary (objects are found to be colliding), and we check to make sure the circles are not on the same exact position. If they are on the same position our distance would be zero, and we must avoid division by zero when we compute t / d.

(여기 가장 중요한 점이 있다. 원들이 같은 위치에 있는지 확실히 확인하여 이때는 제곱근을 구하지 않는다. 만약 같은 위치에 있으면 거리는 0이 될것이고 t/d를 계산할 때 0으로 나누게 된다.)

AABB vs AABB

The AABB to AABB test is a little more complex than Circle vs Circle. The collision normal will not be the vector from A to B, but will be a face normal. An AABB is a box with four faces. Each face has a normal. This normal represents a unit vector that is perpendicular to the face.

(AABB 테스트는 원 vs 원보다 조금 더 복잡하다. 충돌 노멀은 A에서의 B의 벡터가 되지 않고 면의 노멀이 된다. AABB는 4개의 면을 가지고 있다. 각각의 면은 노멀을 가지고 있다. 이 노멀은 면의 수직의 단위벡터이다.)

Examine the general equation of a line in 2D:

(2D에서의 일반적인 식)

 

 

In the above equation, a and b are the normal vector for a line, and the vector (a, b) is assumed to be normalized (length of vector is zero). Again, our collision normal (direction to resolve the collision) will be in the direction of one of the face normal.

(위 식에서 a와 b는 직선의 노벌 벡터이고 벡터(a,b)는 정규화로 구할 수 있다. 다시 충돌 노멀은 면의 노멀의 방향이 될것이다.)

Do you know what c represents in the general equation of a line? c is the distance from the origin. This is very useful for testing to see if a point is on one side of a line or another, as you will see in the next article.

(당신은 직선의 일반식에서 c가 무엇을 표현하는지 아는가? c는 중심으로부터의 거리이다. 이것은 다음 글에 보게 될 것이지만 직선의 옆에 점이 있는지 또는 다른 것을 확인하기에 매우 유용하다.

Now all that is needed is to find out which face is colliding on one of the objects with the other object, and we have our normal. However sometimes multiple faces of two AABBs can intersect, such as when two corners intersect each other. This means we must find the axis of least penetration.

(이제 물체의 어떤 면이 충돌하는지 찾아야 한다. 하지만 때때로 서로의 모서리가 겹칠 때 2개의 AABB들의 여러 면의 겹치게 된다. 이것은 우리가 반드시 최소 침투의 축을 구해야한다는 것을 의미한다.)

 

<figcaption>Two axes of penetration; the horizontal x axis is axis of least penetration and this collision should be resolved along the x axis.(침투의 2개의 축. 수평 x 축이 최소 침투이고(수직 y축에 비해 작음) 이 x축으로 충돌을 해결하는데 쓴다)</figcaption>

 

 

 

 

 

 

 

Here is a full algorithm for AABB to AABB manifold generation and collision detection:

(여기 AABB 다형체 변환과 충돌 감지의 풀 알고리즘이 있다)

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

bool AABBvsAABB( Manifold *m ) {   // Setup a couple pointers to each object   Object *A = m->A   Object *B = m->B      // Vector from A to B   Vec2 n = B->pos - A->pos      AABB abox = A->aabb   AABB bbox = B->aabb      // Calculate half extents along x axis for each object   float a_extent = (abox.max.x - abox.min.x) / 2   float b_extent = (bbox.max.x - bbox.min.x) / 2      // Calculate overlap on x axis   float x_overlap = a_extent + b_extent - abs( n.x )      // SAT test on x axis   if(x_overlap > 0)   {     // Calculate half extents along x axis for each object     float a_extent = (abox.max.y - abox.min.y) / 2     float b_extent = (bbox.max.y - bbox.min.y) / 2        // Calculate overlap on y axis     float y_overlap = a_extent + b_extent - abs( n.y )        // SAT test on y axis     if(y_overlap > 0)     {       // Find out which axis is axis of least penetration       if(x_overlap > y_overlap)       {         // Point towards B knowing that n points from A to B         if(n.x < 0)           m->normal = Vec2( -1, 0 )         else           m->normal = Vec2( 0, 0 )         m->penetration = x_overlap         return true       }       else       {         // Point toward B knowing that n points from A to B         if(n.y < 0)           m->normal = Vec2( 0, -1 )         else           m->normal = Vec2( 0, 1 )         m->penetration = y_overlap         return true       }     }   } }

 

원 vs AABB(Circle vs AABB)

The last test I will cover is the Circle vs AABB test. The idea here is to compute the closest point on the AABB to the Circle; from there the test devolves into something similar to the Circle vs Circle test. Once the closest point is computed and a collision is detected the normal is the direction of the closest point to the circle's center. The penetration depth is the difference between the distance of the closest point to the circle and the radius of the circle.

(원 vs AABB는 마지막 파트이다. AABB에서 원의 가장 가까운 점을 계산한다. 원 vs 원 충돌과 어떤 것은 비슷하다. 가장 가까운 점이 계산되었고 원의 중심에서 가장 가까운 점까지의 방향인 노멀이 충돌 감지된다. 여기서 침투 깊이는 가장까운 점과 원의 반지름의 거리이다.) 

AABB to Circle intersection diagram.

There is one tricky special case; if the circle's center is within the AABB then the center of the circle needs to be clipped to the closest edge of the AABB, and the normal needs to be flipped.

(여기 교묘하고 특별한 경우가 있다. 만약 원의 중심이 AABB안에 있으면 원의 중심은 가장 가까운 AABB의 꼭지점으로 잘려야하고 노멀은 뒤집어 준다.)

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

bool AABBvsCircle( Manifold *m ) {   // Setup a couple pointers to each object   Object *A = m->A   Object *B = m->B     // Vector from A to B   Vec2 n = B->pos - A->pos     // Closest point on A to center of B   Vec2 closest = n     // Calculate half extents along each axis   float x_extent = (A->aabb.max.x - A->aabb.min.x) / 2   float y_extent = (A->aabb.max.y - A->aabb.min.y) / 2     // Clamp point to edges of the AABB   closest.x = Clamp( -x_extent, x_extent, closest.x )   closest.y = Clamp( -y_extent, y_extent, closest.y )     bool inside = false     // Circle is inside the AABB, so we need to clamp the circle's center   // to the closest edge   if(n == closest)   {     inside = true       // Find closest axis     if(abs( n.x ) > abs( n.y ))     {       // Clamp to closest extent       if(closest.x > 0)         closest.x = x_extent       else         closest.x = -x_extent     }       // y axis is shorter     else     {       // Clamp to closest extent       if(closest.y > 0)         closest.y = y_extent       else         closest.y = -y_extent     }   }     Vec2 normal = n - closest   real d = normal.LengthSquared( )   real r = B->radius     // Early out of the radius is shorter than distance to closest point and   // Circle not inside the AABB   if(d > r * r && !inside)     return false     // Avoided sqrt until we needed   d = sqrt( d )     // Collision normal needs to be flipped to point outside if circle was   // inside the AABB   if(inside)   {     m->normal = -n     m->penetration = r - d   }   else   {     m->normal = n     m->penetration = r - d   }     return true }

---

결론(Conclusion)

Hopefully by now you've learned a thing or two about physics simulation. This tutorial is enough to let you set up a simple custom physics engine made entirely from scratch. In the next part, we will be covering all the necessary extensions that all physics engines require, including:

(걍 이런거 배웠고 다음 글에서 아래것들 배운다는 의미)

• Contact pair sorting and culling
• Broadphase
• Layering
• Integration
• Timestepping
• Halfspace intersection
• Modular design (materials, mass and forces)

I hope you enjoyed this article and I look forward to answering questions in the comments.

 

---------------------------------------------------------------------------------------------

번역 다했는데 날아가서 다시 번역함...

분명히 저장을 몇번씩 했는데...

네이버 블로그의 글 저장 기능 더이상은 안믿음..

(네이버 블로그 - 2016.01.05. 01:37)