Elenco de raio - Ray casting
Ray casting é a base metodológica para modelagem de sólidos CAD / CAM 3-D e renderização de imagens. É essencialmente o mesmo que traçado de raio para computação gráfica, onde os raios de luz virtuais são "lançados" ou "traçados" em seu caminho a partir do ponto focal de uma câmera através de cada pixel no sensor da câmera para determinar o que é visível ao longo do raio no Cena 3-D. O termo "Ray Casting" foi introduzido por Scott Roth enquanto trabalhava nos Laboratórios de Pesquisa da General Motors de 1978-1980. Seu artigo, "Ray Casting for Modeling Solids", descreve objetos sólidos modelados combinando sólidos primitivos, como blocos e cilindros, usando os operadores de conjunto união (+), interseção (&) e diferença (-). A ideia geral de usar esses operadores binários para modelagem de sólidos se deve em grande parte ao grupo de modelagem geométrica de Voelcker e Requicha na Universidade de Rochester. Consulte Modelagem de sólidos para uma ampla visão geral dos métodos de modelagem de sólidos. Esta figura à direita mostra uma junta U modelada a partir de cilindros e blocos em uma árvore binária usando o sistema de lançamento de raios de Roth, por volta de 1979.
Antes do lançamento do raio (e traçado do raio), os algoritmos de computação gráfica projetavam superfícies ou bordas (por exemplo, linhas) do mundo 3-D para o plano da imagem onde a lógica de visibilidade tinha que ser aplicada. A projeção do plano de mundo para imagem é uma transformação do sistema de coordenadas homogênea 3-D (também conhecida como: projeção 3D , transformação afim ou transformação projetiva ( homografia )). Renderizar uma imagem dessa maneira é difícil de conseguir com a remoção de superfície / borda oculta. Além disso, as silhuetas de superfícies curvas devem ser explicitamente resolvidas, embora seja um subproduto implícito da projeção de raios, portanto, não há necessidade de resolvê-lo explicitamente sempre que a vista muda.
A projeção de raios simplificou muito a renderização de imagens de objetos e cenas 3-D porque uma linha se transforma em uma linha. Portanto, em vez de projetar bordas e superfícies curvas na cena 3-D para o plano da imagem 2-D, as linhas transformadas (raios) são cruzadas com os objetos na cena. Uma transformação de coordenadas homogênea é representada por uma matriz 4x4. A técnica matemática é comum para computação gráfica e modelagem geométrica. Uma transformação inclui rotações em torno dos três eixos, escala independente ao longo dos eixos, translações em 3-D e até mesmo inclinação. As transformações são facilmente concatenadas por meio da aritmética de matriz. Para uso com uma matriz 4x4, um ponto é representado por [X, Y, Z, 1] e um vetor de direção é representado por [D x , D y , D z , 0]. (O quarto termo é para tradução e não se aplica a vetores de direção.)
Embora simplifique a matemática, o algoritmo de projeção de raios exige muito do processamento do computador. A Pixar tem grandes fazendas de renderização, edifícios com 1000 CPUs, para fazer suas animações usando traçado de raios [também conhecido como "lançamento de raios"] como uma técnica central.
Conceito
Ray casting é o mais básico de muitos algoritmos de renderização de gráficos de computador que usam o algoritmo geométrico de traçado de raio . Algoritmos de renderização baseados em Ray tracing operam em imagem para renderizar cenas tridimensionais em imagens bidimensionais. Raios geométricos são traçados a partir do olho do observador para amostrar a luz ( radiância ) viajando em direção ao observador a partir da direção do raio. A velocidade e a simplicidade da projeção de raios vêm do cálculo da cor da luz sem traçar recursivamente os raios adicionais que mostram a radiação incidente no ponto em que o raio atingiu. Isso elimina a possibilidade de renderizar com precisão os reflexos , refrações ou a queda natural das sombras ; no entanto, todos esses elementos podem ser falsificados até certo ponto, pelo uso criativo de mapas de textura ou outros métodos. A alta velocidade de cálculo fez do ray casting um método de renderização útil nos primeiros videogames 3D em tempo real .
A ideia por trás da projeção de raios é rastrear os raios do olho, um por pixel, e encontrar o objeto mais próximo bloqueando o caminho desse raio - pense em uma imagem como uma porta de tela, com cada quadrado na tela sendo um pixel. Este é então o objeto que o olho vê através daquele pixel. Usando as propriedades do material e o efeito das luzes na cena, esse algoritmo pode determinar o sombreamento desse objeto. A suposição simplificadora é feita de que se uma superfície estiver voltada para uma luz, a luz alcançará essa superfície e não será bloqueada ou na sombra. O sombreamento da superfície é calculado usando modelos tradicionais de sombreamento de gráficos de computador 3D. Uma vantagem importante oferecida pelo ray casting em relação aos algoritmos de linha de varredura mais antigos era sua capacidade de lidar facilmente com superfícies não planas e sólidos, como cones e esferas . Se uma superfície matemática pode ser interceptada por um raio, ela pode ser renderizada usando a projeção de raios. Objetos elaborados podem ser criados usando técnicas de modelagem de sólidos e facilmente renderizados.
Do resumo do artigo "Ray Casting for Modeling Solids": Para visualizar e analisar os sólidos compostos modelados, raios de luz virtuais são lançados como sondas. Em virtude de sua simplicidade, o lançamento de raios é confiável e extensível. O problema matemático mais difícil é encontrar os pontos de intersecção da linha com a superfície. Portanto, superfícies como planos, quádricas, toros e, provavelmente, até remendos de superfície paramétricos podem limitar os sólidos primitivos. A adequação e eficiência da projeção de raios são questões abordadas aqui. Uma capacidade de geração rápida de imagens para modelagem interativa é o maior desafio.
Os raios de luz e a geometria da câmera formam a base de todo o raciocínio geométrico aqui. Esta figura mostra um modelo de câmera pinhole para efeito de perspectiva no processamento de imagem e um modelo de câmera paralela para análise de massa. O modelo simples de câmera pinhole consiste em um ponto focal (ou ponto de visão) e uma matriz quadrada de pixels (ou tela). Raios de luz retos passam pela matriz de pixels para conectar o ponto focal à cena, um raio por pixel. Para sombrear fotos, as intensidades dos raios são medidas e armazenadas como pixels. A superfície refletora responsável pelo valor de um pixel cruza o raio do pixel.
Quando a distância focal, distância entre o ponto focal e a tela, é infinita, a visualização é chamada de “paralela” porque todos os raios de luz são paralelos entre si, perpendiculares à tela. Embora a vista em perspectiva seja natural para fazer imagens, algumas aplicações precisam de raios que possam ser uniformemente distribuídos no espaço.
Para conveniência de modelagem, um sistema de coordenadas padrão típico para a câmera tem a tela no plano XY, a cena no meio espaço + Z e o ponto focal no eixo -Z.
Um raio é simplesmente uma linha reta no espaço 3-D do modelo da câmera. É melhor definido como um vetor de direção na forma parametrizada como um ponto (X 0 , Y 0 , Z 0 ) e um vetor de direção (D x , D y , D z ). Neste formulário, os pontos na linha são ordenados e acessados por meio de um único parâmetro t. Para cada valor de t, um ponto correspondente (X, Y, Z) na linha é definido:
X = X0 + t · Dx Y = Y0 + t · Dy Z = Z0 + t · Dz
Se o vetor for normalizado, o parâmetro t é a distância ao longo da linha. O vetor pode ser normalizado facilmente com o seguinte cálculo:
Dist = √(Dx2 + Dy2 + Dz2) Dx = Dx / Dist Dy = Dy / Dist Dz = Dz / Dist
Dadas as definições geométricas dos objetos, cada um delimitado por uma ou mais superfícies, o resultado do cálculo da interseção de um raio com todas as superfícies delimitadas na tela é definido por duas matrizes,
Ray parameters: t[1], t[2], ..., t[n] Surface pointers: S[1], S[2], ..., S[n]
onde n é o número de interseções da superfície do raio. A lista ordenada de parâmetros de raio t [i] denota os pontos de entrada-saída. O raio entra em um sólido no ponto t [1], sai em t [2], entra em um sólido em t [3], etc. O ponto t [1] está mais próximo da câmera e t [n] está mais longe. Em associação com os parâmetros de raio, os ponteiros de superfície contêm um endereço exclusivo para as informações da superfície interceptada. A superfície pode ter várias propriedades, como cor, especularidade, transparência com / sem refração, translucidez, etc. O sólido associado à superfície pode ter suas próprias propriedades físicas, como densidade. Isso pode ser útil, por exemplo, quando um objeto consiste em uma montagem de diferentes materiais e o centro de massa geral e os momentos de inércia são de interesse.
Aplicando as informações
Três algoritmos que usam a projeção de raios são para fazer desenhos de linha, para fazer imagens sombreadas e para calcular volumes e outras propriedades físicas. Cada algoritmo, dado um modelo de câmera, lança um raio por pixel na tela. Para calcular o volume, a resolução da tela de pixel a ser usada depende da precisão desejada da solução. Para desenhos de linha e sombreamento de imagem, a resolução determina a qualidade da imagem.
DESENHOS DE LINHA . Para desenhar as arestas visíveis de um sólido, gere um raio por pixel movendo de cima para baixo, da esquerda para a direita na tela. Avalie cada raio para identificar a superfície visível S [1], o primeiro ponteiro de superfície na lista classificada de interseções de raio-superfície. Se a superfície visível na localização do pixel (X, Y) for diferente da superfície visível no pixel (X-1, Y), exiba uma linha vertical com um pixel de comprimento centralizado em (X-½, Y). Da mesma forma, se a superfície visível em (X, Y) for diferente da superfície visível no pixel (X, Y-1), exiba uma linha horizontal com um pixel de comprimento centralizado em (X, Y-½). O desenho resultante consistirá em bordas horizontais e verticais apenas, parecendo recortadas nas resoluções do curso.
O sistema de lançamento de raios de Roth gerou as imagens de objetos sólidos à direita. Compartimentos de caixa, limitação dinâmica e coerência foram usados para otimização. Para cada imagem, a tela foi amostrada com uma densidade de cerca de 100x100 (por exemplo, 10.000) raios e novas bordas foram localizadas por meio de buscas binárias. Em seguida, todas as arestas foram seguidas pelo lançamento de raios adicionais em incrementos de um pixel nos dois lados das arestas. Cada imagem foi desenhada em um tubo Tektronix com resolução de 780x780.
IMAGENS SOMBREADAS . Para fazer uma imagem sombreada, lance novamente um raio por pixel na tela. Desta vez, no entanto, use o ponteiro de superfície visível S [1] em cada pixel para acessar a descrição da superfície. A partir disso, calcule a normal da superfície no ponto visível t [1]. O valor do pixel, a intensidade de luz exibível, é proporcional ao cosseno do ângulo formado pela normal de superfície e o vetor fonte de luz para a superfície. O processamento de todos os pixels dessa maneira produz uma imagem do tipo raster da cena.
COMPUTAÇÃO DE VOLUME E MOMENTOS DE INÉRCIA . O volume (e propriedades semelhantes) de um sólido delimitado por superfícies curvas é facilmente calculado pelo método de integração de “somas aproximadas”, aproximando o sólido com um conjunto de paralelepípedos retangulares. Isso é feito tirando uma foto “detalhada” do sólido em uma vista paralela. A projeção de raios através da tela para o sólido divide o sólido em elementos de volume. Duas dimensões dos paralelepípedos são constantes, definidas pelo espaçamento 2-D dos raios na tela. A terceira dimensão é variável, definida pelo ponto de entrada-saída calculado. Especificamente, se as distâncias horizontal e vertical entre os raios na tela são S, então o volume "detectado" por cada raio é
S × S × (t[2]-t[1] + t[4]-t[3] + ∙∙∙ + t[n]-t[n-1]) / L
onde L é definido como o comprimento do vetor de direção. (Se já normalizado, isso é igual a 1.)
L = √(Dx2 + Dy2 + Dz2)
Cada ( t [ i ] - t [ i -1]) / L é um comprimento de um segmento de raio que está dentro do sólido.
Esta figura mostra os paralelepípedos para um sólido modelado usando a projeção de raios. Este é um uso do modelo de câmera de projeção paralela.
Classificação de raio dentro e fora
Esta figura mostra um exemplo dos operadores binários em uma árvore de composição usando + e - onde um único raio é avaliado.
O procedimento de lançamento do raio começa no topo da árvore de composição de sólidos, desce recursivamente para o fundo, classifica o raio em relação aos sólidos primitivos e, em seguida, retorna para cima na árvore combinando as classificações das subárvores esquerda e direita.
Esta figura ilustra a combinação das classificações esquerda e direita para todos os três operadores binários.
Imagens realistas sombreadas
Ray casting é uma ferramenta de modelagem natural para fazer fotos sombreadas. O sistema de ray-casting em tons de cinza desenvolvido por Scott Roth e Daniel Bass no GM Research Labs produziu imagens em uma tela raster colorida Ramtek por volta de 1979. Para compor as imagens, o sistema fornecia ao usuário os seguintes controles:
View
• Viewing direction and position
• Focal length: width-angle perspective to parallel
• Zoom factor
Illumination
• Number of light sources
• Locations and intensities of lights
• Optionally shadow
• Intensities of ambient light and background
Surface Reflectance
• % reflected diffusely
• % reflected specularly
• % transmitted
Esta figura mostra uma cena de mesa com sombras de duas fontes de luz pontuais.
Os algoritmos de sombreamento que implementam todos os efeitos realistas são computacionalmente caros, mas relativamente simples. Por exemplo, a figura a seguir mostra os raios adicionais que podem ser lançados para uma única fonte de luz.
Para um único pixel na imagem a ser renderizado, o algoritmo projeta um raio começando no ponto focal e determina que ele cruza um retângulo semitransparente e um círculo brilhante. Um raio adicional deve então ser lançado a partir daquele ponto na direção simetricamente oposta à normal da superfície no ponto de interseção da superfície do raio para determinar o que é visível na reflexão espelhada. Esse raio cruza o triângulo que é opaco. Finalmente, cada ponto de interseção da superfície do raio é testado para determinar se está na sombra. O raio “sensor de sombra” é lançado a partir do ponto de interseção da superfície do raio até a fonte de luz para determinar se alguma outra superfície bloqueia esse caminho.
Turner Whitted chama os raios secundários e adicionais de “Rastreamento de raio recursivo”. [Uma sala de espelhos seria cara para renderizar, então limitar o número de recursões é prudente.] Refração modelada em branco para transparências gerando um raio secundário do ponto da superfície visível em um ângulo determinado pelo índice de refração do sólido. O raio secundário é então processado como um raio especular. Para a fórmula de refração e exemplos pictóricos, consulte o artigo de Whitted.
Compartimentos e eficiência
O lançamento de raios se qualifica como um método de força bruta para resolver problemas. O algoritmo mínimo é simples, principalmente em consideração às suas muitas aplicações e facilidade de uso, mas as aplicações normalmente lançam muitos raios. Milhões de raios podem ser lançados para renderizar um único quadro de um filme de animação. O tempo de processamento do computador aumenta com a resolução da tela e o número de sólidos / superfícies primitivas na composição.
Ao usar caixas delimitadoras mínimas em torno dos sólidos na árvore de composição, a busca exaustiva por uma interseção de raio-sólido assemelha-se a uma busca binária eficiente. O algoritmo de força bruta faz uma pesquisa exaustiva porque sempre visita todos os nós na árvore - transformando o raio em sistemas de coordenadas locais dos primitivos, testando as interseções da superfície do raio e combinando as classificações - mesmo quando o raio claramente perde o sólido. Para detectar um “erro claro”, um algoritmo mais rápido usa a árvore de composição binária como uma representação hierárquica do espaço que a composição sólida ocupa. Mas todas as informações de posição, forma e tamanho são armazenadas nas folhas da árvore onde residem os sólidos primitivos. Os nós superior e intermediário na árvore especificam apenas os operadores de combinação.
Caracterizar com compartimentos o espaço que todos os sólidos preenchem fornece a todos os nós da árvore um resumo abstrato das informações de posição e tamanho. Em seguida, os testes rápidos “ray intersects cerco” guiam a busca na hierarquia. Quando o teste falha em um nó intermediário da árvore, é garantido que o raio se classifique como fora do composto, portanto, é desnecessário recorrer às suas subárvores para uma investigação mais aprofundada.
Avaliar com precisão a economia de custos para o uso de gabinetes é difícil porque depende da distribuição espacial dos primitivos (a distribuição de complexidade) e da organização da árvore de composição. As condições ideais são:
- Nenhum invólucro primitivo se sobrepõe no espaço
- A árvore de composição é equilibrada e organizada de modo que os sub-sólidos próximos do espaço também estejam próximos da árvore
Em contraste, a pior condição é:
- Todos os invólucros primitivos se sobrepõem mutuamente
A seguir estão diversas melhorias de desempenho feitas no artigo de Roth sobre fundição de raios, mas houve melhorias consideráveis posteriormente feitas por outros.
- Early Outs . Se o operador em um nó de composição na árvore for - ou & e o raio se classificar como fora do sub-sólido esquerdo do composto, então o raio será classificado como fora do composto, independentemente da classificação do raio em relação ao sub-sólido direito sólido. Portanto, classificar o raio em relação ao sub-sólido correto é desnecessário e deve ser evitado para maior eficiência.
- Transformações . Ao combinar inicialmente a transformação de tela para cena com a transformação de cena para local do primitivo e armazenar as transformações de tela para local resultantes nas estruturas de dados do primitivo, uma transformação de raio por interseção de superfície de raio é eliminada.
- Recursão . Dada uma árvore de composição profunda, a recursão pode ser cara em combinação com a alocação e liberação de memória. A recursão pode ser simulada usando matrizes estáticas como pilhas.
- Limitação dinâmica . Se apenas as arestas visíveis do sólido devem ser exibidas, o algoritmo de projeção de raio pode vincular dinamicamente o raio para interromper a pesquisa. Ou seja, depois de descobrir que um raio intercepta um sub-sólido, o algoritmo pode usar o ponto de interseção mais próximo da tela para apertar o limite de profundidade para o teste de “caixa de interseção de raio”. Isso só funciona para a parte + da árvore, começando no topo. Com - e &, partes próximas “dentro” do raio podem mais tarde se tornar “fora”.
- Coerência . O princípio de coerência é que as superfícies visíveis em dois pixels vizinhos têm maior probabilidade de serem iguais do que diferentes. Os desenvolvedores de computação gráfica e sistemas de visão aplicaram essa verdade empírica para obter eficiência e desempenho. Para desenhos de linha, a área da imagem que contém as bordas é normalmente muito menor do que a área total da imagem, portanto, a projeção de raios deve ser concentrada em torno das bordas e não nas regiões abertas. Isso pode ser implementado de forma eficaz através da amostragem esparsa da tela com raios e, em seguida, localizando, quando os raios vizinhos identificam diferentes superfícies visíveis, as arestas por meio de buscas binárias.
Anti-aliasing
As bordas irregulares causadas pelo aliasing são um efeito indesejável das técnicas de amostragem de pontos e um problema clássico com algoritmos de exibição de varredura. Bordas lineares ou suavemente curvas parecerão recortadas e são particularmente questionáveis em animações porque o movimento da imagem faz com que as bordas pareçam difusas ou pareçam pequenas escadas rolantes em movimento. Além disso, detalhes na cena menores que o espaçamento entre os raios podem ser perdidos. As bordas irregulares em um desenho de linha podem ser suavizadas seguindo a borda. O objetivo desse algoritmo é minimizar o número de linhas necessárias para desenhar a imagem com a precisão de um pixel. Resultado de bordas suaves. Os desenhos de linha acima foram desenhados desta forma.
Para suavizar as bordas irregulares em uma imagem sombreada com precisão de subpixel, raios adicionais devem ser lançados para obter informações sobre as bordas. (Consulte Superamostragem para uma abordagem geral.) As bordas são formadas pela interseção de superfícies ou pelo perfil de uma superfície curva. Aplicando "Coerência" conforme descrito acima por meio de pesquisa binária, se a superfície visível no pixel (X, Y) for diferente da superfície visível no pixel (X + 1, Y), então um raio poderia ser gerado no meio deles em (X + ½, Y) e a superfície visível aí identificada. A distância entre os pontos de amostra pode ser subdividida ainda mais, mas a busca não precisa ser profunda. A profundidade de pesquisa primária para suavizar bordas denteadas é uma função do gradiente de intensidade ao longo da borda. Uma vez que (1) a área da imagem que contém bordas é geralmente uma pequena porcentagem da área total e (2) os raios extras lançados em buscas binárias podem ser limitados em profundidade - a dos primitivos visíveis que formam as bordas - o custo para suavizar bordas irregulares é acessível.
História da formação de raios
Para a história do lançamento de raios, consulte o traçado de raios (gráficos) porque ambos são basicamente a mesma coisa. Scott Roth inventou o termo "lançamento de raios" antes de ouvir falar de "rastreamento de raios". O desenvolvimento de modelagem de raios por Scott Roth no GM Research Labs ocorreu simultaneamente com o trabalho de rastreamento de raios de Turner Whitted no Bell Labs.
Ray casting nos primeiros jogos de computador
Nos primeiros jogos de primeira pessoa, o raycasting era usado para renderizar com eficiência um mundo 3D a partir de um campo de jogo 2D usando uma varredura unidimensional simples na largura horizontal da tela. Os primeiros jogos de tiro em primeira pessoa usaram a projeção de raios como técnica para criar um efeito 3D a partir de um mundo 2D. Embora o mundo pareça 3D, o jogador não pode olhar para cima ou para baixo ou apenas em ângulos limitados com distorção de cisalhamento, porque isso permite renderizar o campo de jogo 2D mais rápido.
Wolfenstein 3D
O mundialmente famoso videogame Wolfenstein 3D foi construído a partir de uma grade quadrada de paredes de altura uniforme que se encontram com pisos e tetos de cores sólidas. Para desenhar o mundo, um único raio foi traçado para cada coluna de pixels da tela e uma fatia vertical da textura da parede foi selecionada e dimensionada de acordo com onde no mundo o raio atinge a parede e a distância que percorre antes de fazê-lo.
O objetivo dos níveis baseados em grade era duplo - as colisões de ray-wall podem ser encontradas mais rapidamente, uma vez que os acertos potenciais se tornam mais previsíveis e a sobrecarga de memória é reduzida. No entanto, a codificação de áreas totalmente abertas exige espaço extra.
ShadowCaster
O jogo ShadowCaster da Raven Software usa um motor melhorado baseado em Wolfenstein com texturas de pisos e tetos adicionais e alturas variáveis de parede.
Série Comanche
O mecanismo Voxel Space desenvolvido pela NovaLogic para os jogos Comanche traçou um raio através de cada coluna de pixels da tela e testou cada raio contra pontos em um mapa de altura . Em seguida, ele transformou cada elemento do mapa de altura em uma coluna de pixels, determinada quais são visíveis (ou seja, não foram ocluídos por pixels que foram desenhados na frente), e os desenhou com a cor correspondente do mapa de textura.
Além do raycasting
Mais tarde, jogos DOS , como o DOOM da id Software, mantiveram muitas das restrições de raycasting 2.5D para velocidade, mas passaram a mudar para técnicas de renderização alternativas (como BSP ), tornando-os não mais mecanismos de raycasting.
Configuração de geometria computacional
Em geometria computacional , o problema de projeção de raio também é conhecido como o problema de disparo de raio e pode ser declarado como o seguinte problema de consulta: dado um conjunto de objetos no espaço d- dimensional, pré-processe-os em uma estrutura de dados de modo que para cada raio de consulta, o objeto inicial atingido pelo raio pode ser encontrado rapidamente. O problema foi investigado para várias configurações: dimensão do espaço, tipos de objetos, restrições aos raios de consulta, etc. Uma técnica é usar um voxel octree esparso .