Hello,
(TL;DR + images explicatives en bonus !)
Pour commencer, désolé pour ce nom légèrement incompréhensible, j'ai fait de mon mieux! :p
Histoire de m'amuser un peu sur quelque chose que je n'avais jamais essayé, je me suis lancé dans la construction d'un engine/jeu 3D utilisant des voxels (aka. clone de Cube World / Minecraft).
Même si mon cell shading est pour le moins dégueulasse, j'ai en 1-2 jours réussie à afficher un monde plus ou moins correct: http://puu.sh/gsqXX/d223033442.png
J'avais au début un problème assez important. Mes chunks font 16*16*48, et même si je n'avais qu'à les régénérer qu'à chaque changement sur l'un d'eux (= un block cassé par exemple), celle-ci prenait ~1s. C'était assez embêtant d'avoir 1s de lag à chaque action... bref, j'ai descendu ce temps à 0.15s en ne représentant pas les cubes entre 6 autres (logique), puis à 0.075s en faisant quelque chose d'autre (EDIT: Bon, je suis passé à 0.04s en faisant ce dont je parle ci-dessous pour X et Z aussi, ce qui fait 1/25s donc plus ou moins passable, mais peut-être pas encore assez -- d'autant que ça m'énerve de ne pas optimiser le truc) , mais ça reste toujours trop grand.
Du coup, mes cubes étant formés de 8 arrêtes et 24 triangles (sans compté le cell shading qui rajoute 8 arrêtes et 12 lignes), et je me suis donc dit qu'il était possible de les fusionner avec ceux à côté d'eux s'ils étaient du même type (couleur), ce que j'ai fait ici (sur l'axe Y seulement) --> http://puu.sh/guNFt/943360031a.png
J'ai donc réfléchis à la façon la plus optimale de séparer l'espace, et me suis dit que faire en DP fonctionnerait bien (avec un "marqueur" d'extension pour l'axe X et un pour l'axe Y).
Ça n'a pas fonctionné dès le début, comme montre ce dessin. Du coup, j'ai considéré que s'il y avait un truc au-dessus-à-gauche de toi, il fallait aussi reset les Y, ce que j'ai fait ici, mais ça posait encore un problème -- le plus gros rectangle aurait du être tout à droite et faire 9/2, mais il a été coupé en 7/2 (bien qu'on puisse merge avec le 1/2 du dessus). Cette approximation ne me dérange pas, étant donné que l'algorithme est en O(N), et que j'ai vu des gens sur Internet proposé des O(N^3), bien que je n'ai pas trouvé grand chose.
Cependant, ce n'est pas exactement O(N), étant donné que je devrais ré-appliquer l'algorithme à chaque rectangle -- ce qui serait aussi le cas avec la O(N^3) -- parce que, par exemple, le triangle vert est noté 2/2, mais il devient 1/2 à cause du jaune.
Du coup, considérant que ma map fait 16*16*48, ça nous donne une complexité de 12288*beaucoup (selon le nombre de pavés de plus de 1*1*1 faisables).
De plus, je suis même pas sur que ça nous donne la meilleure répartition -- ce problème me rappelant celui du rendu de monnaie, "Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal."
TL;DR
En bref, j'aimerais savoir, s'il vous plait, comment serait-il possible de connaître la séparations optimale (= le moins de rectangles/pavés possible, même si ce n'est pas forcement les plus gros) pour une map[x][y][z] en 3D.
Merci d'avance, et désolé pour la lecture -- c'était pour mettre dans le contexte, mais c'est parti un petit peu en vrille :p.
Bonne soirée .
Partager