# How to efficiently find which triangles in a scene might intersect a given triangle?

**URL:** <https://forum.castle-engine.io/t/how-to-efficiently-find-which-triangles-in-a-scene-might-intersect-a-given-triangle/373>\
**Category:** Uncategorized\
**Created:** [July 22, 2021, 11:12am UTC](https://forum.castle-engine.io/t/how-to-efficiently-find-which-triangles-in-a-scene-might-intersect-a-given-triangle/373 "2021-07-22T11:12:03Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![DSK](https://forum.castle-engine.io/letter_avatar_proxy/v4/letter/d/67e7ee/32.png) [@DSK](https://forum.castle-engine.io/u/DSK)\
**Post date:** [July 22, 2021, 11:12am UTC](https://forum.castle-engine.io/t/how-to-efficiently-find-which-triangles-in-a-scene-might-intersect-a-given-triangle/373/1 "2021-07-22T11:12:03Z")

</div>

I see that there is private

> TCastleSceneCore.CreateTriangleOctree(): TTriangleOctree;

Is there a “usual” way that I can leverage this to find subsets of triangles which have a chance of intersecting a given triangle?

Looking at the ancestor of TTriangleOctree (TBaseTrianglesOctree) it has methods for colliding various primitives, and I’m interested in BoxCollision:

> TBaseTrianglesOctree.BoxCollision(): PTriangle;

This only returns a pointer to a single triangle. How would collision with multiple triangles be handled?

---

<div class="post-metadata">

**Author:** ![michalis](https://forum.castle-engine.io/user_avatar/forum.castle-engine.io/michalis/32/3_2.png) [@michalis](https://forum.castle-engine.io/u/michalis)\
**Post date:** [July 26, 2021, 3:28am UTC](https://forum.castle-engine.io/t/how-to-efficiently-find-which-triangles-in-a-scene-might-intersect-a-given-triangle/373/2 "2021-07-26T03:28:46Z")

</div>

You can access the `Scene.InternalOctreeVisibleTriangles` or `Scene.InternalOctreeStaticCollisions`. They are non-nil if you include `ssVisibleTriangles` or `ssStaticCollisions` in the `Scene.Spatial`, see [TCastleSceneCore.Spatial docs](https://castle-engine.io/apidoc-unstable/html/CastleSceneCore.TCastleSceneCore.html#Spatial) and [ssXx flags docs](https://castle-engine.io/apidoc-unstable/html/CastleSceneCore.html#TSceneSpatialStructure).

These already contain all shapes of the scene “summed up”.

To access octree for given shape, there is [TShape.InternalOctreeTriangles](https://castle-engine.io/apidoc-unstable/html/CastleShapes.TShape.html#InternalOctreeTriangles). It is available if you add `ssDynamicCollisions` to `Scene.Spatial`.

Up to you whether to use octrees for the whole scene, or the ones per-shape. Using the ones per-shape is more complicated… but if the result of your operation must preserve appearance (materials, textured) then it may be better. Otherwise, in the “whole scene” octree you wlll have a big set of all triangles, with all possible appearances, and you will later need to organize them into new shapes, grouping the resulting triangles with the same appearance.

> Looking at the ancestor of TTriangleOctree (TBaseTrianglesOctree) it has methods for colliding various primitives, and I’m interested in BoxCollision:
> 
> TBaseTrianglesOctree.BoxCollision(): PTriangle;
> 
> This only returns a pointer to a single triangle. How would collision with multiple triangles be handled?

The purpose of this method is to return any triangle that collides with the box. From what I recall, and see in code, it doesn’t have any logic to select a particular colliding triangle. It just returns any colliding triangle. The callers (like `TCastleSceneCore.LocalBoxCollision`) are using it to have a Boolean knowledge “there is some collision with this box / there is none”.

So it’s not really what you need. I think you’d like to add a similar method like `AllBoxCollisions` that lists all the colliding triangles, maybe by calling some callback. It could use a similar logic as current `BoxCollides`, just not exit early – instead find all triangles.

It is possible you can implement it without changing CGE, and just traversing the octree yourself. But admittedly I’m not sure – so far, such operations have been implemented by extending existing CGE octree classes. If need be, go ahead and modify CGE – we can make it included 🙂