Discussion :

[Orci76]

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 .

[Obsidian]

Bonjour,

J'ai mis beaucoup de temps à comprendre ce que tu voulais dire, mais je pense que l'on peut résumer cela ainsi : tu cherches à fusionner des cubes adjacents et similaires en parallélépipèdes de dimensions arbitraires, pourvu que ce soit toujours des parallélépipèdes, et à fusionner judicieusement les cubes de façon à minimiser le nombre de ces parallélépipèdes ainsi produits.

Tu nous précises également que ce choix est un problème similaire au rendu de monnaie et que l'optimal dépend de la valeur des pièces, ce qui est pertinent mais partiellement vrai seulement : ce serait applicable si les dimensions possibles des blocs finaux étaient limitées mais que leur nombre ne dépendait que du nombre initial de cubes, indépendamment de leur disposition. Toi, tu es dans la situation inverse : les dimensions des blocs sont libres, mais ils doivent obligatoirement remplir un cluster de cubes adjacents. Par conséquent, le problème doit être traité individuellement pour chacun de ces clusters.

Une fois ceux-ci identifiés, je pense sans être un expert que l'approche la plus pertinente doit être celle des BSP.
Voir par exemple ici : http://fr.wikipedia.org/wiki/Partiti..._de_l%27espace

[Orci76]

Salut,

Désolé, j'ai essayé d'être explicite, mais c'était de toute évidence pas le cas :p.

Je te remercie pour ta réponse ; je n'avais pas pensé à cette solution.
Je pense que cette dernière devrait faire l'affaire, j'essayerais de l'appliquer.

Merci, bonne soirée .