6

我目前正在尝试渲染一个 Mandelbrot 集,我很快意识到不必重新计算每次渲染的最大迭代次数会很有用……另一方面,需要跟踪大量数据的。在我看来(基于我对 RDMS 的有限经验)关系数据库可能不是要走的路,因为我不希望随着数据集变大而影响性能。对于哈希表来说,这似乎是完美的情况,但我以前从未使用过,而且似乎无法弄清楚如何使用或管理其中一种现有的 Web 服务器语言(Python/PHP/whatever)。

更明确一点:要存储的重要值是:

  • 复平面上数的原实部
  • 复平面上数的原虚部
  • 最大迭代次数
  • 在达到最大迭代之前或直到该点运行到无穷大之前完成的迭代次数 n
  • n次迭代后复平面上数的最终实部
  • n次迭代后复平面上数的最后虚部

在任何给定时间,给定原始实部原始虚部最大迭代次数,我希望能够获得包含最终实部和虚部的结果集。

所以你怎么看?哈希表是要走的路吗?对于普通的数据结构来说,问题是否过于复杂?

任何帮助都将不胜感激。提前致谢!

编辑

应朱莉诺伯特的请求,我将稍微解释一下这个问题。

我的目标是允许用户在没有计算延迟的情况下放大 Mandelbrot 集(即使它是通过预定义的缩放)。我还希望能够在不断向服务器询问新数据数组的浏览器中执行此操作,并提供新的 x 和 y 坐标以及要在复平面上查看的高度和宽度。然而,由于计算像素颜色值可以更快地完成(给定 max_iter、real_final 和 imag_final),而且因为允许用户调整颜色设置会很好,所以我将只发送浏览器我的帖子中列举的变量,让用户的浏览器计算颜色。

看看这个:

http://jsfiddle.net/xfF3f/

如果您查看 drawMandelbrot() 函数,您会发现点循环将重要值存储在名为 dataset 的变量中。然后在 drawMandelbrotFromData() 函数中使用该变量,在该函数中执行剩余的计算来计算每个像素的颜色。

如果您单击“cleardabrot”,它将用白色矩形替换画布。如果您单击“refilldabrot”,它会再次运行 drawMandelbrotFromData() 函数...这样做是为了向您展示如果它不必执行痛苦的迭代计算,它实际渲染集合的速度有多快。

所以这里的最终目标是能够以任意精度计算这些值,因此用户可以缩放到集合的任何级别,让服务器确定这些精确点是否有任何数据(或者,最好是点 NEAR那些确切的点......虽然我不确定如何在不执行某种范围查询的情况下做到这一点),然后逐个像素地吐出信息。例如...

  • 用户正在使用 300x300 画布。
  • 他放大到左上角为x = .000001和的点y = .0000231
  • 他在这个框架中选择的宽度和高度w = .00045h = .00045

他会将这些数字发送到服务器,然后接收一个包含 300*300 索引(一个代表每个点)的数组,每个索引都包含确定画布上每个像素颜色的必要信息。我的问题是......存储预先计算的 Mandelbrot 数据的最佳方法是什么,以便用户可以输入任意 x、y、w 和 h 值并快速拉回复平面上的点的值范围。

4

1 回答 1

2

在任何给定时间,给定原始实部、原始虚部和最大迭代次数,我希望能够获得具有最终实部和虚部的结果集。

从您的问题中不清楚为什么需要这个?为什么需要在同一点重新计算?

如果您正在尝试不同的 max_iterations 设置,您可以将按像素级别获取的 actual_iterations 保存在二进制文件、文本文件或图像或您认为方便加载/存储的任何内容中,例如关系数据库。

如果您正在执行实时渲染并且您正在使用一些需要重新计算递归方程的处理(在相同的原始点和相同的最大迭代次数),那么我想您可以通过查看来加快速度 -上桌。

显然,您的查找表必须比计算更快。您需要一个查找表,其中以下操作总共花费的时间少于再次进行计算。

  • 计算索引(给定 origo_real,origo_imag,max_iter)
  • 加载缓存的计算(final_real、final_imag、actual_iter)
  • 一家初始商店

根据您在相同点重新计算/重新访问的方式,您可以将问题划分为索引很可能在查找表中并且查找表足够小存储在 L1 或 L2 缓存中。

这些是一些想法..但你应该澄清你真正的问题是什么。

如果您只需要大量这些数据进行进一步分析并且不需要实时,那么好吧......澄清您的真正问题是什么:)

更新的答案

这似乎类似于使用地图服务(放大/缩小、四处移动),也就是说,您本质上是在为给定区域提供图像并进行缩放。

但是在这种情况下,由于可以查询任何缩放级别,因此您为一个用户缓存的任何内容都可能不会被下一个用户重新使用。我不知道为什么这样做有意义,而不是编写一个用户可以实时缩放的客户端软件(已经完成)。

任何状况之下。如果您的主要问题是带宽但您有足够的计算能力,那么您可以将计算出的补丁的图像存储在一个高度压缩的文件中,质量稍低,并缓存这些图像。然后,您可能需要将这些补丁拼接在一起以提供用户想要的确切区域。诀窍是在给定缩放和区域的情况下查询最小的补丁集。

我担心大多数查询会要求不存在的补丁(因为任何缩放级别都是可能的)。也许一些关于谷歌地图/地理信息系统如何工作的信息可以给你一些想法。如果您的主要问题是 CPU,那么也许您可以以不同的方式执行此操作,并让用户在 Applet 中进行计算(并可能发回结果)

如果您这样做是为了学习如何通过客户端服务器进行缓存/计算,您可能需要考虑一个不同的挑战,因为任何体面的计算机都可以在客户端解决这个挑战。

于 2010-09-05T10:13:14.003 回答