为 Nintendo 64 寻找最佳正弦函数

Finding the BEST sine function for Nintendo 64

频道:Kaze Emanuar · 时长:26:40 · 发布:2023-06-24 · 播放:420537

在 YouTube 观看

简介

Kaze Emanuar 为 Nintendo 64 寻找最佳正弦近似,比较《马里奥 64》和《时之笛》中的查找表与多项式替代方案。详细介绍了数值计算以及三阶、四阶和五阶近似。

HN 为什么推荐

在讨论正弦实现以及查找表在内存受限硬件上是否优于计算时被引用。

这家伙投入了大量工作来研究在 N64 上是否有更快的方法进行三角函数计算 — HN, 2024

软件性能与优化 · 游戏编程与引擎 · 游戏历史与复古游戏

中文字幕节选

在2D游戏时代,移动角色相当直接, 只需将水平速度加到X坐标上, 将垂直速度加到Y坐标上。这更多是关于编程逻辑, 而不是数学。而且你也不必应对编译器的噩梦, 那是编程和纯机器码的美好旧时光,每个程序员的梦想。 当我们从2D游戏转向3D游戏时,游戏物理和渲染变得 复杂得多。现在必须处理额外的维度,这需要 三角函数来实现。举个例子,想象你 在游戏中有一个角色,这个角色可以向前移动并朝任何 方向旋转。现在角色面向的方向由一个角度表示, 我们称之为朝向角。当角色向前移动时,它们沿着 由朝向角决定的方向移动,这就是我们的朋友正弦和余弦 发挥作用的地方。要移动角色,我们通过将 朝向角的正弦与前进速度相乘来改变其X坐标,同时 通过将朝向角的余弦与前进速度相乘来改变其Z坐标。 类似地,在3D游戏中,我们有3D动画角色,每个角色由 各种骨骼组成,这些骨骼可以独立移动和旋转。在大多数N64游戏中, 每个骨骼都需要使用正弦和余弦函数来计算 旋转。这是因为每个骨骼可以沿三个独立的轴旋转,每个 轴都需要计算一个正弦和一个余弦。不仅仅是动画 角色,所有物体都必须使用这些函数来计算它们的视觉旋转。 所以无论是马里奥转头还是旋转平台,三角函数都在 起作用。棘手的地方在于,准确计算一个值的正弦或余弦 并不容易。正弦是我们所说的超越函数,这类似于 π的值永远持续而不重复,所以我们无法写下 大多数数字的正弦的精确值。但别担心,虽然我们无法得到精确 值,但我们可以尽可能接近真实结果,只是每 增加一位精度都会指数级地消耗更多资源。 因此,由于计算一个值的精确正弦或余弦如此棘手和昂贵, 计算机必须使用近似算法。马里奥64是最早 遇到这个问题的游戏之一。他们处理的方式,或者说他们方法的变体, 成为了大多数N64游戏的标准。但如果我告诉你还有 改进的空间呢?我打赌你想看看如何改进。今天你将学到很多数学, 而且你会喜欢的。在我们深入数学之前,我必须澄清一些 关于马里奥64的事情:它能表示的角度数量有限。为了帮助你 可视化,想象如果你只有四个角度可用,现在如果我们有 八个角度呢?16个角度呢?你明白了。那么实际上我们 在马里奥64中处理多少个角度呢?高达65,536个!这里有些你可能没有 注意到的事情:在游戏过程中,马里奥只使用了4,096个 角度,从65,536个中。令人震惊吧?但即使这个有限的数量也 足够让玩家注意不到任何限制。毕竟控制器本身 甚至无法处理所有65,536个可能的角度。马里奥的角度也会在达到 65,536时循环回零。这意味着我们的正弦函数只需要在 一个相当小的范围内工作。那么马里奥64如何计算它的4,096个正弦和余弦 值呢?答案是它不计算。相反, 马里奥64使用了一个聪明的捷径:它有一个大表,存储每第16个正弦 值。当需要计算一个角度的正弦时,它将角度舍入到 16的倍数,然后在表中查找对应的值。多亏了我们的

HN 上的讨论

是的,在80年代末/90年代初,我为软件渲染器使用了大量的三角函数表,但我只是抛出一些想法,因为最近我看到了很多非常棒的优化,而这些优化在那个时代大多被忽略了。这家伙投入了大量工作来研究在N64上是否有比SM64中使用的更快的方法来进行三角函数计算(剧透:有):[VIDEO] Jez(Argonaut的CEO)曾经给我提供了一个Starfox/DSP团队的面试机会,所以我差点就参与了这个项目。当时他在Usenet的编程小组中非常活跃。 — qingcharles, 2024-08
就是这个视频让我开始思考:[VIDEO] 我在80年代末/90年代初编写软件纹理器等,甚至最近我看到x86的人用各种我当时完全不知道的信息(关于流水线等)让我自愧不如。我会整天随机重新排列汇编指令并重新分析茶壶渲染,看看是否有任何东西能推动进展。 — qingcharles, 2024-08
你可能也会觉得这个视频有趣:“为Nintendo 64寻找最佳正弦函数”[VIDEO] — eska, 2024-03
不仅仅是现代机器,Nintendo64在大多数情况下都受内存限制,因此许多传统的优化(查找表、循环展开)在N64上可能会更慢。循环展开的情况很有趣。因为CPU必须获取更多指令,这给内存总线带来了更大的压力。如果好奇的话,在N64上,图形芯片也是内存控制器,所以CPU为了不占用内存总线所做的每一件事都会产生累积效应,让图形能够做更多的图形工作。这也是为什么N64有奇怪的9位RAM,这是为了使用18位像素格式,每个像素只占两个字节,对于CPU请求,内存控制器忽略第9位,呈现正常的8位字节。他们希望通过高速内存(250 MHz,而CPU运行在90 MHz)能够满足所有人的需求,而且它做得还不错,N64上有一些非常令人印象深刻的游戏。但在大多数游戏中,CPU运行得相当轻松,必须避免占用内存总线。[VIDEO](Kaze Emanuar:为Nintendo 64寻找最佳正弦函数) — somat, 2026-03
如果对于当前问题足够好,那就不是无用的。Kaze Emanuar有两个完整的视频专门优化Nintendo 64上的sin(),他在自制程序中使用这样的近似而没有问题:- [VIDEO] - [LINK] — boricj, 2025-04

相关视频