Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Finding on what side of a polygon a point lays.  (Read 1351 times)
0 Members and 1 Guest are viewing this topic.
Offline DonR

Senior Newbie





« Posted 2011-06-26 18:47:45 »

Hi guys, this problem has been driving me nuts, I hope you can help!

Given a polygon with a surface normal, and a point, I need to find find where the point is in relation to the poly, either inside - the side the normal points to, or outside.  What I have found from searching online, is that the dot product of the point and surface normal should result in 0 at the surface and a positive number inside the surface. So far I have:

1  
float distance = Vector3f.dot(surface.normal, point);


And this almost works - except that the 0 position is not on the surface, but some distance away. Why?
Offline avm1979
« Reply #1 - Posted 2011-06-26 19:28:15 »

My guess is the "point" variable you're passing in is the actual point you're testing. What it needs to be is the direction to that point from some point on the polygon (say, the center - though any point will do - probably easiest to pick one of the vertices).

So instead of "point", you'd need "point - <point on polygon's plane>".

I'd be careful - it sounds like your problem is a bit ill-defined. "Inside a polygon" doesn't make much sense in 3d. What the dot product will tell you is which side of the plane the test point is on. In that case, you're assuming that all the points on the polygon are on the same plane, which isn't necessarily the case unless it's a triangle.

Offline DonR

Senior Newbie





« Reply #2 - Posted 2011-06-26 20:08:06 »

Oh, I see!  Thank you that does help. Do you happen to know how to calculate the direction vector?

[edit] Never mind I've got it, it works great!

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
                       Vector3f direction = Vector3f.sub(surface center, camera position, null);
                           float angle = Vector3f.dot(surface normal, direction);
                                if(angle > 0.0)
            {
               //On the back side of the face
            }
            if(angle <= 0.0)
            {
                                      //On the front side of the face
                                }
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline avm1979
« Reply #3 - Posted 2011-06-26 22:13:43 »

Cool, glad you got it working!

You got two things backwards, btw. Because it's two, they cancel each other out and it works, but still - your direction vector is actually pointing away from the point. The other thing is it ought to be <0 for the back side of the face. A minor, pedantic point, but still.

Also, I wouldn't call the dot product an angle, it's most certainly not Smiley It's the cosine of the angle between the two vectors, but only if the vectors are normalized. (Normalized means length = 1).

Offline Roquen
« Reply #4 - Posted 2011-06-27 11:09:28 »

BTW: An alternate way to think about this problem is to forget about vectors and think of it in terms of the implicit plane equation, so the result is zero if the point is in the plane, positive if on the oriented side (that in which the normal points) and otherwise negative.  If the plane equation is normalized a non-zero results give the orthogonal distance of the point to the plane.  Computationally they are identical to one another.
Offline avm1979
« Reply #5 - Posted 2011-06-27 16:04:44 »

Aha, so:

(normalized surface normal) dot (point - <any point on plane>) = orthogonal distance to plane, from point?

That's handy, and makes sense if you think about it since that's what cosine really is.

In that case a zero result would also give the orthogonal distance though, no? Smiley I think you may have been talking about something else there, then.

Offline Roquen
« Reply #6 - Posted 2011-06-29 14:30:56 »

I didn't word that very well, so yes if the point is on the plane then indeed it's zero distance from the plane.  The vector-centric version (subtracting any point on the plane from the test point) is basically saying: translate the problem to the origin and find the distance to the plane now through the origin.

d = dot(N,P-V)

Where 'V' is any point on the plane.  Translating the implicit plane equation into vectors:

d = dot(N,P) + m

Expanding the vector-centric version yields:

d = dot(N,P) - dot(N,V)

So you get: m = -dot(N,V).

In both cases I think it's more informative to think of the dot as being the parallel projection and in this case distance when normalized.
Offline DonR

Senior Newbie





« Reply #7 - Posted 2011-06-30 15:12:41 »

I am still having a bit of an issue with this.  It worked fine with my original test level (a box) , but I've since tested it with some slightly more complex levels.  First of all some info - My levels are made up of non-convex sectors, which are made up of non-convex surfaces.  I'm looping through each sector, then through each surface of the sector. If it passes the above calculation for every surface of a sector, then I know what sector the camera is in.

The problem is, it starts to return a negative cosine for some surfaces when it shouldn't.  For example, I've made a test level with 3 box sectors.  It works fine for the first 2 sectors, but one surface of the third sector always returns a negative.  Any thoughts?

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  
public void getsector()
   {
      campos = new Vector3f(camera.posx, camera.posy, camera.posz);
      for(int i=0; i<level.getworld_sectors(); i+=1)
      {
            int g = level.sector[i].surfaces[0];
         Inner:
         for(int s=0; s<level.sector[i].surfaces[1]; s+=1)
         {
               direction = Vector3f.sub(campos, level.surface[g+s].surfacep, null);
               float cos = Vector3f.dot(level.surface[g+s].normal, direction);
           
            if(cos < 0.0f)
            {
               break Inner;
            }
            if(cos > 0.0f)
            {
               if(s == level.sector[i].surfaces[1]-1)
               {
                  System.out.println("Sector: "+i);
                  break;
               }
            }        
         }
      }
   }


[edit]

So I figured it out, it turns out my opengl translations were screwed up, so the camera wasn't where I thought.  So the above code works fine!
Pages: [1]
  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.

Longarmx (42 views)
2014-10-17 03:59:02

Norakomi (33 views)
2014-10-16 15:22:06

Norakomi (26 views)
2014-10-16 15:20:20

lcass (30 views)
2014-10-15 16:18:58

TehJavaDev (60 views)
2014-10-14 00:39:48

TehJavaDev (60 views)
2014-10-14 00:35:47

TehJavaDev (50 views)
2014-10-14 00:32:37

BurntPizza (66 views)
2014-10-11 23:24:42

BurntPizza (38 views)
2014-10-11 23:10:45

BurntPizza (80 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!