Are there plans to introduce a spatial index structure such as an octree into the project to improve the responsiveness of user interactions in large-scale responsible scenarios

[xushengbo]

Are there plans to introduce a spatial index structure such as an octree into the project to improve the responsiveness of user interactions in large-scale responsible scenarios

[robertosfield]

One of the main reasons for scene graphs is that they are designed to facilitate hierarchical culling of different types, simply by appropriate organization of the scene graph hierarchy.

If you want a binary tree then you have a hierarchy of vsg::Group containing two nodes, if you want a quad-tree then hierarchy containing vsg::Group (or vsg::QuadGroup) containing four children, if you an oct-tree then a hierachy contains vsg::Group with eight children.

You can have combinations of different numbers of children at different regions of the scene graphs. For instance at global scale you might have a quad-tree of vsg::PagedLOD nodes to facilitate database paging, then for a city you might have a combination of binary, quad or octree to handle different types of building layouts down to the buildings and their rooms.

Within these hierarchies you place cull nodes, like vsg::PagedLOD, LOD, CullNode, CullGroup.

These are all core elements of the scene graph from the earliest development as they are all so fundamental to the functioning of professional grade scene graph.

While all of these capabilities are there, it does require loaders and applications to compose the scene graphs that suite their application requirements.

One element that isn't yet implemented is acceleration of fine grained CPU operations rather than graphics operation, such as scene graph intersections with rays and polytopes, for now the vsg::LineSegmentIntersector and PolytopeIntersector are limited to leveraging the above scene graph culling hierarchy as discussed above, but once the intersector gets down to testing individual triangles within a local mesh it has to do the tests primitive by primitive.

One way to accelerate this would be a local culling hierarchy attached to the geometry nodes specifically for individual primitives. In the OpenSceneGraph project I implemented a kdTree for this purpose. Longer term I expect we'll have something similar in function within the VSG.

[xushengbo]

Thanks for the reply, and look forward to the implementation of this feature.

[robertosfield]

Thanks for the reply, and look forward to the implementation of this feature.

Which feature as your original question lacked specificity? There is no way to know if you are talking about rendering or intersection testing. What exactly do you mean by user interactions?

[xushengbo]

Mainly used in the process of interaction between users and a large number of graphical elements, such as when a user clicks on the screen, it can quickly locate which node the user clicked on without applying a visitor traversal to each node one by one. This is very useful for the development of some computer-aided design programs. Is it possible to automatically associate a spatial index structure when adding a node to the scene to speed up this process.

[robertosfield]

The vsg::LineSegmentIntersector already tests against any CullNode/CullGroup/LOD in the scene so will already prevent traversal of subgraphs that don't intersect the line used of picking, and depending on how your scene graph is managed this may be sufficient already.

If the individual meshes are very large then it becomes more important to accelerate the fine grained intersection testing as the current implementation with test each triangle in a mesh one by one. This is where an extra acceleration structure like a kdTree would be helpful. Such an extra acceleration structure would be nested within the culling provided by the internal culling nodes in the scene graph rather than being a separate entity.

[MasonAlice]

VSG is a general-purpose rendering engine. The octree you mentioned is a specific business logic component—you can derive the nodes you need yourself.