Iterating through a 3D triangle

Question

Given a triangular plane formed by three points in R3 space {p1, p2, p3}, I want to iterate through all points on the triangle plane by using two variables, x0,y0, something like in this example: http://demonstrations.wolfram.com/DirectionalDerivativesIn3D/ The example in that website uses directional derivatives.

If this was in 2D, it is easy to iterate through the triangle, by using 2 for-loops (one each for x & y axis) and looping through a rectangular bounding box formed by that triangle. I could then use barycentric coordinates to isolate the points that fall within the triangle.

However, for 3D space, I have no clue how to do it. Any help or idea would be appreciated.

Answer 1

Why not transform your coordinates into the plane of the triangle and do your iterations there?

Answer 2

If you use barycentric coordinates then the number of dimensions in which the triangle is embedded does not matter; the conversion from barycentric coordinates to euclidean coordinates is just a convex combination of the euclidean points at the vertices of the triangle.

Answer 3

To iterate over the triangle points you could follow this algorithm:

• find the longest edge and use it as direction for the inner loop, in the following it is assumed that the longest edge is (p1,p2) with the third point is p3

• For the inner loop always iterate along the direction D:(p1->p2)

• Iterate along this line starting at point A=p1 with a given step length L until you reach B=p2.

• move into direction of point p3 by updating A=p1 + (p3-p1)*L13, and B=p2+(p3-p2)*L23. L13, L23 are evaluated from the step length for the second dimension that is picked based on the distance of p3 to the line (p1,p2). It should be trivial to get the right formula.

• repeat the iteration from A to B by using the same direction vector D

• continue until all the triangle was covered.

Some C++ code that implements this can be found here, look for draw_triangle, but note that the code also checks whether the points of the line are within a given bounding box, and you would replace draw_point with whatever action you want to run on the triangle point.

(Since I am the author of this GPLed code, I hereby grant the license to freely use the parts of filling a triangle in 3D space to be used as blueprint for one's own implementation).

Answer 4

You could compute the normal of your plane (by cross product) and rotate the plane in opposite direction. This will make the &z& coordinates identical. Then you could project the plane onto 2D cartesian by simply ignoring &z&. Yet you still have a direct map (correspondence) of each triangle coordinate in 3D to the ones in 2D. You can iterate in 2D grid and always map to 3D.

Answer 5

To do it on a plan aligned triangle, you just have to make a loop that fulfils three conditions: for i... i++ if current tested point is on left of line ab, right of line bc and above line ac, point is within triangle. then you just need to use the xy plane that the triangle is pointing at, which is described by the smallest x,y,z value of the ortho axis,

use a square containing all 3 points, loop xy points, move y one higher if x goes from true to false if you want to optimize.

its a lot easier to find fairly random points on a triangle.