Friday, August 2, 2013

Lean Trees

Trees with thin trunks are problematic for a voxel engine. The reason is aliasing. When the tree is far away you still see its crown, but the trunk may have disappeared entirely because of the voxel resolution cannot hold such a thin feature anymore.

I was not ready to give up on skinny trees. They are abundant in colder climates, definitively a must-have for the engine. After some kicking and screaming, I managed to get it done:


Let's see how.

This problem is linked to the sampling theorem and Nyquist frequencies. In a nutshell what this means is you can only reconstruct some information if your sampling frequency is at least twice of the information's frequency. If that sounds weird to you, you are not alone. As it turns out, we live in a freaky reality. Things, regardless of them being real or virtual, have frequencies sort of baked into them and their arrangements. In this particular case the virtual tree trunks had frequencies that were higher than the voxel frequency used to represent them. These trunks would just disappear.

As long as you use a discrete method, like pixels or voxels, to represent a continuous reality you are guaranteed to suffer from these aliasing issues. In the case of pixels, we solved this problem by just throwing lots of memory and processing power to it. With voxels, the hardware is still far from being there.

So this limitation will be there for a while. We better learn it well. Once you think about it, you see the limit is not really how thin a feature can be, but how close two thin features can be. If your voxel size is 1 meter, you can still do a golf ball with them. What you cannot do is have another golf ball next to it, unless you place it at 2 meters.

Maybe this image will help explain it better:


This image is a 2D representation of voxels, which are 3D, so you will need to extrapolate a little bit. The eight squares are voxels. The two red dots are two balls. Each voxel measures "d", which for the sake of argument we will make equal to one meter. We can engage voxels 1, 2, 3 and 4 to represent the first ball. This is how we can achieve a feature inside these voxels that is much smaller than "d". In fact, it could be really small, near zero.

So even huge voxels could encode a tiny feature. The real limit is how close the next feature can appear. In the image you see we cannot use voxels 2, 5, 4 and 7 to add another ball there. This is because voxels 2 and 4 area already engaged into expressing the first ball. So the closest ball can be placed two voxels away, using voxels 5, 6, 7 and 8. The distance between the two balls cannot be less than two meters, that is 2 times "d". This is the sampling theorem rearing its ugly head again.

But this was the key to my solution. Because of how forests are, I did not need two thin trees one immediately next to another after all. I just needed the thin trunks to align with the largest voxels that would still need to display the trunk. This involved shifting the tree a clever amount, which was never too much to disrupt the distribution of trees in the forest.

If you look at the forest screenshot again, you will see some fairly thin trunks in the distance. These trunks are an order of magnitude thinner than  the voxels used to represent them.


19 comments:

  1. Sounds cool, so does this have something to do with marching cubes?
    Can you explain why you cant have, say, 2 trees in the area of 6 voxels?

    ReplyDelete
    Replies
    1. It is pretty much the same with marching cubes. If you use only 6 voxels you will have one edge that will get two surface crossings. Marching cubes won't be able to "see" that. It will think the entire thing is solid so the two balls will be merged.

      Delete
  2. So if I understand this right, if an edge contains two zero crossings, you move one of them some special distance away, and then you keep them from being merged, correct?

    ReplyDelete
    Replies
    1. Yes, but it is more than just edge crossings. The second ball could be anywhere, even with no edge crossings at all. It has to be shifted so it lands on the spot we know it can be represented.

      Delete
    2. So typically with dual contouring you find edge crossings, use normals and find a good point in the cube for the vertex. You however are now finding crossings that exist entirely within a single cube, but if you were just looking at the edges you would miss it.

      Delete
    3. You cannot find crossings unless they are over an edge. That is what makes it a crossing actually. If the feature is fully inside a voxel, it is never seen. The idea in this post is that sometimes you are allowed to place your features in awareness of your voxel grid. If you can get away with that, you will get a lot more mileage of fairly large voxels.

      Delete
    4. Gotcha, when you said "The second ball could be anywhere, even with no edge crossings at all" I assumed [no crossings at all] meant that the second ball was completely in a voxel. I'm guessing you mean you need to move it such that it will have the desired crossings, and thus be represented. Thank you!

      Delete
  3. This sounds like a great solution to this specific problem, but I can't help but think that there are cases where you might have two small trunks growing next to each other. I really love your approach to all this, but I wonder if you've started to explore the idea of marrying traditional mesh-instances approaches with the voxel approach? For example, larger trees use voxels but smaller trees are instead instanced lod meshes pulled from a library? It appears that you're doing something like this with the grass, so I'm just wondering if that's another way you could solve the problem of having high frequency detail in a low-frequency rendering region.

    ReplyDelete
    Replies
    1. Trees would have to be unrealistically close for that to be a problem. The voxel size is small enough to have actually several free voxels between trunks.

      Anyway your argument stands. This is just a trick for tree trunks, but this problem is everywhere.

      Giving up on voxels and bringing meshes in is always an option. But not a solution. In that regard it is not very interesting to me. It does work very well.

      Delete
  4. Would it make sense to mark certain sections of the octree (or whatever it's called, I think I remember you saying you're not using it anymore...) as being a higher-detail feature, so it keeps it's near LOD detail one LOD-skirt farther out?

    ReplyDelete
  5. These trees look good so far!
    What i would like, would be an Video, where you would just be building something, maybe a Little Castle/Tower Thing or maybe a little village, that would be cool.

    ReplyDelete
  6. Oh and, will we be able to realisticaly cut down trees with a falling Animation ? that would be quite amazing.

    ReplyDelete
    Replies
    1. I believe that question has been addressed several times in the comments, and I believe the general answer was "No" or "Not at any time soon."
      To allow you to cut them down, first trees would have to be detectable and aware of all their parts (Which they arent atm, as they are just parts of the world), then, atleast every time you remove a bit from the tree, calculations would have to be made to see if it falls over, if you use animations, it will look bad half the time, as you will have trees which fall in the same direction every time, fall through buildings, rocks, other trees etc. and the ground if they are on a slope. If you use physics, you will have to do physics calculations on a voxel structure, which I believe is quite processor intensive...
      Though Miguel might be able to give you the specifics =P.

      Delete
  7. So the problem is, that the LOD system creates aliasing only on distant trunks?

    Maybe allowing voxels to be semi transparent would work, so the fine detail of air between trunks gets averaged to a large semi transparent voxel.
    In terms of frequencies: the LOD system should have a lowpass/average step, because every high quality sampling rate conversion in signal Processing uses a lowpass filter to reduce aliasing.

    tl;dr: mipmapping for voxels?

    ReplyDelete
    Replies
    1. Yes, LOD system creates the worst aliasing in distant trunks.

      I am sure there are and will be plenty of tricks to deal with this. If you have links to any papers they will be very appreciated.

      Delete
  8. Miguel Your are a complete and utter genius! Its very exciting to see your breakthrough's :) Good luck!

    ReplyDelete
    Replies
    1. I second this !
      Miguel, I've always been amazed by how easily you get things working and by the creative solutions you find.

      Delete
  9. Will we ever see voxels made of materials with different characteristics which would let trees to break like trees and metal to bend instead being crushed (or even material which is elastic, etc)?

    ReplyDelete
  10. This is a bit of a long shot, but after reading your 'voxels-to-polygons' post, I can't help feeling there's some way of storing sub-voxel position information in the normal of a voxel. Let's say that the normal for a voxel is essentially a 3-float point with a length of 1, that would store the position of the face for that voxel. In a situation where that voxel is 10% full and the neighbours are empty then you have a small blob in that voxel space, you could use the normal to offset the position of the blob by using the normal as the direction of the offset, and the normal's length as the amplitude of the offset. You've then got the problem of connecting the offset blobs vertically for trunks, but not horizontally to neighbouring trees and I can't see a good way around that right now, other that storing some sort of matrix-like information in one of the values...

    ReplyDelete