I’ve been thinking for a while and I can’t figure out a good way to find if a triangle intersects a rectangle in the way described in the picture above.
I was originally thinking I should interpolate between each of the vertices of the triangle and then check to see if any of the points in the interpolated values array were within the bounds of the rectangle.
My question would be, how can I do this more efficiently?
https://www.google.com/search?q=rectangle+triangle+intersection+test
One option is to test each line in the triangle against the rectangle, perhaps first testing the triangle’s bounding box against the rectangle.
+1 on @BurntPizza but of course bearing in mind the cases that the triangle is completely contained within the rectangle or that the rectangle is completely contained within the triangle. For both of these cases there will be no line intersections. The test would be is one (only need to test one) of the triangle’s vertices inside the rectangle and is one of the rectangle’s vertices inside the triangle.
In addition to the previous posters’ recommendations, I’d suggest looking into the separating axis test if all you need is a boolean result (or a boolean result and a separation vector). The SAT for the shapes in question is fairly straightforward and will handle all cases correctly (including containment).
If you need the actual area of intersection as shown in your diagram, then that’s a CSG problem, more or less, which is a little more involved.
SAT is almost never a good idea. It’s only upsides is that it works and it’s simple to implement.
So what’s bad about it when it works and is simple to use?
Bubble sort works and is simple. But that’s a bad example because sometimes bubblesort is a good choice.
Roquen, could you explain why SAT would be a poor choice in this case, and what method or methods you think should be preferred? I think that information would be very useful to the OP (and to anyone else, like me, who’s interested in these topics and always looking to expand their knowledge).
@The OP: Just in case Roquen doesn’t get around to elaborating, let me offer some counterpoint here. Although I’m always happy to be shown to be wrong, I’m not entirely sure Roquen is correct here, and in absence of supporting explanation I’d recommend not jumping to the conclusion that the SAT is a poor choice.
First of all, the bog-standard canonical axis-aligned box test that we all know and have seen implemented countless times is in fact the separating axis test, so obviously the SAT has valid applications.
Now, maybe this is why Roquen said ‘almost’. However, the question then becomes, if the SAT is good for axis-aligned boxes, why is it not applicable elsewhere, and at what point do other options start to look better?
In 3-d the SAT can be problematic in some cases due to numerical issues or excessive number of axes. However, these concerns don’t apply in the given context. If your triangles are axis-aligned like in your image, the SAT here is only a bit more involved than the axis-aligned box case, so it’s a little difficult for me to imagine why the SAT would suddenly become unsuitable in this case. Even if your triangles are arbitrary, you’re still only talking about 5 axes to test total.
Additionally, the discrete SAT for simple 2-d tests has the advantages of being entirely stable and robust (given good input), of handling all cases correctly (no concerns about containment or other special cases), and of being easily extended to return a minimum translational vector that can be used to resolve the intersection.
I do think this:
[quote]It’s only upsides is that it works and it’s simple to implement.
[/quote]
Is kind of interesting 
What strikes me as amusing about this is that ‘it works and is simple to implement’ is really quite an endorsement! I mean really, as long as it’s also reasonably efficient (which it is in this case), what more could you ask for? 
Anyway Roquen, I’m sure you have reasons for discouraging its use, but I think some elaboration would be helpful here.
I’ve covered “why not SAT” before. It’s silly to say that AABB is SAT. We really don’t even know what the problem is since OP seems to be AWOL.
EDIT: Picturing it in my head, maybe in 3D: AABB vs. a tri. SAT might be reasonable…humm. Maybe think about that after my vacation.
[quote]I’ve covered “why not SAT” before.
[/quote]
I did a quick search, but couldn’t find anything. Could you provide a link?
[quote]It’s silly to say that AABB is SAT.
[/quote]
The standard intersection test for axis-aligned boxes is absolutely an application of the SAT. I can provide support for this if needed.
Now, maybe by ‘SAT’ what you really mean is non-trivial SAT, but if so I think that probably needs to be specified.
I really don’t mean to be contrary or difficult, but I can’t help but question your claims here. What I’m seeing is that you’re saying the axis-aligned box test is not an application of the SAT, but haven’t explained why, and that the SAT should seldom or never be used, but haven’t given any reasons for this or suggested any alternatives.
I realize you say you’ve discussed this before and evidently are reluctant to repeat yourself, but I think even something like the following would really help clarify things:
1. The SAT should not be used because it’s <inefficient/unstable/etc.>.
2. Instead, you should use .
I’m sure this would only take a couple minutes, and I think would be helpful to a lot of people (me included!).
If you guys don’t know why I need this, basically that rectangle in the image in the main post is the application screen and the triangle is a triangle that was 3D originally but is now 2D because it was projected. I’m just too lazy to implement triangle-only clipping and I’m trying to think of different ways to get the effect.
What’s the context exactly? (I’m just curious because this suggests you’re doing something fairly low-level.)
Also, do you just need a boolean result? Or do you need to clip the triangle to the screen? If boolean only, is a conservative test ok, or do you need an exact test?
3D software rasterizer which I optimized for 3rd person a while ago is now performing horribly in 1st person mode because the triangles were way smaller in 3rd person. I used to just handle culling like this: basically I would only draw the triangle if 1 or more of its vertices were in the view window. But because the screen is a rectangle, a triangle in the corner of the screen could have all of its vertices outside of the view window however that little bit (shown in the main post’s image) could be within the screen.
I just need a boolean and I need it to be a 100% accurate boolean test.
provide link: not from my cell I’m not…nag me after I’m back if you still care.
Sure you can think of AABB as being SAT, but it’s really just a set of independent interval intersection tests. So it’s just a set of zero dimensional problems over Reals. To my mind it’s just as logically to call the standard sphere-sphere (circle-circle) intersection tests SAT. Heck you even calculate the direction of normal of the partitioning line/plane…but in both cases the argument is as circular as the test. Of course the partition must exist if they don’t intersect. Probably the association of AABB with SAT is it’s a simple first example of why the partition must exist in the non-overlapping cases.
What you seem to be really saying is: “Use the symmetry Luke!” I’d endorse that statement.
Personally I if talk about SAT it’s only going to be about an iterative “find the partition” method, so probably what you’re calling non-trivial. And instead one should generally use one of the Minkowski summation based methods that ideally someone else has already written for you.
@Roquen: It sounds like the disagreement here is basically over what ‘separating axis test’ means.
I’m sure you’d agree that the SAT for arbitrary convex polytopes is really the SAT. The SAT for oriented boxes is of course just a special case of the convex polytope case, with the regularity of the shapes exploited to simplify the test. Adding the further constraint that the boxes be axis-aligned causes most of the remaining complexity to drop out, and you’re left with the canonical axis-aligned box test.
What you seem to be saying is that somewhere in this process of simplification, the SAT stops being the SAT. I can’t really follow the logic on this, as it would seem to suggest that simplifying an algorithm for a special case causes that algorithm not to be that algorithm anymore.
In any case, it does indeed seem that you’re using the term ‘SAT’ to mean ‘non-trivial SAT’, so I guess we should probably just leave it at that.
As for Minkowski-based approaches, thank you for suggesting an alternative It’d be interesting to compare a Minkowski-based approach with the SAT for relatively simple shapes (such as boxes and triangles) in 2-d in terms of efficiency, robustness, and ease of implementation. Based on my past experience working with Minkowski-based algorithms I’m a little skeptical that they’d be preferable over the SAT for simple 2-d cases, but I think some formal investigation would be needed to really weigh the two against each other.
Anyway, this has obviously wandered a bit far afield as far as the OP’s case is concerned. Not having done any software-rendering work as of late, I don’t really feel confident in making any suggestions there, so I’ll leave that to others.
@OP: to flesh out my answer:
This SO thread has theory and code for treating the triangle as 3 line segments against a AABB: http://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d
If speed turns out to be an issue with that method and triangles are often well outside of the rectangle, then computing and testing against the triangle’s own AABB might be a fast way to confirm negatives before doing the full line-line-line-rect test, esp. if the triangles coordinates are stored in a way that makes computing the AABB easy.
@Jesse - thread pollution is traditionally. The ‘T’ of SAT is for theorem. And whole thing is a misnomer because it’s really the hyperplane separation theorem (Minkowski did this too). Any two convex bodies that don’t intersect must have at least one separating partition (which projects into the axis)…all well and good. Mathematicans that were alive way before Minkowski was born knew how to compute AABB and sphere-sphere intersections (and many other). Neither of these tests explicitly use the theorem for the result. Of course you have to see how it relates, because it must hold.
On specific specialized tests, the best method will be the one that best exploits the symmetry of problem. Like sphere-sphere/point is distance field with a change of metric. Go toward the bottom of the link below, looking for Rectangle intersection with Points and Circles. The part were I’m extending the point to a circle is Minkowski addition.
http://www.java-gaming.org/topics/vectors-what-s-the-point/24307/view.html
[quote=“Roquen,post:17,topic:55192”]
I’m familiar with these methods and with Minkowski sums. I’ve used them in a variety of contexts myself and in fact just recently provided a solution based on Minkowski sums to someone here on the forums. The material you’re presenting is familiar to me.
I think I’ll just hold to my previous objections. What you seem to be saying is that if an algorithm can be simplified for a special case, it’s no longer the same algorithm. You also seem to be saying that if a newly developed theorem covers cases for which the solutions were already trivially obvious, then it doesn’t ‘really’ apply to those cases. Both of these claims seem illogical to me, but perhaps I’m misunderstanding you.
In any case, as I said before I’m happy to leave it as a semantic disagreement. I think at this point trying to determine whether the separating axis test ‘really’ applies to trivial cases would require more discourse than would be appropriate for this thread. To me it’s obvious that it does, based on both principle and voluminous practical evidence, but obviously your view differs.
Hey thats not a triangle… thats a piece of cloth :3