彩色PointCloud渲染JavaScript算法

Question

我刚刚在JS中制作了一个3D 点云渲染应用程序。这个应用程序能够渲染+200,000 3D黑白点在40 FPS的浓重云。然而，我现在正在尝试实现colours，并且，在我开发这个新特性时，我意识到在屏幕上绘制点的顺序是非常重要的。

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

我的意思是，点是用户的进一步，应该先呈现，然后再呈现更接近的点。使用这种技术，如果两点重叠，则更接近的点将出现在屏幕上。

我做了一个自定义算法O(n^2)，非常慢，我知道是哪种算法对距离用户位置的所有点(超过20万点)进行排序(首先是进一步的点数)。然而，我要花大约7秒的时间才能把它们按正确的顺序排列，因为它是实时的，而我必须想办法阻止浏览器显示“这个页面没有响应”弹出。

有没有其他方法来渲染屏幕上重叠的3D彩色点？别担心，我没有要求一段代码，我只是想知道是否还有更快的方法来实现这一点，如果可能的话，在伪代码中。

我已经知道我可以减少编写一个更有效的算法的时间，但是这仍然太慢了。每一个有效的答案都会得到奖励！

，这就是我到目前为止得到的，

​

​

，这是我想要的

​

​

Answer 1

目前还不清楚为什么会出现O(n^2)时间复杂性。

你有200 K点的数组。你有一个点，你必须计算出一个距离。这是在O(n)中完成的。在我的机器上，它是用42.142ms完成的。

现在，您必须根据这个距离和我在122.358ms中完成的机器对您的点数进行排序。您的排序算法在O(n*log(n))中运行。现在，您从最远到关闭点，它也运行在O(n)。

所以我不知道你是怎么得到O(n^2)的，为什么它会在7秒内运行。

Answer 2

在呈现过程中，您可以记忆呈现的pos /距离，而不是排序。如果您发现要呈现的新点比已经呈现的重叠点更远，则跳过新点。