Consider storing a separate triangle index buffer instead of reordering the triangle index array

[gkjohnson]

Instead of reordering the geometry index array we can create a new index buffer into the existing geometry indices (or directly into the vertex attributes) which would remove the need to rearrange the existing indices.

Pros:

• More flexible because existing cached triangle indices would no longer be invalidated on rebuild.
• Not rearranging the index buffer means geometry groups would no longer have to be split into multiple roots.
• Possibly faster to build because the sorting / partitioning logic would be simpler.

Cons:

• Likely slower raycasting due to more indirection.
• More memory (1-4 more bytes per triangle depending on geometry size).
• Material indices from groups would have to be derived afterward by iterating over groups.

Open Question:

• What to do if no index has been generated? Just generate an increasing one? (or just assume it's constantly increasing?)
• What's the performance impact?

Perhaps a different build option could be provided so both are viable?

[gkjohnson]

Changes required to support an option:

• [ ] Index no longer has to be ensured (buildTree function)
• [ ] Instead of bookkeeping an index array we keep an indirect "triangleIndex" array that is 1/3 the size (buildTree function)
• [ ] "partition" function needs to sort an array that is 1 / 3 the size (partition function)
• [ ] "raycast" function needs to be adjusted to take an indirect array or take function for running intersections (raycast cast function)
• [ ] "raycastFirst" function needs to be adjusted to take an indirect array or take function for running intersections (raycastFirst cast function)
• [ ] "shapecast" functions needs to be adjusted to take an indirect array or it can be wrapped in MeshBVH call (MeshBVH.shapecast or shapecast cast function)
• [ ] Shader BVH packing needs to know about the indirect storage.
• [ ] Tests
• [ ] Worker generation

Option name:

• createIndirectTriangleBuffer
• createIndirectBuffer
• indirect
• immutableIndexBuffer
• immutableGeometry
• arrangeIndexBuffer
• sortIndexBuffer
• modifyIndexBuffer

[McCulloughRT]

This was an important feature for me, so I forked and took a stab at it in my "indirect-triangle-index" branch

It covers most of what you've laid out, except I haven't looked into "shapecast" yet. I also opted to change "intersectTri" in ThreeRayIntersectUtils instead of the "raycast" and "raycastFirst" functions. Also still to do: remove the root splits.

Happy to submit a PR if desired!

[gkjohnson]

Hey @McCulloughRT! This is great -- thanks for taking a stab at it. If you're interested in taking it to the finish line go ahead and make a PR and I can help with any other direction you might need and we can get it reviewed and merged!

And out of curiosity what's your use case that this was required? I always appreciate hearing about how my work is used.

Thanks again!

[gkjohnson]

Hey @McCulloughRT are you still interested in making a PR? This would be great to get in in one of the upcoming releases!

[gkjohnson]

See #428

Table

	index	no index
indirect	retain index	no index
not indirect	rearrange index	create index

Phase 1

• Index no longer has to be ensured (buildTree function)
• "partition" function needs to sort an array that is 1 / 3 the size (partition function)
• adjust "raycast" function to use indirect buffer
• adjust "raycastFirst" function to use indirect buffer
• adjust "shapecast" function to use indirect buffer
• adjust "intersectGeometry" function to use indirect buffer

Phase 2

• Adjust code to be agnostic to index presence.
• fix refit
• figure out option name, indirect field

Phase 3

• Worker generation
• serialization / deserialization
• Shader BVH packing needs to know about the indirect storage.
  • deindex the buffer here
• Tests
  • Randomized tests
  • Serialized tests
  • Option tests
  • Tests with no index
• Benchmark

Phase 4

• Documentation

Open Issues

• Shapecast implicitly relies on the index for "intersectsRange"
  • Add a helper function to dereference the triangle index: bvh.getTriangleIndex, bvh.dereferenceIndex, ??
• Shader functions will not have accurate index position
  • Worry about this later?
• Member names
  • Option: indirect, retainIndex, ??
  • Member: indirectBuffer, ??
• Retain the current groups code path?

[gkjohnson]

Basics added in #555

Next

• figure out option name, indirect field
• write more tests
  • ensure bvhcast is tested
• shave time off benchmark
  • remove tight inner conditionals
  • remove tight inner function calls
• documentation

[gkjohnson]

Fixed in #439