Volumes Of Fun
http://www.volumesoffun.com/phpBB3/

Changes to basic voxel types
http://www.volumesoffun.com/phpBB3/viewtopic.php?f=14&t=306		 Page 1 of 4
Author:  David Williams [ Wed Jan 04, 2012 8:40 am ]
Post subject:  Changes to basic voxel types
Hey all,

Progress on PolyVox is slow at the moment for a number of reasons, but I did find some time to work on it over Chrsitmas. It seemed like a good chance to start addressing some of the rough edges which PolyVox has. I'm generally happy with the design of the library, but a number of small issues have been pointed out in the forums over the last few months.

I decided to work from the bottom up so I started making some changes to the voxel classes. The idea being that after these are in shape I'll move onto the volumes, then the surface extractors, and so on. However, as I traveled back to Holland on New Years Day I was unlucky enough to have my laptop stolen (and my passport - which is a pain when you work in a foreign country!).

Anyway, I hadn't committed my work, but before I start retyping it I thought I should share the basic ideas to get feedback. The changes I was making to the voxel clases are:

  • Expose density/material types: In general the algorithms in PolyVox work for any voxel type which matches the required interface. PolyVox doesn't know much about the type it is operating on and this can cause problems. For example, if we are averaging a group of voxels we want to sum the densities and divide by the number of voxels... but which type should be used to store the sum? The densities could be stored internally as floats or ints, and using the wrong type can cause casting warning and range/precision loss. Therefore, the voxel classes should expose the type they use internaly so you can say something like (untested):
    Code:
    template <typename VoxelType>
    void someFunc(LargeVolume<VoxelType> volume)
    {
      VoxelType::DensityType voxelValue = volume.getVoxelAt(...).getDensity();
    }

    The point here is that voxelValue will always take on the correct type.

  • Remove getThreshold(): At the moment each voxel type defines the density threshold which is used for the marching cubes surface extractor. This doesn't really make sense as this value should be passed to the extractor as a parameter. So I'll remove it from the voxel classes, and add a parameter to the marching cubes surface extractor which defaults to halfway between the min and max densities. This will also affect the Raycast classes.

  • Move some properties to type traits: At the moment the voxel classes provide functions for getting the min and max densities. These will be moved to type traits, similar to how std::numeric_limits works. A potential advantage here is that these properties can be added to primitive types such as floats and ints. Not sure if it is useful though, but volumes are able to store primitive types so it may be. Code to set a voxel to it's maximum density would then look as follows:

    Code:
    voxel.setDensity( VoxelTraits<Your_Voxel_Type_Here>::MaxDensity );

  • Detect presence of member functions: This is the most involved change. As an example, consider the VolumeResampler which scales volume data to be a different size. For each output voxel, the VolumeResampler reads a number of input densities and performs interpolation on them to compute a new value. But what if you are working with a Material volume which doesn't have densities? In this case the Material class provides a fallback implementation of getDensity() which makes up a density based on the material. The VolumeResampler then wastes time interpolating this density, which it then can't write back as the setDensity() member of Material is also a dummy which does nothing (or asserts, I forget which).

    Interestingly, in C++ it it actually possible to use SFINAE to detect the presence of member functions at compile time. I suggest PolyVox uses this feature to avoid the case described above. The VolumeResampler would test (at compile time!) whether the provided voxel type has a setDensity() method, and if not it would not bother doing the interpolation. The code might then look something like the following:

    Code:
    template <typename VoxelType>
    void resamplingFunction(LargeVolume<VoxelType> src, LargeVolume<VoxelType> dest)
    {
      ...
      if(TestHasSetDensity<VoxelType>::result)
      {
        //Do work to read and interpolate densities
      }
      ...
      if(TestHasSetMaterial<VoxelType>::result)
      {
        //Do work to copy materials
      }
      ...
    }


    Note that these tests are optional in user code - you could still provide the dummy getters/setters if you prefer. Also, you are probably coding with known voxel types (you know whether it has a material and/or density) so you can make sure you only call valid functions anyway. This change is mostly internal to PolyVox as it has to work on all voxel types.

    This should have some performance benefits, but to be honest I'm mostly doing it as a code cleanup and from a conceptual point of view.

Ok, that was a long post! Let us know if you have any particular thoughts about these changes.
Author:  ker [ Wed Jan 04, 2012 10:59 am ]
Post subject:  Re: Changes to basic voxel types
ugh, I guess the probability of finding the stolen stuff again goes to zero?
I hope not too much was lost.

David Williams wrote:
Expose density/material types

I've already seen this inside the voxel templates.
I tried using a c++11 "enum class MyMaterial : uint8_t" which will not automatically be cast to uint8_t.
Since the extractors don't use the custom type this fails obviously, but got me to a completely other point.
The PositionMaterial(Normal) templates store a float for the material.
You said it's there so one could dump the std::vector<PositionMaterial> directly to a gl/dx buffer, but you also wrote that this won't be done anymore in the future.
So either PositionMaterial and the Extractors use the type, or a getMaterialID() function is needed that casts to uint*_t.

Also the default value of 0 won't work with custom types except if they have a constructor for a numeric type. maybe this could be a template parameter defaulting to 0?
(the last part I did by creating my own Material class, but I'm guessing many people use enums and might use enum classes in the future)

David Williams wrote:
Remove getThreshold():

so the Material<> template's getDensity() functions won't make any sense anymore... more like a isSolid() function?
obviously this will forbid using MaterialDensityPair inside CubicExtractor and Material inside MarchingCubesExtractor.
Author:  milliams [ Wed Jan 04, 2012 2:09 pm ]
Post subject:  Re: Changes to basic voxel types
David Williams wrote:
  • Expose density/material types: In general the algorithms in PolyVox work for any voxel type which matches the required interface. PolyVox doesn't know much about the type it is operating on and this can cause problems. For example, if we are averaging a group of voxels we want to sum the densities and divide by the number of voxels... but which type should be used to store the sum? The densities could be stored internally as floats or ints, and using the wrong type can cause casting warning and range/precision loss. Therefore, the voxel classes should expose the type they use internaly so you can say something like (untested):
    Code:
    template <typename VoxelType>
    void someFunc(LargeVolume<VoxelType> volume)
    {
      VoxelType::DensityType voxelValue = volume.getVoxelAt(...).getDensity();
    }

    The point here is that voxelValue will always take on the correct type.

With C++11 you should be able to simply replace this with an auto. auto and decltype are two C++11 features which will make working with templates much easier but as much as I'd like to, I worry it might still be a bit early to be relying on them? We can't really make these a compile-time option like other C++11 stuff we use (however it's been in GCC for nearly 3 years and VS since VS2010) so it's an all or nothing choice that will have to be made. Maybe for a later release?

David Williams wrote:
  • Remove getThreshold(): At the moment each voxel type defines the density threshold which is used for the marching cubes surface extractor. This doesn't really make sense as this value should be passed to the extractor as a parameter. So I'll remove it from the voxel classes, and add a parameter to the marching cubes surface extractor which defaults to halfway between the min and max densities. This will also affect the Raycast classes.

Makes sense to me. I agree that the voxel types should be as simple as possible.
Author:  David Williams [ Wed Jan 04, 2012 2:31 pm ]
Post subject:  Re: Changes to basic voxel types
ker wrote:
ugh, I guess the probability of finding the stolen stuff again goes to zero?
I hope not too much was lost.


Pretty much. Besides my laptop and passport they only got my dirty socks, so that was satisfying ;-)

ker wrote:
David Williams wrote:
Expose density/material types

I've already seen this inside the voxel templates.


Yep, I actually added this a couple of weeks a go, but the rest was lost.

ker wrote:
The PositionMaterial(Normal) templates store a float for the material.
You said it's there so one could dump the std::vector<PositionMaterial> directly to a gl/dx buffer, but you also wrote that this won't be done anymore in the future.
So either PositionMaterial and the Extractors use the type, or a getMaterialID() function is needed that casts to uint*_t.


I think that the voxel's getMaterial() function should return MaterialType rather than returning an int. That said, I think that materials should always be integer values, where as densities could be integer or floating point. Unless you can think of a reason why non-integer materials woul be useful?

Regarding the PositionMaterial(Normal) classes, I'm currently thinking they might be removed and the surface extractors would declare their own formats as nested classes. So for example you could declare a vertex of format 'CubicSurfaceExtractor::VertexFormat'. The exact format would vary between surface extractors but templatised code would always access it in the same way. Does that make sense? But I'm not there yet.

ker wrote:
Also the default value of 0 won't work with custom types except if they have a constructor for a numeric type. maybe this could be a template parameter defaulting to 0?
(the last part I did by creating my own Material class, but I'm guessing many people use enums and might use enum classes in the future)


I'm not familiar with enum classes (is this C++11?) but I will keep this issue in mind.

ker wrote:
David Williams wrote:
Remove getThreshold():

so the Material<> template's getDensity() functions won't make any sense anymore... more like a isSolid() function?
obviously this will forbid using MaterialDensityPair inside CubicExtractor and Material inside MarchingCubesExtractor.


In the case of the CubicSurfaceExtractor I'm imagining that it will only use materials and will never look at densities. I think this is ok, as it can't do anything sensible with the densities anyway? The marching cubes extractor will always use densities, and will also use the SFINAE principle described above to use materials only if they exist. So I don't think we lose any functionality here.

Regarding some kind of 'isSolid()' function... this also need consideration with regards to transparency. My current felling is that isSolid() is not enough. I think the user needs a way to tell the CubicSurfaceExtractor whether a quad should be generated for any pair of material IDs. E.g. if you have transparent red next to transparent blue, you would probably (?) still want a quad between them. This information could be conveyed with a callback, a lookup table, or some other approach. I think that the marching cubes surface extractor probably won't support transparency but I'm not sure yet.
Author:  ker [ Wed Jan 04, 2012 3:49 pm ]
Post subject:  Re: Changes to basic voxel types
David Williams wrote:
That said, I think that materials should always be integer values

David Williams wrote:
I'm not familiar with enum classes (is this C++11?) but I will keep this issue in mind.


enum classes are type safe, they cannot be cast automatically to int or other enum classes or anything else for that matter.
also they only put their defined enums inside their own namespace.

if those should be allowed, just using integer values will not work or require manual casts.
Author:  milliams [ Wed Jan 04, 2012 4:09 pm ]
Post subject:  Re: Changes to basic voxel types
David Williams wrote:
I'm not familiar with enum classes (is this C++11?) but I will keep this issue in mind.
Enum classes are strongly-typed enums (also see the proposal). They are available in GCC since version 4.4 (3 years ago) and VS since VC11 so like many C++11 things, we would have to make an explicit decision to start supporting/using it.
Author:  ker [ Wed Jan 04, 2012 4:26 pm ]
Post subject:  Re: Changes to basic voxel types
milliams wrote:
David Williams wrote:
I'm not familiar with enum classes (is this C++11?) but I will keep this issue in mind.
Enum classes are strongly-typed enums (also see the proposal). They are available in GCC since version 4.4 (3 years ago) and VS since VC11 so like many C++11 things, we would have to make an explicit decision to start supporting/using it.


actually not in this case, as they would be template parameters. If it works with enum classes, it works with integers, too. Just the other direction isn't really assured.
Author:  David Williams [ Thu Jan 05, 2012 9:16 am ]
Post subject:  Re: Changes to basic voxel types
Ok, regarding enum classes, it seems that these are basically 'enums done right'. As such I think it would be nice if users can use an enum class for the material instead of an int. This might cause a few issues (currently the marching cubes surface extractor uses the 'smallest' of the two neighbouring material IDs as the vertex material, and it seems this concept of 'smallest' might not make sense in the same way) but nothing we can't overcome (guess we can still cast if we have to).

I think we won't actually use enum classes within PolyVox as it forces C++11, but it's useful if we can allow users to do so in their own code. I think this same principle applies to the use of 'auto' as pointed out by Matt, and the new for loops as pointed out by ker.

I hope to get a new laptop over the coming week and then I'll take a crack at this.
Author:  David Williams [ Tue Jan 10, 2012 2:06 pm ]
Post subject:  Re: Changes to basic voxel types
Note: The surface extractor discussion has been split to here: http://www.volumesoffun.com/phpBB3/viewtopic.php?f=14&t=310
Author:  David Williams [ Fri Jan 13, 2012 10:53 pm ]
Post subject:  Re: Changes to basic voxel types
I just wanted to say that I've started making these changes, so Git might me in a broken and/or non-compiling state for the next few days. I'll post updates in this thread.
Page 1 of 4 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/