Struttura dei dati per archiviare le parti fragili di una mesh

Question

Struttura dei dati per archiviare le parti fragili di una mesh

#1 da (1 voti)

3

Ho una rete a muro divisa in pezzi distruttibili. Quando viene distrutto, il muro può collassare in oggetti separati con una fisica che può essere distrutta. (Taglia il muro a metà orizzontalmente e la parete superiore diventa un oggetto separato con la sua fisica).

Ho già le informazioni di adiacenza per conoscere i vicini, ma come posso conservare i pezzi in modo da poter rilevare quando dividerli in oggetti separati? Che tipo di albero sarebbe adatto a questo e sapere quando il ramo è stato reciso e quali pezzi creare un nuovo oggetto?

Un test sarebbe quello di distruggere un cerchio fuori dal muro, e il centro del cerchio cadrebbe e contenere solo i pezzi rimanenti collegati come un nuovo oggetto.

Qualche esempio là fuori?

Modifica: una struttura grafica funzionerebbe usando il percorso più breve? Qualcosa di più efficace?

Grazie!

data-structures

posta Nubsauce 13.06.2016 - 05:00

fonte

1 risposta

Leggi altre domande sui tag data-structures

In un'applicazione CQRS / ES, le proiezioni possono dipendere? Tecnica per sincronizzare medie / grandi quantità di dati

score 1 · Accepted Answer

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.

Piuttosto che un albero, userei un grafico.

and know when the branch was severed

Questo potrebbe essere semplice come aspettare fino a quando il codice che si interrompe finisce (e testare per la partizione dopo) a qualsiasi cosa memorizzi le informazioni sul ramo che generano un evento (vedi schema di osservatore) su una modifica.

and what pieces to make a new object out of?

Dato che abbiamo a che fare con un grafico, questo è un vecchio problema informatico chiamato strongmente connesso . Se posso iniziare da un nodo casuale e raggiungere ogni altro nodo, il grafico è strongmente connesso. Se non posso, allora qualcuno ha tagliato il muro a pezzi.

Ci sono alcuni algoritmi che risolvono questo problema. Non ho intenzione di dettagliarli qui. Ne parlerò e alcuni fatti su di essi potrebbero essere importanti.

L'algoritmo di Kosaraju richiede una lista di aggiustamento se sarà lineare. È l'algoritmo efficiente concettualmente più semplice. A differenza degli altri due, questo deve eseguire due traversamenti completi del grafico.

L'algoritmo di componenti strongmente connessi di Tarjan ha collegamenti alle implementazioni in molte lingue. Utilizza una matrice indicizzata con vertice di numeri preordinati.

Algoritmo di componente strong basato sul percorso prima reso lineare da Dijkstra, esegue una prima ricerca di profondità, richiede due stack oltre pila ricorsiva.