Skip to content

Instantly share code, notes, and snippets.

@Kielan

Kielan/Subdivide.rs

Last active December 2, 2025 18:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Kielan/5a9f3c10759b71b85ce09351620d3672 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Kielan/5a9f3c10759b71b85ce09351620d3672 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Kielan revised this gist Dec 2, 2025. 1 changed file with 6 additions and 16 deletions.
    22 changes: 6 additions & 16 deletions Subdivide.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,16 +1,14 @@
    use bevy::prelude::*;
    use std::collections::HashMap;

    //
    // --------------- Planet Data Resource ---------------
    //
    // Planet Data Resource
    #[derive(Resource, Clone)]
    pub struct PlanetData {
    pub radius: f32,
    pub lod_focus: Vec3,
    pub max_lod: usize,

    /// lod_levels[i].distance, lod_levels[i].resolution
    // lod_levels[i].distance, lod_levels[i].resolution
    pub lod_levels: Vec<LodLevel>,

    pub min_height: f32,
    @@ -32,9 +30,7 @@ impl PlanetData {
    }
    }

    //
    // --------------- Quadtree Chunk Struct ---------------
    //
    // Quadtree Chunk Struct
    #[derive(Clone)]
    pub struct QuadtreeChunk {
    pub bounds_pos: Vec3,
    @@ -116,9 +112,7 @@ impl QuadtreeChunk {
    }
    }

    //
    // ---------------- PlanetMeshFace Component ----------------
    //
    // PlanetMeshFace Component
    #[derive(Component)]
    pub struct PlanetMeshFace {
    pub normal: Vec3,
    @@ -140,9 +134,7 @@ impl PlanetMeshFace {
    }
    }

    //
    // ---------------- Mesh Regeneration System ----------------
    //
    // Mesh Regeneration System
    pub fn regenerate_mesh_system(
    mut commands: Commands,
    mut query: Query<(Entity, &mut PlanetMeshFace)>,
    @@ -201,9 +193,7 @@ pub fn regenerate_mesh_system(
    }
    }

    //
    // ----------------- Visualize Quad Chunk (Mesh Builder) -----------------
    //
    // Visualize Quad Chunk (Mesh Builder)
    pub fn visualize_chunk(
    chunk: &QuadtreeChunk,
    commands: &mut Commands,
  2. Kielan revised this gist Dec 2, 2025. 1 changed file with 243 additions and 0 deletions.
    243 changes: 243 additions & 0 deletions Subdivide.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -92,3 +92,246 @@ impl QuadtreeChunk {
    let distance = sphere_pos.distance(focus_point);

    let should_subdivide_
    self.depth < self.max_depth
    && distance <= planet.lod_levels[self.depth].distance;

    let child_bounds_pos = if should_subdivide {
    Vec3::new(child_pos_2d.x, 0.0, child_pos_2d.y)
    } else {
    Vec3::new(
    child_pos_2d.x - quarter_size,
    -quarter_size,
    child_pos_2d.y - quarter_size,
    )
    };

    let mut child = QuadtreeChunk::new(child_bounds_pos, half_extents, self.depth + 1, self.max_depth);

    if should_subdivide {
    child.subdivide(focus_point, face_origin, axis_a, axis_b, planet);
    }

    self.children.push(child);
    }
    }
    }

    //
    // ---------------- PlanetMeshFace Component ----------------
    //
    #[derive(Component)]
    pub struct PlanetMeshFace {
    pub normal: Vec3,

    pub chunks: HashMap<String, Entity>,
    pub chunks_current: HashMap<String, bool>,

    pub quadtree: Option<QuadtreeChunk>,
    }

    impl PlanetMeshFace {
    pub fn new(normal: Vec3) -> Self {
    Self {
    normal,
    chunks: HashMap::new(),
    chunks_current: HashMap::new(),
    quadtree: None,
    }
    }
    }

    //
    // ---------------- Mesh Regeneration System ----------------
    //
    pub fn regenerate_mesh_system(
    mut commands: Commands,
    mut query: Query<(Entity, &mut PlanetMeshFace)>,
    planet: Res<PlanetData>,
    mut meshes: ResMut<Assets<Mesh>>,
    mut materials: ResMut<Assets<StandardMaterial>>,
    ) {
    for (entity, mut face) in query.iter_mut() {
    let normal = face.normal;

    let mut quadtree = QuadtreeChunk::new(Vec3::ZERO, Vec3::splat(2.0), 0, planet.max_lod);

    let axis_a = Vec3::new(normal.y, normal.z, normal.x).normalize();
    let axis_b = normal.cross(axis_a).normalize();

    quadtree.subdivide(
    planet.lod_focus,
    normal,
    axis_a,
    axis_b,
    &planet,
    );

    face.quadtree = Some(quadtree);

    face.chunks_current.clear();

    if let Some(q) = &face.quadtree {
    visualize_chunk(
    q,
    &mut commands,
    &mut meshes,
    &mut materials,
    &mut face.chunks,
    &mut face.chunks_current,
    normal,
    axis_a,
    axis_b,
    &planet,
    entity,
    );
    }

    // remove old chunks
    let obsolete: Vec<_> = face.chunks
    .iter()
    .filter(|(id, _)| !face.chunks_current.contains_key(*id))
    .map(|(id, _)| id.clone())
    .collect();

    for id in obsolete {
    if let Some(ent) = face.chunks.remove(&id) {
    commands.entity(ent).despawn_recursive();
    }
    }
    }
    }

    //
    // ----------------- Visualize Quad Chunk (Mesh Builder) -----------------
    //
    pub fn visualize_chunk(
    chunk: &QuadtreeChunk,
    commands: &mut Commands,
    meshes: &mut Assets<Mesh>,
    materials: &mut Assets<StandardMaterial>,
    chunks: &mut HashMap<String, Entity>,
    chunks_current: &mut HashMap<String, bool>,
    face_origin: Vec3,
    axis_a: Vec3,
    axis_b: Vec3,
    planet: &PlanetData,
    parent_ent: Entity,
    ) {
    if chunk.children.is_empty() {
    chunks_current.insert(chunk.identifier.clone(), true);

    if chunks.contains_key(&chunk.identifier) {
    return;
    }

    let size = chunk.bounds_size.x;
    let offset = chunk.bounds_pos;

    let resolution = planet.lod_levels[chunk.depth - 1].resolution;
    let res = resolution;

    let mut vertices = Vec::with_capacity(res * res);
    let mut normals = vec![Vec3::ZERO; res * res];
    let mut indices = Vec::new();

    // build vertices
    for y in 0..res {
    for x in 0..res {
    let i = x + y * res;

    let percent_x = x as f32 / (res - 1) as f32;
    let percent_y = y as f32 / (res - 1) as f32;

    let local =
    Vec2::new(offset.x, offset.z) + Vec2::new(percent_x * size, percent_y * size);

    let point_on_plane =
    face_origin + axis_a * local.x + axis_b * local.y;

    let sphere = planet.point_on_planet(point_on_plane.normalize());

    vertices.push(sphere);
    }
    }

    // indices
    for y in 0..res - 1 {
    for x in 0..res - 1 {
    let i = x + y * res;

    indices.extend_from_slice(&[
    i as u32,
    (i + res) as u32,
    (i + res + 1) as u32,
    i as u32,
    (i + res + 1) as u32,
    (i + 1) as u32,
    ]);
    }
    }

    // compute normals
    for tri in indices.chunks(3) {
    let a = tri[0] as usize;
    let b = tri[1] as usize;
    let c = tri[2] as usize;

    let v0 = vertices[a];
    let v1 = vertices[b];
    let v2 = vertices[c];

    let n = (v1 - v0).cross(v2 - v0).normalize();

    normals[a] += n;
    normals[b] += n;
    normals[c] += n;
    }

    for n in normals.iter_mut() {
    *n = n.normalize();
    }

    // build mesh
    let mut mesh = Mesh::new(PrimitiveTopology::TriangleList);

    mesh.insert_attribute(Mesh::ATTRIBUTE_POSITION, vertices);
    mesh.insert_attribute(Mesh::ATTRIBUTE_NORMAL, normals);
    mesh.set_indices(Some(Indices::U32(indices)));

    let mesh_handle = meshes.add(mesh);

    let mat = materials.add(StandardMaterial {
    base_color: planet.planet_color,
    ..Default::default()
    });

    let ent = commands.spawn(PbrBundle {
    mesh: mesh_handle,
    material: mat,
    ..Default::default()
    })
    .set_parent(parent_ent)
    .id();

    chunks.insert(chunk.identifier.clone(), ent);

    return;
    }

    // recurse
    for child in &chunk.children {
    visualize_chunk(
    child,
    commands,
    meshes,
    materials,
    chunks,
    chunks_current,
    face_origin,
    axis_a,
    axis_b,
    planet,
    parent_ent,
    );
    }
    }
  3. Kielan created this gist Dec 2, 2025.
    94 changes: 94 additions & 0 deletions Subdivide.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,94 @@
    use bevy::prelude::*;
    use std::collections::HashMap;

    //
    // --------------- Planet Data Resource ---------------
    //
    #[derive(Resource, Clone)]
    pub struct PlanetData {
    pub radius: f32,
    pub lod_focus: Vec3,
    pub max_lod: usize,

    /// lod_levels[i].distance, lod_levels[i].resolution
    pub lod_levels: Vec<LodLevel>,

    pub min_height: f32,
    pub max_height: f32,

    pub planet_color: Color,
    }

    #[derive(Clone)]
    pub struct LodLevel {
    pub distance: f32,
    pub resolution: usize,
    }

    impl PlanetData {
    /// Equivalent to Godot's planet_data.point_on_planet(dir)
    pub fn point_on_planet(&self, dir: Vec3) -> Vec3 {
    dir.normalize() * self.radius
    }
    }

    //
    // --------------- Quadtree Chunk Struct ---------------
    //
    #[derive(Clone)]
    pub struct QuadtreeChunk {
    pub bounds_pos: Vec3,
    pub bounds_size: Vec3,
    pub depth: usize,
    pub max_depth: usize,
    pub identifier: String,
    pub children: Vec<QuadtreeChunk>,
    }

    impl QuadtreeChunk {
    pub fn new(bounds_pos: Vec3, bounds_size: Vec3, depth: usize, max_depth: usize) -> Self {
    let identifier = format!(
    "{}_{}_{}",
    bounds_pos, bounds_size, depth
    );

    Self {
    bounds_pos,
    bounds_size,
    depth,
    max_depth,
    identifier,
    children: Vec::new(),
    }
    }

    pub fn subdivide(
    &mut self,
    focus_point: Vec3,
    face_origin: Vec3,
    axis_a: Vec3,
    axis_b: Vec3,
    planet: &PlanetData,
    ) {
    let half_size = self.bounds_size.x * 0.5;
    let quarter_size = self.bounds_size.x * 0.25;
    let half_extents = Vec3::splat(half_size);

    let offsets = [
    Vec2::new(-quarter_size, -quarter_size),
    Vec2::new(quarter_size, -quarter_size),
    Vec2::new(-quarter_size, quarter_size),
    Vec2::new(quarter_size, quarter_size),
    ];

    for offset in offsets {
    let child_pos_2d =
    Vec2::new(self.bounds_pos.x, self.bounds_pos.z) + offset;

    let local_center =
    face_origin + axis_a * child_pos_2d.x + axis_b * child_pos_2d.y;

    let sphere_pos = planet.point_on_planet(local_center.normalize());
    let distance = sphere_pos.distance(focus_point);

    let should_subdivide_