Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tree construction process could create less garbage #22

Open
mqp opened this issue Sep 12, 2018 · 3 comments
Open

Tree construction process could create less garbage #22

mqp opened this issue Sep 12, 2018 · 3 comments

Comments

@mqp
Copy link
Contributor

mqp commented Sep 12, 2018

When I profile tree construction, one main bottleneck I see is that multiple GCs have to happen due to the amount of garbage that gets created. Here are a few categories of things that we construct:

  1. MeshBVHNodes. Of course, we need nodes in our tree.
  2. Spheres, Box3s, and their underlying Vector3s. It seems like we mostly need to store different bounding boxes and spheres for all of our nodes, so this is hard to avoid.
  3. For each node, the array of triangle indices in that node. This one is interesting. We need that list at each level when we are constructing child nodes, but we only need to store it permanently for leaf nodes; the arrays of triangles for intermediate nodes are discarded. It could be possible to rework the construction algorithm to not construct so many intermediate arrays.
  4. For each node, lambdas referring to that node and its split volumes, to put into the creation queue. This one is also interesting. It seems like if we reworked the construction algorithm, the processing queue could just be a queue of nodes, where the meaning of each entry is "this node needs to be split." That would save us creating the lambdas.

3 and 4 could be productive avenues for optimizing tree construction.

@mqp
Copy link
Contributor Author

mqp commented Sep 12, 2018

Oh yeah, and also creating the closure in getLongestEdgeIndex shows up. That one's easy to fix.

@mqp
Copy link
Contributor Author

mqp commented Sep 12, 2018

Another idea: right now the split strategy code returns a temporary object with the split parameters (axis and coordinate.) Instead, the split strategy code could populate the new bounding box and partitioned triangle arrays directly.

@mqp
Copy link
Contributor Author

mqp commented Dec 20, 2018

Everything I wrote in here is now fixed up except for the very last comment. By the way, it looks like on the example page nowadays, one GC almost always still has to happen during tree construction, so further improvements are still probably helpful.

@gkjohnson gkjohnson added the enhancement New feature or request label Aug 13, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants