javascript - 彩色点云渲染JavaScript算法

Question

我刚刚用 JS 制作了一个 3D pointcloud 渲染应用程序。此应用程序能够以 40 FPS 的速度为浓​​密的厚云渲染 +200 000 个 3D 黑/白点。但是，我现在正在尝试实现颜色，并且在我处理这个新功能时，我意识到在屏幕上绘制点的顺序非常重要。

我制作了另一个文件，我在其中为每个点选择了一种颜色。例如0点是红色，1点是绿色，2点是蓝色；所以颜色是预先计算好的。

我的意思是，距离用户较远的点应该首先呈现，距离较近的点应该稍后呈现。使用这种技术，如果两点重叠，则较近的点将出现在屏幕上。

我做了一个自定义算法 [我知道 O(n^2) 很慢]，它对所有点(超过 200 000 个)进行排序，以获得与用户位置的距离(首先是进一步的点)。但是，我需要大约 7 秒才能将它们按正确的顺序排列，因为应用程序本来是实时的，我不得不采取一种解决方法来防止浏览器显示“此页面未响应”弹出窗口.

Is there any other method for rendering 3D coloured points which overlap on the screen? Don't worry, I'm not asking for a piece of code, I just want to know if there's another faster way to achieve this, if possible in pseudo-code.

我已经知道我可以减少编写更高效算法的时间，但这仍然太慢。每个有效答案都将获得赞成票作为奖励!

这就是我目前所知道的

这就是我想要的

Answer 1

目前还不清楚您为什么提出O(n^2) 时间复杂度。

您有 20 万个点的数组。您必须计算到某个点的距离。这是在 O(n) 中完成的。在我的机器上，它在 42.142ms 内完成。

现在你必须根据这个距离对你的点进行排序，在我的机器上它在 122.358ms 内完成。您的排序算法在 O(n*log(n)) 中运行。现在你从最远的地方画出点，它也在 O(n) 中运行。

所以我不确定您是如何以 O(n^2) 结束的，以及为什么它会在 7 秒内运行。