问题标签 [raytracing]

我正在清理我的一个旧项目。它必须做的一件事是——给定一个笛卡尔网格系统，以及网格上的两个正方形，找到连接这两个正方形中心的一条线将通过的所有正方形的列表。

这里的特殊情况是所有起点和终点都被限制在正方形/单元格的确切中心。

这里有一些例子——有成对的样本起点和终点。阴影方块是相应函数调用应返回的方块

删除了无效的 ImageShack 链接 - 示例

起点和终点由它们所在的正方形表示。在上图中，假设左下角是[1,1]，则右下角的线将被标识[6,2]为[9,5]。

即从左起第六列、下第二行的方格（中心）到左起第九列、下起第五行的方格（中心）

这看起来真的没有那么复杂。不过，不知怎么的，我好像在网上找到了一些复杂的算法并实现了。

我记得那是非常非常快的。就像，每帧快速优化了数百或数千次。

基本上，它沿着线（线与网格线相交的点）从正方形的边界跳到边界。它通过查看哪个交叉点更接近（水平的或垂直的）来知道下一个交叉点在哪里，然后移动到下一个交叉点。

这在概念上是可以的，但实际的实现结果并不那么漂亮，而且我担心优化水平可能对我实际需要的东西来说太高了（我称之为遍历算法可能每分钟五六次）。

有没有简单、易懂、透明的直线网格遍历算法？

在程序化方面：

其中给定的坐标标识了正方形本身。

一些例子：

请注意，直接通过拐角的线不应包括线“翼”上的正方形。

（Good ol' Bresenham's 可能在这里工作，但它与我想要的有点倒退。据我所知，为了使用它，我基本上必须将它应用到线上，然后扫描每个正方形真或假的网格。对于大型网格不可行——或者至少不优雅——

（由于我的误解，我正在重新研究 Bresenham 和基于 Bresenham 的算法）

为了澄清起见，一个可能的应用是，如果我将所有对象存储在区域（网格）内的游戏中，并且我有一条射线，并且想查看射线接触到哪些对象。使用这个算法，我可以只测试给定区域内的对象，而不是地图上的每个对象。

在我的应用程序中，它的实际用途是每个图块都有与之关联的效果，并且对象每转都会通过给定的线段。在每一个转弯处，都需要检查对象已经穿过了哪些方格，因此需要对对象应用哪些效果。

请注意，在这一点上，我当前的实现确实有效。这个问题主要是出于好奇的目的。对于这样一个简单的问题，必须有一种更简单的方法......不知何故......

我到底在寻找什么？概念上/整洁干净的东西。另外，我意识到由于我确切指定的内容，所有起点和终点都将始终位于正方形/单元格的中心；所以也许利用这一点的东西也会很整洁。

功能来了 lengthdir_x/y是sin/cos(dir)*dist。不要因为我把 C 标签放在那里而对我大喊大叫。这些语言非常相似，以至于我几乎可以直接复制它。

对，手续已经完成：当前的算法有时会沿对角线运行（其中 x 和 y 在任一符号中都变化一个），但我希望它不要这样做。

EG：
当前：（其中 X 是投射的光线）

通缉：

有道理？

请帮忙。

我正在尝试从Eric Haines 的标准程序数据库 (SPD)中渲染“安装”场景，但折射部分只是不想合作。我已经尝试了我能想到的一切来修复它。

这是我的渲染（使用瓦特公式）：

_{（来源：philosoraptor.co.za）}

这是我使用“正常”公式的渲染：

_{（来源：philosoraptor.co.za）}

这是正确的渲染：

_{（来源：philosoraptor.co.za）}

如您所见，只有几个错误，主要是在球体的两极附近。这让我认为折射或一些精度误差是罪魁祸首。

请注意，场景中实际上有 4 个球体，它们的 NFF 定义 ( s x_coord y_coord z_coord radius) 是：

也就是说，在前景中更明显的三个后面有第四个球体。从这三个球体之间留下的空隙中可以看出。

这是仅第四个球体的图片：

_{（来源：philosoraptor.co.za）}

这是仅第一个球体的图片：

_{（来源：philosoraptor.co.za）}

您会注意到我的版本和正确版本中存在的许多奇怪之处都丢失了。我们可以得出结论，这些影响是球体之间相互作用的结果，问题是哪些相互作用？

我究竟做错了什么？以下是我已经考虑过的一些潜在错误：

• 折射矢量公式。

据我所知，这是正确的。这是几个网站使用的相同公式，我亲自验证了推导。这是我的计算方法：

double sinI2 = eta * eta * (1.0f - cosI * cosI);

transmit = transmit.normalise();

我在 Alan Watt 的第三版 3D Computer Graphics 中找到了一个替代公式。它更接近正确的图像：

唯一的区别是我最后除以 eta^2。

• 全内反射。

我对此进行了测试，在我的其余交集代码之前使用以下条件：

• eta的计算。

我使用类似堆栈的方法来解决这个问题：

如您所见，这将包含此射线的先前对象存储在堆栈中。退出代码时，将当前 IOR 从堆栈中弹出并使用它以及它下面的 IOR 来计算 eta。据我所知，这是最正确的方法。

这适用于嵌套传输对象。但是，它会因相交传输对象而崩溃。这里的问题是您需要为交叉点独立定义 IOR，而 NFF 文件格式不这样做。那时还不清楚什么是“正确”的行动方案。

• 移动新射线的原点。

新光线的原点必须沿着传输路径稍微移动，这样它就不会与前一条光线在同一点相交。

p += transmit * 0.01f;

我尝试使这个值更小（0.001f）和（0.0001f），但这会使球体看起来很实心。我猜这些值不会使光线远离前一个交点。

编辑：这里的问题是反射代码在做同样的事情。因此，当一个物体既具有反射性又具有折射性时，光线的起源就会完全出现在错误的位置。

• 光线反弹量。

我人为地将光线反弹的数量限制为 4。我测试了将此限制提高到 10，但这并没有解决问题。

• 法线。

我很确定我正在正确计算球体的法线。我取交点，减去球体的中心并除以半径。

我需要从对象文件格式（.off）文件（在 c++ 中）中读取多边形列表。.off 文件的格式基本上是这样的：

.off 文件允许每个多边形有任意数量的顶点，这让我想到了我的问题。你怎么知道哪些顶点连接到哪些？例如，如果 .off 文件读取：

多边形是四边形，但并非所有顶点都相连。如果您只是简单地将每个顶点连接到其他顶点，您最终会得到四个三边多边形，而不是一个四边多边形。我希望以类似于循环符号的方式列出顶点，但我似乎找不到任何关于此的信息，所以我猜不是。

所以我的问题是：
.off 文件是否使用任何格式来显示这种连接？如果没有，有没有其他方法可以确定 .off 文件中连接了哪些顶点？

所以我现在应该开始为我的单色模型照明。测试应用程序是仅用于实现最新方法的测试用例，因此我意识到理想情况下它应该实现光线追踪（因为理论上，它可能在几年内成为实时图形的理想选择）。

但是我从哪里开始呢？

假设我从来没有在旧的 OpenGL 中做过光照，所以我会直接使用非弃用的方法。

该应用程序当前已正确设置顶点缓冲区对象、顶点、法线和颜色输入，并且它正确地在空间中以平面颜色绘制和转换模型。

是否有一个信息来源可以从平面彩色顶点到通过 GLSL 获得正确最终结果所需的所有信息？理想情况下，与可能需要补充它的任何其他附加照明方法一起使用。

根据我收集到的信息，他使用了稀疏体素八叉树和光线投射。他似乎没有使用 opengl 或 direct3d，当我查看游戏 Voxelstein 时，似乎实际上正在绘制微型立方体，而不仅仅是一堆 2d 正方形。这让我措手不及，我不确定他是如何在没有 opengl 或 direct3d 的情况下做到这一点的。

我试图通读源代码，但我很难理解发生了什么。我想实现类似的东西，并希望算法这样做。

我对他如何执行渲染、剔除、遮挡和照明很感兴趣。任何帮助表示赞赏。

我开始为 iOS 构建一个实时光线追踪器。我是这个光线追踪的新手，到目前为止我所做的只是在 ObjC 中编写一个基本的。在我看来，基于 C 的光线追踪器会比用 ObjC 编写的更快，但 ObjC 会简单得多，因为对象层次结构非常方便。不过，速度非常重要，因为我希望它是实时的，比如 30 fps。

你对 C 的加速是否值得额外的复杂性有什么看法？我可以预见 C 代码需要更长的时间，并让我因许多错误而头疼（尽管我对 C 并不陌生），但最初追求更高的速度是很诱人的。

有没有用 C 编写的光线追踪器的例子？我在谷歌上搜索这些东西被很多 C++ 和 C# 的结果所污染。

我正在为教育目的构建一个简单的光线追踪器，并希望为对象添加折射。使用 Snells Law，我能够在交叉点递归地创建一条新射线。光线追踪器目前仅支持球体，我使用了一个场景，其中多个球体相互嵌套，具有不同的折射率。

如果我从球体外部开始射线，一切似乎都很简单。你从场景的折射率开始，一旦你击中第一个球体，就使用之前的折射率和球体材料的折射率来折射光线，直到你击中下一个球体，依此类推。使用交叉点的法线，我可以确定我是进入还是离开球体。

但是，我不明白应该如何处理球体叶子以及如果光线没有从场景的外部开始该怎么办。

• 我可以只取一堆折射率并在我离开球体后立即向上一层吗？
• 如果我从球体内开始，我如何确定我必须从什么折射率开始？

例子

您有三个球体，从外到内的折射率分别为 0.9、1.1 和 0.8。空气指数为1.0

• 您的相机在球体之外并指向球体的中心：

  • 开始索引是 1.0，你首先用索引 0.9 击中外球体，然后从 1.0 折射到 0.9 并保存你的光线现在是 0.9 材质
  • 您点击中间球体并注意到 1.1 的材料常数，因为您保存了 0.9，您知道您必须从 0.9 折射到 1.1，并且除了 0.9 之外还保存 1.1
  • 你击中内部球体并从 1.1 折射到 0.8，你已经保存到现在 0.9、1.1 和 0.8
  • 你再次击中内部球体（这次你退出它，所以你检查你保存的值并知道你必须切换回 1.1）
  • ...直到你在外面

• 现在有问题了，当相机在球体内时。您将不知道必须切换到什么折射率。

我遇到了一个奇怪的指针问题。我正在构建一个用于光线跟踪的 kd 树，在 BuildKDtree 函数期间，我打印了 root->left 和 root->right，并且我得到了存储在节点上的各种属性的正确值。当我完成该代码然后尝试使用原始根的指针遍历树时，root->left 和 root->right 值包含垃圾和代码崩溃！关于可能导致这种情况的任何建议？如有必要，我可以粘贴代码，但它非常笨拙。

在光线/盒子相交的上下文中，“有效的相交区间”到底是什么？我一直在搜索不同的教程，但似乎他们似乎大多认为这是先验知识。