Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Looking for an improved method for assigning triangular mesh face indices to multiple bins

Subject: Looking for an improved method for assigning triangular mesh face indices to multiple bins

From: Thomas

Date: 22 Feb, 2014 15:16:12

Message: 1 of 5

Hi Matlab users
I’m currently trying to assign triangular mesh face indexes to multiple bins based upon an Octree segmentation of its associated vertices. I have come up with a vectorized solution using ismember and repmat but the function is running unacceptably slow (around 111 seconds for assigning a 70000 face / 35000 vertex mesh to 500 bins: it would not be unusual for the program to deal with 150000+face meshes / 1000 bins).
An example of the I/O and the function can be seen below:

% points_del – nx3 xyz vertices
points_del =
[6.59964000000000,-2.14960000000000,3.33790000000000;6.58379000000000,-1.71894000000000,3.54157000000000;6.59964000000000,-1.71894000000000,3.53287000000000;6.16898000000000,-1.71894000000000,3.79313000000000;6.59964000000000,-1.68333000000000,3.54157000000000;7.21587000000000,-2.14960000000000,3.11091000000000;7.46096000000000,-2.14960000000000,2.96904000000000;7.46096000000000,-1.85466000000000,3.11091000000000;7.57561000000000,-1.71894000000000,3.11091000000000;7.03030000000000,-1.71894000000000,3.33767000000000;7.46096000000000,-1.71894000000000,3.15422000000000;6.24547000000000,-2.14960000000000,3.54157000000000;5.95366000000000,-2.20361000000000,3.75690000000000;5.98769000000000,-2.14960000000000,3.75690000000000;6.16898000000000,-2.14960000000000,3.60510000000000;5.95366000000000,-2.14960000000000,3.78286000000000;7.24563000000000,-2.14960000000000,3.09743000000000;7.0303000000000
0,-2.14960000000000,3.17660000000000;7.61842000000000,-2.14960000000000,2.89558000000000;7.67629000000000,-2.14960000000000,2.87493000000000];

% pointID – vertex indices
pointID = [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20];

% faces - triangle vertices
faces=[2,3,1;2,1,12;13,14,15;13,16,14;4,15,14;4,14,16;12,15,4;12,4,2;5,3,2;5,2,4;8,7,17;8,17,6;10,18,1;10,1,3;6,18,10;8,6,10;10,11,8;9,20,19;8,9,19;19,7,8;8,11,9;10,3,5];

% bins – n bins
Bins = 3;
% binIDs – vertex to bin indices
binIDs = [1;1;1;1;1;1;2;2;2;2;2;2;2;3;3;3;3;3;3;3];

% assign triangle indices to bins defined by binIDs
% create bin indices of the length of the face list
Pids = cell(bins,1);
for i = 1:bins
    Pids{i} = repmat(i,size(faces,1),1);
end
Pids = cell2mat(Pids);

% create a separate lists of each triangle vertex matched to each bin
P0 = horzcat(Pids,repmat(faces(:,1),bins,1));
P1 = horzcat(Pids,repmat(faces(:,2),bins,1));
P2 = horzcat(Pids,repmat(faces(:,3),bins,1));
% create cloned face list x n bins
faceRep = repmat(faces,bins,1);
% match binIDs and pointIDs
bins_mat = horzcat(binIDs, pointID);

% use ismember to find rows of the face list which contain one of the
% vertices found in P0,P1,P2
P0 = horzcat(Pids(ismember(P0,bins_mat,'rows')),faceRep(ismember(P0,bins_mat,'rows'),:));
P1 = horzcat(Pids(ismember(P1,bins_mat,'rows')),faceRep(ismember(P1,bins_mat,'rows'),:));
P2 = horzcat(Pids(ismember(P2,bins_mat,'rows')),faceRep(ismember(P2,bins_mat,'rows'),:));

% remove duplicates to create stacked face lists (tri_bins(:,2:4))
% matched to bin indices (tri_bins(:,1))
tri_bins = unique(vertcat(P0,P1,P2),'rows');
tri_bins = [1,2,1,12;1,2,3,1;1,4,14,16;1,4,15,14;1,5,2,4;1,5,3,2;1,6,18,10;1,8,6,10;1,8,17,6;1,10,1,3;1,10,3,5;1,10,18,1;1,12,4,2;1,12,15,4;2,2,1,12;2,6,18,10;2,8,6,10;2,8,7,17;2,8,9,19;2,8,11,9;2,8,17,6;2,9,20,19;2,10,1,3;2,10,3,5;2,10,11,8;2,10,18,1;2,12,4,2;2,12,15,4;2,13,14,15;2,13,16,14;2,19,7,8;3,4,14,16;3,4,15,14;3,6,18,10;3,8,7,17;3,8,9,19;3,8,17,6;3,9,20,19;3,10,18,1;3,12,15,4;3,13,14,15;3,13,16,14;3,19,7,8];

This gives the right solution but is too slow. The main reason for this is the multiple calls of ismember, which has a high overhead.
I remember a while back seeing a post about using ‘find’ as alternative to ismember for determining element/row membership but cannot find the link. I have looked at ‘ismembc’ as an alternative but as this requires sorting each column of the face list, it is not really very attractive. I would appreciate any suggestions on how the above code could be speeded up, or any alternative methods for producing the desired output would be most welcome (esp. those that do not require memory hungry cloning using repmat).
Any suggestions/advice from users is appreciated
Thomas

Subject: Looking for an improved method for assigning triangular mesh face indices to multiple bins

From: Thomas

Date: 24 Feb, 2014 10:35:09

Message: 2 of 5

Since there are no takers I will try to simplify the problem. Given that ismember is the main bottleneck, is there anyway using a faster array function (e.g. BSXFUN) to get the same logical vector as ismember with the 'rows' flag enabled?

For example:
P0 = [1,2;1,2;1,13;1,13;1,4;1,4;1,12;1,12;1,5;1,5;1,8;1,8;1,10;1,10;1,6;1,8;1,10;1,9;1,8;1,19;1,8;1,10;2,2;2,2;2,13;2,13;2,4;2,4;2,12;2,12;2,5;2,5;2,8;2,8;2,10;2,10;2,6;2,8;2,10;2,9;2,8;2,19;2,8;2,10;3,2;3,2;3,13;3,13;3,4;3,4;3,12;3,12;3,5;3,5;3,8;3,8;3,10;3,10;3,6;3,8;3,10;3,9;3,8;3,19;3,8;3,10];

bins_mat = [1,1;1,2;1,3;1,4;1,5;1,6;2,7;2,8;2,9;2,10;2,11;2,12;2,13;3,14;3,15;3,16;3,17;3,18;3,19;3,20];

logi = ismember(P0,bins_mat,'rows')

logi =

     1
     1
     0
     0
     1
     1
     0
     0
     1
     1
     0
     0
     0
     0
     1
     0
     0
     0
     0
     0
     0
     0
     0
     0
     1
     1
     0
     0
     1
     1
     0
     0
     1
     1
     1
     1
     0
     1
     1
     1
     1
     0
     1
     1
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     0
     1
     0
     0

I came across this previous post where Matt J presented something similar which did give a big speed up: http://www.mathworks.co.uk/matlabcentral/newsreader/view_thread/306676
I have to say though that even after reading the documentation, BSXFUN remains the most mysterious Matlab function to me (though annoyingly probably one of the most useful).
Any help would be appreciated.
Thanks
Thomas

Subject: Looking for an improved method for assigning triangular mesh face indices to multiple bins

From: Steven Lord

Date: 24 Feb, 2014 15:21:19

Message: 3 of 5


"Thomas " <thomas.seers@postgrad.manchester.ac.uk> wrote in message
news:leaevs$rd4$1@newscl01ah.mathworks.com...
> Hi Matlab users
> Im currently trying to assign triangular mesh face indexes to multiple
> bins based upon an Octree segmentation of its associated vertices. I have
> come up with a vectorized solution using ismember and repmat but the
> function is running unacceptably slow (around 111 seconds for assigning a
> 70000 face / 35000 vertex mesh to 500 bins: it would not be unusual for
> the program to deal with 150000+face meshes / 1000 bins).
> An example of the I/O and the function can be seen below:

*snip*

> % use ismember to find rows of the face list which contain one of the %
> vertices found in P0,P1,P2
> P0 =
> horzcat(Pids(ismember(P0,bins_mat,'rows')),faceRep(ismember(P0,bins_mat,'rows'),:));
> P1 =
> horzcat(Pids(ismember(P1,bins_mat,'rows')),faceRep(ismember(P1,bins_mat,'rows'),:));
> P2 =
> horzcat(Pids(ismember(P2,bins_mat,'rows')),faceRep(ismember(P2,bins_mat,'rows'),:));

I haven't looked too closely, but one obvious gain is not to perform the
same operation twice.

z0 = ismember(P0,bins_mat,'rows');
P0 = horzcat(Pids(z0),faceRep(z0,:));

You could also combine the three ISMEMBER operations into one:

P = [P0; P1; P2];
z = ismember(P, bins_mat, 'rows');

Now use the appropriate piece of z based on the sizes of P0, P1, and P2.

*snip*

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Looking for an improved method for assigning triangular mesh face indices to multiple bins

From: Thomas

Date: 24 Feb, 2014 16:53:08

Message: 4 of 5

Cheers Steve
Stacking the three face lists seems to be a really good idea. I will try this and your other suggestion tonight when I am on my laptop. I may play around with the mysterious BSXFUN with EQ also (I still don't get it!!!). Will get back ASAP.
Thanks
Thomas

Subject: Looking for an improved method for assigning triangular mesh face indices to multiple bins

From: Thomas

Date: 24 Feb, 2014 23:38:08

Message: 5 of 5

Hi Steve
Your suggestion made a big improvement (nearly 10x faster):

tic; sizeP = size(P0,1);
P = [P0; P1; P2];
z = ismember(P, bins_mat, 'rows');
z0 = z(1:sizeP,:);
z1 = z(sizeP+1:sizeP*2,:);
z2 = z(sizeP*2+1:sizeP*3,:);
P0 = horzcat(Pids(z0),faceRep(z0,:));
P1 = horzcat(Pids(z1),faceRep(z1,:));
P2 = horzcat(Pids(z2),faceRep(z2,:));
tri_bins = unique(vertcat(P0,P1,P2),'rows');toc;
Elapsed time is 24.734443 seconds.

I may still have a play with ismembc and bsxfun/eq for my own interest, but this does make the function much more usable for me. I will remember your tips for the future!
Thanks again
Thomas

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us