DragonRuby Ray Marching

main.rb

# Hold b to show squares (circles stay hidden)
# Press space to reset

# @param [GTK::Args] args
def tick(args)
  args.outputs.lines << args.state.lines if args.state.lines
  init(args) unless args.state.initialized && !args.inputs.keyboard.key_down.space
  rerender(args) unless args.state.render_ready && !args.inputs.keyboard.key_down.space && !args.inputs.keyboard.key_down.b && !args.inputs.keyboard.key_up.b
  pos = args.inputs.mouse.position
  pos ||= [640, 360]
  # args.state.lines = make_outline(pos, args.state.sde, 100, 10)
  args.state.lines = cheat_outline(pos, args.state.verts, args.state.sde)
  args.outputs.labels << [
      {x: 10, y: 30, text: "FPS: #{$gtk.current_framerate.to_s.to_i}", r: 255, g: 0, b: 0},
      {x: 10, y: 60, text: "LINES: #{args.state.lines.length}", r: 255, g: 0, b: 0}
  ]
end

# @param [GTK::Args] args
def rerender(args)
  prims = []
  prims << args.state.obstacles.flat_map(&:renderables) if args.inputs.keyboard.key_down.b
  args.outputs.static_primitives.clear
  args.outputs.static_primitives << prims
  args.state.render_ready = true
end

def max(a, b)
  a > b ? a : b
end

def min(a, b)
  a < b ? a : b
end

# @param [GTK::Args] args
def init(args)
  obstacles = []
  while obstacles.length < 4
    square = SquareObstacle.new(rand(1280), rand(720), rand(50) + 50)
    obstacles << square unless obstacles.any? do |o|
      square.right >= o.left &&
          square.left <= o.right &&
          square.top >= o.bottom &&
          square.bottom <= o.top
    end
  end
  obstacles            += (1..3).to_a.map { |_| CircleObstacle.new(rand(1280), rand(720), rand(50) + 50) }
  args.state.obstacles = obstacles
  # Instead of doing a map reduce over each obstacle to find the minimum distance,
  #   bake each obstacle's distance function into one big lambda function.
  # Is this a bad idea? Probably. Does it make things run faster? Definitely.
  args.state.sde   = eval "->(x,y) { [#{obstacles.map(&:dist_str).join(", ")}].reduce(&:lesser)}"
  args.state.verts = obstacles.flat_map { |o| o.verts } + [0, 1280].product([0, 720])

  args.state.initialized = true
end

# @param [Array<Numeric>] pos Initial position
# @param [Integer] max_iter Max number of iterations
# @param [Numeric] theta The angle to march at
# @param [Proc] sde The standard distance estimator for the world.
def march(pos, max_iter, theta, sde)
  x, y   = *pos
  r      = 0
  dx, dy = *(theta.vector)
  iter   = 0
  dist   = sde.yield(x, y)
  steps  = 1
  while iter < max_iter && dist > 0.1 && x >= 0 && x <= 1280 && y >= 0 && y <= 720
    if steps > 10000
      puts x, y, dx, dy, r, dist
      puts __LINE__
      break
    end
    steps     += 1
    last_dist = dist
    dist = sde.yield(x, y)
    x += dx * dist
    y += dy * dist
    r += dist
    if last_dist > dist
      iter += 1
    else
      iter = 0
    end
  end
  if x > 1280
    overshoot = (x - 1280) / dx
    x         -= overshoot * dx
    y         -= overshoot * dy
    r         -= overshoot.abs
  elsif x < 0
    overshoot = x / dx
    x         -= overshoot * dx
    y         -= overshoot * dy
    r         -= overshoot.abs
  end
  if y > 720
    overshoot = (y - 720) / dy
    x         -= overshoot * dx
    y         -= overshoot * dy
    r         -= overshoot.abs
  elsif y < 0
    overshoot = y / dy
    x         -= overshoot * dx
    y         -= overshoot * dy
    r         -= overshoot.abs
  end
  [
      x,
      y,
      r,
      steps
  ]
end

def d_theta(step, r, s)
  r_based     = step / r
  inflect     = 10
  inflect_div = step / (inflect * inflect)
  if r < inflect
    r_based = r * inflect_div
  end
  r_based.greater(1.0)
end

#
# This "cheats" by using an array of vertices. We only really need to cast rays out to each vertex,
# and a little to either side of each vertex, to get a good idea of what's going on.
#
def cheat_outline(pos, verts, sde)
  max_iter = 39
  # March to each vertex
  thetas   = verts.map do |vert|
    Math.atan2(vert[1] - pos[1], vert[0] - pos[0]).to_degrees
  end
  # Also march to the left and right of each vertex
  thetas   = thetas.flat_map do |theta|
    [
        (theta - 0.5 + 720) % 360,
        (theta + 720) % 360,
        (theta + 0.5 + 720) % 360
    ]
  end
  # March every 5 degrees, just to be safe
  thetas   = thetas + (1..72).to_a.map { |n| (n * 5+720)%360 }
  # Do the marching
  points   = thetas.sort.map do |theta|
    x, y, _, _ = march(pos, max_iter, theta, sde)
    [x.round, y.round]
  end
  # If a point is co-linear with the point on the right and the point on the left, ignore it.
  points   = points.find_all.with_index do |p, i|
    left      = points[i - 1]
    right     = points[(i + 1) % points.length]
    phi_left  = Math.atan2(left[1] - p[1], left[0] - p[0])
    phi_right = Math.atan2(p[1] - right[1], p[0] - right[0])
    (phi_left - phi_right).abs > 0.11
  end
  # Turn each point into a line
  points.flat_map.with_index do |point, idx|
    l1           = Line.new
    l1.x         = point[0]
    l1.y         = point[1]
    l1.x2        = points[idx - 1][0]
    l1.y2        = points[idx - 1][1]
    l2           = Line.new
    l2.x, l2.y   = *pos
    l2.x2, l2.y2 = point[0], point[1]
    l2.a         = 20
    [
        l1,
    # Uncomment next line to view the rays
    # l2
    ]
  end
end


#
# Originally, I wanted to dynamically increase the number of rays cast based on the change in slope of the outline,
#  the number of steps in the last march, etc.
# This was pretty slow, and very difficult to get right.
# I'm leaving the code here in case someone is curious.
#
# @param [Array<Numeric>] pos Initial position
# @param [Proc] sde The standard distance estimator for the world.
# @param [Numeric] max_step Max d theta
# @param [Numeric] min_step Min d theta
def make_outline(pos, sde, max_step, min_step)
  max_iter                             = 10
  max_d_theta                          = 5
  phi_tol                              = 0.01
  points                               = [{theta: 0}]
  points[-1][:x], points[-1][:y], r, s = *march(pos, max_iter, points[-1][:theta], sde)
  points[1]                            = {theta: (min_step / r).lesser(max_d_theta)}
  points[-1][:x], points[-1][:y], r, s = *march(pos, max_iter, points[-1][:theta], sde)
  points[-1][:phi]                     = Math.atan2(points[-2][:y] - points[-1][:y], points[-2][:x] - points[-1][:x])
  next_theta                           = points[-1][:theta] + (min_step / r).lesser(max_d_theta)
  counter                              = 0
  thetas                               = []
  skip_calc                            = false
  while next_theta < 360
    # thetas = thetas | [next_theta]
    if (counter += 1) > 10000
      puts __LINE__
      puts d_theta(min_step, r, s)
      # puts thetas
      break
    end
    next_x, next_y, r, s = *march(pos, max_iter, next_theta, sde) unless skip_calc
    next_phi             = Math.atan2(points[-1][:y] - next_y, points[-1][:x] - next_x) unless skip_calc
    skip_calc            = false
    if (next_phi - points[-1][:phi]).abs < phi_tol
      next_point = {
          theta: next_theta,
          x:     next_x,
          y:     next_y,
          phi:   next_phi
      }
      # points << next_point
      points[-1]           = next_point
      next_x, next_y, r, s = *march(pos, max_iter, next_theta + d_theta(max_step, r, s).lesser(max_d_theta), sde)
      next_next_phi        = Math.atan2(points[-1][:y] - next_y, points[-1][:x] - next_x)
      if (next_phi - next_next_phi).abs < phi_tol
        next_theta += d_theta(max_step, r, s).lesser(max_d_theta)
        next_phi   = next_next_phi
        skip_calc  = false
      else
        next_theta += d_theta(min_step, r, s).lesser(max_d_theta)
      end
    else
      points << {
          theta: next_theta,
          x:     next_x,
          y:     next_y,
          phi:   next_phi
      }
      next_theta    += d_theta(min_step, r, s).lesser(max_d_theta)
      last_max_step = false
    end
  end

  points.flat_map.with_index do |point, idx|
    l1           = Line.new
    l2           = Line.new
    l1.x         = point[:x]
    l1.y         = point[:y]
    l2.x, l2.y   = *pos
    l2.x2, l2.y2 = point[:x], point[:y]
    l2.a         = 20
    l1.x2        = points[idx - 1][:x]
    l1.y2        = points[idx - 1][:y]
    [
        l1,
    # Uncomment next line to view the rays
    #        l2
    ]
  end
end

class Obstacle
  def initialize
  end

  def renderables
    raise NotImplementedError
  end

  # @param [Numeric] x
  # @param [Numeric] y
  def dist(x, y)
    raise NotImplementedError
  end

  def dist_str
    raise NotImplementedError
  end

  def verts
    raise NotImplementedError
  end
end

class SquareObstacle < Obstacle
  # @param [Numeric] x
  # @param [Numeric] y
  # @param [Numeric] r
  def initialize(x, y, r)
    @sde_x   = x
    @sde_y   = y
    @sde_r   = r
    @solid   = Solid.new
    @solid.x = x - r
    @solid.y = y - r
    @solid.w = 2 * r
    @solid.h = 2 * r
    @verts   = [
        [(x - r).clamp(0, 1280), (y - r).clamp(0, 720)],
        [(x + r).clamp(0, 1280), (y - r).clamp(0, 720)],
        [(x + r).clamp(0, 1280), (y + r).clamp(0, 720)],
        [(x - r).clamp(0, 1280), (y + r).clamp(0, 720)],
    ]
  end

  def renderables
    @solid
  end

  # @param [Numeric] x
  # @param [Numeric] y
  def dist(x, y)
    max((x - @sde_x).abs, (y - @sde_y).abs) - @sde_r
  end

  def dist_str
    "max((x - #{@sde_x}).abs, (y - #{@sde_y}).abs) - #{@sde_r}"
  end

  def dist_x(x)
    (x - @sde_x).abs - @sde_r
  end

  def dist_x_str
    "(x - #{@sde_x}).abs - #{@sde_r}"
  end

  def dist_y(y)
    (y - @sde_y).abs - @sde_r
  end

  def dist_y_str
    "(y - #{@sde_y}).abs - #{@sde_r}"
  end

  def verts
    @verts
  end

  def left
    @sde_x - @sde_r
  end

  def right
    @sde_x + @sde_r
  end

  def bottom
    @sde_y - @sde_r
  end

  def top
    @sde_y + @sde_r
  end
end

class CircleObstacle < Obstacle
  # @param [Numeric] x
  # @param [Numeric] y
  # @param [Numeric] r
  def initialize(x, y, r)
    @sde_x = x
    @sde_y = y
    @sde_r = r
    @verts = (1..10).to_a.map { |n| [Math.sin((36 * n).to_radians) * r + x, Math.cos((36 * n).to_radians) * r + y] }
  end

  def renderables
    @solid
  end

  # @param [Numeric] x
  # @param [Numeric] y
  def dist(x, y)
    Math.sqrt((@sde_x - x) * (@sde_x - x) + (@sde_y - y) * (@sde_y - y)) - @sde_r
  end

  def dist_str
    "Math.sqrt((#{@sde_x} - x) * (#{@sde_x} - x) + (#{@sde_y} - y) * (#{@sde_y} - y)) - #{@sde_r}"
  end

  def verts
    @verts
  end
end

class Line
  attr_accessor :x, :y, :x2, :y2, :r, :g, :b, :a

  def primitive_marker
    :line
  end
end

class Solid
  attr_accessor :x, :y, :w, :h, :r, :g, :b, :a

  def primitive_marker
    :border #This really ought to be :solid, but ¯\_(ツ)_/¯
  end
end