This is a continuation of the post “Unlimited detail challenge…“. I am still waiting for a real solution to emerge from the various intriguing ideas. Here I want to comment a bit about the kind of the algorithm UD might be.
Bruce Dell compared it with a search algorithm, more specifically compared it with a search algorithm for words. As everybody knows, words form an ordered set, with the lexicographic order.
Moreover, Dell explains that the thing of UD is to pick from the huge database (which might be in a server, while the algorithm runs on a computer elsewhere, thus the algorithm has to be in a sense an online algorithm) only the 3D atoms which are visible on the screen, then render only those atoms.
Therefore, imagine that we have a huge database of 3D atoms with some characteristics (like color) and a separate database made of the coordinates of these atoms. The UD algorithm solves a “sorting” problem in the second database. (I put “sorting” because there is no total order fully compatible with the solution of the ray-casting problem, in the sense that it remains the same when the POV is changed.) Once this “sorting” part is done, the algorithm asks for the characteristics of only those points and proceed to the rendering part, which is almost trivial.
By looking at sorting algorithms, it is then to be expected a time estimate of the kind (for given, fixed number of screen pixels), where is the number of 3D atoms.
There are even sorting algorithms which are more efficient, like , but they are more efficient in practice for really huge numbers of atoms , like , as the AKS sorting.
So, the bottom line is this: think about UD as being a kind of sorting algorithm.