Posts Tagged ‘mesh’

Triangle mesh for image as surface

Sunday, October 26th, 2014

Here’s a little chuck of matlab code I use to make a surface mesh out of an image:

% load image as grayscale
im = rgb2gray(imresize(im2double(imread('hans-hass.jpg')),0.75));
% create triangle mesh grid
[V,F] = create_regular_grid(size(im,2),size(im,1),0,0);
% Scale (X,Y) to fit image
V(:,1) = V(:,1)*size(im,2);
V(:,2) = (1-V(:,2))*size(im,1);
V(:,3) = im(:);

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.