6
$\begingroup$

bmesh vert order

I am working on a bmesh script that procedurally creates a mesh.

I'm having a problem determining how to order the vertices for the generated n-gon face.

I know the position of each vertex - but need to order them somehow so the face doesn't fold over itself.

Normally with blender UI you can select several vertices and use the fill feature to automatically create a face and fill the hole. Somehow this is automatically finding an order.

Should I be sorting the vertex positions by the position in space? I thought about sorting by X then Y or something like that but this won't work in all use cases in any dimension?

So the question is :

Given a list of vertices that are all aligned to a single arbitrary plane - how to determine which vertex order is best to generate a non-self-folding face?

$\endgroup$
4
  • $\begingroup$ Try counterclockwise order. 870 871 872 874 873 $\endgroup$
    – scurest
    Jul 19 '21 at 22:03
  • $\begingroup$ You can see which numbers are counterclockwise by looking at the picture - how to determine order without looking at picture - i.e. by evaluating individual vertex positions. $\endgroup$
    – stackzz
    Jul 20 '21 at 0:21
  • 1
    $\begingroup$ yes counterclockwise order works - but the problem is how to derive "clockwise" order from a list of verts (no picture) $\endgroup$
    – stackzz
    Jul 20 '21 at 0:22
  • $\begingroup$ @Gorgious - thanks for helping to format the question $\endgroup$
    – stackzz
    Jul 20 '21 at 10:38
9
$\begingroup$

The Blender function that makes a poly from a point cloud is BM_vert_sort_radial_plane.

/**
 * Makes an NGon from an un-ordered set of verts
 *
 * assumes...
 * - that verts are only once in the list.
 * - that the verts have roughly planer bounds
 * - that the verts are roughly circular
 * there can be concave areas but overlapping folds from the center point will fail.
 *
 * a brief explanation of the method used
 * - find the center point
 * - find the normal of the vcloud
 * - order the verts around the face based on their angle to the normal vector at the center point.
 *
 * \note Since this is a vcloud there is no direction.
 */

(If you want to read it, here's some quick links to BM_verts_calc_normal_from_cloud_ex and angle_signed_on_axis_v3v3v3_v3 too).

So for verts in a plane, it looks like the idea is to simply sweep out a circle around the centroid, taking verts in the order you hit them.

Assuming the verts are roughly a circle (no verts at the centroid, no edges pointing radially away from the centroid) you can do this with something like the function below. (These assumptions are pretty easy to lift if you need to, they just simplify the code a bit.)

import math
import mathutils
from mathutils import Vector

def sort_radial_sweep(vs, indices):
    """
    Given a list of vertex positions (vs) and indices
    for verts making up a circular-ish planar polygon,
    returns the vertex indices in order around that poly.
    """
    assert len(vs) >= 3
    
    # Centroid of verts
    cent = Vector()
    for v in vs:
        cent += (1/len(vs)) * v

    # Normalized vector from centroid to first vertex
    # ASSUMES: vs[0] is not located at the centroid
    r0 = (vs[0] - cent).normalized()

    # Normal to plane of poly
    # ASSUMES: cent, vs[0], and vs[1] are not colinear
    nor = (vs[1] - cent).cross(r0).normalized()

    # Pairs of (vertex index, angle to centroid)
    vpairs = []
    for vi, vpos in zip(indices, vs):
        r1 = (vpos - cent).normalized()
        dot = r1.dot(r0)
        angle = math.acos(max(min(dot, 1), -1))
        angle *= 1 if nor.dot(r1.cross(r0)) >= 0 else -1    
        vpairs.append((vi, angle))
    
    # Sort by angle and return indices
    vpairs.sort(key=lambda v: v[1])
    return [vi for vi, angle in vpairs]

Example:

vs = [
    Vector((   0,    1, 0)),
    Vector((  -1,    0, 0)),
    Vector((-0.5, -0.5, 0)),
    Vector((   1,    0, 0)),
    Vector(( 0.5, -0.5, 0))
]
indices = [
    870,
    871,
    872,
    873,
    874,
]
print(sort_radial_sweep(vs, indices))
# => [874, 873, 870, 871, 872]

Note that you might get CW order instead of CCW. I think you get CW order if the first two verts in the input list are in CW order (and similarly for CCW). Maybe you have another way to pick the facing direction though.

$\endgroup$
5
  • $\begingroup$ Wow that's a super good answer... It looks like it answered the question perfectly. I haven't tried it yet but will report how it works... sort_radial_sweep looks like a super great function!!! $\endgroup$
    – stackzz
    Jul 20 '21 at 10:32
  • $\begingroup$ It works perfectly with 5 vectors. If you comment out one of the input Vectors (only supply 4 vertices) the angle = math.acos(r1.dot(r0)) line generates a ValueError: math domain error. $\endgroup$
    – stackzz
    Jul 20 '21 at 21:46
  • $\begingroup$ I clamped the arg to acos for you. $\endgroup$
    – scurest
    Jul 20 '21 at 22:33
  • $\begingroup$ Clamping arg to acos made a huge difference - thanks for that. Do you think there is any precision or errors introduced by clamping it? It seems to be working 95% of the time. There are a few cases where it is still folding over - will do some more testing. $\endgroup$
    – stackzz
    Jul 21 '21 at 1:55
  • $\begingroup$ Clamping the dot product seems okay to me, but there might be numeric issues with the rest of it. $\endgroup$
    – scurest
    Jul 21 '21 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.