struct GrassUniforms {
    view_projection: mat4x4<f32>,
    frustum_planes: array<vec4<f32>, 6>,
    camera_position: vec4<f32>,
    camera_right: vec4<f32>,
    camera_tile: vec4<i32>,
    sun_direction: vec4<f32>,
    sun_color: vec4<f32>,
    ambient: vec4<f32>,
    wind: vec4<f32>,
    radii: vec4<f32>,
    params: vec4<f32>,
    counts: vec4<u32>,
    domain: vec4<f32>,
    height_map: vec4<f32>,
    height_bounds: vec4<f32>,
    splat: vec4<f32>,
    pushers: array<vec4<f32>, 8>,
    pusher_strength: array<vec4<f32>, 2>,
};

struct GrassType {
    shape: vec4<f32>,
    curve: vec4<f32>,
    color_base: vec4<f32>,
    color_tip: vec4<f32>,
    misc: vec4<f32>,
    misc2: vec4<f32>,
};

struct GrassBlade {
    position_height: vec4<f32>,
    facing_type: vec4<f32>,
    shape: vec4<f32>,
    extra: vec4<f32>,
};

struct GrassTileEntry {
    data: vec4<i32>,
};

const GRASS_TILE_SIZE: f32 = 8.0;
const GRASS_WORKGROUPS_PER_TILE: u32 = 25u;
const GRASS_MAX_BLADES: u32 = 524288u;
const GRASS_MAX_BLADE_TILES: u32 = 4096u;
const GRASS_MAX_FAR_TILES: u32 = 8192u;
const GRASS_FAR_TILE_SPAN: f32 = 32.0;
const GRASS_FAR_TILE_DIVISIONS: u32 = 8u;
const GRASS_FOLD_HEIGHT: f32 = 0.5;
const GRASS_PI: f32 = 3.14159265;
const GRASS_TAU: f32 = 6.2831853;

fn grass_pcg2d(p_in: vec2<u32>) -> vec2<u32> {
    var p = p_in * 1664525u + 1013904223u;
    p.x += p.y * 1664525u;
    p.y += p.x * 1664525u;
    p ^= p >> vec2<u32>(16u, 16u);
    p.x += p.y * 1664525u;
    p.y += p.x * 1664525u;
    p ^= p >> vec2<u32>(16u, 16u);
    return p;
}

fn grass_scramble(value: u32) -> u32 {
    var x = value ^ (value >> 17u);
    x *= 0xED5AD4BBu;
    x ^= x >> 11u;
    x *= 0xAC4C1B51u;
    x ^= x >> 15u;
    x *= 0x31848BABu;
    x ^= x >> 14u;
    return x;
}

fn grass_hash01(value: u32) -> f32 {
    return f32(value) * 2.3283064e-10;
}

fn grass_hash_tile(tile: vec2<i32>, salt: u32) -> u32 {
    let h = grass_pcg2d(vec2<u32>(bitcast<u32>(tile.x), bitcast<u32>(tile.y)) ^ vec2<u32>(salt, salt * 0x9E3779B9u));
    return h.x ^ grass_scramble(h.y);
}

fn grass_lattice01(cell: vec2<i32>, salt: u32) -> f32 {
    return grass_hash01(grass_hash_tile(cell, salt));
}

fn grass_value_noise(p: vec2<f32>, salt: u32) -> f32 {
    let base = floor(p);
    let fraction = p - base;
    let smooth_fraction = fraction * fraction * (3.0 - 2.0 * fraction);
    let cell = vec2<i32>(base);
    let v00 = grass_lattice01(cell, salt);
    let v10 = grass_lattice01(cell + vec2<i32>(1, 0), salt);
    let v01 = grass_lattice01(cell + vec2<i32>(0, 1), salt);
    let v11 = grass_lattice01(cell + vec2<i32>(1, 1), salt);
    let x0 = mix(v00, v10, smooth_fraction.x);
    let x1 = mix(v01, v11, smooth_fraction.x);
    return mix(x0, x1, smooth_fraction.y);
}

fn grass_wind_sample(world_xz: vec2<f32>, time: f32, wind: vec4<f32>) -> f32 {
    let scroll = world_xz * 0.13 - vec2<f32>(wind.x, wind.y) * time * (0.7 + wind.z * 0.4);
    let broad = grass_value_noise(scroll, 71u);
    let detail = grass_value_noise(scroll * 3.3 + vec2<f32>(17.0, 31.0), 137u);
    return wind.z * (0.5 + 0.5 * broad) * (1.0 - wind.w * 0.5 + wind.w * detail);
}

struct GrassVoronoi {
    point: vec2<f32>,
    cell_value: f32,
    distance: f32,
};

fn grass_voronoi(p: vec2<f32>, scale: f32, salt: u32) -> GrassVoronoi {
    let cell = floor(p / scale);
    var result: GrassVoronoi;
    result.distance = 1e9;
    result.cell_value = 0.0;
    result.point = p;
    for (var offset_y = -1; offset_y <= 1; offset_y++) {
        for (var offset_x = -1; offset_x <= 1; offset_x++) {
            let neighbor = cell + vec2<f32>(f32(offset_x), f32(offset_y));
            let neighbor_cell = vec2<i32>(neighbor);
            let h = grass_hash_tile(neighbor_cell, salt);
            let jitter = vec2<f32>(grass_hash01(h), grass_hash01(grass_scramble(h)));
            let point = (neighbor + jitter) * scale;
            let dist = distance(p, point);
            if dist < result.distance {
                result.distance = dist;
                result.point = point;
                result.cell_value = grass_hash01(grass_scramble(h ^ 0x68BC21EBu));
            }
        }
    }
    return result;
}

fn grass_sample_height(
    height_texture: texture_2d_array<f32>,
    world_xz: vec2<f32>,
    height_map: vec4<f32>,
    height_bounds: vec4<f32>,
    camera_planar_distance: f32,
) -> f32 {
    if height_map.w < 0.5 {
        return 0.0;
    }
    if height_map.w > 1.5 {
        var layer = u32(height_bounds.z);
        var texel = height_map.z;
        var safe_radius = texel * 192.0;
        let max_layer = u32(height_bounds.w);
        for (var step = 0u; step < 8u; step++) {
            if camera_planar_distance <= safe_radius || layer >= max_layer {
                break;
            }
            layer += 1u;
            texel *= 2.0;
            safe_radius *= 2.0;
        }
        return terrain_cache_sample(height_texture, layer, texel, world_xz);
    }
    let resolution = vec2<f32>(textureDimensions(height_texture));
    let uv = (world_xz - height_map.xy) / height_map.z;
    let texel = clamp(uv * resolution - vec2<f32>(0.5, 0.5), vec2<f32>(0.0, 0.0), resolution - vec2<f32>(1.0, 1.0));
    let base = floor(texel);
    let fraction = texel - base;
    let index = vec2<i32>(base);
    let index_max = vec2<i32>(resolution) - vec2<i32>(1, 1);
    let index_next = min(index + vec2<i32>(1, 1), index_max);
    let h00 = textureLoad(height_texture, index, 0, 0).r;
    let h10 = textureLoad(height_texture, vec2<i32>(index_next.x, index.y), 0, 0).r;
    let h01 = textureLoad(height_texture, vec2<i32>(index.x, index_next.y), 0, 0).r;
    let h11 = textureLoad(height_texture, index_next, 0, 0).r;
    let x0 = mix(h00, h10, fraction.x);
    let x1 = mix(h01, h11, fraction.x);
    return mix(x0, x1, fraction.y);
}

fn grass_type_edge(world_xz: vec2<f32>, scale: f32) -> vec3<f32> {
    let cell = floor(world_xz / scale);
    var best_distance = 1e9;
    var best_value = 0.0;
    var second_distance = 1e9;
    var second_value = 0.0;
    for (var offset_y = -1; offset_y <= 1; offset_y++) {
        for (var offset_x = -1; offset_x <= 1; offset_x++) {
            let neighbor = cell + vec2<f32>(f32(offset_x), f32(offset_y));
            let neighbor_cell = vec2<i32>(neighbor);
            let h = grass_hash_tile(neighbor_cell, 11u);
            let jitter = vec2<f32>(grass_hash01(h), grass_hash01(grass_scramble(h)));
            let point = (neighbor + jitter) * scale;
            let dist = distance(world_xz, point);
            let value = grass_hash01(grass_scramble(h ^ 0x68BC21EBu));
            if dist < best_distance {
                second_distance = best_distance;
                second_value = best_value;
                best_distance = dist;
                best_value = value;
            } else if dist < second_distance {
                second_distance = dist;
                second_value = value;
            }
        }
    }
    let edge = clamp((second_distance - best_distance) / (scale * 0.45), 0.0, 1.0);
    return vec3<f32>(best_value, second_value, edge);
}

fn grass_select_type(world_xz: vec2<f32>, scale: f32, type_count: u32, dither: f32) -> u32 {
    let edge_data = grass_type_edge(world_xz, scale);
    var selected = edge_data.x;
    if dither > 0.5 + 0.5 * edge_data.z {
        selected = edge_data.y;
    }
    return min(u32(selected * f32(type_count)), type_count - 1u);
}

fn grass_bezier(p0: vec3<f32>, p1: vec3<f32>, p2: vec3<f32>, p3: vec3<f32>, t: f32) -> vec3<f32> {
    let inverse_t = 1.0 - t;
    return p0 * (inverse_t * inverse_t * inverse_t)
        + p1 * (3.0 * inverse_t * inverse_t * t)
        + p2 * (3.0 * inverse_t * t * t)
        + p3 * (t * t * t);
}

fn grass_bezier_derivative(p0: vec3<f32>, p1: vec3<f32>, p2: vec3<f32>, p3: vec3<f32>, t: f32) -> vec3<f32> {
    let inverse_t = 1.0 - t;
    return (p1 - p0) * (3.0 * inverse_t * inverse_t)
        + (p2 - p1) * (6.0 * inverse_t * t)
        + (p3 - p2) * (3.0 * t * t);
}

const GRASS_MAX_BLADE_LOD: u32 = 5u;

fn grass_lod_for_distance(blade_distance: f32, high_radius: f32) -> u32 {
    if blade_distance < high_radius {
        return 0u;
    }
    let ring = 1u + u32(max(floor(log2(blade_distance / high_radius)), 0.0));
    return min(ring, GRASS_MAX_BLADE_LOD);
}

fn grass_cell_lod(tile: vec2<i32>, camera_xz: vec2<f32>, high_radius: f32) -> u32 {
    let center = (vec2<f32>(tile) + vec2<f32>(0.5, 0.5)) * GRASS_TILE_SIZE;
    return grass_lod_for_distance(distance(center, camera_xz), high_radius);
}

fn grass_inside_domain(world_xz: vec2<f32>, finite: u32, domain: vec4<f32>) -> bool {
    if finite == 0u {
        return true;
    }
    return world_xz.x >= domain.x && world_xz.y >= domain.y && world_xz.x <= domain.z && world_xz.y <= domain.w;
}

fn grass_rect_overlaps(min_a: vec2<f32>, max_a: vec2<f32>, finite: u32, domain: vec4<f32>) -> bool {
    if finite == 0u {
        return true;
    }
    return max_a.x >= domain.x && max_a.y >= domain.y && min_a.x <= domain.z && min_a.y <= domain.w;
}
