CODEWITHSUNDEEP
c++opengloptimization
Raph Schim
Raph Schim

Reputation: 538

Tree to optimize OpenGL Pointcloud

I would like to optimize my OpenGL program. It consists in loading a vector of 3D points then applying shaders to them. But I have billions of points, and my FPS drop to 2 when I try to see the points.

Actually I'm sending every points, and I believe this is what is too much for my computer.

Is making a KD-tree (for example) to store my points and then send to my shaders only the points contained in the viewing frustum an efficient way to optimize my program?

And, since my goal isn't to do research of points, but only use points in the viewing frustum, which tree would be better? Octree? KD-tree?

Upvotes: 0

Views: 1146

Answers (1)

karyon
karyon

Reputation: 2567

using trees is definitely a good way to deal with large point clouds. i worked on a point cloud rendering software for a while and we used kd-trees for rendering, and regular voxel grids for analysis.

i don't exactly remember the reasons for/against using an octree, but i guess it depends on the density distribution of your clouds: if you have large point clouds with some small high-density areas, you would have lots of empty cells in the octree, whether for evenly-distributed point clouds, octrees might be simpler. We also had 2.5D maps (from aerial scans: several square kilometers of terrain but only little devation in height) where we used quad trees for some tasks.

also we did not render all the points that were in the frustum, because that degenerates e.g. when you zoom all the way out so the whole point cloud is in the frustum again.

instead, all the inner (non-leaf) nodes in the kd-tree contained a "representative" selection of the points in their children, and we rendered the tree only up to a depth that seemed appropriate depending on the distance from the camera to the bounding volume of each node. this way, for areas that are far away from the camera, you render a thinned out version of the point cloud, an LOD of sorts.

if you want to go fancy: we actually maintained a "front-line" of nodes, that is a line or cut from left to right through the tree up to which all nodes should be rendered. this way we did not need to check each node but only the ones in the cut whether their status ("rendered" or "not rendered") should change. additionally, we had out-of-core point clouds which where larger that the (V)RAM, where we allowed the front to only move farther down the tree if the parent node had been loaded from disk.

kd-trees are a bit harder to build because you need to determine where the split plane is located. for this we used a first pass where we read the locations of all the points in the node, determining the split plane, and then a second pass doing the actual split.

i think we had 4096 points per node (i think we experimented with more and 8k or 16k were fine as well), and did one draw call per node. as long as your point cloud fits in VRAM you can simply put all of it in one large buffer and do draw calls with offsets into that buffer.

Upvotes: 1

Related Questions