My maths ain't good!

[JBR]

Hi, essentially trying to find if a point is in a convex polygon.

I thought I would, for each triangle, do a cross product and then a dot product.

I'm thinking < 0 means either inside or outside.

Am I on the wrong path with this idea?

Code: [Select]


Inside% = 0

For Local tri% = 0 To CountTriangles(Surf)-1

Local v_x_A# = VertexX( Surf,TriangleVertex( Surf, tri, 0 ) )
Local v_y_A# = VertexY( Surf,TriangleVertex( Surf, tri, 0 ) )
Local v_z_A# = VertexZ( Surf,TriangleVertex( Surf, tri, 0 ) )

Local v_x_B# = VertexX( Surf,TriangleVertex( Surf, tri, 1 ) )
Local v_y_B# = VertexY( Surf,TriangleVertex( Surf, tri, 1 ) )
Local v_z_B# = VertexZ( Surf,TriangleVertex( Surf, tri, 1 ) )

Local v_x_C# = VertexX( Surf,TriangleVertex( Surf, tri, 2 ) )
Local v_y_C# = VertexY( Surf,TriangleVertex( Surf, tri, 2 ) )
Local v_z_C# = VertexZ( Surf,TriangleVertex( Surf, tri, 2 ) )

'now get the cross product
'-------------------------
Local A_x# = v_x_B - v_x_A ' B-A, i.e AB
Local A_y# = v_y_B - v_y_A
Local A_z# = v_z_B - v_z_A

Local B_x# = v_x_C - v_x_A ' C-A, i.e. AC
Local B_y# = v_y_C - v_y_A
Local B_z# = v_z_C - v_z_A


Local Cross_X# = (A_y*B_z - A_z*B_y)
Local Cross_Y# = (A_z*B_x - A_x*B_z)
Local Cross_Z# = (A_x*B_y - A_y*B_x)

Local C_x# = Camera_X - v_x_A ' Camera - A i.e. ACamera
Local C_y# = Camera_Y - v_y_A
Local C_z# = Camera_Z - v_z_A

Local dot# = (Cross_X * C_x) + (Cross_Y * C_y) + (Cross_Z * C_z)

If dot > 0 Then Inside :+ 1

Next



[Matty]

A quick guess of an idea.

Convert the vectors from each arm of triangle AB, AC and BC into unit vectors.

Find the dot product of each combination of these unit vectors which will give you the cosine of the angle between them.  A value between -1 and +1 for each.

If point D is inside the triangle then the angle between AD, CD and BD will be narrower for all the combinations,  hence closer to a value of +1.

So three are 6 dot products to calculate,  6 unit vectors to calculate and then a comparison that says if all 3 angles between point D and the other vectors is less than each angle between the arms of the triangle then youre inside it.

That's a quick guess of the top of my head.

You can write a 2d program to calculate where you draw random triangles and then click somewhere on the screen and flash up inside or outside based on this, a quick visual inspection will tell you if you've got it right.

[Matty]

Or put another way, if the dot product of the unit vectors from arm to point is less than the dot product of that arm to its other arm for any of the sides, then you know it is outside.

As shown on my diagram.

[JBR]

Hi Matty,

Not being funny here but is your solution not for 2D?

I was trying a 3d convex polygon.

Jim.

[Matty]

Sorry yes I realised that myself after I posted it.....

[STEVIE G]

I don't think the cross / dot product solution will work here.  SAT will work with the added bonus of getting  nearest edge and penetration  depth.

[ImJustAnotherCoder]

The dot-product can be used to identify the distance to a plane, ie a polygon, triangle, and has the benefit that the sign of the of the result of the dot product can indicate which side of the polygon the point is.

The cross-product can be used to find a vector that is perpendicular to 2 other vectors of which represent a plane. In other words the cross-product can be used to find a vector that can represent the direction that a plane is facing - either a vector that represents the forward facing or backward facing direction. The direction can be determined by the winding order used in the plane part of the equation.

The easiest way to determine if a point is within a polygon is to adjust all vertex positions by -point so that the point is at the origin. Then calculate all the of the angle of vertices, add them add together. If the result is 360 (or 2*PI) then the point is inside the polygon, anything else then it is outside of the polygon. This will also work for n-sided polygons, with >2 vertices, and not just triangles.