2b:null 2c:["$","title",null,{"children":"WebGPU Assignment Renderer Chassis | Introduction to Computer Graphics MSState | Observable"}] 31:T65a,sg = { // Check if empty const empty = mermaid` graph TD G[Global]` const scene_entries = scene.trim().split("\n"); if(scene_entries.length == 1 && scene_entries[0] == "") return empty; const xform_entries = xforms.trim().split("\n"); if(xform_entries[0] == "") xform_entries.shift(); // Parse xform_entries to make building easier const parsed_xform_entries = {}; for(let xform_index = 0; xform_index < xform_entries.length; ++xform_index) { let xform_entry = xform_entries[xform_index].split(" "); let origin = Number.parseInt(xform_entry.shift()); let dest = Number.parseInt(xform_entry.shift()); parsed_xform_entries[origin] = [ dest, xform_entry.filter((t) => Number.isNaN(Number.parseFloat(t))).join("")]; } // Build graph const scene_graph = {nodes: [], edges: []}; for(let el = 0; el < scene_entries.length; ++el) { scene_graph.nodes.push(scene_entries[el].split(" ")[0] + " " + el); if(parsed_xform_entries[el] === undefined) scene_graph.edges.push(["G", el + "[" + scene_graph.nodes[el] + "]", "I"]); else { let xform_entry = parsed_xform_entries[el]; let start = xform_entry[0]; scene_graph.edges.push([start != -1? start : "G", el + "[" + scene_graph.nodes[el] + "]", xform_entry[1]]); } } //return scene_graph.edges.map((edge) => edge[0] + "-->|" + edge[2] + "|" + edge[1]).join("\n"); return mermaid`graph TD G[Global] ${scene_graph.edges.map((edge) => edge[0] + "-->|" + edge[2] + "|" + edge[1]).join("\n")}` }32:T64a,approx_test_src = ` // Based on WGSL standard, the max ULP for most operations is a 2.5 - 3 ULP (though some like atan are much // larger). We'll use 3 as a base; can be changed here to be more or less lax. const max_ulps : i32 = ${max_ulps}; // Function to test if two floats are almost equal. // Based on https://github.com/randomascii/blogstuff/blob/main/FloatingPoint/CompareAsInt/CompareAsInt.cpp fn approx_equal(lhs : f32, rhs : f32) -> bool { // Cast each float to their binary IEEE 754 representation var lhs_2scomp = bitcast(lhs); if(lhs_2scomp < 0) { lhs_2scomp = i32(0x80000000 - u32(lhs_2scomp)); } var rhs_2scomp = bitcast(rhs); if(rhs_2scomp < 0) { rhs_2scomp = i32(0x80000000 - u32(rhs_2scomp)); } // Subtracting the two give the correct # of ULPs between them return abs(lhs_2scomp - rhs_2scomp) <= max_ulps; } // Test if two floats are not equal fn approx_not_equal(lhs : f32, rhs : f32) -> bool { return !approx_equal(lhs, rhs); } // Test if a float is probably less than another fn approx_less_than(lhs : f32, rhs : f32) -> bool { return lhs < rhs && !approx_equal(lhs, rhs); } // Test if a float is probably greater than another fn approx_greater_than(lhs : f32, rhs : f32) -> bool { return lhs > rhs && !approx_equal(lhs, rhs); } // Test if a float is probably less than or equal to another fn approx_less_equal(lhs : f32, rhs : f32) -> bool { return lhs < rhs || approx_equal(lhs, rhs); } // Test if a float is probably greater than or equal to another fn approx_greater_equal(lhs : f32, rhs : f32) -> bool { return lhs > rhs || approx_equal(lhs, rhs); } `33:Tf99,randomization_fxns = ` // Private instead of function because I don't want to have to pass it around var rngState : u32; fn seed_rng(pixel: vec2, resolution: vec2, tick: u32, state: ptr) { // Adapted from https://github.com/boksajak/referencePT let seed = dot(pixel, vec2(1u, resolution.x)) ^ jenkinsHash(tick); *state = jenkinsHash(seed); } fn jenkinsHash(input: u32) -> u32 { var x = input; x += x << 10u; x ^= x >> 6u; x += x << 3u; x ^= x >> 11u; x += x << 15u; return x; } fn rand_u(state: ptr) -> u32 { *state = *state * 747796405u + 2891336453u; let word = ((*state >> ((*state >> 28u) + 4u)) ^ *state) * 277803737u; return (word >> 22u) ^ word; } fn rand_f(state: ptr) -> f32 { *state = *state * 747796405u + 2891336453u; let word = ((*state >> ((*state >> 28u) + 4u)) ^ *state) * 277803737u; return f32((word >> 22u) ^ word) * bitcast(0x2f800004u); } const PI = 3.141596; fn sample_cosine_hemisphere(normal: vec3, state: ptr) -> vec3 { let u0 = 2. * rand_f(state) - 1.; let u1 = 2. * rand_f(state) - 1.; if(approx_equal(0., u0) && approx_equal(0., u1)) {return vec3f(0., 0., 1.);} var r : f32; var theta : f32; var vector : vec3f; if(approx_greater_than(abs(u0), abs(u1))) { r = u0; theta = PI / 4 * u1 / u0; } else { r = u1; theta = PI / 2 - PI / 4 * u0 / u1; } vector.x = r * cos(theta); vector.y = r * sin(theta); vector.z = sqrt(max(0, 1 - vector.x * vector.x - vector.y * vector.y)); // Generate the matrix to rotate this to the hemisphere defined by the normal // See https://math.stackexchange.com/q/61550 let s = 2 * step(0., normal.z) - 1; let mat1 = mat3x3f(s * normal.z, 0., -normal.x, 0., s * normal.z, -normal.y, normal.x, normal.y, s * normal.z); let mat2 = mat3x3f(normal.y * normal.y, -normal.x * normal.y, 0., -normal.x * normal.y, normal.x * normal.x, 0., 0., 0., 0.); let rotation = mat1 + 1. / (1. + s * normal.z) * mat2; return s * rotation * vector; } fn random_diffuse_dir(normal : vec3f) -> vec3f { // Random hemisphere sampling, after pbrt return normalize(sample_cosine_hemisphere(normal, &rngState)); } fn random_glossy_dir(normal: vec3f, shininess : f32) -> vec3f { let state = &rngState; let u0 = rand_f(state); let u1 = rand_f(state); let theta = acos(pow(u0, 1./ (shininess + 2.0))); let phi = 2 * PI * u1; var vector : vec3f; vector.x = cos(phi) * sin(theta); vector.y = sin(phi) * sin(theta); vector.z = cos(theta); // Generate the matrix to rotate this to the hemisphere defined by the normal // See https://math.stackexchange.com/q/61550 let s = 2 * step(0., normal.z) - 1; let mat1 = mat3x3f(s * normal.z, 0., -normal.x, 0., s * normal.z, -normal.y, normal.x, normal.y, s * normal.z); let mat2 = mat3x3f(normal.y * normal.y, -normal.x * normal.y, 0., -normal.x * normal.y, normal.x * normal.x, 0., 0., 0., 0.); let rotation = mat1 + 1. / (1. + s * normal.z) * mat2; return s * rotation * vector; } fn random_rough_dir(normal: vec3f, roughness : f32) -> vec3f { let state = &rngState; let u0 = rand_f(state); let u1 = rand_f(state); let alpha = roughness * roughness; let theta = atan(sqrt(-alpha*alpha*log(1.-u0/PI))); let phi = 2 * PI * u1; var vector : vec3f; vector.x = cos(phi) * sin(theta); vector.y = sin(phi) * sin(theta); vector.z = cos(theta); // Generate the matrix to rotate this to the hemisphere defined by the normal // See https://math.stackexchange.com/q/61550 let s = 2 * step(0., normal.z) - 1; let mat1 = mat3x3f(s * normal.z, 0., -normal.x, 0., s * normal.z, -normal.y, normal.x, normal.y, s * normal.z); let mat2 = mat3x3f(normal.y * normal.y, -normal.x * normal.y, 0., -normal.x * normal.y, normal.x * normal.x, 0., 0., 0., 0.); let rotation = mat1 + 1. / (1. + s * normal.z) * mat2; return s * rotation * vector; } `34:Tc90,## The Shader Source The shader source is built from different sections in the **Code to Modify** section in the student's code. There are several `struct` types, global variables, and constants that can be used in the shader: - `var camera : camera_struct`: The camera elements. These include: - `camera.origin`` : vec3f`: The camera's origin (focal point) in global coordinates - `camera``.up`` : vec3f`: The camera's vertical orientation in global coordinates - `camera``.gaze`` : vec3f`: The direction that camera is facing in global coordinates - `camera.basis`` : Basis`: The three vectors describing the right, up, and forward directions in global coordinates - `camera.f`` : f32`: The focal length in global units - `var viewport : viewport_struct`: The viewport elements. These include: - `viewport.origin``: vec3f`: The viewport's origin in global coordinates - `viewport.width``: f32`: The width of the viewport in global units - `viewport.height``: f32`: The height of the viewport in global units viewport in global coordinates - ${spancolor(image_color, html`var<private> image : image_struct`)}: The ${spancolor(image_color, "image")} elements. These include: - ${spancolor(image_color, html`

image.width: u32`)}: The ${spancolor(image_color, "width of the canvas")} in pixels
  - ${spancolor(image_color, html`image.height: u32`)}: The ${spancolor(image_color, "height of the canvas")} in pixels
  - ${spancolor(image_color, html`image.pixel : vec2u`)}: The ${spancolor(image_color, "pixel indices")} for this shader thread
  - ${spancolor(image_color, html`image.pixel_width : f32`)}: The ${spancolor(image_color, "width of a pixel")} on the viewport in global coordinates
  - ${spancolor(image_color, html`image.pixel_height : f32`)}: The ${spancolor(image_color, "height of a pixel")} on the viewport in global coordinates

Most of these values are copied from notebook values and update when they do; others are initialized by you in the shader thread.35:T4496,shader_src = ` 
// This is the canvas texture we write to
@group(0) @binding(0) var tex: texture_storage_2d<${presentationFormat}, write>;

// Scene Information
// The struct for the scene array. scene_entry.object_type is the type of object
// (1: sphere, 2: plane, 3: box, 4: triangle) and the next nine entries
// define the object (a sphere uses 4 of them [center point for 3, radius for 1],
// a plane uses 6 [plane point and normal], etc.). 
// Usage of this is handled automatically 
struct scene_entry
{
  object_type : u32,
  entry_1 : f32,
  entry_2 : f32,
  entry_3 : f32,
  entry_4 : f32,
  entry_5 : f32,
  entry_6 : f32,
  entry_7 : f32,
  entry_8 : f32,
  entry_9 : f32
};

// Transform Information
// The struct for the xform array. We indicate the relevant object, its parent, if it is animated,
// And the computed parent to local transforms.
// Uploaded automatically.
struct xform_entry
{
  object: i32,
  parent : i32,
  animated : u32,
  transform : mat4x4f
};

// These are the unforms that holds the scene & transform arrays
@group(0) @binding(1) var scene_array : array;
@group(0) @binding(2) var xform_array : array;



// Helper functions
${approx_test_src}
${schlick}
${randomization_fxns}

// The tick: Frames since the last call to render
@group(0) @binding(3) var tick : u32;

// The delta_t: Milliseconds since the last call to render
@group(0) @binding(8) var delta_t : u32;

// Mesh Information
// Vertex data (stored so we don't need padding [lazy])
struct vertex_data
{
  vx : f32,
  vy : f32,
  vz : f32,  
  nx : f32,
  ny : f32,
  nz : f32,
  u  : f32,
  v : f32
};

// Indices for triangles
struct index_data
{
  t0 : u32,
  t1 : u32,
  t2 : u32
};

// These are the unforms that the mesh
@group(0) @binding(4) var vertex_buffer : array;
@group(0) @binding(5) var index_buffer : array;

// Material Information
// Base materials
struct material
{
  albedo : vec3f,
  roughness : f32,
  metallic: f32,
  ior : f32,
  emissive : bool
};

// Material entries for easy of transfer (no padding)
struct material_entry
{
  albedo_r : f32,
  albedo_g : f32,
  albedo_b : f32,
  roughness : f32,
  metallic: f32,
  ior : f32,
  emissive : u32
};
@group(0) @binding(6) var material_buffer : array;

// Light Information
// Stored in the light buffer (padded in upload)
struct point_light
{
  origin : vec3f,
  color : vec3f
};

struct directional_light
{
  direction : vec3f,
  color : vec3f
};

struct area_light
{
  p0 : vec3f,
  p1 : vec3f,
  p2 : vec3f,
  p3 : vec3f,
  color : vec3f
};

struct light_entry
{
  light_type : u32,
  vec0_x : f32,
  vec0_y : f32,
  vec0_z : f32,
  vec1_x : f32,
  vec1_y : f32,
  vec1_z : f32,
  vec2_x : f32,
  vec2_y : f32,
  vec2_z : f32,
  vec3_x : f32,
  vec3_y : f32,
  vec3_z : f32,
  vec4_x : f32,
  vec4_y : f32,
  vec4_z : f32
};
@group(0) @binding(7) var light_buffer : array;

struct kd_tree_node {
    axis      : u32,
    split     : f32,
    pad0      : vec2,   // padding to make next vec3 aligned to 16 bytes

    bbox_min  : vec3,
    pad1      : f32,         // padding to 16 bytes

    bbox_max  : vec3,
    pad2      : f32,         // padding to 16 bytes

    left      : u32,
    right     : u32,
    tri_start : u32,
    tri_count : u32
};

// add KD tree nodes
@group(1) @binding(0) var kd_nodes : array;

// add KD tree triangle indicies
@group(1) @binding(1) var kd_tri_indices : array;

// The image data; updated automatically by Observable except for the 
// pixel width/height, which is done by the student in the shader.
struct image_struct
{
  width : u32,        // Image width
  height : u32,       // Image height
  pixel : vec2u,      // The pixel (i,j) for this thread
  pixel_width : f32,  // Width of a pxiel in global units
  pixel_height : f32, // Height of a pixel in global units
};
var image = image_struct(${ewidth}, ${height}, vec2u(0,0), 0, 0);

// Viewport information; updated by Observable or on thread start
struct viewport_struct
{
  origin : vec3f,           // The viewport's origin in global coordinates
  width: f32,               // The width of the viewport in global units
  height : f32,             // The height of the viewport in global units
};
// These are set by Observable except for the origin
// which are set in the shader by the student.
var viewport = viewport_struct(vec3f(), 
                                ${viewport.width}, 
                                ${viewport.height});

// Basis: Three vectors forming a vector space basis. Vectors should be normalized
// and orthogonal to each other
struct basis_struct
{
  xhat : vec3f,
  yhat : vec3f,
  zhat : vec3f
};

// Camera Information; updated by Observable or on thread start
struct camera_struct
{
  origin : vec3f,           // The camera's origin (focal point) in global coordinates
  up : vec3f,               // The camera's vertical orientation in global coordinates
  gaze : vec3f,             // The direction that camera is facing in global coordinates
  basis : basis_struct,     // The camera's basis vectors
  f : f32                   // The focal length in global units
};
// Tthese are set by the notebook except for the basis which is set in the shader 
// by the student.
var camera = camera_struct(vec3f(${camera_origin.x}, ${camera_origin.y}, ${camera_origin.z}), 
                                    vec3f(${up.x}, ${up.y}, ${up.z}), 
                                    vec3f(${gaze.x}, ${gaze.y}, ${gaze.z}), 
                                    basis_struct(vec3f(1,0,0), vec3f(0,1,0), vec3f(0,0,1)), 
                                    ${focal_length});

// Light testing
// Determine if a light is visible and, if so, return its color
fn light_radiance(light_id : u32, query_pt : vec3f, normal : vec3f) -> vec3f
{
  // break into one of each light type
  var light = light_buffer[light_id];
  switch light.light_type
  {
    default: {}
    case 0: {return apply_point_light(query_pt, 
                                      point_light(
                                        vec3f(light.vec0_x, light.vec0_y, light.vec0_z),
                                        vec3f(light.vec1_x, light.vec1_y, light.vec1_z)));}
    case 1: {return apply_directional_light(query_pt, 
                                            directional_light(                                                                                              normalize(vec3f(light.vec0_x, light.vec0_y, light.vec0_z)),
                                             vec3f(light.vec1_x, light.vec1_y, light.vec1_z)));}

    case 2: {return apply_area_light(query_pt, 
                                     area_light(
                                        vec3f(light.vec0_x, light.vec0_y, light.vec0_z),
                                        vec3f(light.vec1_x, light.vec1_y, light.vec1_z),
                                        vec3f(light.vec2_x, light.vec2_y, light.vec2_z),
                                        vec3f(light.vec3_x, light.vec3_y, light.vec3_z),
                                        vec3f(light.vec4_x, light.vec4_y, light.vec4_z),
                                     ));} 
  }

  // Unknown light
  return vec3f(0,0,0);
}

fn get_light_dir(light_id : u32, query_pt : vec3f) -> vec3f
{
  // break into one of each light type
  var light = light_buffer[light_id];
  switch light.light_type
  {
    default: {}
    case 0: {return normalize(vec3f(light.vec0_x, light.vec0_y, light.vec0_z) - query_pt);}
    case 1: {return normalize(vec3f(light.vec0_x, light.vec0_y, light.vec0_z));}
    case 2: {return normalize(0.25*(vec3f(light.vec0_x, light.vec0_y, light.vec0_z)
                                       + vec3f(light.vec1_x, light.vec1_y, light.vec1_z)
                                       + vec3f(light.vec2_x, light.vec2_y, light.vec2_z)
                                       + vec3f(light.vec3_x, light.vec3_y, light.vec3_z)) - query_pt);} 
  }

  // Unknown light
  return vec3f(0,0,0);
}

${pt_light_src}
${dir_light_src}
${area_light_src}

// Populate the hit struct
fn populate_hit(object_id : u32) -> hit_info_struct
{
  // Dummy
  var hit_info = hit_info_struct(false, 0, object_id, vec3f(), material(vec3f(),0,0,0,false)); 

  // Fill in material info (normal will be added)
  if(arrayLength(&material_buffer) > 0)
  {
    let mat_entry = material_buffer[hit_info.object_id];
    hit_info.material = material(vec3f(mat_entry.albedo_r, mat_entry.albedo_g, mat_entry.albedo_b),
                                 mat_entry.roughness,
                                 mat_entry.metallic,
                                 mat_entry.ior,
                                 mat_entry.emissive != 0);
  }

  return hit_info;
}

// Object interesection
// Sphere
struct sphere_struct
{
  center : vec3f,
  radius : f32,
  object_id : u32
};

${sphere_src}

// Ellipse
struct ellipse_struct
{
  center : vec3f,
  radii : vec3f,
  object_id : u32
};

${ellipse_src}

// Plane
struct plane_struct
{
  point : vec3f,
  normal : vec3f,
  object_id : u32
};

${plane_src}

// Axis-aligned Box (AAB)
struct box_struct
{
  origin : vec3f,
  dimensions : vec3f,
  object_id : u32
};

${box_src}

// Triangle
struct triangle_struct
{
  p0 : vec3f,
  p1 : vec3f,
  p2 : vec3f,
  object_id : u32
};

${triangle_src}

// Ray generation
struct ray_struct
{
  origin : vec3f,
  direction : vec3f
};

${generate_ray_src}

// Ray propagation
// Struct for hit information from trace
struct hit_info_struct
{
  valid : bool,
  distance : f32,
  object_id : u32,
  normal : vec3f,
  material : material
};

// Note that wgsl matrices, like most graphics matrices for historical reasons,
// are stored column-major, not the C-like row major.
const aces_input_matrix = mat3x3(
    0.59719, 0.07600, 0.02840,
    0.35458, 0.90834, 0.13383,
    0.04823, 0.01566, 0.83777,
);

const aces_output_matrix = mat3x3(
    1.60475, -0.10208, -0.00327,
    -0.53108,  1.10813, -0.07276,
    -0.07367, -0.00605,  1.07602,
);

fn tone_aces(in_c : vec3f) -> vec3f
{
    let v = aces_input_matrix * in_c;
    let a = v * (v + 0.0245786) - 0.000090537;
    let b = v * (0.983729 * v + 0.4329510) + 0.238081;
    return clamp(aces_output_matrix * (a / b), vec3(0.0), vec3(1.0));
}

fn to_srgb(in_c : vec3f) -> vec3f
{
  let cutoff = in_c < vec3f(0.0031308);
  let higher = vec3f(1.055)*pow(in_c, vec3f(1/2.4)) - vec3f(0.055);
  let lower = in_c * vec3f(12.95);
  return mix(higher, lower, vec3f(cutoff));
}

// Fast AABB ray intersection
fn ray_box_intersect(ray : ray_struct, bmin : vec3f, bmax : vec3f) -> bool {
  let inv = 1.0 / ray.direction;

  let t0 = (bmin - ray.origin) * inv;
  let t1 = (bmax - ray.origin) * inv;

  let tmin = max(max(min(t0.x,t1.x), min(t0.y,t1.y)), min(t0.z,t1.z));
  let tmax = min(min(max(t0.x,t1.x), max(t0.y,t1.y)), max(t0.z,t1.z));

  return tmax >= max(tmin, 0.0);
}

fn traverse_kd_tree(ray : ray_struct, obj_id: u32) -> hit_info_struct {
  var stack : array;
  var sp : u32 = 0u;
  stack[sp] = 0u; 
  sp++;

  while (sp > 0u) {
    sp -= 1u;
    let idx = stack[sp];
    let node = kd_nodes[idx];

    if (!ray_box_intersect(ray, node.bbox_min, node.bbox_max)) {
      continue;
    }


    if (node.axis == 3u) {

        for(var i: u32 = node.tri_start; i < node.tri_start + node.tri_count; i++){
          let tri = kd_tri_indices[i];
          var tri_hit_info = populate_hit(0);
          tri_hit_info = intersect_triangle(ray,
                                      triangle_struct(vec3f(vertex_buffer[tri.t0].vx, 
                                                             vertex_buffer[tri.t0].vy, 
                                                             vertex_buffer[tri.t0].vz),
                                                       vec3f(vertex_buffer[tri.t1].vx, 
                                                             vertex_buffer[tri.t1].vy, 
                                                             vertex_buffer[tri.t1].vz),
                                                       vec3f(vertex_buffer[tri.t2].vx, 
                                                             vertex_buffer[tri.t2].vy, 
                                                             vertex_buffer[tri.t2].vz),
                                                        obj_id)); 
    
          if(tri_hit_info.valid && approx_greater_equal(tri_hit_info.distance, 0)){
             return tri_hit_info;
          }      
        }
    }
    

    if(node.left != 0u){
      stack[sp] = node.left; sp++;
    }
    if(node.right != 0u){
      stack[sp] = node.right; sp++;
    }
  }

  return populate_hit(0);
}


fn trace(ray : ray_struct) -> hit_info_struct
{
  // Start by hitting nothing
  var hit_info = populate_hit(0); 

  // Walk through all objects, looking for a shape
  let num_objects : u32 = arrayLength(&scene_array);
  let num_mats = arrayLength(&material_buffer);
  for(var i : u32 = 0 ; i < num_objects; i++)
  {
    var entry : scene_entry = scene_array[i];
    var entry_hit_info = populate_hit(0);

    switch entry.object_type
    {
      default: {}
      case 1: {entry_hit_info = intersect_sphere(ray,
                                                 sphere_struct(vec3f(entry.entry_1,  
                                                                     entry.entry_2,
                                                                     entry.entry_3),
                                                               entry.entry_4,
                                                                i));}
      case 2: {entry_hit_info = intersect_plane(ray,
                                                plane_struct(vec3f(entry.entry_1, 
                                                                   entry.entry_2, 
                                                                   entry.entry_3),
                                                             vec3f(entry.entry_4, 
                                                                   entry.entry_5, 
                                                                   entry.entry_6),
                                                             i));}
      case 3: {entry_hit_info = intersect_box(ray,
                                              box_struct(vec3f(entry.entry_1, entry.entry_2, entry.entry_3),
                                                         vec3f(entry.entry_4, entry.entry_5, entry.entry_6),
                                                         i));}
      case 4: {entry_hit_info = intersect_triangle(ray,
                                                   triangle_struct(vec3f(entry.entry_1, 
                                                                         entry.entry_2, 
                                                                         entry.entry_3),
                                                                   vec3f(entry.entry_4, 
                                                                         entry.entry_5, 
                                                                         entry.entry_6),
                                                                   vec3f(entry.entry_7, 
                                                                         entry.entry_8, 
                                                                         entry.entry_9),
                                                                    i));}
      case 5: { entry_hit_info = traverse_kd_tree(ray, i); }
      case 6: {entry_hit_info = intersect_ellipse(ray,
                                                 ellipse_struct(vec3f(entry.entry_1,  
                                                                      entry.entry_2,
                                                                      entry.entry_3),
                                                                vec3f(entry.entry_4,  
                                                                      entry.entry_5,
                                                                      entry.entry_6),
                                                                i));}

    }
    if(entry_hit_info.valid && approx_greater_equal(entry_hit_info.distance, 0) 
        && (!hit_info.valid || approx_less_than(entry_hit_info.distance, hit_info.distance)))
    {
      hit_info = entry_hit_info;
    }
  }

  return hit_info;
}

${global_src}

// Color generation

// Compute shader; works on 8 x 8 tiles of the image
@compute @workgroup_size(8, 8)
fn set_pixels(@builtin(global_invocation_id) globalId : vec3u) 
{
  // Check to see if we are past the size (GPU might create more pixels that 
  // can be set for its efficiency). i,j are the index into our picture (the
  // pixel coords)
  let i = globalId.x;
  let j = globalId.y;
  if(i >= image.width || j >= image.height) { return; }
  image.pixel = vec2u(i, j);

  seed_rng(vec2u(i, j), vec2u(image.width, image.height), tick, &rngState);

  ${cam_view_update_src}

  // Generate the initial ray
  let ray = generate_ray(i, j);
  let hit_info = trace(ray);
  let num_objects : u32 = arrayLength(&scene_array);

  // Generate the color
  var color = vec3f(1,1,1);
  let num_lights : u32 = arrayLength(&light_buffer);
  ${set_color_src}

  // Tone map and conver to sRGB and then write

  // Write the color to the texture
  textureStore(tex, globalId.xy, vec4f(to_srgb(color), 1));
}
`36:T4eb, bindGroupLayout = device?.createBindGroupLayout({
   label : "Assignment Bind Group",
    entries: [
      {
        binding: 0,
        visibility: GPUShaderStage.COMPUTE,
        storageTexture: {format: presentationFormat, access: "write-only"},
      },
      {
        binding: 1,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"read-only-storage"},
      },
      {
        binding: 2,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"read-only-storage"},
      },
      {
        binding: 3,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"uniform"},
      },
      {
        binding: 4,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"read-only-storage"},
      },
      {
        binding: 5,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"read-only-storage"},
      },
      {
        binding: 6,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"read-only-storage"},
      },
      {
        binding: 7,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"read-only-storage"},
      },
      {
        binding: 8,
        visibility:  GPUShaderStage.COMPUTE,
        buffer: {type:"uniform"},
      },
    ],
  });37:Tc40,function buildKDTree(vertices, indices, maxTrianglesPerLeaf = 1) {
    var nodes = [];

    // Helper: compute bounding box of triangles between start and end indices
    function computeBBox(triStart, triCount) {
        var min = [Infinity, Infinity, Infinity];
        var max = [-Infinity, -Infinity, -Infinity];

        for (var t = 0; t < triCount; t++) {
            var offset = (triStart + t) * 3;
            for (var i = 0; i < 3; i++) {
                var idx = indices[offset + i];
                min[0] = Math.min(min[0], vertices[idx * 3 + 0]);
                min[1] = Math.min(min[1], vertices[idx * 3 + 1]);
                min[2] = Math.min(min[2], vertices[idx * 3 + 2]);
                max[0] = Math.max(max[0], vertices[idx * 3 + 0]);
                max[1] = Math.max(max[1], vertices[idx * 3 + 1]);
                max[2] = Math.max(max[2], vertices[idx * 3 + 2]);
            }
        }

        return { min, max };
    }

    // Helper: compute centroid of a triangle
    function centroid(triOffset) {
        var c = [0, 0, 0];
        for (var i = 0; i < 3; i++) {
            var idx = indices[triOffset * 3 + i];
            c[0] += vertices[idx * 3 + 0];
            c[1] += vertices[idx * 3 + 1];
            c[2] += vertices[idx * 3 + 2];
        }
        return [c[0]/3, c[1]/3, c[2]/3];
    }

    function buildNode(triStart, triCount) {
        var bbox = computeBBox(triStart, triCount);

        if (triCount <= maxTrianglesPerLeaf) {
            var node = {
                axis: 3,  // leaf
                split: 0,
                bbox_min: bbox.min,
                bbox_max: bbox.max,
                left: 0,
                right: 0,
                tri_start: triStart,
                tri_count: triCount
            };
            nodes.push(node);
            return nodes.length - 1;
        }

        var extents = [
            bbox.max[0] - bbox.min[0],
            bbox.max[1] - bbox.min[1],
            bbox.max[2] - bbox.min[2]
        ];
        var axis = extents.indexOf(Math.max(...extents));

        var triIndices = [];
        for (var t = 0; t < triCount; t++) triIndices.push(triStart + t);

        triIndices.sort((a, b) => centroid(a)[axis] - centroid(b)[axis]);

        var temp = indices.slice(triStart*3, (triStart + triCount)*3);
        for (var t = 0; t < triCount; t++) {
            for (var i = 0; i < 3; i++) {
                indices[(triStart + t)*3 + i] = temp[(triIndices[t]-triStart)*3 + i];
            }
        }

        var mid = Math.floor(triCount / 2);

        var node = {
            axis: axis,
            split: (centroid(triIndices[mid-1])[axis] + centroid(triIndices[mid])[axis]) / 2,
            bbox_min: bbox.min,
            bbox_max: bbox.max,
            left: 0,
            right: 0
        };

        nodes.push(node);
        var nodeIndex = nodes.length - 1;

        nodes[nodeIndex].left = buildNode(triStart, mid);
        nodes[nodeIndex].right = buildNode(triStart + mid, triCount - mid);

        return nodeIndex;
    }

    buildNode(0, indices.length / 3);

    return { nodes, triIndices: indices };
}38:T45b,// utility function to convert array of nodes to GPU buffer
function createKDNodesBuffer() {
  const numNodes = kdTreeData.nodes.length;
  const floatsPerNode = 16;         // 64 bytes per node
  const bufferSize = floatsPerNode * 4 * numNodes;

  const data = new ArrayBuffer(bufferSize);
  const f32 = new Float32Array(data);
  const u32 = new Uint32Array(data);

  for (let i = 0; i < numNodes; i++) {
    const n = kdTreeData.nodes[i];
    const o = i * 16;   // float offset

    u32[o + 0] = n.axis;
    f32[o + 1] = n.split;

    // o+2, o+3 are padding

    f32[o + 4] = n.bbox_min[0];
    f32[o + 5] = n.bbox_min[1];
    f32[o + 6] = n.bbox_min[2];
    // o+7 padding

    f32[o + 8]  = n.bbox_max[0];
    f32[o + 9]  = n.bbox_max[1];
    f32[o + 10] = n.bbox_max[2];
    // o+11 padding

    u32[o + 12] = n.left;
    u32[o + 13] = n.right;
    u32[o + 14] = n.tri_start;
    u32[o + 15] = n.tri_count;
  }

  const buffer = device.createBuffer({
    size: data.byteLength,
    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,
  });

  device.queue.writeBuffer(buffer, 0, data);
  return buffer;
}39:Tda6,function updateTransformBuffer()
{
  if(!device) return undefined;

  // Check if empty
  var entries = scene.trim().split("\n");
  if(entries.length == 1 && entries[0] == "")
    return undefined;
  var xform_entries = xforms.trim().split("\n");
  if(xform_entries.length == 1 && xform_entries[0] == "")
    xform_entries.shift();
  
  // Populate CPU data. Need separate array views as the struct has three data types
  // We need a transfrom for each scene entry (even if one wasn't assigned; Identity by default)
  const xform_data = new ArrayBuffer(xform_row_size * entries.length);
  const int_view = new Int32Array(xform_data);
  const uint_view = new Uint32Array(xform_data);
  const float_view = new Float32Array(xform_data);
  for(let i = 0; i < entries.length; i++)
  {
    // Default if no transform entry
    var row_values = [i, -1, "I"];
    for(let j = 0; j < xform_entries.length; ++j)
    {
      var read_row_values = xform_entries[j].trim().split(" ");
      if(i == parseInt(read_row_values[0]))
      {
        row_values = read_row_values;
        break;
      }
    }
    
    var animated = row_values[2] == "*";
    // TODO stuff
    int_view[xform_row_size  / 4 * i] = parseInt(row_values[0]);
    int_view[xform_row_size  / 4 * i + 1] = parseInt(row_values[1]);
    uint_view[xform_row_size  / 4 * i + 2] = animated;

    // Build the tranforms. First, kill the non-transform entries
    row_values.shift();    row_values.shift();
    if(animated) row_values.shift();

    // Start w/ identity
    const transform = glm.mat4.create();
    glm.mat4.identity(transform);
    for(var x = 0; x < row_values.length; ++x)
    {
      switch(row_values[x])
      {
        case "I":
          // Identity. Nothing to do
          break;
        case "R":
          glm.mat4.mul(transform, transform, glm.mat4.fromRotation(glm.mat4.create(),
                                                                   row_values[x+4], 
                                                                  [row_values[x+1],
                                                                   row_values[x+2],
                                                                   row_values[x+3]]));
          x += 4;
          break;
        case "T":
          glm.mat4.mul(transform, transform, glm.mat4.fromTranslation(glm.mat4.create(),
                                                                     [row_values[x+1],
                                                                      row_values[x+2],
                                                                      row_values[x+3]]));
          x += 3;
          break;
        case "S":
          glm.mat4.mul(transform, transform, glm.mat4.fromScaling(glm.mat4.create(),
                                                                  [row_values[x+1],
                                                                   row_values[x+1],
                                                                   row_values[x+1]]));
          x += 3;
          break;
      }
      // Consume until next letter
      while(x < row_values.length - 1 && !isAlpha(row_values[x+1])) x += 1;
    }
  
    float_view.set(transform, xform_row_size  / 4 * i + 4);
  }

  // Populate GPU buffer
  const xform_buffer = device.createBuffer({
    size: xform_row_size  * entries.length,
    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,
  });
  device.queue.writeBuffer(xform_buffer, 0, xform_data);
  
  return xform_buffer;
}3a:Tc2d,render = () => {
  if(device === undefined)
    return;

  // Reset everything
  render_status.firstChild.textContent = "Starting Render";
  error_log.style.display = "none";
  error_log.innerHTML = "";
  
  // Update scene & transforms
  const scene_buffer = updateSceneBuffer();
  if(!scene_buffer)
  {
    render_status.firstChild.textContent = "No scene to render. Exiting";
    return;
  }
  const xform_buffer = updateTransformBuffer();  

  // WebGPU is particular that every uniform must be stored in a buffer, even scalar types. 
  // So we upload tick to a buffer here.
  const tick_data = new Uint32Array([tick()]);
  const tick_buffer = device.createBuffer({
    size: 4,
    usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST,
  });
  device.queue.writeBuffer(tick_buffer, 0, tick_data);

  const delta_data = new Uint32Array([delta_t()]);
  const delta_buffer = device.createBuffer({
    size: 4,
    usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST,
  });
  device.queue.writeBuffer(delta_buffer, 0, delta_data);

  // Get the current texture from the canvas context and
  // set it as the texture to render to.
  const canvasTexture = gpu.getCurrentTexture();

  // Bind the texture & other data to the pipeline for writing
   const bindGroup = device.createBindGroup({
      layout: pipeline.getBindGroupLayout(0),
      entries: [
        { binding: 0, resource: canvasTexture.createView() },
        { binding: 1, resource: { buffer: scene_buffer }},
        { binding: 2, resource: { buffer: xform_buffer }},
        { binding: 3, resource: { buffer: tick_buffer }},
        { binding: 4, resource: { buffer: vertex_buffer }},
        { binding: 5, resource: { buffer: index_buffer }},
        { binding: 6, resource: { buffer: material_buffer }},
        { binding: 7, resource: { buffer: light_buffer }},
        { binding: 8, resource: { buffer: delta_buffer }}
      ],
    });  
  
  const kdNodesBuffer = createKDNodesBuffer();
  const kd_tri_data = new Uint32Array(kdTreeData.triIndices);
  const kd_tri_buffer = device.createBuffer({
    size: kd_tri_data.byteLength,
    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,
  });
  device.queue.writeBuffer(kd_tri_buffer, 0, kd_tri_data);

    
  const kdBindGroup = device.createBindGroup({
    layout: kdBindGroupLayout,
    entries: [
        { binding: 0, resource: { buffer: kdNodesBuffer } },
        { binding: 1, resource: { buffer: kd_tri_buffer } },
    ],
  });  
  
  // make a command encoder to start encoding commands
  const encoder = device.createCommandEncoder({ label: 'WebGPU Chasis encoder' });
  
  // make a computer pass encoder to encode the current pipeline and
  // bind the canvas texture to it for writing
  const pass = encoder.beginComputePass();
  pass.setPipeline(pipeline);
  pass.setBindGroup(0, bindGroup);
  pass.setBindGroup(1, kdBindGroup);

  pass.dispatchWorkgroups(canvasTexture.width / 8, canvasTexture.height / 8);
  pass.end();
  
  const commandBuffer = encoder.finish();

  device.queue.submit([commandBuffer]);
  
  render_status.firstChild.textContent = "Render complete"
}3b:[{"id":"a38d1b9ecba4b794aa6b7a76811328ee05b3ceb7d35b15ccea9083167bb27048750fe98e76ee45e2300995d6455cdd7cbfa6da5ef5cc90ca54ea36baa5140c5c","href":"https://static.observableusercontent.com/files/a38d1b9ecba4b794aa6b7a76811328ee05b3ceb7d35b15ccea9083167bb27048750fe98e76ee45e2300995d6455cdd7cbfa6da5ef5cc90ca54ea36baa5140c5c","name":"austin_mini_geom.json","type":"application/json","lastModified":1765058448431.922,"size":1134168}]
2f:{"id":"875b097f749499df","slug":"cmu32-kdtree-rendering","title":"WebGPU Assignment Renderer Chassis","thumbnail":"1d69f023c681d1c5d00efc8990a5cea8d984258a114a93176f8bdc843bc689a2","access_level":"public","create_time":"$D2025-12-06T19:46:04.407Z","update_time":"$D2025-12-07T20:03:48.939Z","view_time":null,"first_public_time":"$D2025-12-07T22:43:14.791Z","fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"7c0dab8b587e2ed2","login":"cse4413msstate","name":"Introduction to Computer Graphics MSState","avatar_url":"https://avatars-next.observableusercontent.com/343b1e48cbb2480c08063f107b4631944c5bb97a5258576dd939a5be852f30bc","tier":"pro_2024"},"version":992,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"5456442ccbbc5348","login":"chase-ueltschey","name":"Chase Ueltschey","avatar_url":"https://avatars-next.observableusercontent.com/90b73e3d72625a10a45a70e8329028b0130e966f862ed65eb98c1478ad4ea7c6","tier":null}],"members":[{"type":"team","id":"7c0dab8b587e2ed2","login":"cse4413msstate","name":"Introduction to Computer Graphics MSState","avatar_url":"https://avatars-next.observableusercontent.com/343b1e48cbb2480c08063f107b4631944c5bb97a5258576dd939a5be852f30bc","tier":"pro_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"WebGPU Assignment Renderer Chassis","cells":[{"id":0,"value":"# WebGPU Assignment Renderer Chassis\n\nThis code is shared between all the Assignments for the renderer. Not all parts are used in all Assignments, but a common basis makes the code change less between Assignments.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":160,"value":"## The Render Window\n\nWhere everything will be rendered.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":162,"value":"viewof gpu = {\n  // Do we support WebGPU?\n  if(!(\"gpu\" in navigator) || adapter === undefined)\n    return html`WebGPU Not Supported. Please use Chrome or other supported browser.`;\n\n  // Create the backing canvas \n  // For now, ignore the device pixel ratio (the ratio of physical to virtual pixels0\n  const canvas = DOM.canvas(ewidth, height);\n  canvas.style.width = `${ewidth}px`;\n  canvas.style.height = `${height}px`;\n  canvas.style.border = \"thin solid black\";\n  canvas.style.transform = \"scaleY(-1)\";  // WebGPU textures have 0, 0 in the \"wrong\" place\n\n  // Load WebGPU into the canvas\n  const context = (canvas.value = canvas.getContext('webgpu'));\n  context.configure({\n    device,\n    format: presentationFormat,\n    // This is what's required to be able to write to a the canvas from a compute shader\n    usage: GPUTextureUsage.RENDER_ATTACHMENT | GPUTextureUsage.STORAGE_BINDING,\n  });\n  \n  return context.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":164,"value":"render_status = md`*Unrendered*`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":184,"value":"## The Scene Graph\n\nTo indicate visually the structure of the scene, its *scene graph* is depicted below and automatically generated when the transform list is updated. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":187,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5,"value":"## Helper Functions\n\nThese shader functions are helper functions; you do not need to change them but might use them.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":7,"value":"### Boolean Testing\n\n[Comparing floating point numbers is hard](https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/) due to many factors; direct comparison of two floats is not recommended. Thus, we have an \"approximately\" equal, not equal, and other functions here. So, instead of:\n\n~~~wgsl\nvar a : f32, b : f32, c : f32;\n// ... set a,b,c somewhere...\n\n// Now test badly!\nif(a == b && a < c) \n{\n  // Do a thing\n}\n~~~\nWe approximate via `approx_*` functions:\n~~~wgsl\nvar a : f32, b : f32;\n// ... set a,b,c somewhere...\n\n// More accurate\nif(approx_equal(a, b) && approx_less(a, c)) \n{\n  // Do a thing\n}\n~~~\nThis approach does not actually properly [propagate errors](https://www.pbr-book.org/3ed-2018/Shapes/Managing_Rounding_Error \"Handling Rounding Error\"); but to do so would require significantly more work. The functions provided are:\n- `approx_equal`\n- `approx_not_equal`\n- `approx_less_than`\n- `approx_greater_than`\n- `approx_less_equal`\n- `approx_greater_equal`","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":9,"value":"The uncertainty we accept in ULPs (units of least precision):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":11,"value":"max_ulps = 3","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":14,"value":"The `approx_*` implementations:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":16,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":309,"value":"### Random Rays\n\nRandom number, vector, and sampled vectors. Via [bevy](https://github.com/JMS55/bevy/blob/solari3/crates/bevy_pbr/src/solari/global_illumination/utils.wgsl) and [ Johann Muszynski](https://github.com/Nelarius/weekend-raytracer-wgpu/blob/232ffca207dcefce00fedf935cc094950b2dee48/src/raytracer/raytracer.wgsl).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":311,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":305,"value":"### Schlick Approximation\n\nIf you wish to use the Schlick Approximation for Fresnel reflectance, here it is.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":307,"value":"schlick = `\nfn schlick(f0 : vec3f, n_dot_v : f32) -> vec3f\n{\n  return f0 + (1 - f0) * pow(1 - n_dot_v, 5);\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":37,"value":"$34","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":39,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":49,"value":"### Dummy Sections\n\nFor this to be valid, we have to include dummy versions of what the students will implement. These are replaced in the individual notebooks.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":85,"value":"#### Dummy Variables\n\nThese variables are set by controls in the web page so need to be set here.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":104,"value":"ewidth = 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":107,"value":"height = 1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":87,"value":"viewof viewport = Inputs.form({width:Inputs.number([-Infinity, Infinity], {\n                                 label: html`Viewport width`,\n                                 value: 2}),\n                               height:Inputs.number([-Infinity, Infinity], {\n                                 label: html`Viewport height`, \n                                 value: 2})})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":90,"value":"viewof camera_origin = Inputs.form({x: Inputs.number([-Infinity, Infinity], {\n                                label: html`Focal point ${tex`x`}`,\n                                value: 0}),\n                               y: Inputs.number([-Infinity, Infinity], {\n                                 label: html`Focal point ${tex`y`}`,\n                                 value: 0}),\n                               z: Inputs.number([-Infinity, Infinity], {\n                                 label: html`Focal point ${tex`z`}`,\n                                 value: 10})})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":95,"value":"viewof focal_length = Inputs.number([0, Infinity], {label: html`Focal length`, value: 10})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":97,"value":"viewof up = Inputs.form({x: Inputs.number([-Infinity, Infinity], {\n                                label: html`View up ${tex`x`}`,\n                                value: 0}),\n                               y: Inputs.number([-Infinity, Infinity], {\n                                 label: html`View up ${tex`y`}`,\n                                 value: 1}),\n                               z: Inputs.number([-Infinity, Infinity], {\n                                 label: html`View up ${tex`z`}`,\n                                 value: 0})})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":101,"value":"viewof gaze = Inputs.form({x: Inputs.number([-Infinity, Infinity], {\n                                label: html`Gaze ${tex`x`}`,\n                                value: 0}),\n                               y: Inputs.number([-Infinity, Infinity], {\n                                 label: html`Gaze ${tex`y`}`,\n                                 value: 0}),\n                               z: Inputs.number([-Infinity, Infinity], {\n                               label: html`Gaze ${tex`z`}`,\n                                 value: -1})})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":153,"value":"viewof scene = Inputs.textarea({label: \"Scene\", rows: 10, placeholder: \"Create scene here.\", submit: false})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":181,"value":"viewof xforms = Inputs.textarea({label: \"Transforms\", rows: 10, placeholder: \"Create transforms here.\", submit: false})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":425,"value":"Also the buffers.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":427,"value":"vertex_buffer = {\n  if(!device) return undefined;\n\n  let vertexdata = new Float32Array([0,0,0, 0,0,0, 0,0]); // Dummy buffer\n\n  // Populate GPU buffers\n  const vertex_buffer = device.createBuffer({\n    size: vertexdata.byteLength,\n    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,\n  });\n  device.queue.writeBuffer(vertex_buffer, 0, vertexdata);\n  \n  return vertex_buffer;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":429,"value":"index_buffer = {\n  if(!device) return undefined;\n\n  let indexdata = new Uint32Array([0, 0, 0]); // Dummy buffer  \n\n  // Populate GPU buffers\n  const index_buffer = device.createBuffer({\n    size: indexdata.byteLength,\n    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,\n  });\n  device.queue.writeBuffer(index_buffer, 0, indexdata);\n  \n  return index_buffer;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":443,"value":"material_buffer = {\n  if(!device) return undefined;\n\n  // Switch on scene_select\n  let materialdata = new ArrayBuffer(4 * 7); // Dummy buffer\n\n  // Populate GPU buffers\n  const material_buffer = device.createBuffer({\n    size: materialdata.byteLength,\n    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,\n  });\n  device.queue.writeBuffer(material_buffer, 0, materialdata);\n  \n  return material_buffer;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":445,"value":"light_buffer = {\n  if(!device) return undefined;\n\n  // Switch on scene_select\n  let lightdata = new ArrayBuffer(4 * 24); // Dummy buffer  \n\n  // Populate GPU buffers\n  const light_buffer = device.createBuffer({\n    size: lightdata.byteLength,\n    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,\n  });\n  device.queue.writeBuffer(light_buffer, 0, lightdata);\n  \n  return light_buffer;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":110,"value":"#### Setup Camera & Viewport","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":112,"value":"cam_view_update_src = `\n  // TODO: Update the following values using image, camera, and viewport:\n  //    - camera.basis (Basis): The three basis vectors for the camera and viewport space\n  //    - viewport.origin (vec3f): The viewport's origin\n  //    - image.pixel_width (f32): The width of an individual pixel\n  //    - image.pixel_height (f32): The height of an individual pixel\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":55,"value":"#### Generate Rays","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":59,"value":"generate_ray_src = `\n// TODO: If you want to calculate any constants to use elsewhere, do so here.\n\n// The function to generate the rays. Returns both the ray origin on the viewport\n// and the ray direction.\n//\n// ray has two elements:\n//   - ray.origin (vec3f): The ray's origin on the viewport (at the pixel center)\n//   - ray.direction (vec3f): The ray's direction. Should be normalized.\nfn generate_ray(i : u32, j : u32) -> ray_struct\n{\n  var ray : ray_struct;\n\n  // TODO: Calculate and set the ray.origin and ray.direction\n  // The default (which you will replace) is a ray from the origin with no\n  // orientation\n\n  return ray;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":61,"value":"#### Sphere Intersection\n\nIntersect the given ${spancolor(ray_color, \"ray\")} with a `sphere` (described by `sphere.center  : vec3f` and `sphere.radius (f32)`). ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":63,"value":"sphere_src = `\nfn intersect_sphere(ray : ray_struct, sphere : sphere_struct) -> hit_info_struct\n{\n  var hit_info = populate_hit(sphere.object_id);\n\n  // TODO: Intersect ray with the sphere. If there is an intersection, update the\n  // hit_info.\n\n  return hit_info;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":510,"value":"#### Ellipse Intersection\n\nIntersect the given ${spancolor(ray_color, \"ray\")} with an `ellipse` (described by `ellipse.center  : vec3f` and `ellipse.radii (vec3f)`). One should use code from `intersect_sphere` after an appropriate transform has been applied (you cannot call `intersect_sphere` directly as it will overwrite the ellipse transform you create here).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":514,"value":"ellipse_src = `\nfn intersect_ellipse(ray : ray_struct, ellipse : ellipse_struct) -> hit_info_struct\n{\n  var hit_info = populate_hit(ellipse.object_id);\n\n  // TODO: Intersect ray with the ellipse. If there is an intersection, update the\n  // hit_info. Use the same code as for a sphere, but transform the ray appropritely first.\n\n  return hit_info;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":66,"value":"#### Plane Intersection\n\nIntersect the given ${spancolor(ray_color, \"ray\")} with a `plane` (described by `plane.point  : vec3f` and `plane.normal (vec3f))`. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":68,"value":"plane_src = `\nfn intersect_plane(ray : ray_struct, plane : plane_struct) -> hit_info_struct\n{\n  var hit_info = populate_hit(plane.object_id);\n\n  // TODO: Intersect ray with the plane. If there is an intersection, update the\n  // hit_info.\n\n  return hit_info;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":70,"value":"#### Box Intersection\n\nIntersect the given ${spancolor(ray_color, \"ray\")} with an axis-aligned `box` (described by `box.origin  : vec3f` and `box.dimensions (vec3f)`). ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":72,"value":"box_src = `\nfn intersect_box(ray : ray_struct, box : box_struct) -> hit_info_struct\n{\n  var hit_info = populate_hit(box.object_id);\n\n  // TODO: Intersect ray with the box. If there is an intersection, update the\n  // hit_info.\n\n  return hit_info;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":74,"value":"#### Triangle Intersection\n\nIntersect the given ${spancolor(ray_color, \"ray\")} with a `triangle` (described by `triangle.p0  : vec3f`, `triangle.p1 (vec3f)`, and  `triangle.p2 (vec3f)`). ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":76,"value":"triangle_src = `\nfn intersect_triangle(ray : ray_struct, triangle : triangle_struct) -> hit_info_struct\n{\n  var hit_info = populate_hit(triangle.object_id);\n\n  // TODO: Intersect ray with the triangle. If there is an intersection, update the\n  // hit_info.\n\n  return hit_info;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":78,"value":"#### Set Color\n\nSet the color for the ${spancolor(image_color, \"pixel\")}. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":80,"value":"set_color_src = `\n  // TODO: Set the color (a vec3f). The shader variables ray & hit_info holds the current\n  // ray's data.\n  // The default color (which you will replace if an object was hit) is white\n  color = vec3f(1,1,1);\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":561,"value":"#### Additional Global Code","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":563,"value":"global_src = ``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":373,"value":"#### Apply Point Light\n\nApply a point light to the given point. It is assume the point is not in shadow. Parameters are the point in question and a `light : point_light`:\n\n- `light.origin : vec3f` The position of the light.\n- `light.color : vec3f`: The RGB exitant radiance of the light.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":382,"value":"pt_light_src = `\nfn apply_point_light(point : vec3f, light : point_light) -> vec3f\n{\n  // TODO: Given the light, apply it to the given point. Return the appropriate incoming radiance to the point.\n  var out_color = vec3f(0,0,0);\n\n  return out_color ;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":376,"value":"#### Apply Directional Light\n\nApply a directional light to the given point. It is assume the point is not in shadow. Parameters are point in question and a `light : directional_light`:\n\n-  `light.direction : vec3f`: The outgoing direction of the light.\n-  `light.color : vec3f`: The RGB exitant radiance of the light.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":385,"value":"dir_light_src = `\nfn apply_directional_light(point : vec3f, light : directional_light) -> vec3f\n{\n  // TODO: Given the light, apply it to the given point. Return the appropriate incoming radiance to the point.\n  var out_color = vec3f(0,0,0);\n\n  return out_color ;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":379,"value":"#### Apply Area Light\n\nApply an area light (a quad) to the given point. It is assume the point is not in shadow. Parameters are the point in question and a `light : area_light`:\n-  `light.p0 : vec3f`: The lower, left point of the light facing it (the light normal is in the other direction).\n-  `light.p1 : vec3f`: The lower, right point of the light facing it.\n-  `light.p2 : vec3f`: The upper, right point of the light facing it.\n-  `light.p3 : vec3f`: The upper, left point of the light facing it.\n-  `light.color : vec3f`: The RGB exitant radiance of the light.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":387,"value":"area_light_src = `\nfn apply_area_light(point : vec3f, light : area_light) -> vec3f\n{\n  // TODO: Given the light, apply it to the given point. Return the appropriate incoming radiance to the point.\n  // Remember, intersect_triangle(ray_struct, triangle_struct) exists.\n\n  var out_color = vec3f(0,0,0);\n\n  return out_color ;\n}\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":241,"value":"## Implementation\n\n### `tick`\n\n`tick` increases and returns how many frames (`render` calls) have occurred. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":246,"value":"mutable last_tick = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":249,"value":"tick = () => { mutable last_tick += 1; return mutable last_tick; }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":347,"value":"### `delta_t`\n\n`delta_t` indicates how long it has been since the last call to `delta_t` in milliseconds. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":353,"value":"mutable last_t = Date.now()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":356,"value":"delta_t = () => {let t = Date.now(); let delta = t - mutable last_t; mutable last_t = t; return delta % 4294967296; }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":18,"value":"## WebGPU Components","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":20,"value":"### WebGPU Initialization & Pipeline Creation\n\nWe initialize WebGPU if supported and then create a render pipeline as needed (when pipeline constants change).\n\nWrite-to-canvas info from [WebGPUFundamentals](https://webgpufundamentals.org/webgpu/lessons/webgpu-storage-textures.html#canvas-as-a-storage-texture \"WebGPU Storage Textures: Canvas as a Storage Texture\").","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":22,"value":"#### Adapter\n\nCreate the WebGPU adapter if we have it","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":24,"value":"adapter = await navigator.gpu?.requestAdapter();","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":27,"value":"#### Device and Canvas Storage\n\nSpecify the storage format. If the newer `bgra8unorm`, we have to specify its storage (defaults to `rgba`'s version).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":29,"value":"presentationFormat = adapter?.features.has('bgra8unorm-storage')\n      ? navigator.gpu.getPreferredCanvasFormat()\n      : 'rgba8unorm';","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":32,"value":"Create the device to use the GPU. We have to explicitly call for `bgra` storage if that is what is preferred. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":34,"value":"device = {\n  let device = await adapter?.requestDevice({\n    requiredFeatures: presentationFormat === 'bgra8unorm'\n        ? ['bgra8unorm-storage']\n        : [],\n  });\n  invalidation.then(() => device.destroy());\n  return device;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":123,"value":"#### Shader module\n\nCompile the shader. Process any errors for reporting (from [WebGPUFundamentals](https://webgpufundamentals.org/webgpu/lessons/webgpu-debugging.ht \"WebGPU Debugging\")). \n\nFirst, an error logger:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":128,"value":"function log(...args) {\n  const elem = html`
`;\n  elem.innerHTML = args.join(' ');\n  error_log.appendChild(elem);\n  error_log.style.display = \"block\";\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":130,"value":"A dummy `error_log` element for compilation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":132,"value":"error_log = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":137,"value":"Now the shader itself.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":125,"value":"module = \n{\n  if(!device)\n    return undefined;\n\n  const module = device.createShaderModule({\n    label: 'Assignment Shader',\n    code: shader_src\n  });\n\n  error_log.style.display = \"none\";\n  error_log.innerHTML = \"\";  \n  const errors = await module.getCompilationInfo();\n  if(errors.messages.length != 0)\n  {\n  \n    // Split the code into lines\n    const lines = shader_src.split('\\n');\n  \n    // Sort the messages by line numbers in reverse order\n    // so that as we insert the messages they won't affect\n    // the line numbers.\n    const msgs = [...errors.messages].sort((a, b) => b.lineNum - a.lineNum);\n  \n    // Insert the error messages between lines\n    for (const msg of msgs) {\n      lines.splice(msg.lineNum, 0,\n        \"\",\n        `${''.padEnd(msg.linePos - 1)}${''.padEnd(msg.length, '^')}`,\n        msg.message,\n        \"
\"\n      );\n    }\n  \n    log(lines.join('\\n'));\n  }\n  \n  return module;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":140,"value":"#### Pipeline\n\nCreate the pipeline using the shader module and bound buffers.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":281,"value":"Specify the layout (we have to do this as tick/delta_t is not always used).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":272,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":611,"value":"kdBindGroupLayout = device.createBindGroupLayout({\n  label: \"KD Tree Bind Group Layout\",\n  entries: [\n      {\n          binding: 0,                  // kd_nodes\n          visibility: GPUShaderStage.COMPUTE,\n          buffer: { type: \"read-only-storage\" },\n      },\n      {\n          binding: 1,                  // kd_tri_indices\n          visibility: GPUShaderStage.COMPUTE,\n          buffer: { type: \"read-only-storage\" },\n      },\n  ],\n});\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":614,"value":"### Build KD tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":616,"value":"austin_mini_geometry = FileAttachment(\"austin_mini_geom.json\").json()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":619,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":643,"value":"kdTreeData = buildKDTree(austin_mini_geometry.vertexdata, austin_mini_geometry.indexdata);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":635,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":283,"value":"Create the pipeline layout.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":278,"value":"pipelineLayout = device.createPipelineLayout({\n  layout: \"Assignment Pipeline Layout\",\n  bindGroupLayouts: [bindGroupLayout, kdBindGroupLayout],\n});","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":286,"value":"Finally, create the pipeline to be used.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":142,"value":"pipeline = device?.createComputePipeline({\n    label: 'Assignment Pipeline',\n    layout: pipelineLayout,\n    compute: {\n      module,\n      entryPoint: 'set_pixels',\n    },\n  })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":144,"value":"#### Upload Scene \n\nCreate the buffer we will upload the scene information into.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":146,"value":"row_size = 1 * 4 // u32 flag for shape type\n         + 9 * 4 // 9 f32 for data. Only triangles use all 9","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":148,"value":"object_type_map = {return {\"dummy\" : 0, \"sphere\": 1, \"plane\": 2, \"box\": 3, \"tri\" : 4, \"mesh\" : 5, \"ellipse\" : 6}}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":151,"value":"function updateSceneBuffer()\n{\n  if(!device) return undefined;\n\n  // Check if empty\n  var entries = scene.trim().split(\"\\n\");\n  if(entries.length == 1 && entries[0] == \"\")\n    return undefined;\n\n  // Populate CPU data. Need separate arrays as the struct has two data types\n  const scene_data = new ArrayBuffer(row_size * entries.length);\n  const int_view = new Uint32Array(scene_data);\n  const float_view = new Float32Array(scene_data);\n  for(let i = 0; i < entries.length; i++)\n  {\n    var row_values = entries[i].split(\" \");\n    int_view[row_size / 4 * i] = object_type_map[row_values[0]];\n    float_view.set(row_values.slice(1).map(parseFloat), row_size / 4 * i + 1);\n  }\n\n  // Populate GPU buffer\n  const scene_buffer = device.createBuffer({\n    size: row_size * entries.length,\n    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST,\n  });\n  device.queue.writeBuffer(scene_buffer, 0, scene_data);\n  \n  return scene_buffer;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":219,"value":"#### Upload Transforms\n\nCreate and populate the buffer we will upload the transforms into.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":221,"value":"xform_row_size = 1 * 4 // i32 for origin index\n               + 1 * 4 // i32 for parent index\n               + 1 * 4 // u32 for animate flag\n               + 1 * 4 // padding (WebGPU pads to 4 bytes)\n               + 16 * 4 // 16 f32 for 4x4 matrix.","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":224,"value":"$39","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":226,"value":"isAlpha = c => /^[A-Z]$/i.test(c)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":156,"value":"#### GPU Renderer\nThe render function. It processes the current scene description and submits it to be rendered. Called when requested by user so we are not overtaxing the GPU with tracing.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":158,"value":"$3a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":44,"value":"## Color Constants\n\nWe use a lot of colors; define constants to use for them. They are imported.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":46,"value":"import {x_color,y_color,z_color,u_color,v_color,n_color,camera_color,viewport_color,image_color,ray_color,object_color,scene_color,spancolor} from \"@cse4413msstate/graphics-color-functions\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":229,"value":"## Libraries","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":231,"value":"glm = import(\"gl-matrix\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W3b","stdlib":"1","titling":"auto"}}
30:"$2f:body"