Discussion :

[rpereira]

Bonjour à tous ^^ ceci est mon 1er message sur le forum. J'avais l'habitude de trainer sur des fofo anglais, donc n'hésitez pas à me signaler si quelque chose ne va pas dans mon message.

J'ai un petit problème d'algorithmie, et je cherche une solution optimale.

Origine du problème:
Je developpe un editeur de modèle 3D à base de voxel pour mon moteur de jeu.
Ces modèles 3D sont construits à partir de voxel cubique.
En gros, un modèle c'est un tableau à 3 dimensions de blocks, à partir desquelles je genère la mesh qui corresponds.
J'aimerai bien pouvoir assigner différents 'skins' à mes modèles. Donc j'utilise une texture sur laquelle les triangles de ma mesh sont mappés.
Le problème: comment mapper au mieux les vertex de ma mesh.

Problème (allez voir l'image d'exemple que j'ai mise à la fin du post, ce sera plus clair):
• Etant donnée: une liste de plans, ou chaque plan est contient par un doublet (largeur, hauteur)

• Je souhaite:

1) obtenir la plus petite dimension d'une texture pouvant contenir tous ces plans, sans chauvechement

2) obtenir la 'position', et l'orientation des plans, de sorte à ce qu'il soit tous présent sur cette texture, sans chevauchement. La 'position' (x, y) et 'l'orientation' (0 ou 1 si renversé ou non) indique comment mon plan est mappé sur la texture:

Des pixels (x, y) à (x + largeur, y + hauteur) s'il n'est pas renversé

Des pixels (x, y) à (x + hauteur, y + largeur) s'il est renversé

IMPORTANT: Il y a, à priori, plusieurs solutions optimales possibles (voir exemple). Je voudrais juste un algorithme autre que du brute forcing, qui permettent d'obtenir une solution acceptable 'rapidement'.
Quand à l'exemple donnée, la partie "extraction des plans" est déjà implementer (voir code source)

Merci d'avance pour votre temps!

Source code: https://github.com/rpereira-dev/Voxe...esherCull.java
Example: ("LEFT" est renversé une fois mappé ici)
Screenshot:

[pseudocode]

Bonsoir,

J'avoue ne pas avoir compris le sens caché derrière "obtenir la plus petite dimension ...".
S'agit-il d'avoir un rectangle englobant de surface minimale ? ou le plus carré possible ? ou avec le moins de trou ?

Quoi qu'il en soit, je pense que tu cherches à faire du packing 2D.

comme cela: http://codeincomplete.com/posts/bin-packing/demo

[tbc92]

J'ai fait un effort, mais arrivé ici : comment mapper au mieux les vertex de ma mesh, je dois avouer que j'ai décroché.

A propos des vertex de ma mesh, faut pas que j'oublie de prendre rendez-vous avec mon coiffeur.