Computational geometry, volume of the signed tetrahedron

Question

I'm not sure if this is the right place, but here goes ...

Short version: I am trying to calculate the orientation of a triangle on a plane formed by the intersection of three edges without explicitly calculating the intersection points.

Long version: I need to triangulate the PSLG into a triangle in 3D. The vertices of PSLG are determined by the intersections of line segments with the plane through the triangle and are guaranteed to lie within the triangle. Assuming I have intersection points, I could project in 2D and use a test line (or triangular signed area) to determine the orientation of the triangle between any three intersection points.

The problem is that I cannot explicitly calculate the intersection points due to the floating point error that accumulates when I find the intersection of the line. To find out if line segments actually fall into a triangle, I use some freely available reliable geometric predicates that give the volume sign of the tetrahedron or equivalently on which side of the plane the point is. I can determine if the endpoints of the line segment are on opposite sides of the plane through the triangle, then form tetrahedra between the line segment and each edge of the triangle to determine if the intersection point is inside the triangle.

Since I cannot explicitly calculate the intersection points, I wonder if there is a way to express the same 2D-oriented calculation in 3D using only the source points. If there are 3 edges hitting a triangle that gives me 9 points in total to play. Assuming I ask, maybe even (using only 3D tests), then I assume that I will need to form a subset of all possible tetrahedra between these 9 points. It’s hard for me to even visualize this, not to mention overtaking it into a formula or code. I can’t even do this because I don’t know what industry standard terminology might be for this type of problem.

Any ideas how to do this? Thank you Perhaps I should also ask MathOverflow ...

EDIT: after reading some comments, one thing that comes up with me ... Perhaps if I could put non-overlapping tetrahedra between the three segments of the line, then the orientation of any of those that intersected the plane would be the answer I'm looking for. In addition, when the edges cover a simple triangular prism, I am not sure that this subtask is also solvable.

EDIT: The requested image.

Answer 1

I answer this on both MO and SO, expanding on the comments I made on MO.

I believe that no computational tricks with signed volumes of the tetrahedron will fix the accuracy problems that you primarily care about. This is because if you have tightly twisted segments, the orientation of the triangle depends on the exact location of the cutting plane.
[image deleted; see below]
In the above example, the upper plane intersects the segments in the order (a, b, c) [ccw above]: (red, blue, green), and the lower plane intersects in the reverse order (c, b, a): (green, blue, red). The height of the cutting plane can be determined by your last home of precision.

Therefore, I believe that it makes sense to just go and calculate the intersection points in the cutting plane, using sufficient accuracy to make the calculation accurate. If the coordinates of the endpoints of the segment and the planar coefficients have L bits of accuracy, then only a small increase in the constant coefficient is required. Although I'm not sure exactly what this factor is, it is small - maybe 4. You do not need, for example, L ² bits, because the calculation solves linear equations. Thus, there will not be a burst of accuracy necessary to calculate this for sure.

Good luck

(I was unable to post a clarifying image because I have no reputation. Reply instead of MO .)

Edit : see MO answer, but here is the image:

Answer 2

I would call symbolic vector equations, with point and cross products, to find the normal of the intersection triangle. Then the sign of the point product of this normal with the initial triangle gives orientation. So you can express this in the form of a form (F (p1, ..., p9)), where p1 - p9 are your points, and F () is an ugly formula, including points and cross-products of differences (pi-pj) I don’t know if this can be done easier, but this general approach does the job.

Answer 3

As I understand it, you have three lines intersecting the plane, and you want to calculate the orientation of the triangle formed by the intersection points without calculating the intersection points themselves?

If yes: do you have a plane

  N (x - x 0 ) = 0

and six points ...

  l 1a , l 1b , l 2a , l 2b , l 3a , l 3b 

... forming three lines

  l 1 = l 1a + t (l 1b - l 1a )
 l 2 = l 2a + u (l 2b - l 2a )
 l 3 = l 3a + v (l 3b - l 3a )

The intersection points of these lines to the plane occur at certain values ​​of t, u, v, which I will call t _i , u _i , v <sub> yasub>

  N (l 1a + t i (l 1b - l 1a ) - x 0 ) = 0

       N (x 0 - l 1a )
 t i = ----------------
       N (l 1b - l 1a )
 (similarly for u i , v i )

Then specific intersection points

  intersect 1 = l 1a + t i (l 1b - l 1a )
 intersect 2 = l 2a + u i (l 2b - l 2a )
 intersect 3 = l 3a + v i (l 3b - l 3a )

Finally, the orientation of your triangle

  orientation = direction of (intersect 2 - intersect 1 ) x (intersect 3 - intersect 1 )

(x is the cross product). Work backwards by plugging in the values ​​and you will have an equation for an orientation based only on N, x ₀ and your six points.

Answer 4

Let your triangular vertices be called T[0] , T[1] , T[2] , and the endpoints of the first segment are L[0] and L[1] , the second is L[2] and L[3] , and the third is L[4] and L[5] . I assume you need a function

 int Orient(Pt3 T[3], Pt3 L[6]); // index L by L[2*i+j], i=0..2, j=0..1 

which returns 1 if the intersections have the same orientation as the triangle, and -1 otherwise. The result should be symmetric in the exchange of values ​​of j , antisymmetric in the exchange of values ​​of i and T While you can calculate the quantity with these symmetries, that’s all you need.

Try

 Sign(Product( Orient3D(T[i],T[i+1],L[2*i+0],L[2*i+1]) * -Orient3D(T[i],T[i+1],L[2*i+1],L[2*i+0]) ), i=0..2)) 

where the product should be taken over cyclic permutations of the indices (modulo 3). I believe that this has all the necessary symmetry properties. Orient3D is a four-point test in the Shevchuk plane, which I assume you are using.