Teaser: 2D UD

Here are two images which may (or may not) give an idea about another fast algorithm for real time rendering of 3D point cloud scenes (but attention, the images are drawn for the baby model of 2D point cloud scenes).  The secret lies in the database.

I have a busy schedule the next weeks and I have to get it out of my system. Therefore,  if anybody gets it then please send me a comment here. Has this been done before, does it work?

The images now: the first has no name


The second image is a photo of the Stoa Poikile, taken from here:


Hint: this is a solution for the ray shooting problem (read it) which eliminates trigonometry, shooting rays, computing intersections, and it uses only addition operation (once the database is well done), moreover, the database organized as in the pictures cannot be bigger than the original one (thus it is also a compression of the original database).


See the solution given  by JX of an unlimited detail algorithm here and here.


16 thoughts on “Teaser: 2D UD”

    1. No, but thanks for the link. However, it does not matter how much it takes to build the database. In a presentation for the geospatial industry Dell shows a picture with lots of racks while saying that it takes some time to convert the laser scan database into the UD format.

      So, it’s not the same, but it is an interesting idea which may (or not) be used for further optimization. In this warped thing they use two POV to construct an interpolation between them, while in the UD algorithm is suggested that the preprocessing part acts on the 3D database.

      1. Turn around speed matters to the gaming industry, whom often require instant testing. The game industry promotion side of UD is the main contention people have with it.

        Unlike the photo warping described in those articles, the 3D location of all the visible pixels are available to the algorithm, making it perfectly accurate.
        You could use the cubes touching the camera cube to fill in warped space errors, which also means you’ll only have to load the nearest cubes, explaining the near instant speeds the Aero3DPro demonstration loads the data – it isn’t loading the landscape, it’s just loading the view at that point! Which is rather neat.

        The problems I can think of are having to store these boxes everywhere the camera can go which could include vast empty spaces, although they would be run-length compressed. Also the side window aberrations they originally had wouldn’t exist at all – they only seem to exist in D.J. Meagher’s 2D splatting algorithm.

      2. Yes, this is almost JX’s algorithm, see also the artifacts noted by him in the UD images, resulting from hole fillings. JX made available an archive, check his comments.

        He’s quiet now but I hope he sees our exchange and intervenes, because he has a solution.

        Coming back to the teaser, did you notice that I am writing about a toy case, namely a 2D world and its UD rendering on a 1D screen?

      3. “Coming back to the teaser, did you notice that I am writing about a toy case, namely a 2D world and its UD rendering on a 1D screen?”
        The centre box is the 2D square-map and the boxes on the right are reference boxes sized in frustum increments away from the edge of the box?
        I’m afraid to say, I haven’t quite understood JX’s comments. I’ve run the archive, and the results have a lot of holes, and it’s very slow – but it’s a great start.

  1. Hello
    At first it reminded me the shear-warp algorithm: http://www.cg.tuwien.ac.at/courses/projekte/vis/finished/SZambal/basic.html

    Then I understand your idea in this way: few image layers (different depth slices, distant slices have lower resolution) moving as in old-school parallax scrolling http://upload.wikimedia.org/wikipedia/commons/8/82/TWW_parallax_scrolling_sample_1.jpg but for surrounding cubemap case. For each cube (in your case square side) face you check pixel in first layer, if it transparent check corresponding pixel in the next until you get your color, then move to next pixel etc. Right?
    See also what one guy did by hand from photos: http://bezpoligonov3d.narod.ru/ (try to move mouse over the photo, Flash plugin required)

    1. Thanks for the message. I shall put it one of these days, it’s about perspective and some logarithms. For the moment I am deep inside two other things, one of them regarding building a very simple Turing machine with zippers from graphic lambda calculus.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s