 # Determine triangle of a quad for a given point

In 2D this task is pretty simple but how can I determine in 3D on which of the two triangles of a given quad-polygon a given point is located?

I face this problem because of the following bigger task:

I have two meshs, which have the same topology but are differently deformed in space. Now I have hundreds of points on one mesh and I want to determine their corresponding location on the other mesh. With

p, n, f = object.closest_point_on_mesh(point)

I can get the polygon f of the point on my first object and use this to determine the vertices on the other object to calculate the corresponding position. This could be easily done with

mathutils.geometry.barycentric_transform

However, therefore, I need to know which three vertices I have to use. For 2D, the corresponding command would be

mathutils.geometry.intersect_point_tri_2d

but how can I determine the triangle on which the point is in 3D?

Thx for any help.

Use .tessfaces (quads+tris) and triangulate if it’s a quad. I’m not sure if blender changed (or will change) default behavior, but it should be as easy as:

``````import bpy

me = bpy.context.object.data
verts = me.vertices
me.calc_tessface()

tf = me.tessfaces # pick any tessface
v = tf.vertices

if len(v) == 3:
tris = (verts[v], verts[v], verts[v]),
else:
tris = (verts[v], verts[v], verts[v]), (verts[v], verts[v], verts[v])

for tri in tris:
# this may either run once or twice, twice if input tessface is a quad
print(tri.co, tri.co, tri.co)
``````

Note that other vertex orders are possible, what you see in viewport may differ from blender’s definition of a triangulated quad (in editmode, it should work like above, but in object mode it is up to opengl driver and may differ again with VBO enabled). A triangulation modifier provides more control, you can also triangulate from script using the beauty-option (more available in 2.70)

thanks for the tips, codemanx. I think, I found the solution for my problem. This is not very efficient, but at least I have solved it for my purposes. I first project the point into a 2d-triangle, check whether the point is in this triangle and then I transform it to its real locatoin

``````
import bpy
import mathutils.geometry as mug

def map3dPointTo3d(o1, o2, point):
''' maps a 3d-point on a given object on another object. Both objects must have the
same topology '''

# get point, normal and face of closest point to particle
p, n, f = o1.closest_point_on_mesh(point)

# get the vertices of the first triangle of the polygon from both objects
A1 = o1.data.vertices[o1.data.polygons[f].vertices].co
B1 = o1.data.vertices[o1.data.polygons[f].vertices].co
C1 = o1.data.vertices[o1.data.polygons[f].vertices].co

# project the point on a 2d-surface and check, whether we are in the right triangle
t1 = mathutils.Vector();
t2 = mathutils.Vector((1.0, 0.0, 0.0))
t3 = mathutils.Vector((0.0, 1.0, 0.0))

p_test = mug.barycentric_transform(p,A1,B1,C1,t1, t2, t3)

# if the point is on the 2d-triangle, proceed with the real barycentric_transform
if mug.intersect_point_tri_2d(p_test.to_2d(), t1.xy, t2.xy, t3.xy) == 1:
A2 = o2.data.vertices[o2.data.polygons[f].vertices].co
B2 = o2.data.vertices[o2.data.polygons[f].vertices].co
C2 = o2.data.vertices[o2.data.polygons[f].vertices].co

# convert 3d-coordinates of the point
p_new = mug.barycentric_transform(p,A1,B1,C1,A2,B2,C2)

else:

# use the other triangle
A1 = o1.data.vertices[o1.data.polygons[f].vertices].co
B1 = o1.data.vertices[o1.data.polygons[f].vertices].co
C1 = o1.data.vertices[o1.data.polygons[f].vertices].co

A2 = o2.data.vertices[o2.data.polygons[f].vertices].co
B2 = o2.data.vertices[o2.data.polygons[f].vertices].co
C2 = o2.data.vertices[o2.data.polygons[f].vertices].co

# convert 3d-coordinates of the point
p_new = mug.barycentric_transform(p,A1,B1,C1,A2,B2,C2)

### TODO ###
### triangle check could be made more efficient ###

return p_new
``````