1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

/*!

This is an implementation of Eric Lengyel's Transvoxel Algorithm in Rust

Credits: Eric Lengyel's Transvoxel Algorithm. https://transvoxel.org/

# Brief description of the problem
When extracting meshes with Marching Cubes for adjacent blocks at different level of detail independently, the meshes generally do not match at the blocks' junctions, inducing visible holes:
![gap-solid](https://gnurfos.github.io/transvoxel_rs/doc-images/gap-solid.png)
![gap-wireframe](https://gnurfos.github.io/transvoxel_rs/doc-images/gap-wireframe.png)
The Transvoxel Algorithm allows generating a mesh for a block *mostly* with marching cubes, but with increased detail on one or several external faces of the block, in order to match with neighbouring blocks' meshes:
![fixed-wireframe](https://gnurfos.github.io/transvoxel_rs/doc-images/fixed-wireframe.png)

Eric Lengyel's [website](https://transvoxel.org/) describes this better and in more details.

# Scope
This library only provides functions for extracting a mesh for a block, independently of other blocks.
To implement a fully consistent dynamic level-of-detail system, you will also probably need to:
 * decide which blocks you need to render and generate meshes for, and at which resolution (typically depending on the camera position and/or orientation)
 * track yourself constraints:
   * two rendered adjacent blocks can only either have the same resolution, or one have double the resolution of the other
   * in that second case, the low resolution block must also be rendered with a transition face in the direction of the high resolution block
Currently, it is not possible to "flip" a transition face status on a block, without re-extracting a new mesh for the block. Which means changing the resolution for one block can cascade through constraints to re-generating a few other blocks as well

# Basic usage
Either try calling one of the functions in [extraction], or follow the example below:
```rust
// The first thing you need is a density provider. You can implement a ScalarField for that
// but a simpler way, if you are just experimenting, is to use a function:
use transvoxel::density::ScalarFieldForFn;

fn sphere_density(x: f32, y: f32, z: f32) -> f32 {
    1f32 - (x * x + y * y + z * z).sqrt() / 5f32
}

let mut field = ScalarFieldForFn(sphere_density);

// Going along with your density function, you need a threshold value for your density:
// This is the value for which the surface will be generated. You can typically choose 0.
// Values over the threshold are considered inside the volume, and values under the threshold
// outside of the volume. In our case, we will have a density of 0 on a sphere centered on the
// world center, of radius 5.
let threshold = 0f32;

// Then you need to decide for which region of the world you want to generate the mesh, and how
// many subdivisions should be used (the "resolution"). You also need to tell which sides of the
// block need to be transition (double-resolution) faces. We use `no_side` here for simplicity,
// and will get just a regular Marching Cubes extraction, but the Transvoxel transitions can be 
// obtained simply by providing some sides instead (that is shown a bit later):
use transvoxel::structs::Block;
use transvoxel::transition_sides::no_side;
let subdivisions = 10;
let block = Block::from([0.0, 0.0, 0.0], 10.0, subdivisions);
let transition_sides = no_side();

// Finally, you can run the mesh extraction:
use transvoxel::extraction::extract_from_field;
let mesh = extract_from_field(&mut field, &block, threshold, transition_sides);
assert!(mesh.tris().len() == 103);

// Extracting with some transition faces results in a slightly more complex mesh:
use transvoxel::transition_sides::TransitionSide::LowX;
let mesh = extract_from_field(&mut field, &block, threshold, LowX.into());
assert!(mesh.tris().len() == 131);

// Unless, of course, the surface does not cross that face:
use transvoxel::transition_sides::TransitionSide::HighZ;
let mesh = extract_from_field(&mut field, &block, threshold, HighZ.into());
assert!(mesh.tris().len() == 103);
```

# How to use the resulting mesh
A mesh for a simple square looks like this:
```ron
Extracted mesh: Mesh {
    positions: [
        10.0,
        5.0,
        0.0,
        0.0,
        5.0,
        0.0,
        0.0,
        5.0,
        10.0,
        10.0,
        5.0,
        10.0,
    ],
    normals: [
        -0.0,
        1.0,
        -0.0,
        -0.0,
        1.0,
        -0.0,
        -0.0,
        1.0,
        -0.0,
        -0.0,
        1.0,
        -0.0,
    ],
    triangle_indices: [
        0,
        1,
        2,
        0,
        2,
        3,
    ],
}
```
It is made of 4 vertices, arranged in 2 triangles.
The first vertex is at position x=10.0, y=5.0, z=0.0 (the first 3 floats in position).
As the first in the list, it's index is 0, and we can see it is used in the 2 triangles
(the first triangle uses vertices 0 1 2, and the second triangle vertices 0 2 3)

If you need to use the mesh in [Bevy](https://bevyengine.org/), you can enable feature `bevy_mesh` and use functions in [bevy_mesh] 

[bevy_mesh]: crate::bevy_mesh

# How to request transition sides
```rust
use transvoxel::transition_sides::{TransitionSide, no_side};

// If you don't hardcode sides like in the example above, you can build a set of sides incrementally:
// They use the FlagSet crate
let mut sides = no_side();
sides |= TransitionSide::LowX;
sides |= TransitionSide::HighY;

assert!(sides.contains(TransitionSide::LowX));
assert!(!sides.contains(TransitionSide::HighX));
```

# Remarks
 * Although they are a data source, the fields are mutable, in case you want to do smart things while generating densities (like your own caching)
 * You should balance the amount of subdivisions and the size of your blocks: too few subdivisions means you will need to produce many smaller blocks and meshes. Too many means you will have big meshes. Also, the algorithm currently fetches several times the density for some voxels during a single extraction, so this might add overhead too.

# Limitations / possible improvements
 * Output/Input positions/normals are only f32. It should be feasible easily to extend that to f64
 * [Density] is limited to [Float] at the moment (only implemented for f32 and could be easily extended to f64). Some thinking would be needed for allowing more types, regarding interactions with gradients and interpolation of coordinates
 * Voxel densities caching is sub-optimal: probably only in the cas of an empty block will densities be queried only once per voxel. In non-empty blocks, densities are very likely to be queried several times for some voxels
 * Algorithm improvements. See [Algorithm]

[Algorithm]: crate::implementation::algorithm
[Density]: crate::density::Density
[Float]: num::Float

*/
#![warn(missing_docs)]
#![allow(private_intra_doc_links)]

#[cfg(test)]
mod unit_tests;

pub mod density;
pub mod extraction;
pub mod structs;
pub mod transition_sides;
pub mod voxel_coordinates;
pub mod voxel_source;

mod implementation;
pub use implementation::algorithm::shrink_if_needed;

#[cfg(feature = "serde")]
#[macro_use]
extern crate serde;

#[cfg(feature = "bevy_mesh")]
#[cfg_attr(docsrs, doc(cfg(feature = "bevy_mesh")))]
pub mod bevy_mesh;