Archive for January, 2013

New ETHZ masters thesis project available: Make Me Dance!

Tuesday, January 29th, 2013

Make me dance! eth masters project

Jean-Charles Bazin, Tiberiu Popa, Markus Gross and I will be hosting a master’s thesis project. The project, entitled Make Me Dance, is now available, and we are eagerly awaiting applications.

The topic of the thesis is simple to explain: you would like to dance like Lady Gaga or Michael Jackson but your dancing skills are not great. The goal is to virtually improve your dancing skills: given a video of you (or anyone else) dancing, the project aims to process and manipulate the video, in an automatic manner, so that your “upgraded” dance looks like the one of the dancer of your choice (e.g. Lady Gaga or Michael Jackson).

Task Description: To reach this goal, several approaches from computer vision and computer graphics will be investigated and combined. For example you will use Microsoft’s Kinect to get a depth map and a human skeleton. Given your estimated skeleton and the target pose of the professional dancer, you will apply some character animation techniques. Finally you will map the texture onto the 3D human model to create a realistic video in which your dance moves now matches the ones of the professional dancer.

Please don’t hesitate to contact me for more details.

Also, check out the full list of IGL projects.

Note: You will need to be at an ETH IP address to visit these links.

New ETHZ masters thesis project available: Content-Aware 3D Navigation with a 2D Mouse

Tuesday, January 29th, 2013

Content-Aware 3D Navigation with a 2D Mouse

Olga Sorkine and I will be hosting a master’s thesis project. The project, entitled Content-Aware 3D Navigation with a 2D Mouse is now available, and we are eagerly awaiting applications.

In recent years, many 3D input devices have emerged: 3D mice, haptic pens, hand-tracking gloves. But the ubiquitous 2D mouse isn’t going away any time soon! Here we consider the problem of navigating in a virtual 3D environment with a 2D mouse. Navigation should rely on intuitive and simple gestures, realizable with a standard, single-button mouse. The unprojected 3D-coordinates should respond to the content of the virtual 3D scene without the user needing to change the camera position.

In this thesis, the student will explore user-interface design and 2D mouse gesture recognition in order to build a system that allows easy 3D navigation of complex scenes with a standard 2D mouse. Such navigation is necessary for path design, object placement, object selection, and keyframing for animation. The resulting system will be tested with novice and expert users to scientifically evaluate its effectiveness.

Please don’t hesitate to contact me for more details.

Also, check out the full list of IGL projects.

Note: You will need to be at an ETH IP address to visit these links.

New ETHZ masters thesis project available: Optimizing Bounded Biharmonic Weights Computation

Tuesday, January 29th, 2013

optimizing bounded biharmonic weights computation eth masters project

Olga Sorkine and I will be hosting a master’s thesis project. The project, entitled Optimizing Bounded Biharmonic Weights Computation is now available, and we are eagerly awaiting applications.

Bounded biharmonic weights (BBW) are compactly supported, smooth functions defined over a 2D or 3D shape. Their primary use is for blending transformations to achieve shape deformation in real time. However, computing them requires optimizing a quadratic program (QP) over a finite-element discretization of the shape’s volume. This is costly (~minutes) and limits applications to those where it is acceptable to precompute such weights once and reuse them. Dynamically adapting BBWs by recomputing them interactively would greatly enhance its list of applications: physically-based simulation, interactive modeling, even many-to-many image registration.

In this thesis, the student will explore algorithmic and pragmatic optimization of the computation of bounded biharmonic weights. Current solutions lean on black-box QP solvers, which do not take advantage of the geometry-specific and problem-specific nature of the BBW energy minimization problem. We will explore algorithmic and data-structure optimizations such as multi-resolution hierarchies (both geometric and algebraic). Then we will explore performance optimizations that make the most of modern multi-core SIMD CPUs.

Please don’t hesitate to contact me for more details.

Also, check out the full list of IGL projects.

Note: You will need to be at an ETH IP address to visit these links.

Empty trash without Preview (secretly) blocking

Thursday, January 24th, 2013

I run into this problem all the time. Even though Preview.app is not open, when I empty the trash I get warnings like:


The operation can't be completed because the item "some.pdf" is in use.

I’m not sure how it happens. But it seems some instance of Preview continues to run even after quitting or force quitting. I found this out by issuing:


sudo lsof ~/.Trash/some.pdf

This showed:


COMMAND   PID USER   FD   TYPE DEVICE SIZE/OFF    NODE NAME
Preview 73409  ajx  txt    REG   14,2 18966290 4989399 /Users/ajx/.Trash/some.pdf

Then I knew to issue:


kill 73409

Then I could empty the trash with no errors.

Citing CGAL or other software using acmsiggraph.bst bibtex style

Monday, January 14th, 2013

CGAL suggests that you use the following bibtex record:

@misc{cgal,
  title = "\textsc{Cgal}, {C}omputational {G}eometry {A}lgorithms {L}ibrary",
  note  = "http://www.cgal.org"
}

But the acmsiggraph.bst style creates citations that look like:

[cga ]

To fix this I use a slightly different bibtex record:

@misc{cgal,
  key = {CGAL},
  title = "\textsc{Cgal}, {C}omputational {G}eometry {A}lgorithms {L}ibrary",
  note  = "http://www.cgal.org"
}

And changed the lines in acmsiggraph.bst that look like:

FUNCTION {author.key.label}
{ author empty$
    { key empty$
        { cite$ #1 #3 substring$ }
        { key #3 text.prefix$ }
      if$
    }
    { author format.lab.names }
  if$
}

to


    FUNCTION {author.key.label}
    { author empty$
        { key empty$
            { cite$ #1 #3 substring$ }
            % Alec: use full key
            { key }
          if$
        }
        { author format.lab.names }
      if$
    }

FUNCTION {author.key.label}
{ key empty$
  { author empty$
    { cite$ #1 #3 substring$ }
    { author format.lab.names }
      if$
  }
  % Alec: use full key
  { key }
  if$
}

and the lines that look like:

  year empty$
  {
    "\protect\citename{" swap$ * " }" *
    "" * 'label :=
  }

to

  year empty$
  {
    % Alec: rm space after name if no year
    "\protect\citename{" swap$ * "}" *
    "" * 'label :=
  }

Now my citation looks like:

[CGAL]

Reverse engineering matlab’s jet function into a function of x

Sunday, January 13th, 2013

Here are some anonymous functions to act like matlab’s jet function for building colormaps. Here I return the R,G,B values for a given parameter value between [0,1].


R = @(x) (x<3/8).*0 + (x>=3/8 & x<5/8).*(x-3/8)./(5/8-3/8) + (x>=5/8 & x<7/8).*1 + (x>=7/8).*(1-(x-7/8)./(1-7/8).*0.5);
G = @(x) (x<1/8).*0 + (x>=1/8 & x<3/8).*(x-1/8)./(3/8-1/8) + (x>=3/8 & x<5/8).*1 + (x>=5/8 & x<7/8).*(1-(x-5/8)./(7/8-5/8)) + (x>7/8).*0;
B = @(x) (x<1/8).*(0.5+(x)./(1/8).*0.5) + (x>=1/8 & x<3/8).*1 + (x>=3/8 & x<5/8).*(1-(x-3/8)./(5/8-3/8)) + (x>5/8).*0;

Test it with:


x = linspace(0,1,1024);
plot(x,jet(numel(x)),x,[R(x);G(x);B(x)],'--','LineWidth',3);

Note: This will only match jet’s output for large m: jet(m).

Consistent (tet) mesh neighbor information

Thursday, January 10th, 2013

I’ve been using tet mesh from a matlab interface I wrote. It produces a list of tet indices, I call TT in matlab, where each row is a four-tuple of tet indices. It can also output a .neigh file which contains a list of each tet’s neighbor by index. I call this TN in matlab. This is also a list of rows of four, when now a positive index of j on row i means that tet i is a neighbor with tet j. Neighboring means sharing a face. Sharing a face means tet i and tet j have 3 indices in common.

One would expect that these come in a consistent ordering. For example, if j appears as the kth element on row i, then I might expect tet j to be the “kth neighbor” of tet i. So if k=3 I expect that tet i shares the face opposite its kth vertex (kth column in TT).

Doch leider ist es nicht wahr. (actually it is, see below).

Instead it seemed that tetgen was using a different ordering. To find out which consistent ordering scheme it was using I wrote a little script:


TE = [repmat(1:size(TT,1),1,size(TT,2))' TN(:)];
% verify edges are symmetric
A = sparse(TE(TE(:,2)>0,1),TE(TE(:,2)>0,2),1);
assert(size(A,1)==size(A,2));
assert(max(max(A'-A))==0);

all_perms = perms(1:4);
% loop over all perms
for p = 1:size(all_perms,1)
  TI = [T(:,[2 3 4]); T(:,[3 4 1]); T(:,[4 1 2]); T(:,[1 2 3])];
  TI = [ ...
    T(:,all_perms(p,[2 3 4])); ...
    T(:,all_perms(p,[3 4 1])); ...
    T(:,all_perms(p,[4 1 2])); ...
    T(:,all_perms(p,[1 2 3]))];
  A = sparse(TE(TE(:,2)>0,1),TE(TE(:,2)>0,2),sum(TI(TE(:,2)>0),2));
  fprintf('%d: %d\n',p,full(max(max(abs(A-A')))));
  if max(max(abs(A-A'))) == 0
    % found it
    break;
  end
end

First I do a little sanity check to make sure that tet’s agree that they are neighbors. Then I consider every (4! = 24) possible consistent ordering of tets by checking whether their shared faces agree.

But again! Foiled. Tetgen seems to output neighbors in an inconsistent manner. To resolve this I wrote another small script:


% Get rid of boundary edges
TE = TE(TE(:,2)>0,:);
TNI = zeros(size(TE,1),1);
for c = 1:size(TT,2)
  [TNIc] = all(~bsxfun(@eq,TT(TE(:,1),c),TT(TE(:,2),:)),2);
  % Assert face-manifoldness
  assert(all(TNI(TNIc) == 0));
  TNI(TNIc) = c;
end
% Assert that edges correspond to face sharers
assert(all(TNI>0));
% Rebuild TN
new_TN = full(sparse(TE(:,1),TNI,TE(:,2),size(TN,1),size(TN,2)));
new_TN(new_TN==0) = -1;

As a consequence the first script can be used to check for a consistent ordering and the second script can be used to check for face-manifoldness and correct neighbor relations.

Update: Turns out tetgen was fine and I had a bug. I was reordering the columns in my TT, without reordering the columns in TN. But these scripts did help me find and eliminate my bug!

C++ gotcha: test bool against bit logic

Wednesday, January 9th, 2013

I tried to do:


bool v;
...
if( v != (my_bits & MASK) )
{
  my_bits ^= MASK;
}

and was surprised to find out that this failed to do what I expected it to: if the truth of v matches the truth of the statement (my_bits masked with MASK) then toggle my_bits according to MASK.

I guess the root of the problem is that bool is not really a byte, so I’m not comparing true/false to true/false, but rather [bit expression for zero]/[bit expression for one] to (my_bits & MASK).

My fix was to change the if statement to:


if(v != (0!=(my_bits & MASK))

which at least semantically still makes sense.

undef min, define min macro ruins sstream

Wednesday, January 9th, 2013

Depending on my header include order I got a large amount of errors from sstream:


In file included from /opt/local/include/gcc47/c++/istream:873:0,
                 from /opt/local/include/gcc47/c++/sstream:39,
                 from medit.h:69,
                 from ellipse.c:1:
/opt/local/include/gcc47/c++/bits/istream.tcc: In member function 'std::streamsize std::basic_istream<_CharT, _Traits>::readsome(std::basic_istream<_CharT, _Traits>::char_type*, std::streamsize)':
/opt/local/include/gcc47/c++/bits/istream.tcc:693:46: Error: error: expected unqualified-id before '(' token
In file included from /opt/local/include/gcc47/c++/sstream:581:0,
                 from medit.h:69,
                 from ellipse.c:1:
/opt/local/include/gcc47/c++/bits/sstream.tcc: In member function 'virtual std::basic_stringbuf<_CharT, _Traits, _Alloc>::int_type std::basic_stringbuf<_CharT, _Traits, _Alloc>::overflow(std::basic_stringbuf<_CharT, _Traits, _Alloc>::int_type)':
/opt/local/include/gcc47/c++/bits/sstream.tcc:112:39: Error: error: expected unqualified-id before '(' token
/opt/local/include/gcc47/c++/bits/sstream.tcc:114:35: Error: error: expected unqualified-id before '(' token
In file included from /opt/local/include/gcc47/c++/istream:873:0,
                 from /opt/local/include/gcc47/c++/sstream:39,
                 from medit.h:69,
                 from gisfil.c:1:
/opt/local/include/gcc47/c++/bits/istream.tcc: In member function 'std::streamsize std::basic_istream<_CharT, _Traits>::readsome(std::basic_istream<_CharT, _Traits>::char_type*, std::streamsize)':
/opt/local/include/gcc47/c++/bits/istream.tcc:693:46: Error: error: expected unqualified-id before '(' token
In file included from /opt/local/include/gcc47/c++/istream:873:0,
                 from /opt/local/include/gcc47/c++/sstream:39,
                 from medit.h:69,
                 from geometry.c:1:
/opt/local/include/gcc47/c++/bits/istream.tcc: In member function 'std::streamsize std::basic_istream<_CharT, _Traits>::readsome(std::basic_istream<_CharT, _Traits>::char_type*, std::streamsize)':
/opt/local/include/gcc47/c++/bits/istream.tcc:693:46: Error: error: expected unqualified-id before '(' token
make: *** [dlists.o] Error 1
In file included from /opt/local/include/gcc47/c++/sstream:581:0,
                 from medit.h:69,
                 from geometry.c:1:
/opt/local/include/gcc47/c++/bits/sstream.tcc: In member function 'virtual std::basic_stringbuf<_CharT, _Traits, _Alloc>::int_type std::basic_stringbuf<_CharT, _Traits, _Alloc>::overflow(std::basic_stringbuf<_CharT, _Traits, _Alloc>::int_type)':
/opt/local/include/gcc47/c++/bits/sstream.tcc:112:39: Error: error: expected unqualified-id before '(' token
/opt/local/include/gcc47/c++/bits/sstream.tcc:114:35: Error: error: expected unqualified-id before '(' token
In file included from /opt/local/include/gcc47/c++/sstream:581:0,
                 from medit.h:69,
                 from gisfil.c:1:
/opt/local/include/gcc47/c++/bits/sstream.tcc: In member function 'virtual std::basic_stringbuf<_CharT, _Traits, _Alloc>::int_type std::basic_stringbuf<_CharT, _Traits, _Alloc>::overflow(std::basic_stringbuf<_CharT, _Traits, _Alloc>::int_type)':
/opt/local/include/gcc47/c++/bits/sstream.tcc:112:39: Error: error: expected unqualified-id before '(' token
/opt/local/include/gcc47/c++/bits/sstream.tcc:114:35: Error: error: expected unqualified-id before '(' token

Turns out this was because the library I was linking with (medit) had the following lines:


#ifdef min                                                                                                
#undef min                                                                                                
#undef max                                                                                                
#endif
#define  min(a,b)       ( ((a) < (b)) ? (a) : (b) )                                                       
#define  max(a,b)       ( ((b) > (a)) ? (b) : (a) )      

Some how undefining min and max and then redefining them as these ruins sstream when included after.