Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Short version: I'm trying to compute the orientation of a triangle on a plane, formed by the intersection of 3 edges, without explicitly computing the intersection points.

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

The problem is I can't explicitly compute the intersection points because of the floating-point error that accumulates when I find the line-plane intersection. To figure out if the line segments strike the triangle in the first place, I'm using some freely available robust geometric predicates, which give the sign of the volume of a tetrahedron, or equivalently which side of a plane a point lies on. I can determine if the line segment endpoints 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 whether the intersection point lies within the triangle.

Since I can't explicitly compute the intersection points, I'm wondering if there is a way to express the same 2D orient calculation in 3D using only the original points. If there are 3 edges striking the triangle that gives me 9 points in total to play with. Assuming what I'm asking is even possible (using only the 3D orient tests), then I'm guessing that I'll need to form some subset of all the possible tetrahedra between those 9 points. I'm having difficultly even visualizing this, let alone distilling it into a formula or code. I can't even google this because I don't know what the industry standard terminology might be for this type of problem.

One thing that occurs to me: Perhaps if I could fit non-overlapping tetrahedra between the 3 line segments, then the orientation of any one of those that crossed the plane would be the answer I'm looking for. Other than when the edges enclose a simple triangular prism, I'm not sure if this sub-problem is solvable either.

Any ideas how to proceed with this? Thanks.

share|improve this question
2  
Not certain, but perhaps it is not possible to avoid precision issues even if you work with the three segments in 3D. If the segments are "twisted" tightly about one another, then the exact position of the cutting plane determines the orientation of the determined triangle. Because segment/plane intersection is a linear computation, the precision doesn't increase that much, so it may be better to just compute that exactly and swallow the cost. –  Joseph O'Rourke Jul 12 '10 at 17:16
    
Compute exactly? Do you mean with an arbitrary precision arithmetic library? I tried computing the intersection points to double precision and I run into what I assume are precision problems when those points are close to the edges or vertices of the triangle. The predicates I'm using are the CMU Shewchuk ones, with simulation-of-simplicity on top of that. That appears to reliably determine if the line segments strike the triangle at all, so perhaps it's not unreasonable to expect it to work for this problem too, assuming it's broken down into just the tet signed volume tests. I'm not sure. –  mr grumpy Jul 12 '10 at 17:58
    
@mrgrumpy: I cannot quote exactly, but if your segment endpoint coordinates and plane normal vector have $L$ bits of precision, then the intersection points on the plane need at most $k L$ bits of precision, where $k$ is small, maybe 3 or 4(?). If you look this up, then you could compute the points exactly by allocating sufficient precision. –  Joseph O'Rourke Jul 12 '10 at 18:44
    
Link to question on SO: stackoverflow.com/questions/3230171 –  BlueRaja Jul 12 '10 at 23:20
    
@BlueRaja: Thanks. I posted also to SO, but there I don't have the rep to post an image! Oh well... –  Joseph O'Rourke Jul 13 '10 at 12:43

2 Answers 2

up vote 2 down vote accepted

I am answering this on both MO & SO, expanding the comments I made on MO.

My sense is that no computational trick with signed tetrahedra volumes will avoid the precision issues that are your main concern. This is because, if you have tightly twisted segments, the orientation of the triangle depends on the precise positioning of the cutting plane.
alt text
In the above example, the upper plane crosses the segments in the order (a,b,c) [ccw from above]: (red,blue,green), while the lower plane crosses in the reverse order (c,b,a): (green,blue,red). The height of the cutting plane could be determined by your last bit of precision.

Consequently, I think it makes sense to just go ahead and compute the points of intersection in the cutting plane, using enough precision to make the computation exact. If your segment endpoints coordinates and plane coefficients have $L$ bits of precision, then there is just a small constant-factor increase needed. Although I am not certain of precisely what that factor is, it is small--perhaps 4. You will not need e.g., $L^2$ bits, because the computation is solving linear equations. So there will not be an explosion in the precision required to compute this exactly.

Good luck!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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