Hybrid narrow phase using convexity detection

While writing Convex polygon based collision detection I came up with the idea of using a hybrid narrow phase to maximize usability and performance. It might have been thought of before and if you stumble upon this, I would like to hear your thoughts about it.

It basically consist of taking the pairs found in the broad phase and checking the convexity of the polygons before sending them down to the narrow phase. As I described in the earlier post, SAT only works on convex polygons because it uses the separating axis between two non-colliding convex polygons. This limits the users of the engine to use convex polygons only and thus resort to methods of convex decomposition to get concave polygon support.

If the polygons were checked for their convexity before being send to the narrow phase, the engine could send the pair of potentially colliding polygons to a narrow phase of its choice - depending on the composition of the pair:

  • Convex vs. concave – Send to concave narrow phase
  • Convex vs. convex – Send to convex narrow phase
  • Concave vs. concave – Send to concave narrow phase

The convexity check could even be done at tool-time or engine startup. Whenever the vertices of an object changes it needs to redo the convexity check.

Problems that it would solve:

Small angles

Some triangulation algorithms try to maximize the minimum angle of the triangles (like Delaunay Triangulation). But most will come up with a result that contains narrow triangle and thus it can cause tunneling problems.

Convex seems

Composing a concave polygon from several convex polygons will create a lot of seems (part where the polygons meet) and that can cause trouble for most 2D physics engines. Unrealistic collisions and hiccups can occur in the middle of a collision.

Holes

Because of the precision and accuracy of algorithms (due to iterative nature and float errors) – cases of no-intersection can happen when an intersection is expected. Imagine two narrow triangles where the narrow part are up against each other. A small gap can exist between the triangles and a ray cast in between the two triangles would go right though it. This can of course be solved by extending the edges a little.

Problems that it would create:

Memory issue

The main issue would be memory consumption. Instead of a single narrow phase algorithm you would now have a dual algorithm. Using a narrow phase collider like the Signed Distance Field can consume a lot of memory.

Expensive to change polygons

Again, if you use a narrow phase collider like the SDF you need to recalculate both the convexity check and the cached grid containing the narrow phase data for the physics object. Most games don’t change polygons on the fly, so this should not be a major issue.

Comments

Post a Comment

Popular posts from this blog

.NET Compression Libraries Benchmark

Image
I often find myself needing a compression library in a software development project, and after a few tests with disappointing results I usually fall back to spawning 7Zip as an external process. This time however, the application specification prohibits any data written to disk, which 7Zip needs to do in order to work correctly. I needed to do everything in memory, and so I had to test some of the C# libraries available for compression as well as the different compression algorithms. Here is a full list of the tested libraries: .NET DeflateStream ICSharpCode SharpZip Zlib.NET DotNetZip Managed LZMA LZMA SDK QuickLZ    Compression 101 Before I get to the results of the benchmark, I think it is important to understand the different archive formats and compression algorithms in order to compare the results with other benchmarks/and or tests. Lets get to it! A compression algorithm can be compared to a small machine that takes in some data, do some math on it and transfor
Read more

Reducing the size of self-contained .NET Core applications

Just for note keeping, I've written down some methods of reducing the size of a .NET Core application. I thought others could use it as well, so here you go. Original Size First off, let's see how much disk space a self-contained 'hello world' application takes up. > dotnet new console > dotnet publish -r win-x86 -c release Size: 53.9 MB -  yuck! Trimming Microsoft has built a tool that finds unused assemblies and removes them from the distribution package. This is much needed since the 'netcoreapp2.0' profile is basically .NET Framework all over again, and it contains a truckload of assemblies our little 'hello world' application don't use. > dotnet new console > dotnet add package Microsoft.Packaging.Tools.Trimming -v 1.1.0-preview1-25818-01 > dotnet publish -r win-x86 -c release /p:TrimUnusedDependencies=true Size: 15.8 MB Much better! Although, we have only removed unused assemblies - what about unused
Read more

Convex polygon based collision detection

Image
A lot of people have asked me: Why use a convex polygon only engine like Box2D? In this post I will provide some info on why convex polygons is the optimal polygon type to use. What does convex mean? Convex polygons needs to satisfy the following requirements: All internal angles must be below 180 degrees Every line segment between two vertices can be contained fully inside or at the edge the polygon A non-convex polygon is called a concave polygon and it must have an internal angle measuring greater than 180 degrees. As you might have thought about yourself; concave polygons can be quite handy. Convex-only engines can’t represent a simple player polygon like Pac-Man . Why use convex-only? There are really only one big juicy reason: performance Physics engines are able to take quite a few shortcuts and use cheap algorithms to determine the closest vertex, shortest distance and a lot more. An algorithm like Separating Axis Theorem and the Gilbert – Johnson –
Read more