Home > Uncategorized > Discussion about how an UD algorithm might work

## Discussion about how an UD algorithm might work

I offer this post for discussions around UD type algorithms. I shall update this post, each time indicating the original comment with the suggested updates.

[The rule concerning comments on this blog is that the first time you comment, I have to aprove it. I keep the privilege of not accepting or deleting comments which are not constructive]

For other posts here on the subject of UD see the dedicated tag unlimited detail.

I propose you to start from this comment by JX, then we may work on it to make it clear (even for a mathematician). Thank you JX for this comment!

I arranged a bit the comment, [what is written between brackets is my comment]. I numbered each paragraph, for easiness.

Now I worked and thought enough to reveal all the details, lol. [see this comment by JX]
I may dissapoint you: there’s no much mathematics in what I did. JUST SOME VERY ROUGH BRUTE-FORCE TRICKS.

1) In short: I render cubemaps but not of pixels – it is cubemaps of 3d points visible from some center.

2) When camera is in that cubemap’s center – all points projected and no holes visible. When camera moves, the world realistically changes in perspective but holes count increases. I combine few snapshots at time to decrease holes count, I also use simple hole filling algorithm. My hole filling algorithm sometimes gives same artifacts as in non-cropped UD videos (bottom and right sides) .

[source JX #2]   ( link to the artifacts image )this artifacts can be received after appliying hole-filling algorithm from left to right and then from top to the bottom, this why they appear only on right and bottom sides. Another case is viewport clipping of groups of points arranged into grid: link from my old experiment with such groups.

This confirms that UD has holes too and his claim “exactly one point for each pixel” isn’t true.
3) I used words “special”, “way”, “algorithm” etc just to fog the truth a bit. And there is some problems (with disk space) which doesn’t really bother UD as I understand. [that's why they moved to geospatial industry] So probably my idea is very far from UD’s secret. Yes, it allows to render huge point clouds but it is stupid and I’m sure now it was done before. Maybe there is possibility to take some ideas from my engine and improve them, so here is the explanation:
4) Yes, I too started this project with this idea: “indexing is the key”. You say to the database: “camera position is XYZ, give me the points”. And there’s files in database with separated points, database just picks up few files and gives them to you. It just can’t be slow. It only may be very heavy-weight (impossible to store such many “panoramas”) .

5) I found that instead of keeping _screen pixels_ (like for panoramas) for each millimeter of camera position it is possible to keep actual _point coordinates_ (like single laser scanner frame) and project them again and again while camera moves and fill holes with other points and camera step between those files may be far bigger than millimeters (like for stereo-pairs to see volumetric image you only need two distant “snapshots”).

6) By “points linked with each other” I meant bunch of points linked to the some central points. (by points I mean _visible_ points from central point).

7) What is central point? Consider this as laser scanner frame. Scanner is static and catches points around itself. Point density near scanner is high and vice versa.

8) So again: my engine just switches gradually between virtual “scanner” snapshots of points relative to some center. During real-time presentation, for each frame a few snapshots are  projected, more points projected from the nearest, less from far snapshots.

9) Total point count isn’t very big, so real-time isn’t impossible. Some holes appear, simple algorithm fills them using only color and z-buffer data.
10) I receive frames(or snapshots) by projecting all the points using perspective matrix, I use fov 90, 256×256 or 512×512 point buffer (like z-buffer but it stores relative (to the scanner) point position XYZ).

11) I do this six times to receive cubemap. Maximum points in the frame is 512x512x6. I can easily do color interpolation for the overlapped points. I don’t pick color of the point from one place. This makes data interleaved and repeated.

12) Next functions allow me to compress point coordinates in snapshots to the 16bit values. Why it works – because we don’t need big precision for distant points, they often don’t change screen position while being moved by small steps.

int32_t expand(int16_t x, float y)
{
int8_t sign = 1;
if (x<0) { sign = -1; x = -x; }
return (x+x*(x*y))*sign;
}

int16_t shrink(int32_t z, float y)
{
int8_t sign = 1;
if (z<0) { sign = -1; z = -z; }
return ((sqrtf(4*y*z+1)-1)/(2*y))*sign;
}

13) I also compress colors to 16bit. I also compress normals to one 24bit value. I also add shader number (8bit) to the point. So one point in snapshot consists of:  16bit*3 position + 24bit normal + 16bit color + 8bit shader.

14) There must be some ways to compress it more (store colors in texture (lossy jpeg), make some points to share shader and normals). Uncompressed snapshot full of points (this may be indoor snapshot) 512x512x6 = 18Mb , 256x256x6 = 4,5Mb

Of course, after lzma compression (engine reads directly from ulzma output, which is fast) it can be up to 10 times smaller, but sometimes only 2-3 times. AND THIS IS A PROBLEM. I’m afraid, UD has smarter way to index it’s data.

For 320×240 screen resolution 512×512 is enough, 256×256 too, but there will be more holes and quality will suffer.

To summarize engine’s workflow:

15) Snapshot building stage. Render all scene points (any speed-up may be used here: octrees or, what I currently use: dynamic point skipping according to last point distance to the camera) to snapshots and compress them. Step between snapshots increases data weight AND rendering time AND quality. There’s no much sense to make step like 1 point. Or even 100 points. After this, scene is no longer needed or I should say scene won’t be used for realtime rendering.

16) Rendering stage. Load nearest snapshots to the camera and project points from them (more points for closer snapshots, less for distant. 1 main snapshot + ~6-8 additional used at time. (I am still not sure about this scheme and changing it often). Backfa..point culling applied. Shaders applied. Fill holes. Constantly update snapshots array according to the camera position.

17) If I restrict camera positions, it is possible to “compress” huge point cloud level into relatively small database. But in other cases my database will be many times greater than original point cloud scene. [ See comments   JX#2  , JX#3 , chorasimilarity#4 , chorasimilarity#5 . Here is an eye-candy image of an experiment by JX, see JX#2:]

Next development steps may be:

18) dynamic camera step during snapshot building (It may be better to do more steps when more points closer to camera (simple to count during projection) and less steps when camera in air above the island, for example),

19) better snapshot compression (jpeg, maybe delta-coding for points), octree involvement during snapshot building.

20) But as I realized disk memory problems, my interest is falling.

Any questions?

1. January 19, 2013 at 9:06 am | #1

Re: 12) Dell mentions in an interview that he’s doing only addition operations, you have multiplications and square roots.

Re: 17) In the comments on the video by AEROmetrex mentioned here, they say “For a 15Gb 3D model the Euclideon Unlimited Format file is about 2 Gb”. The implication is that the UD database is smaller than the original one.

See also my question here where I speculate that it might be possible to compress M points in O(log(M)) space, by analogy with numbers. I shall come back to this, but the idea is to use a kind of geometric positional system see here. If you think about this, the reason that you can store a number N in O(log(N)) space is because you use a positional system notation. Why not for configurations of points in space?

2. January 19, 2013 at 7:47 pm | #2

“expand” and “shrink” functions is just part of my “compression algorithm”, they are not necessary on each frame, it is possible to compute them after loading the snapshot into memory.
but multiplications (and one division) is still used inside projection function (the most power-consuming part of my engine during reatime rendering):
const float tx=x-camx, ty=y-camy, tz=z-camz;
newx = tx * cosyaw + tz * sinyaw;
newz0=-tx * sinyaw + tz * cosyaw;
newy = ty * cospitch – newz0 * sinpitch;
newz = ty * sinpitch + newz0 * cospitch;
if (newzMAX_DIST) return;
nfov = FOV/newz;
screen_x = HALF_WIDTH + newx * nfov;
screen_y = HALF_HEIGHT – newy * nfov;
(cos/sins computed only once after camera motion)

I believe _there are_ muls and divs in UD (it is ridiculous to avoid them EVERYWHERE, how you do fog without them for example?), just _not in extracting-points-from-database part_ (I think, Dell spoke about that part when said about divisions (did he said about multiplications too?), yes in that part you may not use trig or complex formulas, you don’t need to, because it is just database query thing.
Assumption: Dell puts points taken from database into octree and then traverses it somehow, this would really allow him not to use trigonometry at all.
But if you had limited bunch of 3d points (only visible points), projection of these points isn’t such a big issue. Issue is how to get that points.

Re: 2) link to the artifacts image: http://www.gamedev.ru/files/images/zubchiki.png
this artifacts can be received after appliying hole-filling algorigthm from left to right and then from top to the bottom, this why they appear only on right and bottom sides
another case is viewport clipping of groups of points arranged into grid:
link from my old experiment with such groups: http://www.gamedev.ru/files/images/artifacts.jpg

Re: 17) Fractal compression is too smart for me now, I need to read about it more. I think indexing just must be smarter.
About groups. New (and at the same time old) idea:
What if we should index not each specific points but just pointer to the bunch of points? This can drastically decrease snapshot size (and maybe the whole indexing process) and instead of repeated data database will split into 1) small snapshots (indexes) and 2) actual, unique data: groups of points that can be shared between different snapshots. During rendering sampling depth of each group will depend on distance from camera to that group, sorting by Z-order curve will help to organize points in groups so skipping will keep objects uniform (don’t know how to do color interpolation in this case, maybe some color overhead information added to each group). I had experiments with groups and skipping, here is image:
http://file.oboz.ua/files/vf5058893390b80_2012918174611.png
and achieved realtime (3-10 fps). actually it was _one_ big “snapshot” assembled from small groups of points (grass, rocks and plane), total point count is over 2 billion. here is this demo: https://www.dropbox.com/s/f0w4p0ocnxn6tfd/arch.tar.gz (if it says “std-bad_alloc”, try to move it into path without spaces and unicode. this is for windows, but works fine under wine).
using many small snapshots for many camera positions containing pointers to groups of points rendering speed can be easily increased and this indexes won’t be as big as my current brute-force snapshots. I’d say up to million times smaller. using Z-ordering we don’t need to load distant groups of points fully, just read some bytes from head of files. there also might be pointers to group of pointers to group of points etc.

3. January 19, 2013 at 7:57 pm | #3

P.S. in this demo i didn’t used z-ordering so quality of skipping is really bad.
Also look carefully at the sides, I’d say this artifcats are almost identical to the artifacts in UD video: http://www.youtube.com/watch?feature=player_detailpage&v=THaam5mwIR8#t=58s

The reason of that artifacts is: skipping.

4. January 19, 2013 at 9:19 pm | #4

Re: 17) that is not usual fractal compression. Look, the number 123 means that we are in the country 100, in the city 20 and on the street 3. Likewise, I am in the country Romania, the city Bucharest and the street Vasile Lascar. That is easy to set. What is more subtle is how to use this to determine relative positions between points. In terms of numbers this correspond to taking the difference of two numbers, where you have a nontrivial algorithm concerning carrying digits. I can imagine similar algorithms for positions, but until now I was interested only in noncommutative groups (instead of the commutative group of integers) and in this case I have not solved completely the problem. BUT, regardless what I am looking for, IF there is a way to represent positions in space in the same way as we represent numbers by using digits (such that there is an algorithm for finding relative position similar to difference of integers, THEN it means that really there are ways to represent, maybe within a given approximation, the configuration of M points in 3D in O(log(3M)) = O(log(M)) space. Does Dell have such an algorithm?

Re: muls and divs in UD, agree with your explanation.

5. January 19, 2013 at 10:36 pm | #5

OK, I read more carefully your comment here #2. Looks we write about the same thing re:17). [ADDED LATER: can you make sense of these slides, by using arxiv:1107.2817?] I have to think and parse what you are saying. BTW, I sent a mail to Bruce Dell, to invite him to comment, will he? Another hypothesis of mine is that he seems to have difficulties with his patent applications because is just about a trivial (after having the right ideas) solution to a problem like 17). Is just math! But the right math may be trivial and simultaneously can do wonders, like the idea of positional number system, which is younger than the romans and greeks, for example.

6. January 20, 2013 at 1:55 pm | #6

Re: 17) Take a look at The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing, Nir Goldschmidt, Dan Gordon , 2007

Re: 16) “fill holes”. Googling “natural images” “hole filling algorithm” I got lots of things, some among them related to Eero Simoncelli, but the most simple idea of filling holes like those appearing in your algorithm is the following. In the preprocessing of the database, run several times an algorithm to collect a library of the most frequent 8X8 images. Alternatively, just use such libraries which are available on the net for “natural images” (this is what our brains are trained to easily understand). To find those google “natural image statistics”. Then use these to fill holes, by the most simple convolution (i.e. averaging) algorithm, applied to the cubemap you got. If you arrive to do this faster than 5 times per second then you are done, I guess, because your (JX) UD algorithm is already using a huge database of 3D points, contrary to the problems the researchers in computer vision seem to be interested in solving (typically they have a corrupted image which they want to enhance; you have a too much detailed image which you want to make more eye-friendly).

Incidentally, during googling on natural image statistics I found citations which attribute to David Marr the comparison between image representation and numbers representation, but I have not yet seen the exact context.

7. January 21, 2013 at 12:04 am | #7

algorithm description: http://s14.postimage.org/3wmswzw6p/holes.png
usage example before-after: http://s14.postimage.org/4kr2275ip/holes2.png

I’ve read your slides about but unfortunately I am not mathematician at all so didn’t understood it well. Is this just about setting new origins and scales for some areas to use smaller numbers in relative(local) coordinates instead of using global coordinates for every point? If it is, this really can help to save memory a little. Or it is about dynamic changing of details level? Octree volumes has such feature.
About Dell – don’t think he’s ready to share his secrets yet – he didn’t even released the public demo he promised.
His company, Euclideon has patents too: http://www.ipaustralia.com.au/applicant/euclideon-pty-ltd/patents/
One of them says about octrees. On the official site we still can read about single point for every pixel: “technology efficiently grabs only one point for every screen pixel” – this really can be done with octrees and it is not very big innovation. The problem of octrees is high memory consumption and slow speed. Maybe Dell added seamlessly loading and unloading nodes on the fly (indexing like mine could be used to achieve this). But such scheme still may be slow (due to delay in random seek in disk access) and therefore will depend on detail level.

I’m confused about UD. What is clear for me:
- pre-processing (data sorting and indexing) is important and long stage, UD can’t work with raw point cloud data
- purpose of sorting – to load needed points faster. I can’t think how to go without repetitions here. loading of one point is slow process, loading by groups may be faster, but not infinitely.
- purpose of indexing – to know what data to load depending on camera position

What is not clear:
- why there was that saw-like artifacts? this doesn’t fit well with “one point for every screen pixel”. if it was point skipping, maybe that means, UD receives excessive information?
- another artifact seen in that video (same link above) – when camera moves, some small objects, or shadows is changing. I don’t know what it mean, but it looks like changing between “snapshots” of different points. this means data is repeated many times in different variations to be accessed faster, but as I realized such snapshots is impossible due to their high memory usage, there must be some tricky compression to allow this.

I give up for now.

8. January 21, 2013 at 8:00 am | #8

Apparently now is Euclideon International, there is also an US based part of Euclideon (found by searching for #Euclideon on G+). Is this true or not? Are there any US patents?

Re: JX#7, I looked for your presence on forums too, unfortunately I don’t speak russian, but google translate helps. I was intrigued by some efforts to understand space which look to me familiar. I do hope you and your fellows continue and bring fresh ideas. The main thing is to rely at a minimum on coordinates, global or relative. You may use them to design the right database, but not for exploiting the database, this is a sound principle. Excuse me if I seem inappropriate, I don’t want to give uncalled advices, it is a matter which interests me most. Think that the brain never ever uses coordinates in vision. So: no geometrical expertize on the side of making sense from the database, looks extreme but is not.

9. January 21, 2013 at 10:34 pm | #9

JX, I got it right? Your cubemaps allow to decouple rotations from translations. If you stay in a point and rotate, it’s just a cubemap panorama, easy to do. Now, suppose you translate in one direction. Then you compress your successive cubemaps like if it’s a movie, right? At the end is just a 2D movie (translations in 2 directions, or 3, whatever). That is the idea, simple put?

10. January 22, 2013 at 1:40 am | #10

Yes, you’ve got it.

However my cubemaps (I call them snapshots) is not images now, it’s just lists of points, so it is hard to compress them that way (as movie), but that can be reorganized:

instead of keeping rgbxyz for each point in snapshot I may save cube face’s colors as textures add additional channel to them, this channel will represent depth. Having that depth it is possible (haven’t checked this yet though) to warp points while camera moves to the next such cubemap and to have more-or-less correct zbuffer (to combine cubemaps with animated polygons, for example).

Having all info as digital images it is possible to:
compress them (lossy, as jpegs)
and to make use of similarities between near cubemaps compress them even more as movie: http://en.wikipedia.org/wiki/Motion_compensation

Looking on movie file sizes I can predict one such cubemap will weight around 128kBytes for HD screen format.
Yes, such system will be unlimited in terms of processing power and detail level, and it can be easily streamed from one server to many computers inside local network.
But it is suitable only for some small (and definitely static) worlds and Dell with his 1km^2 island on a laptop has obviously much more effective system regarding compression and pre-processing time.

Even with 25cm gap betwen cubemaps and with one axis locked for camera it will be arleady ~2TB for Dell’s island.
Not to mention powerful render-farm will be required to prepare that cubemaps in adequate time.
To unlock axis to allow camera fly as high as, say, 50m above that island – we’ll need ~400TB. (for comparison: UD now has limit: 140TB).

Dell also mentioned that he can apply changes to the world (words about “footprints in the sand”) and it is impossible to interactively apply such changes to all the cubemaps.
But as I said before, I am confused about UD due to glitches seen in his videos, because they may point to usage of cubemaps rendered in different time with different lighting setup.

11. January 22, 2013 at 6:22 am | #11

Re: JX#10. I see. So, in my slides Y is your cubemap or snapshot, X is the initial “laser scanned” database, maps are database queries. The relative maps are what you get when you combine two database queries, either at different scales but the same viewpoint, or same scale but different viewpoints. I have also supposed that you have cubemaps at several scales and exploit this. My problem is how to compress these data (i.e. the “maps”) efficiently, that is why I am interested in UD since it’s first announcement. And my point is that you don’t need to have so much brute data, take instead as objects of interest the queries themselves and exploit the fact that they are redundant because are maps of same X. Therefore they satisfy lots of constraints which could be used to program with them as primitives. That’s “computing with space”. But I am no programmer, used to do numerical programming long time ago, lately not. So I took lambda calculus and tried to add these “maps” (which are really database queries as I told before) as primitives, and now I got this graphic lambda calculus. But there is a long way, instead you and many others may have more straightforward ideas.

I shall think and make a proposal for editing this “Discussion” page to make it more clear. Otherwise, you may come to the light, give your real name and advertize yourself, if you wish.

12. January 22, 2013 at 12:17 pm | #12

Re: JX#10. Is too funny. Look VERY CAREFULLY at Daguerre Dioramas and also look at Myriorama. So you say that Dell makes us see dioramas of the geospatial data. In the case of the island, is a myriorama.
What do you think?

13. February 7, 2013 at 7:38 pm | #13

I found this today, it’s from Siggraph ’98.
You load and play with LDI’s (layered Depth Images) – they have some strange errors down the sides of the screen when zoomed in….. : )

14. February 7, 2013 at 7:50 pm | #16

Dave H., nice, I shall look over!

15. February 7, 2013 at 8:39 pm | #17

Dave H. yes, is part of the puzzle. I’ve read the paper, is full of hints. Also LOL stuff like “The model of the chestnut tree seen in the color images was too complex to sample with a pure stochastic method on a machine with 320MB of memory.” That was in ’98.
Now, they don’t put this as a search problem in their database of LDI, their sprites are JX’s cubemaps, they reason correctly in 4D but they don’t make the connection with perspective view in 4D which transforms the changing of the POV in 3D into a matter of applying translations, nor do they use any octree like compression of their database.

• February 7, 2013 at 9:10 pm | #18

Hi, yeah I thought it was interesting, and strangely slow.
Some problems I have with the cubemap idea:
What happens if your have, say, 25 trees all in a line, with 24 obscured from the camera snapshot? I can understand that you can easily use the same projection using neighbouring cubes, but there’s another problem. What happens if there’s a deep hole in a wall, but no camera sees straight down it to record the holes sides?
There are ways around the latter by having two layers, the second being the first object removed therefore revealing the hole. You’ll have to project both layers though.
All this ‘fixing’ seems like it may add special problem areas, or too much data is needed to be practical.
I’ve figured out a few more things, but I’ll test them first if I have the time.

• February 7, 2013 at 9:27 pm | #19

Dave, you have to separate the rendering problem in two parts: the slow one, which you do before when you prepare the database, the fast part, where you exploit the database. In the slow part JX says that you prepare the database so that you can retrieve fast (later) the 3D points needed for the cubemap, so for your hole example it just means that some cubemaps may need more 3D points than others. What I believe is that you don’t really need the 3D points, but only the “voxels”, at the corect scale, which make an impression on the pixels of the cubemap. So the layers I suggest are not in 3D, they are in 4D and they are simply made by the “voxels” at a given scale. When you compress the database of 3D points you may use an octree system, only that the childs are not inside the parent, they are translated with a certain amount which is a function of their scale. So, these layers do not contain more information than the original database of 3D points, but (much) less. Coming back to your hole example, if the hole is small compared to the image then you simply do not see it. If it is big, then there is not so much difference of data needed to fill it when you change the POV.

• February 8, 2013 at 4:44 am | #20

I think you maybe over complicating it, and that you don’t understand how fast Dell renders those pixels on a laptop, there can’t much happening per pixel, as well as a very impressive anti-aliasing rendering at that. So perhaps he’s using image warping like Microsoft’s research into IBR? Anti-aliasing means that he’s storing the cube map at massive resolutions to follow the trend in thinking here, which is a bit confusing.

• February 8, 2013 at 3:18 pm | #21

chorasimilarity :
Dave, you have to separate the rendering problem in two parts: the slow one, which you do before when you prepare the database, the fast part, where you exploit the database. In the slow part JX says that you prepare the database so that you can retrieve fast (later) the 3D points needed for the cubemap, so for your hole example it just means that some cubemaps may need more 3D points than others. What I believe is that you don’t really need the 3D points, but only the “voxels”, at the corect scale, which make an impression on the pixels of the cubemap. So the layers I suggest are not in 3D, they are in 4D and they are simply made by the “voxels” at a given scale. When you compress the database of 3D points you may use an octree system, only that the childs are not inside the parent, they are translated with a certain amount which is a function of their scale. So, these layers do not contain more information than the original database of 3D points, but (much) less. Coming back to your hole example, if the hole is small compared to the image then you simply do not see it. If it is big, then there is not so much difference of data needed to fill it when you change the POV.

I fully understand that image-space rendering decouples the geometric complexity of the 3D data from the run-time of the rendering algorithm. My issue is the amount of data in doing so, remember you can go in between leaves of a tree which will need many, many small cubes to produce all of the POV projections.
Lets say a cube’s side is 1024×1024, even if it needs to be higher because each side is a 90 degree FOV, which is way higher than normal viewing angles. And he’s got anti-aliasing so it would be far higher.
The six sides are 6×4 MB in size, as I’ve found a way to compress each pixel down to 4 bytes containing position and colour information.
It’s possible the image data could be compressed with a lossy jpeg compression, which may give 60:1 compression in places, but Z information cannot be lossy compressed and will need something like ZLIB or something more suited for depth map specific data. So lets have a guess at around 500K for each POV, and that’s being really generous as it’s only represents the first visible parts of the projection from that point.
Close to, and around every renderable surface are millions of these POV projections, down every crevice and behind every leaf, and their ‘island’ is massive.
They say that the repeating objects are not instances, so they couldn’t instance the POV for each one, although that’s an interest idea! : ) Perhaps they lied about instancing.

Having said all that, I’m going to have a go and see if it works in practice with my own take on image-based rendering – wish me luck!
I’ll use a fractal ‘Mandelbulb’, which is a good test as it’s a highly complex space – and should look spectacular if it works.
Imagine flying around this in real-time on a basic computer:

That would be amazing, but it worries me why Euclideon haven’t done that themselves.

I can’t say when I’ll get it running, but I’ll get back here with a demo if it’s a practical solution.
( Or, perhaps I’ll just hide away for 8 years like Euclideon…

16. February 8, 2013 at 3:35 pm | #22

Sorry, wrong vid!

17. February 8, 2013 at 3:51 pm | #23

18. February 8, 2013 at 4:15 pm | #24

I’m just generally commenting on why it takes up a lot of memory and explained why I think so. That’s a comment that JX made before saying he or she is giving up on the idea.
After ALL that I said, you just picked up on ” Perhaps they lied about instancing.” explaining why, and you ran me into the ground with it.
I’lll not post any ideas on here again.

• February 8, 2013 at 4:48 pm | #25

My understanding is: JX proposes to prepare the database so that it is easy to find fast the needed points for a particular cubemap. Besides, not stressed enough maybe, to put the problem as cubemap rendering decouples rotations from translations.
When it comes to lies, what I think is that the UD algorithm is a solution to the problem: you have a database of N coloured 3D points, construct another database which allows you to render a POV on M pixels in time O(M log N). So notice, I don’t say O(M), I am clement and say O(M log N), which I believe is the truth. Be it so, it is already a huge advance with respect to O(M poly(N)), which is known.
Finally, don’t get upset, that’s how mathematicians speak. We spend our time claiming the partner of discussion is stupid (actually we use words like “the proof is trivial”, or “is obvious that…”) and we are OK about being declared stupid when supporting evidence is produced.

19. February 8, 2013 at 5:10 pm | #26

It takes a LOT of memory as JX admitted, but I found ways of reducing the data size from his estimates (you don’t need the X & Y coordinates for example, just the depth).
Anyway, we do appear to be talking about two slightly different solutions.
I’m going to test my idea by writing the code – it’s the only way. ; )

20. February 12, 2013 at 9:28 am | #27

About lies: it seems they don’t need to use instancing, just look at their Geoverse, at the new pictures on their updated site. Geoverse has clients already (they posted screenshots on Ausgamers forum). Also look at AeroMetrex (it uses UD technology). Instancing was possible with island demo but not with lidar data.

THEY HAS SMARTER IDEA THAN CUBEMAPS
There is a statement on updated site: UD format compression is ~5-20% from LAS. (LAS is binary xyzrgb, correct me if I’m wrong). It’s not very surprising: known compression algorithms will do same job. But this also means that there is at least no overhead in size after indexing. So obviously Dell found more elegant way to index data than simple depth-cubemaps with lots of repetitions, but I am still sure main concept lays in indexing and main essential feature of such indexed data is possibility of streaming, you should keep searching in that direction. I described idea about storing only depth (jpeg image layer + depth later) above, this can truly reduce cubemap size, but it is not the solution.

EXAMPLE OF SMARTER IDEA
I repeat my another idea from above: maybe instead of storing individual pixels in cubemap it is better to store only _links_ to the whole _groups_ of points. And sort that groups of points using Z-order to allow to read only headers for groups far from camera.
This will decrease snapshot size, increase indexing speed and also will give excessive data to input (problem with deep hole in the wall will be solved because of that). Then during projection stage excessive points may be _skipped_ depending on error accumulation (type of errors: a) if point projected to the same screen coordinates, b) if point projected outside of screen, c) if point projected and can’t pass Z-buffer). By the way let me again recall saw-like artifacts from early UD videos – _skipping_ gave me same artifacts. My demo with gray stones uses almost similar approach.

• February 13, 2013 at 7:06 am | #28

Thanks JX, what I think is that they use instancing on their island (because everything is on a laptop) and they don’t need to use instancing in Geoverse.

21. February 13, 2013 at 12:45 pm | #29

They use instancing on that island demo because it had to be compiled by hand. In a way it highlights the human effort to create such places. A difficult one for the gaming industry to pay for of course.

The laptop he uses is a ‘gaming’ machine with plenty of storage. Specs:-
http://www.asus.com/Notebooks_Ultrabooks/G73SW/#specifications

I think it still uses pre-rendered ‘bubbles’ or cubes because of two extreme things it appears to do:
1. Anti-aliasing. This cannot be dismissed as it doubles or quadruples your data search.
2. It loads any part of the scene in under a second.
Their new web page page is up, stating this boldly:

http://www.euclideon.com/

Dave

• February 13, 2013 at 1:31 pm | #30

Thanks Dave, I agree with both comments. I shall take a look at the euclideon page!

22. February 13, 2013 at 12:58 pm | #31

To quote their web page:-

“Euclideon’s Unlimited Detail technology, used in its Geoverse software, is based on the concept of atoms in 3D space – that is, storing objects as collections of 3D pixels. This is a better way of representing real-world objects, as it doesn’t ‘fill in’ objects with homogenous textures and repetitive shapes. Rather, it represents every pixel of a scanned object just as it appears in the real world.”

Hmmm – “collections of 3D pixels”… That implies screen pixels, doesn’t it?

23. April 8, 2013 at 9:06 am | #32

Related to the topic:

These were obtained by harassing the author. Let him be thanked.

Shabtronic invented a super fast octree renderer related to an approach of Meagher’s: Unlimited Detail-like (the video featuring yellow mice).

I am under the impression that NVIDIA & others are paying (grants) money-loving/Mammon-worshipping researchers to investigate techniques (raycasting) that are hopeless without a GPU. Really, why would one go the image-order way is inexplicable.

• April 8, 2013 at 11:46 am | #33

Thanks for the links to the articles. I shall read them all!

24. April 8, 2013 at 12:16 pm | #34

I wouldn’t say ‘Shabtronic’ invented it, as Donald Meagher patents are dated over 25 years ago, but he does kindly give away some source code. These methods still require a lot of overdraw because individual objects are splatted from an octree, which has to be traversed into the distance. Seems unlikely to me, IMHO. And of course these objects are NOT unlimited in detail, only an image based solution has that quality. But who knows!
Thanks for finding these documents. Until researching an image based solution, I always thought that’s how UD was done especially as Meagher told me Dell had approached him at a trade fair once – probably just mutual interest rather than anything else though… ; )

• April 8, 2013 at 12:25 pm | #35

Good points Dave H. Btw, I would not mind if you take your time and detail even more, systematically, your method. I read it with more attention and what impressed me most was that is not viewer-centered, but viewed-object centered.

25. April 8, 2013 at 3:21 pm | #36

Meagher’s algorithm number 1 is a back-to-front octree splatter. However, his algorithm number 2 projects octrees on an occlusion quadtree, in a front-to-back traversal. So overdraw is avoided. (His algorithm number 3 is very beautiful).

Dell’s patent is about an alternate method for the rejection of octrees (Meagher’s non-alternate method is to reject those octrees whose projection falls only on black/full quadtree nodes).

Ned Greene’s Hierarchical Z-buffer is but a reformulation of Meagher’s algorithm number 2.

• April 8, 2013 at 6:07 pm | #37

Interesting, but that doesn’t explain ‘unlimited detail.’ The limit is based on the resolution of the original object.
If I’m looking at a low camera shot through a field of grass stems, would it have to project and render all the octree boxes down that line that occupy a tree? Isn’t that quite expensive? I’ll look at Green’s work, thanks for the heads-up.

• April 8, 2013 at 7:35 pm | #38

That’s were, in a sense, Meagher-like renderers are optimal.
Not only is solely the visible surface rendered, whole occluded subtrees being rejected and no octree re-traversed (unlike image-order algorithms), but one does not even descend those that aren’t occluded deeper than necessary: when your octree’s projection is small enough, stop. (That’s how a speedup was obtained in VD. But VD doesn’t project, it works in object space: no / or *).

General: http://design.osu.edu/carlson/history/PDFs/clark-vis-surface.pdf
R. A. Schumacker seems to have the priority here.

How is your image-based (!= image-order) renderer progressing? As for JX, I took the liberty to extend my harassment to him: he’s so busy that he cannot so much as think about UD; as soon as he’s done, he’ll return to it.

• April 8, 2013 at 7:43 pm | #39

Hi there, 17genr, you do have a point here ” works in object space: no / or *”, but pls no appeal to authority on this blog. Dave H. question with the grass blades is very good!

• April 8, 2013 at 8:31 pm | #40

Very cool the paper by Clark, thanks 17genr!

• April 8, 2013 at 8:39 pm | #41

One more, short. You can actually * or / by powers of 2 relative to the POV (if you have everything in base 2), as well you can do fast estimates of the relevant digits by using carry free addition algorithms.

26. April 8, 2013 at 9:26 pm | #42

> You can actually * or / by powers of 2 relative to the POV (if you have everything in base 2)

I abuse of that: there are SHLs, SARs & SHRs all over the .C

Why is nobody, except a very few, contributing? Trotskyist Defeatism/effeminacy? Chorasimilarity, please be an example: implement or describe your idea.

Rules: a novel traversal of an octree-style data structure that doesn’t re-traverse subtrees (hence no inexplicably popular raycasting/marching etc.); no * or /; no floats; about one page long .C function; Cache-oblivious.

I’ll keep quiet for a while now.

27. April 9, 2013 at 4:42 am | #43

People use past knowledge to influence their judgements. The phrase unlimited detail, if understood, means specifically that. Extrapolating reveals it’s a mass 3d to 2d translation, in pre-processing. It’s late, I’ll post some links tomorrow.

28. April 9, 2013 at 7:17 am | #44
29. April 9, 2013 at 2:51 pm | #45

That ‘skull’ runs really slowly in full screen, and I don’t understand how something that was invented 25 years ago could run so slowly now, the screen resolution can’t be the only reason.
Now try imagine running an entire dirt particle covered, palm tree strewn, grassy landscape, filled with millions and millions of leaves with that software? Logic dictates it’s something else, sorry.
I’m more and more believing UD must be some kind of pre-rendered 2D image warping. But how?

30. April 9, 2013 at 2:58 pm | #46

I found this yesterday, it feels like I’m getting closer to UD when reading it:
“Multiple-Center-of-Projection Images”

Anybody else agree? Or is this miles out. It’s an interesting article anyway.

• April 9, 2013 at 3:11 pm | #47

I shall read it, but you made me ask if anybody considered a system based on two POVs (like two eyes). The idea is that a point in space is uniquely determined by the positions it’s image on two screens occupy. In 3D means that you associate to a point in space two pairs of coordinates in screen pixels space. From these you can estimate fast the “level of distance”, hence the detail you need to see, as well as you can sort points by using one pair of coordinates (which defines a ray) and sorting w.r.t. the “level of distance” to find which point is visible. Finally when you move, you keep one POV fixed and you move with the second, then move the second and you keep the first. The pre-processing of the database would consist in a octree-style presentation of the scene, as in Clarke paper (and not an absolute coordinates based octree), with points coordinates given in screen pixels coordinates for two POVs.

UPDATE: cool paper!

31. April 9, 2013 at 3:30 pm | #48

I’m sorry probably I was posting on a abandoned thread.
I posted on the “UD challenge, most easy formulation” thread my idea for the UD functioning.
Fully computed in CPU and with O(1) time complexity.

My latest demo can be found here:
http://www.mediafire.com/?38rs08p9a8rrnig

Should I repost everything there for clarity? I still need feedback.

• April 9, 2013 at 3:32 pm | #49

Don’t worry, it’s visible, from the stats I can grasp. My last comment was also directed at you, have you seen it?

• April 9, 2013 at 3:52 pm | #50

Well I replyed to comment 35 so yeah thanks.
I was having connection issues so I couldn’t keep track of newer threads. Damn.

32. April 9, 2013 at 10:12 pm | #51

An issue with IBR is that Euclideon did not censor, on their facebook wall, a link to JX’s presentation on this blog. On the other hand VD’s traversal appears to have been blocked.

I believe that UD works like Quake except that 0) substitute octrees for BSPs and 1) you have AVS (actually visible sets), determined on the fly, instead of Quake’s precomputed PVS.

VD achieves that without /, * or floats. Too bad I’m no good programmer to make it fast.

How can somebody still use raycasting/image-order algorithms after this
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.397
and this
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1295

Malevolent design.

• April 9, 2013 at 10:44 pm | #52

17genr, about “An issue with IBR is that Euclideon did not censor, on their facebook wall, a link to JX’s presentation on this blog.”
What is IBR?
What were they saying about JX’s presentation?

33. April 9, 2013 at 11:12 pm | #53

IBR = Image-based rendering (what D. Hoskins is investigating).
There’s a link, on Euclideon’s facebook wall, to your blog by “Steven Mark Rose” where JX’s effort is mentioned.

By the way, JX’s technique is not unlike having a regular grid where to each cell there corresponds an AAVS (almost actually visible set) of points (those visible from a certain point of the cell, say the center). These AAVS can be made rather small: associate (injection) to each point of the world an integer i. Then bit i of a cell’s AAVS = 1 means it’s visible from (the center of) that cell, otherwise not visible. There should be lots of 0s.

• April 9, 2013 at 11:16 pm | #54

Yes, you’re right about JX. There is more though to it, you also need to have “points” with a scale, there’s no need to have invisible detail to handle.
I have put a new post on UD, dedicated to discussions, for the moment, this one starts to be hard to follow.

34. April 10, 2013 at 3:22 am | #55

Here’s a good link, it is also impossible to implement this patent. Controversial I know but the data required to stream this is enormous, it appears that Nintendo are covering an idea that did not really pan out because it’s not properly thought through. You really need to read it to know what I mean.
http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220040222988%22.PGNR.&OS=DN/20040222988&RS=DN/20040222988
It’s in lawyer/patent speak so it’s not easy follow, but if you’ve been following the debate you may recognise the details.

1. January 22, 2013 at 1:18 pm | #1
2. January 25, 2013 at 12:54 pm | #2
3. April 9, 2013 at 11:09 pm | #3
Sauropod Vertebra Picture of the Week #AcademicSpring

SV-POW! ... All sauropod vertebrae, except when we're talking about Open Access

Science to Grok

computing with space

isomorphismes

computing with space

Retraction Watch

Tracking retractions as a window into the scientific process

Shtetl-Optimized

computing with space

Not Even Wrong

computing with space

Theoretical Atlas

He had bought a large map representing the sea, / Without the least vestige of land: / And the crew were much pleased when they found it to be / A map they could all understand.

Gödel's Lost Letter and P=NP

a personal view of the theory of computation

Gowers's Weblog

Mathematics related discussions

Research and Lecture notes

by Fabrice Baudoin

Calculus VII

being boring

The "Putnam Program"

Language & Brains, Machines & Minds

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao