代码之家 › 专栏 › 技术社区 › Luecx

减少光线跟踪时的计算

bounding-volume kdtree raytracing intersection

0

Luecx · 技术社区 · 7 年前

我已经编写了自己的3D游戏引擎(花了我一年时间),我想创建一个在我的CPU(而不是GPU)上运行的光线跟踪器

目前,光线跟踪过程简化如下:

为了提高光线跟踪器的速度,我向每个实体添加了一个球形边界框。如果当前光线与边界框相交,它将对实体的每个三角形运行相交测试。

我在射线三角形相交和射线点距离上使用了最快的方法,但每个射线仍然必须测试每个可能相交实体的每个三角形。

因此,我需要5分钟来渲染一个包含大约10000个多边形的对象(1920x1080),我认为这不是我想要的。

你好,芬恩

1 回复 | 直到 6 年前

1

2

Daniel A. Thompson 7 年前

有没有办法减少我需要检查的三角形数量?

听起来你的场景是由一系列三角形组成的,你在列表中线性迭代并检查每个三角形以找到最近的一个。这是线性搜索,具有 O(n)

你可以将其降低到平均值 O(log(n)) 使用时间 volumetric kd-trees bounding volume hierarchies 存储三角形。就个人而言,我更喜欢kd树,但这两种方法都适用。请注意,BVH通常在动画场景中表现更好。

请注意,加速结构在其构造或遍历方式中可能包含微妙的错误,因此您可能希望开发某种方法,使用朴素列表方法(对于参考图像)和结构化方法渲染同一场景。在我的爱好追踪中,我这样组织它:

AbstractScene -所有场景类型的基类。大多数代码只与 抽象场景

KDScene -将场景实现为kd树的派生类。

BVHScene -将场景实现为BVH的派生类。

NaiveScene -将场景实现为三角形列表的派生类。