1
\$\begingroup\$

So I have this middle-large mesh that is composed from vertices and respective indices. At some point I need to add new ones and remove some. But that brings me into trouble. Because if I have, for example, a 10k array (or vector) of indices and I want to remove one with index n, I have todo lot of processing on the array:

a) Find n b) Slice n c) Slice the respective Vertex from other array (the easiest part) d) Shift the array e) Shift the indices (worst part). If I remove 6, 7 needs to become new 6, 8 new 7 and so on...

Another strategy is to recreate Vertex and Index arrays/vectors every time something changes, but that isn't efficient neither.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Can you cut down the mesh into smaller chunks, where you'd have only a subset of ~1k to worry about instead of 10? \$\endgroup\$
    – Vaillancourt
    Sep 9 at 13:19
  • \$\begingroup\$ So I would have 10 meshes with own stack of vertices and indices? \$\endgroup\$ Sep 9 at 13:43
  • \$\begingroup\$ Yes, if that makes sense for your application. \$\endgroup\$
    – Vaillancourt
    Sep 9 at 13:43
2
\$\begingroup\$

One thing you can do is defer the deletion of vertices.

Replace a "removed" vertex's data with NAN values, but leave it where it is, and record its index in a separate small collection of "open slots".

Any triangles referring to the removed index will be discarded by the GPU, because of the NANs propagating through the rasterization calculation. But you can also swap such triangles with the last valid triplet of indices in the list to get a contiguous buffer of only valid triangles without shifting the entire array down, and that way you don't send invalid ones to the GPU at all.

There is a small overhead to this, due to storing/transferring "dead" vertex data that's not going to be used, but if you're already pushing 10 k vertices and only deleting dozens or hundreds at a time, this probably won't impact the performance significantly.

Whenever you want to add new vertices, you can check the "open slots" and overwrite them with the new vertex information, inheriting the old unused index. Just make sure you've cleared out any triangles that were referencing the unused vertex, if any.

If your open slots list ever exceeds a threshold size, you can then take the time to re-optimize your mesh data (potentially on a background thread), shifting down the valid vertices to consecutive indices and rebuilding the indices array to match. The advantage is that you don't need to do this eagerly with every small change if they're frequent, and you can continue using the old up-to-date but slightly-less-than-optimal version while you wait for the background process to clean it up, instead of stalling your core update loop every time the mesh is edited.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.