Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (575) Games in Android Showcase (154) games submitted by our members Games in WIP (623) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: 1 [2]
 ignore  |  Print
 Getting distance of a point in a 2d triangle without calculating perpendicular..  (Read 7335 times) 0 Members and 1 Guest are viewing this topic.
CyanPrime
 « Reply #30 - Posted 2012-06-22 20:34:28 »

CyanPrime
 « Reply #31 - Posted 2012-06-23 23:21:35 »

Getting distance of a point in a 2d triangle without calculating perpendicular vectors? <-- full topic

Alright, so I'm trying to get the distance of a point in a 2d triangle without calculating perpendicular vectors.

float qd = Vector2f.dot(new Vector2f(pos.x, pos.z), new Vector2f(normal.pos.x, normal.pos.z)) - Vector2f.dot(new Vector2f(q.center.x, q.center.z), new Vector2f(normal.pos.x, normal.pos.z));

That's the code I'm using. (Note: it's converting 3f vectors to 2d ones, but you don't have to worry about that). I need the result of the calculation to be between 0 and 1 I.E. 0.5 or something.

If I'm still not explaining right maybe this will help?

My question is: How do I get the distance of a point in a 2d triangle without calculating perpendicular vector's distance? I.E. if the tringle is facing up (y = -1) without any tilt I would need the distance in the triangle without any X.
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #32 - Posted 2012-06-23 23:36:25 »

What does "distance of a point" mean? Distance to what? Distance to the closest point on the triangle?

See my work:
OTC Software
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #33 - Posted 2012-06-23 23:37:02 »

CyanPrime, I warned you on IRC about making a new topic for every little geometry problem you run into. This was your 7th topic or so. It's now merged into one.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
CyanPrime
 « Reply #34 - Posted 2012-06-23 23:39:27 »

What does "distance of a point" mean? Distance to what? Distance to the closest point on the triangle?
Distance from the top of the triangle?
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #35 - Posted 2012-06-24 00:04:59 »

Still not clear enough. The "top" of the triangle is relative. Think if it in terms of only a point in space and its relation to a triangle in space. Sounds like you want the closest point on the triangle.

OR, if you're talking something in global space where negative on the global Y axis is always down, then you can cast a ray from the point to the triangle along the Y and get that distance.

Which do you mean?

See my work:
OTC Software
jonjava
 « Reply #36 - Posted 2012-06-24 23:14:55 »

Getting distance of a point in a 2d triangle without calculating perpendicular vectors? <-- full topic

Alright, so I'm trying to get the distance of a point in a 2d triangle without calculating perpendicular vectors.

show us the from and to points for both triangles.

CyanPrime
 « Reply #37 - Posted 2012-06-28 03:58:56 »

Yeah, but you also need to check the cross product to make sure it's on the right side. Like this (broken into two functions to preserve code).

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19 `public boolean isPointInTriangle( Vector3f p, Vector3f a, Vector3f b, Vector3f c ){    return ( pointsAreOnSameSide(p, a, b, c) && pointsAreOnSameSide(p, b, a, c) && pointsAreOnSameSide(p, c, a, b) );}public boolean pointsAreOnSameSide( Vector3f p1, Vector3f p2, Vector3f a, Vector3f b ){    Vector3f diffba = new Vector3f(0,0,0);    Vector3f.sub( b, a, diffba );    Vector3f diffp1a = new Vector3f(0,0,0);    Vector3f.sub( p1, a, diffp1a );    Vector3f diffp2a = new Vector3f(0,0,0);    Vector3f.sub( p2, a, diffp2a );    Vector3f cross1 = Vector3f.cross(diffba, diffp1a);    Vector3f cross2 = Vector3f.cross(diffba, diffp2a);    return ( Vector3f.dot( cross1, cross2 ) >= 0 );}`

Holy god LWJGL vectors are lame? Why no myVec.sub(otherVec) etc. You really need to pass everything into static functions? Stupid. Why not put both in there?
Does anyone know of a way I could add a radius to this code for p? Like basically saying "this is true if the triangle is < N dist from the point"
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #38 - Posted 2012-06-28 04:10:29 »

BTW: your isPointInTriangle method might not do what you think it does.

It will return true for points inside an infinitely far stretching volume (confined by the three planes of the triangle).

Are you by any chance simply looking for triangle->sphere collision detection?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #39 - Posted 2012-06-28 15:41:43 »

Yeah, now you're asking for something totally different - sphere/circle and triangle collision.

I think that would go something like first testing if the center of the circle is inside the triangle using our previous method (if so, then obviously you have a collision), then by checking to see if the point is within radius distance of any of the sides (if so, we have a collision).

I tried this out with my little script I pasted earlier and it works.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49 `public static boolean isCircleInTriangle( boolean barycentric, Vector3f p, float r, Vector3f a, Vector3f b, Vector3f c)   {      //is the point inside the triangle?      if ( isPointInTriangle(barycentric, p, a, b, c) )      {         return true;      }            //is the point within the radius of any of the line segments?      float rSquared = r * r;      if ( getSquaredDistanceToLineSegment( p, a, b ) <= rSquared )      {         return true;      }      if ( getSquaredDistanceToLineSegment( p, a, c ) <= rSquared )      {         return true;      }      if ( getSquaredDistanceToLineSegment( p, b, c ) <= rSquared )      {         return true;      }            return false;   }      private static float getSquaredDistanceToLineSegment( Vector3f p, Vector3f a, Vector3f b )   {      Vector3f ab = b.subtract(a);      Vector3f ap = p.subtract(a);            float dotabap = ab.dot(ap);      float dotabab = ab.dot(ab);            //if we're closest to a vertex, return the distance to that vertex      if ( dotabap <= 0.0f )      {         return p.squaredDistance(a);      }      if ( dotabab <= dotabap )      {         return p.squaredDistance(b);      }            //if not, calculate the distance to the segment      float ratio = dotabap / dotabab;      Vector3f nearestPoint = new Vector3f( a.x + ab.x * ratio, a.y + ab.y * ratio, a.z + ab.z * ratio );      return p.squaredDistance(nearestPoint);   }`

See my work:
OTC Software
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #40 - Posted 2012-06-28 16:31:16 »

@Eli Delventhal: how do you prevent a true response with infinitely far spheres that lie in the volume confined by the 3 planes? You have to check for the distance to a 4th plane too: the plane on which the triangle lies.

IMHO the method name 'isPointInTriangle' is incredibly misleading in 3D.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
CyanPrime
 « Reply #41 - Posted 2012-06-28 17:16:53 »

Eli, is the formula for
 1 `p.squaredDistance(a)`
just
 1  2 `float dist = sqrt((p.x-a.x)^2 + (p.y-a.y)^2 + (p.y-a.y)^2dist = dist * dist`

?
ra4king

JGO Kernel

Medals: 374
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #42 - Posted 2012-06-28 17:28:51 »

Or simply remove the sqrt.
 1  2 `float xd = p.x-a.x, yd = p.y-a.y, zd = p.z-a.z;float squaredDist = xd*xd + yd*yd + zd*zd;`

Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #43 - Posted 2012-06-28 17:44:35 »

@Eli Delventhal: how do you prevent a true response with infinitely far spheres that lie in the volume confined by the 3 planes? You have to check for the distance to a 4th plane too: the plane on which the triangle lies.

IMHO the method name 'isPointInTriangle' is incredibly misleading in 3D.
Not sure exactly what you mean, Riven, but I'm sure this has issues in 3D. I was thinking in terms of 2D despite all the vectors being 3D vectors. If you can suggest specific code edits or be more clear that'd be handy for everyone.

See my work:
OTC Software
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #44 - Posted 2012-06-28 17:45:56 »

Eli, is the formula for
 1 `p.squaredDistance(a)`
just
 1  2 `float dist = sqrt((p.x-a.x)^2 + (p.y-a.y)^2 + (p.y-a.y)^2dist = dist * dist`

?
What ra4king said. The point of using the squared distance is that you avoid needing to do square root calls, which are very costly. So it's just: (p.x-a.x)^2 + (p.y-a.y)^2 + (p.z-a.z)^2.

 1  2  3  4  5 `public float squaredDistance( Vector3f other ){   Vector3f dist = other.subtract(this);   return ( dist.x * dist.x + dist.y * dist.y + dist.z * dist.z );}`

See my work:
OTC Software
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #45 - Posted 2012-06-28 17:47:39 »

So it's just: (p.x-a.x)^2 + (p.y-a.y)^2 + (p.y-a.y)^2.
Don't copy and paste bugs

 1  2  3  4  5 `public float squaredDistance( Vector3f other ){   Vector3f dist = other.subtract(this);   return ( dist.x * dist.x + dist.y * dist.y + dist.z * dist.z );}`
Don't create new objects in code that is performance critical enough to get rid of a square root

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ra4king

JGO Kernel

Medals: 374
Projects: 3
Exp: 5 years

I'm the King!

 « Reply #46 - Posted 2012-06-28 18:30:28 »

Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #47 - Posted 2012-06-28 19:41:05 »

So it's just: (p.x-a.x)^2 + (p.y-a.y)^2 + (p.y-a.y)^2.
Don't copy and paste bugs

 1  2  3  4  5 `public float squaredDistance( Vector3f other ){   Vector3f dist = other.subtract(this);   return ( dist.x * dist.x + dist.y * dist.y + dist.z * dist.z );}`
Don't create new objects in code that is performance critical enough to get rid of a square root
You're always such a friendly person, Riven. I find the second part of your post to be purposelessly confrontational. This is not going to end up being a bottleneck in his code. First of all, he doesn't use the vector class which has that function; the one I wrote in 30 seconds in an example java class (which you can see above if you were to scroll up). He uses the LWJGL vector class which just so happens forces you to instantiate extra vectors all over the place.

The entire point of posting that code snippet was to show him how to do what he needs to do, because clearly he doesn't understand enough to be worrying about performance at this juncture. I considered not putting the squared magnitude up there (and using regular magnitude instead) because I figured he would get confused - because efficiency isn't the point here. Looks like I should have done that, poor choice on my part.

Instead of your usual spiel of busting into a post and saying "you're wrong, you're wrong," how about to respond to the question I posted above by clarifying what you meant when you pointed out the only actual bug in the code?

Here you go:
 1  2  3  4  5  6  7 `public float squaredDistance( Vector3f other ){   float xDiff = other.x - x;   float yDiff = other.y - y;   float zDiff = other.z - z;   return ( xDiff * xDiff + yDiff * yDiff + zDiff * zDiff );}`

See my work:
OTC Software
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #48 - Posted 2012-06-28 20:12:42 »

Not meant to be so rough on you, I thought that the emoticons revealed that I wasn't too serious.

As per your request, here's an image that shows the problem in 3D:

From this, you can deduce that a sphere->triangle intersection works like this:
• ensure that the sphere either lies above or intersects plane A,B,C
• ensure that the sphere intersects plane D

Note that there is no need to calculate 'is on same side', which btw. contains a lot of redundant calculations, when you do it 3 times. The planes A,B,C already (should) have normals pointing towards the triangle.

Your code would have returned true for all spheres intersecting in the 'triangle volume' and those intersecting with the triangle edges.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #49 - Posted 2012-06-29 00:58:54 »

Ah of course, I see what you mean. I'll go in and edit this code at some point soon.

See my work:
OTC Software
CyanPrime
 « Reply #50 - Posted 2012-06-30 17:46:46 »

Alright, thank you all very much for your help so far.

Is there anyway I can see if the point is facing the normal in this code (from Eli)? My player is getting stuck on corners.

Edit: I'm using the circle in triangle for ground collision, so it's not going to waste. :>

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21 `public boolean isPointInTriangle( Vector3f p, Vector3f a, Vector3f b, Vector3f c )   {       return ( pointsAreOnSameSide(p, a, b, c) && pointsAreOnSameSide(p, b, a, c) && pointsAreOnSameSide(p, c, a, b) );   }   public boolean pointsAreOnSameSide( Vector3f p1, Vector3f p2, Vector3f a, Vector3f b )   {       Vector3f diffba = new Vector3f(0,0,0);       Vector3f.sub( b, a, diffba );       Vector3f diffp1a = new Vector3f(0,0,0);       Vector3f.sub( p1, a, diffp1a );       Vector3f diffp2a = new Vector3f(0,0,0);       Vector3f.sub( p2, a, diffp2a );       Vector3f cross1 = new Vector3f();             Vector3f.cross(diffba, diffp1a, cross1);       Vector3f cross2 = new Vector3f();              Vector3f.cross(diffba, diffp2a, cross2);       return ( Vector3f.dot( cross1, cross2 ) >= 0 );   }`
Eli Delventhal

JGO Kernel

Medals: 42
Projects: 11
Exp: 10 years

Game Engineer

 « Reply #51 - Posted 2012-07-02 15:10:56 »

Not sure what you mean. Points do not have a direction, so they can't face anything. And that code you pasted doesn't have any normals in it. You shouldn't need to redo anything to fix that bug - instead how you make your player react to collisions needs to be adjusted.

See my work:
OTC Software
Pages: 1 [2]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 BurntPizza (29 views) 2015-04-23 03:42:11 theagentd (35 views) 2015-04-22 16:23:07 Riven (48 views) 2015-04-16 10:48:47 Duke0200 (59 views) 2015-04-16 01:59:01 Fairy Tailz (41 views) 2015-04-14 20:13:12 Riven (44 views) 2015-04-12 21:36:37 bus hotdog (60 views) 2015-04-10 02:39:32 CopyableCougar4 (66 views) 2015-04-10 00:51:04 BurntPizza (70 views) 2015-04-06 22:06:58 ags1 (68 views) 2015-04-02 10:58:48
 theagentd 23x BurntPizza 17x wessles 15x kingroka123 11x alwex 11x 65K 11x kevglass 8x Rayvolution 7x Roquen 7x Riven 7x chrislo27 7x Hanksha 7x Olo 7x Ecumene 7x ra4king 7x KevinWorkman 6x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org