## Nested Cages project page

October 2nd, 2015

We’ve posted a project page for our upcoming SIGGRAPH Asia paper Nested Cages, a collaboration between Leonardo Sacht, Etienne Vouga and myself.

Abstract: Many tasks in geometry processing and physical simulation benefit from multiresolution hierarchies. One important characteristic across a variety of applications is that coarser layers strictly encage finer layers, nesting one another. Existing techniques such as surface mesh decimation, voxelization, or contouring distance level sets do not provide sufficient control over the quality of the output surfaces while maintaining strict nesting. We propose a solution that enables use of application-specific decimation and quality metrics. The method constructs each next-coarsest level of the hierarchy, using a sequence of decimation, flow, and contact-aware optimization steps. From coarse to fine, each layer then fully encages the next while retaining a snug fit. The method is applicable to a wide variety of shapes of complex geometry and topology. We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for elastic simulation, and cage-based geometric modeling.

## Accompanying video for “Nested Cages”, SIGGRAPH Asia 2015

September 22nd, 2015

Here’s the accompanying video for the upcoming SIGGRAPH Asia 2015 paper “Nested Cages” that I’ve been working on with Leonardo Sacht and Etienne Vouga:

Abstract:
Many tasks in geometry processing and physical simulation benefit from multiresolution hierarchies. One important characteristic across a variety of applications is that coarser layers strictly encage finer layers, nesting one another. Existing techniques such as surface mesh decimation, voxelization, or contouring distance level sets do not provide sufficient control over the quality of the output surfaces while maintaining strict nesting. We propose a solution that enables use of application-specific decimation and quality metrics. The method constructs each next-coarsest level of the hierarchy, using a sequence of decimation, flow, and contact-aware optimization steps. From coarse to fine, each layer then fully encages the next while retaining a snug fit. The method is applicable to a wide variety of shapes of complex geometry and topology. We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for elastic simulation, and cage-based geometric modeling.

You can find the paper on my site.

## CSG Tree operations in libigl

September 22nd, 2015

I’ve added support for constructive solid geometry tree operations in libigl. Check out igl::boolean::CSGTree and the tutorial entry.

The class constructors take advantage of C++ initializer lists to make tree encoding simple using a reverse polish encoding:

// Compute result of (A ∩ B) \ ((C ∪ D) ∪ E)
igl::boolean::CSGTree<MatrixXi> CSGTree =
{{{VA,FA},{VB,FB},"i"},{{{VC,FC},{VD,FD},"u"},{VE,FE},"u"},"m"};


September 9th, 2015

Here’s a little script demonstrating some of the fancy 3d-model rendering features you can squeeze out of MATLAB with a little effort. Stroking sharp edges and silhouettes and giving just the hint of transparency, you can achieve a CAD-style effect.

[V,F] = load_mesh('~/Dropbox/models/fandisk.off');
V = V*axisangle2matrix([1 0 0],pi);
N = normals(V,F);
BC = barycenter(V,F);

% sharp edges
A(1&A) = abs(A(1&A)-pi)>pi*0.11;
[CI,~,CV] = find(C.*A);
E = F([CI+mod(CV,3)*size(F,1) CI+mod(CV+1,3)*size(F,1)]);

% cut mesh at sharp edges to get crisp normals
[G,I] = cut_edges(F,E);
W = V(I,:);

% floor board
BB = bounding_box(V(:,1:2));
BB = bsxfun(@plus,bsxfun(@minus,BB,mean(BB))*2,mean(BB));
BB(:,3) = min(V(:,3))-4e-3;
BB = reshape(permute(BB,[1 3 2]),[2 2 3]);
% checkboard texture
ch = repmat(1-0.2*xor((mod(repmat(0:128-1,128,1),8*2)>7), ...
(mod(repmat((0:128-1)',1,128),8*2)>7)),[1 1 3])*0.5 + 0.5;

clf;
hold on;
blue = [0.2 0.3 0.8];
tf = tsurf(G,W, ...
'FaceVertexCData',repmat(blue,size(W,1),1), ...
'SpecularStrength',0, ...
'DiffuseStrength',0.1, ...
'AmbientStrength',1.0, ...
'EdgeColor','none','FaceAlpha',0.9,fphong);
te = tsurf(E(:,[1 2 2]),V,'EdgeColor',blue*0.75);
to = tsurf([1 1 1],V,'LineWidth',2,'EdgeColor',blue*0.5);
sc = surf(BB(:,:,1),BB(:,:,2),BB(:,:,3), ...
'CData',ch,'FaceColor','texturemap', ...
'SpecularStrength',0, 'DiffuseStrength',0, 'AmbientStrength',1);
view(130,38);
axis equal;
l = light('Position',[1 4 5.0],'Style','infinite');
% faint amient occlusion
AO = ambient_occlusion(W,G,W,per_vertex_normals(W,G),1000);
AO = AO*0.17;
tf.FaceVertexCData = bsxfun(@times,tf.FaceVertexCData,1-AO);
hold off;
axis vis3d;
camproj('persp');
set(gca,'Visible','off');
T = get(gca,'tightinset');
set(gca,'position',[T(1) T(2) 1-T(1)-T(3) 1-T(2)-T(4)]);

% Set up rotatation callbacks to hide view-dependent effects during drag
up = @() ...
set(to,'Faces', ...
outline(F((sum(N.*bsxfun(@minus,BC,campos),2)<=0),:))*[1 0 0;0 1 1]) | ...
set(h,'FaceAlpha',0.5*(g*[campos 1]'<0)) | ...
set(sc,'FaceAlpha',1.0*(g*[campos 1]'<0));
up();
down = @() set(to,'Faces',[]);
set(rotate3d,'ActionPostCallback',@(src,obj) up());
set(rotate3d,'ActionPreCallback',@(src,obj) down());

for t = linspace(0,-360,60)
view(64+t,20);
up();
drawnow;
end


Update: It even looks reasonable for less artificial shapes, though perhaps the hard edges just accidentally look fuzzy like fur:

## Append rows and columns of zeros to sparse matrix, but only if they don’t already exist

September 3rd, 2015

Analogous to the trick for dense matrices, here’s a way to add more empty rows and columns to sparse matrix, but only if they don’t already exist. This happens to me often when dealing with meshes that might have unreferenced vertices. For example, if I build the adjacency matrix of a mesh (V,F):

A = adjacency_matrix(F);


the size will be max(F(:)) by max(F(:)), so if there’s an unreferenced vertex with index greater than max(F(:)) I’ll run into trouble. A rather verbose inelegant way to solve this is:

n = size(V,1);
A = [A sparse(size(A,1),n - size(A,2));sparse(n - size(A,1),n)];


But here’s a cute way to do it with far fewer characters:

A(end+1:n,end+1:n) = 0;


## Re-order id3 track numbers of multi-disc audiobook

September 3rd, 2015

Yesterday I was floundering trying to get iTunes and the iPhone iBook app to iFunctionCorrectly. I have an audiobook composed of multiple mp3s ripped from multiple cds. The track names look like:

1-01-madame-bovary-1a.mp3
...
...
...


This is already unfortunate because lexicographically they sort to:

1-01-madame-bovary-1a.mp3
...
...
...


iTunes deals with this reasonably well. The bigger problem was the id3 tags of these files. All files had the same artist and album.

1-01-madame-bovary-1a.mp3
...


had track numbers 1/30, 2/30, 3/30 etc. and all had part number 1/11 (part 1 of an 11 part set). However, iBook refused to sort these by part number then track number. Instead, only sorting by track number, getting this:

1-01-madame-bovary-1a.mp3
...
...
...


I tried converting everything into a single giant mp3 file using ffmpeg:

ls *.mp3 | sort -n | sed -e "s/^$.*$$/file '\1'/" > concat.txt ffmpeg -f concat -i concat.txt -y -vn -acodec copy -threads 3 madame-bovary.mp3  or a single m4b file: ffmpeg -f concat -i concat.txt -y -vn -acodec libfaac -ab 64k -ar 44100 -threads 3 -f mp4 madame-bovary.m4b  but these files were 900MB and 350MB and iBooks seems to choke on that size. Finally, my solution is to re-order all of the track numbers to increment across parts. I achieved this with a little bash script, I saved in track_number_explode.sh #!/bin/bash USAGE="track_number_explode [path to directory of mp3s]" if [ -z "$1" ]; then
echo "Usage: $USAGE" exit 1 fi OLD_DIR=$(pwd)
cd "$1" MP3S=$(ls *.mp3 | sort -n)
N=$(echo -e "$MP3S" | wc -l)
# cheap way to clear leading spaces
N=$((N+0)) T="1" SAVEIFS=$IFS
IFS=$(echo -en "\n\b") for mp3 in$MP3S; do
id3v2 --id3v2-only -T "$T/$N" "$mp3" # strip id3.1 as it can handle large track numbers id3v2 -s "$mp3" &>/dev/null
T=$((T+1)) done IFS=$SAVEIFS
cd "\$OLD_DIR"


Then I run this on the directory containing my mp3s

track_number_explode.sh madame-bovary/


Finally I load these onto the iPhone, select all of them, right-click and choose Get Info > Options and set media kind to Audiobook.

## Memory gotcha in eigen

August 26th, 2015

I recently ran into a frustrating memory leak “gotcha” involving Eigen. The following code compiles

template <typename Derived>
Eigen::PlainObjectBase<Derived> leaky(
const Eigen::PlainObjectBase<Derived> & A)
{
Derived B = A;
return B;
}

int main(int argc, char * argv[])
{
Eigen::MatrixXd A(10000,1);
Eigen::MatrixXd B = leaky(A);
}


but causes a memory leak (without any warnings/asserts from Eigen):

.main(33789,0x7fff7bb2d300) malloc: *** error for object 0x7f9ed188da00: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug


The problem seems to be the cast happening in the return. Changing the return type of leaky to Derived:

template <typename Derived>
Derived leaky(
const Eigen::PlainObjectBase<Derived> & A)


fixes the issue. Or it could be fixed by changing the type of B inside leaky to Eigen::PlainObjectBase<Derived>.

  Eigen::PlainObjectBase<Derived> B = A;


## Bounded biharmonic weights demo binary

August 13th, 2015

I’ve finally gotten around to creating a stand-alone mac os x app for the prototype I use to give demos of our bounded biharmonic weights. The only catch is that you’ll have to grab a mosek (free academic trial) license and put it in the right place

Unfortunately do to license reasons I cannot release the source code for this app, but the code for bounded biharmonic weights is in my matlab gptoolbox and in our C++ libigl

## Slice, rearrange and extract output arguments of matlab function

August 6th, 2015

It is a bit annoying how matlab handles anonymous functions an output arguments. Suppose there’s a function called solver that expects to be pass a function handle fval and grad that compute the value and the gradient of some function at point X respectively. Then you’d call solver like this:

Z = solver(@fval,@grad);


Well, suppose I already have a function grad_fval that computes the gradient and function value at some point X, as in:

[G,f] = grad_fval(X);


It’s easy to create an anonymous function to compute the gradient:

grad = @(X) grad_fval(X);


But since anonymous functions can only have one line and the output must match it’s impossible to extract the second output argument from grad_fval. I guess the official way to do this is to create a file on my hard drive in the current path, say called fval.m and give it the contents:

function f = fval(X)
end


This is pretty silly.

Instead, I’ve created a one-off utility function slice_argout.m which is similar to a lot of get_the_nth_output functions found online. Only here I use the matlab-style slicing to enable full manipulation of the output arguments. In the case above I’d use:

fval = @(X) slice_argout(@grad_fval,[2],X);


If I wanted to reverse the output arguments I could use:

fval_grad = @(X) slice_argout(@grad_fval,[2 1],X);


Here’re the contents of slice_argout.m:

function varargout = slice_argout(func,order,varargin)
% SLICE_ARGOUT Slice (permute, reorder, extract blocks from, etc.) output
% arguments of a given function.
%
% [O1,O2,O3,...] = slice_argout(func,order,I1,I2,I3, ...)
%
% Calling this is effectively the same as calling:
%
%     [T1,T2,T3,...] = func(I1,I2,I3,...)
%
%
if islogical(order)
n = numel(order);
else
n = max(order(:));
end
varargout = cell(n,1);
[varargout{:}] = func(varargin{:});
varargout = varargout(order);
end


August 5th, 2015

Here’s what I added to the wp-admin/admin-header.php file of my wordpress site to re-typeset the preview of the latex-math as I type into the post editor:

<script>
function()
{
// http://stackoverflow.com/a/4029518/148668
var idleTime = 0;
// Increment every 100 millisecond
setInterval(timerIncrement, 100);
function timerIncrement()
{
idleTime+=100;
if(idleTime>1000)
{
idleTime=0;
if(MathJax.Hub.queue.running == 0 && MathJax.Hub.queue.pending == 0)
{
MathJax.Hub.Typeset();
}
}
}

document.getElementById("content").onkeypress =
function(e)
{
idleTime = 0;
};
},false);
</script>
`