Como posso gerar um efeito de raio?

26

Existe um algoritmo para gerar um raio?

Eu gostaria de um algoritmo que gere uma lista de objetos de segmento ou ponto, especificando onde o parafuso pousará. O método precisaria de um parâmetro de ponto inicial, juntamente com um ponto final. O parafuso deve ter ramificações aleatórias saindo e zig-zag em intervalos aleatórios. O resultado será um efeito aleatório de raio que se pareceria com isso


(fonte: wikimedia.org )

Se alguém souber de um algoritmo para o qual isso funcione, a ajuda será muito apreciada!

Geoffroi
fonte
2
Este documento da Nvidia deve ser exatamente o que você precisa, embora possa ser um pouco extenso. Verifique os slides 7 a 11, eles têm algumas boas ideias que devem lhe dar uma idéia do que apontar. Se você seguir o segundo link, encontrará o código fonte (C ++, Direct3D). developer.download.nvidia.com/SDK/10/direct3d/Source/Lightning/… developer.download.nvidia.com/SDK/10/direct3d/samples.html
Falha

Respostas:

32

Existe um algoritmo bastante simples que você pode usar para gerar parafusos de iluminação.

Comece com um segmento de linha entre a origem do parafuso ( O) e o ponto final ( E)

Escolha um ponto nessa linha (aproximadamente ou exatamente no meio), chamado Se divida o segmento em dois segmentos de linha ( O->Se S->E). Deslocar Spara longe a partir do segmento de linha original (ao longo do segmento normal) por alguma pequena quantidade aleatória. Isso fornece uma única "curva" de raio.

Depois de calcular a dobra, com base em uma pequena chance aleatória, convém adicionar um terceiro segmento de linha (geralmente uma extensão do O->Ssegmento). É assim que você produz os "garfos" no raio. Geralmente, você deseja rastrear informações sobre a intensidade do parafuso durante esse processo de geração, porque deseja que os garfos sejam mais escuros ou com um borrão mais sutil:

insira a descrição da imagem aqui

Em seguida, repita o processo acima para todos os novos segmentos de linha que você possui; você precisará escolher uma quantidade de repetição que produza as formas que você gosta:

insira a descrição da imagem aqui

Há uma explicação bastante clara dessa técnica no blog do meu amigo aqui (é de onde eu descaradamente roubei as fotos); Ele também tem uma profundidade adicional sobre a adição do efeito de brilho.

Finalmente, há também este documento da NVIDIA que descreve o mesmo algoritmo básico (também com mais detalhes).

Josh
fonte
13

Eu recomendaria uma abordagem alternativa: a árvore aleatória de exploração rápida (TRR) . Uma coisa legal sobre isso é que você pode fazê-lo girar nas esquinas ou explodir em todas as direções.

O algoritmo é realmente básico:

// Returns a random tree containing the start and the goal.
// Grows the tree for a maximum number of iterations.
Tree RRT(Node start, Node goal, int maxIters)
{
    // Initialize a tree with a root as the start node.
    Tree t = new Tree();
    t.Root = start;


    bool reachedGoal = false;
    int iter = 0;

    // Keep growing the tree until it contains the goal and we've
    // grown for the required number of iterations.
    while (!reachedGoal || iter < maxIters)
    {
         // Get a random node somewhere near the goal
         Node random = RandomSample(goal);
         // Get the closest node in the tree to the sample.
         Node closest = t.GetClosestNode(random);
         // Create a new node between the closest node and the sample.
         Node extension = ExtendToward(closest, random);
         // If we managed to create a new node, add it to the tree.
         if (extension)
         {
             closest.AddChild(extension);

             // If we haven't yet reached the goal, and the new node
             // is very near the goal, add the goal to the tree.
             if(!reachedGoal && extension.IsNear(goal))
             {
                extension.AddChild(goal);
                reachedGoal = true;
             }
         }
         iter++;
    }
    return t;
}

Modificando as funções RandomSamplee ExtendToward, você pode obter árvores muito diferentes. Se RandomSampleapenas amostrar uniformemente em todos os lugares, a árvore crescerá uniformemente em todas as direções. Se for enviesado em direção ao objetivo, a árvore tenderá a crescer em direção ao objetivo. Se sempre amostrar a meta, a árvore será uma linha reta desde o início até a meta.

ExtendTowardpode permitir que você faça coisas interessantes para a árvore também. Por um lado, se você tiver obstáculos (como paredes), poderá fazer com que a árvore cresça ao redor deles simplesmente rejeitando extensões que colidem com paredes.

É assim que você parece quando você não influencia a amostra em direção à meta:

img
(fonte: uiuc.edu )

E aqui está o que parece com paredes

Algumas propriedades legais do RRT quando terminar:

  • O RRT nunca se cruzará
  • O RRT eventualmente cobrirá todo o espaço com filiais cada vez menores
  • O caminho desde o início até a meta pode ser completamente aleatório e estranho.
mklingen
fonte
Eu apenas usei esse algoritmo para gerar uma animação de raio. Devo dizer que funcionou muito bem! Há um erro de digitação importante no código, como o iter não sendo incrementado a cada loop. Outras que este está quase pronto para usar como postada
applejacks01