Jump to content

Voxel Cone Tracing Part 2 - Sparse Octree


Josh

2,398 views

 Share

At this point I have successfully created a sparse octree class and can insert voxelized meshes into it. An octree is a way of subdividing space into eight blocks at each level of the tree:

Image3.png.10776c0d93770f6a660c0e319bc12c21.png

A sparse octree doesn't create the subnodes until they are used. For voxel data, this can save a lot of memory.

It was difficult to get the rounding and all the math completely perfect (and it has to be completely perfect!) but now I have a nice voxel tree that can follow the camera around and is aligned correctly to the world axis and units. The code that inserts a voxel is pretty interesting: A voxel tree is created with a number of levels, and the size of the structure is equal to pow(2,levels). For example, an octree with 8 levels creates a 3D grid of 256x256x256 voxels. Individual voxels are then inserted to the top-level tree node, which recursively calls the SetSolid() function until the last level is reached. A voxel is marked as "solid" simply by having a voxel node at the last level (0). (GetChild() has the effect of finding the specified child and creating it if it doesn't exist yet.)

A bitwise flag is used to test which subnode should be called at this level. I didn't really work out the math, I just intuitively went with this solution and it worked as I expected:

	void VoxelTree::SetSolid(const int x, const int y, const int z, const bool solid)
	{
		int flag = pow(2, level);
		if (x < 0 or y < 0 or z < 0) return;
		if (x >= flag * 2 or y >= flag * 2 or z >= flag * 2) return;
		flag = pow(2, level - 1);
		int cx = 0;
		int cy = 0;
		int cz = 0;
		if ((flag & x) != 0) cx = 1;
		if ((flag & y) != 0) cy = 1;
		if ((flag & z) != 0) cz = 1;
		if (solid)
		{
			if (level > 0)
			{
				GetChild(cx, cy, cz)->SetSolid(x & ~flag, y & ~flag, z & ~flag, true);
			}
		}
		else
		{
			if (level > 0)
			{
				if (kids[cx][cy][cz] != nullptr)
				{
					kids[cx][cy][cz]->SetSolid(x & ~flag, y & ~flag, z & ~flag, false);
				}
			}
			else
			{
				//Remove self
				auto parent = this->parent.lock();
				Assert(parent->kids[position.x][position.y][position.y] == Self());
				parent->kids[position.x][position.y][position.y] = nullptr;
			}
		}
	}

The voxel tree is built by adding all scene entities into the tree. From there it was easy to implement a simple raycast to see if anything was above each voxel, and color it black if another voxel is hit:

Image1.thumb.jpg.501708f9018f4239206394f14dc0b1d9.jpg

And here is the same program using a higher resolution voxel tree. You can see it's not much of a stretch to implement ambient occlusion from here:

Image2.thumb.jpg.a52075df6466d4ce611389cdb951993d.jpg

At a voxel size of 0.01 meters (the first picture) the voxelization step took 19 milliseconds, so it looks like we're doing good on speed. I suspect the rest of this project will be more art than science. Stay tuned!

  • Like 5
  • Thanks 1
  • Upvote 2
 Share

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...