引言
“如果我们用有理数替换浮点数并尝试渲染图像会发生什么？”
在考虑了研究人员和计算机图形老师Morgan McGwire的推文后，我问了自己这个问题。 他谈到了计算机科学专业的学生，当他们第一次学习将熟悉的浮点数存储在现代计算机中时，一定会感到惊讶的。 这些折衷使简单的任务变得困难，例如，检查点是否属于三角形。 当然，问题在于，使用行列式或某种矢量乘法（但实际上这是同一件事）来检查四个点是否在同一平面（共面）中，将永远不会给出完全等于零的值，这是必需的这些是数学方法。 即使在同一平面上的真实计算是准确的，以几乎1.0的精度进行的相同折衷也可以得出四个点本身不共面的答案。
这引起了我的想法-如果我们假设所有传入的渲染器数据（顶点坐标，3D变换等）都设置为有理数，那么它们将创建所有操作，从创建射线到遍历加速结构到相交三角形的光线只是有理数？ 如果真是这样，那么我们将能够准确地进行共面性测试！ 您可能想知道为什么以有理数表示的3D场景只能给出有理数的结果...
一个简单的场景，其中的路径跟踪是通过有理算法执行的。 它使用浮点数系统，而不是浮点数。首先，有理数是可以表示为两个整数之比的数字，例如1/2或355/113。 其次，“正常渲染操作”（例如边界框测试，检查射线与三角形的交点，射线的反射等）基于矢量和标量积以及标量除法（包括坐标变换和矩阵求逆，四元数等），它们又基于四个基本运算：加法，减法，乘法和除法。 当对有理数进行加，减，乘，除时，也可以获得有理数。 数学家会说，许多有理数构成一个在四个基本算术运算下都是封闭的字段。 对我们来说，这意味着如果我们仅遵守有理数，则实际上可以从3D场景的输入数据移至完全渲染的图像，而无需离开有理数的世界。
“有理数的作用给出有理数”规则的例外是平方根和三角函数/先验函数。 至于后者，我总是说如果您必须在渲染器的几何内部执行三角计算，那么很可能您做错了什么（我展示了
如何解决最标准的情况 ）[Habré上的
翻译 ]。 对于平方根，除了圆锥形截面（球，圆柱体等）并执行着色/ DFOS /着色外，不必像通常那样经常对光线和法线进行归一化。 创建射线，其通过，相交，反射等当然不需要做。 不幸的是，我经常看到程序员除了“好吧，我不知道，我这样做是为了安全起见。 在实践中，在绘制几何图形的部分中，很少需要对值进行规范化，因此我希望您可以在不离开有理数世界的情况下跟踪整个场景-这就是我所说的“有理绘制”。
为了付诸实践，我需要基于计算机可以使用的有理数创建一个数字系统。 然后，在此之上，我可以实现常规的路径跟踪算法，在不损失准确性的情况下计算图像，执行具有准确答案的共面性检查，并使所有学习计算机图形学的学生满意。
本文是一个有关研究这种想法的现实主义两个晚上的故事。 我将谈论我学到的许多方面，想出什么，以及在此过程中发现的一些惊喜。 这篇文章是按照我的工作的时间顺序写的。 此外，它以我非同寻常的非正式和非常不科学的风格（我为此感到自豪）编写。 上面显示的图像是一种破坏者，但请仔细阅读文章，因为我将讨论优缺点。
准备工作
我要做的第一件事是在
Shadertoy中实现
最小限度的示踪剂，用于一个
极其简单的场景，包括平面，球体，长方体和三角形-真实渲染器的构建块。 然后，我将代码复制到C ++文件中，并进行了一些小的更改后，使用
piLibs框架对其进行了编译。 因此，为了进行比较，我使用了符合IEEE754标准并带有浮点数的常规数字将跟踪图像渲染到CPU。 我还从跟踪代码中删除了所有射线归一化，因为如上所述，实际上并不需要它们。 让我提醒您，规范化需要平方根，并且使用有理数时不会保留有理数（有理数的平方根不是有理数）。 稍后，我们将看到仍然可以应用平方根，当然，我只是想使代码在数学上尽可能地简洁，以了解我可以对有理数的精确算术进行四舍五入而无需舍入。
最后的准备步骤-我学习了所有的vec3，mat4x4和其他基本的代数/数学课程，然后进行了更改，以使它们使用有理数而不是浮点数。 由于我的理性结构使所有标准运算符（加法，加法，减法，mul，div，符号反转，比较等）过载，因此替换发生时没有问题。 我很快实现了其余的常规操作（abs，sign，mod，fract，floor，sqrt等），从理论上讲，这足以获得漂亮的合理效果图。
测试1-天真的解决方案
但是，让我们看看第一个实现是什么样的。 首先，我总是尝试最简单的方法，然后查看结果。 实现有理值的最简单方法是使用两个整数。 就像本节的名称所暗示的那样，这不是我的最终决定，但第一次尝试是一个合理的决定。 因此，每个数字
x都应表示为分子
N和分母
D ，形成值
N /
D。 x值由最接近真实
x值的最佳
N /
D对（在指定的位深度内）近似。 我决定两个数字都必须为正，并且数字的符号应存储在单独的位中，以简化工作并消除歧义，尽管这不是很重要。 在此阶段，分子和分母均为无符号类型。 但是，即使在分隔符号时，
N /
D也有很多冗余：例如，1/4和7/28表示相同的数字，但是具有完全不同的位表示。 我们将在稍后进行讨论，但是现在，让我们不要集中注意力，看看这四个基本算术运算在这种有理形式下的样子。
首先，请注意，减去
a -
b只是将
a和与
b相反的值相加，即
a +（-
b ），其中
-b可以通过简单地更改
b的符号来计算。 类似地，除以
a /
b与将
a乘以
b的倒数相同。 换句话说，
a /
b =
a ·（1 /
b ），其中（1 /
b ）可以通过简单地改变分子
b n和分母
b d的分母
b d的位置来计算。 因此，这是有理算术的第一个有趣的特性-除法和乘法具有相同的代价，因此，与通常的浮点渲染不同，在浮点渲染中，通常避免在缓慢的纹理请求的延迟下进行除法，延迟或隐藏除法，因此无需担心有理算术中的这些运算。
我们转向加法乘：我们知道对和反值都很容易计算，因此我们得到：
乘法期间的符号保留是微不足道的，它只是异或运算，因为两个正值给出一个正结果，以及两个负值。 保存要加号的过程是一个更为复杂的过程，对于快速解决方案，我通过三个分支来实现它（如果符号
a和
b重合，则加法比较简单，但是当它们不匹配时，则需要选择一个较小的数字并将其从较大的一个中减去-在本文中我将更详细地描述这些小细节，但仅将源代码布置在某处）。
我还将跳过fract（）和floor（）的实现； 如果您决定尝试自己实现它们，您将看到它们的简单性和美感。 还应注意比较运算符。 照顾好迹象并假设
a和
b为正，我们得到
重要的是在这里要注意，即使是为了进行比较，我们也需要几个乘法运算，这可能会导致转换到下一个字长，并且重要性会低一些。
最后，我们在单独的部分中查看平方根，知道在大多数情况下我们不需要它们（第一个测试的球除外）。
这足以运行第一个渲染并跟踪测试场景（平面+球体+三角形+矩形框）以查看会发生什么。 我为第一个测试慷慨地使用了65位有理数，它实际上代表了大量数据（相当于“双精度”数据类型）：分子使用32位，分母使用32位，而符号则使用另一位。 第一个是通过这种幼稚方法获得的图像，第二个是使用浮点数（参考）制作的图像：
“天真” 65位有理数浮点参考结果非常糟糕，盒子和三角形甚至没有出现在渲染中，地板的球体和平面太吵了。 当然，问题在于每次我的有理数在绘制的任何算法阶段执行任何基本算术运算时，由于使用了整数乘法，因此分子和分母变得越来越不受控制。 请考虑以下问题：如果我们最初世界的单位是米，并且将源几何图形（顶点和相机）附加到毫米精度，那么对于一个相当小的场景，只有源数据会占据16位的体积。 同时，利用标准的高清屏幕分辨率和4倍平滑度，合理的光束方向编号将很容易需要12位。 也就是说，在梁和几何体的首次交互期间，使用两组输入数据的最简单算术运算会将结果转换为28位长度-足够接近我在第一个实现中为自己设置的32位限制。 而且甚至在我们执行第一个矢量或标量积之前。 当标量积完成时，渲染器将需要数百位长的有理数来表示数字。 当然，这是最坏的情况，但平均情况将接近此情况。 考虑到我仅为分子和分母分配了32位容量，因此很容易理解在测试中这些值超出边界的速度有多快-不足为奇的是，除了底平面和球体的一部分外，几乎看不见任何东西。
测试2-减少最大公因数
然后，我通过使用上面简要提到的属性改进了系统-不同的有理数可以表示相同的数量。 实际上，6/12与1/2相同，但是它使用的位数比最后一个要多得多。 因此，想法如下：如果在每次基本算术运算之后（或之后），我将从分子和分母中提取所有公除数，并将小数化为最简单的形式，那么也许我将能够使所有事物都受到控制，并继续进行更长的运算精确的算术而不会损失准确性。 也许您可以做足够长的时间以获得干净的渲染图像？ 我将做一个小小的例子来说明另一个示例：588/910可以简化为42/65，因为14是588和910的除数。但是要存储42/65，显然，比588/910所需的位更少。 可以使用Great Common Divisor（GCD）算法查找同时除以其他两个数字的最大可能数，您可以在任何地方找到有效的实现方式（我个人直接从Wikipedia复制了它，并通过执行扫描步骤将其加快了一点）位使用内部x64操作）。 因此，有了GCD算法，我的理性类应该不断简化渲染过程中生成的分数。 这可以通过两种方式完成：
首先是将加法和乘法运算符的中间结果转换为下一种类型的位数据（在我目前的天真解决方案中为uin64_t），在这种更为庞大的数据类型中搜索GCD，然后将结果减小为原始位长（32）。 第二种方法是分析在两个算术运算符中
a n ，
a d ，
b n和
b d如何相互组合，并在执行乘法之前从它们中提取公因数。 第二种方法基本上消除了对大位长度的需求。 知道仍然有必要使用它们时，我决定选择第一种方法，因为它易于实现，并且可以加快工作速度（傍晚时分飞快）。 完成所有这些操作后，让我们看看我现在可以创建什么渲染：
GCD减少了65位有理数浮点参考好多了！ 当然，到目前为止，还远未达到理想状态，但看起来很有希望。 我使框和三角形出现，并且球体现在看起来更大了。 但是，在右上角出现了一个有趣的伪像，许多像素的有理数仍然超出边界，这导致了图像中的许多点。 但是，值得注意的是，对于某些（许多）像素，我开始获得
准确而完美的结果！ 也就是说，示踪剂发现了数学上准确的点和距离的交点，这是尝试使用有理数的根本原因。
在继续进行证明有理数适用性的过程的下一步之前，我想简要地停止并分享我对GCD和有理数减少的发现。
第一个发现与有理数的位数有关。 尽管我仍然无法渲染出漂亮的图像，并且这比担心优化数据量更重要，并且尽管这种早期实现仍然使用了大量位（1 + 32 + 32），但我已经在考虑前面提到的浪费位以多余分数的形式。 特别是，在添加具有GCD的段之后，不再适用2/4之类的位组合，因为在写入任何寄存器或变量之前，它们会自动减小为1/2。 也就是说，从某种意义上说，在可能是分子和分母的所有2
64个位组合中，有许多未使用。 而且你不能浪费这样的东西。 还是可能吗？ 我实际上会损失多少空间？ 我做了一点题外话来探讨这个问题。
离题-互质数
下图显示了5/5位和7/7位中有理数位的使用。 图的水平轴和垂直轴表示所有可能的有理数的分子和分母的值，这些分子的分子和分母最高为5位（31）和7位（127）。 黑色像素是未使用的组合，白色像素是使用的分数。 例如，除了1/1像素外，整个对角线都是黑色的，因为形式为n / n的所有分数都减小为1/1。
使用5/5有理数位
将位用于7/7有理数如果像我一样对像素进行计数，那么您会很快理解，随着位数增加，有用像素的比例趋于60.8％。 一项在线研究显示，该比率恰好是6 /π2，因为这也是两个随机数相对质数（没有共同的因数）的概率。 您可能会问，圆周率是从哪里来的？ , « „“ » — , ,
- , 2, 1/ζ(2). , - .
, , 40% . , , … . , , , , , . - - -, , , . ,
.
, : , . , — (, , ), «» , , . , . , , , . . .
, — - , , . , 16/16- , , 16/16 ++ .
3 —
, . , .
, , , , , ( , — , . , , , ).
不管怎样，如果我以某种方式保护分子和分母不溢出，我决定检查渲染结果。最简单的方法是，如有必要，将分子和分母都向右移动足够数量的位，直到它们再次出现在分配给它们的位空间中。实际上，这意味着分子和分母都除以一个值的整数，这意味着该数字的值大致保持不变。在这里，我偏离了实验的最初目标。在我的第一个实现中，我查看了分子和分母所需的位数，将两者均取最大值，并将两者均移位了该位数（四舍五入为最接近的整数）。当这在加法和乘法运算符中实现时，一切看起来都可以接受：通过GCD和规范化减少了65位有理数浮点标准由于一切看起来都不错，因此在这一阶段，我着手解决当前实现中使用大量位的问题。我尝试使用16/16（33位）而不是32/32（65位），结果图像非常好！我仍然看到球体的某些边缘上有小孔，并且在三角形的纹理图中有小间隙。但这对于足够接近浮点数的数量来说还不错。它给了我学习新思想的能量。测试4-浮动斜线
— - , 32 . , ( ).
起初，我认为值得坚持GCD和规范化的思想，但明智的做法是存储和使用位。对我而言，第一件事是，即使分子和分母变大，这通常也不会发生。或至少不会同时发生。因此，当分子较小时，可以使分母较大，反之亦然。两个整数值之一的未使用位可用于表示较大的值。然后我意识到，类似地，浮点数本质上是定点格式，其中“固定”点是可变的。我可以取我的有理数，也可以使分数小数的位布局可变。也就是说，将小数设置为16/16并不困难，但有时允许相同的32位变量设置为16/16，有时根据需要有时为5/27或13/19。值得一试。无论如何，内部setter和getter中的几行打包/解包代码可以快速编写。对我而言，最合乎逻辑的方案似乎是1 | 5 | 26，即：1位：
5位符号：分数线位置（B）
26位：分子和分母的组合数据；分子是高26-B位，分母是低B位，
其中分数条（B）确定分母的大小。例如，数字7/3将写为7/3 = 0 00010 000000000000000000000111 11，
0 , 2 ( 3), 2 , .
, IEEE754, : «1», . . «3» «1» «1»:
7/3 = 0 00001 0000000000000000000000111 1
, : , , 1 . , , 2
26 , . ! , «rational», , — , («int» «float») ! , «int» «rational». , .
, :
32- (1|5|26)32- --, ! - , , - . . , , , , . ( ), , .
( — ). ( ) , GPU :
https://www.shadertoy.com/view/Xd2fzR .
C++, . :
32- 32- , ! , . :
, , ; . , , . , . , , :
64
64- , 32- (1|5|26) . 64- ?
1|6|57 ( x64 ). 57 / .
( , ). ! , , , . , , «» . . , , 64 , . : - , , , ? , «» ? , .
平方根
在研究的最后一个（第二个）晚上，我决定简要介绍一下这个主题并研究新的信息。我想为有理数实现最佳的平方根函数。我当前的幼稚决定（bad）取了分子的整数平方根（带有相应的舍入），然后对分母进行了同样的处理。通常，由于分数的平方根是分子和分母的平方根的分数，因此此方法返回的结果不错，与最佳答案相差不大。但是他当然不会返回有理数平方根的最佳有理逼近。他执行两个近似而不是一个近似。我尝试了以下操作：最后，我们在这里寻找两个整数x y , ,
() («» , ):
在搜索维基百科之后，我发现这个特定的方程式就是所谓的“修正佩尔方程式”。 有一些算法可以找到最小的
x和
y值来求解该方程。 不幸的是，我的注意力很快转移到了其他令人好奇的Diophantine数学上，并且我没有继续执行任何这些算法。
更有效的减少
在傍晚的最后几分钟，我想到了探索使用多个成员（例如，在矢量乘积中结合复杂的几何算符）的想法。 假设向量乘积的第一个成分是
假设sy = a / b，tz = c / d，ty = e / f，sz = g / h
这意味着现在我可以尝试找到常见的除数，例如，在a与d之间，或e与h之间，并将它们用于初步归约。
我有另一个想法：如果在某个阶段渲染速度出现问题，那么您可以完全禁用搜索GCD的步骤，而仅应用规范化。 快速检查表明，在这种情况下，图像渲染仍然可以接受并且可以以更高的速度正常工作。 但是，在这种情况下，我们当然会得到较少的算术准确结果。
作为一种折衷，您可以拒绝执行该过程或GCD方案，而改用一些数学上简单，在代码中进行硬编码且有效的方法，仅将除数确定为2、3和5。尽管我们找不到穷尽的除数，但是在实践中，这将导致找到大量的缩写。 想想看-2分频比7分频高3倍，而41分频数高20倍！
结论
经过这个实验，我开始相信数字表示很有可能基于有理数，类似于我所说的“浮线分数”。 与整数兼容的表示形式，能够以精确的算术方式执行许多任务（假设输入数据以有理形式显示）。 尽管32位版本（1 | 5 | 26）已经创建了有趣的效果图，但64位版本（1 | 6 | 57）具有很大的潜力。
如果不是两个晚上的实验，而是在工作室或公司中创作的专业作品，那么将来可以采取以下步骤：
*获得精确和不精确跟踪的像素数的直方图（换句话说，归一化执行频率）
*尝试对分频器2、3和5实施硬编码归约，并测量丢失的精确像素百分比
*显示浮点渲染和分数浮点渲染之间的像素差异
*寻找巧妙的方法来使用位格式“浮线分数”的未使用值，例如，表示Inf和NaN
*实现对NaN，Inf，下溢，上溢的检测。
总而言之，这是一个有趣的研究。 在此过程中，我发现了一些惊喜，并提出了一项小发明，并从中了解了很多有关Pell方程，平方根，GCD，x86_64内部机制，Riemann zeta函数和其他方面的知识。 我对此感到非常高兴！