[提交于 2004 年 11 月 18 日 (v1),最后修订于 2004 年 11 月 29 日 (当前版本 v3)] 查看 G. J. Chaitin (IBM 研究院) 所著题为《实数有多“实”?》的论文 PDF。查看 PDF 摘要:我们讨论了反对连续性并支持离散性的数学与物理论据,重点介绍了埃米尔·博雷尔 (1871-1956) 的思想。来源:Gregory J. Chaitin [查看电子邮件] [v1] 2004 年 11 月 18 日星期四 22:35:07 UTC (11 KB) [v2] 2004 年 11 月 24 日星期三 03:15:31 UTC (11 KB) [v3] 2004 年 11 月 29 日星期一 16:41:15 UTC (11 KB)
Gruen 等人荣获大奖的论文《Ray Tracing Massive Amounts of Animated Geometry》提出了一种新颖的解决方案,旨在解决复杂动画场景中实时光线追踪的性能瓶颈。
在传统的渲染流程中,对密集网格进行动画处理需要频繁且昂贵地更新加速结构(BVH),这往往会超出 GPU 的帧时间预算。作者提出通过使用低分辨率四面体笼(tetrahedral cages)将动画与三角形数量解耦。这些笼子充当代理:在运行时,仅对笼子进行动画处理,而复杂的几何体则保持在静态的、预计算的“静止姿态”。进入四面体的射线会被变换到该静止姿态空间,从而无需更新底层 BVH 即可高效进行求交计算。
这种方法显著降低了内存占用和计算开销,使得以 60 FPS 渲染拥有数亿个动画三角形的场景成为可能。虽然该技术最适用于植被摇曳或人群等保持连接性的动画,但它为传统的顶点动画提供了一种可扩展的替代方案。目前的研究正致力于提升笼子的质量,并提供 C++ 库以便将此方法集成到现代光线追踪流程中,帮助开发者克服当前动画几何体在扩展性上的限制。
在《Crafting Interpreters》一书中,Robert Nystrom 探讨了在运行时错误中将字节码偏移量映射到源代码行号的高效方法。虽然使用平行的行号数组可以实现 $O(1)$ 的查找效率,但它需要 $O(n)$ 的内存空间。
为了将内存优化至 $O(r)$(其中 $r$ 为行跳转的次数),Nystrom 比较了两种主要策略:
1. **游程编码(Run-length encoding):** 存储属于同一行的连续字节长度。虽然这种方法对于顺序遍历非常高效(配合游标为 $O(n)$),但随机查找需要 $O(r)$ 的线性搜索。
2. **起始偏移量(Starting offsets):** 存储 `(offset, line_number)` 对。这种格式支持**二分查找**,使随机查找效率达到 $O(\log r)$。结合游标使用时,它仍能保持 $O(n)$ 的顺序处理性能。
这种兼顾两种用途的结构对虚拟机设计非常有效。现实世界的实现反映了这些权衡:JVM 使用类似的“起始偏移量”表(通常进行线性搜索),而 Lua 使用带有周期性绝对检查点的增量编码方案,以平衡内存效率和查找速度。最终,结合二分查找的起始偏移量方法,为通用虚拟机行号追踪提供了最稳健的平衡方案。