Jump to content
  • Advertisement
Sign in to follow this  
Brift

Unity Unity 3d Octree Voxel data structure via recursion

This topic is 1433 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi game developers,
 
I had a question about recursively creating an octree data structure in Unity 3d for the purpose of creating blocky voxel landscape similar to what is found in Minecraft.  Now before you tell me this has been done many times over and I should give up this endeavor I wish to say that I am implementing this as a school project.  My goal is to make an approximately 1024 x 1024 x 256 area of editable blocks by starting out with a 1024 cube and putting in null for the upper cubes in the children. 
 
I tried creating a class that called itself in the start and Unity gives me an error about not being able to create game objects with the new keyword.  My instructors have only used C# in XNA and the solution they provided me with doesn't work in a Unity context.  I know that there are many people who have worked with voxels and octrees inside of Unity, so I humbly request some help getting started.  I am hoping to have a tree that can be referenced by the voxels for things like neighbors and so on. 

 

Share this post


Link to post
Share on other sites
Advertisement

Unity is unusual in that a script is something that you attach to a GameObject, not something that extends a GameObject. This means that instantiating it will be a little different.

 

You have two main options:

  1. If the thing you're creating is a concrete physical thing that should be visible in your game, your easiest option is instantiating a prefab. This will give you a game object with all attached colliders, scripts, properties, etc. Then you can set any properties that should be different in your code. See the documentation.
  2. Otherwise if what you're creating is more conceptual, make a class that doesn't extend Monobehavior. It won't need to be attached to a GameObject at all. Just remember that for your code to be executed, at some point you will have to run a script that is attached to a GameObject. So you may have a script attached to your Camera with an OnStart method (for example) which instantiates your octree.

Share this post


Link to post
Share on other sites

Here's an article I wrote up on Octrees a few months back. It's written in C# on XNA, but you should be able to port the code over to Unity.

 

So... the code isn't really the important part for you. What you want is a solid grasp of the fundamentals of how Octrees and voxels work and are implemented. I believe that if you have a firm grasp of how any system works, writing the code to implement it is mostly just a formality / exercise.

As for the null nodes in an octree - You don't actually want to do this manually. You want to create a public method which acts as an interface to let users insert objects into the octree. The user shouldn't care about *how* or *when* or *where* the object is in the tree, so long as its in there and can be retrieved quickly. If your octree builder is correctly implemented, it will automatically take on the structure that you're thinking of.

As far as voxels go... I haven't implemented them in depth myself, but they're pretty straight forward. Just start by creating a "cube" object and rendering it. Then give all of your cubes an unsigned integer to act as a differentiating ID, (ie, grass = 1, dirt = 2, etc). Cubes may be sufficient for a school project, but if you really want to go the extra mile, you can create voxel cubes which have angled slopes (such as ramps, or inset corners). You may be interested in looking up the marching cubes algorithm, which has been around for decades.

If this weren't an academic exercise, I would completely skip the octree implementation and let the Unity engine figure out how it wants to do object storage and collision detection -- that's the point of using an engine (it might be interesting to see if you're doing double work on this: unity has its own internal object storage datastructure and you add yours as well).

Share this post


Link to post
Share on other sites

@ Jefferytitan My goal is to create a tree with physical objects at the bottom most level or leaf nodes.  The idea behind voxels is that I will only draw the faces where one block is filled and it's neighboring block is empty.  In this way I'm not drawing lots of extra faces and killing performance.  So the upper part of the tree will be conceptual and the bottom will actually have the mesh and colliders and all.  I'm thinking that I might just keep all of the tree conceptual and instantiate the prefabs separately.

 

@Slayemin I have read your article, and while it was useful for object collisions what I am working towards is using the octree structure to draw the blocks in the world.

 

I am actually working on implementing a different kind of voxel that is a triangular prism with equilateral triangles for top and bottom and squares for sides( I have a simple Html5 demo of what I'm trying to do at http://apoidgames.web44.net/wedge.html).  So I won't be able to use the cube prefab or cubic shapes in general.  To accomplish this I have adapted the cubic coordinate system for hexagons from http://www.redblobgames.com/grids/hexagons and made it 3d.  Basically I am replacing the X and Z axes and replacing them with Q, R, and S axes, which I put together another simple 2d demo of at http://apoidgames.web44.net/trigridX.html to show what I mean.  One of the coordinates is redundant, which means I could represent all of the points with only 2 of these axes, but because of this redundancy I have the attribute of for every QRS value the sum of all the values will always equal 0 ( which has some very useful properties). In the end I will have QRSY coordinates. The octree data structure will allow me to create space partitioning on which I would be able to create the world of what I call triblocks.  I could accomplish the same thing using a 4 dimensional array, three dimensions for the XYZ coordinates and 1 more to split each block in half, but I think that an octree would be more efficient way to store the world.

 

My biggest problem is that my university training has given me a ton of theory and not a lot of practice, so I know enough to know that this would be a good way to do this, and not enough to be able to implement the theory.  So that is why I was looking for some help from someone who has implemented the octree for the purpose of voxel rendering to help me out.  I may end up implementing this in XNA instead since I have tutors here at school who know that system better.  I just don't like the idea of implementing my own collisions and also being so limited as far as what platform this would run on.

Edited by Brift

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!