Hey guys,
So I wanted to test sorting the data. I was able to figure out how to sort rows using matlab, but it turns out that to actually do a 2D sort requires several passes over both axes if you use a traditional sort. Thats because once you sort the X row, once you start sorting Y, it disturbs the X sort a certain amount and that continues. Maybe you guys know how to do that using matlab or some other method but I found it easier to solve using the GPU and shaders.
Basically I did something similar to a ‘bubble sort’, but its not as bad on the GPU as its considered on the CPU. That is because the GPU can compare every 2 texels simultaneously so you only need to consider the individual passes. And if you alternate between sorting on the X and Y rows after every 2 texels, you can sort the whole texture in a single pass for each axis. So a 4k texture requires 8k passes to sort both X and Y. It looks pretty cool to visualize this by looking at the color data since it basically stitches something that looks like a city out of noise.
This kind of method would definitely make more sense if the data was rectangular to begin with, but it still gives decently squarish regions.
it is interesting, but just sorting the data like this causes it to render faster! If you do r.screenpercentage 200, the difference becomes huge. I think the reason is because when tons of nearby screen pixels have to look up all over the 4k texture, it causes poor memory coherence whereas having the points located nearby in the texture reduces that. On my Titan video card, at screen percentage 200, the unsorted data runs at 17fps and the sorted data runs at 53fps!
The next step is to try actually using LODs based on the distances. Currently I don’t have an easy way to set the bounds of each section to correlate with the actual data they contain. I may just switch to testing a rectangular region so that I can just set the bounce of each section programatically (assuming the calculated values will be close enough for LOD purposes). Currently I would have to export the texture and extract bounds from it using matlab or something like that.
[video]Sorting point cloud data via GPU
You can see how it breaks up the area:
Note that the larger regions are actually less dense in the original data. Smaller regions are more dense.