<p align="center"> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/circle_collision/master/docs/LOGO.png" align="center" alt="" height="200"/> </p> <p align="center"> <img src="https://www.khronos.org/assets/uploads/apis/vulkan2.svg" align="center" alt="" height="40" hspace="20"/> <img src="https://upload.wikimedia.org/wikipedia/commons/c/c9/Intel-logo.svg" align="center" alt="" height="40" hspace="20"/> </p>

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.

<p align="center"> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/circle_collision/master/docs/Collision-detection-pipeline.png" width="372" height="85"/> </p>

Images and Preview

<p align="center"> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/circle_collision/master/docs/heart_collision.jpg" alt="" width="320" height="180" /> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/circle_collision/master/docs/draw-fun.gif" alt="" width="320" height="180" /> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/circle_collision/master/docs/explode_fun.gif" alt="" width="320" height="180" /> </p>

Charts and Plots

<p align="center"> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/CircleCollision/master/docs/Brute%20Force.png"/> <img src="https://raw.githubusercontent.com/Erfan-Ahmadi/CircleCollision/master/docs/Grid%20Spatial%20Partitioning.png"/> </p>

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

<img src="https://raw.githubusercontent.com/Erfan-Ahmadi/circle_collision/master/docs/spatial%20partitioning.PNG" alt="" />

Implemented

• Brute Force
  • [x] CPU
  • [x] Compute Shader
  • [x] SIMD: AVX2
    • [x] Load/Store Same Simple Data Structure and Calculate
    • [x] All SIMD Data Strcuture
  • [x] Multi-Threaded
  • [x] Multi-Threaded + SIMD
• Spatial Partitioning
  • Grid
    • [x] CPU
    • [x] 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.