1362 views

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.
*
*/
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.
*
*/
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.
*
*/
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.
*
*/
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.
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

14 minutes ago, swiftcoder said:

They are not scalars but vectors; that's what the arrow means on top of a variable. So it's not scalar multiplications but dot products.

My friend just told me that I can use TeX instead of images for the equations : I'll update that at the same time that I'll upload the video.

Quote

// In which direction the voxel ids are incremented.
double stepX = MathExt.getSignZeroPositive(m_direction.x);

Shouldn't the steps be integers? Actually there is double to int conversion in the inner loop caused by this.

10 hours ago, JoeJ said:

Shouldn't the steps be integers? Actually there is double to int conversion in the inner loop caused by this.

You're right, thank you. I'll fix it.

Very impressive.  Nicely done.  If you don't mind saying, what language did you write this code in?  I can't follow or understand it.  I know English isn't your native language, but would you be willing to offer up a simplified explanation of the logic you used for this blog post?

6 hours ago, Awoken said:

If you don't mind saying, what language did you write this code in?﻿

It's in Java but everything remains the same as other C languages, except the calls to my personal methods, which is kind of egoistic of me. I just haven't tried yet if they are more performant than Java's JDK math methods.

6 hours ago, Awoken said:

ould you be willing to offer up a simplified explanation of the logic you used for this blog post

For the gradient or the algorithm? Well, first of all, for the algorithm, you need to at least read the research paper to get a grasp of what was the intent and the result wanted by the authors, even if you don't understand everything.

Second of all, 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 .

Third of all, 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?

I'll add this explanation to the article ^^

I'm still confused.  Which part of the code you posted actually determines which voxels are hit?

4 hours ago, Awoken said:

I'm still confused.  Which part of the code you posted actually determines which voxels are hit?

        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;
}
}

Look more specifically at onTraversingVoxel.apply(voxelIndex) : this line of code applies a Java functional interface, which is a lambda. The supplied parameter is the absolute (world) index of the voxel touched.

Posted (edited)

Oh fantastic explanation.  I now understand the logic and it's remarkably simple, which is a good thing.  Great blog post, very educational.

Edited by Awoken

Create an account

Register a new account

• Similar Content

• By sprotz
I know that there are Vehicle and Car blueprints all over the net on almost every car model that exists and has existed, but surprisingly few textures. To be precise, photo textures of side view, front view and rear view of even common car models is hard to find. Even raster graphics drawn textures are rare. The best that could be found is on the Google Warehouse and typing 'textured car' in the search box. This will give you some good numbers of textured cars and car textures. Google warehouse is also excellent for finding textured buildings and building textures for any region. But where on earth are the vehicle textures?

• Hi,
We know that it is possible to modify the pixel's depth value using "System Value" semantic SV_Depth in this way:
struct PixelOut { float4 color : SV_Target; float depth : SV_Depth; }; PixelOut PS(VertexOut pin) { PixelOut pout; // … usual pixel work pout.Color = float4(litColor, alpha); // set pixel depth in normalized [0, 1] range pout.depth = pin.PosH.z - 0.05f; return pout; } As many post-effect requires the depth value of current pixel (such as fog, screen space reflection), we need to acquire it in the PS. A common way to do that is to render the depth value to a separate texture and sample it in the PS. But I found this method a bit clumsy because we already have depth value stored in the depth-stencil buffer, so I wonder whether it is possible to access from NATIVE depth buffer instead of ANOTHER depth texture.
I found this on MSDN:  https://docs.microsoft.com/en-us/windows/desktop/direct3dhlsl/dx-graphics-hlsl-semantics

that mentions READ depth data in shader. I tried this in Unity:
half4 frag (Vert2Frag v2f, float depth : SV_Depth) : SV_Target { return half4(depth, depth, depth, 1); } However it turns out to be a pure white image, which means this depth values in all pixels are 1. So is that MSDN wrong? Is it possible to sampling a NATIVE depth buffer?
Thanks!

• This is my TMNT party wagon. I know its super messed up but it was my first real big project car. I found a blueprint of the car on a Episode of TMNT and when i uploaded it to my 3D program I noticed it was centered. So thank you to whoever rendered that one frame, because its all I needed. I made some custom textures and a UV layout from scratch. It's not exact but hey i think it looks cool. I will defiantly go back in and redo this now I have better knowledge of topology.

• This is a project I've been working on for awhile now. I'd say over all going on around a year. I did the Machbot 2.0 all from scratch including the textures. I spent countless hours trying to figure out how to get the models from Twisted Metal. I finally figured out how to manually extract the mesh. But the only problem was it was not UV mapped. So i pretty much had to go back in and remap everything. Which wasn't hard but the assembling of the model itself was a challenge. I did the best I could at placing stuff where it goes I'm sure there are things that are incorrect. All in all it was for this one render. Not sure if my models can be used as game assets but i do want to eventually make this into a fighting game. Both vehicles and bots. Let me know what you think and thank you for checking out my work.

• By jb-dev
Let's hit the pipes!!! For a reasonable cost, the player can gain a permanent random stats bonus when selecting those dumbbells over there, on the mat. But each time the player uses a dumbbell it disappears afterwards and the cost of the others dumbbells are doubled.
×