## Posts Tagged ‘libigl’

### Offset surface of triangle mesh in matlab

Wednesday, March 22nd, 2017

Here’s a little demonstration of how to use gptoolbox and MATLAB to generate an offset surfaces of a triangle mesh. This takes a mesh in V,F and creates a mesh SV,SF of the isosurface at signed distance iso:

% Extract offset at minus 3% of bounind box diagonal length
iso = -0.03;
% Resolution grid → resolution of extracted offset surface
side = 60;
% Amount of smoothing to apply to distance field
sigma = 1.4;
bbd = norm(max(V)-min(V));
% Pad generously for positive iso values
[BC,side,r] = voxel_grid([V;max(V)+iso*1;min(V)-iso*1],side);
D = signed_distance(BC,V,F);
D = reshape(D,side([2 1 3]));
% Smooth signed distance field
D = imfilter(D,fspecial('gaussian',9,sigma),'replicate');
BC3 = reshape(BC,[side([2 1 3]) 3]);
% Use matlab's built-in marching cubes iso-surface mesher (works most of the time)
surf = isosurface(BC3(:,:,:,1),BC3(:,:,:,2),BC3(:,:,:,3),D,iso*bbd);
SV = surf.vertices;
SF = surf.faces;


Here’s a blue bunny with a positive offset surface, an orange “cage”:

Here’s a blue bunny with a negative offset surface. This is useful for hollowing out objects to 3d print:

Because the iso-surface extraction will over tesselate low curvature patches of the output surface, it would make a lot of sense to remesh/decimate this mesh.

(to create these fancy renderings:)

clf;
hold on;
t  = tsurf(F,V,'EdgeColor','none',fsoft,  'FaceVertexCData',repmat(blue,size(V,1),1),'FaceAlpha',1+(iso<0)*(0.35-1),fphong);
ts = tsurf(SF,SV,'EdgeAlpha',0.2+(iso<0)*(0-0.2),fsoft,'FaceVertexCData',repmat(orange,size(SV,1),1),fphong,'FaceAlpha',1+(iso>0)*(0.2-1));
apply_ambient_occlusion(ts);
hold off;
axis equal;
view(-20,20)
camlight;
t.SpecularStrength = 0.04;
l = light('Position',[5 -5 10],'Style','local');
set(gca,'pos',[0 0 1 1])
set(gca,'Visible','off');
set(gcf,'Color','w');
drawnow;


### Command line program to view 3d meshes from files and piped input

Thursday, December 15th, 2016

Here’s a little C++ program to directly render meshes in 3D viewer from the command line.

This let’s you write little test programs without worrying about linking to a 3D viewer. You just need to output a mesh in a standard format. For example, here’s a tiny program that outputs a cube in an .off format:

#include <igl/read_triangle_mesh.h>
#include <Eigen/Core>
#include <iostream>

int main(int argc, char * argv[])
{
using namespace Eigen;
MatrixXd V(8,3);
MatrixXi Q(6,4);
V<<
0,0,1,
0,1,1,
1,1,1,
1,0,1,
0,0,0,
0,1,0,
1,1,0,
1,0,0;
Q<<
3,2,1,0,
0,1,5,4,
6,5,1,2,
3,7,6,2,
4,7,3,0,
4,5,6,7;
std::cout<<
"OFF\n"<<V.rows()<<" "<<Q.rows()<<" 0\n"<<
V.format(IOFormat(FullPrecision,DontAlignCols," ","\n","","","","\n"))<<
(Q.array()).format(IOFormat(FullPrecision,DontAlignCols," ","\n","4 ","","","\n"));
return EXIT_SUCCESS;
}


Compile this into cube_off then issue:

./cube_off | view mesh


**Update: ** And here’s a funny, little one-liner you can call from matlab to display a mesh via the .obj format:

system(sprintf('echo \"%s%s\" | /usr/local/bin/viewmesh',sprintf('v %0.17f %0.17f %0.17f\n',V'),sprintf('f %d %d %d\n',F')))


### Background computation threads with igl::viewer::Viewer

Sunday, December 4th, 2016

Here’s a minimal example showing how to launch background computation threads for each mesh in a list of meshes. Meanwhile the main thread runs a mesh viewer with all meshes concatenated into one huge multi-component mesh. Whenever a computation thread signals that an update to the mesh needs to be made, the main thread will re-concatenate the meshes and update the viewer. In this example, the “computation” is determining how much to move a clock “hand” (random mesh).

Here’s the program running on the cow, cheburashka and knight models:

// Tiny example to demonstrate spawning a background computation thread for
// each mesh in a list and update the viewer when computation results in a
// change to (one of) the meshes.
//
// In this example, three meshes are read in and interpreted as "hands" of a
// clock. The "computation" is just a busy-wait until the hand should move
// (after one second, one minute, one hour). This is, of course, a terrible way
// to implement a clock.
//
// ./test libigl/tutorial/shared/{cow.off,cheburashka.off,decimated-knight.off}
#include <igl/point_mesh_squared_distance.h>
#include <igl/combine.h>
#include <igl/viewer/Viewer.h>
#include <Eigen/Geometry>
int main(int argc, char * argv[])
{
using namespace std;
using namespace Eigen;
// Read in k meshes (<=3 will be used)
std::vector<Eigen::MatrixXd> VV(argc-1);
std::vector<Eigen::MatrixXi> FF(argc-1);
for(int i = 1;i<argc;i++)
{
VV[i-1].col(0).array() -= VV[i-1].col(0).mean();
VV[i-1].col(1).array() -= VV[i-1].col(1).minCoeff();
}
bool continue_computing = true;
// Flag to redraw and mutex to guard it
bool redraw = false;
std::mutex m;
// After waiting tic seconds, rotate V by deg degrees
const auto rot = [&continue_computing,&redraw,&m](
const double tic, const double deg, Eigen::MatrixXd& V)
{
while(continue_computing)
{
// Let's watch this at 500x: Real clocks are slow.
V *= Eigen::AngleAxisd(deg/180.*igl::PI,
Eigen::Vector3d(0,0,1)).toRotationMatrix();
{
std::lock_guard<std::mutex> lock(m);
redraw = true;
}
}
};
// Launch background "computation" threads for each "hand" of the clock
// std::ref is important, otherwise std::bind passes by copy
switch(VV.size())
{
case 3:
case 2:
case 1:
default: break;
}
igl::viewer::Viewer v;
v.data.clear();
// Helper function to view k meshes
const auto & set_meshes = [](
const std::vector<Eigen::MatrixXd> & VV,
const std::vector<Eigen::MatrixXi> & FF,
igl::viewer::Viewer & v)
{
Eigen::MatrixXd V;
Eigen::MatrixXi F;
igl::combine(VV,FF,V,F);
v.data.set_mesh(V,F);
};
set_meshes(VV,FF,v);
// Continuous draw loop. TODO: trigger draws using glfwPostEmptyEvent
v.core.is_animating = true;
// Before every draw check if the meshes have changed.
v.callback_pre_draw =
[&redraw,&m,&VV,&FF,&set_meshes](igl::viewer::Viewer & v)->bool
{
if(redraw)
{
set_meshes(VV,FF,v);
{
std::lock_guard<std::mutex> lock(m);
redraw = false;
}
}
return false;
};
v.launch();
// Tell computation threads to stop
continue_computing = false;
for(auto & t : threads) if(t.joinable()) t.join();
}


This is pretty hacky, but it will allow me to use the standard libigl viewer for making comparisons of mesh-editing methods whose performances are very different.

### Implementing QSlim mesh simplification using libigl

Friday, November 4th, 2016

One of my research projects is looking at mesh simplification and the perennial comparison is always to Garland and Heckbert’s “Surface simplification using quadric error metrics” (aka QSlim). And relevant to us, the lesser-known followup for “Surfaces with Color and Texture using Quadric Error” (aka QSlim in nD)

Currently, libigl has built in edge-collapse based mesh simplification with an exposed function handle: cost_and_placement which determines the cost of collapsing an edge and the placement. This function is used for two purposes: to initialize the heap of edges to collapse and to update edges in that heap after a collapse.

Currently I had only implemented a very simple metric: cost is the length of the edge and collapsed vertices are placed at edge midpoints.

So a bit out of research necessity and a bit just for a challenge, I timed how long it would take for me to implement QSlim in nD.

So, 1 hour and 20 minutes later, here is my QSlim in nD demo based off of the decimation entry in the libigl tutorial:

#include <igl/collapse_edge.h>
#include <igl/edge_flaps.h>
#include <igl/viewer/Viewer.h>
#include <Eigen/Core>
#include <iostream>
#include <set>

int main(int argc, char * argv[])
{
using namespace std;
using namespace Eigen;
using namespace igl;
cout<<"Usage: ./703_Decimation_bin [filename.(off|obj|ply)]"<<endl;
cout<<"  [space]  toggle animation."<<endl;
cout<<"  'r'  reset."<<endl;
// Load a closed manifold mesh
string filename(argv[1]);
if(argc>=2)
{
filename = argv[1];
}
MatrixXd V,OV;
MatrixXi F,OF;

igl::viewer::Viewer viewer;

// Prepare array-based edge data structures and priority queue
VectorXi EMAP;
MatrixXi E,EF,EI;
typedef std::set<std::pair<double,int> > PriorityQueue;
PriorityQueue Q;
std::vector<PriorityQueue::iterator > Qit;
// If an edge were collapsed, we'd collapse it to these points:
MatrixXd C;
int num_collapsed;

// Function for computing cost of collapsing edge (lenght) and placement
// (midpoint)
const auto & shortest_edge_and_midpoint = [](
const int e,
const Eigen::MatrixXd & V,
const Eigen::MatrixXi & /*F*/,
const Eigen::MatrixXi & E,
const Eigen::VectorXi & /*EMAP*/,
const Eigen::MatrixXi & /*EF*/,
const Eigen::MatrixXi & /*EI*/,
double & cost,
RowVectorXd & p)
{
cost = (V.row(E(e,0))-V.row(E(e,1))).norm();
p = 0.5*(V.row(E(e,0))+V.row(E(e,1)));
};

// c **is** allowed to be a or b.
{
std::get<0>(c) = (std::get<0>(a) + std::get<0>(b)).eval();
std::get<1>(c) = (std::get<1>(a) + std::get<1>(b)).eval();
std::get<2>(c) = (std::get<2>(a) + std::get<2>(b));
};
// State variables keeping track of whether we've just collpased edge (v1,v2)
int v1 = -1;
int v2 = -1;
const auto & qslim_optimal = [&quadrics,&plus,&v1,&v2](
const int e,
const Eigen::MatrixXd & V,
const Eigen::MatrixXi & /*F*/,
const Eigen::MatrixXi & E,
const Eigen::VectorXi & /*EMAP*/,
const Eigen::MatrixXi & /*EF*/,
const Eigen::MatrixXi & /*EI*/,
double & cost,
RowVectorXd & p)
{
// Then we just collapsed (v1,v2)
if(v1>=0 && v2>=0)
{
v1 = -1;
v2 = -1;
}
// Quadric: p'Ap + 2b'p + c
// optimal point: Ap = -b, or rather because we have row vectors: pA=-b
const auto & A = std::get<0>(quadric_p);
const auto & b = std::get<1>(quadric_p);
const auto & c = std::get<2>(quadric_p);
p = -b*A.inverse();
cost = p.dot(p*A) + 2*p.dot(b) + c;
};

// Function to reset original mesh and data structures
const auto & reset = [&]()
{
F = OF;
V = OV;
edge_flaps(F,E,EMAP,EF,EI);
Qit.resize(E.rows());
Q.clear();

const int dim = V.cols();
// Initialize each vertex quadric to zeros
V.rows(),{Eigen::MatrixXd::Zero(dim,dim),Eigen::RowVectorXd::Zero(dim),0});
Eigen::MatrixXd I = Eigen::MatrixXd::Identity(dim,dim);
// Rather initial with zeros, initial with a small amount of energy pull
// toward original vertex position
const double w = 1e-10;
for(int v = 0;v<V.rows();v++)
{
Eigen::RowVectorXd Vv = V.row(v);
}
// Generic nD qslim from "Simplifying Surfaces with Color and Texture
for(int f = 0;f<F.rows();f++)
{
Eigen::RowVectorXd p = V.row(F(f,0));
Eigen::RowVectorXd q = V.row(F(f,1));
Eigen::RowVectorXd r = V.row(F(f,2));
Eigen::RowVectorXd pq = q-p;
Eigen::RowVectorXd pr = r-p;
// Gram Determinant = squared area of parallelogram
double area = sqrt(pq.squaredNorm()*pr.squaredNorm() - pow(pr.dot(pq),2));
Eigen::RowVectorXd e1 = pq.normalized();
Eigen::RowVectorXd e2 = (pr-e1.dot(pr)*e1).normalized();
// e1 and e2 be perpendicular
assert(std::abs(e1.dot(e2)) < 1e-10);
// Weight face's quadric (v'*A*v + 2*b'*v + c) by area
const Eigen::MatrixXd A = I-e1.transpose()*e1-e2.transpose()*e2;
const Eigen::RowVectorXd b = p.dot(e1)*e1 + p.dot(e2)*e2 - p;
const double c = (p.dot(p) - pow(p.dot(e1),2) - pow(p.dot(e2),2));
face_quadrics[f] = { area*A, area*b, area*c };
// Throw at each corner
for(int c = 0;c<3;c++)
{
plus(
}
}

C.resize(E.rows(),V.cols());
VectorXd costs(E.rows());
v1 = -1;
v2 = -1;
for(int e = 0;e<E.rows();e++)
{
double cost = e;
RowVectorXd p(1,3);
qslim_optimal(e,V,F,E,EMAP,EF,EI,cost,p);
C.row(e) = p;
Qit[e] = Q.insert(std::pair<double,int>(cost,e)).first;
}
num_collapsed = 0;
viewer.data.clear();
viewer.data.set_mesh(V,F);
viewer.data.set_face_based(true);
};

const auto &pre_draw = [&](igl::viewer::Viewer & viewer)->bool
{
// If animating then collapse 10% of edges
if(viewer.core.is_animating && !Q.empty())
{
bool something_collapsed = false;
// collapse edge
const int max_iter = std::ceil(0.01*Q.size());
for(int j = 0;j<max_iter;j++)
{
std::pair<double,int> p = *(Q.begin());
bool shouldnt_collapse = false;
if((! Q.empty()) &&
(p.first != std::numeric_limits<double>::infinity()))
{
v1 = E(p.second,0);
v2 = E(p.second,1);
}else
{
v1 = -1;
v2 = -1;
shouldnt_collapse = true;
}
if(!collapse_edge(qslim_optimal,V,F,E,EMAP,EF,EI,Q,Qit,C))
{
break;
}else
{
// we just collapsed.
assert(!shouldnt_collapse);
}
something_collapsed = true;
num_collapsed++;
}

if(something_collapsed)
{
viewer.data.clear();
viewer.data.set_mesh(V,F);
viewer.data.set_face_based(true);
}
}
return false;
};

const auto &key_down =
[&](igl::viewer::Viewer &viewer,unsigned char key,int mod)->bool
{
switch(key)
{
case ' ':
viewer.core.is_animating ^= 1;
break;
case 'R':
case 'r':
reset();
break;
default:
return false;
}
return true;
};

reset();
viewer.core.is_animating = true;
viewer.callback_key_down = key_down;
viewer.callback_pre_draw = pre_draw;
return viewer.launch();
}


I’m pretty happy that this didn’t take me all day, but admittedly it should have been faster. One confusing part was that the current API in libigl for edge collapsing doesn’t have an explicit function handle that’s called when an edge is successfully collapsed. Detecting this is necessary to propagate the quadric to the collapsed vertex (but isn’t necessary for simple costs like edge-length). I faked this for now using v1 and v2 as state variables. Probably, I’ll change the libigl API to accommodate this. The other time sink was worry about degenerate Quadrics (when the system matrix is singular). Rather than try to detect this categorically, I opted to sprinkle in a little energy pulling vertices toward their (ancestors’) original positions. This seems to work fairly well.

### Adding libigl as a submodule

Thursday, June 9th, 2016

If you’re adding libigl as a submodule to your project, you should add it recursively so that all of its submodules are also pulled in:

git submodule add https://github.com/libigl/libigl.git
git submodule update --init --recursive


### Mesh Arrangements for Solid Geometry preprint

Thursday, April 21st, 2016

I’m very excited to publish my work with Qingnan Zhou, Eitan Grinspun and Denis Zorin on mesh booleans at this year’s SIGGRAPH. The paper is titled Mesh Arrangements for Solid Geometry. The code is (and has been) in libigl and gptoolbox and pymesh.

### Variadic mesh boolean operations in libigl and gptoolbox

Thursday, April 14th, 2016

I’ve just pushed some new changes to libigl and gptoolbox to expose the variadic implementation of our robust mesh boolean operations. By variadic, I mean that the boolean function can take one mesh as input or two meshes as input (usual binary case) or three or four and so on. This means you can easily take the union or intersection of n objects, but it also means that complex operations can be reduced to single call. For example, identifying regions inside at least k out of n objects. I first became aware of this variadic concept when reading “QuickCSG: Arbitrary and Faster Boolean Combinations of N Solids”.

In libigl, you can call igl::copyleft::cgal::mesh_boolean with an n-long list of mesh vertex arrays and an n-long list of mesh face arrays. Rather than the usual union, intersection, minus etc., you can also pass a C++ function handle. This function handle will filter the winding number vector at any point in space. For example, if you’d like to extract the region inside object 0 and not inside object 1 and either inside object 2 or not inside object 3. The filter would return w(0) > 0 && w(1)<=0 && (w(2)>0 || w(3)<= 0).

After a bit of pointer tweaking, I’ve also exposed this interface to the matlab wrapper in gptoolbox. You can pass a matlab function handle after the optional argument ‘WindingNumberFilter’. For example, assuming V and F are cell arrays containing vertex position arrays and face indices respectively, the following command will extract the region inside at least 3 of the inputs:

 [VV,FF,J] = mesh_boolean(V,F,'','WindingNumberFilter',@(w) sum(w>0)>=3);


You could also call it with

 [VV,FF,J] = mesh_boolean(V{1},F{1},V{2},F{2},V{3},F{3},V{4},F{4},'','WindingNumberFilter',@(w) sum(w>0)>=3);


Here’s an example of extracting min-k results from 4 spheres:

Since extraction from our mesh arrangement is cheap, each operation takes the same amount of time. And fortunately it seems that the mex function handle overhead is not so bad.

Update: Variadic operations are also useful for condensing entire binary CSG trees: (A union B) minus (C union D) could be a single extraction function on (A,B,C,D) return (w(0)>0 || w(1)>0) && !(w(2)>0 || w(3)>0)

### Using meshfix “from libigl”

Wednesday, March 30th, 2016

Here’s a little example of how to call meshfix using plain Eigen types to represent a mesh (i.e. in the libigl style. I’ve included this example in my github fork of the meshfix code.

#define MESHFIX_WITH_EIGEN
#include "meshfix.h"

#include <igl/write_triangle_mesh.h>
#include <iostream>

int main(int argc, char * argv[])
{
// Load in libigl's (V,F) format
Eigen::MatrixXd V,W;
Eigen::MatrixXi F,G;
if(argc <= 2)
{
std::cout<<R"(Usage:
./meshfix-libigl [input](.obj|.ply|.stl|.off) [output](.obj|.ply|.stl|.off)
)";
return EXIT_FAILURE;
}
meshfix(V,F,W,G);
// Write to OBJ
igl::write_triangle_mesh(argv[2],W,G);
}


Then you can run this by issuing something like:

./meshfix-libigl input.obj output.ply


### Hacky texture map editor using libigl

Thursday, January 7th, 2016

Here’s a little program that reads a texture mapped mesh from an .obj with UVs and a texture map from a .png and visualizes them.

Before every frame is drawn, I reload the .png file. So if you’ve saved a newly edited version, say in photoshop with a window open next to the viewer window, then it will be loaded. The bottleneck currently is for sure me hitting the save key.

#include <igl/readOBJ.h>
#include <igl/viewer/Viewer.h>
#include <igl/unzip_corners.h>
#include <YImage.hpp>
#include <iostream>
int main(int argc, char * argv[])
{
using namespace std;
Eigen::MatrixXd V, TC, N;
Eigen::MatrixXi F,FTC,FN;
if(FTC.size() == 0)
{
FTC = F;
}
igl::viewer::Viewer viewer;
typedef Eigen::Matrix<unsigned char,Eigen::Dynamic,Eigen::Dynamic> MatrixXuc;
MatrixXuc R,G,B;
const auto & update_texture = [&]()
{
YImage yimg;
R.resize(yimg.width(),yimg.height());
B.resize(R.rows(),R.cols());
G.resize(R.rows(),R.cols());
for(int i = 0;i<yimg.width();i++)
{
for(int j = 0;j<yimg.height();j++)
{
const auto & p = yimg.at(i,j);
R(i,yimg.height()-1-j) = p.r;
G(i,yimg.height()-1-j) = p.g;
B(i,yimg.height()-1-j) = p.b;
}
}
};
viewer.callback_pre_draw = [&](igl::viewer::Viewer &)->bool
{
update_texture();
viewer.data.set_texture(R,G,B);
return false;
};
viewer.data.set_mesh(V,F);
viewer.data.set_colors((Eigen::MatrixXd(1,3) << 1,1,1).finished());
viewer.data.set_uv(TC,FTC);
viewer.core.show_texture = true;
viewer.core.is_animating = true;
viewer.launch();
}


### Unzip OBJ-style mesh into a per-vertex attribute mesh

Wednesday, January 6th, 2016

The .obj mesh file format allows corners of triangles to pull attributes from different sources. The triangle:

v 0 0 0
v 1 0 0
v 0 0 0
vn 1 0 0
vn 0 1 0
vt 0 0 0
f 1/1/1 2/1/1 3/1/2


pulls vertex positions from entries (1,2,3) in the v ... vertex position list, texture coordinates from entries (1,1,1) in the vt ... list, and normals from entries (1,2,2) in the vn normals list.

If we think of corners being described by all attributes there are potentially #F*3 distinct corners. Often information is shared, and in the best case the position/texture/normal indices are all the same, so #V distinct corners. Usually it’s some mixture in between.

I added igl::unzip_corners to libigl which “unzips” an OBJ-style mesh into per-vertex attribute mesh: each new vertex is a distinct corner, so the new face list indexes all attributes in lock step (ideal for OpenGL). I was careful to determine uniqueness combinatorially so, for example, combinatorially distinct input vertices happening to share the same attributes (two vertices at the same position, etc.) don’t get merged (you could always use igl::remove_duplicate_vertices if you wanted to do that).

Here’s a little demo program:

  Eigen::MatrixXd V, TC, N;
Eigen::MatrixXi F,FTC,FN;