Is there any way to speed up the function `changem`?

I am doing some substitutions of the index of triangle mesh. After removing or selecting some points on the mesh, I need to "retrench" the connectivitylist. I always using changem to achieve this. Like below,

function TR1 = simpleTR(TR)
node_idx = unique(TR.ConnectivityList); 
node1 = TR.Points(node_idx,:);
node_idx1 = 1:size(node1,1);
face1 = changem(TR.ConnectivityList,node_idx1',node_idx);
TR1 = triangulation(face1,node1);
end

I found the speed of this is slow when the input TR is big. In profiling, the code in changem below takes the most of time.

B(A == oldval(k)) = newval(k);

Is there any way to accelerate this?

----------------------edit for @Cam Salzberger comment---------------------------------------------

I would like to clarify my problem in two aspects. One is the bigger picture, which is what I would like to do with the codes. The other is the problem of changem.

• 1. The goal of my codes is to make a new triangle mesh. The new mesh has fewer vertices(TR.Points) than the original one, after I deleted some vertex of it. The index of the faces (TR.ConnectivityList) should be "retrench", that is, the range of the faces (TR.ConnectivityList) will be smaller. See the example below, which is from matlab page,triangulation

% the original mesh
P = [ 2.5    8.0
      6.5    8.0
      2.5    5.0
      6.5    5.0
      1.0    6.5
      8.0    6.5];
T = [5  3  1;
     3  2  1;
     3  4  2;
     4  6  2];
 TR = triangulation(T,P)
 triplot(TR)

Now I delete the 5th vertex. The new mesh should be,

T_new = [   3  2  1;
            3  4  2;
            4  6  2];
 TR1a = triangulation(T_new,P);% some vertices is not referenced  
 TR1b = simpleTR(TR1a); % the content is above

%>>  TR1b.Points
ans =
          2.5            8
          6.5            8
          2.5            5
          6.5            5
            8          6.5
%>> TR1b.ConnectivityList
ans =
     3     2     1
     3     4     2
     4     5     2

In the process, I need to replace "6" with "5" with changem. In practise, I have to changem many number for a large mesh.

• 2. For the problem of changem. In this function, I found it did a loop for "find" and "change value" combination.

B(A == oldval(k)) = newval(k);

I believe it has some chance to improve. Because it seems in every loop, it traverses through all of the elements in the matrix(TR.ConnectivityList). I think this way may be imperfect. It may use some hashtable-like thing to do it., which could be done in one loop.

All of this is my guess. Thank you for any suggestions.

[Cam Salzberger]

It may help if you rephrase what you are trying to do in a bigger picture. There's not really any way to specifically speed up logical indexing and replacement (except possibly avoiding using changem and using arrayfun rather than a for loop). However, that's probably not where the performance increase could be done. If you frame what you want this function to do in a larger picture (what's an example input, and what would be the output from that), people may be able to make advice to avoid this step entirely.

[wei zhang]

@Cam Salzberger. I have edited as your comment. Could you give me more suggestions? Thank you.

Answer 1

[Bruno Luong]

Sorry; I don't speed changem up, I just remove it entirely.

function TR1 = simpleTR(TR)
F = TR.ConnectivityList;
n = size(F,2);
[subsetX,~,F] = unique(F);
X = TR.Points(subsetX,:);
F = reshape(F,[],n);
TR1 = triangulation(F,X);
end

[wei zhang]

Very effectively! The changem is too slow since it use "for loop" of "find".

[Strider]

Bruno's answer is great. Here is a more general alternative to changem that helped me understand it since my problem was not direclty mappable to triangulaiton.

Answer 2

[Moses Huang]

Hi Wei,

From your example, I can not tell whether you are deleting more than one vertex at once, so I will assume that you are deleting the vertices one at a time.

While running your function "simpleTR" with your example, I noticed that node_idx and node_idx1 are very similar in value. In fact, they only differ in one vertex. If the input to simpleTR is TR1a, then node_idx and node_idx1 are as follows:

node_idx  = [1 2 3 4 5];
node_idx1' = [1 2 3 4 6];

From the MATLAB documentation, it mentions that the "changem" command exchanges all the values of OLDVAL with the corresponding value in NEWVAL. I think your performance bottleneck comes from the fact that you are passing in vectors for both OLDVAL and NEWVAL that only differ by one value. I will substitute the value of node_idx and node_idx1' from above into the command so that you can see.

face1 = changem(TR.ConnectivityList,
                [1 2 3 4 6],
                [1 2 3 4 5]);

With the following input, the changem function will replace node 1 with 1, node 2 with 2, ..., until it finishes replacing node 6 with 5. This is a lot of unnecessary work if only one vertex is being deleted at a time. You can modify the simpleTR function as follows to avoid this:

function TR1 = simpleTR(TR)
    node_idx = unique(TR.ConnectivityList);
    node1 = TR.Points(node_idx,:);
    node_idx1 = 1:size(node1,1);

    % This produces a vector of 0's and 1's where 1 means that the node number has changed
    compareResult = node_idx ~= node_idx1';

    % We only replace the node number for the node that changed to eliminate unnecessary work
    face1 = changem(TR.ConnectivityList, node_idx1(compareResult), node_idx(compareResult));
    TR1 = triangulation(face1,node1);
end