Post by Kyle Gagner on Dec 28, 2011 2:21:10 GMT -5
Sometimes I have very good ideas and I am afraid that they will be stolen. I believe (possibly mistakenly) that the best way to protect my ideas is to prove that I had them first. So... This is my idea...
Instead of representing voxels in an octree, represent them as a simple three dimensional "grid". Voxels that are not opaque can have a number associated with them that represents the size of a bounding box centered on that voxel that does not contain any whole opaque voxels. The sides of the bounding box must not lie in the same planes as the bounds of any voxels (if they did the raycasting algorithm would have to be unnecessarily complex). For optimum performance, the outside of each bounding box would intersect at least one opaque voxel, but for compression purposes this would likely not be true for many bounding boxes.
Raycasting would be simple using a parametric equation for a ray to cast. Find the size of the bounding box of the voxel which the origin of the ray lies in. Find the intersection where the ray exits that box. Now find the voxel in which that intersection lies. If it is an opaque voxel, return that voxel (maybe a pointer to it, or perhaps just its color), otherwise repeat the same action using this intersection point instead of the origin. I suspect that algorithm would quickly find the first intersection with an opaque voxel in most cases, making this approach possibly better than raycasting voxel octrees (certainly, it seems much more simple to program).
Several variations on this idea are possible. For example: instead of storing the size of a bounding box, one could store the locations of two opposite corners of the box. This could improve the speed of the algorithm.
Immediately, using an octree structure to store the sizes/corners of bounding boxes comes to mind as a scheme for compression. To illustrate how this would work, consider a 4 by 4 by 4 voxel world. Now suppose you want to compress the bounding box sizes data. You could store the bounding box sizes of the voxels in one quadrant by simply finding the smallest bounding box size in that region and using that. This could be done with a larger world, at any iteration level. Simply removing one level of data would probably have little impact on performance and cut the storage space required by almost eightfold (I say almost because the octree data structure requires memory as well). Moving two levels up the octree removes almost all but one 64th of the data. This could also be done selectively, compressing data more in large open spaces with no opaque voxels, and less closer to opaque voxels. In fact, if it is not done selectively, there is little point in using an octree, and the bounding boxes of transparent voxels could be stored in a voxel structure that simply has a lower resolution than the structure containing the opaque voxels.
I think that this will be easy to program and probably at least as effective as voxel octrees for my purposes. In voxel octrees, you can usually choose to terminate the iteration before reaching a leaf in the octree structure, since larger parent voxels with properties that are the average of their childrens' approximate their children quite well at a distance. My idea lacks this capability, though it would probably not be too difficult to introduce multiple models at different levels of detail, much as is done with current triangle meshes.
Semitransparent voxels (fog/smoke) would also be possible using this idea. Bounding boxes would contain only regions of the same density and color.
Now it is late, and way past my bedtime, and my writing was probably all muddled because I am very tired. But there is my idea, in writing, 12/27/2011. So nobody can say they had it before me.
Edit:
As an afterthought... The bounding boxes actually SHOULD have sides that all lie in the planes that the sides of voxels lie in. This makes the algorithm just slightly more complex because one must find which voxel the ray is passing into (as opposed to the adjacent voxel it is passing out of). It would have been nice to avoid that programming inconvenience, but I see now that it cannot be avoided.
Instead of representing voxels in an octree, represent them as a simple three dimensional "grid". Voxels that are not opaque can have a number associated with them that represents the size of a bounding box centered on that voxel that does not contain any whole opaque voxels. The sides of the bounding box must not lie in the same planes as the bounds of any voxels (if they did the raycasting algorithm would have to be unnecessarily complex). For optimum performance, the outside of each bounding box would intersect at least one opaque voxel, but for compression purposes this would likely not be true for many bounding boxes.
Raycasting would be simple using a parametric equation for a ray to cast. Find the size of the bounding box of the voxel which the origin of the ray lies in. Find the intersection where the ray exits that box. Now find the voxel in which that intersection lies. If it is an opaque voxel, return that voxel (maybe a pointer to it, or perhaps just its color), otherwise repeat the same action using this intersection point instead of the origin. I suspect that algorithm would quickly find the first intersection with an opaque voxel in most cases, making this approach possibly better than raycasting voxel octrees (certainly, it seems much more simple to program).
Several variations on this idea are possible. For example: instead of storing the size of a bounding box, one could store the locations of two opposite corners of the box. This could improve the speed of the algorithm.
Immediately, using an octree structure to store the sizes/corners of bounding boxes comes to mind as a scheme for compression. To illustrate how this would work, consider a 4 by 4 by 4 voxel world. Now suppose you want to compress the bounding box sizes data. You could store the bounding box sizes of the voxels in one quadrant by simply finding the smallest bounding box size in that region and using that. This could be done with a larger world, at any iteration level. Simply removing one level of data would probably have little impact on performance and cut the storage space required by almost eightfold (I say almost because the octree data structure requires memory as well). Moving two levels up the octree removes almost all but one 64th of the data. This could also be done selectively, compressing data more in large open spaces with no opaque voxels, and less closer to opaque voxels. In fact, if it is not done selectively, there is little point in using an octree, and the bounding boxes of transparent voxels could be stored in a voxel structure that simply has a lower resolution than the structure containing the opaque voxels.
I think that this will be easy to program and probably at least as effective as voxel octrees for my purposes. In voxel octrees, you can usually choose to terminate the iteration before reaching a leaf in the octree structure, since larger parent voxels with properties that are the average of their childrens' approximate their children quite well at a distance. My idea lacks this capability, though it would probably not be too difficult to introduce multiple models at different levels of detail, much as is done with current triangle meshes.
Semitransparent voxels (fog/smoke) would also be possible using this idea. Bounding boxes would contain only regions of the same density and color.
Now it is late, and way past my bedtime, and my writing was probably all muddled because I am very tired. But there is my idea, in writing, 12/27/2011. So nobody can say they had it before me.
Edit:
As an afterthought... The bounding boxes actually SHOULD have sides that all lie in the planes that the sides of voxels lie in. This makes the algorithm just slightly more complex because one must find which voxel the ray is passing into (as opposed to the adjacent voxel it is passing out of). It would have been nice to avoid that programming inconvenience, but I see now that it cannot be avoided.