point in 3d triangle

Blitz3D Forums/Blitz3D Programming/point in 3d triangle

Warner (Posted 2008) [#1]

Does anybody know how to determine if a 3d point is inside a 3d triangle ?

Ross C (Posted 2008) [#2]

Surely it would be a 2d point running across the 3d triangle? Or else, it would be verrrrrrrry difficult to get this answer, due to floating point in accuracies in 3d space. If you can imagine a triangle in 3d, and you wanted to click on the triangle and place a dot where the mouse hits (and only it it hits the triangle) Is this the kind of thing your after? If so, fredborg's picked U() and PickedV() commands are what you need. There might be something more suitable though. I'll check.

amitjf (Posted 2008) [#3]

look, in 2d what you need to do is that if you have function: PointInside(x,y,x1,y1,x2,y2,x3,y3) then you need to calculate the area of the triangles: (x,y)(x1,y1)(x2,y2) , (x,y)(x2,y2)(x3,y3) , (x,y)(x1,y1)(x3,y3) and if it equals to the area of (x1,y1)(x2,y2)(x3,y3) you can be sure it is inside the triangle. I'm tired and going to sleep, so I would look tomorrow if no one will answer you how to implement it in 3d.

Ross C (Posted 2008) [#4]

Should be pretty much the same man. You'll first need to convert the point into a 2d point relative to the triangle.

Warner (Posted 2008) [#5]

Thanks very much for the idea! I've given a go at implementing it, using two functions from the archive by RaGR: Graphics3D 800, 600, 0, 2 SetBuffer BackBuffer() ;create plane plane = CreatePlane() TurnEntity plane, -90, 0, 0 EntityPickMode plane, 2 EntityAlpha plane, 0.2 ;create camera cam = CreateCamera() MoveEntity cam, 0, 0, -15 ;create red dot sp = CreateSphere() ScaleEntity sp, 0.1, 0.1, 0.1 EntityColor sp, 255, 0, 0 EntityFX sp, 1 ;create mesh with 1 triangle mesh = CreateMesh() surf = CreateSurface(mesh) ;generate triangle For i = 2 To 0 Step -1 h = i * 120 x# = Cos(h)*(5+i) y# = Sin(h)*(5+i) TFormPoint x, 0, y, plane, 0 AddVertex surf, TFormedX(), TFormedY(), TFormedZ() Next AddTriangle surf, 0, 1, 2 ;read triangle coords x0# = VertexX(surf, 0) y0# = VertexY(surf, 0) z0# = VertexZ(surf, 0) x1# = VertexX(surf, 1) y1# = VertexY(surf, 1) z1# = VertexZ(surf, 1) x2# = VertexX(surf, 2) y2# = VertexY(surf, 2) z2# = VertexZ(surf, 2) ;main loop Repeat ;keys If KeyHit(200) Then TranslateEntity plane, 0, 0, -1 If KeyHit(208) Then TranslateEntity plane, 0, 0, 1 If KeyHit(57) Then PositionEntity plane, 0, 0, 0 RenderWorld() Text 0, 0, "use cursor up/dn and space to move plane along z axis" Text 0, 20, "triangle will turn red if picked dot is inside triangle" ;draw outlines CameraProject cam, x0, y0, z0 gx0# = ProjectedX() gy0# = ProjectedY() CameraProject cam, x1, y1, z1 gx1# = ProjectedX() gy1# = ProjectedY() CameraProject cam, x2, y2, z2 gx2# = ProjectedX() gy2# = ProjectedY() Line gx0,gy0,gx1,gy1 Line gx1,gy1,gx2,gy2 Line gx2,gy2,gx0,gy0 ;pick 3d mouse position CameraPick cam, MouseX(), MouseY() PositionEntity sp, PickedX(), PickedY(), PickedZ() ;determine if point is in triangle test = pointintriangle(PickedX(),PickedY(),PickedZ(), x0,y0,z0,x1,y1,z1,x2,y2,z2) If test Then EntityColor mesh,255,0,0 Else EntityColor mesh,0,255,0 End If Flip Until KeyHit(1) End Function PointInTriangle(Px#, Py#, Pz#, x0#,y0#,z0#, x1#,y1#,z1#, x2#,y2#,z2#) ;determine min/max x/y/z values nx1# = findmin(x0,x1,x2) nx2# = findmax(x0,x1,x2) ny1# = findmin(y0,y1,y2) ny2# = findmax(y0,y1,y2) nz1# = findmin(z0,z1,z2) nz2# = findmax(z0,z1,z2) ;with/height/depth nxx# = nx2 - nx1 nyy# = ny2 - ny1 nzz# = nz2 - nz1 ;determine which angle to drop ;;;If (nzz < nxx) And (nzz < nyy) Then axis = 1 ;xy ->drop z If (nyy < nzz) And (nyy < nxx) Then axis = 2 ;xz ->drop y If (nxx < nyy) And (nxx < nzz) Then axis = 3 ;yz ->drop x Select axis Case 1 test = PointInTriangle2D(px,py,x0,y0,x1,y1,x2,y2) ;inside 2d tri tstz# = PointHeightOnTri(px,py,x0,z0,y0,x1,z1,y1,x2,z2,y2) ;z value of triangle tstc# = pz# ;z value of point Case 2 test = PointInTriangle2D(px,pz,x0,z0,x1,z1,x2,z2) ;inside 2d tri tstz# = PointHeightOnTri(px,pz,x0,y0,z0,x1,y1,z1,x2,y2,z2) ;z value of triangle tstc# = py# ;z value of point Case 3 test = PointInTriangle2D(py,pz,y0,z0,y1,z1,y2,z2) ;inside 2d tri tstz# = PointHeightOnTri(py,pz,y0,x0,z0,y1,x1,z1,y2,x2,z2) ;z value of triangle tstc# = px# ;z value of point End Select ;calculate difference between z triangle and z point dif# = Abs(tstz#-tstc#) ;if below epsilon If dif# < 0.001 Then Return test ;else no intersection Return False End Function ;find min. val of abc Function findmin#(a#,b#,c#) If b < a Then a = b If c < a Then a = c Return a End Function ;find max. val of abc Function findmax#(a#,b#,c#) If b > a Then a = b If c > a Then a = c Return a End Function ; by RaGR (Ralph G. Roeske). Function PointHeightOnTri#(px#,pz#, x1#,y1#,z1#,x2#,y2#,z2#,x3#,y3#,z3#) e#=(x2-x1)*(z3-z1)-(x3-x1)*(z2-z1) e=1.0/e e1#=e*((x2-px)*(z3-pz)-(x3-px)*(z2-pz)) e2#=e*((x3-px)*(z1-pz)-(x1-px)*(z3-pz)) e3#=e*((x1-px)*(z2-pz)-(x2-px)*(z1-pz)) Return e1*y1+e2*y2+e3*y3 End Function ; by RaGR (Ralph G. Roeske). Function PointInTriangle2D(px#,pz#, x1#,z1#,x2#,z2#,x3#,z3#) Local bc#,ca#,ab#,ap#,bp#,cp#,abc# bc# = x2*z3 - z2*x3 ca# = x3*z1 - z3*x1 ab# = x1*z2 - z1*x2 ap# = x1*pz - z1*px bp# = x2*pz - z2*px cp# = x3*pz - z3*px abc# = Sgn(bc + ca + ab) If (abc*(bc-bp+cp)=>0) And (abc*(ca-cp+ap)=>0) And (abc*(ab-ap+bp)=>0) Return True End Function *edit* Well .. it is usable, but it seems somewhat slow. If someone has a faster and/or better method for this, I would still like to know.