How can I delete parts of a mesh in Unity?

Question

I am trying to make a destructible game environment; I want to delete the vertices (and triangles assorted to them) within some sphere of a given radius with its center at the contact point (in essence, just delete the part of the mesh that would be destroyed by an explosion of a projectile contacting it).

The way I'm trying to achieve it now is: take a mesh, and whenever there is a collision with it, construct a vector from each vertex to the hitpoint and measure its magnitude, if the magnitude is less than a given radius, then I add the vertex to a list (say TaggedVerts). After that I arrange the triangles array into a list of triplets. I take each vertex in TaggedVerts and translate it into its corresponding triangle number (basically its index in the mesh.vertices array) and check each triplet in the triangle list I had built earlier. If any triplet contains the tagged vertex, then I remove the whole triplet from the list. After doing this for all vertices in TaggedVerts, I put the List into an array and set mesh.triangles equal to it.

However, this method only works with a cube, and I am not quite sure it works correctly anyway since it deletes some triangles and some others it leaves intact.

Is there a better way to do this?

Answer 1

I'm going to describe solutions in 2D which should be trivial to port to 3D.

TL;DR - (1) You can replace whatever part of a Mesh you want in Unity but you must re-upload the entire mesh; (2) don't run through your entire vertex array(s) and do radius checks - it is prohibitive for larger meshes. (3) Don't use classic CSG as you are... voxels are easier to work with.

Solutions

...if the magnitude is less than a given radius...

Doing random access on the entire vertex array(s) is a no-no; it will be very slow as the mesh grows, as a (vertex) array is poorly suited to random access. Speculating here, but with unsigned short vertex indices Unity uses, we've a max of 64k vertices to sort through for every impact per mesh @ minimum 2 meshes per impact = up to 128k vertices to seek through.

Instead, use spatial subdivision.

• Divide your world space up into a grid. We'll call each square a zone. Let's say they're 32x32 units each, in a much larger world. This arrangement serves as an occupancy grid. Occupancy is a list of islands currently overlapping a given zone.
• We have a bunch of islands floating about in space - these are our discrete meshes. You'll need to limit their maximum bounds in XYZ. In this case let's say that on average, they're the size of a zone (32x32). Some are bigger, some are smaller, and when moving, even a small mesh can overlap up to 4 zones (8 in 3D) if sitting on the corner between these zones.

• Whenever an island moves (typically each tick), you need to update:

  • the occupancy grid - this means getting the bounds of the island and seeing which zones it overlaps, then putting it into the occupancy list for each such zone.
  • for all zones, the set of all vertices from any island which zone overlaps - different from the list of vertices which each island contains; necessary if you plan to store vertices by zone (below); performance impact of this can be reduced by only doing it a few times a second.

• Do a high level collision check using the occupancy grid: run through every zone, look at its set of occupying islands; if there is more than one island in that zone's set, those islands have potentially collided - this is only a coarse check i.e. broadphase collision detection.

• Do a geometric or voxel-based collision check to see if the finer details within these zones have indeed collided; we must compare every island in the zone's set to every other for total O(n^2) checks (but that should be fine if you have sparse islands in a large space).
• Use the results of the last step to resolve geometry destruction appropriately.

As we run through all zones each frame, this resolves all collisions. You may have more details to attend to, e.g. synchronising collisions of the same island across multiple zones.

As for getting the vertex array into its final form for upload to GPU...

• For each zone in the grid, write its vertices into the vertex array. That way as we walk vertex array, we have one zone after another. This affords spatial coherence which is good for CPU performance when it destroys terrain, and good for GPU read performance when rendering triangles.

• Store the start and end vertex indices for each and every zone. Now you can easily get back to that zone and modify it later, if a collision occurs. Sometimes, you will need to re-order / re-compress things. (With OpenGL or DirectX access, you could upload only the changed parts of the array... bummer about Unity!) Eskil Steenberg talks about this briefly here.

• Use a spatial hash function like a Z-curve to decide the best order (performance-wise) to insert your vertices into vertex array(s).

Conclusion

Other than this, the only inherent problem with what you're doing is that geometric approaches to destroying geometry can have some serious complications, drawbacks, and corner cases over using voxels - which is much of the reason voxels are now so common. You can stick with what you're doing and use the above to improve your current method, or switch to voxels and you can still benefit by the above improvements. In all, I hope this provides you a full answer.