<p>As no one else seems to want to suggest something, given that you said you wanted to navigate within an arbitrary enclosed volume, perhaps you could use an approach similar to that of the 1995 game <a href="https://en.wikipedia.org/wiki/Descent_(video_game)" rel="nofollow noreferrer">Descent</a>.</p>

<p>IIRC the world model of the 'mine' the spacecraft and enemy robots navigated was made up of "cuboid" units/voxels that pieced seamlessly together, <em>some</em> of which had solid walls that then formed the boundaries of the enclosing volume. The source code is freely available online <a href="https://archive.org/details/Descent_source" rel="nofollow noreferrer">e.g. here </a>.</p>

<p>If, in the likely scenario you can't force the enclosing volume to have quadrilateral facets, you might want to consider "tetrahedral" volumes.</p>

CC BY-SA 4.0
2020-02-14T10:39:21.973Z
2020-02-18T08:10:53.970Z
2020-02-18T08:10:53.970Z
Simon F
<p>I  think you can make a graph of the entire surface and have your algorithm &quot;walk&quot; over it. Your planes would be hugging the surface but it would be the shortest. You could fix the hugging by a local upward translation on the plane.</p>
<p>If you have a weird maze-like structure, you might want to &quot;cross the gaps&quot;, so you need to adapt the algorithm to be able to cross air gaps, you could do this by just iterating all triangles and connecting them to all other triangles (thus creating a graph). Of course, you can't pass through the walls, so you need to take into account the surface normals. If you construct the lines between two surfaces, and you compare the surface normals to the direction of that line, it can tell you whether you are going through the surface (forbidden) or away from it (crossing air gaps). If the 2 surfaces are direct neighbors you don't need to do the line-normal check, and you can assume your algorithm can walk from one triangle to the other.</p>
<p>Most 3d model files reuse the same vertices for multiple triangles so it's easy to check whether they are neighbors: just check if they have vertices in common.</p>
<p>Once you have constructed the final graph, you can just use a pathfinding algorithm to find the shortest path to traverse the graph.</p>

CC BY-SA 4.0
2020-11-16T10:37:57.023Z
2020-11-16T10:37:57.023Z
AnnoyinC
<p>I am not sure if this is the correct SE to ask this question. However, lets say I have been given 3D models of several enclosed spaces.</p>

<p>I want to populate spaces with, lets say, planes flying through them, taking the optimum route from A to B. Since there are many of them, I want to write an algorithm that does this; I already have the 3D models of the planes. </p>

<p>I am looking for resources I can use to learn how to do define the boundary conditions for the opimization algorithm given the 3D model. </p>

CC BY-SA 4.0
2020-02-07T09:22:12.030Z
I'm assuming by "planes" you mean aeroplanes (as I originally interpreted 'planes' in the mathematical/graphics sense :-) ). Seriously though, when you say *"lets say I have been given 3D models of several enclosed spaces."* do you mean they are a set of objects the aircraft must avoid (e..g like the stereotypical "spaceship in an asteroid field" ) or do you mean, given an arbitrary one of these enclosed volumes, allow the aircraft to fly around inside it (and not crash)?
Simon F
CC BY-SA 4.0
2020-02-07T14:45:46.550Z
@Simon F Hmm, I am interested in learning both, but for this question I'll restrict it to enclosed volumes if the methods are fundamentally different.
Avatrin
CC BY-SA 4.0
2020-02-14T20:31:57.480Z
Look into winding numbers
Makogan
CC BY-SA 4.0
2024-07-29T19:55:35.933Z
This is several questions wrapped into one, with several additional sub questions depending on how it is read. Even the clarification brings up additional questions. For this reason I voted to close it.
pmw1234
<3d>
Defining "inside" and "outside" of a 3D space
Avatrin
# Defining "inside" and "outside" of a 3D space

(Asked by: username_0 on 2020-02-06)

I am not sure if this is the correct SE to ask this question. However, lets say I have been given 3D models of several enclosed spaces.

I want to populate spaces with, lets say, planes flying through them, taking the optimum route from A to B. Since there are many of them, I want to write an algorithm that does this; I already have the 3D models of the planes.

I am looking for resources I can use to learn how to do define the boundary conditions for the opimization algorithm given the 3D model.

**Tags:** 3d

> **Comments:**
> **username_1**: I'm assuming by "planes" you mean aeroplanes (as I originally interpreted 'planes' in the mathematical/graphics sense :-) ). Seriously though, when you say *"lets say I have been given 3D models of several enclosed spaces."* do you mean they are a set of objects the aircraft must avoid (e..g like the stereotypical "spaceship in an asteroid field" ) or do you mean, given an arbitrary one of these enclosed volumes, allow the aircraft to fly around inside it (and not crash)?  
> **username_0**: @username_1 Hmm, I am interested in learning both, but for this question I'll restrict it to enclosed volumes if the methods are fundamentally different.  
> **username_2**: Look into winding numbers  
> **username_3**: This is several questions wrapped into one, with several additional sub questions depending on how it is read. Even the clarification brings up additional questions. For this reason I voted to close it.  

---

## 2 answers

### Answer by username_1 on 2020-02-14. Score: 0

As no one else seems to want to suggest something, given that you said you wanted to navigate within an arbitrary enclosed volume, perhaps you could use an approach similar to that of the 1995 game [Descent](https://en.wikipedia.org/wiki/Descent_(video_game)).

IIRC the world model of the 'mine' the spacecraft and enemy robots navigated was made up of "cuboid" units/voxels that pieced seamlessly together, *some* of which had solid walls that then formed the boundaries of the enclosing volume. The source code is freely available online [e.g. here](https://archive.org/details/Descent_source) .

If, in the likely scenario you can't force the enclosing volume to have quadrilateral facets, you might want to consider "tetrahedral" volumes.


---

### Answer by username_4 on 2020-11-16. Score: 0

I think you can make a graph of the entire surface and have your algorithm "walk" over it. Your planes would be hugging the surface but it would be the shortest. You could fix the hugging by a local upward translation on the plane.

If you have a weird maze-like structure, you might want to "cross the gaps", so you need to adapt the algorithm to be able to cross air gaps, you could do this by just iterating all triangles and connecting them to all other triangles (thus creating a graph). Of course, you can't pass through the walls, so you need to take into account the surface normals. If you construct the lines between two surfaces, and you compare the surface normals to the direction of that line, it can tell you whether you are going through the surface (forbidden) or away from it (crossing air gaps). If the 2 surfaces are direct neighbors you don't need to do the line-normal check, and you can assume your algorithm can walk from one triangle to the other.

Most 3d model files reuse the same vertices for multiple triangles so it's easy to check whether they are neighbors: just check if they have vertices in common.

Once you have constructed the final graph, you can just use a pathfinding algorithm to find the shortest path to traverse the graph.


---

