Introdução à Programação de Jogos
Ray Casting
Universidade Federal do Rio de Janeiro
Pedro Demasi
[email protected]
http://www.labic.nce.ufrj.br/jogos
Introdução
• O que é Ray Casting?
– Técnica que permite transformar uma representação
simples de dados numa projeção 3D.
• Quando ficou “famoso”?
– Wolfenstein 3D, em 1992.
• Por que estudar Ray Casting?
– Técnica relativamente fácil de aprender que pode
produzir resultados interessantes mesmo com pouco
poder computacional devido à sua simplicidade.
Introdução
Introdução
• Idéia Básica
• Quais jogos usaram Ray Casting?
–
–
–
–
–
Wolfestein 3D
Doom
Dark Forces
Shadow Caster
Arena
– Determinar a visibilidade de superfícies traçando raios
imaginários de luz do olho do observador até os
objetos na cena.
Introdução
• Ray Casting x Ray Tracing
– Ray Casting é uma subclasse de Ray Tracing.
• Ray Tracing: traça um raio de luz para cada ponto na tela.
• Ray Casting: traça um raio de luz para cada coluna na tela.
– Comparação:
• Ray Casting: mais rápido, mais simples, menos realista.
• Ray Tracing: muito lento, um pouco mais complicado,
muito realista.
Introdução
• Limitações do Ray Casting
– Ângulo entre paredes e chão ou teto deve ser sempre
reto.
– Impossibilidade de aplicar uma rotação em torno do
eixo Z.
– As paredes são feitas de cubos do mesmo tamanho.
– Cubos pequenos diferentes podem permitir uma
“ilusão” de tamanhos diferentes maiores, porém
quanto menor for o tamanho do cubo, mais lento será
o processo.
1
Mundo
• Tendo em mente as limitações do Ray Casting,
podemos começar a criar um mundo (o mapa).
• O mapa é geralmente feito em arquivo de texto.
• Um possível mapa (# = bloco, . = vazio):
########
#...#..#
#......#
#...#..#
########
Características de Projeção
• Campo de Visão (FOV, Field Of View)
– O FOV é o ângulo de visão que a pessoa tem.
– Em geral, perto de 90 graus.
– Usaremos FOV = 60 (valor empírico).
Características de Projeção
• Coordenadas
– Suponhamos que o mapa tenha largura W e altura H.
– Cada bloco representa 64x64 pontos.
– Logo, uma coordenada (x,y) no mundo representa a
coordenada (x / 64, y / 64) no mapa.
– As coordenadas vão de (0, 0) a (64*W - 1, 64*H - 1)
no mundo e de (0, 0) a (W - 1, H - 1) no mapa.
Mundo
• Definições
– Aresta do cubo: 64 (preferencialmente potência de 2,
devido à rapidez de operações de shift).
– Cada bloco representa 64x64 pontos no mapa (2D) e
64x64x64 pontos na projeção (3D).
– Origem (0,0) no canto inferior esquerdo do mapa.
– Resolução de vídeo usada: 320x200 (lembre-se:
origem da tela no canto superior esquerdo).
– Eixo horizontal é origem do ângulo. Ângulo positivo
no sentido anti-horário.
Características de Projeção
• Tamanho do jogador
– É a altura que o jogador terá proporcionalmente no
mundo. Sendo a parede de altura 64, usaremos a
altura do jogador como 32 (metade da parede).
Características de Projeção
• Ângulo de Visão
– Ângulo que o centro da visão do jogador forma com a
horizontal. Indica em que direção o jogador está
olhando.
2
Características de Projeção
• Ponto de Visão (POV)
– O POV do jogador é definido pelas coordenadas (Px,
Py) do ponto do mundo em que ele está, junto com o
ângulo de visão.
– Logo, a tripla (Px, Py, ângulo de visão) é informação
suficiente para que a cena seja desenhada.
– Lembrando que o jogador tem FOV de 60 graus, logo
o campo dele vai de (ângulo de visão - FOV/2) a
(ângulo de visão + FOV/2) em relação à horizontal.
Características de Projeção
• Plano de projeção: é a tela do monitor que, na
verdade, é um plano onde se projetam (em 2D) os
objetos do mundo virtual em 3D.
Características de Projeção
• Ilustração da distância do jogador para o plano de
projeção:
Características de Projeção
• Sabemos que a dimensão do plano de projeção é
320x200 (resolução da tela).
• Sabemos que o FOV é de 60 graus.
• Precisamos lançar 320 raios (um para cada
coluna).
• O ângulo entre cada raio deve ser de FOV /
colunas.
• Logo, o ângulo entre cada raio será de 60 / 320 =
0,1875 grau
Características de Projeção
• O centro do plano de projeção é (160,100).
• O centro da visão do jogador coincide com o
centro do plano de projeção.
• Queremos encontrar a distância do jogador para o
plano de projeção.
• Logo, tan(FOV/2) = (colunas/2) / distância =>
distância = 160 / tan(30).
• Distância = 277,12813 ≅ 277
Lançando Raios
• Tendo calculado as informações anteriores, agora
lançamos um raio para cada coluna até que o
mesmo atinja uma parede.
• Calculamos a distância
deste raio e, baseados nessa
distância, calculamos o
tamanho (em pontos) que
esse “feixe” de parede terá
na tela.
3
Algoritmo Básico
• a = ângulo de visão - 30
• para cada coluna, de 0 a 319, faça:
–
–
–
–
Lance um raio com ângulo a
Trace o raio até que atinja uma parede
d = distância para a parede
Baseado na distância, desenhe o feixe da parede na
coluna atual
– Incremente a de 0,1875
Interseções
• A melhor forma é verificar interseções
horizontais e verticais separadamente. Depois,
usa-se a menor distância entre as duas como a
distância de interseção.
• Na figura anterior, os pontos horizontais são A,
C, D e F e os verticais B e E.
• A interseção horizontal seria em D e a vertical em
E. Como a distância para D é menor do que a
para E, o ponto D é escolhido como interseção.
Interseções Horizontais
• Ya = 64, se 0 < a < 180
• Ya = -64, se 180 < a < 360
• Pela figura, vemos que temos um
triângulo cujos catetos são Xa e a
altura do bloco (64).
• Logo, tan(a) = 64 / Xa
• Xa = ±64 / tan(a) (positivo para a
direita, negativo para a esquerda)
Interseções
• Quando raio é traçado, não precisamos verificar
cada ponto do percurso por uma interseção.
• Ao invés disso, apenas
verificamos as bordas das
células para saber se o raio
atingiu uma parede (pontos
A, B, C, D, E e F). No caso,
o algoritmo irá parar no
ponto D (atingiu a parede).
Interseções Horizontais
• Determinando o primeiro ponto (A, na figura):
• (Px,Py) são as coordenadas
(x,y) do jogador.
• Depois que achamos o
ponto A (Ax,Ay), os
demais são todos na forma
(Ax + kXa, Ay + kYa),
onde Xa e Ya são os
incrementos e k um inteiro.
Interseções Horizontais
• Py / 64 nos dá a posição y no mapa do jogador.
• Logo, (Py / 64) * 64 nos dá a posição y da borda
horizontal inferior do bloco do jogador (note
que Py / 64 é uma divisão inteira e, portanto, o
resultado é arredondado para baixo).
• Por exemplo, se Py = 133, Py / 64 = 2, e a borda
horizontal está em 128.
• Lembre-se de que essa é borda horizontal
inferior do jogador.
4
Interseções Horizontais
• Ay = (Py / 64) * 64, se 180 < a < 360
• Ay = (Py / 64) * 64 + 64, se 0 < a < 180
• Sabendo Ay, podemos calcular Ax, pois Ax - Px
e Ay - Py formam dois catetos de um triângulo.
• Logo, tan(a) = (Ay-Py) / (Ax-Px)
• Ax-Px = (Ay-Py) / tan(a)
• Ax = (Ay-Py) / tan(a) + Px
Interseções Verticais
• Se a < 90 ou a > 270
– Xa = 64
– Bx = (Px / 64) * 64 + 64
– By = (Bx-Px) * tan(a) + Py
• se 90 < a < 270
– Xa = -64
– Bx = (Px / 64) * 64
– By = (Bx-Px) * tan(a) + Py
• Ya = ± 64 * tan(a)
Calculando o Tamanho do Feixe
• Sabendo a distância d do raio, a distância do para
o plano de projeção (277) e o tamanho do bloco
(64), por semelhança de triângulos temos:
• 64/d = h/277
• h = (64*277)/d
• Sendo h o
tamanho do
feixe da parede
na tela.
Interseções Horizontais
• Sabendo (Ax,Ay) e tendo Xa e Ya, basta variar
um inteiro k a partir de 0 até que o ponto (Ax +
kXa, Ay + kYa) coincida com um bloco.
• Para checar a interseção, sabendo (Ax,Ay),
fazemos:
– x’ = Ax / 64
– y’ = Ay / 64
– Se a posição (x’,y’) do mapa é preenchida por um
bloco, então ocorreu interseção.
Calculando a Distância
• Seja (Ix, Iy) o ponto de interseção. Ix-Px e Iy-Py
formam os catetos dum triângulo cuja hipotenusa
é justamente a distância.
• Há várias formas de calcular d:
– d = √((Ix-Px)² + (Iy-Py)²)
– d = | Ix-Px | / cos(a)
– d = | Iy-Py | / sen(a)
• Usaremos funções trigonométricas pois elas
podem ser facilmente tabeladas (otimização).
O Efeito “Aquário”
• Devido ao uso conjunto de coordenadas cartesianas
e polares, acontece uma distorção da distância,
quanto mais afastado for o ângulo do ângulo
central de visão. Na figura abaixo, A e C deveriam
ter a mesma distância. Porém C terá uma distância
maior que A.
• O resultado é
ilustrado na
figura da direita.
5
O Efeito “Aquário”
• Para corrigir, verificamos na figura abaixo que a
distância errada é a hipotenusa de um triângulo e o
distância correta o seu cateto adjacente. Onde b é o
ângulo do raio em relação ao ângulo de visão.
• cos(b) = d_correta / d => d_correta = d * cos(b)
O Efeito “Aquário”
•
•
•
•
Lembrando que h = (64 * 277) / d
Temos que d_correta = d * cos(b)
Logo, h = (64 * 277) / (d * cos(b))
Como b é o ângulo do raio em relação ao ângulo
de visão, temos que b = a - ângulo de visão
• Tendo h, basta pintar uma linha de (col, 100 - h/2)
a (col, 100 + h/2), onde col é a coluna atual de raio.
• A constante 100 representa a linha central da tela.
Resultado
Relembrando...
•
•
•
•
•
•
•
O que é Ray Casting?
Ray Casting x Ray Tracing
Limitações
Mundo / Mapa de blocos
Campo de Visão (FOV)
Tamanho do jogador
Coordenadas
Relembrando...
•
•
•
•
•
•
•
Ângulo de Visão
Ponto de Visão (POV)
Plano de projeção
Centro do plano de projeção
Distância para o plano de projeção
Algoritmo básico
Interseções
Relembrando...
• Interseções horizontais
–
–
–
–
–
–
Encontrando Xa e Ya
Encontrando Ax e Ay
Verificando (Ax + kXa, Ay + kYa), k ≥ 0
Verificando se o raio bateu num obstáculo
Calculando a distância para o obstáculo
Tabelamento de funções trigonométricas
6
Relembrando...
• Interseções verticais
• Texturas a serem utilizadas (parede, chão e teto
respectivamente):
– Caso análogo ao das horizontais
•
•
•
•
•
Texturas
Calculando altura do feixe a ser desenhado
Desenhando o feixe
O efeito “Aquário”
Corrigindo o efeito “Aquário”
Resultado
Texturas
• Ao invés de paredes com cores fixas, queremos
mapear texturas nos blocos (assim como no chão
e no teto também).
• Temos a altura de cada feixe, sua posição na tela,
e sabemos em que bloco do mapa o raio colidiu.
• Lembremos do ponto I (Ix,Iy).
• Sabemos qual é o bloco olhando na posição (Ix /
64, Iy / 64) do mapa de blocos.
Texturas
• Queremos, dados o bloco, o tamanho do feixe e
sua posição, desenhar uma linha da textura
correspondente, com o respectivo tamanho, nessa
coluna. Ou seja:
Texturas
Texturas
• Como descobrir qual coluna da textura devemos
desenhar?
• Como descobrir qual coluna da textura devemos
desenhar?
• Se a interseção foi
vertical, basta pegar
(Iy % 64).
• Se a interseção foi
horizontal, basta pegar
(Ix % 64).
7
Texturas
Chão
• Sabemos onde desenhar, o que desenhar e com
qual tamanho.Ao invés de desenhar uma linha
com o tamanho do feixe, desenhamos a coluna
correspondente na textura desejada com o
tamanho do feixe:
• Já temos texturas na parede, agora queremos no
chão também.
• Floor Casting:
Chão
Chão
• Só precisamos traçar o chão visível. Ou seja,
aquilo que não está encoberto pelas paredes.
• Iniciamos a partir do
final do feixe de
parede para aquela
coluna, linha por
linha, até chegarmos
ao fim da tela.
– Trace um raio e encontre uma interseção com o chão
– Determine o ponto do mundo em que houve a
interseção
– Calcule a distância
– Desenhe proporcionalmente
• Para encontrar a distância para o chão, usamos
novamente semelhança de triângulos.
• P é o ponto real e PJ é a projeção, então:
– (distância para P) / (distância para o plano) = (altura
do jogador) / (linha PJ - linha central).
• A distância é dada por:
– d = (32*277) / (linha-100)
Chão
• Essa distância ainda não é a que desejamos, pois
ela representa a distância em linha reta e não em
ângulo:
• Logo:
– d_certa = d/cos(b)
– onde b é o ângulo
em relação ao
ângulo de visão
(logo 0 ≤ b ≤ 30º)
Chão
• Agora que sabemos a distância, precisamos saber
que ponto da textura desenhar.
• Ora, usando o ponto do jogador (Px,Py) como
referencial, a distância para o chão d_certa é a
hipotenusa de um triângulo retângulo, e seus
catetos são as distâncias x e y (em relação ao
jogador). Logo:
– dx = d_certa * cos(a)
– dy = d_certa * sen(a)
8
Chão
• Sabendo (dx,dy), basta somarmos a (Px,Py) para
obtermos as coordenadas, no mundo, do ponto de
interseção do chão.
• Logo P_chão = (dx+Px, dy+Py).
• Agora, para saber qual o pixel correspondente da
textura, basta fazer ((dx + Px) % 64, (dy + Py) %
64)) e temos o pixel correspondente no bitmap da
textura de chão.
Teto
• Análogo ao chão. A diferença está na fórmula:
• d = (64 * 277) / (100 - linha)
• Inicia-se a partir do início do feixe da parede e
vai subindo até terminar a tela.
Efeitos - Andando
• Jogador está na posição (Px,Py) e tem um ângulo
de visão a.
• Dada uma velocidade v de deslocamento, ao
andar para frente, a nova posição será:
– Px = Px + (v * cos(a))
– Py = Py + (v * sen(a))
• Ao andar para trás, a nova posição será:
– Px = Px - (v * cos(a))
– Py = Py - (v * sen(a))
Efeitos - Girando
• Ao se pressionar setas para direita ou esquerda, o
jogador faz uma pequena rotação em seu ângulo
de visão (ou seja, como se ele estivesse girando o
corpo em torno de seu eixo).
• Seja um incremento a’ de ângulo de visão, o novo
ângulo de visão a será:
– a = a + a’ (esquerda)
– a = a - a’ (direita)
Efeitos - Olhar para cima/baixo
• Para simular um efeito de olhar para cima e para
baixo, basta mudarmos o centro horizontal do
plano (que inicia como 100). Seja c o centro e c’
o incremento, temos então:
– c = c - c’ (para baixo)
– c = c + c’ (para cima)
Efeitos - Corrida
• Para simular o efeito de um corrida, em que
oscilamos um pouco a visão, basta aplicar uma
senóide ao centro horizontal c no cálculo da nova
posição (Px, Py).
– c = c + sen(passo) * K
• Onde passo é um ângulo que vai sendo
incrementado na corrida e K é uma constante
qualquer (quando maior K, mais tremida será a
visão).
9
Efeitos - Colisão
• Para evitar que o jogador atravesse paredes,
precisamos detectar colisão.
• Se a nova posição (Px, Py) do jogador no mapa
de blocos estiver ocupada, volta para a posição
antiga.
• Ou seja, verifica se a posição (Px / 64, Py / 64) no
mapa de blocos é um bloco. Em caso positivo,
não atualiza a posição.
Sugestões para Implementação
• Iluminação / Sombreamento
– Usar paleta de forma segmentada.
– Efeitos (água, gosma, neblina etc.)
– Pontos mais distantes mais escuros, pontos mais
próximos mais claros.
• Transparência
– Verificar transparência no bloco e continuar o raio.
– Pilha de interseções. Desenhando feixes de trás para
frente.
Sugestões para Implementação
• Blocos de tamanhos variáveis.
• Mais de um mapa de blocos (ou seja, cada um
representando um nível do ambiente).
• Inimigos
– Implementar inimigos.
– Atacando, defendendo, colidindo.
10