polyspheres-generator

The aim of this project is to implement a method for deterministically generating chunk-based, LOD compatible 3D geometry in the format of a polygonally tiled sphere, or "polysphere". The method satisfies these constraints:

• All geometry lies on the surface of a specified sphere.
• Geometry is generated in chunks which can be fully separated from each other.
• Chunks "agree" with each other; no visible boundaries, artifacts, or distortions at chunk boundaries.
• LOD-compatible:
  • Chunk generation is informed by a 3D boundary, which the resultant geometry roughly complies with. Adjacent chunks will still agree, even when they cross their shared input boundary.
  • This means that the next, higher resolution LOD level can be defined by using each face of the previous level as the boundary for a new chunk.
• Spatial locality: While chunks may depend on partial generation results from their neighbors, no chunk requires any chunk far away from it to be generated, nor does it require its neighbors to be fully generated.
• Performant: The process should complete in a reasonable time and scale efficiently. Generation should be fast and cheap enough to allow for applications in procedural video game terrain generation.

Implementation

The project is implemented as a compiled library written in Rust, which can be invoked through FFI, thus making it portable and performant. The library uses the tokio async runtime to manage concurrency, allowing chunks to be generated in parallel and supporting straightforward internal management of task dependencies.

The final stage of the process, calculating a voronoi graph on the surface of the sphere, has been implemented as a series of compute shaders due to performance considerations. This makes the project dependent on a GPU.

Contents of this repo

This repo links to three submodules:

• library-rs - The core library.
• server-asp - An example ASP.NET server that hooks into the library and provides geometry data over HTTPS.
• visualizer-react - A web visualizer written in React + Babylon.js that displays the geometry returned by server-asp.

Usage

The rust library can be compiled into a *.dll file with cargo build --release, which will generate polyspheres_generator.dll in the target/release directory. This DLL can be imported by a wide variety of programming languages, and should be placed next to the final executable of the program seeking to use it. You will have to create bindings in the importing language, which describe the functions and data types involved. A full usage example is provided in server-asp.

Important

The internal logic for some functions uses blocking thread-safe access, and should not be called on non-blocking threads (such as ASP.NET I/O worker threads). This is known to be an issue specifically for get_task_result(). It is recommended to assign invocations of these functions to their own threads, and they may panic if they detect that they are on an inappropriate thread.

Return Codes

All functions return a result code from the following enum:

pub enum FunctionReturnCodes {
    Ok = 0,
    InvalidArguments = 1,
    InvalidContext = 2,
    UnknownError = 3,
}

Any other return values are assigned via pointers passed in to the function.

InvalidContext refers to the function being called at an inappropriate time or on properly formed arguments that are nonetheless inappropriate for the operation (e.g. calling init_context_async when init has already been started, or calling get_task_result on a task handle that is still running.).

Functions

---

init_context_async(callback: Option<InitCallback>)

Performs required init such as retrieving references to the GPU device and loading the compute shader. callback will be invoked when the task is finished, or encounters an error.

---

get_init_status(status_out: *mut TaskStatus)

Checks the status of the global init function launched by init_context_async.

---

create_generator(state_out: *mut *mut GeneratorState, seed: u32, sphere_radius: f32, settings: GeneratorSettings)

Instantiates a generator and state machine with the specified settings. Sets a handle to the created state struct that can be passed to most other functions.
Returns InvalidContext if init_context_async has not been resolved before calling this function.

---

get_chunk_async(state: *mut GeneratorState, chunk_index: u32, lod: u32, handle_out: *mut TaskHandle, callback: Option<TaskCallback>)

Launches a task which generates the specified chunk, or retrieves it if it has been generated in the past. callback will be invoked when the task is finished, or encounters an error. The task can be accessed through get_task_status(), get_task_result(), and get_task_error().

---

get_task_status(state: *mut GeneratorState, handle: TaskHandle, status_out: *mut TaskStatus)

Reports on the status of a running task. Returns InvalidArguments if passed an invalid handle (or null pointers).

---

get_task_result(state: *mut GeneratorState, handle: TaskHandle, mesh_out: *mut *mut MappedPolyMesh)

Retrieves the result of a finished task. Returns InvalidArguments if passed an invalid handle (or null pointers), and InvalidContext if the result has not been populated (usually because the task is still running).

---

get_task_error(state: *mut GeneratorState, handle: TaskHandle, message_out: *mut *const c_char)

Retrieves the error message of a finished task. Returns InvalidArguments if passed an invalid handle (or null pointers), and InvalidContext if the record has not been populated (usually because the task is still running)
NOTE: Messages NYI, will only show a placeholder.

---

dispose_generator_async(state: *mut GeneratorState)

Asynchronously shuts down and cleans up the generator. Running tasks will abort as soon as possible. Using state after invoking this will cause undefined behaviour.

---

free_mapped_polymesh(ptr: *mut MappedPolyMesh)

Frees a mapped polymesh.

---

Generation Process

The process described here is what has been implemented, but the details of individual stages can be modified substantially while still fulfilling the intended constraints, to produce whatever type of geometry the user is interested in.

Define Initial Context

The polysphere is defined with certain attributes:

• Sphere center and radius
• Seed
• Chunks layout:
  • Indices
  • Boundaries (edge loops in 3D space)
  • Centers
  • Adjacencies (which chunks are adjacent to which other chunks?)

For our examples, a standard icosahedron can be used to trivially generate the chunk layout; each face of the icosahedron corresponds to one chunk.

The project currently uses hardcoded functions to provide the chunk layout. One of the next steps is to replace these with callbacks passed in by the user, allowing for configurable layouts.

Individual Chunk Generation, Stage One: Local Data

This stage generates all information for a chunk that does not depend on any information from its neighbors. In our case, this consists of a list of randomly placed points ("sites") generated by Poisson Disk Sampling, and then culled to lie within the chunk boundary.

Stage Two: Relaxation

This process must be completed by the current chunk and all neighbors, meaning it depends on the local data from all neighbors up to two steps away.

First, we assemble all sites from the current chunk and all immediate neighbors, then filter to only include those within a certain distance of the chunk boundary. Filtering is done by projecting the sites and boundary into the tangent plane centered at the chunk center before checking distance (it could plausibly be replaced by great-circle distance, but this has not yet been investigated). For this reason, chunks must be somewhat smaller than a hemisphere.

Then, we run an iterative relaxation function to enforce uniform point density near the shared edges between chunks. Only points within another, smaller distance from the chunk boundary are moved by the relaxation process, but information from the wider threshold is used.

Each site's relaxed position is recorded. Once all neighbors of a certain chunk have run the relaxation process, that chunk can determine the average relaxed position for each of its sites.

In this way, chunks can agree on relaxed positions without generating the entire polysphere at once.

Stage Three: Voronoi and Culling

We now collect the sites from the current chunk and neighbors again, and filter them to within a certain geodesic distance from the chunk center. We use these sites to generate a geodesic voronoi graph (lying on the surface of the sphere, and using geodesic distance measurements), and cull that graph to only include faces where the centroid of the face lies within the chunk boundary.

The resultant graph is the final geometry for this chunk. Since the input sites agree, and the culling is based on the chunk boundary (consistent between adjacent chunks), the final geometry agrees as well.

Aside: Voronoi Graph Implementation

Our algorithm for generating the geodesic voronoi graph could be described as "brute force sampling", but yields an exact result.

The underlying principle is to quantize the region which the graph will occupy with concentric rings of sample points (on the surface of the sphere), then determine the closest three sites for every sample point (by great-circle distance in this case). We then compare the distances to each of these three sites. If they fall within some "equidistance threshold" of each other, we consider this to be affirmative proof that there exists a vertex of the final graph which is equidistant from those three points.

We collect all such Triads (sets of three site indices), and filter them for uniqueness. The precise location of each vert can determined as the spherical circumcenter of those three sites. We can then collect a list for each site of all triads that include it, sort them by angular position around the site, and consider that edge loop to define a face of the voronoi graph.

We use two stages of triad sampling; a "coarse" pass designed to include false positives but be cheap to perform, and a slew of fine passes that are localized around flagged locations but use a higher sampling resolution. These fine passes are necessary to correctly handle situations where more than three sites are nearly equidistant to each other.

In its current form, this method assumes that no four-way or greater intersections exist, and furthermore that no vertices lie within the fine sampling spacing of each other.

Work Needed

• Investigate need for panic wrappers around the internals of certain FFI functions, including performance tradeoff.
• Implement error catching for the core generation process, tying into the task management system (get_task_error()).
• Restructure to have chunk centers, boundaries, and adjacencies provided by user callbacks; currently hardcoded.
• Expose more configuration details to the user.
• Expose init_for_lod as an FFI function to support multiple LOD levels.
• Investigate performance optimizations.
• Collect performance metrics.
• Collect user feedback.