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

Offline 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.
Offline 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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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?
Offline 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
Offline 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.

 Clueless

show us the from and to points for both triangles.


Offline 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"
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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)^2
dist = dist * dist

?
Offline ra4king

JGO Kernel


Medals: 346
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;

Offline 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
Offline 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)^2
dist = 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
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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 Emo

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 Emo

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

JGO Kernel


Medals: 346
Projects: 3
Exp: 5 years


I'm the King!


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

Sad Riven is sad.

Offline 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 Emo

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 Emo
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
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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.

Sorry, I've had a bad day.

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

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

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 );
   }
Offline 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.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

radar3301 (11 views)
2014-09-21 23:33:17

BurntPizza (29 views)
2014-09-21 02:42:18

BurntPizza (19 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (27 views)
2014-09-20 20:14:06

BurntPizza (30 views)
2014-09-19 03:14:18

Dwinin (47 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!