NavMesh :: Optimalizace tri-meshe

[VODA]

Zdravím lidi,

provádím nějaké optimalizace navmeshů. No a klasický způsob, jak snížit počet uzlů grafu takového navmeshe je pospojovat několik trianglů do konvexních polygonů. Ale nějak nemohu vymyslet obecný postup, jak něco takového udělat.
Přikládám dva obrázky pro ty, co to nepochopili z textu:



Možná že za nějaký čas na to přijdu sám, ale proč se o takovou věc nepodělit s ostatními...

Díky za pomoc...

Pozn.: Všiml jsem si pár chybiček v tom druhém obrázku...udělal jsem tam jeden nekonvexní polygon...a někde jsem mohl polygon vytvořit větší...
_________________
Opravdovost se pojí s trýzní...

[micky]

Nejsem si jistý, jestli lze najít nejoptimálnější variantu, aniž bys otestoval všechny kombinace... Ale tak zkusil bych vždycky začít na jednom trojúhelníku a seskupit celé okolí do konvexního polygonu (dokud by to šlo). Následně bych přešel k dalšímu trojúhelníku. Ale to nejoptimálnější řešení nenajde... Jen najde cosi přijatelného... možná.
_________________
https://www.bluepulsar.cz/
https://twitter.com/11thDream_Game/

[igor]

Trojúhelníky jsou v rovině nebo obecně v prostoru?

Prý je to NP-úplné pro obecné polygony s dírami, lepší je to pro polygony bez děr (které by z toho meshe ale měly jít vytvořit).

Zahlédl jsem nějaké papery
http://www.cs.unc.edu/~snoeyink/papers/ (ten On the time bound for convex decomposition of simple polygons)
http://cs.gmu.edu/~jmlien/research/app-cd/

Moc jsem je nestudoval, tak nevím, jestli nejsou nepoužitelné nebo nechutně složité (jak už to u paperů bývá

Mě mimo soutěž napadá akorát něco docela primitivního heuristického - přiřadíš párům trojúhelníků nějaké hodnoty, podle kterých bude lepší spojovat právě je (velikost? počet sousedů? podobnost? něco s úhly? všechno dohromady?), vybereš nejlepší pár a tyto trojúhelníky spojíš (vznikne polygon, kterému opět přiřadíš hodnotu a dále počítáš). Vzniklé polygony bude do toho třeba nějak zařadit (ať už nějak rovnocenně s trojúhelníky nebo ihned se snažit co nejlepší trojúhelníky na polygon nalepit dokud bude pořád konvexní). A dál provádět dokud to bude možné nebo dokud nebude dosaženo nějaké časové/trojúhelníkové hranice. Není optimální, složitost blbá, ale předpokládám, že to je spíš pro nějaký preprocessing.

Pak třeba BSP by to dokázalo nějak rozdělit na konvexní útvary, ale kvalita zase záleží na výběru rovin/přímek a hlavně to rozsekává trojúhelníky, což by ale možná šlo nějak řešit (držet informace o rozseknutích a zkoušet zpětně spojit? To ale může selhávat, občas po rozseknutí 2 konvexní útvary nevytvoří spolu konvexní útvar, ale kdyby se tam přidal třetí, tak jo...)

No nic chytrého jsem koukám nenapsal, hlavně koukni na ty články, pokud je ještě nemáš za sebou.

Jo a ještě tohle vypadá jednoduše http://www.philvaz.com/compgeom/

[VODA]

Ach jo, za tento týden jsem s tím skoro vůbec nehnul. Začínám přemýšlet jestli bych raději neměl zrychlit nějakým způsobem algoritmus na předpočítání pathfindingu...
Stavající algoritmus je založen na Floyd-Warshallovi...ale když to nechám počítat při loadingu, tak na nějakých obrovských datech se to počítá příliš dlouho (N^3)...a zase se mi nechce předpočítávat tabulku mimo jádro do souboru...
No a když použiju A* za běhu, tak bude zas pomalejší generování cesty (resp. směru pohybu)...
Pořád uvažuji o zahrnutí Recast&Detour, ale stále se mi nepodařilo sehnat nějakou pořádnou dokumentaci a z těch jejich kódů se mi to luštit nechce (jednak jsem línej a jinak mám spousta další práce do školy)...

Tak já nevím...tohle mě tak dojebává...
_________________
Opravdovost se pojí s trýzní...

[VODA]

Já jsem věděl, že to časem dokážu...

Původní mesh:


Optimalizace:


Je pravda, není to ještě úplně ideální, ale algoritmus se snaží najít co největší polygony...trochu ještě zlobí test na konvexnost (když jsou dvě sousední hrany rovnoběžné), ale to se ještě pokusím dát dohromady...

U tohoto navmeshe se snížil počet uzlů z 92 na 41, což znamená, že v tomto případě se výpočet floyda přibližně 11x zrychlí. Je jasné, že to zavisí na sestavení meshe...může se stát, že se třeba nemusí vůbec zoptimalizovat, ale takový případ snad nenastane.
_________________
Opravdovost se pojí s trýzní...