Ray tracing

rt.html

<script>

// TODO
// отражение одно сферы с текстурой в другой зеркальной сфере
// multiple light sources
// multiple reflections
// TODO multimethods
// waves
// зеркала напротив друг друга
// сделать сочетание цветов

// IDEAS
// semi-mirror toroid
// paraboloid, ellipsoid, toroid


// TODO CPP

var vector = {
  add(x,y){
    return [x[0] + y[0], x[1] + y[1], x[2] + y[2]]
  },
  sub(x,y){
    return [x[0] - y[0], x[1] - y[1], x[2] - y[2]]
  },
  mul(x, factor){
    return [x[0] * factor, x[1] * factor, x[2] * factor]
  },
  product(x,y){
    return x[0] * y[0] + x[1] * y[1] + x[2] * y[2]
  },
  squared_length(x){
    return vector.product(x,x)
  },
  squared_distance(x,y){
    return vector.squared_length(vector.sub(x,y))
  },
  length(x){
    return Math.sqrt(vector.squared_length(x))
  },
  normalize(x){
    return vector.mul(x, vector.length(x))
  },
  angle(x,y){
    return Math.acos(vector.product(x,y) / vector.length(x) / vector.length(y)) 
      / Math.PI
  },
  reflect(x, normal){
    return vector.add(
      x,
      vector.mul(
        vector.sub(
          vector.mul(normal, vector.product(x, normal)),
          x
        ),
        2
      )
    )
  },
}

var sceneobject = (() => {
  var objects = {}
  function define(type, spec){
    objects[type] = spec

  }
  function of(obj){
    var spec = objects[obj.type] 
    if(spec == null){
      throw new Error('unknown type: ' + obj.type)
    }
    return spec
  }
  return {define, of}
})()

sceneobject.define('sphere', {
  is_collidable: true,
  collide: function collide_sphere(origin, dir, obj){
    var {sub,add,product,mul,squared_length} = vector
    function sqr(x){
      return x*x
    }
    
    var {center, size} = obj

    var b = product(dir, sub(origin, obj.center)) * 2

    var D = 
      sqr(b)
      -
      4 * squared_length(dir) * (squared_length(sub(origin, obj.center)) 
                                                                   - size*size)
    if(D < 0){
      return null
    }

    var d1 = (-b - Math.sqrt(D)) / 2 / squared_length(dir)
    var d2 = (-b + Math.sqrt(D)) / 2 / squared_length(dir)

    var d

    if(d1 > 0){
      d = d1
    } else if (d1 < 0 && d2 > 0){
      d = d2
    } else {
      return null
    }

    var point = add(origin, mul(dir, d))
    var normal = vector.normalize(vector.sub(point, obj.center))
    return {point, normal}
  },
})

sceneobject.define('plain', {
  is_collidable: true,
  collide: function(origin, dir, plain){
    var PRECISION = 0.001
    var normal = plain.eq
    var prod = vector.product(normal, dir)
    if(Math.abs(prod) < PRECISION){
      return null
    }
    var d = - (normal[3] + vector.product(normal,origin)) / prod
    var point = vector.add(vector.mul(dir, d), origin)
    return {point, normal}
  }
})

sceneobject.define('light', {
  is_collidable: false
})

var MAX_DEPTH = 7

var SCENE = [
  {
    type: 'sphere',
    center: [4,-1,0],
    size: 1,
    color: [0, 255, 0],
    /*
    texture: (obj, x) => {
      var angle = vector.angle(vector.sub(x, obj.center),  [1,0,0])
      return Math.round(angle*100) % 2 == 0 ? [0, 255, 0] : [255, 0, 0]
    },
    */
    diffuse: angle => Math.pow(1 - angle/Math.PI, 2),
  },
  {
    type: 'sphere',
    center: [7,2,0],
    size: 1,
    color: [255, 255, 255],
    diffuse: angle => Math.pow(1 - angle/Math.PI, 2),
  },
  /*
  {
    type: 'wave',
    center: [5, -2, 0],
    normal: [0, 1,  0],
    amplitude: 1,
  },
  */
  {
    type: 'plain',
    diffuse: angle => Math.pow(1 - angle/Math.PI, 2),
    eq: [0,0,1,-1.5],
    color: [0, 0, 255],
    texture: (obj, x) => {
      return (Math.round(x[0]) + Math.round(x[1])) % 2 == 0
        ? [0,0,0]
        : [255,255,255]
    }
  },
  {
    type: 'light',
    center: [-1, 0, 0],
    color: [255,255,255],
  },
]

window.addEventListener('load', main)


var CAMERA = [0,0,0]

var IMAGE_PLANE = {
  center: [1, 0, 0],
  corners: [[1, 1, 1], [1, -1, 1]],
}

var CANVAS_SIZE = [1000, 1000]

function main(){
  var canvas = document.getElementsByTagName('canvas')[0]

  function getCursorPosition(event) {
    const rect = canvas.getBoundingClientRect()
    const x = event.clientX - rect.left
    const y = event.clientY - rect.top
    return [x,y]
  }

  canvas.addEventListener('click', function(e){

    var [x,y] = getCursorPosition(e)
    
    /*
    for(var i = 0; i < canvas.width; i++){
      setPixel(i,i,[255,0,0,255])
    }
    */

    /*
    for(var i = e.x - 10 ; i < e.x + 10; i++){
      for(var j = e.y - 10 ; j < e.y + 10; j++){
        setPixel(i,j,[255,0,0,255])
      }
    }
    */

    var [r,g,b] = getPixel(x,y)
    console.log('r', r,g,b, 'xy', x, y)
    canvas.style.backgroundColor = `rgb(${r},${g},${b})`
    setTimeout(() => canvas.style.backgroundColor = null, 1000)

    var result = trace(null, CAMERA, ray([x,y]), 0, true)
  })

  canvas.setAttribute('width',  CANVAS_SIZE[0])
  canvas.setAttribute('height', CANVAS_SIZE[1])
  var context = canvas.getContext('2d')
  var image = context.createImageData(canvas.width, canvas.height)
  var data = image.data

  var COLOR_LENGTH = 4

  function getPixel(x,y){
    var offset = COLOR_LENGTH * (canvas.width * y + x)
    return [data[offset], data[offset+1], data[offset+2]]
  }

  function setPixel(x,y,color){
    var offset = COLOR_LENGTH * (canvas.width * y + x)
    for(var i = 0; i < COLOR_LENGTH; i++){
      data[offset + i] = color[i]
    }
  }

  //var COLOR = [0, 255, 0, 255]
  //for(var i = 0; i < data.length; i+=COLOR_LENGTH){
  //  for(var j = 0; j < COLOR_LENGTH; j++){
  //    data[i+j] = COLOR[j]
  //  }
  //}

  //for(var i = 0; i < canvas.width; i++){
  //  setPixel(i,i,[255,0,0,255])
  //}

  function ray([i,j]){
    // TODO dont calculate for each ray
    var dirX = vector.sub(IMAGE_PLANE.corners[1], IMAGE_PLANE.corners[0])
    var dirY = 
      vector.sub(
        vector.mul(
          vector.sub(IMAGE_PLANE.center, IMAGE_PLANE.corners[0]),
          2
        ),
        dirX
      )
    return vector.add(
      vector.add(IMAGE_PLANE.corners[0], vector.mul(dirX, i/canvas.width)),
      vector.mul(dirY, j/canvas.height)
    )
  }

  function collide_wave(origin, dir, obj){
    var TEST_LENGTH = 20
    function line(d){
      return vector.add([1,0,0], vector.mul([-0.5,0,-0.5], d))
    }


    /*

    bisect_eq(v => 
      
      obj.normal

      origin,
      vector.add(origin, vector.mul(dir, TEST_LENGTH))
    )
    */
    
    //  (x,y,z) = l0 + d*l
    //  z = Math.sin(x^2 + y^2)
  }


  function collide(origin, dir, obj){
    if(!sceneobject.of(obj).is_collidable){
      return null
    }
    return sceneobject.of(obj).collide(origin, dir, obj)
  }

  function add_lights(lights){
    var result = [0,0,0]
    for(var i = 0; i < lights.length; i++){
      if(lights[i] != null){
        result = vector.add(result, lights[i])
      }
    }
    return result
  }

  function blend(light_color, surface_color){
    var result = []
    for(var i = 0; i < 3; i++){
      result.push(light_color[i] * surface_color[i] / 255)
    }
    return result
  }

  window.debug_i = 0

  function lightness(obj, origin, point, reflection){
    //TODO regarding collision
    // TODO brightness of light
    var result = [0,0,0]
    SCENE.forEach(o => {
      if(o.type == 'light'){
        var light_dir = vector.sub(o.center, point)
        for(var coll of SCENE){
          var collision = collide(point, light_dir, coll)
          if(collision != null){

            var light_distance = vector.squared_distance(point, o.center)
            var collision_distance = vector.squared_distance(point, collision)
            var PRECISION = 0.1
            if(collision_distance > PRECISION && light_distance > collision_distance){
              return
            }

          }
        }
        var angle = vector.angle(reflection, light_dir)
        var brightness = obj.diffuse(angle)
        var obj_color = obj.texture == null
          ? obj.color
          : obj.texture(obj, point)
        var color = blend(o.color, obj_color)
        result = vector.add(result, vector.mul(color, brightness))

        /*
        window.debug_i++
        if(window.debug_i % 100 == 0){
          console.log('a', angle)
        }
        */
      }
    })
    return result
  }

  function trace(origin_object, origin_point, dir, depth = 0, debug = false){
    if(depth > MAX_DEPTH){
      console.log('MAX_DEPTH reached')
      return null
    }
    for(var obj of SCENE){
      if(obj == origin_object){
        continue
      }
      // TODO find only first collision
      var collision = collide(origin_point, dir, obj)
      if(collision != null){
        var {point, normal} = collision
        var reflection = vector.reflect(vector.sub(origin_point,point), normal)
        var l = lightness(obj, origin_point, point, reflection)
        if(debug){
          console.log({origin_point, depth, collision, lightness: l, obj, reflection, dir})
        }
        return add_lights([
          l,
          trace(obj, point, reflection, depth+1, debug),
        ])
      }
    }
    return null
  }
  
  function test_sin_eq(){
    /*
    var res = 1
    for(var i = 0; i < 20; i++){
      res = 2*Math.sin(res)
      console.log(res)
    }
    */

    /*
    y = Math.sin(x)
    y = 0.5x
    */

    function line(d){
      return vector.add([1,0,0], vector.mul([-0.5,0,-0.5], d))
    }
    function wave(d){
      var l = line(d)
      return l[2] - Math.sin(Math.sqrt(l[0]*l[0] + l[1]*l[1]))
    }
    console.log(line(3))
    var res = 0.5
    for(var i = 0; i < 20; i++){
      res = wave(res)
      console.log(res)
    }
    console.log('RES', line(res))
  }

  function bisect_eq(f, start, end, precision = 0.0001){
    var value_start = f(start)
    var value_end = f(end)
    if(Math.sign(value_start) * Math.sign(value_end) != -1){
      throw new Error('bad interval')
    }
    var middle = vector.add(start, vector.mul(vector.sub(end, start), 0.5))
    var value_middle = f(middle)

    if(Math.abs(value_middle) < precision){
      console.log('middle', middle, 'v', value_middle)
      return middle
    } else if(Math.sign(value_start) * Math.sign(value_middle) == -1){
      return bisect_eq(f, start, middle, precision)
    } else {
      return bisect_eq(f, middle, end, precision)
    }
  }

  function test_bisect(){
    function cube(x){
      return x*x*x
    }
    var f = x => cube(x[0] - 1) + cube(x[1] - 2) + cube(x[2] - 3)
    console.log(bisect_eq(f, [-10,-10,-10], [10,10,10]))
  }


  //test_bisect()

  //test_sin_eq()

  function render(){

    window.debug_j = 0

    for(var i = 0; i < canvas.width; i++){
      for(var j = 0; j < canvas.height; j++){
        var color = trace(null, CAMERA, ray([i,j]))
        if(color != null){
          var color_with_alpha = [...color, 255]
          setPixel(i,j,color_with_alpha)

          /*
          if(debug_j % 10 == 0){
            console.log('ii', color)
          }
          debug_j++
          */

        }
      }
    }
  }

  render()


  //console.log(collide(CAMERA, [2,1.1,0], SCENE[0]))
  //console.log(ray([0,0]))
  //console.log(ray([10,500]))



  var p = SCENE.find(o => o.type == 'plain')
  console.log('p', p)
  console.log(
    sceneobject.of(p).collide(
      [0,0,2], 
      [Math.SQRT1_2,Math.SQRT1_2,1],
      p
    )
  )
    

  context.putImageData(image, 0, 0)

  window.canvas = canvas
  window.context = context
  window.image = image
  window.data = data
}




</script>

<body>
  <canvas></canvas>
</body>