Hi Pierre While I don't have concrete advice for your implementation, I would like to suggest having a look at Entwine [1] and/or PotreeConverter [2] projects and maybe reuse their code. Both of them have only a single task - to build an octree from potentially massive amounts of point cloud data.
I will start working on point cloud visualization in QGIS in the coming months and I plan to use code from one of the projects to build octrees for efficient visualization (more details here [3]). Regards Martin [1] https://github.com/connormanning/entwine [2] https://github.com/potree/PotreeConverter [3] https://github.com/qgis/QGIS-Enhancement-Proposals/issues/194 On Wed, Sep 23, 2020 at 3:11 AM Pierre Abbat <p...@bezitopo.org> wrote: > > https://github.com/phma/wolkenbase > I just published the repo. I've been racking my brains on this problem for > months. Wolkenbase reads a point cloud and makes an octree, in order to > classify points. The basic algorithm of building the octree is sound, but > slow, so I'm trying to multithread it. > > Wolkenbase has to handle point clouds that are too big to fit in RAM, so it > allocates block buffers until RAM gets low, then swaps blocks out to files. So > that it can continue putting points in the octree while writing blocks to > files, it uses more files than there are threads. > > I'm testing it with a small point cloud of 250024 points, so that it doesn't > have to write to disk while it constructs the octree, but still it loses > points. I've found and fixed bugs in the splitting routine. I currently have > it > checking after each point it inserts to make sure that it's in there. I've > found, and I think I fixed, a bug where one thread checked a point while > another thread was splitting the block where the point was inserted, so it > didn't find it. Now it fails to find a point, but the point is not in the > block > being split. It may fail to find 24 points while it's building the octree, but > when it's finished they're all there, or it's missing one or three of them. > > I have a huge point cloud (19 files, 3.5 GB total) which I've tried Wolkenbase > on, but it complains that the point is already in the octree. This turned out > to be points scattered through the cloud that have been "deleted" by > overwriting with all zeros. (0,0,0) is offset to somewhere within the cube, > and > is equal to (0,0,0), so I can't rely on the point count in the dump file. > > I cut it down to one thread; it works perfectly. With two threads, it works > fine, but with three, it loses points. Usually two threads are sufficient to > allow a concurrency bug to happen. > > Can someone look at the program and suggest how to make it work? > > Pierre > -- > li ze te'a ci vu'u ci bi'e te'a mu du > li ci su'i ze te'a mu bi'e vu'u ci > > > > _______________________________________________ > Discuss mailing list > Discuss@lists.osgeo.org > https://lists.osgeo.org/mailman/listinfo/discuss _______________________________________________ Discuss mailing list Discuss@lists.osgeo.org https://lists.osgeo.org/mailman/listinfo/discuss