Edge collapse and mesh decimation in libigl

April 16th, 2015

Libigl purposefully does not build itself around complicated mesh data-structures. This is freeing for many reasons: it’s very easy to include our code in an arbitrary project, functions are not artificially limited to manifold meshes, array based data structures are easily serialized and fast, matrix operations on vertex positions are directly exposed, etc.

mesh decimation in libigl

But our choice is also limiting. In particular, combinatorial changes to the mesh are potentially expensive and difficult to implement. Recently, I took a first stab at implementing an efficient edge-collapse routine for libigl. Indeed I’m seeing good performance: O(1) constant time for a single edge collapse and O(log m) time for cost-priority-queue-based collapses. The data structures are a little “messy” in the sense that when edges or faces disappear their rows are not deleted, but rather just redacted: entries are replaced with NULL values. This is because my approach is array-based and constant resizing would ruin performance. Luckily for edge-collapse, the number of elements only decreases. For edge-split I’ll have to think about amortized costs…

For now, check out the updated tutorial entry for libigl’s new mesh decimation and edge collapse features.

The code is “programmable” in the sense I expose function handles for computing edge costs and merged vertex placements. Though the default functions I currently provide are quite naive, this should support rather advanced “Progressive Meshes” style simplification with creases, sharp features, adaptivity, etc.

Port and Modification of Pascal Frey’s medit software for tet-mesh visualization on github

April 15th, 2015

I’m moving my patched and improved version of Pascal Frey’s medit software from libigl/external to its own github repository. The new version still depends on libigl and AntTweakbar. There’s a matlab wrapper for it in my gptoolbox.

This tool has been essential to my research on tetrahedral meshes. There are more advanced tet-mesh, 3d-slicing visualization tools around, but this one is straightforward and open-source. I’ve made some modifications to make it easier to visualization data and make more complicated slices (hot-dog view!). The input is the same .mesh tet mesh format used by TetGen.

medit screen capture

qslim for Mac OS X on github

April 15th, 2015

A while ago I patched Michael Garland’s qslim to compile on modern Mac OS X. I’ve finally wrangled in the instructions and modified files to a github repo. There are also wrappers for this tool in my gptoolbox. It’d be cool to have a proper C++ API to this tool, but that’s future work.

Qslim is one of the seminal mesh decimation/edge-collapse/simplification techniques. It’s fast, simple and predictable. It’s a good starting place if you’re trying to simplify your mesh, especially in an automated way.

DEC using gptoolbox

April 14th, 2015

Speaking with the Caltech Discrete Exterior Calculus (DEC) promulgators, it seems that despite using DEC notation to explain their math they advocate for building the final algebraic entities (discrete cotangent Laplacian) directly. That is, rather than by multiplying the core DEC stars and d’s.

Nonetheless, when re-implementing these papers I find it useful to follow the texts step-by-step. To do that, I build DEC operators (differentials) using functions in my gptoolbox for MATLAB. I’ll use D0 for d1 and S0 for ★0 and so on:

% List of all "half"-edges: 3*#F by 2
allE = [F(:,[2 3]); F(:,[3 1]); F(:,[1 2])];
% Sort each edge and remember if order changed
[sortallE,I] = sort(allE,2);
% 1 if edge matches half-edge orientation, -1 otherwise
flip = 3-2*I(:,1);
% find unique edges. EMAP(i) tells us where to
% find sortallE(i,:) in uE: so that sortallE(i,:) = uE(EMAP(i),:)
[E,~,EMAP] = unique(sortallE,'rows');
% number of edges
ne = size(E,1);
% number of vertices
nv = size(V,1);
% number of faces
nf = size(F,1);
% S0  nv by nv lumped diagonal mass matrix
S0 = massmatrix(V,F);
% S1  ne by ne diagonal matrix of edge dual-primal ratios (cotangents)
C = cotangent(V,F);
S1 = sparse(EMAP,EMAP,-C(:),ne,ne);
% S2  nf by nf diagonal matrix of inverted face areas
S2 = diag(sparse(doublearea(V,F).^-1))/2;
% D0  ne by nv edge to vertex signed incidence matrix
D0 = sparse(repmat(1:ne,2,1)',E,repmat([1 -1],ne,1),ne,nv);
% D1  nf by ne edge to face signed incidence matrix
D1 = sparse(repmat(1:nf,1,3)',EMAP,flip,nf,ne);

Then you can build familiar matrices like the discrete Laplacian:

L = D0' * S1 * D0;

The analogous code for building these in C++ libigl should hopefully be obvious.

Battle with acmsiggraph.cls’s copyright space

April 13th, 2015

Switching to the final version of the acm siggraph latex template always messes up the first page, but lately I’ve had a lot of trouble with the copyright space. Somehow I end up with blank space all other the first two columns rather than just a small portion at the bottom of the first column. To fix this, in acmsiggraph.cls I replaced:

\footnotetext[0]{\rule[\ACMcopyrightspace]{2.71828in}{0in}}%

with

\footnotetext[0]{\vspace*{1in}}%

MeshFix on github

April 13th, 2015

I’ve moved the meshfix port I made for mac from its buried location inside libigl to its own github repo.

If you’re commonly dealing with bad meshes (self-intersections, non-manifold bits, holes, etc.). This is a great fully automatic tool. I often use it before sending meshes to tetgen. It works particularly for single component meshes with lots of little problems.

Extract full resolution (original) gif image (or other media) from a power point file

March 29th, 2015

I’d lost the original to an animated gif that I’d embedded in a previous talk’s powerpoint slide. I tried clicking “Save image as…” but this gave me a lower resolution, scaled version without the animation. Seems there is a well known trick to finding original media in modern Microsoft office files. The .*x files are actually zipped directories. So unzip them to a folder using something like:

unzip myfile.pptx -d myfile/

Then you should find your media files somewhere in this directory. I found mine in: myfile/ppt/media/.

source

Two-sided material in matlab

March 23rd, 2015

Unfortunately there seems to be no builtin support for two-sided surfaces in matlab. There’s some rudimentary control over back-face lighting, but that’s all. At least you can determine the back-facing triangles for a given camera position:

N = normals(V,F);
BC = barycenter(V,F);
back_facing = sum(N.*bsxfun(@minus,BC,campos),2)<=0;

Here’s an example for an armadillo mesh:

t = tsurf(F,V,'EdgeColor','none','FaceLighting','phong');view(2);
axis equal;
camproj('persp')
t.FaceVertexCData = 1*(sum(N.*bsxfun(@minus,BC,campos),2)<=0)
apply_ambient_occlusion();

armadillo two-sided material

Of course, if you change the view, the coloring is no longer valid:

armadillo two-sided material

So you need to recompute the coloring:

armadillo two-sided material

You can also insert nans to achieve back-face culling:

t.FaceVertexCData(sum(N.*bsxfun(@minus,BC,campos),2)>0) = nan;

armadillo back-face culling matlab

EZproxy bookmarklet

March 20th, 2015

The columbia proxy/vpn never worked super well for me. Or at least I didn’t try very hard to set it up. I really only need it for viewing academic articles off campus. So usually I just search for it via the columbia library’s website, log in, and retrieve the article. Doing this I noticed that the library is just feeding me the usual link (e.g. from acm dl) but via an “ezproxy”. So

http://dl.acm.org/citation.cfm?id=2185544 becomes

http://dl.acm.org.ezproxy.cul.columbia.edu/citation.cfm?id=2185544.

I wrapped this replacement into a javascript bookmarklet.

javascript:(function(){window.location.href=window.location.href.replace(/http:\/\/[^\/]*/,"$&.ezproxy.cul.columbia.edu");})()

Now I can follow the google search result, hit this bookmarklet, log in if I haven’t already, and view the articles.

Parse a list of numbers without hard coding size

March 19th, 2015

I’ve been used to parsing numbers from strings with the c-style sscanf function. So if I need to read in 3 floats into a vector I’d use something like:

vector<float> v(3);
sscanf(string_to_parse,"%f %f %f",&v[0],&v[1],&v[2]);

This is fine if you know at compile time that the vector will be size 3. But if the number isn’t known at compile time, the c-style gets messy with loops.

Here’s a c++-style solution. Admittedly there are also some messy-looking loops, but I still prefer it. It also makes it easy to have a richer delimiter set.

// http://stackoverflow.com/a/1894955
#include <vector>
#include <string>
#include <sstream>
...
  using namespace std;
  vector<double> vect;
  string delimeters = ", ";
  stringstream ss(string_to_parse);
  double v;
  while(ss >> v)
  {
    vect.push_back(v);
    while(string::npos != delimeters.find(ss.peek()))
    {
      ss.ignore();
    }
  }