Making some progress

I’ve finally managed to implement the algorithm I described in my previous post. It is still rather slow (2FPS at 1024×768 on average), with some frames taking up to 5 seconds. Also, my implementation does not yet always traverse nodes in the correct order, which causes some ordering errors.

Sibenik dataset

Sibenik dataset


16 thoughts on “Making some progress

    • Worst case it is 25M. This will go down once I start optimizing.

      Edit: Managed to reduce it to 5M calls to the traversal function and its running at 3 FPS (worst case).

    • For comparison, my previous, cubemap based method had 2.5M calls. So the new method does use significantly more traversals. However, the new method also produces sharper and more detailed results.

      I tried to improve the image quality of my cubemap based method, this raised the traversals to 4M, but the image quality was still worse than what is produced by my new implementation.

  1. Blah. Is the point of this traversal expected to greatly cut-down & reduce the number of traversals? I mean, that is the goal isn’t it?

    • Not entirely. The goal of this traversal is that it is fast. Reducing the number of traversals helps to achieve that. Currently it has 6.4 traversals per pixel, which is still too much, but nothing compared to ray tracing.

  2. The image quality is good, shame the fps is so slow. I had trouble with that dataset, could you please tell me the format of the points? Having fun with ‘the tower’ set at the moment, as flying around inside this big data world is really interesting.

  3. Thanks, I worked that out, but it’s the number format of the 3 coordinates i can’t make sense of. Are they just ushorts and big or little endian. I just get a dense soup even when I shuffle bits around.

    • They are unsigned shorts, little endian (which is the native endian for x86 and x86-64). On little endian machines struct {unsigned short x,y,z; unsigned char r,g,b; char dummy;} should work. I used the following python script on a x86-64 machine to convert it into my own format struct {uint32_t x,y,z,color;}:

    • Lensman,

      Why do you think you are reading them wrong? How do you expect the numbers to look like? Any values are actually valid. The points are concentrated around the center, (32768, 32768, 32768), and the building is several thousand atoms long.

  4. Thanks, I was scratching my head as to why I could see familiar colours but no structure, but it was my scaling function truncating values.

    You may find these screenshots of interest.

    I captured them from the latest Euclideon video. It sure looks like dual wave surfing to me. Axis aligned planes, no depth info. I get similar results if I run Voxel-Engine, but stop rercursion of the octree as soon as a node is hit, rather than going further. The effect looks like stepped billboards, rather than cubes, but the framerate is much higher. The trick to hiding the stepping is by having density of information, and essentially you are trading octree recursion for more texture lookups and trying to find the sweet spot somewhere between. LOD is a mip mapping process as you can tell from the screenshots. At further distances the colour bleeding is hard to hide unless you store colour per face or use a smarter filter with some gamma correction.

  5. Hm, making a cube out of several squares seems an interesting idea. Maybe it will look nicer than just a single expanded square which I do. Thanks Lensman!

  6. Hi, I’m not a usual follower of your blog as you can probably tell, but I take interest in the work you’re doing. I just wanted to say great work with everything, also, here are some recent videos showing off Euclideon’s Geoverse product in case you haven’t seen them yet:

    I don’t know if these will be helpful to you, but personally I find them interesting.

  7. Didn’t know you were blogging about this.
    I’ll add it to my list of blogs to follow, keep the nice work coming.
    I’m already looking forward to your next posts 😀

  8. data to screen approach with link less array; very fast traversal, 1 hit per node at depth n;

    using Hilbert curve I can calculate x,y,z and traverse the octree at N depth as a sort of link less array; initial batch read for empty/leaf nodes for each depth as 2 bit per node; doing all this in registers is very fast, occlusion is done with frustum/quad tree for depth; translation of Hilbert in 3d to quad tree in screen space is done in registers as well; the last piece is to batch read many nodes after traversal is complete for color;

    file structure stores lead/empty details in different sector/block as per its smaller and more traverse friendly read speeds;

    colors are loaded after traversal per identified node on screen; and can then be stored in memory;

    this is around 18 fps and hits each node 1 time, but traverses each node dependent on occlusion/empty nodes;

    most of the calculation, and traversal never leaves the L2 cache, only time it does is when reading the HDD sectors and storing into RAM;

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s