Mi piace il suggerimento per l'ottavo, ma in realtà credo che tu possa frustare la tua implementazione della griglia in 3D. Ho fatto cose simili testando l'autointersecazione con mesh che attraversano milioni di verts in millisecondi usando lo stesso algoritmo di base. Era in C ++ e ho utilizzato più thread, ma dubito che maxscript sia quello molto più lento in modo da prendere 6 secondi su una mesh che copre solo 6 kts.
As noted in the comments I do absolutely expect MaxScript to be slower, but your case is processing something like 1,000 triangles/sec, while my former cases (and this was on older hardware) was processing something like 80 million triangles/sec (~80,000 times faster) using the same algorithm. I can understand if C++ is a few hundred times faster than MaxScript, but 80,000 times faster probably implies that something else going on like perhaps explosive memory use described below combined with a boatload of cache misses and possibly grid cell sizes that are way too small causing the triangles to be inserted into far more cells (the combo of all four could definitely explain this type of performance difference). And I imagine memory use isn't that big of a concern as long as it's not insane given this type of "build data structure, use it for intersection tests, toss away" one-time use case.
In realtà la griglia non è male per i test di auto-intersezione, perché se costruisci prima un octree, è un po 'più costoso da costruire di solito e alla fine devi spesso eseguire il drill-down verso le foglie per eseguire quelle auto-intersezioni test. Con la griglia potresti attraversare alcune celle vuote, ma la griglia è molto più facile da usare per la cache purché le celle siano disposte in modo contiguo.
On further thought the grid should be theroetically more optimal than octree in this particular case detecting self-intersections, because if you imagine the work required to detect colliding/intersecting triangles for a given triangle, the grid resolves this in constant time, while the octree would do it in logarithmic time... but moreover the octree is sorta doing the same thing, drilling down to the leaf nodes of the tree to check for the triangles in the same cell(s), so to speak. It does have the benefit that it might not have to split nodes as much leading to fewer cells to check in some cases, but then the practical side kicks in where tree node traversal doesn't tend to be nearly as cache-friendly as cell traversal in the grid. And then on top of that, building the tree tends to be more expensive with insertions requiring logarithmic time as well as a lot more work in each iteration splitting cells and so forth.
La cosa principale che sospetto che tu stia facendo è che ho visto molto in VFX che rallenta gli indici spaziali a una scansione (sia che parliamo di una griglia o di un hash spaziale o di un octree o di un albero o di un albero kd o di una BVH ) pur facendoli prendere centinaia di volte più memoria di quanto dovrebbero memorizzare un contenitore di dimensioni variabili con ogni nodo dell'albero o cella / secchio della griglia. Questo tende ad essere un killer dalle prestazioni massicce in termini di costruzione della struttura e attraversamento dell'albero, poiché tende ad essere piuttosto esplosivo nell'uso della memoria e causa errori di cache ovunque quando si considera il numero di celle o nodi che questi indici spaziali possono avere e moltiplicare quello con la dimensione di una sequenza di dimensioni variabili. In realtà sono riuscito a ridurre un'implementazione di octree che ho scoperto in una base di codice legacy richiedendo 1,2 giga di RAM fino a poco più di 3 megabyte utilizzando questa tecnica di base illustrata di seguito con riduzioni quasi proporzionali del tempo trascorso nell'operazione *.
- That particular case was in C++ and had each octree node storing its own instance of
std::vector where it started off inserting everything to the root node and then splitting it and transferring portions of that vector to the vectors below. Moreover it didn't factor in that removing elements or even completely clearing a vector doesn't deallocate its dynamic memory, so it ended up just exponentially using more memory than required.
La soluzione è solo memorizzare un contenitore di dimensioni variabili per l'intera griglia (o albero se si sceglie di andare con l'ottetto, questo è applicabile in entrambi i casi). Memorizza tutti gli elementi necessari in un'unica gigantesca sequenza di accesso casuale.
Ora un modo semplice per "emulare" avere un contenitore / elenco di dimensioni variabili separate per nodo o cella di griglia (senza allocare blocchi di memoria separati e tenere traccia delle loro dimensioni e così via) è quindi di memorizzare un indice con ciascun elemento che ti permette di saltare la sequenza (array, cioè) in una sorta di elenco di link collegati singolarmente, in questo modo:
Trannechetuttiinodisonoallocatiearchiviatiinmodocontiguoinungigantescoarray,estiamousandogliindicipersaltareattraversol'array.Eognicellamemorizzanient'altrocheuninteroa32bitperunindicenell'array(latestadell'elenco).Idatipossonoesserecosìsemplici:
struct Grid
{
struct GridCell
{
// Index pointing to the first element in the cell
// or -1 if the cell is empty.
int first;
};
struct GridElement
{
// Index pointing to the original element (ex: triangle) outside
// the grid.
int element;
// Index pointing to the next element in the cell or -1 if
// this is the last element in the cell.
int next;
};
// Stores all the cells in the grid.
std::vector<GridCell> cells;
// Stores all the elements in the grid.
std::vector<GridElement> elements;
// Maybe some data for grid and cell size/AABBs.
...
};
Se lo fai in questo modo, sarei sorpreso se non arrivassi a una frazione di secondo almeno al primo tentativo, a condizione che la dimensione della tua cella fosse ragionevole in proporzione alla dimensione della mesh AABB *.
- There is admittedly some fiddling to the cell size you use for a grid to often get the most out of it. In my case I used like a trial-and-error approach where I constructed a test case and benchmark involving a variety of meshes and tried to come up with a simple function to try to quickly approximate a decent cell size based on the resolution of the mesh combined with the size of its AABB which would give optimal times for each test case without benefiting one at the cost of the other. That fiddliness still tends to apply though to some degree even if you use tree structures here, especially with the kind of content you can find in VFX (which isn't always cleaned up very much and could have coincident polygons and such) to limit the tree depth, for example. I tend to favor grids a lot in VFX even in cases where trees seem more optimal theoretically since the disgusting kind of content that hasn't been cleaned up that you can encounter here can cause those types of structures to want to split indefinitely (even loose variants and ones that split tris/polys where nodes split: imagine 30 triangles right on top of each other sharing all three vertex positions), whereas the grid at least doesn't choke like that on those cases.