<div dir="ltr"><div><div><div><div>Hey,<br><br></div><div>For instance in every Lidar point cloud, the order is paramount, because the sensing is structured (lines usually).<br></div><div>So ordering can give you neighbourhood relation for free.<br></div><div>Also, ordering may be important when you want to improve your point cloud registration .<br></div><div>I don't mean point cloud global geolocalisation, but each point localisation in the sensor reference system.<br></div><div>Typically points are sensed in the sensor reference system, then knowing the sensor trajectory in WGS, you put the point in WGS (for instance).<br></div><div>Sadly sensor trakectory is always false to a point. Correcting it allow to re-register the points and improve points precision.<br></div><div><br></div>Sorry my answer was a little cryptic. <br><br></div><div>(I talk about LOD in [this presentation](<a href="https://github.com/Remi-C/Postgres_Day_2014_10_RemiC/raw/master/presentation/A%20PostgreSQL%20Server%20for%20Point%20Cloud%20Storage%20and%20Processing.pdf">https://github.com/Remi-C/Postgres_Day_2014_10_RemiC/raw/master/presentation/A%20PostgreSQL%20Server%20for%20Point%20Cloud%20Storage%20and%20Processing.pdf</a>) , p49 and 50)<br><br></div><div>For ordering points I build an octree, then for each level of the octree (0 to N), I take the point closest to the center of the cell.<br></div>This gives you at most 8^K points at the level K. <br></div>(here illustration in 2D on real data. Biggest point = most important point = lower Level point. )<br></div>I don't build an octree in fact, because you can get what point goes in which cell simply by looking at the binary coordinates of the points (after offset and scale).<br><div><div><div><br>This is cool is the user read the whole level. <br>But you can do something better by allowing continuous-LOD.<br>In this scenario the user can read only a part of a level, and we still want that he gets well spaced points.</div><div><br>For instance the level 1 would have 64 points, maybe the user read points 1 to 30.<br></div><div><br></div><div>If you order points within a level by morton curve, the user will only get points in the upper part of the patch (for instance).<br></div><div>So the user would have no points in the lower part of the patch !<br><br></div><div>We want to do precisely the opposite, and that the user gets points well spaced in the patch. <br>I used random because it was easy, but it is not deterministic.<br>The inverse morton code provides a cool order to dispatch points and kinda solve this problem (as well as being easy & fast to write in low level langages).<br></div><div><br></div><div>Cheers</div><div><br></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-04-17 13:07 GMT+02:00 Peter van Oosterom <span dir="ltr"><<a href="mailto:P.J.M.vanOosterom@tudelft.nl" target="_blank">P.J.M.vanOosterom@tudelft.nl</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000">
    <div>Hi Rémi,<br>
      <br>
      Good to hear that other persons find our work of interest. Thanks!<br>
      <br>
      Fair remark about the fact that original order of points can be
      significant.<br>
      (could you give one example where this is really clear?)<br>
      <br>
      I do not understand what you mean with 'for LOD I considered using
      an inverse morton curve'.<br>
      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'?<br>
      <br>
      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).<br>
      <br>
      Kind regards, Peter.<div><div class="h5"><br>
      <br>
      On 17-4-2015 12:35, Rémi Cura wrote:<br>
    </div></div></div><div><div class="h5">
    <blockquote type="cite">
      
      <div dir="ltr">
        <div>
          <div>
            <div>
              <div>
                <div>Hey Oscar (and Peter), <br>
                </div>
                great series of articles, the benchmark was really
                interesting !<br>
                <br>
              </div>
              I personally am adamantly against reordering the points
              for storage purpose, because the order can have a strong
              meaning (physical or theoretical).<br>
              <br>
            </div>
            For instance I re-ordered the points of my patch so that the
            points follows a LOD schema.<br>
          </div>
          So reading more and more points gives a better and better
          approximation of the patch.<br>
        </div>
        <div>This gives free LOD facilities when all the patch have been
          re-ordered (free CPU wise, and no data duplication).<br>
        </div>
        <div><br>
        </div>
        <div>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).<br>
        </div>
        <div>This has a strong impact, for instance reordering patches
          randomly will greatly increase patch storage size in
          pgpointcloud.<br>
        </div>
        <div>It is funny because for LOD I considered using an inverse
          morton curve (interleave X Y Z , then read is backward ! ).<br>
        </div>
        <div><br>
        </div>
        <div>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.<br>
        </div>
        <div><br>
        </div>
        <div>Anyway, just to say that pgpointcloud is ultimately not
          about storing points, but easing point cloud usage in my
          opinion.<br>
        </div>
        <div><br>
        </div>
        <div>Cheers,<br>
        </div>
        <div>Rémi-C<br>
        </div>
        <div><br>
        </div>
        <br>
        <div>
          <div><br>
          </div>
        </div>
      </div>
      <div class="gmail_extra"><br>
        <div class="gmail_quote">2015-04-17 11:02 GMT+02:00 Oscar
          Martinez Rubi <span dir="ltr"><<a href="mailto:o.martinezrubi@tudelft.nl" target="_blank">o.martinezrubi@tudelft.nl</a>></span>:<br>
          <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
            <div bgcolor="#FFFFFF" text="#000000"> Hi,<br>
              <br>
              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.<br>
              <br>
              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!<br>
              <br>
              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.<br>
              <br>
              Kind Regards,<br>
              <br>
              Oscar.
              <div>
                <div><br>
                  <br>
                  <br>
                  <div>On 16-04-15 18:15, Rémi Cura wrote:<br>
                  </div>
                </div>
              </div>
              <blockquote type="cite">
                <div>
                  <div>
                    <div dir="ltr">
                      <div><span style="font-family:monospace,monospace">epic
                          fail ! I had avoided html just for you<br>
                        </span></div>
                      <div><span style="font-family:monospace,monospace"><br>
                             Dataset   |subset size  | compressing   |
                          decompressing |<br>
                                       |(Million pts)|(Million
                          pts/s)|(Million pts/s)|<br>
                          Lidar        |   473.3     |    4,49       |
                              4,67      |<br>
                        </span></div>
                      <span style="font-family:monospace,monospace">21-atributes
                        |   105.7     |    1,11       |     2,62      |<br>
                      </span>
                      <div>
                        <div><span style="font-family:monospace,monospace">Stereo
                                  |    70       |    2,44       |    
                            7,38      |<br>
                            <br>
                          </span></div>
                        <div><span style="font-family:monospace,monospace">Cheers<br>
                          </span></div>
                      </div>
                    </div>
                    <div class="gmail_extra"><br>
                      <div class="gmail_quote">2015-04-16 17:42
                        GMT+02:00 Sandro Santilli <span dir="ltr"><<a href="mailto:strk@keybit.net" target="_blank">strk@keybit.net</a>></span>:<br>
                        <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On Thu, Apr 16,
                            2015 at 05:30:12PM +0200, Rémi Cura wrote:<br>
                            > OUps<br>
                            ><br>
                            > Dataset        |  subset size(Million
                            pts) | compressing (Million pts/s) |<br>
                            > decompressing (Million pts/s)<br>
                            > Lidar           |            473.3     
                                      |               4,49<br>
                            >               |             __4,67__<br>
                            > 21 attributes |           105.7       
                                     |<br>
                            > 1,11                     |           
                             2,62<br>
                            > Stereo         |              70       
                                      |                2,44<br>
                            >                |             7,38<br>
                            <br>
                          </span>These tables aren't really readable
                          here.<br>
                          Could you make sure to use a fixed-width font
                          to write those tables<br>
                          and to keep lines within 70 columns at most ?<br>
                          <br>
                          --strk;<br>
                        </blockquote>
                      </div>
                      <br>
                    </div>
                    <br>
                    <fieldset></fieldset>
                    <br>
                  </div>
                </div>
                <span>
                  <pre>_______________________________________________
pgpointcloud mailing list
<a href="mailto:pgpointcloud@lists.osgeo.org" target="_blank">pgpointcloud@lists.osgeo.org</a>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/pgpointcloud" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/pgpointcloud</a></pre>
                </span></blockquote>
              <br>
            </div>
          </blockquote>
        </div>
        <br>
      </div>
    </blockquote>
    <br>
    <br>
    </div></div><span class="HOEnZb"><font color="#888888"><pre cols="72">-- 
Peter van Oosterom          <a href="mailto:P.J.M.vanOosterom@tudelft.nl" target="_blank">P.J.M.vanOosterom@tudelft.nl</a>
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
<a href="http://geomatics.tudelft.nl" target="_blank">http://geomatics.tudelft.nl</a> MSc Geomatics
<a href="http://www.msc-gima.nl" target="_blank">http://www.msc-gima.nl</a>      MSc GIMA (Geo-Info Management&Appl)
<a href="http://www.gdmc.nl" target="_blank">http://www.gdmc.nl</a> 

</pre>
  </font></span></div>

</blockquote></div><br></div>