Objects within a triangle

Unity Engine
1

Hello,

Ok i have a problem i been trying to solve for the past couple hours with no luck.

Say i have 3 vector3’s (a, b and c) and i want to determine what objects lie within the triangle that they make and are only in front of the triangle not behind. The objects can be in front of the triangle, they just have to within it in terms of not on the outside of the lines. And the triangle will be constantly rotating in all different directions.

I know how to cycle through the game objects and stuff but i have no idea how i would determine if the objects are within the triangle.

Any help would be awesome Thanks!

2

First you need four planes: the plane in which the triangle lies, and three additional planes, each perpendicular to the triangle plane and containing one of the edges of the triangle.

The normal for the first plane can be computed by taking the cross product of two of the triangle edges and (optionally) normalizing it. To find the plane distance, compute the dot product of the plane normal and a vertex from the plane.

Computing the ‘edge planes’ is similar, except the terms of the cross product are the edge direction and the triangle normal, and the point used to compute the distance should be one of the edge endpoints.

Finally, to see if a point is in front of the triangle and within the specified boundaries, test the query point against each of the four planes. Bases on the results of these tests, you can determine whether or not the point is contained (the details will depend on which way the plane normals are pointing).

3

You know, Unity has already handled all that stuff for you. :roll:

4

Maybe a bit faster if you calculate it yourself. I wrote this code for a processing application following this article.
Here is the code (it’s java/processing - not usable like this in C# or javascript):

  /* Returns true if point p lies inside triangle a-b-c */
  boolean pointInTri(PVector a, PVector b, PVector c, PVector p)  {
    PVector v0 = PVector.sub(b,c);
    PVector v1 = PVector.sub(a,c);
    PVector v2 = PVector.sub(p,c);
    float dot00 = v0.dot(v0);
    float dot01 = v0.dot(v1);
    float dot02 = v0.dot(v2);
    float dot11 = v1.dot(v1);
    float dot12 = v1.dot(v2);
    float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
    return (u > 0)  (v > 0)  (u + v < 1);
  }

“PVector” is just a class that holds two values as x and y coordinates and offers geometric functions such as dot-product etc.

EDIT: Transforming to C# is easy, just turn PVector into Vector2…

  /* Returns true if point p lies inside triangle a-b-c */
  boolean PointInTri(Vector2 a, Vector2 b, Vector2 c, Vector2 p)  {
    Vector2 v0 = b-c;
    Vector2 v1 = a-c;
    Vector2 v2 = p-c;
    float dot00 = Dot(v0,v0);
    float dot01 = Dot(v0,v1);
    float dot02 = Dot(v0,v2);
    float dot11 = Dot(v1,v1);
    float dot12 = Dot(v1,v2);
    float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
    return (u > 0.0f)  (v > 0.0f)  (u + v < 1.0f);
  }
5

This was helpful thank you all :slight_smile:

6

I don’t know if that was in response to my post, but unless you can point me to a function that determines whether a point lies in front of a triangle’s plane and within the orthogonal extrusion of that triangle, then no, Unity doesn’t handle all that stuff for you.

7

You didn’t do that either. What you said was

Personally, I don’t feel we’ve been given enough information to come up with a good solution. Something involving barycentric coordinates may be the fastest method if the triangle is in a plane.

8

In what way was my answer not correct?

The OP stated that the objects must be ‘only in front of the triangle not behind’, which suggests that only objects in the positive halfspace of the triangle’s supporting plane be considered.

The OP then stated that the objects ‘just have to within it in terms of not on the outside of the lines’. Granted, the meaning of this isn’t unequivocally clear, but can you suggest a reasonable interpretation other than ‘falling within the orthogonal extrusion of the triangle’?

(If that’s not what the OP meant, perhaps he or she could clarify for us.)

Right, so the Unity Plane class includes a function for computing the distance to a point. But that’s just an implementation detail - it’s not a solution to the problem. So what was the ‘eye roll’ for?

How can a triangle not be in a plane?

Sure, there are different ways the solution can be expressed; some may be a little more or less efficient than others, but they all reduce to pretty much the same thing.

Anyway, not trying to be contrary - I guess I just don’t get what your point is. (And I still don’t see what was wrong with my original reply.)

9

It’s at a plane at any point in time. If it’s spinning in 3D, the solution will be more complicated. I don’t even know if barycentric coordinates would be helpful then; I don’t know enough about them.

There’s nothing wrong with it. You’re just taking offense and wasting time and typing too many words and you like hearing yourself type and you like punching with your fingers and should take out your frustration on something you can bite instead! MAYBE YOU’RE JEALOUS THAT MY NAME IS SPELLED BETTER!

10

That’s a pretty strange response :expressionless:

I provided an answer to the OP’s question. You replied that ‘Unity has already handled all that stuff for you’ (which doesn’t even make sense), and then threw in an ‘eye roll’ emoticon. Are you really that surprised you got a reaction? :slight_smile:

The solution isn’t more complicated if the triangle is spinning. Whether it’s spinning or stationary, you can still use barycentric coordinates (or ‘side planes’, which is really just another way of expressing the barycentric coordinate solution) with no problem.