Posts Tagged ‘mesh’

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

Sunday, November 23rd, 2014

correct facet orientations on a bike, cell phone, chair, and truck

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

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:

selfintersections

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

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:

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

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

Mesh quicklook preview

Or when you use one of the fancier Finder.app 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

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');
[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

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