New addons ofxRaycaster

#1

Hello, I have improved this addon https://github.com/edap/ofxRaycaster and I think it is pretty stable now.

f you want to use rays in your #openFrameworks app, maybe this is for you:

  1. It contains a minimal definition of a ray in 2D and in 3D. It checks for the intersection of a ray with a segment, a sphere, a triangle, a plane, an ofPrimitive, an ofPolyline an with an ofMesh.
    mesh-intersection

  2. Whenever it is possible, it uses the GLM methods, like glm::reflect and glm::intersectRayTriangle, without re-inventing the wheel (and the math).
    polyline

  3. It runs continuous integration testing on mac, linux and windows. https://travis-ci.org/edap/ofxRaycaster and https://ci.appveyor.com/project/edap/ofxraycaster.

  4. All the public methods are documented in the README file, and linked to the example where they are used.

  5. It contains a mouse picker to easily identify meshes, spheres, ofPrimitives under your mouse cursor in a 3d space.
    mousepicker

  6. Last but not least, all the example have animated gifs, so that you do not need to compile them in order to find what you are looking for.

8 Likes
#2

Awesome! Thanks. I will need this soon on an upcomming project. :smiley:

#3

Wow! Cool!
What is the benefit of lay based mouse picking compare to the default GL one? ( I remember ofWorldToScreen() or something is included in oF. )

I imagine Laycaster can find front object if there is another one behind? But how about performance?

#4

The core functionality of this addon is testing ray intersection against polylines, meshes etc… Mouse picking is just a little functionality added at the end, and it uses internally screenToWorld as @roymacdonald was suggesting in the forum a while ago. https://github.com/edap/ofxRaycaster/blob/4937ea4f3460d191e41eca2548f3dffbac939814/src/Mousepicker.cpp#L15

There are 2 ways to do mouse picking in openGL, one is ray casting, what I have used in this addon, and the other one is to render the scene in another buffer , and in this buffer each object has an identifier. More info here -> https://www.opengl.org/archives/resources/faq/technical/selection.htm
I prefer the ray picking because it does not involve an additional render pass.

Chapter performances: A ray stores only two glm::vec3, the memory footprint is therefore low. What is not performant at the moment is the ray mesh intersections method. This is because it simply tests the intersection of a ray with every triangle composing a mesh, without any optimization. There are two kind of optimization that I could add:

  • A simple bounding box. Instead of testing the intersection of a ray with a triangle, I could simply test the intersection of a ray with the box containing the triangle. This is fast but not so really precise, you can easily imagine all the false positive that you can have testing the intersection of a ray with a tree using a bounding box containing a tree. There is an old PR here https://github.com/openframeworks/openFrameworks/pull/514, any feedback is welcome.
  • Using more sophisticated spatial algorithm to represent the mesh, like a A BVH tree, Bounding Volume Hierarchy tree. Basically, smaller details are enclosed into smaller boxes, and those boxes are ordered in a tree structure. There are already other addons covering this topic (like https://github.com/kylemcdonald/ofxBvh by @kylemcdonald and https://github.com/bakercp/ofxSpatialHash by @bakercp ), so I would probably simply add a method that accepts those data structure as a parameter instead of adding those algorithms into this addon.
3 Likes
#5

Very nice.
Would it be possible to check where two spheres are intersect with each other? Ideally get the circle that discribes this intersection.

Thanks

#6

Hello Stephan. No, the addon contains just intersection methods between a ray and other primivitives. What you are looking for is probably some library that does boolean operation between solids, like https://github.com/neilmendoza/ofxCorkCsg.

To get the intersection between two sphere should not be difficult by the way. You get the position of the centers of the 2 spheres, if the distance between the 2 points is less than the sum of the radius of the two spheres, there is an intersection. The next step would be to identify where exactly those points are. On the wolfram website there is a tutorial about it. http://mathworld.wolfram.com/Sphere-SphereIntersection.html

1 Like
#7

What would I have to do to check if a given point is inside a 3d mesh?
Let’s I have the mesh of cuboid and want to see if my point is inside or outside of it?

In the past I used ofxIntersection and there I needed to count the amount of intersections. Any even amount meant the point is not inside.

thx

#8

The addon is a raycaster, it does not cover the use case you mention. Anyway, I guess that to find if a point is inside a cube, you just need to get the boundingBox of that cube, and then check if the component x,y and z of your point are between the min and max.

here the code to get the bounding box:

struct ofBoundingBox{
    glm::vec3 min = glm::vec3(0,0,0);
    glm::vec3 max = glm::vec3(0,0,0);
};

    ofBoundingBox boundingBox;
    const vector<glm::vec3>& vertices  = getMesh().getVertices();
    for(auto v : vertices){
        if (v.x < boundingBox.min.x) boundingBox.min.x = v.x;
        if (v.y < boundingBox.min.y) boundingBox.min.y = v.y;
        if (v.z < boundingBox.min.z) boundingBox.min.z = v.z;
         if (v.x > boundingBox.max.x) boundingBox.max.x = v.x;
        if (v.y > boundingBox.max.y) boundingBox.max.y = v.y;
        if (v.z > boundingBox.max.z) boundingBox.max.z = v.z;
    }
#9

Thanks for the quick reply.
I just said box to keep it simple. Infact it’s a mesh structure more complicated than a box.

But good to know:)

Does the add-on provide the amount of mesh intersections or just the first one?
If a point is inside a closed mesh structure it would intersect an uneven amount.

#10

I forked your add-on and changed it a bit to return the number of intersections for a ray. This allows me to determine if the ray origin is inside or not.

#11

I also forked and started adding multiple reflection feature.


Like the screenshot, we keep casting ray again and again after reflection.
We can limit the reflection by using setMaxReflectionNum() or setMaxDistance().

I also found difficult Issue. In the screenshot, theoretically ray should stay inside of the box. But sometimes it escapes and go out side of the box! Maybe switch to double precision reduce this error a bit. (I know where this happen but didn’t manage to fix so far…)

Here is forked repo.
Please see /example-multicast project for this feature.

+Edit
Also the name for this feature “multicast” sounds wrong, since it is a single cast. (But multiple reflection) Do not merge at the moment please :sweat_smile:

#12

Hello @hrs, I did not add multiple bounces to the addon because I have preferred to keep the classes Ray and Ray2D small and essential. Reagarding multiple bounces, I have an example working on my laptop, it is something close to https://github.com/edap/udk-2018-mirage-of-mirrors/blob/master/01-RayBounceRecursive/src/ofApp.cpp . I will add it to the example list.

1 Like
#13

Hi! I just sent a PR with better performance for the mouse picking example :slight_smile:

Above it was mentioned to use bounding boxes, but bounding spheres are faster because you don’t need 6 tests, right?

This is the comment explaining the main change:

    // Speed optimization. Two pass hit test.
    // First test if the ray hits the bounding sphere of the object
    // and if it does, test if it really hits a triangle in the object.
    // Testing against a bounding sphere is a very fast test.
    // If it doesn't hit the bounding sphere then there
    // is no point in testing against every single triangle in the mesh.
    // You can use this even if the shapes are not spheres.

ps. Maybe the library itself could use this approach of a two-test-pass for meshes, right? In that case I could send a different PR to do that.

#14

Thanks @hamoid, I am looking into it. As I was saying here New addons ofxRaycaster this addon does not implement any form of optimization when testing the mesh intersection. I have to think a bit how, and if, to integrate it to the API of the addon. A sphere, as you where suggesting, works good when approximating icosphere, but it it does not work good with other geometries, like boxes.

#15

I would say it’s good enough even for boxes, as a box has at least 12 triangles, and a sphere is just a center and a radius. I tried with setting 0 iterations for the icosphere, which gives you something similar to a box (20 triangles) and it gets the same speed benefit (about 10x).

Maybe I didn’t make it clear that this is an optimization for testing against a large number of items. It does not improve anything if you just have one 3D mesh. It actually makes it slower.

The more vertices the tested meshes have, the more it would benefit from doing two passes, because the computation time would match the number of meshes, instead of the number of vertices.

An example: you have hundreds of 3D plants. You test the ray against a bounding sphere for each plant. If it doesn’t hit the sphere, then there’s no need to test if it really hits the mesh, avoiding thousands of operations. If it does hit the sphere, the second test may find that it was a false positive, but that’s ok. This will probably happen with a few shapes that were near the ray.

The one case in which it would be wasteful is if you are dealing with lots of very long tubes that cross the screen, because in that case the ray would hit every single bounding sphere (because they are huge) and then the second pass would tell you that it wasn’t actually a hit. This specific case would perform worse.

Maybe I’m misunderstanding why you say that boxes would not work well?

#16

Hello @hamoid, the “problem” is clear to me. As I have already said, this addon does not have any form of optimisation regarding 3d mesh intersection. Therefore I am not surprised that using a sphere as bounding volume it is 20 faster. Intersection tests between a ray and a mesh is an old topic in computer graphics (~30 years), the latest “Real Time Rendering” book it has a chapter only about this topic. Simple volume like sphere,axis aligned bounding box or oriented bounding boxes, works well for certain scenario, but over the years different solutions where proposed, that have their benefits too. For sure, the simplest optimisation, like a sphere or a bbox is better than nothing. I still do not know if I want to add those optimisations inside the API of addon,or if I should leave to the developer the implementation of those intersection test techniques, like you did with the sphere. I think it would be nice to have a separated example, like example-bounding-sphere where there are a lot of cubes and each of them is surrounded by a bounding sphere, and then the example perform the test you where proposing in the mouse picker example. And maybe in the future I will add another example with an AABB, and one with a BVH tree. But in this last case, I think it would make much more sense to do not cover BVH creation in the addon, but instead, making an example about how to use ofxRaycaster and, let’s say, ofxBvh or ofxSpatialHash to optimize the ray intersection test.

1 Like
#17

Sorry, I forgot to answer here. A sphere it is better than nothing, but there are better bounding volumes to enclose a box while making test intersection, that reduce the false positives.

1 Like