Archive for September, 2015

Accompanying video for “Nested Cages”, SIGGRAPH Asia 2015

Tuesday, 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

Tuesday, 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"};

CSG tree operations in libigl

CAD-style rendering in matlab

Wednesday, 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.

cad-style rendering in matlab

[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,C] = adjacency_dihedral_angle_matrix(V,F);
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');
[h,~,~,g] = add_shadow(tf,l,'Nudge',2e-3,'Fade','local','Color',[0.8 0.8 0.8]);
% 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;
  figgif('fan-disk-matlab-cad-rendering.gif');
end

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

bunny cad style matlab

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

Thursday, 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

Thursday, 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
1-02-madame-bovary-1b.mp3
1-03-madame-bovary-1c.mp3
...
2-01-madame-bovary-2a.mp3
2-02-madame-bovary-2b.mp3
2-03-madame-bovary-2c.mp3
...
11-01-madame-bovary-11a.mp3
11-02-madame-bovary-11b.mp3
11-03-madame-bovary-11c.mp3
...

This is already unfortunate because lexicographically they sort to:

1-01-madame-bovary-1a.mp3
1-02-madame-bovary-1b.mp3
1-03-madame-bovary-1c.mp3
...
11-01-madame-bovary-11a.mp3
11-02-madame-bovary-11b.mp3
11-03-madame-bovary-11c.mp3
...
2-01-madame-bovary-2a.mp3
2-02-madame-bovary-2b.mp3
2-03-madame-bovary-2c.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
1-02-madame-bovary-1b.mp3
1-03-madame-bovary-1c.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
2-01-madame-bovary-2a.mp3
...
11-01-madame-bovary-11a.mp3
1-02-madame-bovary-1b.mp3
2-02-madame-bovary-2b.mp3
11-02-madame-bovary-11b.mp3
...
1-03-madame-bovary-1c.mp3
2-03-madame-bovary-2c.mp3
11-03-madame-bovary-11c.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.