Circle Collision

Implementing Different Methods of Circle to Circle Collision Detection using Vulkan Graphics and Compute API

Circles were chosen to focus more on Broad-Phase algorithms of the Collision Detection Pipeline.

Images and Preview

Charts and Plots

Motivation

This Project Is For Learning Purposes of Following Topics

• SIMD/Vectorization using AVX/AVX2
• Vulkan Compute Shaders and GPGPU Programming
• Data Oriented Programming

Features

• Broad-Phase

  • Brute Force ( O(n^2) )
  • Spatial Partitioning
    • Grid
    • K-D Tree
    • Quadtrees
    • BSP
  • Sort and sweep
  • Simplex-Based : GJK

• Narrow-Phase

  • We Have Circles Here and Math/Physics Calculations are easy.

• Technologies/API's

  • CPU
    • Simple Sequential
    • Multi-Threaded
    • SIMD
      • AVX2
      • AVX-512
  • GPU
    • Vulkan Compute Shaders
    • OpenCL

Implemented

• Brute Force
  • CPU
  • Compute Shader
  • SIMD: AVX2
    • Load/Store Same Simple Data Structure and Calculate
    • All SIMD Data Strcuture
  • Multi-Threaded
  • Multi-Threaded + SIMD
• Spatial Partitioning
  • Grid
    • CPU
    • Multi-Threaded

Build

• Visual Studio 2019
• :soon: Linux Builds Will be Added Soon

Blog

You can here about implementation details soon in my blog, GraphicsCoder

Slides

Presentation Slides

Resources

• SIMD
  • SIMD at Insomniac Games
  • Crunching Numbers with AVX and AVX2
  • Intel Intrinsics Guide
• Spatial Partitioning
  • Game Programming Patterns Book/Spatial Partitioning
• Vulkan and GPU Programming
  • A Simple Vulkan Compute Example
  • Thinking Parallel, Part I: Collision Detection on the GPU
• Circle Collision Handling
  • Circle-Circle Collision Tutorial (Math)
  • Programming Balls #1 Circle Vs Circle Collisions C++ (Fun Video)

:heavy_exclamation_mark: This project is not for benchmarking purposes!, Although It would give me some ideas to be suspicious about.

:heart_decoration: I would appreciate optimization ideas and results on your system on issues.