How to build a voxel world that isn't procedural | Not sure if this is in the right forum.

News & General Discussion
1

Hopefully I’m posting this somewhere acceptable.

Basically I’ve been fooling with Unity and read/watching a lot of tutorials and such.

I want to experiment with making a tiny world to walk around on and test what I’ve learned with picking up and placing blocks and such. I did so with a small plane made of cubes so that I could texture them all uniquely but the more I read the more I’m realizing that’s inefficient and that voxels are the answer? (maybe I’m way wrong with that)

Regardless my question is simple though I’m sure the answer is not.
How can I creat a list of voxel definitions (not sure how to word that) and place them in the world? I don’t want it to be procedural, I want to build my tiny plane to fool around on not generate it.

Thanks in advance,
BaeWater

PS I’m sure my vocabulary is minimal but I am learning. I have also looked for the answers myself but it seems that voxels are immensely connected to procedural generation so I can’t seem to separate the two topics. Maybe I just missed something in front of my face?

2

Welcome!

I found this series to be a fantastic starting point for generating cubic voxel terrain. In order to not have hills and features, and just have flat land, don’t use the Perlin noise generation portion; just set the height values to the same value for each point.

Good luck, and have fun!

PS - Your English is fine! No need to apologize!

Edit: If you want to do generated voxel terrain that’s not cubes, check out this series by Sebastian Lague. It’s definitely much more focused on the procedural portion, but the same concepts apply (you can manipulate vertex data to displace land).

3

I meant my vocab concerning terms in Development/Unity/Programming but I’m glad my English is good too :wink:

I actually followed a similar guide and kinda figured out how to manipulate a chunk into different sizes of width and depth. I suppose to clarify (I just can’t seem to figure out in my head with some direction) I want to build my world in unity. Lets say I set up a flat plane of voxels. How would I be able to add a custom hill where I want it (for simplicity sake let’s define a hill as a 2x2x2 cube of voxels).
Maybe this is what voxel engines do and I can’t achieve such a thing on my own. From what I’ve been reading over the past few days it seems voxel engines are too complicated for a novice to develop a homebrew version of one, even if its extremely simplified.

I just like the idea of the voxel system so I wanted to experiment with it but I don’t want to spend $100 on a basic engine to do so. I’m not trying to be the next big thing in game development, I just wanna explore something that interests me :smile:

4

Whoops, my bad! On a few fronts, it seems…

Anyway, I’ve not done much with voxels other than tinkering, so I can’t be of much further use, sadly. I don’t doubt someone will come along shortly with better info for you, though.

:smile:

5

Well I appreciate the help you’ve given me :slight_smile:

6

Well there is two things in voxel:

  • the visual representation
  • the data

The visual representation is what’s the tutorial spend time dealing too with how to polygonize the data.

Data is basically just a 3d array, so you can just fill it like a 2d array but in 3d. So if you know how to draw a solid montain in 2d, you should be able to figure out how to do it in 3d.

1 Like
7

I’ll just have to experiment more with the array then :slight_smile:

8

The loop is simple, put or remove data on the array, rebuild necessary mesh part, repeat.

9

The only difference between procedural and non-procedural voxel world is how the data was initially generated. Aside from that all the techniques are the same.

At the simplest/dumbest representation, voxelworld is an array of cubes where each cube has integer coordinates in the world and material index. This implementation is very inefficient, though.

At a more advanced implementation, voxel world can be represented as a hash map (int coordinate to material index) where empty cells are removed, or a voxel array sorted according to space filling curve (like z curve, also see morton code https://en.wikipedia.org/wiki/Z-order_curve )

A more efficient way to store data would be to create a technique similar to aabb tree for voxels.

Basically… a node (which is a box with size x times bigger than a single voxel) of such aabb tree is filled with voxels of the same type (which could be an “empty voxel”), if it has no child/leaf nodes. Meaning the whole node could represent a 65536x65536x65536 volume of voxels, for example. If child/leaf nodes are present, the node is subdivided into 8 child nodes, and each of them are processed in the same way - if there are no children, they’re filled with the same voxel value, and if there are children present, the children are processed recursively.

This allows faster building of the world and also compresses the data.

In more advanced implementation of voxels, voxels have density and are no longer represented as cubes. This allows creation of curved surfaces using voxels. I think pretty much the only recent game that did it was Planet Explorers.

I’d also recommend to try non-polygonal voxels, where instead of building meshes, you use raycasting. This potentially allows very interesting effect (for example, you could be able to create a realtime reflections in such environment).

I briefly tinkered with this a long time ago, but haven’t had time to finish the idea.

https://www.youtube.com/watch?v=Xd6tlw02iio

–edit-

The difference betweeen “array of cubes”, “z-curve sorted array of cubes”, “hash map” and “tree” is amount of work done to process voxels. When dealing with voxel world, you have two major kind of queries: “give me list of voxels within the volume” and “give me the voxel data at this point/coordinates”.

  • Unsorted array of cubes cannot be efficiently used to process either query. Adding/removing voxels is fast, though - you can append one more at the end, or swap a voxel with the last voxel, then remove last voxel.
  • z-curve is essentually a flattened aabb tree, and it can respond to both queries relatively quickly, the issue is that querying voxel at coordinates will have O(log2(N)) complexity, because it will have to perform binary search. Also, adding a new voxel to this structure requires sorting the whole array again, same applies to removing voxels.
  • Hashmap-based approach is very fast when querying voxel at coordinates. Addition and removal of voxels is very fast too. However “voxels within a volume” query will be slow, because you’ll need to iterate through every voxel within the volume and query if something exists at the coordinates.
  • AABB tree is similar to z-curve, meaning that you can have fairly quick “voxel within volume” query, fast “gimme voxel at those coordinates” query (unlike z-curve array you won’t need to perform binary search, and in some cases may get immediate response). Adding/removing voxels is faster than with z-curve array, but slower than hash map, because it may trigger partial restructuring of the tree.
1 Like
10

Sound overkill for someone who hasn’t figure out that the data could be anything. lol

I’m sure about the z order things, what gain do that bring?

11

Well, they’ll have to figure it out either way. Might as well start right now.

Z-curve - sorted array automatically acts as an AABB tree for the purposes of querying data.

You can get list of all voxels or objects in an aabb cell by binary searching (using an equivalent of upper/lower bound functions). Basically, you can easily calculated lowest possible and highest possible indexes of an AABB cell, find corresponding elements with binary search, adn everything between those elements will be everything within AABB cell.

It is a fairly compact representation of data that requires very simple storage container - array. When scenes are voxelized by GPUs, they typically use z-curve.

^^^ Source: wikipedia.

The problem is that element addition/removal is slower.

12

I understand what a z curve is, but I mean, it’s a space traversal techniques, I don’t see the gain in a potentially sparse and random representation. The only reason I see them used by GPU is because gpu hardware are processing data by group of 4 adjacent pixel typically, which mean it’s more efficient as a traversal.

I mean there is two case with OP

  • either he want to generate landscape and then there is some predictability in the data (land will be below, so we know we would have higher density there even with random generation), which mean there is bigger chance to get coherent order to store and compress. But it’s mostly useful if we are going to store things on disk.
  • Or he want to make the equivalent of a 3d painter, and there is no guarantee to have consistent structures, so the data is as good as random and then there is no way to traverse space.

Typically minecraft type of voxel (which I assume OP is going for, that’s where the tut ecology is) use a 3d array because it’s straightforward, fast, cache coherent and need only O(1) for access, while every other technique add overhead and complication (octree is specifically frown upon). Since the data is random, you will have to go through all cells no matter what. The only things is that they segment space into chunks to manage generation time and in unity polygon limits.

Now if OP do stuff on the gpu maybe, but I doubt typical tuts do things elsewhere than CPU.

Maybe there is something I missed?

13

Are you sure about that?

It is not random. It is very organized. And it is not a space traversal technique. Read the article I linked, search for first mention of morton code and think about it.

To any 3d object you assign an unique code based on thier coordinates, called a morton code.
Sorting objects by that code organizes them in such fashion that is already partitioned in correct way to represent a collapsed aabb tree.

Here’s 2d aabb tree based on z curve.

┌──┬──┬──┬──┐
│ 0│ 1│ 4│ 5│
├──┼──┼──┼──┤
│ 2│ 3│ 6│ 7│
├──┼──┼──┼──┤
│ 8│ 9│12│13│
├──┼──┼──┼──┤
│10│11│14│15│
└──┴──┴──┴──┘

You want the whole cell? The indexes are in [0…15] range.
Upper left corner? Indexes are in [0…3] range.
Bottom left? [8…11] range.

Data is sorted. You can find upper_bound/lower_bound indexes and individiual indexes using binary search.
Storage is trivial - it is an array. If you know boundaries of data of bigger cell, you can find data in a lower resolution at less time.

Also, coordinates of the cell are already encoded into the index.

That’s absolutely not what the z-curve is about. GPU hardware is also perfectly capable of processing random data without “pixels” being involved.

If there are people who frown upon octrees while dealing with voxels, I think they should consider changing their profession.

No, you don’t.

The data is not random. Techiniques like octrees allow you to skip huge blocks of voxels entirely without processing individual cells. That’s the whole point.

Yes.
You missed benefits of octrees while processing sparse data, and you missed the point of using morton codes which are based off z-filling curve.

The point of z-filling curve is that based of objects coordinates you generate unique index (which encodes coordiantes), and when object are sorted by this index, they end up in a compact representation of AABB trees. The reason why it is used on gpus is because GPUs can perform parallel sort. Meaning in systems like NVXGI you can grab the scene, generate morton cells of it, sort them, and then feed them into something else without ever touching CPU side of things.

I’d suggest to google for “morton code GPU”. For example:
https://devblogs.nvidia.com/parallelforall/thinking-parallel-part-iii-tree-construction-gpu/

Octrees and bounding volume hieararchies will be very important when dealing with voxels, because otherwise you’ll be much more limited by your computer memory. Basically, volume hierarchies allow sparce representation of data, where data that does not existed is not stored. A basic “dumb” 3d array representation will severely limit you, and it takes much more time to traverse it.

Volume Hierarchies or z-curve based representation allows you to immedaitealy realize that the whole underlying block is empty or that the whole underlying block is filled with a single value, meaning you will not need to waste your time walking through it probing every cell for data.

So, basically, in case of 256x256x256 cube algorithmic complexity in best case scneario will drop from 16 million operations to one check, and similarly amount of used memory will drop from 16 megabytes to just a few bytes. And now you tell me there’s someone in the world who look down at octrees with dealing with this kind of data.

2 Likes
14

I must admit most of the recent response goes well over my head. Those some does make sense to me (or as much sense as it could to someone who knows little about programming)
Regardless it interests me none the less and has given me some direction and at the very least a list of topics to understand after i master the simplest of voxels.

I’m still just playing with the idea of a 3d array so we shall see how that goes.

15

We’re an excitable bunch, and we have a tendency to get a bit carried away sometimes.

1 Like
16

I’ll certainly take an excess of information I need to learn than non descriptive generic answers any day. Like I said I find myself interested in this and the more direction I’m given the more I can direct my own efforts in understanding it all!

17

Ignore the posts where I respond to neoshaman, and concentrate o the one with youtube video in it.
https://forum.unity3d.com/threads/how-to-build-a-voxel-world-that-isnt-procedural-not-sure-if-this-is-in-the-right-forum.482733/#post-3141211

“Responses” had excessive details in it that you don’t need right now. The one with the video will have enough information to have an overview/get started with it.

18

@neginfinity

  • I wasn’t saying z curve where random, but the data, you cannot predict what it will be.
  • On gpu “pixel”, The way I understand it, the processor are organized in group of 4 cores, the reference to pixel is that they tend to process 4 of them (fragments) in each group of core, these core have shared memory which help in some operation like dealing with aliasing or need extra care to waste resources like in checkerboard rendering. Being parallel, any long term dependency to other groups of core would stall the entire gpu. Now you can feed more than one data to any core, but since the underlying data structure is already spatially coherent and local, it make sense to fetch them in a z pattern. But I’m no expert lol.
  • About octree I think it’s a matter of context (ie heavy generation and modification), Notch himself shy away from it (and it did quit lol) and any wannabee after him jumped straight to octree too, but it turns out it was premature optimization. Now Sparse voxel octree, which is another level of details, do use octree, but had to massively adapt it to make it memory consistent with a specific lay out and a specific way to build the index. Now I haven’t made a full blown voxel engine (yet), only dabble in it. But I had a bunch of favorited links that discuss the topic in depth. They are able to articulate the problem better than me (it’s not my idea).
    An Analysis of Minecraft-like Engines – 0 FPS

That was for context

  • I’ll dig more in those morton code, thanks (it looks like the thing I mentioned in the sparse voxel part (Samuli Laine paper), but I don’t know the difference yet). Maybe things have move since last time I checked.
19

You do know how gpu scene voxelization works, right? Render scene from multiple views, upon rasterization phase, voxelize and dump into array in random order, then parallel sort the array.

I’m fairly sure this data is very likely to be outdated.
Please refer to CUDA/OpenCL cores, threads, thread blocks, walls, etc.
The things like scene voxelization are at least partially processed in a compute shader. In a compute shader, there are no pixels.

1 Like
20

So I’m sure this question is rudimentary but if Im sitting here fooling with different code and slowly grasping what certain phrases within C# mean and such. I’m just fooling with a simple 3d array.
So with the array bellow I make a flat plane that is 3 high and the 4th plane is the one I start to fiddle with. In the end it leaves me with a single cube from line A and a 1x3 shape from lines B,C and D. Is there a way to make that code more efficient by combining lines B,C and D?
Or am I still clueless and there is a much more efficient way overall that I am completely ignoring? xD

map[x, 0, z] = 1;
map[x, 1, z] = 1;
map[x, 2, z] = 1;
map[1, 3, 1] = 1; A
map[1, 3, 4] = 1; B
map[2, 3, 4] = 1; C
map[3, 3, 4] = 1; D

Like I said I’m sure these questions are like “wow that’s easy” but total noob here lol

Edit: I’m also wondering. What if I just build my world with cubes and apply a similar isTransparent filter with a script to a parent empty game object containing the cubes?