Thanks to preda and to appc23 for showing us the new UD video:
The previous post on this subject, New discussion on UD (updated) , has lots of interesting comments. It has become difficult to make sense of the various proposals concerning the UD algorithm, therefore I made this new post which shall serve first as a place for new discussions, then it will be updated.
It is maybe the time to make sense a bit of the material existent (or linked to) on this blog. That is why I invite everybody who is willing to do this to make it’s own proposal, preferably with (either) programs or proofs or evidence (links). Especially, in a random order, this invitation is addressed to:
- Dave H
- preda
- 17genr
- JX
- appc23
- bcmpinc
- Shea
- Tony
but anybody which has something coherent to communicate is welcome to make a proposal which will blow our minds.
Make your respective proposals as detailed as you wish, take your time to make them convincing and then, if you agree, of course, we shall make feature posts here with each of them, in order to become easier to follow the different threads.
Let me finish, for the moment, by stating which points are the most important in my opinion, until now (I stress, in my opinion, feel free to contradict me):
- UD works like a sorting algorithm,
- cubemaps are used, but their main utility is to eliminate rotations wrt the POV from the problem,
- UD is not a rendering algorithm (or, at least, the most interesting part of UD is not one), it is an algorithm for fast searching the data needed to put a colour on each pixel,
- UD needs to turn a cloud of points into a database, only once, operation which takes considerable more time than the searching algorithm part,
- does not need antialiasing
- does not raycasting for each pixel
- it is a mathematical breakthrough, though not a CS or math technical one (i.e. does not need the latest edge CS or math research in order to make sense of it, but it’s a beautiful idea).
Almost finished, but I have to explain a bit my attitude about UD. I am thorn between my curiosity about this, explained in other posts (for example by it’s partial overlap with the goals of Digital Materialization), and the fact that I don’t want this blog to be absorbed into this subject only. I have my ideas concerning a possible UD algorithm, especially from a math viewpoint, but unless I produce a program, I can’t know if I’m right or wrong (and I am not willing to try yet, because I am sympathetic with the underdog Dell and also because it would take me at least several months to get off the rust from my programming brain and I am not yet willing to spent real research time on this). Suppose I’m wrong, therefore, and let’s try to find it in a collaborative, open way. If we succeed then I would be very happy, in particular because it would get out of my mind.
chorasimilarity 
It doesn’t matter if you’re wrong, that’s the whole point of a collective discussion. You appear to be perfectly OK with everybody else arguing methods on here, but not yourself?
Good question for me. I believe I’m right, that’s why. But I don’t want to spoil the party and, much more important, my nose tells me that’s more to it, to better wait a bit. I don’t know why, exactly. Be sure though that if the solution which will emerge is related to mine, then I will not shy to write “I told you” and to link to the relevant posts where I suggested this bit and that bit. (Of course with all due congratulations for the author(s) of the solution and for their primacy for finding it and exposing it in a coherent way.)
I’m not OK with any arguing method, for example I just trashed a stupid comment on this post already. Even more, I don’t care about the arguing method, as long as it conveys some information (by definition of information versus noise, i.e. something previously unexpected).
I’m irrational, not a machine. Nose is a very important, albeit frequently discarded tool in research.
Hmmm I think, perhaps, that all the commentators you list above want you to join the discussion with them, rather than being the outside holding back. I think it’s time to stop telling us “I’m right” to actually exposing your ideas in the open, just like everybody else has done.
Maybe someone else can code up your idea, and see if it’s viable or not.
That’s fair if you want us to carry on, don’t you think?
OK, Dave, fair enough. I think the stumbling block for representing a 3D world like it is seen by a human on a 2D screen is that it is easy to represent in a database where everything is, for example by using an octree (which is basically the 3D equivalent of a positional number system), but it is costly to deal with the fan of rays emanating from a changing POV. That is where divisions and multiplications appear. Imagine that you want to represent the 3D world as seen from infinity, so that a POV is a family of parallel lines, going to infinity. Then it is very quick to solve the rendering problem, there is no division, multiplication, and scale is POV independent. It is easy because the octree structure is built that way. If you make a parallel projection of an octree on a plane then you get a quadtree, and so on. Now, suppose that you spend time to find out who’s in front from a particular POV and then you change the POV. There is not much you can use from what you already have, mainly because scale, in this conical projection, is POV dependent, so what you can use is at scales from which the change of POV is negligible.
So I wonder if there is a database structure for a 3D cloud of points for which changing the POV can be turned into translations in the database. Look at the Stoa Poikile picture from the Teaser 2D UD. This picture can be interpreted in two ways. The first is that it is a picture of a 3D cloud of points. By the effect of perspective, some parallel lines, like those vertical or horizontal, are represented as parallel in the picture, and a family of parallel lines, those going along the corridor, are represented in the picture as a fan of lines which converge at a point of infinity, seen in the picture as somewhere in the middle of the wall far way. The second interpretation of the same picture is that it represents a 2D world, along with a POV (the one in the middle of the wall), along with the fan of rays emanating from that POV. The information we have is the same in bot interpretations. But we can use the first interpretation as an organization principle for a database which makes easy the solving of the 2D UD problem. Suppose that you are a 2D creature, wanting to solve the 2D UD problem, consisting in fast rendering on a 1D screen (or a “squaremap”) the huge 2D world. How can you do it? You can build a 3D world, map your 2D points to the 3D world such that the rays from your POV (or any other POV in the 2D world) correspond in the 3D world you built to families of parallel lines. That’s basically my idea, where you have to add 1D to any of the dimensions above. So my suggestion is to build a 4D very sparse database, organized in a 4D equivalent of a quadtree, such that changing the POV in 3D amounts to translations in the 4D world (which is not perfectly possible but a good management of scales can do it).
So would the idea be a 4D database of homogeneous coordinates for a 3D projective space if I happen to glance over this right?
Even if I am wrong I can see the possible progression of this since I even played with plucker space for a period of time in rendering.
Yes, a projective space is a good idea!
Maybe of interest, if you go back to the comments at Digital materialization, euclideon and fractal image compression, Dave H. on jan 28, 2013, puts this video
and remarks that at 6:55, there are stripes which “look like perspective LOD bands”. In a sequent comment JX says “Yes, he’s definitely using octree but I want to notice, that stripes has strange U-, sometimes V-like form, they do not surround viewer, but the point far forward. “
Those stripes happen more so from old school techniques like perspective roto zooming. It happens because it creates false alignments as treating diagonals across a unit step is the same distance as an up-down/left-right step. In pixel unit space a diagonal of a square is the same pixel run count (length) as any one of the sides. I broke out a couple of samples but angle step size and perspective correction can be different.
But I do believe than the intensity of the shading is different lods.
Shea: “But I do believe than the intensity of the shading is different lods.” Could you tell us more?
Feel free to delete this as well, but I can see the train of through the map-territory relation that there is no difference.
Yes, no coordinates in the brain, no knowledge of euclidean geometry in the fly’s little brain (or our uneducated brain), but we are expert in manipulating space. Nature has a way to achieve this otherwise than by the map-territory idea. It’s not magic, for sure, we can understand it and will probably have many applications if we figure it out.
Great !
be nice a public wiki or other place for share information, for not mess the blog of Marius..
It’s OK, mess it. I like to stay informed, I’m curious how it unfolds. (Or tell me where you move to discuss, if you want to stay discrete then mail me to the gmail address). Thanks!
And yet massive copyright claims against publishing their data here doesn’t appear to bother you?
Dave H: “And yet massive copyright claims against publishing their data here doesn’t appear to bother you?”
Please explain what you mean, because I don’t understand.
I won’t comment on abstracts of concepts, as I’m strictly a computer algorithm guy. 🙂
But I will comment on the new video at the top.
The largest giveaway is in the slow connection demo starting at 12:30 – it’s probably best to watch it full screen. You can see the LOD cubes streaming in at about 1/4 mile square chunks. The load order appears random, but I’m guessing it’s simply the stream chunks arriving at different times over the server. Either that or it’s directly related to the octree winding, but it appears to be a different order each time it jumps to the correct resolution needed.
It could be that these LOD chunks have put a dampener on the cube-map idea, and it may be a version of the D. Meagher’s quadtree splatting after all. Damn it! ; )
If the data is stored as 1/4 or 1/2 mile chunks then the points could be stored in resolution increasing data lengths within those cubes.
So if a cube has 20000 points, the lowest resolution would be the first 500 bytes of data, for example, and next res could be the following 800 bytes, which would mean all file pointers stay in the correct location for the next resolution. This helps the streaming as the needed resolution is always in lengths of data from the start of each 1/4 mile block, rather than load each point separately which would mash the drive heads and slow down the whole access process.
I can’t gather much else from the video, apart from being amazed at the high resolution rendering of TWO frames for 3D, which is a massive step up from what they were showing before.
Based in the uds you said it looks to me like these could be a series of “2D planes”, in the sense of what you can see with the camera when you are there, and maybe the engine is just interpolating the points of a few of these planes every frame. This is done in constant time and checking for occlusion looks easy.
Thanks preda! Looking forward for interpretations of this.
It is funny you bring up row tracing since I am basically used that for the images I posted earlier but it is done by column since the volumetric info was a relief from the ground. It does not use a HOM, (since since it is just wave surfing) but kept just an incremented counter.
Dave the watermark is just a base64 encoded png image
I uploaded the logo on my folder, check it.
Question: in the UD movie, at 7:40, Dell says the pc converts 3.5 billion points/hour into the UD format. How many operations per point this means (rough estimate)?
Assuming 10^9 operations per second (I use this number at programming contests), that would be 1000 operations per point. If an octree is involved, with 22 levels, it reduces to about 50 per point per level.
Assuming a sequential disk read rate of 100MB/s and no writing (speed of my disk), this is 100 bytes per point (and 5 per point per level).
Assuming a disk seek rate of 200/sec (a very optimistic guess, common hard disks have a seek delay of 9ms), you need to process 4900 points between each seek.
With such numbers I don’t expect the conversion to do anything fancy.
What are the red marks meaning?
take in 0x3d87 a list of increment in block type 1 4bytes integer end with 0 0 and the same list in next block type 1 in 0x10bc9 other list with en in 0 0
this list is a subdivision of the block
There are a video of mountains (the eiden interview)show the access to disk in a bar, I incline to think in a octree because the first block have the coarse level (always in ram) and access to fine detail in next blocks.
26406 = 2 x 3 x 3 x 3 x 3 x 163
For 163 see this wiki page
Moreover, 440101 is prime. See Properties of 440101.
Erhm, nope.
Block size may be strictly dependent on model extension or size…
Also, the 440101 number of points is absolutely random.
btw the red marks are just patterns, they remind me of those green LOD bands:
I took it from your picture, where did you took it from?
Otherwise, I don’t think we are looking at a screen image or at a point cloud, it makes no sense, because either: (a) if we look at a 3d cloud point then this uds file is useless, that cannot be the UD database, OR (b) if we are looking at a part of the UD database, then why a pc needs an hour to convert 3.5 billion points?
appc23, you mean you picked at random a prime number with 6 digits? Possible, of course, but the chance for this is about 1/10.
I’m still writing down my idea of the unlimited detail algorithm, which I will post here when finished. While their database is fancy, I think that their algorithm would work equally well on a database that only stores an octree in a naive format. I also think that their algorithm is some fancy form of octree ray tracing, but with such a different technique that you might not recognize it.
I did not think that cubemaps and 5D-tree traversion would play a role, but it is funny how they pop up while figuring out the details of my algorithm.
A short summary of my algorithm: I have a fast query algorithm that returns the cubemap of the queried point, which is then rendered (with some optimization such that unrendered pixels are not queried). The query is performed by seeing each side of the cubemap as a quadtree and then traversing this quadtree and the octree simultaneously (which is where the 5D-tree traversal pops up).
The faces of the cubemap and the octree are both axis aligned. Which causes perspective correct interpolation to be exactly the same as linear interpolation. I can do this linear interpolation using a digital differential analyzer/bresenham-like algorithm. As such I can implement the cubemap query algorithm with only integer additions, subtractions and bitshifts. (Unless there is a catch, I’ve been wrong here before, thinking that the view itself could be queried with only cheap integer instructions.)
For each cubemap face I also keep track of a depth buffer in the form of a quadtree. This allows me to do perfect occlusion culling (rendering each pixel at most once and performing no other operations with respect to that pixel).
The algorithm kind of computes the cubemap by ray-tracing it, but the 5D-tree traversal bundles the rays as much as possible, hopefully giving the speed up that makes UD run in interactive frame rates. As John Carmack said, interactive sparse-octree ray-tracing is already possible as a demo, but will be practical in 5 years or so. Some smart optimization might cut that down to 0. Ray bundling might be that optimization.
[This was a sneak preview of my method. I hope to get the details up within a few days, despite that my graduation thesis (on the topic of probabilistic arithmetic and combinatorial optimization) needs my attention as well.]
Looking forward for it. Good luck with the thesis, also!
Ok, as promised: https://www.box.com/s/rxvvymcz4nfygvs6fz7a.
Thanks, interesting, looks viable, but is it that fast?
Ok, I’ve part of the implementation running: performing one of the 32 sub-queries, without screen space occlusion, its running at 8 fps or something with a resolution of 1024×768. The query fills about 70% of the screen, so with occlusion, performing all queries wont be much slower. No optimizations yet, so this seems promising. I’m astonished by how fast it already is.
Also the implementation is buggy as hell, but showing something resembling the loaded scenery. So therefore no screen shots.
Found an error in my document x2-x1>=2 must be x2-x1<=2.
A bit of archeology give me a nice web
in 1985 in comp.graphics.algorithms a guy called Youri VASSILIEF say about storing octree “sharing” nodes and he can store a 32K cubic voxels in 64kb !!!???
and then found this web (in russian)
http://www.enlight.ru/ib/tech/voxels/index.htm
I read about the traslator…
I was just a little concerned over the nature of that uds file. It’s Kimoto’s/Euclideon’s data that was pulled and then re-copied to a New Zealand ‘Mega’ file site. It’s their private data, and you’re publishing it here (in comments).
I’m not a lawyer, but I would be cautious. It’s really hard to know.
*shrugs* but I guess you can wait until they ask you to take it down!
I see, thank you Dave H. It’s not published here, in my opinion, there is (was?) only a link in a comment, but I am no expert on this kind of stuff. Is this a matter of real concern for anybody? Please let me know then.
Ha! OK, sorry it was the CR/LF that fooled me. I’m not sure where your “my folder” is?
It’s because Marius “took your advice seriously” and removed the comment with the link.
Oh well, I’m guessing this was the right thing to do anyway…
Probably best 🙂 There’s probably not much more guesswork we could do with it on here anyway.
Yes, sorry, I don’t want this blog to be blocked, because it has a nice name. But I welcome and I’m eager to see any open source proposal related to UD. Don’t forget to keep me informed about your thoughts, I suspect that thinking is still legally allowed.
Please excuse me preda, appc23 and Dave H, I took the advice by Dave H seriously and trashed some of your comments.
Cool! Thank you Tony!
Has temporal coherence caching been already discussed there? JX did it if I remember correctly to accelerate rendering but I could be wrong.
Some random pdfs on the subject:
Click to access scherzer.pdf
Click to access vis97.pdf
Click to access tempco.pdf