Imagine um mundo baseado em cubos (como Minecraft, Trove ou Cube World), onde tudo é composto de cubos de tamanho idêntico e todos os cubos são do mesmo tipo .
O objetivo é representar o mundo com o menor número de caixas retangulares (mesclando cubos, mas mantendo a forma convexa (também conhecida como forma de caixa retangular)). Meu algoritmo consegue isso, mas seu desempenho é muito lento para o objetivo a que se destina. Existem algoritmos mais rápidos?
O código pseudo-C # para o meu algoritmo é basicamente:
struct Coordinate { int x,y,z; }; //<-- integer based grid
HashSet<Coordinate> world; // <-- contains all the cubes
//width, height, and length represent how many cubes it spans
struct RectangularBox { Coordinate coord; int width,height,length; }
void Begin()
{
List<RectangularBox> fewestBoxes = new List<RectangularBox>();
while(world.Count > 0)
{
RectangularBox currentLargest = ExtractLargest();
fewestBoxes.Add(currentLargest);
world.RemoveRange(currentLargest.ContainedCubes());
}
//done; `fewestBoxes` contains the fewest rectangular boxes needed.
}
private RectangularBox ExtractLargest()
{
RectangularBox largestBox = new RectangularBox();
foreach (Coordinate origin in world)
{
RectangularBox box = FindMaximumSpan(origin);
if (box.CalculateVolume() >= largestBox.CalculateVolume())
largestBox = box;
}
return largestBox;
}
private RectangularBox FindMaximumSpan(Coordinate origin)
{
int maxX, maxY,maxZ;
while (world.Contains(origin.Offset(maxX, 0, 0))) maxX++;
while (world.Contains(origin.Offset(0, maxY, 0))) maxY++;
while (world.Contains(origin.Offset(0, 0, maxZ))) maxZ++;
RectangularBox largestBox;
for (int extentX = 0; extentX <= maxX; extentX++)
for (int extentY = 0; extentY <= maxY; extentY++)
for (int extentZ = 0; extentZ <= maxZ; extentZ++)
{
int lengthX = extentX + 1;
int lengthY = extentY + 1;
int lengthZ = extentZ + 1;
if (BoxIsFilledWithCubes(origin, lengthX, lengthY, lengthZ))
{
int totalVolume = lengthX * lengthY * lengthZ;
if (totalVolume >= largestBox.ComputeVolume())
largestBox = new RectangularBox(origin, lengthX, lengthY, lengthZ);
}
else
break;
}
return largestBox;
}
private bool BoxIsFilledWithCubes(Coordinate coord,
int lengthX, int lengthY, int lengthZ)
{
for (int gX = 0; gX < lengthX; gX++)
for (int gY = 0; gY < lengthY; gY++)
for (int gZ = 0; gZ < lengthZ; gZ++)
if (!world.Contains(coord.Offset(gX, gY, gZ)))
return false;
return true;
}
Essencialmente, para cada bloco do mundo, ele primeiro descobre quantos blocos contíguos existem em cada uma das três dimensões positivas (+ X, + Y, + Z). E então meio que preenche esse volume e verifica qual é o maior preenchimento que não está faltando nenhum bloco.
Atualização: Como parecia sugerir que isso era para o mecanismo de renderização de um jogo, só quero esclarecer que isso não é para o mecanismo de renderização de um jogo; é para um conversor de arquivos; sem GUI.
fonte
Respostas:
Você pode fazer uso do fato de que quando
retorna true, não é necessário verificar
BoxIsFilledWithCubes(c,x+1,y,z)todos os cubos no intervalo de coordenadas "(c, x, y, z)" novamente. Você só precisa verificar esses cubos com a nova coordenada xc.x + (x+1). (O mesmo vale paray+1, ouz+1). De maneira mais geral, dividindo uma caixa em duas caixas menores (para as quais você já deve saber se elas estão cheias de cubos ou se não estão cheias), é possível aplicar aqui uma técnica de dividir e conquistar, que se torna mais rápida que a sua abordagem original quando você armazena em cache os resultados intermediários.Para fazer isso, você começa a implementar
BoxIsFilledWithCubes(c,x,y,z)recursivamente, por exemplo:e use a memorização (como discutido aqui ) para evitar chamadas repetidas para
BoxIsFilledWithCubesos mesmos parâmetros. Observe que você terá que limpar o cache de memorização ao aplicar uma alteração ao seuworldcontêiner, como porworld.RemoveRange. No entanto, acho que isso tornará seu programa mais rápido.fonte
Crie um octree com um nó folha aabb do tamanho da sua caixa. Ao percorrer o octree, você pode mesclar nós de maneira barata. Nós completamente preenchidos são triviais para mesclar (nova caixa = aabb pai), enquanto que para nós parcialmente preenchidos, você pode usar uma variante do seu algoritmo atual para verificar a capacidade de mesclagem.
fonte
Você parece ter pelo menos O (n ^ 2) (veja a notação O grande ) ao percorrer todas as caixas do mundo em "Begin ()"; depois, para cada caixa, percorrer todas as caixas do mundo em ExtractLargest ( ) Portanto, um mundo com 10 caixas não relacionadas levará 4 vezes mais tempo do que um mundo com 5 caixas não relacionadas.
Portanto, você precisa limitar o número de caixas que ExtractLargest () deve examinar, para fazer isso, você precisa usar algum tipo de pesquisa espacial , enquanto trabalha em 3d, talvez seja necessário uma pesquisa espacial em 3d. No entanto, primeiro comece entendendo a pesquisa espacial em 2D.
Então considere se você terá muitas caixas por cima uma da outra, se não, uma pesquisa espacial em 2D que cubra apenas x, y pode ser suficiente para reduzir o loop.
Octree / quadtree são uma opção, mas existem muitas outras opções para particionamento de espaço ,
Mas você pode usar apenas uma matriz bidimensional de listas ( índice espacial de grade ), onde todas as caixas que cobrem o ponto (a, b) estão na matriz [a, b] .list. Mas o mais lamentavelmente isso levaria a uma matriz muito grande, e quanto à matriz [mod (a, 100), mob (b, 100)]. Tudo isso depende de como são os seus dados .
(Vi a solução da rede funcionar muito bem na vida real.)
Ou faça o que Wilbert diz com uma octree com um nó de folha aabb do tamanho da sua caixa, mas mais tarde você provavelmente encontrará a caixa que o mouse do usuário está apontando etc, mais uma vez, um caso de pesquisa espacial.
( Você deve decidir se está apenas tentando fazer com que este software funcione ou se está tentando entender como ser um programador melhor e, portanto, está mais interessado no aprendizado do que em uma solução rápida. )
fonte