Writing a Physics Engine from scratch - collision detection optimization

Summary

Verlet積分は、シンプルな物理シミュレーションを簡単に行うための優れたツールです。このビデオでは、衝突判定の性能を大幅に向上させるシンプルな方法を紹介しています。オブジェクトが重なるのを最小化するために、空間分割やマルチスレッド処理を使用し、数千個のオブジェクトを効率的にシミュレートします。結果として、固定グリッドによる衝突判定とマルチスレッド処理により、大規模なシミュレーションでも高いパフォーマンスを維持できます。さらに、シミュレーションは決定論的であり、同じ初期状態から常に同じ結果が得られる点も強調しています。

Takeaways

• 👍 Verlet統合は、シンプルな物理相互作用を簡単にシミュレートする素晴らしいツールです。
• 📽️ 動画では、基本的な物理エンジンを作成するためのシンプルなアルゴリズムを使用しました。
• ⚡ ナイーブなアルゴリズムは少数のオブジェクトでのみ動作しますが、より多くのオブジェクトをシミュレートする方法を紹介します。
• 🔍 オブジェクト間の重なりを最小限にすることがシミュレーションの目標です。
• 📏 重なりは、オブジェクトの中心間の距離を半径の合計から引いて計算されます。
• 🔄 重なりを減らすために、オブジェクトを少しずつ移動させます。
• 🔧 サブステップを使用して重なりを最小限にすることで、シミュレーションのパフォーマンスを向上させます。
• 🗺️ 空間分割の概念を導入することで、衝突チェックの数を大幅に減らします。
• 🧵 複数のスレッドを使用して、シミュレーションのパフォーマンスをさらに向上させます。
• 🎨 データ競合を回避するために、スレッドゾーンを2つに分割し、衝突を2回に分けて解決します。

Q & A

Verlet Integrationとは何ですか？

Verlet Integrationは、簡単な物理相互作用をシミュレートするための優れたツールです。

動画で示された衝突検出の方法は何ですか？

動画では、物体間の距離がそれぞれの半径の合計より小さい場合に重なりが発生することを利用したナイーブなアルゴリズムが使用されています。

シミュレーションのパフォーマンスを向上させるための方法は何ですか？

シミュレーションのパフォーマンスを向上させるためには、空間分割の概念を導入し、固定グリッドを使用することが有効です。

固定グリッドの使用方法はどのように説明されていますか？

固定グリッドでは、シミュレーションの空間を正方形のセルに分割し、各オブジェクトのインデックスをセルに追加します。

衝突検出のためのナイーブな方法の問題点は何ですか？

ナイーブな方法では、オブジェクトの数が二乗に比例してチェックが必要なため、非常に遅くなります。

固定グリッドを使用することの利点は何ですか？

固定グリッドを使用することで、非常に遠く離れたオブジェクト間の無駄なチェックを大幅に削減できます。

サブステップを使用する利点は何ですか？

サブステップを使用することで、物理フレーム間のオブジェクトの移動を小さくし、オーバーラップを最小限に抑えることができます。

マルチスレッド化の目的は何ですか？

マルチスレッド化の目的は、複数のスレッドを使用して計算を高速化し、衝突検出のパフォーマンスを向上させることです。

データレースの問題を解決する方法は何ですか？

データレースの問題を解決するために、各スレッドのゾーンを2つに分け、2回のパスで衝突を解決します。

シミュレーションが決定論的であることの利点は何ですか？

シミュレーションが決定論的であることで、特定の初期状態が常に同じ結果を生み出し、シミュレーションの再現性が保証されます。

Outlines

00:00

🛠️ Verlet Integrationと簡単な物理シミュレーション

Verlet Integrationはシンプルな物理シミュレーションを簡単に行うための優れたツールです。基本的な物理エンジンのデモで、衝突検出には単純なアルゴリズムを使用しましたが、これでは数千個のオブジェクトしか処理できません。そこで、シミュレーションのパフォーマンスを大幅に向上させる方法を紹介します。重なりを最小限に抑えるために、オブジェクトの中心間の距離が半径の合計より小さい場合、それらを移動させて重なりを解消します。この技術を用いて、多数のオブジェクトのシミュレーションを行い、適切なサブステップ数で物理ソルバーを高速に動作させます。

05:36

⚙️ 固定グリッドと衝突検出の効率化

従来の衝突検出方法は非効率的で、多くの無駄なチェックが含まれています。空間分割を導入することで、衝突検出の効率を大幅に向上させることができます。固定グリッドを使用し、オブジェクトの半径に基づいてセルを設定します。各オブジェクトをグリッドに追加し、セル内と周囲のセルのオブジェクト間の距離を計算します。この方法により、シミュレーションのオブジェクト数を大幅に増やすことが可能になります。また、決定論的シミュレーションの特性を活かし、初期状態が常に同じ結果を生むことを示します。

10:38

🔀 マルチスレッドによるシミュレーションの高速化

シミュレーションのパフォーマンスをさらに向上させるために、マルチスレッドを活用します。固定グリッドの衝突検出は依然として時間がかかるため、グリッドを複数のパートに分割し、それぞれのパートにスレッドを割り当てます。10スレッドを使用した場合のパフォーマンスを確認します。フリクションを考慮しないため、オブジェクトが流体のように振る舞うことがあります。データレースの問題を解決するために、各スレッドゾーンを2つに分けて衝突を2回に分けて解決し、シミュレーションを再実行します。

Keywords

💡Verlet Integration

Verlet積分は、シンプルな物理的相互作用を簡単にシミュレートするための優れた手法です。ビデオ内では、基本的な物理エンジンを作成する際に使用されており、特定の初期状態が常に同じ結果を生成する決定論的なシミュレーションの基盤となっています。

💡衝突検出

物体同士が接触するかどうかを判定するプロセスです。動画では、オブジェクト間の距離をチェックし、接触している場合はそれらを分離するアルゴリズムについて説明しています。シミュレーションの効率を向上させるために空間分割を利用する方法が紹介されています。

💡空間分割

シミュレーション空間を小さなセルに分割する技術です。これにより、遠く離れたオブジェクト間の無駄なチェックを減らし、衝突検出の効率を大幅に向上させることができます。ビデオでは固定グリッドを用いて説明されています。

💡サブステップ

シミュレーション内の物理的なフレーム間でオブジェクトの移動量を小さくするための技術です。ビデオでは、サブステップを8回使用することで、シミュレーションを480Hzで実行し、重なりを最小限に抑える方法が紹介されています。

💡決定論的シミュレーション

特定の初期状態が常に同じ結果を生み出すシミュレーションの特性です。ビデオでは、初期状態を再現し、オブジェクトに色を設定して再度シミュレーションを実行することで、画像を生成する方法が示されています。

💡マルチスレッド

複数のスレッドを使用して計算を並列化する技術です。ビデオでは、グリッドをいくつかの部分に分割し、各部分にスレッドを割り当てることで衝突検出のパフォーマンスを向上させる方法が説明されています。

💡固定グリッド

シミュレーション空間を固定サイズのセルに分割する構造です。ビデオでは、各セルにオブジェクトを追加し、隣接するセルとの間で距離を計算して衝突を検出する方法が示されています。

💡オーバーラップ

オブジェクトが重なっている状態を指します。ビデオでは、オーバーラップを最小限にするために、距離を計算してオブジェクトを分離する方法が説明されています。

💡データ競合

複数のスレッドが同じデータに同時にアクセスして競合する問題です。ビデオでは、スレッドのゾーンを2つに分け、衝突を2回に分けて処理することでこの問題を解決する方法が示されています。

💡摩擦

オブジェクト間の動きに抵抗を与える力です。ビデオでは、シンプルなソルバーでは摩擦が考慮されていないため、オブジェクトが流体のように振る舞うことがあると説明されています。

Highlights

Verlet Integration is a fantastic tool to easily simulate simple physic interactions.

Naive algorithm to find collisions between objects can handle a few thousand objects at a reasonable framerate.

Improving performance of the simulation by minimizing overlaps between objects.

Overlap value is computed by subtracting the distance between the objects from the sum of their radius.

Moving objects along the axis defined by their centers by half the overlap.

Using multiple iterations or sub steps to minimize overlaps, with 8 sub steps resulting in 480Hz physics solver.

Naive algorithm for detecting overlaps is slow due to the number of checks being equal to the number of objects squared.

Introducing space partitioning with a fixed grid to reduce the number of collision checks.

Dividing simulation space into square cells and adding objects into the grid based on their center.

Iterating on all cells and computing distances between objects in the current cell and surrounding cells.

Improving performance of the algorithm allows the simulation to handle around 16 times more objects.

Deterministic simulations ensure specific initial states always produce the same results.

Animating the creation of an image by assigning colors to objects based on their final positions in the simulation.

Using multithreading to improve solver performance by dividing the grid and assigning threads to different parts.

Handling more than 100K objects and generating a high-definition image with the improved solver.

Fixing data races in multithreaded zones by separating thread zones and solving collisions in two passes.

Achieving a deterministic multithreaded basic physic solver with improved performance.

Transcripts

Verlet Integration is a fantastic tool to easily simulate simple physic interactions.

In the video I did to demonstrate how easy it is to create a very basic physic engine,

I used a naive algorithm to find collisions between objects.

This allowed to handle a few thousands objects at a reasonable framerate but what if we want

to simulate way more?

In this video I will present a simple way to greatly improve the performance of the

simulation.

This is the technic I use in all my projects involving physics be it Verlet integration

or impulse based solvers.

The aim of the simulation is to minimize the overlaps between objects.

Two objects overlap if the distance between their centers is smaller than the sum of their

radius.

The value of the overlap is computed by subtracting the distance between the objects from the

sum of their radius.

Then, we move them along the axis defined by their centers.

Each object is moved half the overlap.

Here is an illustration of this principle applied to multiple objects.

In this example the initial overlaps were quite important, a single iteration is not

sufficient to fix them.

We can either perform multiple iterations that will iteratively improve the situation

or we can try to minimize these overlaps in the first place by using sub steps, resulting

in much smaller objects movements between physics frames and thus much smaller overlaps.

All the simulations of this video will be using 8 sub steps, meaning that the physics

solver will run at 480Hz.

This is how I enable sub stepping in my code

The naive way of detecting overlaps is to iterate on all objects and for each of them

to iterate on all the others, check the distance and move them apart if they're too close.

While valid, this algorithm is very slow because the number of checks to perform is equal to

the number of objects squared.

This algorithm could be written like this:

Let's run a simulation where we continuously add objects and stop it as soon as the framerate

drops under 60 fps and see how much objects it can handle this way.

As you can see the simulation can only handle a few objects.

What's really inefficient with this approach is that we perform a lot of useless checks

between objects that are very far away.

In order to vastly reduce the number of collision checks, we have to introduce the notion of

space partitioning.

One of the simplest structure is the fixed grid.

The simulation's space is divided in square cells.

For maximum performance I will use objects all having the same radius and set the cells

size to objects diameter.

First, we have to add the objects into the grid.

To do so, each object's index is added into the cell above which its center is.

At the end of the process, each cell stores the list of its contained objects.

Then, to find collisions we iterate on all the cells and compute the distances between

all the current cell's objects and the ones associated to the surrounding cells.

To remove any boundaries check we don't iterate on the cells on the border.

This algorithm could be written like this:

Let's run the simulation again and see how much objects this new algorithm can handle.

It's already much better, the simulation can now handle around 16 times more objects.

We can improve performance further as we will see later but now that we can run bigger simulations

we can have some fun taking advantage of a very powerful characteristic of these simulations:

they are deterministic.

This means that a specific initial state will always produce the same results when the simulation

is executed on it.

Here is an example to illustrate this:

With more objects we can animate the creation of an image.

To do so, we execute the simulation a first time, see where each object lands on the picture

and assign them the color of the underlying pixel.

Then, we re run the simulation with the objects having their color set.

Since the simulation will always produce the same result, all the objects will return to

their previous places with the right colors

Thanks to modern hardware we have a lot of cores that we can use to speed up our computations.

Let's take advantage of this to improve the performance of our solver even further.

Even if we drastically improved the collisions detection stage of our simulation using a

fixed grid, it's still the most time consuming part of the solver.

One straightforward way of multithreading the simulation is to split the collisions

detection by dividing the grid in several parts and assign each one a thread.

With two threads it would look like that:

Let's check the performance with 10 threads:

As you may have noticed, the objects are sometimes acting a bit like a fluid.

This is because friction is not taken into account in this very simple solver.

Using multithreading we multiplied the number of objects by 5.

Now that we have more than 100K objects, let's try to generate a high definition chicken!

We run the simulation a first time, set the colors of objects, and run it again, as before.

It seems that we got a very nice KFC chicken but that's not exactly what we wanted.

The problem here is that data races occur when multiple threads are working on the same

cells at the boundaries of their zones.

To fix this, we separate each thread zone is two and solve collisions in two passes,

ensuring that no cells are being processed by two threads at the same time.

With this change implemented, let's run the simulation again and see if it works.

This is much better!

And that's it, we now have a deterministic multithreaded basic physic solver!