Jump to content
  • Advertisement

Voxel Traversal Algorithm (Ray Casting)

thecheeselover

5399 views

For more information and updates about the game, which is a voxel colony simulation / survival, please subscribe to r/CheesyGames.

World Generation

image.thumb.png.17fa74b357314a335ce832b6bba44677.png

 

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?

image.png.795262d06175e7eef086822b9a19cb46.png

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

Capture-2.thumb.png.d01ec6b16fe9960734bdf464692cb352.pngCapture-4.thumb.png.d894ebdd7869ab90ec51542e74c0a421.pngCapture-3.thumb.png.ef840ead6db6c7b7cb4e31eadea4e50c.png

 

 




6 Comments


Recommended Comments

Don't the gradients cancel in your formula? You should end up with just position/gradient?

Share this comment


Link to comment
14 minutes ago, swiftcoder said:

Don't the gradients cancel in your formula? You should end up with just position/gradient?

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.

Share this comment


Link to comment
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.

Share this comment


Link to comment
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.

Share this comment


Link to comment

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? 

Share this comment


Link to comment
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 ^^

Share this comment


Link to comment

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

Share this comment


Link to comment
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.

Share this comment


Link to comment

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

Share this comment


Link to comment

It's interesting that neither this thread nor the linked paper mentions it: I'm convinced this is just a 3D bresenham implementation. (credit where due)
Back in early 2010, I played around with implementing bresenham in a fragment shader working on a volume texture, and it actually did pretty good.
It's sort of a nice way to avoid using polygons, if you're into that sort of thing, but it was a little too much branching for my GPU at the time...

Share this comment


Link to comment
3 hours ago, SuperVGA said:

It's interesting that neither this thread nor the linked paper mentions it: I'm convinced this is just a 3D bresenham implementation. (credit where due)
Back in early 2010, I played around with implementing bresenham in a fragment shader working on a volume texture, and it actually did pretty good.
It's sort of a nice way to avoid using polygons, if you're into that sort of thing, but it was a little too much branching for my GPU at the time...

I didn't know that algorithm. However, the result of the Bresenham's method is the first of two possible choices, which can traverse diagonally. For my algorithm, I need the second choice because I don't want the ray cast to select voxels diagonally, as it might select hidden voxels.

Share this comment


Link to comment
49 minutes ago, thecheeselover said:

I didn't know that algorithm. However, the result of the Bresenham's method is the first of two possible choices, which can traverse diagonally. For my algorithm, I need the second choice because I don't want the ray cast to select voxels diagonally, as it might select hidden voxels.

Ah, right. Yeah, I don't think it's something that requires a whole lot of thought either, so it's fair enough. Mostly I was just puzzled as to why the paper didn't reference it.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
  • Advertisement
  • Blog Entries

  • Similar Content

    • By Shadowsane
      My project started in 2014 but recently ended due to no funds.  AltarisNine was a Minecraft project based on RPG. The concept was nine islands that you explore at a time to follow an in depth lore based on our own production team. This is where the 'Nine' comes in. With skepticism of future success we hope to make this tale into chapters. Such as the first one introducing Nine islands at time.
      It wasn't always the same though, my world did evolve over time and now I have a better idea of what it is better than ever. In the first island, Main Isle, is themed around jungles and wilderness. There's lore that stretches throughout the chapter which will engage the player. There would also be kinds of characters you can be such as any other RPG which could be talked about (because i'm still  about what I have lol)
      My former team was designing a world players would get into interact with in various ways. Boss battles would be minigames and the RPG lore would be engaged in and something indie platforms would enjoy and talk about beyond platforms.
      In the minecraft varient I was a builder, the leader, and the story director which everyone respected. I led my own team of builders and story writers. While I chose certain individuals to be the head department of development and art design.
      The reason I am here is to find a new team to help take this away from minecraft and hope we can be successful about it. I'll happily commute each and every person that volunteers and will be accommodated down the line with promotions, wages, and definitely praised for helping start my dream up.

      Here are some questions that were frequently asked and that I can thoroughly answer:
      What is the goal of the game? If you've ever heard of Wizard101. I got inspired by that game a little. I like the concept of making yourself in this world of mystery and impressing people with new mechanics and events that they enjoy. I'd like for the game to be successful and be mostly on PC but if this keeps up we could reach out to other consoles. But for now, PC, one platform at a time lol. My goal personally is to give people the entertainment and enjoyment I think they'll deserve. Something thats not cheesy, not cliche, something new to keep evolving the gaming community Is this in first-person or third-person? This will be a third person game. We can play around with the camera angles but I kind of want it from a aerial pov I saw RPG in the post so can I assume that the game will have generic RPG elements, e.g. quests, npcs, story-line, items? Yes this will have generic RPG elements. But with a few surprises that make the game different. Such as making boss fights some type of minigame. I don't know how the audience will like or even if it'll flow with game play. But I'd still like to take the idea on for now. Will there be combats, e.g. vs. monsters, vs. players(?) ? There will be tons of concepts. As i've said before the 'Nine' comes in the Nine isles of this world we haven't named yet lol. Each nine islands we come up with will not only give players plenty of content to play, but something we break up into story chapters. Each island will have its on set monsters tied to the story or even monsters that are just natural in their environment. There will also be a PvP aspect which can't be brought up too much because its difficult to try to come up with a player style culture that isn't too predictable or generic or even cliche. I was wondering if it should be an initiated fight or a head on duel like world of warcraft. Is this a single player game or a multiplayer one? Definitely multiplayer. Will the game look like Minecraft? like a voxel/blocks game? I imagined it not looking like minecraft but maybe that can be a concept of its own down the line (like an island concept). I was thinking along the lines of a 3D style and not like minecraft. What are the core mechanics to be included, e.g. player movement, enemy movement, enemy AI? This question is more technical but there will be interactive things in the world, things to collect, natural occurring crafting supplies to make new loot and weapons with. There will be NPC's and thats a broad topic enough lol. I'd even a imagine a pet, housing, and gardening system. But thats for accessories in coding and to give more content in the game for later polishing. Is there a storyline already made? There is an indirect storyline. We've made a script for voice actors (and just what to make the NPC's say in general) in A9 v1. Are there goals already planned out? There are many goals to set out. One each at a time for separate upcoming departments The first 8 pictures were of our hub, the other 9 was our factions world. The factions world doesn't retain to this project I wanted you to see how dedicated I was to making this project. I built everything in the hub myself except for the giant pagodas. The last two photos were all the ones I could find of the RPG world
       




















    • By bzt
      Hi,
      I was looking for a way to effectively interpolate between skeletons represented by list of bones with position vector + orientation quaternion pairs. To my surprise, I couldn't find any good solution, not to my taste that is. I can't use NLERP because I need a general solution, and NLERP is only good for small distance interpolations. SLERP would be perfect, but I couldn't find a decent implementation, only slow ones, so I spent a lot of time looking at game engines and quaternion libraries and reading academic articles on the topic. Finally, I decided to collect my findings and write my own optimized version of SLERP, which focuses on performance over precision, and which I now would like to share with you.
      Optimized cross-platform SLERP
      I've started from the well known formula, as implemented by most C++ libraries, and used all the tricks I could find on the net. Then I took it to the next level, and made some more adjustments on my own speeding up a little bit more. Finally I ended up with two solutions:
      1. one that is cross-platfrom, ANSI C solution that is easily embeddable in C++ and compatible with any C / C++ quaternion class (provided their data can be seen as 4 floats), very simple, very minimal. Use it freely if you want, MIT licensed
      2. a SIMD version, which I had to leave half-ready, because my compiler and Intel disagree on what intrinsics should be provided for SSE, moreover the compiler does not work the way its documentation say it should :-( Shit happens. I would only recommend this for experimental purposes, also MIT licensed
      Both versions are simpler and much faster than any implementations I could find, designed to be called in a loop several times. The only dependency they have is lib math (acosf, sinf). The SIMD version is half-ready, but even in this form it's almost 1.5 as fast as the other one, especially if you call it in a loop with memory prefetch on the quaternions.
      If I made any mistake, miscalculated or mistyped something, let me know. If anybody has an idea how to overcome that intrinsics blockade I have, that would be appreciated very much, because I can clearly see the path how to make the code several times faster, only if I could get rid of the library calls. I also plan to create an ARM NEON port once I have that.
      Cheers,
      bzt
    • By Octane_Test
      I want to render an ocean where players can change waves’ amplitude in real-time. Initially, I would render rolling waves (see picture). As the amplitude increases, I need to transition the rolling waves into breaking waves (see picture). For now, I am not going to show the shoreline onscreen so I don’t need to render breaking waves interacting with the shoreline; I only need breaking waves on the open ocean.

      I’ve tried three different approaches so far and I’ve only had success with rolling waves using approach 1. Breaking waves have been impossible so far with all three approaches.

      Approach 1: Mesh deformation

      a.     I can create smooth rolling waves using the Sine and Gerstner equations.

      b.     Since I can’t use these equations for breaking waves, I tried to implement them by using this free plugin whose output is similar to this paid mesh deformation plugin. But there are 2 problems with this plugin approach:

      ·      There is no smooth transition between rolling waves generated by approach 1a and the breaking waves generated by the Deform plugin

      ·      The output of the plugin does not look similar to real breaking ocean waves in three different ways:

                                                     i.     No smooth blending with the ocean surface

                                                    ii.     A large depression is created below the crest

                                                  iii.     The entire wave is the same height (rather than with more realistic variations)

      c.      I considered using vertex shaders but this approach seems similar to mesh deformation.

      Approach 2: Fluid dynamics + metaballs

      1.     To render an ocean I will need thousands of particles which will be too expensive in terms of performance (especially for mobile devices).

      Approach 3: Using mesh files

      1.     I can create breaking waves using some 3D software like in this post but then I can’t modify the ocean in real-time. It will be more like a pre-rendered simulation.

      To summarize, I am looking for an approach where I can vary ocean waves’ amplitude for a smooth transition between rolling waves and breaking waves. Please let me know if you have more questions.

    • By bandages
      So, in real life, incoming dot normal at the silhouette is always 0.  With smooth shaded meshes, it never is, not naturally, not outside of contrived situations.  (Not with flat shaded meshes either, I guess.)
      And incoming dot normal is one of the bedrocks of CG.  Probably the equal of 4x4 matrix multiplication.  Problems with silhouette normals show up in Fresnel, in diffuse lighting, in environment mapping....  everywhere.  But I can't really find anybody talking about it.  (Maybe I'm not Googling the right terms.)
      Obviously, the problem decreases as poly count goes up, eventually reaching a point where it's dwarfed by other silhouette problems (like translucency or micro-occlusion) that CG doesn't handle well either.  But, if I'm reasoning correctly, normal maps don't improve the problem-- they're as likely to exacerbate it as improve it, and the exacerbations are, aesthetically speaking, probably worse than the improvements are better.
      I've tried playing with crude fixes-- basically, rotating normals toward incoming by a percentage, or of course clamping incoming dot normal (like we all have to do) to prevent it from bending behind the mesh.  Nothing I've tried looks good.  I suppose the best option might be to rotate normals to perpendicular to incoming at the silhouette and then interpolate to the nearest inflection point  of something like screen space depth to preserve curvature, but the math for how to do that is beyond me, and I'm not sure it would look any better.  Or maybe, instead, somehow, adjust the drawn silhouette to match the silhouette defined by incoming dot normal?  Not even sure how that would work, not if the normal was pointing away from incoming.
      I don't know-- is this a solvable problem?  Has anyone tried other stuff and given up, pursued anything that was promising but too expensive, anything like that?  Are there any papers I'm missing?  It's really surprising to me that I can't find anyone else talking about this.
      (Apologies if I chose the wrong subforum for this.  I considered art forums, but I felt that people frequenting the programming forums would have more to say on the subject.)
    • By vinibiavatti
      Hi there! I have one issue for now. I'm creating a RayCasting application, and for my floor and ceiling I'm trying to use Mode7 for rendering (I think this is easier to understand). but, I cant align the RayCasting walls with the mode7 floor. I use a rotate matrix to make the rotation of floor. Do you know what a need to think in the implementation to fix that? Or do you know if there is some tutorial explaining about it? Thanks!!! (Check the image below for understand)

      Here is my mode7 code:
      function mode7() { let _x = 0; let _y = 0; let z = 0; let sin = Math.sin(degreeToRadians(data.player.angle)); let cos = Math.cos(degreeToRadians(data.player.angle)); for(let y = data.projection.halfHeight; y < data.projection.height; y++) { for(let x = 0; x < data.projection.width; x++) { _x = ((data.projection.width - x) * cos) - (x * sin); _y = ((data.projection.width - x) * sin) + (x * cos); _x /= z; _y /= z; if(_y < 0) _y *= -1; if(_x < 0) _x *= -1; _y *= 8.0; _x *= 8.0; _y %= data.floorTextures[0].height; _x %= data.floorTextures[0].width; screenContext.fillStyle = data.floorTextures[0].data[Math.floor(_x) + Math.floor(_y) * data.floorTextures[0].width]; screenContext.fillRect(x, y, 1, 1); } z += 1; } }  
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!