# Data structure to store breakable parts of a mesh

I have a wall mesh that is divided into destructible pieces. As it gets destroyed, the wall can collapse into separate objects with physics that can be destroyed as well. (Cut the wall in half horizontally and the top wall becomes a separate object with its own physics).

I already have the adjacency info to know neighbors, but how should I store the pieces so that I can detect when to split them into separate objects? What kind of tree would suit this and know when the branch was severed and what pieces to make a new object out of?

A test would be to smash a circle out of the wall, and the middle of the circle would fall out and contain only those remaining connected pieces as a new object.

Any examples out there?

Edit: would a graph structure work using shortest path? Anything more effecient?

Thanks!

I already have the adjacency info to know neighbors, but how should I store the pieces so that I can detect when to split them into separate objects? What kind of tree would suit this.

Rather than a tree I’d use a graph.

and know when the branch was severed

This could be as simple as waiting until the severing code finishes (and testing for partition after that) to whatever stores the branch info raising an event (see observer pattern) on a change.

and what pieces to make a new object out of?

Since we’re dealing with a graph this is an old computer science problem called strongly connected. If I can start at a random node and reach every other node then the graph is strongly connected. If I can’t then someone has cut your wall into pieces.

There are a few algorithms that solve this problem. I’m not going to detail them here. I will mention them and a few facts about them you may find important.

Kosaraju’s algorithm demands an adjancecy list if it’s going to be linear. It is the conceptually simplest efficient algorithm. Unlike the other two this must perform two complete traversals of the graph.

Tarjan’s strongly connected components algorithm has links to implementations in many languages. Uses a vertex-indexed array of preorder numbers.

Path based strong component algorithm first made linear by Dijkstra, performs a depth first search, requires two stacks besides recursive stack.