More/different raycast options

Issue #22 resolved
Matt Williams
created an issue

The two current raycast functions were presumably added specifically for the purpose of facilitating the ambient occlusion calculator. However, for a number of common cases, they're not as usable -- requiring saving state in a callback functor for example.

I propose adding a new (set of) functions(s) to make a few common cases directly easy. For example, during work on the Python example using the cubic extractor, the most common case for needing a raycast is to either find out the voxel that the cursor is currently pointing at (in order to change material or remove it) or to find the last non-empty voxel before it (in order to set the voxel value from empty to some value).

To this end, I'm thinking of a function which looks something like:

Vector3DUint32 raycastPickVoxel(VolumeType* volData,
                                const Vector3DFloat& v3dStart,
                                const Vector3DFloat& v3dDirAndLength);

This would return the first non-empty voxel it came across. Perhaps to make it more flexible, instead of being fixed to return the first non-empty voxel, it could take an argument for the a voxel value to count as a hit:

Vector3DUint32 raycastPickVoxel(VolumeType* volData,
                                const Vector3DFloat& v3dStart,
                                const Vector3DFloat& v3dDirAndLength,
                                VoxelType valueThatIsAHit);

or, in fact instead of a value, it could take a simple callback which returns a bool depending on whether it's a hit or not. In this last case it is very similar to the current function except the raycast returns a position instead of a RayCastResult.

Perhaps, given this last fact, the new raycast could simply be implemented as a wrapper around the existing functions. Regardless of the specifice, it would be nice to have a simple picking function available in my Python example.

Any thoughts about the API or even the usefulness of such functions?

Comments (17)

  1. David Williams

    I agree with this in principle, but then the tricky part is deciding what functionality to include. It's amusing because I can see you following the same thought process that I had, in that first you want to know what voxel was hit, then you also want to know the previous voxel, and then also to specify an example of what should be 'solid'. A voxel can have multiple properties of course, at which point you need a way to determine which properties make a voxel solid... and before you know it you're back to callbacks :-)

    But I can imagine that callbacks are tricky to wrap in Python, and there may well be some performance overhead too. So I don't mind adding simplified versions if you can decide what they should do. They probably should be wrappers around the existing functionality though, to avoid code duplication.

  2. David Williams

    Ok, reading though you post again I realise your not arguing against the use of callbacks as such, but instead against the fact that callbacks get a little complex because they have to maintain state. I do agree this is a little awkward.

    In this sense I think your proposed functions are a good idea, but there are a couple of things to be aware of. Rather than just returning the hit position I think it is useful to also return the previous position - i.e you could wrap these into some kind of structure. You should also consider that the ray might not hit anything so you probably want a flag in there too.

    I think deciding the stop criteria is the more difficult aspect. You can still choose to use a callback here but it could be simpler than the ones currently used, and would not need to maintain any state. It could just return a bool based on the voxel position such as 'bool isVoxelSolid(const VoxelType& voxel)'.

    Alternatively you can provide an example of a solid voxel as you describe (or perhaps an example of a non-solid voxel makes more sense... an application probably only has one of those?).

    Actually it's probably appropriate to provide both callback and example-based forms as function overloads? This would handle most peoples cases, and they could fall back on the lower-level API if they really needed to.

  3. Matt Williams reporter

    I've looked into this again and I wanted to see if you had any comments on the following.

    I've implemented a raycast function called raycastPickWithEndpoints since it's main purpose is position picking rather than testing for AO. The declaration looks like:

    template<typename VolumeType>
    PickResult raycastPickWithEndpoints(VolumeType* volData, 
                                        const Vector3DFloat& v3dStart,
                                        const Vector3DFloat& v3dEnd,
                                        const typename VolumeType::VoxelType& emptyValue
                                          = typename VolumeType::VoxelType());

    It's very similar in form to the existing raycastWithEndpoints. There's also a corresponding raycastPickWithDirection. The argument emptyValue is the value of a voxel defined as 'empty' by the user. This is usually 0 (or 0.0) and it defaults to the default-constructed value of the voxel type..

    It returns a PickResult which looks like:

    struct PickResult
      explicit PickResult(const Vector3DInt32& startVoxel) : 
      bool didHit;
      Vector3DInt32 hitVoxel;
      Vector3DInt32 previousVoxel;

    So it can tell you the solid voxel it hit, the voxel it was in before that as well as boolean to say whether it actually hit anything.

    Do you have any thoughts on this design? Do you think it is worth also defining a version which takes a callback? I'm not sure it is yet as I would think that this covers most use cases.

    I've written a test for this version of the code and I'll commit it in a branch if you think it looks mostly sensible.

  4. David Williams

    Sorry, I almost missed this post. I think this suggestion is very sensible - I like the idea of building slightly higher-level picking functionality on top of the raycasting. My only real comments would be on the naming conventions.

    Firstly, I wonder whether we need both pickWithEndpoints and pickWithDirections version. With raycasting these make sense - the direction version might be used to test whether bullets hit something when fired from a gun, while the endpoints version might be used to determine whether two charachters can see eachother. But when picking you don't know the endpoint (by definition - that's why you are picking). Given this, ‭I wonder whether the function name can be simplified to just pickVoxel() or something?

    Next, I wonder whether 'emptyValue' can be 'emptyVoxelExample' or something like that?

    Lastly, will this go in raycast.h or a new picking.h? I guess the user doesn't actually need to know that raycasting is involved at all?

  5. Matt Williams reporter

    I think you're right about it not needing both *EndPoint and *Direction versions and so pickVoxel() sounds like a good name to me. The second vector argument defining the direction obviously implicitly contains a length and I was just trying to avoid the confusion that people had with the raycasting which prompted the original *EndPoint and *Direction versions. Overall, I agree that a single simple version is better and I'll just try to make this very clear in the documentation.

    emptyVoxelExample sounds like a better name, I'll change it to that.

    It's currently sitting in raycast.h and raycast.inl since it's just a copy-paste version of the existing raycast functions. It should be possible to implement it by actually calling the real raycast functions with an appropriate functor rather than what I'm doing at the moment with tracking state inside the main loop. Regardless, if you think it's more appropriate API-wise to have it in a picking.h then I'll do that.

    I'll make the above changes and then upload it into a branch. I'll also post about it on the forums to see if anyone has any opinions on the API.

  6. David Williams

    Yep, sounds good. I think there shouldn't be any confusion over direction vs. endpoint as someone doing picking will only have the direction, but it should be made clear that the direction also includes the length. Unless you think the 'maximum pick range' should be a separate parameter? I guess it's best to keep it consistent with the existing raycast code (though maybe that should have a maximum range...?).

    And yes, I think picking.h is better. It helps keep things a bit tidier.

  7. Matt Williams reporter

    Ok, so this should be available in f98959f92a now. Hopefully it will build fine on Windows but it's possible some of the judicious use of typename might throw it off.

    I've also committed a simple test for it and enabled it in the bindings.

  8. David Williams

    Great stuff, at some point soon I shall pull this into the Cubiquity branch and test it in Cubiquity. It looks like there are some minor compilation issues (typename) on Windows so I'll probably fix those on Monday.

  9. David Williams
    • changed status to open

    Unfortunately I haven't been able to resolve the compilation issues. the only way I can get it to compile to remove the default parameter for emptyVoxelExample. Actually I already have an example of doing something similar for for some reason I can't get it to work:

    I'm sure it's a Visual Studio problem, but do you have any ideas?

  10. Matt Williams reporter

    Perhaps the simplest solution would be to remove the option of having a default value for the parameter. It's not absolutely required but it made sense to avoid users typing 0 every time.

    I think the only alternative to this is to have an #ifdef like in the other case you pointed to. I tried last night and GCC doesn't compile without the typenames. I was perhaps trying to be overly clever by having a default value based on a dependent typedef based on another inferred template parameter :)

    I think overall it's best to avoid #ifdefs and have code which just works on both platforms. we can always just add the default value back in in the future if we can work out a nice way to make it work.

    So, removing the default parameter and adding a comment to look into it in future sound ok?

  11. David Williams

    The strange thing is that I can't get it to work even with an #ifdef, yet as far as I can see it is structurally the same as the other example I pointed to. Perhaps I just didn't try hard enough - in the past I've usually resorted to making a separate example, simplifying it as far as I can, and posting it on StackOverflow if I still can't work it out. Templates are hard :-)

    Anyway, we can just remove the default parameter for now, and add it back in the future without breaking backwards compatibility. I'll commit this change later after I verify it again.

  12. David Williams

    Just a heads up that I've finally merged this into Cubiquity version of PolyVox and it's all working nicely. I'm testing both the finding of the hit voxel and also the previous voxel. Good stuff!

  13. Log in to comment