raster.fut

type pixel = { z: f32
             , colour: i32
             }

let closest (a: pixel) (b: pixel): pixel =
  if a.z < b.z
  then a
  else b

let raster_onepass (w: i32) (pixel_pos: []i32) (pixels: []pixel) =
  reduce_by_index (replicate w {z=f32.inf, colour=0})
                  closest {z=f32.inf, colour=0}
                  pixel_pos pixels
  |> map (.colour)

let raster_twopass (w: i32) (pixel_pos: []i32) (pixels: []pixel) =
  let depthmap = reduce_by_index (replicate w f32.inf)
                                 f32.min f32.inf
                                 pixel_pos (map (.z) pixels)
  in scatter (replicate w 0)
             (map2 (\i p -> if p.z == unsafe depthmap[i] then i else -1)
                   pixel_pos pixels)
             (map (.colour) pixels)

-- This one is more imprecise than the others, but not necessarily all that much
-- (depending on the range of z values).
let raster_bitfiddle (max_z: i32) (w: i32) (pixel_pos: []i32) (pixels: []pixel) =
  let z_factor = f32.i32 (i32.highest / max_z)

  let encode (p: pixel): i64 =
    (i64.f32 (p.z * z_factor) << 32) | i64.i32 p.colour

  let decode (code: i64): pixel =
    {z=f32.i64 (code >> 32) / z_factor, colour=i32.i64 code}

  in reduce_by_index (replicate w (encode {z=f32.inf, colour=0}))
                     i64.min (encode {z=f32.inf, colour=0})
                     pixel_pos (map encode pixels)
  |> map (decode >-> (.colour))

-- ==
-- entry: test_raster_onepass test_raster_twopass test_raster_bitfiddle
-- random input { 1000000 [5000]i32 [5000]f32 }
-- random input { 1000000 [50000]i32 [50000]f32 }
-- random input { 1000000 [500000]i32 [500000]f32 }
-- random input { 100000 [5000000]i32 [5000000]f32 }
-- random input { 1000000 [5000000]i32 [5000000]f32 }

entry test_raster_onepass (w: i32) (is: []i32) (zs: []f32) =
  raster_onepass w (map (%w) is) (map2 (\z colour -> {z, colour}) zs is)
entry test_raster_twopass (w: i32) (is: []i32) (zs: []f32) =
  raster_twopass w (map (%w) is) (map2 (\z colour -> {z, colour}) zs is)
entry test_raster_bitfiddle (w: i32) (is: []i32) (zs: []f32) =
  raster_bitfiddle 1000 w (map (%w) is) (map2 (\z colour -> {z, colour}) zs is)

-- $ futhark bench raster.fut --backend=opencl
Compiling raster.fut...
-- Results for raster.fut:test_raster_onepass:
-- dataset 1000000i32 [5000]i32 [5000]f32:           306.40μs (avg. of 10 runs; RSD: 0.11)
-- dataset 1000000i32 [50000]i32 [50000]f32:         620.00μs (avg. of 10 runs; RSD: 0.00)
-- dataset 1000000i32 [500000]i32 [500000]f32:      4055.20μs (avg. of 10 runs; RSD: 0.00)
-- dataset 100000i32 [5000000]i32 [5000000]f32:    13434.30μs (avg. of 10 runs; RSD: 0.01)
-- dataset 1000000i32 [5000000]i32 [5000000]f32:   38403.30μs (avg. of 10 runs; RSD: 0.00)
-- Results for raster.fut:test_raster_twopass:
-- dataset 1000000i32 [5000]i32 [5000]f32:           152.80μs (avg. of 10 runs; RSD: 0.01)
-- dataset 1000000i32 [50000]i32 [50000]f32:         454.50μs (avg. of 10 runs; RSD: 0.02)
-- dataset 1000000i32 [500000]i32 [500000]f32:      3380.40μs (avg. of 10 runs; RSD: 0.00)
-- dataset 100000i32 [5000000]i32 [5000000]f32:     6120.60μs (avg. of 10 runs; RSD: 0.02)
-- dataset 1000000i32 [5000000]i32 [5000000]f32:   27068.20μs (avg. of 10 runs; RSD: 0.00)
-- Results for raster.fut:test_raster_bitfiddle:
-- dataset 1000000i32 [5000]i32 [5000]f32:           318.00μs (avg. of 10 runs; RSD: 0.01)
-- dataset 1000000i32 [50000]i32 [50000]f32:         487.40μs (avg. of 10 runs; RSD: 0.00)
-- dataset 1000000i32 [500000]i32 [500000]f32:      2250.30μs (avg. of 10 runs; RSD: 0.00)
-- dataset 100000i32 [5000000]i32 [5000000]f32:    10519.30μs (avg. of 10 runs; RSD: 0.01)
-- dataset 1000000i32 [5000000]i32 [5000000]f32:   19990.30μs (avg. of 10 runs; RSD: 0.01)