Say I have an axis aligned bounding box (3D), and two arbitrary points on that bounding box. How would I find the shortest path between the two points over the surface of the bounding box? The bounding box may be considered to be axis aligned, and at the origin. I want the result-path to be defined by an array of waypoints to follow. It may sound easy at first, but it looks like it''s quite complicated. Cheers! Nick

Well, you should be able to pre-build a graph of the bounding box.

If the 2 points are on the same side:
Then you already have the shortest path, a straight line.

Else:
Add the 2 points to the graph, link them to the 4 corners of the side they are on.
Run a pathfinding algo on the graph.

Here is an example:
0, 1, 2, 3, 4, 5, 6, 7 are the corners of the box.
0,1,2,3 make up the front, 4,5,6,7 make up the back.
the from of the box looks like this:

8,9 are the 2 points.
8 lies in the plane created from 0,1,2,3.
9 lies in the plane created form 0,4,7,3 ( the left side )

The box graph would look like this:
0->1->3->4 ( 0 is connected to 1,3&4 )
1->0->2->5
2->1->3->6
3->0->2->7
4->0->5->7
5->1->4->6
6->2->5->7
7->3->4->6

and the 2 points:
8->0->1->2->3
9->0->4->7->3

From this, using no weights, the shortest path would be: 8->0->9 or 8->3->9.

Obviously, calculating the lenghts of each connection ( cost ) would be appropriate.

However, If you leave the bbox in local space, the cost is the same to travel to each point ( 1 unit length), so you dont need to store this. You just need to map the 2 points into the bbox local space. From this you should be able to determine the length to the points 4 adjacent corners. Interestingly enough, each length will be less than or equal to 1

Lets assume point 8 maps directly into the middle & point 9 maps into the middle of the top edge.

Adding in the (roughly rounded) cost for each traversal yields:
8->0: 0.5
8->1: 0.5
8->2: 0.5
8->3: 0.5

9->0: 1.2
9->3: 0.5
9->4: 1.2
9->7: 0.5


Given the above information, the cost can be found:
8->3->9: 0.5 + 0.5 = 1.0
8->0->9: 0.5 + 1.2 = 1.7

From this, 8->3->9 is our winner.



So, the basic algo is:
- given to points (A, B) & a bounding box BB:
- construct a matrix from BB to transform A & B into local bbox space.
- transform A & B into local space.
- contruct the weighted graph for A & B.
- run a traversal algo on the graph.

One thing to note. If both A & B are in the same side ( thier graphs connect the same 4 points ), then the shortest path is simply a straight line.

Hope this made some sense & helps a little.

oops. that should read:
Interestingly enough, each length will be less than or equal to 1.414 or sqrt( 2 ) ( from that a^2 + b^2 = c^2 theorem )
Sorry for that.

quote:

---

Original post by maxsteel
from that a^2 + b^2 = c^2 theorem

---

FYI: That would be Pythagorus'' Theorem.

Just a quick comment... from a quick read, maxsteel''s answer provides a path between two points that passes through the vertices of the bounding box, rather than across the surface per se. If you want the path across the surface, that intersects edges, rather than vertices, give a holler and I''ll post an analytic solution.

Cheers,

Timkin

He asked for the shortest path. The shortest path does not pass through the vertices.

The problem is quite simple because you can "un-wrap" your box (ie.: you can consider that the faces are ''flat'' in the direction that you choose). If your destination point is on a face that is adjacent to the face of the starting point, then the "unwrapping direction" is quite obvious.

Let''s say that the starting point is on the top face, and the destination point is on the right face. You have to ''rotate'' the right face so that it is coplanar with the top face. So, the destination point''s new position will be:

P'' = (Width / 2 + (Height / 2 - P.y), Height / 2)

I used Width / 2 and Height / 2 because I assumed that your box is centered at the origin.

Then you can quite easily compute the line equation between StartPoint and P''. To get the waypoint, find the z value of the line when x = Width / 2 (when the line crosses the right face).

If the ending point is on the bottom face and the starting point is on the top face, it''s more complicated to choose which way to go. It''s an interesting problem, and I''ll give it some thought, but I have to go to school now.

You could always try going through the 4 faces adjacent to the top one, using the "unwrapping" method described earlier, and find the one with the shortest distance.

Cédric

Your quite correct. The simple algo above will yield a path through the points that make up the cube. This is a starting point....

Once you have the path through the points, you can determine the edges the path passes through. Once you have the edges....

I also didn''t mention anything about determinig what plane(s) the 2 points in question intersect so you can build the point graph. However, I did give a hint in my second post.


There may very well be faster ways ( I am not an AI programmer ), but I think this one is fairly simple to implement & has some nice features.

Thanks guys,

This was one of those questions you think about for a while, and then you decide to post it somewhere. And just after you press the send button, you think ''Ah! I''ve got it!''

I solved it in exactly the way described, by ''flattening'' the
cube, and it works nicely.

Thanks for the help

Nick