December 03, 2020, 08:10:03 PM

Author Topic: [bb] 2D Point in Triangle by sswift [ 1+ years ago ]  (Read 683 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] 2D Point in Triangle by sswift [ 1+ years ago ]
« on: June 29, 2017, 12:28:38 AM »
Title : 2D Point in Triangle
Author : sswift
Posted : 1+ years ago

Description : I haven't actually tested this function, as I didn't end up needing it, but I based it off a ray intersect function I wrote in 3D which I know worked, so it should work.

Code :
Code: BlitzBasic
  1. ; -------------------------------------------------------------------------------------------------------------------
  2. ; This function tells you if a point is inside a triangle, in 2D.
  3. ; It also calculates the UV coordinates of said point as part of the intersection test, but does not return them.
  4. ;
  5. ; Pxy is a point.
  6. ;
  7. ; V0xy, V1xy, and V2xy, are the locations of the three vertices of the triangle.
  8. ;
  9. ; For these vertices, V0 is location of UV(0,0), V1 is the location of UV(1, 0), and V2 is the location of UV(0,1)
  10. ;
  11. ; These are important to know if you want to return the exact location in texture space of the collision, but
  12. ; you don't have to worry about them if you only want to find out if a collision occured.
  13. ; -------------------------------------------------------------------------------------------------------------------
  14. Function PointInTri(Px#, Py#, V0x#, V0y#, V1x#, V1y#, V2x#, V2y#)
  15.  
  16.         ; vector(e1,v1,v0)
  17.         E1x# = V1x# - V0x#
  18.         E1y# = V1y# - V0y#
  19.  
  20.         ; vector(e2,v2,v0)
  21.         E2x# = V2x# - V0x#
  22.         E2y# = V2y# - V0y#
  23.  
  24.         ; crossproduct(h,d,e2)
  25.         Hx# = -E2y#
  26.         Hy# =  E2x#
  27.  
  28.         ; a = dotproduct(e1,h)
  29.         A# = (E1x# * Hx#) + (E1y# * Hy#)
  30.        
  31.         F# = 1.0 / A#
  32.        
  33.         ; vector(s,p,v0)
  34.         Sx# = Px# - V0x#
  35.         Sy# = Py# - V0y#
  36.                
  37.         ;u = f * (dotProduct(s,h))
  38.         U# = F# * ((Sx# * Hx#) + (Sy# * Hy#))
  39.        
  40.         ; If the value of the U coordinate is outside the range of values inside the triangle,
  41.         ; then the ray has intersected the plane outside the triangle.
  42.         If (U# < 0) Or (U# > 1)
  43.                 Return False
  44.         EndIf
  45.        
  46.         ; crossProduct(q,s,e1)
  47.         Qz# = (Sx# * E1y#) - (E1x# * Sy#)
  48.  
  49.         ; v = f * dotProduct(d,q)
  50.         V# = F# * Qz#
  51.        
  52.         ; If the value of the V coordinate is outside the range of values inside the triangle,
  53.         ; then the ray has intersected the plane outside the triangle.
  54.         If (V# < 0) Or (V# > 1) Then Return False
  55.  
  56.         ; U + V together cannot exceed 1.0 or the point is not in the triangle.
  57.         ; If you imagine the triangle as half a square this makes sense.  U=1 V=1 would be in the
  58.         ; lower left hand corner which would be in the second triangle making up the square.
  59.         If (U# + V#) > 1 Then Return False
  60.  
  61.         ; The point was in the triangle. Yay!          
  62.         Return True
  63.                
  64.         ; Note that you could also return the U and V coordinates calculated in this function
  65.         ; if you need those values!
  66.  
  67. End Function


Comments :


RemiD(Posted 8 months ago)

 Thanks, this seems to work correctly here.


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal