Division spatiale alignée sur l'axe: diviser l'espace en rectangles aléatoires?

11

J'ai besoin d'une méthode pour diviser l'espace 3D en formes de boîtes alignées sur des axes aléatoires. Pour l'instant, je divise actuellement l'espace 2D à des fins de test. L'approche la plus immédiate que j'ai trouvée était de définir un rectangle de taille (1, 1), puis de diviser récursivement tous les rectangles existants en deux rectangles inégaux alternant entre les axes X et Y.

entrez la description de l'image ici

Le problème ici est évident. Cette approche entraîne de longues lignes d'étirement (marquées en rouge)

entrez la description de l'image ici

Ce que je voudrais, c'est quelque chose de plus organique (j'ai inclus un exemple)

Vous voyez, pas de longues lignes droites de haut en bas ou de gauche à droite.

entrez la description de l'image ici

La seule contrainte est que je puisse souhaiter limiter la taille minimale du rectangle sans affecter la granularité des tailles. c'est-à-dire si le plus petit rect est de 1 centimètre carré que la seconde plus petite pièce ne doit pas être de 2 unités carrées.

Donc, idéalement, l'algorithme devrait répondre aux trois contraintes suivantes:

  1. Les rectangles ne sont pas infiniment petits.
  2. Les tailles rect ne sont pas une multiplication discrète de la plus petite taille rect. c'est-à-dire que si le plus petit rect est de 3 unités carrées, les plus grands rectes ne sont pas limités à 6, 9, 12 et ainsi de suite, et peuvent donc être de 3,2 ou 4,7, d'ailleurs).
  3. L'algorithme s'exécute en temps polynomial (doit être calculé rapidement).
AturSams
la source

Réponses:

12

L'approche que vous décrivez est simple et utile, mais souffre de terribles artefacts comme indiqué. L'éviter. Vous avez besoin d'un algorithme de croissance parallèle; pour un modèle monothread, une approche à tour de rôle suit:

  1. Placez au hasard divers points dans votre espace de carte. Normaliser leur distribution (évite les regroupements laids) en utilisant la distribution gaussienne ou en appliquant un algorithme de relaxation itératif pour éloigner les points placés au hasard les uns des autres, conformément à la relaxation de Lloyd pour les diagrammes de Voronoi . Ces points représentent les centres de gravité de vos futures pièces.
  2. (Round-robin parallèle / répété pour toutes les pièces) À partir de chaque point, développez 4 sommets vers l'extérieur (une pièce rectangulaire), en vous déplaçant du point central par itération globale (vous pouvez agrandir différentes pièces à des taux différents dans chaque axe plutôt que les mêmes pour tous, et voyez comment cela se passe - peut-être pour un résultat plus organique / varié). À un moment donné, certains de vos rectangles commenceront à se presser. À ce stade, limitez la croissance dans cet axe, assurez-vous que les bords adjacents des deux pièces se touchent exactement et continuez.
  3. Répétez l'étape 2, en augmentant progressivement chaque pièce, jusqu'à ce que toute croissance soit limitée par les pièces adjacentes ou les limites de la carte.
  4. Cela laissera toujours des espaces vides. Le problème devient maintenant celui de localiser et de créer des pièces à partir d'espaces non occupés. En fait, si votre espace sous-jacent est une grille (indexée sur un nombre entier) (et chaque itération de croissance s'aligne sur cette grille), cela est beaucoup plus facile à gérer, car vous pouvez maintenir des listes de cellules de grille occupées et inoccupées: une fois que vous '' ve placé et agrandi toutes vos chambres, recherchez dans la liste inoccupée des espaces discrets constitués de groupes de cellules adjacentes. Comme de nombreux espaces inutilisés auront des formes non rectangulaires, vous devrez choisir une cellule au hasard dans cet espace non rectangulaire et la développer à sa taille maximale comme vous l'avez fait avec des pièces à l'étape 2. Répétez dans ledit non -espace rectangulaire, jusqu'à ce qu'il soit complètement rempli.
  5. Répétez l'étape 4 jusqu'à ce que votre carte soit occupée à 100%.
Ingénieur
la source
C'est un bon conseil. L'inconvénient est qu'il ne fait peut-être rien pour me protéger des rects infiniment petits. J'ai besoin d'une manière de limiter la taille et la taille des rects. Actuellement, je suis en train de travailler sur une autre méthode. Je vais comparer les résultats et mettre à jour.
AturSams
@ArthurWulfWhite Votre question était alors sous-spécifiée et devrait être mise à jour. La taille minimale de votre pièce est déterminée par la résolution de votre cellule de carte; Donc, si vous faites ce grain assez grossier pour accueillir la taille minimale de la pièce, vous pouvez ensuite ajuster les axes en virgule flottante, en retournant un aspect plus organique.
Ingénieur
Vous avez raison! Je pensais avoir écrit cette partie. Mais non. Je m'excuse pour cette erreur. Oui, je connais la taille de la grille. Une pièce ne peut être aussi petite que le permet la grille.
AturSams
OK - j'espère que vous trouverez une solution appropriée. BTW, je voulais dire "ajuster les lignes de la grille", pas "ajuster les axes".
Ingénieur
1
En fait, je fais exactement quelque chose comme ça librement en me basant sur les concepts que vous me pensiez. Je publierai également les résultats ici.
AturSams
2

Comme vous pouvez le voir, j'ai réussi à débarrasser le monde de ces artefacts. L'idée est très similaire.

  1. Divisez l'espace 2D en une grille non uniforme. Si deux lignes sont trop proches, supprimez-en une.
  2. Choisissez un rectangle au hasard, vérifiez s'il a été modifié sur l'axe-y (en hauteur) et si son voisin direct a été modifié sur l'axe-y. Je n'ai pas été modifié tous les deux, demandez-leur de renégocier le segment entre eux (l'un donnera de l'espace à l'autre).
  3. Faites la même chose qu'à l'étape 2 mais cette fois sur l'autre axe.
  4. Répétez le processus jusqu'à ce que vous en ayez modifié autant que possible.

Grille non uniforme (1):

entrez la description de l'image ici

Négociation sur l'axe x (2):

entrez la description de l'image ici

Négociation sur l'axe y (3):

entrez la description de l'image ici

Résultat (4):

entrez la description de l'image ici

entrez la description de l'image ici

AturSams
la source
Cela a été vaguement inspiré par la perspicacité de @Nick Wiggill
AturSams
2
On pourrait encore améliorer cela en fusionnant d'abord de manière aléatoire des groupes de n * m cellules adjacentes en un seul rectangle. Cela masque la grille sous-jacente encore visible dans la sortie ci-dessus. La négociation avec ces grands rectangles doit désormais fonctionner sur toutes les cellules le long d'un de ses bords.
DMGregory
D'ACCORD. Encore un grand nombre de limites colinéaires, je travaillerais sur celles-ci plus loin, mais c'est bien que vous ayez trouvé votre solution! Heureux de vous aider.
Ingénieur
@DMGregory J'ai considéré cela, mais je voulais que le rapport entre les petits rects et les grands rects soit quelque peu cohérent. Si c'était une texture ou un niveau, je le ferais certainement (en fait, j'ai un exemple précédent qui fait ça).
AturSams
@NickWiggill Je peux éliminer complètement les lignes colinéaires. Il s'agit juste de peaufiner l'algorithme. Il doit y avoir un moyen de l'améliorer davantage (mise à jour avec la variation la plus récente)
AturSams