# mihoyo

**Repository Path**: heguoling/mihoyo

## Basic Information

- **Project Name**: mihoyo
- **Description**: 提高碰撞查询效率的方法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-08-21
- **Last Updated**: 2022-08-24

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 数据结构
1. struct 定义

![structure.png](/Image/structure.png "structure")

2. QuatTree定义
   
![QuatTree.png](/Image/QuatTree.png "QuatTree")

## 计算原理
1. 直线与矩形相交
* 计算矩形四个顶点位置
* 计算射线顶点与矩形顶点的四个向量
* 计算四个向量与射线方向的叉积
* 当四个叉积值均为大于0或小于0时说明直线与矩形不相交

<img src="./Image/linesquare.png" alt="图片替换文本" width="718" height="297" align="center" />

2. 直线与圆形相交
* 计算射线顶点与圆形圆心的向量
* 计算向量与射线方向的叉积
* 叉积值的模长大于圆形半径时，说明直线与圆形不相交

![linecircle.png](/Image/linecircle.png "直线与圆形相交")

3. 相交检测查询
* 插入圆形时，生成四叉树，将节点放到对应叶子节点中
* 查询与直线相交的圆形时，先查找与直线相交的叶子节点（矩形区域）
* 查找到相交的叶子节点后遍历叶子节点中的圆形

4. 圆形绘制原理
* 以极坐标形式生成圆上的坐标
* 圆心与圆上相邻两点绘制triangle
 
![circlecode.png](/Image/circlecode.png "圆形绘制代码")

![circle.png](/Image/circle.png "圆形绘制")

## 渲染优化
1. 将所有的矩形、圆形数据合成两个buffer，只调用两次drawcall从而提高渲染效率
## 运行截图

![runtime.png](/Image/runtime.png "runtime")

## 效果说明
1. 矩形默认颜色随机生成、直线相交时绘制为深蓝色
2. 圆形默认颜色为亮灰色、直线相交时为红色
3. gui可调节直线自动旋转，圆形插入速度，直线坐标、方向、长度，显示查看矩形内圆形数量、相交数量以及与遍历方式查询时间的比较（绿色表示查询时间比遍历查询段短）
   
![gui.png](/Image/gui.png "gui")

## 比较
与遍历的方式对比起来，圆数量较少时，查询消耗的时间可能会大于遍历查询，但是当圆的数量增大到一定程度时，查询时间消耗更短。下图设备中，查询7000多个圆时，消耗的时间（2ms）远小于遍历(10ms)。
![time.png](/Image/time.png "time")