Posts Tagged ‘gptoolbox’

Paper-worthy rendering in MATLAB

Thursday, July 20th, 2017

MATLAB is not a great tool for creating 3D renderings. However, the learning curves for most commercial rendering tools are quite steep. Other tools like Mitsuba can create beautiful pictures, but can feel quite cumbersome for rendering pure geometry rather than the physical scenes their designed for.

Over the years, I’ve developed a way of creating plots of 3D shapes in MATLAB using a few extra functions in gptoolbox. This started as a way to just make images from research prototypes more palatable, but eventually became the usual way that I render images for papers. If the code for my research is already written in MATLAB then one huge advantage is that every image in my paper can have a *.m script that deterministically generates the result and the corresponding image with user intervention. This helps with reproducibility, editing and sharing between collaborators.

Here’s a “VFX Breakdown” of rendering a 3D shape in MATLAB.

t = tsurf(F,V);
set(gcf,'COlor',0.94*[1 1 1]);
teal = [144 216 196]/255;
pink = [254 194 194]/255;
bg_color = pink;
fg_color = teal;
for pass = 1:10
  switch pass
  case 1
    % blank run
    axis([-209.4       119.38      -181.24       262.67      -247.28 247.38]);
  case 2
    axis equal;
    axis([-209.4       119.38      -181.24       262.67      -247.28 247.38]);
    axis vis3d;
  case 3
    t.EdgeColor = 'none';
  case 4
    set(t,fphong,'FaceVertexCData',repmat(fg_color,size(V,1),1));
  case 5
    set(t,fsoft);
  case 6
    l = light('Position',[0.2 -0.2 1]);
  case 7
    set(gca,'Visible','off');
  case 8
    set(gcf,'Color',bg_color);
  case 9
    s = add_shadow(t,l,'Color',bg_color*0.8,'BackgroundColor',bg_color,'Fade','infinite');
  case 10
    apply_ambient_occlusion(t,'AddLights',false,'SoftLighting',false);
  end

  vidObj = VideoWriter(sprintf('nefertiti-%02d.mp4',pass),'MPEG-4');
  vidObj.Quality = 100;
  vidObj.open;
  thetas = linspace(30,-30,450);
  for theta = thetas(1:end-1)
    view(theta,30);
    drawnow;
    vidObj.writeVideo(getframe(gcf));
  end
  vidObj.close;

end

Inflate Wire Mesh in libigl C++ or gptoolbox MATLAB

Wednesday, July 12th, 2017

For a visualization and 3D printing, it’s often useful to “inflate” a edge-network into a thickened surface mesh. One method to do this is described “Sculptural Forms from Hyperbolic Tessellations” by George C Hart. This method works by adding rotated polygons at the ends of each edge offset a bit from the vertices. Then for each vertex the convex hull of incident edges’ polygons is computed and unioned with the convex hull of the polygons at either end of each edge. Hart writes that polygons shared by “edge hulls” and “vertex hulls” can simply be discarded. This is unfortunately not true, in general. It’s not super easier to categorize which faces can be discarded (even in general position) since the answer depends on the thickness, the number of sides of the polygons, their rotations, their offsets, and the angle between neighbouring edges. Fortunately, libigl is very good at conducting unions. We can just conduct the union explicitly and exactly using libigl.

I’ve written a new function for libigl igl::wire_mesh that takes in a wire network and spits out a solid (i.e., closed, watertight, manifold) mesh of a the inflated surface.

I’ve also wrapped this up in a Matlab Mex function in gptooolbox wire_mesh.

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

bunny with positive offset surface

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

bunny with positive offset surface

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');
add_shadow(t,l,'Color',0.8*[1 1 1],'Fade','local','Ground',[0 0 -1 min([V(:,3);SV(:,3)])]);
set(gca,'pos',[0 0 1 1])
set(gca,'Visible','off');
set(gcf,'Color','w');
drawnow;

Quad meshing in matlab using gptoolbox

Friday, February 17th, 2017

This morning I played around with a very simple way of quad meshing a triangle mesh. This is more or less the “ideal pipeline” for quad meshing via parameterization. It will likely only work for very simple meshes. I’m pleasantly surprised that it works at all.

% Load a mesh with boundary and no topological (donut) holes
[V,F] = load_mesh('~/Dropbox/models/beetle.off');
V = V*axisangle2matrix([1 0 0],-pi/2);
% Construct the LSCM matrix
[~,Q] = lscm(V,F,[],[]);
M = massmatrix(V,F);
% Use Fiedler vector as parameterization
[EV,ED] = eigs(Q,repdiag(M,2),5,'sm');
U = reshape(EV(:,end-3),[],2);
% try to find "canonical" rotation
[sU,sS,sV] = svd(U'*U);
U = U*sU;
% Lay down a grid in 2D
h = ((max(U(:,1))-min(U(:,1)))/(160-2));
[X,Y] = meshgrid(min(U(:,1))-h:h:max(U(:,1))+h,min(U(:,2))-h:h:max(U(:,2))+h);
% Find all quads that are strictly inside the parameterized mesh
[QQ,QU] = surf2patch(X,Y,0*Y);QU = QU(:,1:2);
[sqrD,I,C] = signed_distance([QU QU(:,1)*0],[U U(:,1)*0],F);
QQ = QQ(all(abs(sqrD(QQ))<1e-10,2),:);
[QU,I] = remove_unreferenced(QU,QQ);
QQ = fliplr(I(QQ));
% Snap boundary vertices of quad mesh to boundary of mesh, and
% solve little Dirichlet problem to diffuse the displacements smoothly
QF = [QQ(:,[1 2 3]);QQ(:,[1 3 4])];
L = cotmatrix(QU,QF);
b = unique(outline(QQ));
[~,~,QU(b,:)] = point_mesh_squared_distance(QU(b,:),U,outline(F));
QU = min_quad_with_fixed(-L,[],b,QU(b,:));
% Locate each quad mesh vertex in the parameterized mesh
[sqrD,I,C] = signed_distance([QU QU(:,1)*0],[U U(:,1)*0],F);
B = barycentric_coordinates(C(:,1:2),U(F(I,1),:),U(F(I,2),:),U(F(I,3),:));
% Interpolate 3D positions at quad mesh vertex locations
QV = V(F(I,1),:).*B(:,1) + V(F(I,2),:).*B(:,2) + V(F(I,3),:).*B(:,3);

To create the image above use:

clf;
hold on;
tq = tsurf(QQ,QV,'FaceVertexCData',repmat(blue,size(QV,1),1),'EdgeColor','none',fsoft,fphong);
tt = tsurf(F,V-[0.8 0 0],'FaceVertexCData',repmat(1-0.8*(1-blue),size(V,1),1),'EdgeAlpha',0.5,fsoft,fphong);
axis equal;
camproj('persp');
view(-38,17);
drawn;
camlight;
plot_edges(QV,[QQ(:,2:3);QQ(:,[4 1])],'Color',orange);
plot_edges(QV,[QQ(:,1:2);QQ(:,3:4)],'w');hold off;
l = light('Position',[-10 0 10],'Style','infinite');
sq = add_shadow(tq,l,'Fade','infinite','Color',[0.8 0.8 0.8]);
st = add_shadow(tt,l,'Fade','infinite','Color',[0.8 0.8 0.8]);
set(gca,'Visible','off');
set(gcf,'Color','w');

There’s a lot to improve about the quad mesh: the boundaries are not aligned with the meshing direction, the meshing directions are not always aligned with principle curvature, etc. Not bad for 30 mins of coding using tools that are just lying around.

Plot a bunch of edges in matlab with per-edge color data

Monday, December 19th, 2016

Suppose you have a list of vertices V (#V by dim) and a list of edges E (#E by 2) indexing V, then one hacky to draw all of these edges with per-vertex color data DV (#V by 1) is to use trisurf:

trisurf(E(:,[1 1 2]),V(:,1),V(:,2),V(:,3),'CData',DV,'EdgeColor','interp');

However, if you try to use this trick to draw per-edge color data DE (#E by 1), you’ll find that 'EdgeColor','flat' does not work. Instead you can explode you compact “mesh” of edges into individual edges and repeat you edge color data for each edge point:

trisurf(reshape([1:size(E,1),1:size(E,1)*2],[],3),V(E(:),1),V(E(:),2),V(E(:),3),'CData',repmat(DE,2,1),'EdgeColor','interp');

Mesh Arrangements for Solid Geometry preprint

Thursday, April 21st, 2016

mesh booleans

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:

four spheres variadic boolean operation

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)

Boolean operations using generalized winding numbers

Tuesday, February 2nd, 2016

booleans using generalized winding number

I posted a little tech report about how to use the generalized winding number for constructive-solid geometry (CSG) style boolean operations (union, intersection, difference etc.) on nasty meshes.

Code implementing this has existed for a little while now in the mesh_boolean_winding_number function of gptoolbox.

Conservative voxelization in gptoolbox

Tuesday, November 3rd, 2015

A while ago I implemented a function to voxelize a given triangle mesh in matlab as part of gptoolbox. Rather than use 3D-Bresenham-style rasterization, I needed a conservative voxelization: where every point (not just vertex) on the mesh is contained inside the voxelization. In other words, output all voxels that intersect the triangle mesh.

Here’s a little snippet to produce the following meshes:

for k = [10 20 40 80]
  [W,BC,DV,Q] = voxelize(V,F,k,'Pad',1);
  [DV,I] = remove_unreferenced(DV,Q);
  Q = I(Q);
  d = render_in_cage(V,F,DV,Q,'ColorIntersections',false);
  d.tc.LineWidth = 2;
end

big alien model voxelized
big alien model voxelized
big alien model voxelized
big alien model voxelized

Mesh decimation (aka simplification) in matlab

Thursday, October 15th, 2015

I’d forgotten that I’d discovered that matlab has a built-in function for triangle mesh simplification: reduce_patch. Here’s a little comparison between this method and the ones I’ve wrapped up in gptoolbox.

Input mesh

Given an input mesh with vertices V and faces F (this elephant has 14732 faces):

cartoon-elephant-input.gif

Built-in matlab reduce patch

We can decimate the mesh to 1000 faces using pure built-in matlab:

[mF,mV] = reducepatch(F,V,1000);

cartoon-elephant-decimated-matlab.gif

Notice that it’s a rather adaptive remeshing. There aren’t (m)any options for controlling reducepatch, just the 'fast' flag, but in this case it will produce an identical output.

Libigl’s decimate

Libigl has a framework for edge-collapse decimation on manifold meshes and a default setting for regular meshing:

[iV,iF] = decimate_libigl(V,F,1000);

cartoon elephant decimated libigl

CGAL’s decimation

I have a wrapper for CGAL’s decimation algorithms. These can result in a regular remeshing with 1000 faces:

[c1V,c1F] = decimate_cgal(V,F,1000/size(F,1));

cartoon-elephant-decimated-cgal-regular.gif

or an adaptive meshing:

[c2V,c2F] = decimate_cgal(V,F,1000/size(F,1),'Adaptive',true);

cartoon-elephant-decimated-cgal-adaptive.gif

CGAL has a fairly general interface for an edge-collapser, but these are the only metrics provided by default from CGAL.

QSlim

cartoon-elephant-decimated-qslim.gif

Timing

Suppose my original elephant had 3.7 million faces instead of just 14K, how do these methods measure up when reducing to 1000 faces:

Method Time
reducepatch 64.4s
libigl 74.56s
cgal (regular) 117.7s
cgal (adaptive) 214.8s
qslim 108.0s + 507.5s + 59.4s

My qslim wrapper is currently very silly. It’s calling qslim as an executable and then reading in the entire collapse log and conducting the collapse within matlab (the second time is for reading the log, the third for conducting the collapse).

None of these methods guarantee that the result is self-intersection free. I’ve noticed that qslim and matlab will create non-manifold meshes from manifold inputs. The current libigl implementation should not creative non-manifold output, but assumes the input is a closed surface. For casual decimation, it seems like matlab’s reducepatch and libigl’s decimate_libigl are the best bets for speedy adaptive and regular meshing respectively. Conveniently they also require the least in terms of dependencies.