# Vertex interpolation using Barycentric Coordinates and Bilinear Filtering

About a week ago I had to get uv coordinates accurately transferred on to a new set of points.
I knew these points lay on the existing surface, and that a nearest neighbour solution would cause problems, because a point can be closer to a different vert than the primitive it sits on. I also knew I had to be able to correctly interpolate quads and triangles.

After consulting the web I found out that you could use the triangle’s Barycentric coordinates and the quadratic’s filtered uv position to correctly interpolate the vertices that define a primative (or face). Both methods return a set of uv coordinates that help define the point’s relative position on that sampled face.

Remember that with this particular uv set I mean the uv set relative to a certain primitive or face. Not the uv set that defines a vert’s position in 2d space (relative to other vertices).

In the case of a triangle (defined by: A,B,C), the uv set specifies the weight of every vert, say: (U: 0.2, V: 0.5, W: 0.3). Note that for simplicity the last value is often left out because if the point lies within the triangle, the seperate weights always add up to one. Coming back on the previous weights, we can write the third weight (W) as: 1-(0.2+0.5).

You could also say that the uv coordinates describe the distance you have to walks over the edge of the triangle starting from vert A to vert B and C. If the value of u or v (where u = location on edge: A-B, and v = location on edge: C-A) ends up to be higher or lower than one, the point lies outside of the triangle.

The point’s position (P) can now easily be calculated: P = (B*U) + (C*V) + (A*W)

For a quadratic primitive the uv coordinates don’t describe the vert weights directly. The set only describes the relative position of the point based on the primitive’s local uv space. But by using a simple bilinear interpolation we can use these coordinates to calculate that point’s position (or interpolated uv values). We start by defining two new points in the u axis, and use these points to find the final weight in the v axis.

Say we have a square defined by: A, B, C and D and a uv set that defines a point in this square with the coordinates: (U)0,2 and (V)0,5. It’s a right sided primitive. We can figure out the two new points (P1 and P2) in the u direction by using the primtive’s edges: P1 = (B-A)*U, P2= (D-C)*U. But this only get’s us half way. We have the interpolated u value as a set of 2 points, but we can use these points as an edge to get the final position (PF) (or whatever data you see fit): PF = (P2-P1)*V. And that’s it… But this doesn’t explain how to get those uv coordinates. Houdini has some build in functions for this that can be accessed with VEX, C++ and Python. For this example I will stick with Python. But you could also write your own. A good example on finding the Barycentric coordinates of a triangle can be found here. Finding the coordinates for a quadratic primitive is more diffifcult and depends on the way the primitive is described. Doing a simple google search on: ‘parametric surface’ will get you half way. This wiki article is also a good starting point.

Now for some code. I wrote a UV Interpolator in Python that corrrectly interpolates the uv attribute from a set of vertices. I already know the primitve to sample, so I don’t perform any unnecessary ray casts. The operator works with both quads and triangles. The function that is used to get the uv coordinates local to the primitive is: hou.Prim.nearestToPosition(Point). In vex these coordinates are generated when doing an intersect operation.

"""
This operator interpolates the uv coordinates from a primitive, indexed from the second input.
The points defined in the first input should have an integer attribute pointing to the primitive to sample from.
The primitive should have uv coordinates defined on vertices or points.
Only works with quadractic or triangle primitives!
For Quadratic primitives: bilinear interpolation is used to find the new uv coordinates.
For Triangle primitives: the Barycentric coordinates are used to find the new uv coordinates
For a sample reference: http://www.gamerendering.com/2008/10/05/bilinear-interpolation/
"""

# This code is called when instances of this SOP cook.
node = hou.pwd()
geo_one = node.geometry()
geo_two = node.inputs().geometry()

# Sample the parameters
uv_location = node.parm("uv_location").evalAsString()
prim_index_name = node.parm("prim_index_name").eval()
max_distance = node.parm("max_distance").eval()
prim_type = node.parm("prim_type").evalAsString()
group_name = "faulty_samples"

#Attributes-------------------------------------------------------------------------------

# First sample the uv attribute from the second input
uv_attrib = None
if uv_location == "points":
uv_attrib = geo_two.findPointAttrib("uv")
else:
uv_attrib = geo_two.findVertexAttrib("uv")
use_points = (uv_location == "points")
use_triangles = prim_type == "triangle"

# Make sure the attribute was found
if uv_attrib is None:
raise hou.NodeError("Can't find uv attribute")

# Now sample the primitive index attribute from the first input
prim_index_attrib = geo_one.findPointAttrib(prim_index_name)
if prim_index_attrib is None or prim_index_attrib.dataType() != hou.attribData.Int:
raise hou.NodeError("Can't sample primitive index attribute of type Int: %s" % prim_index_name)

# Add a new point uv attrib if necesarry

# Create a faulty point group
faulty_point_group = geo_one.findPointGroup(group_name)
if faulty_point_group is None:
faulty_point_group = geo_one.createPointGroup(group_name)

#Methods--------------------------------------------------------------------------------

"""
From the incoming primitive we first create two new interpolated points on the u axis
From these points we create the final uv coordinate based on the v axis, using bilinear interpolation
"""

verts = inPrimitive.vertices()
vertuvs = []

if len(verts) != 4:
raise hou.NodeError("Primitive: %d does not have excactly 4 verts!" % inPrimitive.number())

# get the uv values from our verts or points
for vert in verts:
if not use_points:
vertuvs.append(vert.attribValue(uv_attrib))
else:
vertuvs.append(vert.point().attribValue(uv_attrib))

# get our final weights in u and v
rv = 1-inCoordinates
ru = 1-inCoordinates
pv = inCoordinates
pu = inCoordinates

# calculate two new uv samples in the u direction
bottom_uv = ((vertuvs*pu + vertuvs*ru), (vertuvs*pu + vertuvs*ru))
top_uv = ((vertuvs*pu + vertuvs*ru), (vertuvs*pu + vertuvs*ru))

# interpolate over v to get our final value
final_uv = ((top_uv*pv + bottom_uv*rv), top_uv*pv + bottom_uv*rv, 0.0)

return final_uv

def getUVCoordinatesFromTriangle(inCoordinates, inPrimitive):
"""
Compute the new uv coordinates based on the incoming Barycentric coordinates.
The first coordinate maps to the 3rd vert, the second coordinate to the 2nd vert.
The weight of the first vert is computed by complementing the added two weights.
"""

verts = inPrimitive.vertices()
vertuvs = []

if len(verts) != 3:
raise hou.NodeError("Primitive: %d does not have excactly 3 verts!" % inPrimitive.number())

# get the weights
vert_weights = (1-(inCoordinates+inCoordinates), inCoordinates, inCoordinates)

# get the uv values from our verts or points
for vert in verts:
if not use_points:
vertuvs.append(vert.attribValue(uv_attrib))
else:
vertuvs.append(vert.point().attribValue(uv_attrib))

# compute the new uv values
new_u = (vertuvs*vert_weights) + (vertuvs*vert_weights) + (vertuvs*vert_weights)
new_v = (vertuvs*vert_weights) + (vertuvs*vert_weights) + (vertuvs*vert_weights)

return (new_u,new_v, 0.0)

#Compute---------------------------------------------------------------------------------

"""
Iterate over every point that we need to interpolate the coordinates for.
"""

points = geo_one.points()
prims = geo_two.prims()

warning_string = ""
warning_occured = False

for point in points:
# Get the primitive
sample_prim = prims[point.attribValue(prim_index_attrib)]

# Make sure the primitive is a poly
if sample_prim.type() != hou.primType.Polygon:
raise hou.NodeError("Primitive: %d is not of type Polygon" % sample_prim.number())

# Get the parametric uv location of the point on the primitive
local_sample_data = sample_prim.nearestToPosition(point.position())
para_uv_coor = (local_sample_data, local_sample_data)

distance = local_sample_data

# Add an entry if it's too far away from the primitive
if distance &gt; max_distance:
warning_string += "Point: %d appears to be %f units away from indexed primitive: %d\n" % (point.number(), distance, sample_prim.number())