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

1 次查看（过去 30 天）
wei zhang
wei zhang 2020-7-31
编辑： Strider 2024-6-22
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.
  2 个评论
Cam Salzberger
Cam Salzberger 2020-7-31
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
wei zhang 2020-8-1
@Cam Salzberger. I have edited as your comment. Could you give me more suggestions? Thank you.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2020-11-11
编辑：Bruno Luong 2020-11-11
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
  2 个评论
wei zhang
wei zhang 2020-11-16
Very effectively! The changem is too slow since it use "for loop" of "find".
Strider
Strider 2024-6-22
编辑：Strider 2024-6-22
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.

请先登录，再进行评论。

更多回答（1 个）

Moses Huang
Moses Huang 2020-11-11
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

类别

在 Help Center 和 File Exchange 中查找有关 Graphics Performance 的更多信息

标签

产品


版本

R2019a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by