I asked a question before about how to walk on a particular type of triangular mesh. This question poses the issue of constructing that mesh from a list of triangles.

As some background we define a triangle to be an ordered triplet of points. The side that has a clockwise ordering of points is the actual face of the triangle. The other side for all intensive purposes does not exist unless it happens to be another triangle.

Alright, so to start off we have a triangle in space that we can refer to as $T = (p_1,p_2,p_3)$. We know that there exists some number of triangles that also contain points $p_1$ and $p_2$ within their triplet.

If these triangles all exist as part of some surface geometry, then if we draw a geodesic from some point on T to the line segment $p_1p_2$, which triangle will it spill onto? I know I did not actually provide a literal other set of triangles so by this I mean what is the test to determine which triangle works "best".

I presume that there is there some number of measurement or angle that is greater or lesser than all other triangles in the set such that the one holding that greatest value is the triangle truly connected to $T$. (I know that last sentence was a bit rambled. They form my "thoughts" on how to maybe solve the problem)

The purpose for me asking this question is as follows. This other half to the algorithm essentially allows me to take any 3D model (which for the most part can be broken down into a list of triangles) and convert it into a walkable triangular mesh. The end result would be that I can make anything walk in space on any 3D model. If the significance for that is not quite clear, understand that an efficient algorithm for the walking (as construction can be saved to a file) essentially allows anyone to examine a parametric surface visually and understand its curvature a little bit more tangibly. Plus, I hear it is a really good video game thingy. That's my particular usage for it.


I am not 100% certain if this method works. So I am posting this as an answer to see if it spurs any thoughts.

Trivial Rejection

Just as gears turning together rotate in opposite directions, for any triangle to be "facing" the same direction as out surface the points $p_1$, $p_2$, and $p_4$ of any other potential triangle must be in the order $(p_2,p_1,p_4)$. Anything that fails this test can be dropped from the list to dig through (or skipped).

Angle Between Two Planes

We wish to compare the angle formed by the two triangles. This can be computed as the following formula:

$\arccos(<\frac {p_4 - \frac {<p_4,p_2-p_1>}{|p_2 - p_1|} - p_1}{|p_4 - \frac {<p_4,p_2-p_1>}{|p_2 - p_1|} - p_1|},\frac {p_3 - \frac {<p_3,p_2-p_1>}{|p_2 - p_1|} - p_1}{|p_3 - \frac {<p_3,p_2-p_1>}{|p_2 - p_1|} - p_1|}>)$

The triangle forming the smallest is the one to pick.

So for deriving it, I subtracted away the component along the line $(p_1p_2)$ from each point $p_3$ and $p_4$ along with the point $p_1$. My belief is that the angle between these two resulting vectors is the angle between the two planes. Then, normalizing them and taking their distance in spherical geometry (since the normalized vectors are in the Spherical Plane) should yield the actual angle between the triangles. The triangle forming the smallest angle should be the one extending the geodesic.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.