Posts Tagged ‘mesh’

Classic bump deformation example mesh

Saturday, June 28th, 2014

This is code I end up re-writing every once in a while to demonstrate k-harmonic deformation on a simple 2d domain. The domain is just a square. This codes meshes the domain so that two inner circles show up in the edge set. Then I can select the vertices on and outside the outer circle and on and inside the inner circle to create a bump.

R = 1;
r = 0.15;
outer_sam = 200;
inner_sam = ceil(outer_sam/R*r);
inner_theta = linspace(0,2*pi,inner_sam+1)';
outer_theta = linspace(0,2*pi,outer_sam+1)';
P_inner = r*[cos(inner_theta(2:end)) sin(inner_theta(2:end))];
P_outer = R*[cos(outer_theta(2:end)) sin(outer_theta(2:end))];
E_inner = [1:size(P_inner,1);2:size(P_inner,1) 1]';
E_outer = [1:size(P_outer,1);2:size(P_outer,1) 1]';
P_bb = 1.1*[-R -R;-R R;R R;R -R];
E_bb = [1 2;2 3;3 4;4 1];
[P_bb,E_bb] = resample_polygon(P_bb,E_bb,2*pi*R/outer_sam);
P = [P_inner;P_outer;P_bb];
E = [E_inner;size(P_inner,1)+[E_outer;size(P_outer,1)+E_bb]];
[V,F] = triangle(P,E,[],'Flags',sprintf('-Yq32a%0.17f',(2*pi*R/outer_sam)^2),'Quiet'); 

bump domain matlab

Compute and visualize self-intersections and intersections between two meshes

Saturday, April 26th, 2014

I add the self-intersection computation code from our winding numbers project to libigl. I made a small example (libigl/examples/intersections) that will compute and visualize all triangles participating in self-intersections in red. Here are the self-intersections of the Klein bottle:


I also wrote up a function to compute intersections between two meshes. Here’s that same example run on two meshes:

intersections between two meshes

Determine manifold patches of a triangle mesh

Tuesday, October 8th, 2013

Here’s a very compact algorithm for determining the manifold patches of a given triangle mesh (V,F). I’m defining a manifold patch to be a collection of neighboring facets in F such that they’re union forms an edge-manifold submesh. A mesh is edge-manifold if no edge is shared by more than 2 facets.

Save this in a file called manifold_patches.m:

function [C,A] = manifold_patches(F)
  % Compute connected components of facets connected by manifold edges.
  % Inputs:
  %   F  #F by simplex-size list of facets
  % Outputs:
  %   C  #F list of component ids

  % simplex size
  ss = size(F,2);
  assert(ss == 3);

  % List of all "half"-edges: 3*#F by 2
  allE = [F(:,[2 3]); F(:,[3 1]); F(:,[1 2])];
  % Sort each row
  sortallE = sort(allE,2);
  % IC(i) tells us where to find sortallE(i,:) in uE: 
  % so that sortallE(i,:) = uE(IC(i),:)
  [uE,~,IC] = unique(sortallE,'rows');
  % uE2F(e,f) = 1 means face f is adjacent to unique edge e
  uE2F = sparse(IC(:),repmat(1:size(F,1),1,ss)',1);
  % kill non-manifold edges
  uE2F(sum(uE2F,2)>2,:) = 0;
  % Face-face Adjacency matrix
  A = uE2F'*uE2F;
  % All ones
  A = A>0;
  % Connected components are patches
  %C = components(A); % alternative to graphconncomp from matlab_bgl
  [~,C] = graphconncomp(A);

The “trick” if there is one, is that we first build an undirected edge to facet adjacency matrix. We zap-out any rows corresponding to edges with more than two incident facts. Then we “square” this matrix to give use a facet to facet adjacency matrix where two facets are neighbors iff the edge they share have only two incident facets. Finally we use a library call to compute the connected components of the graph induced by this adjacency matrix.

Here’s the result on an example, all manifold patches visualized with a unique pseudocolor:

Truck mesh pseudocolor manifold patches

And for comparison here’s a visualization of the graph connected components (defined per vertex, neighboring vertices share an edge).

Truck mesh pseudocolor connected components

Plot piecewise constant function over 2D triangle mesh as height field

Tuesday, October 8th, 2013

I typically deal with piecewise linear functions defined over a triangle mesh (values defined per vertex). I can plot this over a 2d triangle mesh domain using the trisurf function:


I wrap this into my own function tsurf to make it easier to call since I call them so often:

tsurf(F,[V S]);

piecewise linear height-field over triangle mesh

Sometimes I deal with piecewise constant functions (values defined per triangle). To plot this I use:

tsurf(bsxfun(@plus,size(F,1)*(0:size(F,2)-1),(1:size(F,1))'),[V(F(:),:) repmat(S,size(F,2),1)]);

Or broken down:

% positions of all "Corners"
C = V(F(:),:);
% Scalar field defined at corners
SC = repmat(S,size(F,2),1);
% new disjoint triangle indices into C for each original triangle
FC = bsxfun(@plus,size(F,1)*(0:size(F,2)-1),(1:size(F,1))');
% plot each triangle as piecewise linear function (each of which happens to be constant)
tsurf(FC,[C SC]);

piecewise constant height-field over triangle mesh

QuickLook generator plugin for 3D model mesh file formats (.off, .obj, .mesh, .wrl)

Sunday, October 6th, 2013

Using libigl and Mesa3D’s off screen rendering is was easy to whip up a QuickLook preview and thumbnail generator for our favorite 3D model file formats. I opted to avoid Xcode and compile the application using a good old Makefile. You can find the project in the libigl examples libigl/examples/quicklook-mesh/ (as of version 0.3.2).

Once installed the QuickLook generator will make (static) previews of any .mesh, .off, .obj or .wrl files when hit [space] after selecting the file in

Mesh quicklook preview

Or when you use one of the fancier views

Mesh quicklook thumbnail

I imagine I’ll be perfecting this over time, but for now it shows 6 canonical views and uses a double-sided material to give you an idea of any inconsistent mesh orientation issues. It should work for triangle meshes or general polygonal meshes.

You can skip compiling and just download Mesh.qlgenerator. Install it by moving Mesh.qlgenerator/ into /Library/QuickLook/. Then either restart you computer or issue in a Terminal:

qlmanage -r
qlmanage -r cache

Update: I’ve finally fixed some issues with the dynamic libraries. The updated Mesh.qlgenerator now contains a binary which should work anywhere, without requiring you to install Mesa3D or any other dependencies.

Update: I’ve moved this out of the libigl/examples to its own repo on github.

Compile SVR on mac os x

Saturday, August 24th, 2013

I managed to get the PLC meshing program SVR (an alternative to tetgen). It was a little difficult to get compiled on Mac OS X so here are my notes.

The first weird thing is that the make configuration for SVR tries to download and compile the boost libraries. To get rid of this and just use boost as installed from macports I commented out the following line in boost/ from:

all: stamp-boost



Then I ran:

./configure --prefix=/usr/local/svr CPPFLAGS='-Wno-deprecated -fno-strict-aliasing'

Before making there are a few files that need to be altered. In utilities/details/hash.h add the following include:

#include <boost/cstdint.hpp>

In feature-refine/GenericMesh.h, feature-refine/RefineVertex.h, and utilities/FastHash.h remove the following

: public boost::noncopyable

In feature-refine/SVR.cpp, front-end/SVR.cpp, and point-refine/svr.cpp add the following after the definition of valgrind_hack:


Using patcht to texture map a triangle mesh in matlab

Friday, August 9th, 2013

Recently I found the patcht script which lets you texture map a triangle mesh in matlab. It unfortunately does it in a brute force way: creating a textured surface for every triangle. But it’s at least something. Here’s how I use it for 2d meshes of images using the xy positions as texture coordinates:

im = imread('woody.png');
[V,F] = load_mesh('woody.obj');
patcht(F,V,F,[max(V(:,2))-V(:,2) V(:,1)],im);
axis equal

which produces:

patcht script texture mapping triangle mesh in matlab

We thank Scott Schaefer for providing the wooden gingerbread man image from “Image Deformation Using Moving Least Squares”.

Visualizing samples on a sphere

Friday, May 17th, 2013

In my project, I need to uniformly sample directions or equivalently points on the unit sphere. A correct way is to sample the azimuth and cosine of the polar angle uniformly. Another way is to sample points in ℝ3 randomly with mean at the origin and variance 1.

One naive non uniform way, is to sample the x, y and z between [-1,1] uniformly and normalize. I knew that this was biased, but I wanted to see the bias. Here’s a small matlab program that continuous splats random points onto a textured sphere:

% Can't use sphere(); have to use funny parameterization so tex-mapping works
n = 100;
theta = (-n:2:n)/n*pi;
sinphi = (-n:2:n)'/n*1;
cosphi = sqrt(1-sinphi.^2); cosphi(1) = 0; cosphi(n+1) = 0;
sintheta = sin(theta); sintheta(1) = 0; sintheta(n+1) = 0;
X = cosphi*cos(theta);
Y = cosphi*sintheta;
Z = sinphi*ones(1,n+1);
% square texture resolution
w = 1000;
im = ones(w,w);
s = surf(X,Y,Z,'FaceColor','texturemap','Cdata',im,'EdgeColor','none');
axis equal;
method = 'naive';
%method = 'uniform';
%method = 'normal-deviation';
it = 0;
sam = 2000000;
while true
  switch method
  case 'naive'
    % uniformly random 3d point, each coord in [-1,1] and normalize
    N = normalizerow(2*rand(sam,3)-1);
  case 'normal-deviation'
    N = normalizerow(normrnd(zeros(sam,3),1));
  case 'uniform'
    % random polar angle and azimuth
    Z = rand(sam,1)*2-1;
    A = rand(sam,1)*2*pi;
    R =  sqrt(1-Z.^2);
    N = [Z R.*cos(A) R.*sin(A)];
  % project
  S = [(N(:,3)+1)/2 (atan2(N(:,2),N(:,1))+pi)/(2*pi)];
  % splat!
  S = round([mod(w*S(:,2),w-0.5) mod(w*S(:,1),w-0.5)]+1);
  im = im + full(1-sparse(S(:,2),S(:,1),1,w,w));
  it = it + 1;

This produces an incrementally improving image of a textured sphere where black means high probability and white means low probability:
naive sampling sphere matlab visualization

When this converges we can examine the bias around the sphere:
naive sampling sphere matlab visualization spin

The “converged” texture map looks like:
naive sampling sphere texture

Of course, a correct uniform sampling converges rather boringly to a uniformly black sphere.
uniform sampling sphere matlab visualization

In a different project we need not only a random sampling on the sphere, but also a Delaunay triangle mesh. Since all points lie on the sphere they also lie on their respective convex hull:

V = normalizerow(normrnd(zeros(sam,3),1));
F = convhulln(V);

The result looks something like this:
random delaunay mesh on sphere

OBJ reader, mesh viewer in browser with WebGL

Wednesday, April 10th, 2013

mesh in browser

I’m getting around to release source code and demos for my PhD projects and I thought it would be cool to try out writing those demos using WebGL. After toying around (for a few years now), I have a little proof of concept.

This little mesh viewer can load an .obj mesh file (just bare basics of the format) from (1) the remote server, (2) a selected file, or (3) a drag-and-drop file. Just drag an .obj file from your folder onto the viewer! For now there’s not much interface, just a simple zoom mechanism. But I’m going to build on this and keep updated the page.

The source code is heavily borrowed from around the web. See the .js sources.

Bounded biharmonic weights c++ demo for surfaces/volumes in 3d

Monday, December 24th, 2012

By popular demand I’ve created a quick-and-dirty 3d C++ demo of our paper “Bounded Biharmonic Weights for Real-time Deformation” [Jacobson et al. 2011].

The demo takes a mesh (.obj or .off) and a description of a skeleton (in my own ridiculous .bf and .tgf file formats) and computes a tetrahedral volume mesh using tetgen (saved to a .mesh file) and then computed bounded biharmonic weights for each handle over this mesh (save to my not-so-ridiculous .dmat file format).

This is a small program that illustrates how to compute Bounded Biharmonic Weights (BBW) for a given surface mesh and skeleton description. This only supports point handles and skeleton trees (bones). Cages are not supported. This program only computes and outputs the weight function values. You should be able to load them into matlab or maya or whatever.


First install the dependencies (e.g. mosek). If your on a mac, and why wouldn’t you be, then you *should* with any luck and by the grace of God be able to compile with:



Then run an example with (e.g.):

./bbw_demo examples/brick.obj examples/brick.tgf

This will produce at least 2 files:

  examples/brick-volume.mesh  Tetrahedral mesh over which weights were computed
  examples/brick-volume.dmat  Coefficients of weights defined over .mesh

File Formats

See file-formats/index.html

The dependencies are:


Igl lib

IGL_lib is our groups internal library. It will someday be publicly available, but not yet. Thus I only include here a bare minimum to get this demo to work. The library functions as an inlined header library. All the source is located in ./igl_lib/include/igl

Eigen3: The igl dependencies rely on a depracted version of the Sparse Matrix suite in eigen 3. Thus you need the correct version of eigen. To make this easier I have included the necessary version of eigen here: ./eigen3

Mosek: Mosek is free for academics and has its own installation instructions. Adjust your makefile accordingly.

Tetgen Tetgen is also free and easy to install. Be sure to compile the library version, i.e.:

make tetlib

To make life a little easier I include a working version of tetgen in ./igl_lib/external/tetgen/. You can go there and compile libtet.a or download the tetgen source and do that on your own. Whatever.

You can try to contact me with questions. Especially regarding the algorithm described in “Bounded biharmonic weights for real-time deformation” by [Jacobson et al. 2011]. However, please
try to solve compilation troubles on your own. I didn’t intend for this code to be machine independent or even necessarily easy to compile. This is a quick and dirty demo because so many people requested it.

Sometime in the not too distant future I still plan to release a *nice* 3d, C++ demo.

Update: I have updated this demo to use the libigl library. Please find the new version on the bbw project page.