Dynamic Shadow는 광원의 위치가 계속 바뀌고 그에 따라 그림자가 변하는 효과입니다. 공포/잠입 게임에 사용하면 현실감을 좀 더 높여줄 수 있다고 생각합니다. 생각나는 게임으로는 Monaco, Among Us가 있습니다. 공포/잠입 게임은 아니지만 Celeste 에서도 사용 되었습니다. 관련글

크게 Ray Casting과 Shadow Casting 방식이 있는데 뭐가 더 좋다고 할 수는 없는 듯 합니다. Ray Casting의 경우 CPU 비용이 크지만 실제 영역을 계산할 수 있고 Shadow Casting의 경우 무식하긴한데 무식함을 GPU로 커버하여 더 빠르게 그릴 수 있습니다.

Ray Casting

Ray Casting 방식은 광원으로 부터 모든 방향으로 빛을 쏘아서 가장 가까운 방해물까지 그리는 방식입니다. 방해물은 제일 단순한 선분으로 생각합니다. 방해물이 다각형이라면 여러개의 선분들로 구성하여 표현할 수 있습니다. 실제로 모든 방향으로 광선을 쏠 수는 없고 선분의 끝 지점만 쏘아서 계산할 수 있습니다.

광선을 쏠 때 마다 모든 선분들과 교차점을 판별하게 된다면 시간이 간선의 개수의 제곱에 비례하게 됩니다. 광선과 교차하지 않는 선분들이 대부분일건데 이를 제외하고 계산하면 좋을것 같습니다. 그래서 Sweeping 기법을 사용할 것인데 광선을 각도순을 쏜다면 이전 정보를 활용할 수 있습니다. 각도를 움직일 때 마다 교차하는 선분 집합을 계속 업데이트 하고 집합에 있는 선분들만 확인하면 됩니다.

1. 선분 끝지점의 각도로 해당 선분이 추가되는지 제거되는지 Event라고 합시다.
2. Event를 각도순으로 정렬하고 각 Event마다..
   1. 현재 교차하는 선분들 중 가장 가까운 선분을 구하고 이를 s라고 합시다.
   2. s로 이전 각도, 현재 각도로 광선을 발사하였을 때 교점을 각각 a, b라고 한다면 답안에 (0, a, b) 삼각형을 추가합니다.
3. 선분 집합을 업데이트 후 다음 각도로 이동합니다.

방법만 들으면 쉬운데 실제로는 구현이 좀 까다롭습니다. 특히 두 선분이 끝점이 교차하는 경우 어느 것을 먼저 빼느냐에 따라 교차점이 달라지기 때문에 잘 처리해야 합니다.

전체적인 시간은 (간선의 개수)*(평균적인 교점 개수) + (정렬 시간) 이 될 것 같습니다. 어려운 난이도에 비해 극적으로 시간이 줄지는 않았네요.

BOJ에 이를 구현하는 문제 그림자가 있습니다. 32ms로 정답을 받았는데 Lua라서 느린것도 있고 실제로 생각한 최적화까지는 구현을 못했습니다. 발로 짠듯한 코드긴한데 혹시라도 보고 싶으신 분이 있다면 여기서 보실 수 있습니다. LÖVE 코드도 들어가 있어서 LÖVE로도 실행할 수 있습니다.

스위핑 부분이 다름 사람보다 비효율적이긴하나 정렬 부분에서 시간이 많이 들어서 한계가 명확하다고 생각됩니다. LÖVE로 구현해봤는데 선분이 2500정도에 광원이 10개 정도 되는 경우 40fps정도 였고 정렬만 해도 60fps가 안되었습니다.

Shadow Casting

Ray Casting이 빛을 그리는 방식이였다면 Shadow Casting은 그림자를 그리는 방식입니다. 그림자 영역을 먼저 그리고 빛을 그릴 때 그림자 영역을 제외하고 빛 영역을 그립니다.

이 동영상을 많이 참고 하였습니다.

설명을 글로 적어보려고 했는데 설명이 힘들고 영상이 잘 되어 있어서 설명은 위의 영상으로 대체합니다. 해당 영상은 게임 메이커로 구현하였는데 LÖVE로 구현해 보았습니다.

코드가 길어서 핵심부분만 올렸는데 위 동영상을 봤다면 대충 느낌은 올거라고 생각됩니다.

function ShadowSystem:addPolygon(key, vertices)
  local b = {}
  for i=1, #vertices do
    local u = vertices[i]
    local v = vertices[i < #vertices and i+1 or 1]
    table.insert(b, {u[1], u[2], 0})
    table.insert(b, {v[1], v[2], 0})
    table.insert(b, {u[1], u[2], 1})
    table.insert(b, {v[1], v[2], 0})
    table.insert(b, {v[1], v[2], 1})
    table.insert(b, {u[1], u[2], 1})
  end

  local mesh = love.graphics.newMesh({
      {"VertexPosition", "float", 3}
    },
    b, "triangles", "static"
  )

  self.meshes[key] = mesh
end

ShadowSystem.shadowShader = love.graphics.newShader(
[[
  vec4 effect( vec4 color, Image tex, vec2 texture_coords, vec2 screen_coords ) {
    return vec4(0.0); // 그리는거 없이 depth값만 업데이트
  }
]],
[[
  uniform float depth;
  uniform vec2 lpos;
  vec4 position( mat4 transform_projection, vec4 vertex_position ) {
    vec2 d = vertex_position.xy - lpos;
    vertex_position.xy += 100000.0 * normalize(d) * vertex_position.z;

    vec4 ret = transform_projection * vertex_position;
    ret.z = depth;
    return ret;
  }
]])
ShadowSystem.lightShader = love.graphics.newShader(
[[
  vec4 effect( vec4 color, Image tex, vec2 uv, vec2 screen_coords ) {
    float d = length(uv - 0.5)*2.0;
    float b = max(1.0 - d, 0);
    return color*b;
  }
]],
[[
  uniform float depth;
  vec4 position( mat4 transform_projection, vec4 vertex_position ) {
    vec4 ret = transform_projection * vertex_position;
    ret.z = depth;
    return ret;
  }
]])
ShadowSystem.lightMesh = love.graphics.newMesh({
  {0, 0, 0, 0},
  {1, 0, 1, 0},
  {0, 1, 0, 1},
  {1, 1, 1, 1},
}, "strip") --정사각형 mesh

function ShadowSystem:clear()
  local g = love.graphics
  g.setCanvas({self.canvas, depthstencil = self.depthBuffer})
  g.clear(0.0, 0.0, 0.0, 1, false, 1.0) -- rgb를 0으로 depth를 1로
  g.setCanvas()
  self.depth = 1.0
end

function ShadowSystem:lightPoint(lx, ly)
  --준비
  local g = love.graphics
  g.setCanvas({self.canvas, depthstencil = self.depthBuffer}) --canvas 설정
  g.setDepthMode("less", true) --depth값이 더 적다면 그린다.
  g.setBlendMode("add") --빛은 additive

  self.depth = self.depth - 1 / 2^13

  g.setShader(self.shadowShader)
  g.setColor(0, 0, 0)
  self.shadowShader:send("depth", self.depth)
  self.shadowShader:send("lpos", {lx, ly})
  for key, mesh in pairs(self.meshes) do
    g.draw(mesh)
  end

  local radius = 20
  g.setShader(self.lightShader)
  self.lightShader:send("depth", self.depth)
  g.draw(self.lightMesh, lx-radius, ly-radius, 0, 2*radius, 2*radius)

  --정리
  g.setBlendMode("alpha")
  g.setDepthMode()
  g.setCanvas()
  g.setShader()
end

function love.draw()
  local g = love.graphics

  ShadowSystem:clear()
  for _, light in ipairs(lights) do
    local lx, ly = unpack(light)
    ShadowSystem:lightPoint(lx, ly)
  end

  ShadowSystem:draw()
  g.draw(fgCanvas)
end

위는 800x800 해상도에 광원 100개를 그린 것입니다. GPU를 90%로 태워먹고 있지만 60fps을 유지하고 있습니다. 참고한 동영상과는 다르게 해상도가 커서 불필요하게 그리는 그림자영역이 매우 많은데 최적화 할 여지가 있는지 고민해야겠습니다.