About this blog
This journal is dedicated to my auto formation and my experimentations.
Entries in this blog
Context
I recently started reading the book Artificial Intelligence for Humans, Volume 1: Fundamental Algorithms by Jeff Heaton. Upon finishing reading the chapter Normalizing Data, I decided to practice what I had just learnt to hopefully finally understand 100 % of a special algorithm : equilateral encoding.
Equilateral Encoding
The purpose of this algorithm is to normalize N categories by creating an equilateral triangle of N - 1 dimensions. Each vertex in that triangle is a category and so, because of the properties of the equilateral triangle, it's easy to construct this structure with medians of 1 unit.
For selecting a category, all you need is a location vector of N - 1 dimensions that's ideally inside the equilateral triangle. For example, consider the vertex C and point c. The vertex C is 100% of a specified category, whilst the point c is 0% of that category. The vertices A and B are also 0% of C's category. In other words, the further away a location vector is from a vertex along its median axis, the less it belongs to the vertex`s category. Also, if the mentioned axis distance is greater than the length of a median (all medians have the same length in an equilateral triangle, which is the range of values in this context), then the location vector absolutely does not belong to the specified category.
The reason why we just don't select directly a category is because this algorithm is originally for machine learning. It quantifies qualitative data, shares the blame better and uses less memory than simpler algorithms, as it uses N - 1 dimensions.
The Application
First of, here's the link to my application : https://github.com/thecheeselover/image-recognition-by-equilateral-encoding
How It Works
To be able to know the similarities between two images, a comparison must be done. Using the equilateral encoding algorithm, a pixel versus pixel comparison is the only way to do so and thus shapes do not count towards the similarities between the two images.
What category should we use to compare images? Well, colors of course!
Here are the colors I specified as categories :
Red
Green
Blue
White
Black
The algorithm will select the closest category for each pixel according to the differences between both colors and save it's location vector in an array. Then, when both images are loaded, compare each image pixels against each other by computing the median distance, as mentioned before, between both of them. Simply project the first pixel's vector onto the other one and compute the Euclidean distance to get the median distance.
Sum all computed median distances
This way, it would also works if there were location vectors not totally on a vertex, even though it doesn't happen for the just described comparison algorithm.
Preliminaries
Of course, this can be really slow for immense images. Downscale the images to have a maximum width and height, 32 pixels in my case. Also, remove the transparency as it is not a color component in itself.
If both images do not have the same aspect ratio and so not the same downscaled dimensions, then consider using extremely different location vectors and so just different categories for "empty" pixels against non-empty pixels.
The Code
The equilateral encoding table :
package org.benoitdubreuil.iree.model;
import org.benoitdubreuil.iree.utils.MathUtils;
/**
* The image data for the image recognition by equilateral encoding.
* <p>
* See the author Jeff Heaton of this algorithm and his book that contains everything about it :
* <a href="https://www.heatonresearch.com/book/aifh-vol1-fundamental.html">Artificial Intelligence for Humans, Vol 1: Fundamental Algorithms</a>
* <p>
* The base source code for the equilateral encoding algorithm :
* <a href="https://github.com/jeffheaton/aifh/blob/master/vol1/java-examples/src/main/java/com/heatonresearch/aifh/normalize/Equilateral.java">Equilateral.java</a>
*/
public class EquilateralEncodingTable {
// The algorithm with only one category does not make sense
private static final int MIN_CATEGORIES_FOR_ENCODING = 2;
private int m_categoryCount;
private int m_dimensionCount;
private double m_lowestValue;
private double m_highestValue;
private double m_valueRange;
private double[][] m_categoriesCoordinates;
public EquilateralEncodingTable(int categoryCount, double lowestValue, double highestValue) {
if (categoryCount < MIN_CATEGORIES_FOR_ENCODING) {
throw new ArrayIndexOutOfBoundsException("Not enough categories for equilateral encoding");
}
this.m_categoryCount = categoryCount;
this.m_dimensionCount = computeDimensionCount(categoryCount);
this.m_lowestValue = lowestValue;
this.m_highestValue = highestValue;
this.m_valueRange = highestValue - lowestValue;
this.m_categoriesCoordinates = computeEquilateralEncodingTable();
}
/**
* Encodes a supplied index and gets the equilaterally encoded coordinates at that index.
*
* @param equilateralCoordsIndex The index at which the equilaterally encoded coordinates are.
*
* @return The equilaterally encoded coordinates.
*/
public double[] encode(int equilateralCoordsIndex) {
return m_categoriesCoordinates[equilateralCoordsIndex];
}
/**
* Decodes the supplied coordinates by finding its closest equilaterally encoded coordinates.
*
* @param coordinates The coordinates that need to be decoded. It should not be equilateral it doesn't matter, as the goal is simply to find the closest equilaterally encoded
* coordinates.
*
* @return The index at which the closest equilaterally encoded coordinates are.
*/
public int decode(double[] coordinates) {
double closestDistance = Double.POSITIVE_INFINITY;
int closestEquilateralCoordsIndex = -1;
for (int i = 0; i < m_categoriesCoordinates.length; ++i) {
double dist = computeDistance(coordinates, i);
if (dist < closestDistance) {
closestDistance = dist;
closestEquilateralCoordsIndex = i;
}
}
return closestEquilateralCoordsIndex;
}
/**
* Computes the Euclidean distance between the supplied coordinates and the equilaterally encoded coordinates at the supplied index.
*
* @param coordinates Coordinates of the first n-dimensional vector.
* @param equilateralCoordsIndex Index for the equilaterally encoded coordinates.
*
* @return The Euclidean distance between the two vectors.
*/
public double computeDistance(double[] coordinates, int equilateralCoordsIndex) {
return MathUtils.computeDistance(coordinates, m_categoriesCoordinates[equilateralCoordsIndex]);
}
/**
* Computes the equilateral encoding table, which is used as a look up for table for the data.
*
* @return The equilateral encoding table.
*/
private double[][] computeEquilateralEncodingTable() {
double negativeReciprocalOfN;
double scalingFactor;
final double[][] matrix = new double[m_categoryCount][m_dimensionCount];
matrix[0][0] = -1;
matrix[1][0] = 1.0;
if (m_categoryCount > 2) {
for (int dimension = 2; dimension < m_categoryCount; ++dimension) {
// scale the matrix so far
scalingFactor = dimension;
negativeReciprocalOfN = Math.sqrt(scalingFactor * scalingFactor - 1.0) / scalingFactor;
for (int coordinate = 0; coordinate < dimension; ++coordinate) {
for (int oldDimension = 0; oldDimension < dimension - 1; ++oldDimension) {
matrix[coordinate][oldDimension] *= negativeReciprocalOfN;
}
}
scalingFactor = -1.0 / scalingFactor;
for (int coordinate = 0; coordinate < dimension; ++coordinate) {
matrix[coordinate][dimension - 1] = scalingFactor;
}
for (int coordinate = 0; coordinate < dimension - 1; ++coordinate) {
matrix[dimension][coordinate] = 0.0;
}
matrix[dimension][dimension - 1] = 1.0;
// Scale the matrix
for (int row = 0; row < matrix.length; ++row) {
for (int col = 0; col < matrix[0].length; ++col) {
double min = -1;
double max = 1;
matrix[row][col] = ((matrix[row][col] - min) / (max - min)) * m_valueRange + m_lowestValue;
}
}
}
}
return matrix;
}
public static int computeDimensionCount(int categoryCount) {
return categoryCount - 1;
}
public int getCategoryCount() {
return m_categoryCount;
}
public int getDimensionCount() {
return m_dimensionCount;
}
public double getLowestValue() {
return m_lowestValue;
}
public double getHighestValue() {
return m_highestValue;
}
public double getValueRange() {
return m_valueRange;
}
public double[][] getCategoriesCoordinates() {
return m_categoriesCoordinates;
}
}
The mathematics utilities :
package org.benoitdubreuil.iree.utils;
public final class MathUtils {
/**
* Computes the Euclidean distance between the supplied vectors.
*
* @param lhsCoordinates Coordinates of the first n-dimensional vector.
* @param rhsCoordinates Coordinates of the second n-dimensional vector.
*
* @return The Euclidean distance between the two vectors.
*/
public static double computeDistance(double[] lhsCoordinates, double[] rhsCoordinates) {
double result = 0;
for (int i = 0; i < rhsCoordinates.length; ++i) {
result += Math.pow(lhsCoordinates[i] - rhsCoordinates[i], 2);
}
return Math.sqrt(result);
}
/**
* Normalizes the supplied vector.
*
* @param vector The vector to normalize.
*
* @return The same array, but normalized.
*/
public static double[] normalizeVector(double[] vector) {
double squaredLength = 0;
for (int dimension = 0; dimension < vector.length; ++dimension) {
squaredLength += vector[dimension] * vector[dimension];
}
if (squaredLength != 1.0 && squaredLength != 0.0) {
double reciprocalLength = 1.0 / Math.sqrt(squaredLength);
for (int dimension = 0; dimension < vector.length; ++dimension) {
vector[dimension] *= reciprocalLength;
}
}
return vector;
}
/**
* Negates the vector.
*
* @param vector The vector to negate.
*
* @return The same array, but each coordinate negated.
*/
public static double[] negateVector(double[] vector) {
for (int dimension = 0; dimension < vector.length; ++dimension) {
vector[dimension] = -vector[dimension];
}
return vector;
}
/**
* Multiplies the vector by a scalar.
*
* @param vector The vector to multiply.
* @param scalar The scalar by which to multiply the vector.
*
* @return The same array, but each coordinate multiplied by the scalar.
*/
public static double[] multVector(double[] vector, double scalar) {
for (int dimension = 0; dimension < vector.length; ++dimension) {
vector[dimension] *= scalar;
}
return vector;
}
/**
* Computes the dot product of the two supplied points.
*
* @param lhsVector The first point.
* @param rhsVector The second point.
*
* @return The dot product of the two points.
*/
public static double dotProductVector(double[] lhsVector, double[] rhsVector) {
double dotResult = 0;
for (int dimension = 0; dimension < lhsVector.length; ++dimension) {
dotResult += lhsVector[dimension] * rhsVector[dimension];
}
return dotResult;
}
private MathUtils() {
}
}
The image data that shows how to encode pixels :
package org.benoitdubreuil.iree.model;
import org.benoitdubreuil.iree.controller.ControllerIREE;
import org.benoitdubreuil.iree.gui.ImageGUIData;
import org.benoitdubreuil.iree.pattern.observer.IObserver;
import org.benoitdubreuil.iree.pattern.observer.Observable;
import java.awt.*;
import java.awt.image.BufferedImage;
public class ImageData extends Observable<ImageData> implements IObserver<ImageGUIData> {
private double[][] m_encodedPixelData;
/**
* Encodes the pixel data of the supplied image data.
*
* @param newValue The new value of the observed.
*/
@Override
public void observableChanged(ImageGUIData newValue) {
if (newValue.getDownScaled() != null) {
encodePixelData(newValue);
modelChanged(this);
}
}
private void encodePixelData(ImageGUIData imageGUIData) {
EquilateralEncodingTable encodingTable = ControllerIREE.getInstance().getEncodingTable();
EquilateralEncodingCategory[] categories = EquilateralEncodingCategory.values();
BufferedImage image = imageGUIData.getDownScaled();
int width = image.getWidth();
int height = image.getHeight();
m_encodedPixelData = new double[width * height][];
for (int x = 0; x < width; ++x) {
for (int y = 0; y < height; ++y) {
int orignalPixel = image.getRGB(x, height - 1 - y);
int r = (orignalPixel >> 16) & 0xff;
int g = (orignalPixel >> 8) & 0xff;
int b = orignalPixel & 0xff;
int minColorDistance = 255 * 3;
int minColorDistanceCategory = 0;
for (int category = 0; category < encodingTable.getCategoryCount(); ++category) {
Color categoryColor = categories[category].getColor();
int colorDistance = Math.abs(r - categoryColor.getRed()) + Math.abs(g - categoryColor.getGreen()) + Math.abs(b - categoryColor.getBlue());
if (colorDistance < minColorDistance) {
minColorDistance = colorDistance;
minColorDistanceCategory = category;
}
}
m_encodedPixelData[x * height + y] = encodingTable.encode(minColorDistanceCategory).clone();
}
}
}
public int getPixelCount() {
return m_encodedPixelData.length;
}
double[][] getEncodedPixelData() {
return m_encodedPixelData;
}
}
The actual image data recognition algorithm :
package org.benoitdubreuil.iree.model;
import org.benoitdubreuil.iree.controller.ControllerIREE;
import org.benoitdubreuil.iree.utils.MathUtils;
public final class ImageDataRecognition {
/**
* Compares two images and return how similar they are.
*
* @param lhs The first image to compare.
* @param rhs The second image to compare.
*
* @return Inclusively from 0, totally different, to 1, the same.
*/
public static double compareImages(ImageData lhs, ImageData rhs) {
double meanDistance = 0;
double[][] lhsEncodedPixelData = lhs.getEncodedPixelData();
double[][] rhsEncodedPixelData = rhs.getEncodedPixelData();
if (lhsEncodedPixelData != null && rhsEncodedPixelData != null) {
EquilateralEncodingTable table = ControllerIREE.getInstance().getEncodingTable();
int maxPixelCount = Math.max(lhs.getPixelCount(), rhs.getPixelCount());
double emptyPixelMeanValue = 1.0;
for (int pixel = 0; pixel < maxPixelCount; ++pixel) {
double[] lhsVector;
double[] rhsVector;
if (pixel < lhs.getPixelCount()) {
lhsVector = lhsEncodedPixelData[pixel];
}
else {
meanDistance += emptyPixelMeanValue;
continue;
}
if (pixel < rhs.getPixelCount()) {
rhsVector = rhsEncodedPixelData[pixel];
}
else {
meanDistance += emptyPixelMeanValue;
continue;
}
double rhsDotLhs = MathUtils.dotProductVector(rhsVector, lhsVector);
double[] rhsProjectedOntoLhs = MathUtils.multVector(lhsVector.clone(), rhsDotLhs);
meanDistance += MathUtils.computeDistance(lhsVector, rhsProjectedOntoLhs) / table.getValueRange() / maxPixelCount;
}
}
return meanDistance;
}
private ImageDataRecognition() {
}
}
Subscribe to our subreddit to get all the updates from the team!
Introduction
In our 3D game (miimii1205), we use a dynamically created navigation mesh to navigate onto a procedurally generated terrain. To do so, only the A* and string pulling algorithms were more specifically used until our last agile sprint. We recently added two new behaviors to the pathfinding : steering and wall collision avoidance. In this article, I will describe how I achieved a simple way for agents to not walk into walls.
Configuration
3D or 2D navigation mesh, as long as the 3D one is not cyclic.
Navigation cells and their : polygonal edges, connections (other cell), shared edges (the line intersecting between two connected cells), centroids and normals.
An A* and string pulled (not tested without string pulling) generated path consisting of waypoints on the navigation mesh.
The Algorithm
The agent is the pink low-poly humanoid and the final destination is the flag.
The ideal algorithm (yet unoptimized) would be to cast an oriented rectangle between each consecutive waypoint where its width is the two times the radius. Think of the agent's center position being in the middle of the width. Anyway, this algorithm is too complicated, too long to develop for our game, too big for nothing and so I thought about another algorithm, which has its drawbacks actually. However, it's more suited for our game.
Psss, check this article if you haven't seen it yet.
The algorithm is the following :
For each waypoint, pick the current one and the next one until the next one is the last.
Iterate over the current navigation cell's edges, which is defined by the agent's 3D position. To do that, you need a spatial and optimized way to determine the closest cell of a 3D point. Our way to do it is to first have have an octree to partition the navigation mesh. After that, get all the cells that are close to the point plus an extra buffer. To find the cell that is the closest to the point, for each picked cell, cast a projection of the position onto each one of them. This can be done using their centroids and normals. Don't forget to snap the projected position onto the cell. After, that compute the length of the resulting vector and pick the smallest one.
Convert each edge to a 2D line by discarding the Y component (UP vector).
For each side left and right, which are defined by the agent's position and direction towards the next waypoint, cast a 2D line that start from the agent's position, that goes towards one of the two perpendicular directions related to the direction to the next waypoint and that has a length of the defined radius.
If there's an intersection on a connection and that it's on the shared part of the connection, then continue with the connected cell's edges.
If there are any intersections other than #5, create a new waypoint before the next waypoint. This new one's position is defined by the intersection's position translated by a length of two times the radius and projected towards the agent's current direction as a 2D line. The same translation is applied to the next waypoint.
Cast two 2D lines, one on each side of the agent as described before, starting from the sides, going towards the same direction as the agent and of the same length between the current and next waypoint. Check for #5. If there is an intersection on a connection and that it's on the unshared part of the connection, then do #6 (no if). If there's an intersection on a simple edge, then translate the next waypoint as described in #6.
Here's a video of the algorithm in action :
Subscribe to our subreddit to get all the updates from the team!
Last month, I made a pretty simple dungeon generator algorithm. It's an organic brute force algorithm, in the sense that the rooms and corridors aren't carved into a grid and that it stops when an area doesn't fit in the graph.
Here's the algorithm :
Start from the center (0, 0) in 2D
Generate a room
Choose a side to extend to
Attach a corridor to that side
If it doesn't fit, stop the generation
Attach a room at the end of the corridor
If it doesn't fit, stop the generation
Repeat from steps 3 to 7 until enough rooms are generated
It allowed us to test out our pathfinding algorithm (A* & String pulling).
Here are some pictures of the output in 2D and 3D :
Subscribe to our subreddit to get all the updates from the team!
First off, here's a video that shows the unit vision in action :
So, what is the unit vision? It's a simple mechanism that notifies a unit when another unit enters its vision field. It also takes into account if the vision is blocked by entities.
This is how it is implemented step by step :
A cone ghost control is attached to the unit's head
All units intersecting with the cone's AABB fire events (AABB because of how Bullet Physics work)
Cast a ray towards the visible unit and then adjust the angle so that it fits in the cone
If the ray cast touches the supposedly visible unit, then it is truly visible
Using the debug view of Bullet Physics in the jMonkey Engine 3.1, we're able to see what the vision cone actually looks like.
And when inside the cone we can't see it because of culling. However, we can see the enemy's arm moving, which is a test I did for when a unit see another unit.
Behind a box, the enemy does not move its arm because he can't see me.
But when I leave my hiding spot, he can see me again.
Subscribe to our subreddit to get all the updates from the team!
I have integrated the zone separation with my implementation of the Marching Cubes algorithm. Now I have been working on zone generation.
A level is separated in the following way :
Shrink the zone map to exactly fit an integer number of Chunk2Ds, which are of 32² m².
For each Chunk2D, analyse all zones inside its boundaries and determine all possible heights for Chunk3Ds, which are of 32³ m³. Imagine this as a three dimensional array as an hash map : we are trying to figure out all keys for Chunk3Ds for a given Chunk2D.
Create and generate a Chunk3D for each height found.
Execute the Marching Cubes algorithm to assemble the geometry for each Chunk3D.
In our game, we want levels to look like and feel like a certain world. The first world we are creating is the savanna. Even though each Chunk3D is generated using 3D noise, I made a noise module to map 3D noises into the 2D to able to apply 2D perturbation to the terrain.
I also tried some funkier procedural noises :
An arch!
The important thing with procedural generation, it's to have a certain level of control over it. With the new zone division system, I have achieved a minimum on that path for my game.
Subscribe to our subreddit to get all the updates from the team!
A friend and I are making a rogue-lite retro procedural game. As in many procedural rogue-lite games, it will have rooms to complete but also the notion of zones. The difference between a zone and a room is that a zone is open air whilst a room is not. Rooms are connected mainly by corridors while zones are mostly naturally connected / separated by rivers and mountains.
Because we want levels with zones to be generated, we need to tame the beast that is procedural generation. How can we generate each zone itself and also clearly divide them? Until now, I had only been using the Java noise library called Joise, which is the Java community port of JTippetts' Accidental Noise Library. I needed the zone data to be generated with basis function modules, i.e. Perlin noise, but in contrast I needed a more structured approach for the zone division. Joise library does have a cell noise module that is a Worley noise. It looks like this depending on its 4 parameters (1, 0, 0, 0) :
Using math modules, I was able to morph that noise into something that looks like a Voronoi diagram. Here's what a Voronoi diagram should look like (never mind the colors, the important parts are the cell edges and the cell centers) :
A more aesthetic version :
The Worley noise that I had morphed into a Voronoi-like diagram did not include the cell centers, did not include metadata about the edges and was not enough deterministic in a sense that sometimes, the edges would around 60 pixels large. I then searched for a Java Voronoi library and found this one called Voronoi-Java. With this, I was able to generate simple Voronoi diagrams :
Relaxed : 1 iteration
Relaxed : 2 iterations
The relaxation concept is actually the Lloyd's algorithm fortunately included within the library.
Now how can I make that diagram respect my level generation mechanics? Well, if we can limit an approximated number of cells within a certain resolution, that would be a good start. The biggest problem here, is that the relaxation reduces the number of cells within a restricted resolution (contrary to the global resolution) and so we need to keep that in mind.
To do that, I define a constant for the total number of sites / cells. Here's my code :
private Voronoi createVoronoiDiagram(int resolution) {
Random random = new Random();
Stream<Point> gen = Stream.generate(() -> new Point(random.nextDouble() * resolution, random.nextDouble() * resolution));
return new Voronoi(gen.limit(VORONOI_SITE_COUNT).collect(Collectors.toList())).relax().relax().relax();
}
A brief pseudo-code of the algorithm would be the following :
Create the Voronoi diagram
Find the centermost zone
Selects X number of zones while there are zones that respect the selection criteria
Draw the border map
Draw the smoothed border map
The selection criteria is applied for each edge that is connected only to one selected zone. Here's the selection criteria :
Is connected to a closed zone, i.e. that all its edges form a polygon
Does have two vertices
Is inclusively in the resolution's boundaries
Here's the result of a drawn border map!
In this graph, I have a restricted number of cells that follow multiple criteria and I know each edge and each cell center point.
To draw the smoothed border map, the following actions must be taken : emit colors from already drawn pixels and then apply a gaussian blur. Personally, I use the JH Labs Java Image Filters library for the gaussian blur.
With color emission only :
With color emission and a gaussian blur :
You may ask yourself why have we created a smoothed border map? There's a simple reason for this, which is that we want the borders to be gradual instead of abrupt. Let's say we want rivers or streams between zones. This gradual border will allow us to progressively increase the depth of the river and making it look more natural in contrast with the adjacent zones.
All that's left is to flood each selected cell and apply that to a zone map.
Subscribe to our subreddit to get all the updates from the team!
Recently I've been tackling with more organic low poly terrains. The default way of creating indices for a 3D geometry is the following (credits) :
A way to create simple differences that makes the geometry slightly more complicated and thus more organic is to vertically swap the indices of each adjacent quad. In other words, each adjacent quad to a centered quad is its vertical mirror.
Finally, by not sharing the vertices and hence by creating two triangles per quad, this is the result with a coherent noise generator (joise) :
It is called flat shading.
I integrated LibGDX's Behavior Tree AI module into our roguelite, vaporwave and procedural game, which is made use the jMonkey Engine 3.1.
I then created the following behavior :
- Follow enemy
- Search the enemy's last recorded position
- Return back to initial chase position
- Stop the chase after a certain amount of time
- Attacking the enemy resets the timer
Here's the behavior tree logic. Beware that it's possible there are still bugs.
subtree name:"notIsReturningToInitialChasePosition"
invert
isReturningToInitialChasePosition
subtree name:"notIsMovingToFollowingEnemyLastPosition"
invert
isMovingToFollowingEnemyLastPosition
subtree name:"notHaveSpottedEnemies"
invert
haveSpottedEnemies
subtree name:"followEnemy"
selector
parallel
lookOutForEnemies
alwaysSucceed
lookAtClosestSeenEnemy
alwaysSucceed
(isPlayingAnimation animation:"look_around") stopAnimation animation:"look_around"
followClosestSeenEnemy
parallel policy:"selector"
alwaysFail
wait seconds:10
attackClosestSeenEnemy
root
selector
$followEnemy
(isFollowingEnemyAlive) (knowFollowingEnemyLastPosition) ($notHaveSpottedEnemies) sequence
resetLookAt
moveToFollowingEnemyLastPosition
parallel policy:"selector"
alwaysFail
playAnimation animation:"look_around"
lookOutForEnemies
alwaysFail
resetLookAt
returnToInitialChasePosition
I'm new to AI programming and still have a lot of work to do for making better behavior trees. I think it's really easy to make spaghetti behaviors. Do you have any tutorials on how to create a "good" behavior tree?
Today, I finally finished the following features :
Add new solid voxels at the selected position
Destroy voxels at the selected position
Generate chunks on the fly
Remove chunks on the fly
Here is a video demonstrating those features :
For more information and updates about the game, which is a voxel colony simulation / survival, please subscribe to r/CheesyGames.
World Generation
This is a simple world made of chunks of 32³ voxels. The world itself is not static : as you can see on the top of the image, chunks only exist if there is at least one solid voxel in them. In other words, the world is dynamic and can contain as many chunks as the player's computer can handle.
In this particular screenshot, the world is generated with the simple vectorial gradient equation that I invented in high school but which I suppose already existed. Here's the basic equation :
\(\overrightarrow{ \textit{voxel value} } = \frac{ \overrightarrow{\textit{position} } \cdot \overrightarrow{ \textit{gradient}}}{ \overrightarrow{\textit{gradient} } \cdot \overrightarrow{ \textit{gradient}} }\)
That's the equation I came up with and remembered. The gradient * gradient can be simplified for the magnitude (length) of the gradient power squared.
\(\overrightarrow{ \textit{voxel value} } = \frac{ \overrightarrow{\textit{position} } \cdot \overrightarrow{ \textit{gradient}}}{ \left \| \overrightarrow{ \textit{gradient}} \right \| ^{2} }\)
In conclusion, this gives an N dimensional gradient which gives a single decimal number.
Voxel Traversal Algorithm
As for the voxel traversal algorithm, I decided to go with the most popular one, which was made by John Amanatides and Andrew Woo. As much as I like research papers, I also despise them because they lack simplicity, examples and full source code. That's why I had to google implementations of it and later on remembered that I had actually already implemented this algorithm a few years ago.
Summary
The simplest way to understand the algorithm is to imagine a line in an 3D world made of blocks. Which blocks does the line touch? Then, in which order are they touched based on the line's start and end positions? The goal is to traverse iteratively the blocks that are touched by the line .
More simply, the logic of the algorithm can be summed making a distinction between the ray's direction's components. Those three define the importance of their axes in terms of how many blocks need to be traversed in what direction. Think of this with integers : two people are running to reach a goal; the fastest runs a 5 km/h, while the slowest runs at 1 km/h. For each time step, i.e. an hour, how many kilometers have each runner traveled? The ratio is 5 : 1, so, to merge the analogy, a ray would traverse each step 5 blocks on the X axis and 1 block on the Y axis. Of course, it's more complicated than that, as there are more parameters to it, especially because of exceptions such as what to do when each component is equal with one another?
Implementation
The first thing to know about my implementation is that each voxel index is centered within the voxel itself. In other words, the voxel at the position (0, 0, 0) starts at (-0.5, -0.5, -0.5) inclusively and ends at (0.5, 0.5, 0.5) exclusively. This is for a cube extent of 1, naturally. The original research paper doesn't work that way as it starts at the lowest corner, i.e. the voxel spans from (0, 0, 0) to (1, 1, 1). Without any further delay, here is the class for the VoxelRay :
import com.cheesygames.colonysimulation.math.MathExt;
import com.cheesygames.colonysimulation.math.vector.Vector3i;
import com.cheesygames.colonysimulation.world.World;
import com.jme3.math.Vector3f;
import com.jme3.scene.plugins.blender.math.Vector3d;
import java.util.function.Function;
/**
* Ray for ray casting inside a voxel world. Each voxel is considered as a cube within this ray. A ray consists of a starting position, a direction and a length. The voxel distance
* is computed once the method {@link #rayCastLocal(double, Function, Vector3i)} or {@link #rayCast(double, Function)} is called.
*/
public class VoxelRay {
private Vector3d m_start;
private Vector3d m_offsettedStart;
private Vector3d m_direction;
private double m_length;
private int m_voxelDistance;
private boolean m_wasStopped;
/**
* Constructs an invalid {@link VoxelRay} as its direction and length are null. The setters must be called after constructing a {@link VoxelRay} with this constructors.
*/
public VoxelRay() {
this.m_start = new Vector3d();
this.m_offsettedStart = new Vector3d();
this.m_direction = new Vector3d();
this.m_length = 0;
}
/**
* Constructs a {@link VoxelRay} from two points : start and end.
*
* @param start The absolute starting position of the ray.
* @param end The absolute ending position of the ray.
*/
public VoxelRay(Vector3d start, Vector3d end) {
this.m_start = new Vector3d(start);
this.m_offsettedStart = new Vector3d();
this.m_direction = end.subtract(start);
this.m_length = m_direction.length();
this.m_direction.normalizeLocal();
}
/**
* Constructs a {@link VoxelRay} from two points : start and end.
*
* @param start The absolute starting position of the ray.
* @param end The absolute ending position of the ray.
*/
public VoxelRay(Vector3f start, Vector3f end) {
this.m_start = new Vector3d(start);
this.m_offsettedStart = new Vector3d();
this.m_direction = new Vector3d(end).subtractLocal(m_start);
this.m_length = m_direction.length();
this.m_direction.normalizeLocal();
}
/**
* Constructs a {@link VoxelRay} from a start, a direction and a length.
*
* @param start The absolute starting position of the ray.
* @param direction The direction of the ray. Must be normalized.
* @param length The length of the ray.
*/
public VoxelRay(Vector3d start, Vector3d direction, double length) {
this.m_start = new Vector3d(start);
this.m_offsettedStart = new Vector3d();
this.m_direction = new Vector3d(direction);
this.m_length = length;
}
/**
* Constructs a {@link VoxelRay} from a start, a direction and a length.
*
* @param start The absolute starting position of the ray.
* @param direction The direction of the ray. Must be normalized.
* @param length The length of the ray.
*/
public VoxelRay(Vector3f start, Vector3f direction, float length) {
this.m_start = new Vector3d(start);
this.m_offsettedStart = new Vector3d();
this.m_direction = new Vector3d(direction);
this.m_length = length;
}
/**
* Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed.
* This allows the lambda to stop anytime the algorithm to continue its loop.
*
* @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The
* supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if
* the algorithm should stop.
*
* @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a>
*/
public void rayCast(Function<Vector3i, Boolean> onTraversingVoxel) {
rayCastLocal(World.VOXEL_HALF_EXTENT, onTraversingVoxel, new Vector3i());
}
/**
* Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed.
* This allows the lambda to stop anytime the algorithm to continue its loop.
*
* @param voxelHalfExtent The half extent (radius) of a voxel.
* @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The
* supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if
* the algorithm should stop.
*
* @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a>
*/
public void rayCast(double voxelHalfExtent, Function<Vector3i, Boolean> onTraversingVoxel) {
rayCastLocal(voxelHalfExtent, onTraversingVoxel, new Vector3i());
}
/**
* Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed.
* This allows the lambda to stop anytime the algorithm to continue its loop.
* <p>
* This method is local because the parameter voxelIndex is locally changed to avoid creating a new instance of {@link Vector3i}.
*
* @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The
* supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if
* the algorithm should stop.
* @param voxelIndex The voxel index to locally modify in order to traverse voxels. This parameter exists simply to avoid creating a new {@link Vector3i} instance.
*
* @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a>
*/
public void rayCastLocal(Function<Vector3i, Boolean> onTraversingVoxel, Vector3i voxelIndex) {
rayCastLocal(World.VOXEL_HALF_EXTENT, onTraversingVoxel, voxelIndex);
}
/**
* Casts the ray from its starting position towards its direction whilst keeping in mind its length. A lambda parameter is supplied and called each time a voxel is traversed.
* This allows the lambda to stop anytime the algorithm to continue its loop.
* <p>
* This method is local because the parameter voxelIndex is locally changed to avoid creating a new instance of {@link Vector3i}.
*
* @param voxelHalfExtent The half extent (radius) of a voxel.
* @param onTraversingVoxel The operation to execute when traversing a voxel. This method called the same number of times as the value of {@link #getVoxelDistance()}. The
* supplied {@link Vector3i} parameter is not a new instance but a local instance, so it is a reference. The return value {@link Boolean} defines if
* the algorithm should stop.
* @param voxelIndex The voxel index to locally modify in order to traverse voxels. This parameter exists simply to avoid creating a new {@link Vector3i} instance.
*
* @see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf">A Fast Voxel Traversal Algorithm</a>
*/
public void rayCastLocal(double voxelHalfExtent, Function<Vector3i, Boolean> onTraversingVoxel, Vector3i voxelIndex) {
assert !Double.isNaN(voxelHalfExtent);
assert !Double.isNaN(m_start.x);
assert !Double.isNaN(m_start.y);
assert !Double.isNaN(m_start.z);
assert !Double.isNaN(m_direction.x);
assert !Double.isNaN(m_direction.y);
assert !Double.isNaN(m_direction.z);
assert !Double.isNaN(m_length);
m_wasStopped = false;
final double voxelExtent = voxelHalfExtent * 2;
// This id of the first/current voxel hit by the ray.
m_offsettedStart.set(m_start).addLocal(voxelHalfExtent, voxelHalfExtent, voxelHalfExtent);
VoxelWorldUtils.getVoxelIndexNoOffsetLocal(voxelExtent, m_offsettedStart, voxelIndex);
computeVoxelDistance(voxelExtent, voxelIndex);
assert !Double.isNaN(m_voxelDistance);
// In which direction the voxel ids are incremented.
int stepX = (int) MathExt.getSignZeroPositive(m_direction.x);
int stepY = (int) MathExt.getSignZeroPositive(m_direction.y);
int stepZ = (int) MathExt.getSignZeroPositive(m_direction.z);
// Distance along the ray to the next voxel border from the current position (tMaxX, tMaxY, tMaxZ).
double nextVoxelBoundaryX = (voxelIndex.x + (MathExt.getNegativeSign(stepX) + 1)) * voxelExtent;
double nextVoxelBoundaryY = (voxelIndex.y + (MathExt.getNegativeSign(stepY) + 1)) * voxelExtent;
double nextVoxelBoundaryZ = (voxelIndex.z + (MathExt.getNegativeSign(stepZ) + 1)) * voxelExtent;
// tMaxX, tMaxY, tMaxZ -- distance until next intersection with voxel-border
// the value of t at which the ray crosses the first vertical voxel boundary
double tMaxX = (m_direction.x != 0) ? (nextVoxelBoundaryX - m_offsettedStart.x) / m_direction.x : Double.MAX_VALUE;
double tMaxY = (m_direction.y != 0) ? (nextVoxelBoundaryY - m_offsettedStart.y) / m_direction.y : Double.MAX_VALUE;
double tMaxZ = (m_direction.z != 0) ? (nextVoxelBoundaryZ - m_offsettedStart.z) / m_direction.z : Double.MAX_VALUE;
// tDeltaX, tDeltaY, tDeltaZ --
// how far along the ray we must move for the horizontal component to equal the width of a voxel
// the direction in which we traverse the grid
// can only be FLT_MAX if we never go in that direction
double tDeltaX = (m_direction.x != 0) ? stepX * voxelExtent / m_direction.x : Double.MAX_VALUE;
double tDeltaY = (m_direction.y != 0) ? stepY * voxelExtent / m_direction.y : Double.MAX_VALUE;
double tDeltaZ = (m_direction.z != 0) ? stepZ * voxelExtent / m_direction.z : Double.MAX_VALUE;
if (onTraversingVoxel.apply(voxelIndex)) {
m_wasStopped = true;
return;
}
int traversedVoxelCount = 0;
while (++traversedVoxelCount < m_voxelDistance) {
if (tMaxX < tMaxY && tMaxX < tMaxZ) {
voxelIndex.x += stepX;
tMaxX += tDeltaX;
}
else if (tMaxY < tMaxZ) {
voxelIndex.y += stepY;
tMaxY += tDeltaY;
}
else {
voxelIndex.z += stepZ;
tMaxZ += tDeltaZ;
}
if (onTraversingVoxel.apply(voxelIndex)) {
m_wasStopped = true;
break;
}
}
}
/**
* Computes the voxel distance, a.k.a. the number of voxel to traverse, for the ray cast.
*
* @param voxelExtent The extent of a voxel, which is the equivalent for a cube of a sphere's radius.
* @param startIndex The starting position's index.
*/
private void computeVoxelDistance(double voxelExtent, Vector3i startIndex) {
m_voxelDistance = 1 +
MathExt.abs(VoxelWorldUtils.getVoxelIndexNoOffset(voxelExtent, m_offsettedStart.x + m_direction.x * m_length) - startIndex.x) +
MathExt.abs(VoxelWorldUtils.getVoxelIndexNoOffset(voxelExtent, m_offsettedStart.y + m_direction.y * m_length) - startIndex.y) +
MathExt.abs(VoxelWorldUtils.getVoxelIndexNoOffset(voxelExtent, m_offsettedStart.z + m_direction.z * m_length) - startIndex.z);
}
public Vector3d getStart() {
return m_start;
}
public Vector3d getDirection() {
return m_direction;
}
public double getLength() {
return m_length;
}
public int getVoxelDistance() {
return m_voxelDistance;
}
public void setStart(Vector3d start) {
m_start.set(start);
}
public void setStart(Vector3f start) {
m_start.set(start);
}
/**
* Sets the direction.
*
* @param direction The direction to set to the ray. Must be normalized.
*/
public void setDirection(Vector3d direction) {
m_direction.set(direction);
}
/**
* Sets the direction.
*
* @param direction The direction to set to the ray. Must be normalized.
*/
public void setDirection(Vector3f direction) {
m_direction.set(direction);
}
/**
* Sets the length of the ray.
*
* @param length The new length of the ray. Must be positive.
*/
public void setLength(double length) {
m_length = length;
}
/**
* Sets the end position of the ray, which is not a real variable but a way to set the direction and the length at the same time. The start position does matter for this
* method.
*
* @param end Where the ray ends.
*/
public void setEnd(Vector3d end) {
m_direction.set(end).subtractLocal(m_start);
m_length = m_direction.length();
m_direction.normalizeLocal();
}
/**
* Gets if the voxel ray cast was stopped by the "onTraversingVoxel" method call.
*
* @return True if the voxel ray cast was stopped by the "onTraversingVoxel" method call, false otherwise.
*/
public boolean wasStopped() {
return m_wasStopped;
}
}
Here are the external static methods :
/**
* Gets the voxel index of the specified position. This method suppose that the parameter position is already offsetted with + voxel half extent. This method local because the
* supplied voxel index will be locally modified and returned.
*
* @param voxelExtent The extent of a voxel, which is the equivalent to a cube of a sphere's diameter.
* @param position The position to get the voxel index from. Must already be offsetted with + voxel half extent
* @param voxelIndex Where to store the voxel index.
*
* @return The voxel index parameter that is set to the supplied position's voxel index.
*/
public static Vector3i getVoxelIndexNoOffsetLocal(double voxelExtent, Vector3d position, Vector3i voxelIndex) {
return voxelIndex.set(getVoxelIndexNoOffset(voxelExtent, position.x), getVoxelIndexNoOffset(voxelExtent, position.y), getVoxelIndexNoOffset(voxelExtent, position.z));
}
/**
* Gets the sign of the supplied number. The method being "zero position" means that the sign of zero is 1.
*
* @param number The number to get the sign from.
*
* @return The number's sign.
*/
public static long getSignZeroPositive(double number) {
assert !Double.isNaN(number);
return getNegativeSign(number) | 1;
}
/**
* Gets the negative sign of the supplied number. So, in other words, if the number is negative, -1 is returned but if the number is positive or zero, then zero is returned. It
* does not check if the parameter is NaN.
*
* @param number The number to get its negative sign.
*
* @return -1 if the number is negative, 0 otherwise.
*/
public static long getNegativeSign(double number) {
assert !Double.isNaN(number);
return Double.doubleToRawLongBits(number) >> BIT_COUNT_EXCLUDING_SIGN_64;
}
The important parts to adjust the algorithm to fit my voxel boundaries are the following :
m_offsettedStart.set(m_start).addLocal(voxelHalfExtent, voxelHalfExtent, voxelHalfExtent);
It is mandatory to add the half extent to the starting position.
double nextVoxelBoundaryX = (voxelIndex.x + (MathExt.getNegativeSign(stepX) + 1)) * voxelExtent;
double nextVoxelBoundaryY = (voxelIndex.y + (MathExt.getNegativeSign(stepY) + 1)) * voxelExtent;
double nextVoxelBoundaryZ = (voxelIndex.z + (MathExt.getNegativeSign(stepZ) + 1)) * voxelExtent;
What the MathExt method call does could be programmed as : (stepX >= 0 ? 1 : 0).
I don't know how to express how it is delightful when everything starts to fit and work properly :')
Here are some screenshots :
Subscribe to our subreddit to get all the updates from the team!
I have had difficulties recently with the Marching Cubes algorithm, mainly because the principal source of information on the subject was kinda vague and incomplete to me. I need a lot of precision to understand something complicated Anyhow, after a lot of struggles, I have been able to code in Java a less hardcoded program than the given source because who doesn't like the cuteness of Java compared to the mean looking C++?
Oh and by hardcoding, I mean something like this :
cubeindex = 0;
if (grid.val[0] < isolevel) cubeindex |= 1;
if (grid.val[1] < isolevel) cubeindex |= 2;
if (grid.val[2] < isolevel) cubeindex |= 4;
if (grid.val[3] < isolevel) cubeindex |= 8;
if (grid.val[4] < isolevel) cubeindex |= 16;
if (grid.val[5] < isolevel) cubeindex |= 32;
if (grid.val[6] < isolevel) cubeindex |= 64;
if (grid.val[7] < isolevel) cubeindex |= 128;
By no mean I am saying that my code is better or more performant. It's actually ugly. However, I absolutely loathe hardcoding.
Here's the result with a scalar field generated using the coherent noise library joise :
Edit :
I've finally decided that I would share the code of my Java marching cubes algorithm interpretation. I was kind of possessive and didn't want people to copy my code. However, after thinking about it, for multiple algorithms, I had to translate or adapt open source code from someone else. It's so much easier to understand that way, mostly because research papers for algorithms are usually incomplete in terms of code and examples. Also, even if someone copies textually my everything that I will post here, it's not a little piece of code that would be a game changer in an application, even if it's a critical one because if it is, then those people would do everything to make it work.
What I will post here is in Java 9 and uses the jMonkey Engine 3.1 (a little customized but that doesn't matter). I also changed the way the tables data are saved as variables, so that it's more convenient to access them. This result in the removal of insignifiant zeros.
MarchingCubesTable.java :
/**
* Contains the lookup tables for the marching cube algorithm. Those are the edge and the triangle tables.
*/
class MarchingCubesTables {
public static final int EDGE_BITS = 12;
public static final int[] EDGE_TABLE = { 0x0, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 0x190, 0x99, 0x393,
0x29a, 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 0x230, 0x339, 0x33, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f,
0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9, 0x1a3, 0xaa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0, 0x460, 0x569, 0x663,
0x76a, 0x66, 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60, 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff, 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6,
0x9fa, 0x8f3, 0xbf9, 0xaf0, 0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55, 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950, 0x7c0, 0x6c9, 0x5c3, 0x4ca,
0x3c6, 0x2cf, 0x1c5, 0xcc, 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0xcc, 0x1c5, 0x2cf, 0x3c6, 0x4ca,
0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c, 0x15c, 0x55, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650, 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6,
0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0xff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x66, 0x76a, 0x663,
0x569, 0x460, 0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa, 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f,
0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33, 0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99,
0x190, 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 };
public static final int[] EDGE_FIRST_VERTEX = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3 };
public static final int[] EDGE_SECOND_VERTEX = { 1, 2, 3, 0, 5, 6, 7, 4, 4, 5, 6, 7 };
public static final int[][] TRIANGLE_TABLE = { {}, { 0, 8, 3 }, { 0, 1, 9 }, { 1, 8, 3, 9, 8, 1 }, { 1, 2, 10 }, { 0, 8, 3, 1, 2, 10 }, { 9, 2, 10, 0, 2, 9 },
{ 2, 8, 3, 2, 10, 8, 10, 9, 8 }, { 3, 11, 2 }, { 0, 11, 2, 8, 11, 0 }, { 1, 9, 0, 2, 3, 11 }, { 1, 11, 2, 1, 9, 11, 9, 8, 11 }, { 3, 10, 1, 11, 10, 3 },
{ 0, 10, 1, 0, 8, 10, 8, 11, 10 }, { 3, 9, 0, 3, 11, 9, 11, 10, 9 }, { 9, 8, 10, 10, 8, 11 }, { 4, 7, 8 }, { 4, 3, 0, 7, 3, 4 }, { 0, 1, 9, 8, 4, 7 },
{ 4, 1, 9, 4, 7, 1, 7, 3, 1 }, { 1, 2, 10, 8, 4, 7 }, { 3, 4, 7, 3, 0, 4, 1, 2, 10 }, { 9, 2, 10, 9, 0, 2, 8, 4, 7 }, { 2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4 },
{ 8, 4, 7, 3, 11, 2 }, { 11, 4, 7, 11, 2, 4, 2, 0, 4 }, { 9, 0, 1, 8, 4, 7, 2, 3, 11 }, { 4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1 }, { 3, 10, 1, 3, 11, 10, 7, 8, 4 },
{ 1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4 }, { 4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3 }, { 4, 7, 11, 4, 11, 9, 9, 11, 10 }, { 9, 5, 4 }, { 9, 5, 4, 0, 8, 3 },
{ 0, 5, 4, 1, 5, 0 }, { 8, 5, 4, 8, 3, 5, 3, 1, 5 }, { 1, 2, 10, 9, 5, 4 }, { 3, 0, 8, 1, 2, 10, 4, 9, 5 }, { 5, 2, 10, 5, 4, 2, 4, 0, 2 },
{ 2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8 }, { 9, 5, 4, 2, 3, 11 }, { 0, 11, 2, 0, 8, 11, 4, 9, 5 }, { 0, 5, 4, 0, 1, 5, 2, 3, 11 }, { 2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5 },
{ 10, 3, 11, 10, 1, 3, 9, 5, 4 }, { 4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10 }, { 5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3 }, { 5, 4, 8, 5, 8, 10, 10, 8, 11 },
{ 9, 7, 8, 5, 7, 9 }, { 9, 3, 0, 9, 5, 3, 5, 7, 3 }, { 0, 7, 8, 0, 1, 7, 1, 5, 7 }, { 1, 5, 3, 3, 5, 7 }, { 9, 7, 8, 9, 5, 7, 10, 1, 2 },
{ 10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3 }, { 8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2 }, { 2, 10, 5, 2, 5, 3, 3, 5, 7 }, { 7, 9, 5, 7, 8, 9, 3, 11, 2 },
{ 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11 }, { 2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7 }, { 11, 2, 1, 11, 1, 7, 7, 1, 5 }, { 9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11 },
{ 5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0 }, { 11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0 }, { 11, 10, 5, 7, 11, 5 }, { 10, 6, 5 }, { 0, 8, 3, 5, 10, 6 },
{ 9, 0, 1, 5, 10, 6 }, { 1, 8, 3, 1, 9, 8, 5, 10, 6 }, { 1, 6, 5, 2, 6, 1 }, { 1, 6, 5, 1, 2, 6, 3, 0, 8 }, { 9, 6, 5, 9, 0, 6, 0, 2, 6 },
{ 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8 }, { 2, 3, 11, 10, 6, 5 }, { 11, 0, 8, 11, 2, 0, 10, 6, 5 }, { 0, 1, 9, 2, 3, 11, 5, 10, 6 },
{ 5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11 }, { 6, 3, 11, 6, 5, 3, 5, 1, 3 }, { 0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6 }, { 3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9 },
{ 6, 5, 9, 6, 9, 11, 11, 9, 8 }, { 5, 10, 6, 4, 7, 8 }, { 4, 3, 0, 4, 7, 3, 6, 5, 10 }, { 1, 9, 0, 5, 10, 6, 8, 4, 7 }, { 10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4 },
{ 6, 1, 2, 6, 5, 1, 4, 7, 8 }, { 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7 }, { 8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6 }, { 7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9 },
{ 3, 11, 2, 7, 8, 4, 10, 6, 5 }, { 5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11 }, { 0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6 }, { 9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6 },
{ 8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6 }, { 5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11 }, { 0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7 },
{ 6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9 }, { 10, 4, 9, 6, 4, 10 }, { 4, 10, 6, 4, 9, 10, 0, 8, 3 }, { 10, 0, 1, 10, 6, 0, 6, 4, 0 }, { 8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10 },
{ 1, 4, 9, 1, 2, 4, 2, 6, 4 }, { 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4 }, { 0, 2, 4, 4, 2, 6 }, { 8, 3, 2, 8, 2, 4, 4, 2, 6 }, { 10, 4, 9, 10, 6, 4, 11, 2, 3 },
{ 0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6 }, { 3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10 }, { 6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1 },
{ 9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3 }, { 8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1 }, { 3, 11, 6, 3, 6, 0, 0, 6, 4 }, { 6, 4, 8, 11, 6, 8 },
{ 7, 10, 6, 7, 8, 10, 8, 9, 10 }, { 0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10 }, { 10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0 }, { 10, 6, 7, 10, 7, 1, 1, 7, 3 },
{ 1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7 }, { 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9 }, { 7, 8, 0, 7, 0, 6, 6, 0, 2 }, { 7, 3, 2, 6, 7, 2 },
{ 2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7 }, { 2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7 }, { 1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11 },
{ 11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1 }, { 8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6 }, { 0, 9, 1, 11, 6, 7 }, { 7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0 }, { 7, 11, 6 },
{ 7, 6, 11 }, { 3, 0, 8, 11, 7, 6 }, { 0, 1, 9, 11, 7, 6 }, { 8, 1, 9, 8, 3, 1, 11, 7, 6 }, { 10, 1, 2, 6, 11, 7 }, { 1, 2, 10, 3, 0, 8, 6, 11, 7 },
{ 2, 9, 0, 2, 10, 9, 6, 11, 7 }, { 6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8 }, { 7, 2, 3, 6, 2, 7 }, { 7, 0, 8, 7, 6, 0, 6, 2, 0 }, { 2, 7, 6, 2, 3, 7, 0, 1, 9 },
{ 1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6 }, { 10, 7, 6, 10, 1, 7, 1, 3, 7 }, { 10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8 }, { 0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7 },
{ 7, 6, 10, 7, 10, 8, 8, 10, 9 }, { 6, 8, 4, 11, 8, 6 }, { 3, 6, 11, 3, 0, 6, 0, 4, 6 }, { 8, 6, 11, 8, 4, 6, 9, 0, 1 }, { 9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6 },
{ 6, 8, 4, 6, 11, 8, 2, 10, 1 }, { 1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6 }, { 4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9 }, { 10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3 },
{ 8, 2, 3, 8, 4, 2, 4, 6, 2 }, { 0, 4, 2, 4, 6, 2 }, { 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8 }, { 1, 9, 4, 1, 4, 2, 2, 4, 6 }, { 8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1 },
{ 10, 1, 0, 10, 0, 6, 6, 0, 4 }, { 4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3 }, { 10, 9, 4, 6, 10, 4 }, { 4, 9, 5, 7, 6, 11 }, { 0, 8, 3, 4, 9, 5, 11, 7, 6 },
{ 5, 0, 1, 5, 4, 0, 7, 6, 11 }, { 11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5 }, { 9, 5, 4, 10, 1, 2, 7, 6, 11 }, { 6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5 },
{ 7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2 }, { 3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6 }, { 7, 2, 3, 7, 6, 2, 5, 4, 9 }, { 9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7 },
{ 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0 }, { 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8 }, { 9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7 },
{ 1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4 }, { 4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10 }, { 7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10 },
{ 6, 9, 5, 6, 11, 9, 11, 8, 9 }, { 3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5 }, { 0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11 }, { 6, 11, 3, 6, 3, 5, 5, 3, 1 },
{ 1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6 }, { 0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10 }, { 11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5 },
{ 6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3 }, { 5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2 }, { 9, 5, 6, 9, 6, 0, 0, 6, 2 }, { 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8 },
{ 1, 5, 6, 2, 1, 6 }, { 1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6 }, { 10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0 }, { 0, 3, 8, 5, 6, 10 }, { 10, 5, 6 },
{ 11, 5, 10, 7, 5, 11 }, { 11, 5, 10, 11, 7, 5, 8, 3, 0 }, { 5, 11, 7, 5, 10, 11, 1, 9, 0 }, { 10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1 }, { 11, 1, 2, 11, 7, 1, 7, 5, 1 },
{ 0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11 }, { 9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7 }, { 7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2 }, { 2, 5, 10, 2, 3, 5, 3, 7, 5 },
{ 8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5 }, { 9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2 }, { 9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2 }, { 1, 3, 5, 3, 7, 5 },
{ 0, 8, 7, 0, 7, 1, 1, 7, 5 }, { 9, 0, 3, 9, 3, 5, 5, 3, 7 }, { 9, 8, 7, 5, 9, 7 }, { 5, 8, 4, 5, 10, 8, 10, 11, 8 }, { 5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0 },
{ 0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5 }, { 10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4 }, { 2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8 },
{ 0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11 }, { 0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5 }, { 9, 4, 5, 2, 11, 3 }, { 2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4 },
{ 5, 10, 2, 5, 2, 4, 4, 2, 0 }, { 3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9 }, { 5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2 }, { 8, 4, 5, 8, 5, 3, 3, 5, 1 },
{ 0, 4, 5, 1, 0, 5 }, { 8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5 }, { 9, 4, 5 }, { 4, 11, 7, 4, 9, 11, 9, 10, 11 }, { 0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11 },
{ 1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11 }, { 3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4 }, { 4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2 },
{ 9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3 }, { 11, 7, 4, 11, 4, 2, 2, 4, 0 }, { 11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4 }, { 2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9 },
{ 9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7 }, { 3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10 }, { 1, 10, 2, 8, 7, 4 }, { 4, 9, 1, 4, 1, 7, 7, 1, 3 },
{ 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1 }, { 4, 0, 3, 7, 4, 3 }, { 4, 8, 7 }, { 9, 10, 8, 10, 11, 8 }, { 3, 0, 9, 3, 9, 11, 11, 9, 10 }, { 0, 1, 10, 0, 10, 8, 8, 10, 11 },
{ 3, 1, 10, 11, 3, 10 }, { 1, 2, 11, 1, 11, 9, 9, 11, 8 }, { 3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9 }, { 0, 2, 11, 8, 0, 11 }, { 3, 2, 11 }, { 2, 3, 8, 2, 8, 10, 10, 8, 9 },
{ 9, 10, 2, 0, 9, 2 }, { 2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8 }, { 1, 10, 2 }, { 1, 3, 8, 9, 1, 8 }, { 0, 9, 1 }, { 0, 3, 8 }, {} };
}
Chunk3DMeshFactory :
import com.chevreuilgames.retroflashyrpg.math.MeshBufferUtils;
import com.chevreuilgames.retroflashyrpg.world.level.zonelevel.chunk.Chunk3D;
import com.chevreuilgames.retroflashyrpg.world.level.zonelevel.chunk.ChunkMap;
import com.chevreuilgames.retroflashyrpg.world.level.zonelevel.chunk.IChunk;
import com.jme3.math.Vector3f;
import com.jme3.scene.Mesh;
import com.jme3.scene.VertexBuffer;
import com.jme3.scene.VertexBuffer.Format;
import com.jme3.scene.VertexBuffer.Type;
import java.nio.FloatBuffer;
import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.List;
/**
* Factory for creating meshes out of a scalar field using the marching cubes algorithm. The reference is the back bottom left point, which is locally the point (0, 0, 0).
*/
public final class Chunk3DMeshFactory {
private ChunkMap m_chunkMap;
private Chunk3D m_chunk;
private Chunk3D[][][] m_adjacentChunks;
private float m_isoLevel;
private float[] m_cubeScalars;
private Vector3f m_origin;
private List<Vector3f> m_vertices;
/**
* Constructs a new Chunk3DMeshFactory for generating meshes out of a scalar field with the marching cubes algorithm.
*
* @param chunkMap The chunk map that contains the adjacent chunks.
* @param chunk The chunk used to create a mesh.
* @param isoLevel The minimum density needed for a position to be considered solid.
*/
public Chunk3DMeshFactory(ChunkMap chunkMap, Chunk3D chunk, float isoLevel) {
this.m_chunkMap = chunkMap;
this.m_chunk = chunk;
this.m_adjacentChunks = createAdjacentChunks();
this.m_isoLevel = isoLevel;
this.m_origin = computeCenterPoint();
}
/**
* Constructs a new Chunk3DMeshFactory for generating meshes out of a scalar field with the marching cubes algorithm.
*
* @param chunkMap The chunk map that contains the adjacent chunks.
* @param chunk The chunk used to create a mesh.
* @param isoLevel The minimum density needed for a position to be considered solid.
* @param origin The local origin for all vertices of the generated mesh.
*/
public Chunk3DMeshFactory(ChunkMap chunkMap, Chunk3D chunk, float isoLevel, Vector3f origin) {
this.m_chunkMap = chunkMap;
this.m_chunk = chunk;
this.m_adjacentChunks = createAdjacentChunks();
this.m_isoLevel = isoLevel;
this.m_origin = origin;
}
private Chunk3D[][][] createAdjacentChunks() {
Chunk3D[][][] adjacentChunks = new Chunk3D[3][3][3];
final int length = 3;
for (int x = 0; x < length; ++x) {
for (int y = 0; y < length; ++y) {
for (int z = 0; z < length; ++z) {
adjacentChunks[x][y][z] = m_chunkMap.getChunk3DWithEmpty(m_chunk.getIndex().add(x - 1, y - 1, z - 1));
}
}
}
return adjacentChunks;
}
public Mesh createMesh() {
Mesh mesh = new Mesh();
FloatBuffer positionBuffer = createPositionBuffer();
IntBuffer indexBuffer = createIndexBuffer();
FloatBuffer normalBuffer = MeshBufferUtils.createNormalBuffer(m_vertices);
FloatBuffer textureBuffer = MeshBufferUtils.createTextureBuffer(m_vertices.size());
MeshBufferUtils.setMeshBuffer(mesh, Type.Position, positionBuffer);
MeshBufferUtils.setMeshBuffer(mesh, Type.Index, indexBuffer);
MeshBufferUtils.setMeshBuffer(mesh, Type.Normal, normalBuffer);
MeshBufferUtils.setMeshBuffer(mesh, Type.TexCoord, textureBuffer);
mesh.updateBound();
return mesh;
}
private IntBuffer createIndexBuffer() {
IntBuffer indexBuffer = (IntBuffer) VertexBuffer.createBuffer(Format.Int,
MeshBufferUtils.INDEX_BUFFER_COMPONENT_COUNT,
m_vertices.size() / MeshBufferUtils.INDEX_BUFFER_COMPONENT_COUNT);
for (int vertexIndex = 0; vertexIndex < m_vertices.size(); ++vertexIndex) {
indexBuffer.put(vertexIndex);
}
return indexBuffer;
}
private FloatBuffer createPositionBuffer() {
m_vertices = new ArrayList<>();
for (int x = -1; x <= IChunk.CHUNK_SIZE; ++x) {
for (int y = -1; y <= IChunk.CHUNK_SIZE; ++y) {
for (int z = -1; z <= IChunk.CHUNK_SIZE; ++z) {
Vector3f[] cubeVertices = new Vector3f[MeshBufferUtils.SHARED_VERTICES_PER_CUBE];
int cubeIndex = computeCubeIndex(cubeVertices, x, y, z);
int edgeBitField = MarchingCubesTables.EDGE_TABLE[cubeIndex];
if (edgeBitField == 0) {
continue;
}
Vector3f[] mcVertices = computeMCVertices(cubeVertices, edgeBitField, m_isoLevel);
addVerticesToList(m_vertices, mcVertices, cubeIndex);
}
}
}
return MeshBufferUtils.createPositionBuffer(m_vertices);
}
/**
* Add the generated vertices by the marching cubes algorithm to a list. The added vertices are modified so that they respect the origin.
*
* @param vertrexList The list where to add the marching cubes vertices.
* @param mcVertices The marching cubes vertices.
* @param cubeIndex The cubeIndex.
*/
private void addVerticesToList(List<Vector3f> vertrexList, Vector3f[] mcVertices, int cubeIndex) {
int vertexCount = MarchingCubesTables.TRIANGLE_TABLE[cubeIndex].length;
for (int i = 0; i < vertexCount; ++i) {
vertrexList.add(mcVertices[MarchingCubesTables.TRIANGLE_TABLE[cubeIndex][i]].add(m_origin));
}
}
/**
* Computes the marching cubes vertices. Those are the lerped vertices that can later be used to form triangles.
*
* @param cubeVertices The vertices of a cube, i.e. the 8 corners.
* @param edgeBitField The bit field representing all the edges that should be drawn.
* @param isoLevel The minimum density needed for a position to be considered solid.
*
* @return The lerped vertices of a cube to form the marching cubes shape.
*/
private Vector3f[] computeMCVertices(Vector3f[] cubeVertices, int edgeBitField, float isoLevel) {
Vector3f[] lerpedVertices = new Vector3f[MarchingCubesTables.EDGE_BITS];
for (int i = 0; i < MarchingCubesTables.EDGE_BITS; ++i) {
if ((edgeBitField & (1 << i)) != 0) {
int edgeFirstIndex = MarchingCubesTables.EDGE_FIRST_VERTEX[i];
int edgetSecondIndex = MarchingCubesTables.EDGE_SECOND_VERTEX[i];
lerpedVertices[i] = MCLerp(cubeVertices[edgeFirstIndex], cubeVertices[edgetSecondIndex], m_cubeScalars[edgeFirstIndex], m_cubeScalars[edgetSecondIndex]);
}
}
return lerpedVertices;
}
/**
* Lerps two vertices of a cube along their shared designed edge according to their densities.
*
* @param firstVertex The edge's first vertex.
* @param secondVertex The edge's second vertex.
* @param firstScalar The first vertex's density.
* @param secondScalar The second vertex's density.
*
* @return The lerped resulting vertex along the edge.
*/
private Vector3f MCLerp(Vector3f firstVertex, Vector3f secondVertex, float firstScalar, float secondScalar) {
if (Math.abs(m_isoLevel - firstScalar) < Math.ulp(1f)) {
return firstVertex;
}
if (Math.abs(m_isoLevel - secondScalar) < Math.ulp(1f)) {
return secondVertex;
}
if (Math.abs(firstScalar - secondScalar) < Math.ulp(1f)) {
return firstVertex;
}
float lerpFactor = (m_isoLevel - firstScalar) / (secondScalar - firstScalar);
return firstVertex.clone().interpolateLocal(secondVertex, lerpFactor);
}
/**
* Computes the cubeIndex, which represents the adjacent voxels' densities.
*
* @param cubeVertices The 8 corners of a cube.
* @param indexX The X position of the marching cube in the grid.
* @param indexY The Y position of the marching cube in the grid.
* @param indexZ The Z position of the marching cube in the grid.
*
* @return The cubeIndex.
*/
private int computeCubeIndex(Vector3f[] cubeVertices, int indexX, int indexY, int indexZ) {
m_cubeScalars = new float[MeshBufferUtils.SHARED_VERTICES_PER_CUBE];
final int edgeLength = 2;
int cubeVertexIndex = 0;
int cubeIndex = 0;
int cubeIndexRHS = 1;
/*- Vertex indices
4 ___________________ 5
/| /|
/ | / |
/ | / |
7 /___|______________/6 |
| | | |
| | | |
| 0 |______________|___| 1
| / | /
| / | /
| / | /
|/__________________|/
3 2
*/
for (int y = 0; y < edgeLength; ++y) {
for (int z = 0; z < edgeLength; ++z) {
for (int x = z % edgeLength; x >= 0 && x < edgeLength; x += (z == 0 ? 1 : -1)) {
cubeVertices[cubeVertexIndex] = new Vector3f(indexX + x, indexY + y, indexZ + z);
m_cubeScalars[cubeVertexIndex++] = queryGridScalar(indexX + x, indexY + y, indexZ + z);
if (queryGridIsSolid(indexX + x, indexY + y, indexZ + z)) {
cubeIndex |= cubeIndexRHS;
}
cubeIndexRHS <<= 1;
}
}
}
return cubeIndex;
}
/**
* Queries if the grid is dense enough to be considered solid at the give (x, y, z) point.
*
* @param x The index on the X axis.
* @param y The index on the Y axis.
* @param z The index on the Z axis.
*
* @return If the grid is solid or empty at the given point.
*/
private boolean queryGridIsSolid(int x, int y, int z) {
return isScalarSolid(queryGridScalar(x, y, z));
}
/**
* Queries the grid scalar at the given point and manages the boundaries, i.e. it's ok if x = -1 or is bigger than the gridLengthX.
*
* @param x The scalar X position in the grid.
* @param y The scalar X position in the grid.
* @param z The scalar X position in the grid.
*
* @return The grid scalar at the (x, y, z) position.
*/
private float queryGridScalar(int x, int y, int z) {
int chunkX = IChunk.getChunkIndex(x);
int chunkY = IChunk.getChunkIndex(y);
int chunkZ = IChunk.getChunkIndex(z);
return m_adjacentChunks[chunkX + 1][chunkY + 1][chunkZ + 1].getVoxelUnsafe(x - (chunkX << IChunk.CHUNK_SIZE_POWER_OF_2),
y - (chunkY << IChunk.CHUNK_SIZE_POWER_OF_2),
z - (chunkZ << IChunk.CHUNK_SIZE_POWER_OF_2));
}
public Vector3f computeCenterPoint() {
return new Vector3f((-IChunk.CHUNK_SIZE + 1) / 2, (-IChunk.CHUNK_SIZE + 1) / 2, (-IChunk.CHUNK_SIZE + 1) / 2);
}
private boolean isScalarSolid(float scalar) {
return scalar > m_isoLevel;
}
}
So here it is! I hope you find it useful
So we had our first hater... but first please listen to one of our music we think we was bashing against. After that, let's hear the context.
Context
Our development blogs on gamedev mainly focus on the actual development of our game(s) and any related research that we've done. So, our target audience is other video game developers. We also have our own subreddit where our target audience is everyone. Thus, we decided to make our subreddit public and allow subscribers to post content that follows the rules, which they are mainly about posting relevant content.
Recently, we've been gaining more popularity and finally gained our 25th subscriber! 🎉 However, with popularity means more human attention. One thing I know about humans is that there are among them douchebag, troll, egoist, evil [and so forth] people. Inevitably, we were bound to attract the attention of one of those toxic people and so we had our first experience with what we call a hater.
The Hater
The hater firstly unannouncedly posted this on our subreddit :
The person actually posted music of his game [I suppose]. It is an electronic music video. While it's true that we post vaporwave music videos on our subreddit, they follow the rule that it's about our game and our company.
So I decided to remove his post and send him a warning as a message :
Now, I don't clearly understand exactly what he meant by "Someone better than you, and wanted to make you feel better" but I do understand that this guy is saying he's better than us and that him posting his content on our subreddit would make us feel better (lol). I suppose the "better than us" part is related to our music, which is meant to be that way to fit into the game design of the game. Anyway, as you can see, this guy is so cool because he breaks rules. Wow.
But wait, there's more!
Just before I banned him, he posted this on our subreddit :
Of course we banned you for posting content about your game on our subreddit to gain popularity. Our subreddit specifies precisely through rules that it is meant to be a platform of communication for our company and a way to keep our subscribers in touch with the development of our games. Just look at r/fallout for example. Their first rule says that all posts must be directly related to Fallout. Are they not cool to ban people who disrespect that rule? No, it does not make sense. Reddit is a magnificent social network that allows specific sub-forums as ours and it's actually what defines it.
Anyway, I decided to ban him and then ignore him. I've always been more of an observer than someone who needs to express his opinion loudly and publicly on social networks but because this is the first time we had a hater for our game, I just needed to post about this.
What we learned from this :
Added a rule about not spamming that allows us to give warnings and ban people from our subreddit.
Ignore banned people.
Made our subreddit restricted instead of public. Now, only approved redditors are able to post on our subreddit.
Toxic people take time from us video game developers that we could put into making our game(s)
Subscribe to our subreddit to get all the updates from the team!
Idea
We wanted units in our game to be able to pick up items, including the player. But how can the player know which item will be picked up when he executes that action? Traditionally, video game developers and designers do this by using an outline shader. However, in our game, we thought that it was too "normal", cartoonish and not enough A E S T H E T I C.
Solution
The solution was to use Fresnel optics to simulate a cooler outline. The Fresnel Effect is used, approximated actually because it is extremely complex, in shaders such as a reflection shader for specular colors. In real life, this visual effect occurs on surfaces that reflect and refract light. An object that refracts light lets a fraction of the incoming light pass through its body. A good example for this is water.
Examples and Tutorials
Here are examples and tutorials for the Fresnel Effect in computer graphics programming :
Simple demonstration of what is the Fresnel Effect
Tutorial and more profound explanations on the subject
Simple get to the point tutorial with Unity as tool
How to Do It
Here's how I did it with the jMonkeyEngine, which is a Java 3D game engine.
Firstly, you need to create a material definition that will describe what will be the shaders and their inputs.
Material Definition
MaterialDef Fresnel Outline {
MaterialParameters {
Color FresnelOutlineColor
Float FresnelOutlineBias
Float FresnelOutlineScale
Float FresnelOutlinePower
}
Technique {
VertexShader GLSL100: shader/vertex/fresnel_outline/fresnel_outline_vertex_shader.vert
FragmentShader GLSL100: shader/fragment/fresnel_outline/fresnel_outline_fragment_shader.frag
WorldParameters {
WorldViewProjectionMatrix
WorldMatrix
CameraPosition
}
}
}
Material Parameters
As you can see, there are 4 uniforms that we need to specify to the shaders for them to function properly :
FresnelOutlineColor - The color of the Fresnel Effect. Usually, it is an environment map that deals with that.
FresnelOutlineBias - Acts like a diffuse color for the specular component.
FresnelOutlineScale - How far the Fresnel Effect affects the model. The smaller the angle between I and N (the surface's normal), the less Fresnel Effect there is and the more scale is needed for that surface to be lit by it.
FresnelOutlinePower - Exponentially increases the Fresnel Effect's color but decreases the scale.
We will need to either set them in the material or in the code. You'll see about that later in the article.
Technique
The technique describes what shaders to execute and their engine's uniforms.
There's no need to use a recent version of OpenGL / GLSL for this shader. The first GLSL version will do.
For the Fresnel shader, we need to the following uniforms to be supplied by the game engine :
WorldViewProjectionMatrix - The MVP matrix is needed to compute each vertex' position
WorldMatrix - The world matrix is needed to compute the position and normal for each vertex in world coordinates
CameraPosition - The camera position is needed to calculate the I (incident) vector
Material
The material uses a material definition and then applies render states and parameters to it. It is instantiable codewise.
Material Fresnel Outline : material_definition/fresnel_outline/fresnel_outline_material_definition.j3md {
MaterialParameters {
FresnelOutlineColor : 1.0 0.0 0.0 1.0
FresnelOutlineBias : 0.17
FresnelOutlineScale : 2.0
FresnelOutlinePower : 1.0
}
}
As you can see, we can set the uniforms right here instead of doing so in the code, which saves us programmers from dealing with design components.
Vertex Shader
#import "Common/ShaderLib/GLSLCompat.glsllib"
uniform vec3 g_CameraPosition;
uniform mat4 g_WorldMatrix;
uniform mat4 g_WorldViewProjectionMatrix;
uniform float m_FresnelOutlineBias;
uniform float m_FresnelOutlineScale;
uniform float m_FresnelOutlinePower;
attribute vec3 inPosition;
attribute vec3 inNormal;
varying float fresnelOutlineR;
void main() {
vec3 worldPosition = (g_WorldMatrix * vec4(inPosition, 1.0)).xyz;
vec4 worldNormal = normalize(g_WorldMatrix * vec4(inNormal, 0.0));
vec3 fresnelI = normalize(worldPosition - g_CameraPosition);
fresnelOutlineR = m_FresnelOutlineBias + m_FresnelOutlineScale * pow(1.0 + dot(fresnelI, worldNormal.xyz), m_FresnelOutlinePower);
gl_Position = g_WorldViewProjectionMatrix * vec4(inPosition, 1.0);
}
This is how each vertex position, normal, color, texture coordinates [...] are transferred into the vertex shader by the jMonkeyEngine.
attribute vec3 inPosition
The same procedure is applied onto g_ and m_ variables. g_ variables are definied by the engine, whilst m_ variables are defined by the material definition.
Here's how to do the Fresnel outline shader on the vertex side :
Compute the world position and normal
Compute the eye to vertex direction
Compute the Fresnel Effect R variable (description reference)
Fragment Shader
#import "Common/ShaderLib/GLSLCompat.glsllib"
uniform vec4 m_FresnelOutlineColor;
varying float fresnelOutlineR;
void main() {
gl_FragColor = mix(vec4(0.0, 0.0, 0.0, 1.0), m_FresnelOutlineColor, fresnelOutlineR);
}
All that's left to do is a linear interpolation between the black color and the desired color with R being the interpolation value between the two.
Because this is a simple tutorial, it only shows how to compute the Fresnel outline specular color.
Result
And with a bias of 1.0.
Teal!
Tested on a pickable item
Voxels! Unlike my old Xna application, this one's code is way more beautiful to the eye. Zero "switch" or "if and else" for cube faces, as I did with my cubic planet faces.
My only problem with voxels is that it's a 3D grid. A 3D grid take a lot longer to compute than six 2D grids.
250 * 6 = 1500 quads to compute and draw.
2503 = 15,625,000 voxels to compute and maybe draw.
As I use more and more complex objects to abstract the computation and the drawing part, the code slows.
Following this entry, I'll make another one but with two videos:
1) Spherical planet made of voxels
2) Cubic planet made of voxels
I'm an amateur and hobbyist video game developer. I've been programming for 9 years now even though I'm almost 21. When I started, it was rough being extremely bad with the english language and a noob programmer. Instead of helping me, people over multiple forums were only degrading my lack of skills and so I stopped being an active user. I have now finished what we call in Quebec a "technique". A technique is an academic degree of 3 years that is the equivalent of college degree. The technique I've done was called "Technique de l'informatique de gestion", which is a computer science technique applied to management softwares. As I finished college, I noticed I've improved my programming competencies and so I started again to research and program for fun, which I did 4 years ago. See
I'm currently working on planet generation. Everything was done using the jMonkey Engine 3, Java 8, Eclipse Mars and Joise (a java adaptation of the accidental noise library from JTippetts). The following videos sum up what I've done so far: