Transform a mesh of quads and triangles into a mesh composed of only triangles

Question

I do not know how to explain my problem well comprehensively. So I'll show you an example ...

I have this array indicating the vertices indices for each quad or triangle:

>>> faces
array([[0, 1, 2, 3],
       [4, 7, 6, 5],
       [0, 4, 1, 0],
       [1, 5, 6, 2],
       [2, 6, 7, 3],
       [4, 0, 3, 7],
       [1, 4, 5, 0]])

Triangles are the elements that end with 0

I want to make a transformation like this:

>>> faces
array([[0, 1, 2, 3],  #->[[0, 1, 2], [0, 2, 3],
       [4, 7, 6, 5],  #-> [4, 7, 6], [4, 6, 5],
       [0, 4, 1, 0],  #-> [0, 4, 1],
       [1, 5, 6, 2],  #-> [1, 5, 6], [1, 6, 2],
       [2, 6, 7, 3],  #-> [2, 6, 7], [2, 7, 3],
       [4, 0, 3, 7],  #-> [4, 0, 3], [4, 3, 7],
       [1, 4, 5, 0]]) #-> [1, 4, 5]]

So how can I make this transformation efficiently?

I did a function that solves it differently. Place the tirangles obtained by the quads at the end of the array.

def v_raw_to_tris(tessfaces):
    len_tessfaces = len(tessfaces)
    quad_indices = tessfaces[:, 3].nonzero()[0]
    t3 = np.empty(((len_tessfaces + len(quad_indices)), 3), 'i4')

    t3[:len_tessfaces] = tessfaces[:, :3]
    t3[len_tessfaces:] = tessfaces[quad_indices][:, (0, 2, 3)]

    return t3

But I don't want the resulting triangles to be at the end of the array. And yes in front of the original quads

Answer 1

We could replicate each row with the one-off shifting for each row as two rows and mask out the triangular ones at the end. The implementation would look something like this -

def transform1(a):
    idx = np.flatnonzero(a[:,-1] == 0)
    out0 = np.empty((a.shape[0],2,3),dtype=a.dtype)      

    out0[:,0,1:] = a[:,1:-1]
    out0[:,1,1:] = a[:,2:]

    out0[...,0] = a[:,0,None]

    out0.shape = (-1,3)

    mask = np.ones(out0.shape[0],dtype=bool)
    mask[idx*2+1] = 0
    return out0[mask]

Sample run -

In [94]: a
Out[94]: 
array([[0, 1, 2, 3],
       [4, 7, 6, 5],
       [0, 4, 1, 0],
       [1, 5, 6, 2],
       [2, 6, 7, 3],
       [4, 0, 3, 7],
       [1, 4, 5, 0]])

In [95]: transform1(a)
Out[95]: 
array([[0, 1, 2],
       [0, 2, 3],
       [4, 7, 6],
       [4, 6, 5],
       [0, 4, 1],
       [1, 5, 6],
       [1, 6, 2],
       [2, 6, 7],
       [2, 7, 3],
       [4, 0, 3],
       [4, 3, 7],
       [1, 4, 5]])

Possible improvement

We can introduce np.lib.stride_tricks.as_strided to replace the two step assignments for out0[:,0,1:] and out0[:,1,1:] as one and that hopefully should improve it, like so -

from numpy.lib.stride_tricks import as_strided
def strided_axis1(a, L):
    s0,s1 = a.strides
    m,n = a.shape
    nL = n-L+1
    return as_strided(a, (m,nL,L),(s0,s1,s1))

def transform2(a):
    idx = np.flatnonzero(a[:,-1] == 0)
    out0 = np.empty((a.shape[0],2,3),dtype=a.dtype)    
    out0[...,1:] = strided_axis1(a[:,1:], 2)    
    out0[...,0] = a[:,0,None]
    out0.shape = (-1,3)
    mask = np.ones(out0.shape[0],dtype=bool)
    mask[idx*2+1] = 0
    return out0[mask]