## Posts Tagged ‘mesh’

### A Simple Method for Correcting Facet Orientations in Polygon Meshes Based on Ray Casting

Sunday, November 23rd, 2014

We’ve finally published our paper A Simple Method for Correcting Facet Orientations in Polygon Meshes Based on Ray Casting in the Journal of Computer Graphics Tools. The paper was written by Kenshi Takayama, Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung.

Abstract: We present a method for fixing incorrect orientations of facets in an input polygon mesh, a problem often seen in popular 3D model repositories, such that the front side of facets is visible from viewpoints outside of a solid shape represented or implied by the mesh. As opposed to previously proposed methods which are rather complex and hard to reproduce, our method is very simple, only requiring sampling visibilities by shooting many rays. We also propose a simple heuristic to handle interior facets that are invisible from exterior viewpoints. Our method is evaluated extensively with the SHREC Generic 3D Warehouse dataset containing 3168 manually designed meshes, and is demonstrated to be very effective.

You can find an implementation of this method in the embree extension of libigl: igl/embree/reorient_facets_raycast.h. If you store your mesh by its vertices in rows of a #V by 3 matrix V and triangle indices in the rows of a #F by 3 matrix F. Then you can quickly reorient your triangles to all point outward consistently with a single function call:

#include <igl/embree/reorient_facets_raycast.h>
...
Eigen::MatrixXI FF; // #F by 3 list of output triangle indices, some rows potentially reversed
Eigen::VectorXi I; // #F list of booleans revealing whether facet was reversed
igl::reorient_facets_raycast(V,F,FF,I);


As a preprocessor to our generalized winding numbers, this forms a powerful tool for determining the inside from outside for arbitrary meshes. This is especially important for creating volumetric tetrahedral meshes.

### 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
% 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');
tsurf(F,V)


### 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:

### 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;
A = uE2F'*uE2F;
% All ones
A = A>0;
% Connected components are patches
%C = components(A); % alternative to graphconncomp from matlab_bgl
[~,C] = graphconncomp(A);
end


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:

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

### 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:

trisurf(F,V(:,1),V(:,2),S);

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

tsurf(F,[V S]);


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]);


### 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 Finder.app.

Or when you use one of the fancier Finder.app views

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/Makefile.in from:

all: stamp-boost


to

all:


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:

((void)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');
patcht(F,V,F,[max(V(:,2))-V(:,2) V(:,1)],im);
axis equal


which produces:

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;
colormap(gray(255));
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)];
end
% 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));
set(s,'CData',matrixnormalize(im));
it = it + 1;
drawnow;
end


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

When this converges we can examine the bias around the sphere:

The “converged” texture map looks like:

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

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: