How to append PointClouds in linear time.
- Dominant language
- C++
- Stars
- 14k
- Forks
- 2.6k
- Avg merge
- 5d 18h
- Merged PRs (30d)
- 6
Description
### Checklist
- [X] I have searched for [similar issues](https://github.com/isl-org/Open3D/issues).
- [X] For Python issues, I have tested with the [latest development wheel](http://www.open3d.org/docs/latest/getting_started.html#development-version-pip).
- [X] I have checked the [release documentation](http://www.open3d.org/docs/release/) and the [latest documentation](http://www.open3d.org/docs/latest/) (for `master` branch).
### My Question
Is there a function to concatenate many PointClouds in approximately linear time? I'm working with the Tensor API, but am flexible.
This obvious loop starts fast, but then gets slower with each successive addition. I assume the entire growing point cloud is copied at each step.
```
# Slow.
total_pc = None
for pc in point_clouds:
if total_pc is None:
total_pc = pc
else:
total_pc = total_pc.append(pc)
```
I wrote a concatenation function that is faster, but is ugly. Essentially it collects references to all the PointClouds' internal Tensors and passes them to one call of numpy.concatenate. It must do this for every attribute.
```
def concatenate_pc(pcs):
"""
Concatenate a list of compatible Tensor PointClouds.
I *think* the only copy happens inside the call to np.concatenate.
"""
# Fill positions.
attr = 'positions'
arrays = []
for pc in pcs:
arrays.append(getattr(pc.point, attr).numpy())
tensor = o3c.Tensor.from_numpy(np.concatenate(arrays, axis=0))
total_pc = o3d.t.geometry.PointCloud(tensor)
# Fill other attributes.
attributes = set(k for k,b in pcs[0].point.items()) - set(['positions'])
for attr in attributes:
arrays = []
for pc in pcs:
arrays.append(getattr(pc.point, attr).numpy())
tensor = o3c.Tensor.from_numpy(np.concatenate(arrays, axis=0))
setattr(total_pc.point, attr, tensor)
return total_pc
# Faster.
total_pc = concatenate_pc(point_clouds)
```
This feels like a pretty common use case, so I'm hoping there is a more direct API function to solve this problem.
A second question is about memory. The memory footprint of my list of point clouds is already pretty large, but then it gets (temporarily) doubled in the process of concatenation. I altered my function slightly to start deleting attributes from each old pc as they are copied into the total_pc, and that does help somewhat. However, that memory management feels even more like a thing that the library might handle more gracefully than me. In my real application these point clouds are being streamed out of a file, so ideally my memory footprint would be no bigger than the final point cloud size.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the Tensor API's PointCloud.append behavior and the NumPy concatenation approach shown in the issue. Determine whether a direct multi-cloud or streaming API exists, with completion defined as linear-time concatenation without unnecessary temporary memory.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, python
- Domain
- computer-vision, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100