Checking for a point inside a region of a spherical surface

This is a discussion on Checking for a point inside a region of a spherical surface within the Game Programming forums, part of the General Programming Boards category; Hi everybody, I am working on a 3D Morphing algorithm. I have a point X on lying on a unit ...

  1. #1
    Registered User Zeeshan's Avatar
    Join Date
    Oct 2001
    Location
    Munich, Germany
    Posts
    224

    Checking for a point inside a region of a spherical surface

    Hi everybody,

    I am working on a 3D Morphing algorithm.

    I have a point X on lying on a unit sphere in the spherical coordinate system. I have three other points A,B, and C which are also on the unit sphere. The sphere is centered at the origin.

    I need to find out whether X lies on the spherical 'triangular' area enclosed by A,B, and C or not.

    Can any one tell me how to do this?

    Thanks a lot in advance.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm thinking you could maybe make barycentric coordinates work for you, since the surface of a sphere is a 2D surface -- not exactly a plane, but you should be able to deal with just longitude and latitude. There's a system to solve, and if any of your coordinates are less than zero or bigger than one, you're outside the triangle. My handout says that the system is equation 5.58 in Lengyel's book, but I don't know if I have a copy here.

    EDIT: If p0, p1, and p2 are your triangle, and p is your other point, then: define q1=p1-p0 and q2=p2-p0 and r=p-p0. Solve the system
    (q1*q1)w1 + (q1*q2)w2 = (q1*r)
    (q2*q1)w1 + (q2*q2)w2 = (q2*r)
    for w1 and w2 (with * meaning dot product), and then w0 = 1 - w1 - w2. The w's are your barycentric coordinates.
    Last edited by tabstop; 06-21-2008 at 02:47 PM.

  3. #3
    Registered User Zeeshan's Avatar
    Join Date
    Oct 2001
    Location
    Munich, Germany
    Posts
    224
    Thanks a lot for the reply.

    So, you are saying that I should represent the points P1, P2, and P3 in Latitude and Longitude form...and this system will still work?

    How will I take the dot product in that case?

    Again, thanks a whole lot.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm thinking that latitude and longitude should work as a map from surface-of-sphere to Cartesian flat-piece-of-paper (just be sure that your triangle doesn't cross the "international date line" at the edges). It's not going to keep area or distance, obviously, but it will keep inside/outside.

    Dot products are dot products (x*x+y*y).

  5. #5
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,579
    I'm always against translating coordinate systems in order to solve a problem
    This is mainly because, if a coordinate system exists it will be able to handle any problem that results from the planes it handles.

    But, I may be wrong on those occasions where a translation results in faster performance. Testing would dictate. However, for a first approach I feel the solution should lie within the adopted coordinate system and only then, if performance is not acceptable - and formulae simplification proved still inadequate - should we look into another system.

    I work mostly in 2D, I have very little knowledge of 3D formulas and am even nowhere an expert in 2D spaces. However, I feel this will help.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. For the numerical recipes in C types!
    By Smattacus in forum C Programming
    Replies: 5
    Last Post: 10-28-2008, 08:57 PM
  2. Point in polygon test - spherical coords
    By bhdz in forum C Programming
    Replies: 1
    Last Post: 11-07-2007, 01:25 PM
  3. Replies: 6
    Last Post: 06-02-2006, 03:30 AM
  4. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM
  5. DJGPP error checking (inside RHIDE)
    By VirtualAce in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 11-15-2001, 07:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21