Wannabe: The Perils of Hidden Voxel Removal

At least part of the problem Wannabe has with rendering is that we’re blindly drawing every voxel in a somewhat arbitrary manner.  Right now, it’s sorted only by Z, the rest stays in the order added to the initial grid.  We can trick the various RenderTypes to show the wrong thing pretty easily then, just by crafting the data properly.  Only reason things have been reasonably decent is because I’ve tended to add voxels from left to right, top to bottom, and the best looking renderer is up-and-to-the-left.  Any mistakes will get drawn over.

This overdraw, though, leads to glitches in rendering.  And worse, it’s slow.  Pull up the “deep heightmap” (just like the heightmap but with voxels all the way down to 0 for each point on the map) and you’ll see just how bad it is.  There’s no reason to draw each one!

Ugh, less than 5 fps!  Maybe we can fix both of these issues at once.  To do so properly, I’m going to have to tighten up some definitions and basic classes.  And I’ll have to clean up the readme which is wildly out of date at this point.

  • Position – an x, y, z coordinate.  Immutable.
  • Voxel – Basic “pixel” in Wannabe, consisting of a color and an immutable Position.
  • Grid – Collection of voxels.  Has a translation layer, so that whole collections of Voxels may be moved at once.  Implementations may vary on immutability, but grids should never have multiple voxels at the same position.
  • Neighbors – a Grid manages the a set of Voxels that are immediately adjacent to a voxel.  This provides hints about which sides to draw or whether to draw at all.

So, Neighbors is the new concept here, and it requires a tightening of the other concepts.  Since Wannabe is all about simplicity (is it, though?) all these changes are in favor of ease of implementation.  Position must become immutable so that the established Neighbors are never wrong.  Grids must reject voxels at the same location so that it can provide the right neighbors.  And then our engine can look at neighbor data and determine what to draw.

The neighbors concept is symmetric:  if I’m your neighbor then you’re my neighbor.  So each time a Voxel comes into to a Grid, we must find all the neighbors and introduce ourselves.  Which of course is annoying and repetitive.

Here’s what that looks like in SimpleGrid, where the following happens when adding a voxel to the grid:

private void populateNeighbors(Neighbors neighbors) {
  Translation workhorse = new Translation(neighbors.voxel.position);
  // Above:
  workhorse.z++;
  Neighbors otherNeighbors = positionToNeighbors.get(workhorse);
  neighbors.neighborAbove(otherNeighbors);
 
  // Below:
  workhorse.z -= 2;
  otherNeighbors = positionToNeighbors.get(workhorse);
  neighbors.neighborBelow(otherNeighbors);
 
  // North:
  workhorse.z++;
  workhorse.y--;
  otherNeighbors = positionToNeighbors.get(workhorse);
  neighbors.neighborNorth(otherNeighbors);
 
  // South:
  workhorse.y += 2;
  otherNeighbors = positionToNeighbors.get(workhorse);
  neighbors.neighborSouth(otherNeighbors);
 
  // East:
  workhorse.y--;
  workhorse.x++;
  otherNeighbors = positionToNeighbors.get(workhorse);
  neighbors.neighborEast(otherNeighbors);
 
  // West:
  workhorse.x -= 2;
  otherNeighbors = positionToNeighbors.get(workhorse);
  neighbors.neighborWest(otherNeighbors);
}

And one of those methods in Neighbor:

public void neighborNorth(Neighbors other) {
  north = other;
  if (other != null) {
    other.south = this;
  }
}

Ugly, ugly, but performance is decent:

That gets us in the realm of what we need.  As you can see, we’ve added some processing time to the grid, but have cut rendering time greatly.

Tracking neighbors lets us do a couple of things.  We can choose to ignore those voxels that are entirely surrounded since they might not be rendered.  That may not always be desired, which I spoke about in the last entry.  But the bigger benefit is when performing complex rendering, specifically, avoiding that work..

 

Acting upon neighbor data will be hard for some of the RenderTypes.   The cube-type renderers will need to start excluding sides, and if you recall from when I added cube sides, these are actually six-sided polygons.  Will it be easy to remove a part of one and have it still render?

Let’s run through an example.  If we’re drawing above-right to show height, then we’ll be seeing the north and east faces of a cube.  These are drawn, naturally, up and to the right.  If there is a north neighbor, then I want to skip drawing that side.  Likewise if there’s an east neighbor.  If both, then I draw no sides at all (because those neighbors’ sides will cover even that little corner).  Or if there’s only a neighbor north-east, I want to skip drawing that small square and any edge lines there.

I go into excruciating detail in the comment for RenderType.populateAboveLeft.  And then repeat the code subtly differently three more times below.

Conclusion

So, this works, but is generally terrible.  Is it worth adding a second and third data structure? Now there’s a list, a map (so we can find neighbors), and the neighbor linked data structure itself.  As mentioned, our raw data processing time has really gone up now even if we can shave lots of time off rendering.

Clearly, this really should be a single data structure.  Maybe just x,y,z -> voxel is all we need.  And perhaps Neighbors just needs to be the booleans we end up using in Rendered.  I’m sure this can be better.  Is there a data structure that can

  • Help with the neighbors concept
  • Help with occluded voxels
  • Help with filtering out a block of voxels in a given x,y,z to x’,y’,z’ bounds such that I don’t have to iterate each one

Next up: I think I’ll try to hit the Swing Alpha milestone before getting to more exotic activities.  But who knows, a better data structure may be on the books as well.

For the code involved in this entry, see all the commits in #16.

This entry was posted in Wannabe and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *