i want to develop a method for path finding on a 3D model. The actual model consists of Vally and hills. I want to mark some points and connect them, the problem is that these points connect through the model, so the user can not see them. I was searching for some methods of projecting this line to the surface, or finding some other points on the surface e.x by interpolation, but i am not sure the points of interpolation will be on the surface or not. my idea is to use these points to cast them on a plane, make a line on the plane and project it again on the model. I am not sure if it will work or not. If anyone has a better idea i appreciate to hear.
If your model consists of valleys and hills, it sounds like it is a 2D surface (by 2D surface, I mean, there is exactly one Y coordinate for any XZ pair). Given that assumption, if you conceptually look at your model from above (i.e., disregard the Y coordinates), you see a 2D tessellated/meshed/triangulated area. Find two points you want to connect with a line on that surface. Intersect that line with every triangle edge on the surface that crosses it. (Each intersection will produce X, Y, and Z coordinates.) Draw a short line segment across each triangle that crosses the line by connecting the calculated intersection points. Each such line segment will be on the surface of the triangle that it traverses, and the collection of those short lines will be the shortest path (as the crow flies) between your two original points.
Thanks for the quick reply. I thought about this method before, but actually in 3D. I intended to find the intersection of a plane and triangles, but the reason i gave up was that i have no idea on how to find the intersection between line(plane) and triangles edges? Can you please give me some tips. btw, i am going to apply this method in LabView.
You compute the intersections of the line and the triangle edges in 2D (XZ space - completely ignore the Y coordinates), and then interpolate between the XZ endpoints of each triangle edge that crosses the line to get the proper Y coordinate.
So, for example, if the XZ line crosses an XZ triangle edge 1/3 of the way from the first to the last endpoint of a triangle edge, then the Y coordinate of the line at the XZ intersection will be the value 1/3 of the way between the Y coordinates at the endpoints of that triangle edge.
So, there’s two major steps:
Process all 3 edges of each triangle as a group: find their parametric intersections with the XZ line. If all three edges have a parametric intersection either less than zero and/or greater than one, then the triangle doesn’t intersect the XZ line, otherwise it does.
For the intersecting triangles, interpolate between the 3D endpoints of the triangle edges using the parametric intersections found in step one. Those are the 3D endpoints of the short line segments to draw.
The link doesn’t explain how to convert an intersection point to parametric form, but that’s straightforward application of 1D proportions:
if the line is wider than it is tall, P = (Xi - X0) / (X1 - X0)
if the line is taller than it is wide, P = (Yi - Y0) / (Y1 - Y0)
Oops, I made a mistake in my previous post (I hope it was obvious). The last lines should have been:
“The link doesn’t explain how to convert an intersection point to parametric form, but that’s a straightforward application of 1D proportions:”
if the line is wider than it is deep, P = (Xi - X0) / (X1 - X0)
if the line is deeper than it is wide, P = (Zi - Z0) / (Z1 - Z0)
Where P is the parametric proportion, (Xi,Zi) is the 2D point of intersection of the XZ line and a XZ triangle edge, (X0,Z0) is the first 2D endpoint of the XZ triangle edge, and (X1,Z1) is the other 2D endpoint of the XZ triangle edge.