New vsg::PolytopeIntersector class

[robertosfield]

Hi All,

I have completed my work on vsg::PolytopeIntersector and checked it into VSG master and vsgExamples master. vsg::PolytopeIntersector provides support for finding point, line or triangle intersections of a scene graph with a polytope. Changes are:

• VulkanSceneGraph changes
• vsgExample changes

The usage is similar to the vsg::LineSegmentIntersector - you construct the intersector and traverse the scene graph to collect the intersections, then utilize the intersections. A common usage case is to use the intersector for picking, to create a PolytopeIntersector for this purpose you create it using the vsg::Camera and dimensions in screen space:

auto intersector = vsg::PolytopeIntersector::create(*camera, xMin, yMin, xMax, yMax);

Traverse the scene graph to find the intersections:

        scenegraph->accept(*intersector);

And to process the intersections:

        if (intersector->intersections.empty()) return;

        for (auto& intersection : intersector->intersections)
        {
            std::cout << "intersection = world(" << intersection->worldIntersection << "), instanceIndex " << intersection->instanceIndex;
        }

        std::string name;
        for (auto& node : intersection->nodePath)
        {
            std::cout << ", " << node->className();
            if (node->getValue("name", name)) std::cout << ":name=" << name;
        }

        std::cout << ", Arrays[ ";
        for (auto& array : intersection->arrays)
        {
            std::cout << array << " ";
        }
        std::cout << "] [";
        for (auto& index : intersection->indices)
        {
            std::cout << index<<" ";
        }
        std::cout << "]";

        std::cout << std::endl;

As part of the work I wrote a vsg::PrimitiveFunctor template class for helping map Vulkan primitive types to point, line and triangle primitives. I haven't refactored vsg::LineSegmentIntersector to use this class but that's on my TODO list as it'll make it easy to support triangle strips etc. that aren't support be the LineSegmentInteresector right now.

[TP-David]

Hi Robert,
There is no longer a "ratio" component which we used to sort the intersections by distance and retrieve the closest.
How would you recommend getting the closest intersection?

[robertosfield]

I chose not to implement a ratio as it's isn't a clear cut value for a polytope intersection like it is for a line segment intersection - which polytope face would be the nominated one for computing the control distance/ratio that you sort against?

In the case of the polytope built around a window space rectangle using the near far would probably be a reasonable default. One could compute this in post processing. Potentially we could have nominated face that is used for computing a reference distance.

[dov]

Does the intersection do a "any" or "all" type of intersection? Can you control this?

Here's an illustration of what I mean by "any" an "all" (I'm sure they have more accurate geometric names):

The chosen objects have orange outlines.

My interpretation is that in "any" the intersection between the rectangle and the object is not empty. And in the "all" case then the rectangle fully contains the object.

[robertosfield]

Both the vsg::PolytyopeInteresector and vsg::LineSegmentIntersector will return all the intersected primitives from all the meshes that have intersections. You can post process the intersection results if you want to add extra rules.

[TP-David]

I chose not to implement a ratio as it's isn't a clear cut value for a polytope intersection like it is for a line segment intersection - which polytope face would be the nominated one for computing the control distance/ratio that you sort against?

In the case of the polytope built around a window space rectangle using the near far would probably be a reasonable default. One could compute this in post processing. Potentially we could have nominated face that is used for computing a reference distance.

Thanks, I noticed in OSG our team had simply been calling "getFirstIntersection" which seems to retrieve the first hit only. So there does seem to be a nominated face being used for the distance, in the past?

[robertosfield]

Off the top of my head I don't recall the specifics as it's a looong time since I worked on osgUtil::PolytopeIntersector. The code will tell you what is going on.

[dov]

I finally got around to testing the PolytopeIntersector and it's not working as I expected.

I used the Builder to create a scene composed of a ground floor and a grid of cubes, and I then used my new rectangular interactive selector to interactively draw a rectangle. I intersected the rectangle with my scene through the PolytopeIntersector and I then changed the color of the cubes that were intersected.

Here are two screenshots from this interaction:

1. Selecting a single cube:

2. Extending the selection to the right so that it surrounds the second cube:

Now, what surprised me was that once I intersect a second cube, I no longer got the intersections with the first cube.

My code is very similar to your code @robertosfield:

    void intersectionRect(const MouseRectSelector::Rectangle& Rect)
    {
        double xMin = Rect.pos.x;
        double xMax = Rect.pos.x + Rect.size.x;
        double yMin = Rect.pos.y;
        double yMax = Rect.pos.y + Rect.size.y;

        auto intersector = vsg::PolytopeIntersector::create(*_camera, xMin, yMin, xMax, yMax);
        _scene->accept(*intersector);

        if (intersector->intersections.empty())
            return;

        selectNode(); // Reset all colors 
        for (auto& intersection : intersector->intersections)
        {
            {
                string name;
                vector<string> names;

                for (auto& node : intersection->nodePath)
                {
                    if (node->getValue("name", name))
                    {
                        names.push_back(name);
                        selectNode(node);
                    }
                }
                if (names.size())
                    print("Names: {}\n", fmt::join(names,","));
            }
        }
    }

So why don't I get any intersections from the first cube?

I'm also worried about the efficiency of this method for meshes that contain >100k primitives. In my use case, I don't care which primitives are intersected. All I want to know is whether the mesh intersects the selection rectangle.

I think that in my case it would be a more efficient to draw to a "label image" texture, but I'll ask about that in a separate discussion.

[robertosfield]

It could be a bug in the mapping of the screen selection rectangle to the PolytopeIntersector, a bug in the intersector or even a bug in the selectNode(node), but can't say without being able to test and review code myself.

The first thing I'd check is whether selectNode can select multiple nodes without disabling the selection of others.

[dov]

Sorry. Indeed my mistake. My selectNode() was erroneously disabling the selection of other nodes. It's working perfect now.

[robertosfield]

Oh, forgot to mention, w.r.t performance, PolytopeIntersector has to tests of every triangle, line segment or point against each face of the polytope to know that it's inside, and in the case of triangles and line segments has to successively trim the primitive to find whether it's partially within the polytope. This will be expensive for scenes with large meshes.

One can help lower the cost by decorating the mesh with vsg::CullGroup/CullGroup with their bounding spheres set to be a tight bound around the meshes geometry. The PolytopeIntersector/LineSegmentIntersector can then test against the bounding sphere and not traverse the subgraph if it's not intersected.

Longer term I'd like to see some support built into the scene graph for acceleration structures that can be used for intersection testing, such a KdTree. The OSG has this so I've implemented this type of functionality before, it's not a trivial task though so I haven't yet tackled it for the VSG.

The are alternative approaches for picking as well, each approach has it's own advantages and disadvantages.

[zhuzhiyong8679]

The large mesh must be made into a pageLod, and finally go to some of the underlying nodes to partially traverse the vertices of the triangulation. This is by far the fastest way to find intercourse.

[TP-David]

Hi Robert,
As mentioned the PolytopeIntersector works great, we just have troubles clicking on text.

I found adding apply(const TextTechnique& txt) override to Intersector with the following seems to do it, for the most part:

void Intersector::apply(const TextTechnique& txt)
{
    if (auto cpuTechnique = txt.cast<CpuLayoutTechnique>())
        cpuTechnique->scenegraph->accept(*this);
    if (auto gpuTechnique = txt.cast<GpuLayoutTechnique>())
        gpuTechnique->scenegraph->accept(*this);
}

What's missing is TextLayout support (for billboarding, position etc.) but we are not using this in our case, so this seems a good rudimentary solution for now. What are your thoughts?

[robertosfield]

I did test text when I wrote PolytopeIntersector. From your description it looks likely that LineSegmentIntersector won't be working either, and again it's not something I've tested or aimed for support.

The ArrayState is how the VSG copes with novel ways of mapping vertex array state to final vertex positions, but I haven't tried it with vsg::Text's way of doing things.

If the above tweak to Intersector takes us a step towards better support then could you generate a PR for this change and then I can do some testing at my end. Thanks.

[TP-David]

Actually, just noticed my snippet doesn't account for GpuLayoutTechnique at all, since it uses instancing. Will do some experimentation...