[pgpointcloud] RLE and SIGBITS heuristics
Peter van Oosterom
P.J.M.vanOosterom at tudelft.nl
Fri Apr 17 04:07:02 PDT 2015
Hi Rémi,
Good to hear that other persons find our work of interest. Thanks!
Fair remark about the fact that original order of points can be significant.
(could you give one example where this is really clear?)
I do not understand what you mean with 'for LOD I considered using an
inverse morton curve'.
Options for selecting points for higher LODs could be random (not so
smart, but easy) or some spatial analysis (figure our relative
relevance/ importance of points, smarter, but non-trivial). So, in
general two nearly equal (very close) points should not both go to
higher LOD, so better look for the different point to push to higher
level. You could do this with real distance in 3D space, but it may be
easier with distance of 1D morton code. So, when points are processed
(in original sequence), you compute their morton code, and when next
point is significantly different wrt morton, it goes up (and otherwise
stay at lowest level). Is this what you mean with 'inverse morton for LOD'?
We really need LOD and smart data organization for efficient use,
current test of 640 billion points we need it (and there is a 30
trillion data set announced for Netherlands, which we also would like to
use efficiently in interactive manner).
Kind regards, Peter.
On 17-4-2015 12:35, Rémi Cura wrote:
> Hey Oscar (and Peter),
> great series of articles, the benchmark was really interesting !
>
> I personally am adamantly against reordering the points for storage
> purpose, because the order can have a strong meaning (physical or
> theoretical).
>
> For instance I re-ordered the points of my patch so that the points
> follows a LOD schema.
> So reading more and more points gives a better and better
> approximation of the patch.
> This gives free LOD facilities when all the patch have been re-ordered
> (free CPU wise, and no data duplication).
>
> Now I have to admit that efficient storage and LOD are in conflict,
> because storing is about putting the similar points together somehow,
> and LOD is about the opposite (kind of sequential vs random access).
> This has a strong impact, for instance reordering patches randomly
> will greatly increase patch storage size in pgpointcloud.
> It is funny because for LOD I considered using an inverse morton curve
> (interleave X Y Z , then read is backward ! ).
>
> I'm well aware that we could simply store the original order in an
> attribute, and so compression based on morton on XYZ might be
> transparent for the user.
>
> Anyway, just to say that pgpointcloud is ultimately not about storing
> points, but easing point cloud usage in my opinion.
>
> Cheers,
> Rémi-C
>
>
>
>
> 2015-04-17 11:02 GMT+02:00 Oscar Martinez Rubi
> <o.martinezrubi at tudelft.nl <mailto:o.martinezrubi at tudelft.nl>>:
>
> Hi,
>
> About the XYZ binding for better compression. In our research in
> the NL escience center and TU Delft we have been thinking (not
> testing yet though) about one possible approach for this.
>
> It is based on using space filling curves. So, once you have the
> points that go in a block you could compute the morton/hilbert
> code of the XYZ. Since all the points are close together such
> codes will be extremely similar, so one could store only the
> increments which could fit in many few bits. We have not tested or
> compared this with any of the other compressions but we just
> wanted to share it with you just in case you find it useful!
>
> An additional improvement would be to sort the points within the
> blocks according to the morton code. Then, when doing crop/filter
> operations in the blocks one can use the morton codes for the
> queries similarly to what we presented in our papers with the flat
> table (without blocks), I attach one of them (see section 5.2). In
> a nutshell: You convert the query region into a set of
> quadtree/octree nodes which can be also converted to morton code
> ranges (thanks to relation between morton/hilbert curve and a
> quadtree/octree). You scale down the ranges to increments (like
> you did when storing the point of the block) and then you simply
> do range queries in sorted data with a binary algorithm. In this
> way you avoid the decompression of the morton code for most of the
> block. This filtering is equivalent to a bbox filter so it still
> requires a point in polygon check for some of the points.
>
> Kind Regards,
>
> Oscar.
>
>
>
> On 16-04-15 18:15, Rémi Cura wrote:
>> epic fail ! I had avoided html just for you
>>
>> Dataset |subset size | compressing | decompressing |
>> |(Million pts)|(Million pts/s)|(Million pts/s)|
>> Lidar | 473.3 | 4,49 | 4,67 |
>> 21-atributes | 105.7 | 1,11 | 2,62 |
>> Stereo | 70 | 2,44 | 7,38 |
>>
>> Cheers
>>
>> 2015-04-16 17:42 GMT+02:00 Sandro Santilli <strk at keybit.net
>> <mailto:strk at keybit.net>>:
>>
>> On Thu, Apr 16, 2015 at 05:30:12PM +0200, Rémi Cura wrote:
>> > OUps
>> >
>> > Dataset | subset size(Million pts) | compressing
>> (Million pts/s) |
>> > decompressing (Million pts/s)
>> > Lidar | 473.3 |
>> 4,49
>> > | __4,67__
>> > 21 attributes | 105.7 |
>> > 1,11 | 2,62
>> > Stereo | 70 |
>> 2,44
>> > | 7,38
>>
>> These tables aren't really readable here.
>> Could you make sure to use a fixed-width font to write those
>> tables
>> and to keep lines within 70 columns at most ?
>>
>> --strk;
>>
>>
>>
>>
>> _______________________________________________
>> pgpointcloud mailing list
>> pgpointcloud at lists.osgeo.org <mailto:pgpointcloud at lists.osgeo.org>
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/pgpointcloud
>
>
--
Peter van Oosterom P.J.M.vanOosterom at tudelft.nl
Section GIS technology (room 00-west-520) Department OTB
Faculty of Architecture and the Built Environment, TU Delft
tel (+31) 15 2786950 Julianalaan 134, 2628 BL Delft, NL
fax (+31) 15 2784422 P.O. Box 5043, 2600 GA Delft, NL
http://geomatics.tudelft.nl MSc Geomatics
http://www.msc-gima.nl MSc GIMA (Geo-Info Management&Appl)
http://www.gdmc.nl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgpointcloud/attachments/20150417/ccf17b2a/attachment-0001.html>
More information about the pgpointcloud
mailing list