# CollisionAnimation

**Repository Path**: SouthernHermit/collision-animation

## Basic Information

- **Project Name**: CollisionAnimation
- **Description**: CUDA大规模小球碰撞的实时模拟+OpenGL渲染
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-06-23
- **Last Updated**: 2023-01-31

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 基于GPU的小球碰撞动力学模拟

徐开元   

### 开发测试环境

操作系统：Windows 11

CPU： AMD Ryzen 3900X

GPU： Nvidia RTX 3080

CUDA版本：11.0

nvcc编译的目标平台：sm_52（可在10系及更新的显卡上运行）

### 使用说明

可执行程序为`bin/dynamics.exe`

该程序的功能是随机生成小球，每隔一定的模拟时间步长Δt计算场景内小球的碰撞和运动，并渲染为一帧。该过程使用了基于GPU的碰撞检测与牛顿动力学模拟。

程序使用方法（确保cmd目录为`bin`）：

```
dynamics.exe n_balls max_velocity delta_time
```

n_balls为正整数，即生成小球的数量（位置、半径、初速度随机）；

max_velocity为最大初始速度；

delta_time为模拟的时间步长；

渲染窗口中，可以使用鼠标控制视角，wasd键控制移动。

### 效果示意

在RTX 3080上，使用10万小球，最大初速度5m/s，时间步长0.02s，可以达到大于50fps的帧率。截图：

![1655989832480](readme.assets/1655989832480.png)

### 算法

本程序有两个重点：1）大量小球之间的快速碰撞检测；2）动力学仿真。下面分别介绍。

#### 碰撞检测

碰撞检测使用了经典的基于BVH的算法。众多BVH实现中，Linear BVH（LBVH）适合并行化构造，可以在GPU上高效地构造/遍历。我的实现参考了[1]和[2]，其中[1]提出了一种完全并行化的自底向上LBVH生成算法，[2]在[1]的基础上对树的内部节点根据depth-first遍历顺序重新排序，实现了cache-friendly的访问，大幅提高了GPU的缓存命中率，从而提升性能。

LBVH生成和碰撞检测的代码位于`GPUCD/lbvh`。

#### 物理交互

主要包括小球的牛顿力学运动和非完全弹性碰撞后的速度计算。运动过程中动力学参量的数值计算`Velocity Verlet`积分方法，是半隐式积分方法。

代码位于`GPUCD/physics`。

#### 渲染

使用OpenGL的实例化方法`glDrawElementsInstanced`进行批量绘制，节省draw call与CPU开销。

### 性能分析

由于渲染并未细致优化，下面只统计碰撞检测+物理模拟的开销。统一参数：

最大初始速度5m/s，时间步长0.1s，模拟1000帧取每帧平均耗时。

| 小球数量 | 平均每帧耗时（毫秒） |
| -------- | -------------------- |
| 100      | 1.997                |
| 1000     | 2.086                |
| 10000    | 4.368                |
| 100000   | 29.321               |

耗时大致与小球数量的对数成正比，验证了算法的有效性。

### 参考文献

[1]APETREI C.: Fast and simple agglomerative LBVH construction. In Computer Graphics and Visual Computing (CGVC) (2014), Borgo R., Tang W., (Eds.), The Eurographics Association. 

[2]X. L. Wang: Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring. In Eurographics 2018