A simple rust library to help create octrees and quadtrees for chunked level of detail

Overview

Documentation

LodTree

LodTree, a simple tree data structure for doing chunk-based level of detail.

Goals

The aim of this crate is to provide a generic, easy to use tree data structure that can be used to make Quadtrees, Octrees and more for chunked level of detail.

Internally, the tree tries to keep as much memory allocated, to avoid the cost of heap allocation, and stores the actual chunks data seperate from the tree data.

This does come at a cost. Mainly, only the chunks that are going to be added and their locations can be retreived as a slice, although for most (procedural) terrain implementations.

Non-goals

Be a general-usage tree data structure for storing items at specific locations.

Features

  • Provides sets of chunks that need some action performed on them
  • Tries to avoid memory (re)allocations and moves
  • Stores chunks themselves in a contiguous array
  • Uses an internal chunk cache to allow reusing chunks at a memory tradeoff
  • Provides some extra iterators for finding chunks in certain bounds

Examples:

  • rayon: shows how to use the tree with rayon to generate new chunks in parallel.
  • glium: shows how a basic drawing setup would work, with glium to do the drawing.

Usage:

Import the crate

use lodtree::*;
use lodtree::coords::OctVec; // or Quadvec if you're making an octree

The tree is it's own struct, and accepts a chunk (anything that implements Sized) and the lod vector (Anything that implements the LodVec trait).

let mut tree = Tree::<Chunk, OctVec>::new();

If you want to update chunks due to the camera being moved, you can check if it's needed with prepare_update. It takes in 3 parameters.

Targets: where to generate the most detail around.

The given LodVec implementations (OctVec and QuadVec) take in 4 and 3 arguments respectively. The first 3/2 are the position in the tree, which is dependant on the lod level. and the last parameter is the lod level. No lods smaller than this will be generated for this target.

Detail: The amount of detail for the targets The default implementation defines this as the amount of chunks at the target lod level surrounding the target chunk.

Chunk creator: Internally a buffer for new chunks is filled, and this function is called to create the new chunk. It takes in the LodVec of the position of the chunk.

let needs_updating = tree.prepare_update(
	&[OctVec(8, 8, 8, 8)], // the target positions to generate the lod around
	4, // amount of detail
	|pos| Chunk {} // and the function to construct the chunk with
);

Now, the tree is ready for an update, so now we'll want to do something with that. First, we want to process all chunks that are going to be added. This is the only thing the API exposes as a slice, so we can nicely iterate over that in parallel with rayon.

tree.get_chunks_to_add_slice_mut()
	.iter_mut() // or par_iter_mut if you're using rayon
	.for_each(|(position, chunk)| {

		// and run expensive init, probably does something with procedural generation
		chunk.expensive_init(*position);
	});

Next, we'll also want to change the visibility of some chunks so they don't overlap with higher detail lods.

// and make all chunks visible or not
for i in 0..tree.get_num_chunks_to_activate() {
	tree.get_chunk_to_activate_mut(i).set_visible(true);
}

for i in 0..tree.get_num_chunks_to_deactivate() {
	tree.get_chunk_to_deactivate_mut(i).set_visible(false);
}

We'll probably also want to do some cleanup with chunks that are removed.

for i in 0..tree.get_num_chunks_to_remove() {
	tree.get_chunk_to_remove_mut(i).cleanup();
} 

And finally, actually update the tree with the new chunks. Note that it's likely needed to do the prepare_update and do_update cycle a number of times before no new chunks need to be added, as the tree only adds one lod level at a time.

tree.do_update();

But we're not done yet! After this step there's a number of chunks that are removed from the cache, and will not be added back into the tree We'll want to clean those up now

for (position, chunk) in tree.get_chunks_to_delete_slice_mut().iter_mut() {
	chunk.true_cleanup();
}

// and finally, complete the entire update
tree.complete_update();

Roadmap

0.2.0:

  • Support getting "edited" chunks, via also passing along a region in which chunks would be edited. PARTIALLY DONE, NEEDS DOCS
  • caching DONE
  • iterators for all chunk data accessing methods. DONE
  • getting a chunk by position DONE
  • swap L and C, so the key (position) is before the chunk, which is consistent with other key-value datatypes in rust

0.3.0:

  • progressive loading (double bounds check, one for when to subdivide and one for when to merge, as well as limit on the amount of things we can add at a time)
  • no-std (although alloc will be required here)

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

You might also like...
Coding-challenge - Algorithms and Data-structures, problems and solutions in Rust language using cargo-workspaces

Coding Challenge LeetCode/Hackerrank e.t.c Using this as an opportunity to improve my knowledge of rust lang If you found this repo useful to you, add

Rust-algorithm-club - Learn algorithms and data structures with Rust

Rust Algorithm Club 🚧 🚧 This repo is under construction. Most materials are written in Chinese. Check it out here if you are able to read Chinese. W

Array helpers for Rust's Vector and String types

array_tool Array helpers for Rust. Some of the most common methods you would use on Arrays made available on Vectors. Polymorphic implementations for

K-dimensional tree in Rust for fast geospatial indexing and lookup

kdtree K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup Crate Documentation Usage Benchmark License Usage Add kdtr

Algorithms and Data Structures of all kinds written in Rust.

Classic Algorithms in Rust This repo contains the implementation of various classic algorithms for educational purposes in Rust. Right now, it is in i

Serialize/DeSerialize for Rust built-in types and user defined types (complex struct types)

Serialize/DeSerialize for Rust built-in types and user defined types (complex struct types)

Common data structures and algorithms in Rust

Contest Algorithms in Rust A collection of classic data structures and algorithms, emphasizing usability, beauty and clarity over full generality. As

Rust data structures and client for the PubChem REST API

pubchem.rs Rust data structures and client for the PubChem REST API. 🔌 Usage 💊 Compound Create a Compound to query the PubChem API for a single comp

rust_aads - Rust Algorithms And Data Structures

rust_aads - Rust Algorithms And Data Structures rust_aads is an open repository with algorithms and data structures, used in computer science and comp

Comments
  • Chunk caching and editing

    Chunk caching and editing

    Plan for editing: provide a way to get all chunks affected by an edit, and all chunks in the tree affected by an edit, preferably via an iterator

    Also, try and implement caching: keep old chunks around, so reloading is easy This should probably be a demo, alongside editing/saving

    enhancement 
    opened by Dimev 0
Owner
Dimev
Dimev
Rust library for string parsing of basic data structures.

afmt Simple rust library for parsing basic data structures from strings. Usage You can specify string formats to any strucute, via the use of the fmt

Eduard 4 May 8, 2021
Library containing various Data Structures implemented using Rust.

rust-data-structures Library containing various Data Structures implemented using Rust. Running You can test the library by running cargo test, an exa

c1m50c 1 Jan 6, 2022
A library for comparing data structures in Rust, oriented toward testing

Delta: Structural differencing in Rust The delta crate defines the trait Delta, along with a derive macro for auto-generating instances of this trait

John Wiegley 19 Oct 7, 2022
A library for comparing data structures in Rust, oriented toward testing

The comparable crate defines the trait [Comparable], along with a derive macro for auto-generating instances of this trait for most data types. Primar

John Wiegley 19 Oct 7, 2022
A lightweight Rust library for BitVector Rank&Select operations, coupled with a generic Sparse Array implementation

A lightweight Rust library for BitVector Rank&Select operations, coupled with a generic Sparse Array implementation

Alperen Keleş 5 Jun 20, 2022
🦀️Linkmap file parse library for rust

Linkmap file parse library for rust

everettjf 8 Sep 7, 2022
NixEl is a Rust library that turns Nix code into a variety of correct, typed, memory-safe data-structures

?? NixEL Lexer, Parser, Abstract Syntax Tree and Concrete Syntax Tree for the Nix Expressions Language. NixEl is a Rust library that turns Nix code in

Kevin Amado 56 Dec 29, 2022
Hypergraph is a data structure library to generate directed hypergraphs.

Hypergraph is data structure library to create a directed hypergraph in which a hyperedge can join any number of vertices.

Davy Duperron 112 Aug 24, 2021
Library containing implementations of various sequential data-structures.

Library containing implementations of various sequential data-structures.

c1m50c 0 May 15, 2022
Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

Serde is a framework for serializing and deserializing Rust data structures efficiently and generically.

null 6.5k Dec 31, 2022