Faster and more compact vt

[bbrrck]

This commit simplifies the computation of Vertex-Face topology (13 lines > 3 lines). Also, the new code is about 30% faster.

[alecjacobson]

Oh funny. I didn't even know this existed... I always just built it using sparse... While we're at it we should drop the V input as it's obviously not needed.

[bbrrck]

Libigl has vertex_triangle_adjacency.h, which I did not find here, so I just implemented it myself and only found it afterwards. Maybe we should change the name from vt to vertex_triangle_adjacency to match libigl?

[alecjacobson]

yeah, that makes sense. I fairly confident this is not used anywhere else in gptoolbox though many places just construct this on the fly. Sadly calling a function has a significant overhead so it's probably not worth factor those out.

[bbrrck]

I ran a quick test on a mesh with ~200k triangles – calling the function seems to be only marginally slower.

num_iter = 100;

tic
for iter=1:num_iter
  i = (1:size(F,1))';
  j = F;
  VT = sparse([i i i],j,1);
end
toc

tic
for iter=1:num_iter
  [VT] = vertex_triangle_adjacency(F);
end
toc

Elapsed time is 5.052412 seconds.
Elapsed time is 5.057198 seconds.

[alecjacobson]

For a big mesh that's probably true. For a small mesh I think the function overhead will dominate.

[bbrrck]

Btw the only function that calls vt is et. And there are two other functions in this category, tt and vv (which is also implemented using nested for loops). Do you think these too are worth renaming/modifying?

[bbrrck]

For a small mesh (2k faces) I'm consistently getting faster timings by calling the function.

% 1000 iters
Elapsed time is 0.393886 seconds. % not using vertex_triangle_adjacency
Elapsed time is 0.379115 seconds. % using vertex_triangle_adjacency

[alecjacobson]

re:timings, well that's weird. Maybe function overhead is no longer something to worry about (btw, I like use timeit for these things).

re:other functions, I don't think I'm using vv or et anywhere, these are all super old legacy functions written by NYU folks. But I do think I'm using tt (and I remember optimize it at one point) in a few places (inside and outside of gptoolbox). So renaming is fine but we should have tt.m as a dummy wrapper that throws a warning and calls the new function.

[bbrrck]

Summary of the changes:

• et.m replaced by edge_triangle_adjacency.m
• tt.m replaced by triangle_triangle_adjacency.m
• vt.m replaced by vertex_triangle_adjacency.m
• tt.m kept as a dummy function calling triangle_triangle_adjacency.m
• vv.m kept as a dummy function calling adjacency_matrix.m
• few changes to other functions referencing tt, namely cdt.m, connectedComponent.m, find_ears.m

[alecjacobson]

thanks!