Search code examples
javascriptalgorithm3dpseudocodepoint-clouds

Coloured PointCloud rendering JavaScript algorithm

I've just made a 3D pointcloud rendering app in JS. This app is able to render +200 000 3D black/white points at 40 FPS for dense heavy clouds. However, I'm now trying to implement colours, and, while I was working on this new feature, I realised that the order in which points were painted on the screen was really important.

I've made another file where I've selected a colour for each point. For example, point 0 is red, point 1 is green and point 2 is blue; so colours are precalculated.

I mean, points that are further from the user should be rendered first and points that are closer should be rendered later. With this technique, if two points overlap, the point which is closer is the one which will appear on the screen.

I made a custom algorithm [O(n^2) pretty slow I know] which sorted all the points (more than 200 000) for the distance from the position of the user (further points first). However, it takes me about 7 seconds to put them in the right order, for and app which was intended to be real-time, and I had to make a workaround for preventing the browser from showing a "this page is not responding" popup.

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.

I already know that I can reduce that time writing a more efficient algorithm but that would still be too slow. Every valid answer will be rewarded with an upvote!

THIS IS WHAT I'VE GOT SO FAR

enter image description here

THIS IS WHAT I'D LIKE TO HAVE

enter image description here

Solution

  • It is not clear why you came up with your O(n^2) time complexity.

    You have your array of 200k points. You have some point to which you have to calculate a distance. This is done in O(n). On my machine it is done in 42.142ms.

    Now you have to sort your points based on this distance and on my machine it done in 122.358ms. Your sorting algorithm runs in O(n*log(n)). Now you draw the points from furthest to closes and it also runs in O(n).

    So I am not sure how you ended up with O(n^2) and why it runs in 7 seconds.