Archive for June, 2014

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

Get polygon from user in matlab as list of points

Wednesday, June 25th, 2014

Simple as that:

P = getPosition(impoly);

Projecting out the null space of an underconstrained linear system

Wednesday, June 25th, 2014

This came up twice now recently, so I’m writing it out as a reference.

Suppose you have a system:

A x = b

where A is n by n, x is n by 1 and b is n by 1. However, rank(A) = m < n. This means there is not just one unique solution, but a family of solutions. Now, let’s assume we can build a basis for the null space of A. That is we can write an n by n-m matrix N such that

A N u = 0

for any n-m by 1 vector u. Then we can also write the matrix M = N which spans the space orthogonal to N. Then we can write any n by 1 vector in these bases:

x = N u + M v

Substituting this into our original system, we see that the choice of u doesn’t matter

A (N u + M v) = b
A M v = b

Now we have a system of n equations and m unknowns. This is over-constrained. Let’s choose the minimum in the least squares sense.

minimize |A M v - b|^2

Differentiating with respect to v and setting to zero we get

M' A' A M v = M' A' b

which we can solve for v.

Then we can recover x as

x = M v

We can show that indeed this satisfies the original equation by substituting this back in above:

A M v = b
A M ( M' A' A M ) \ M' A' b = b

Let Z = A M, then write this as

Z (Z' Z) \ Z b = b

But (Z’ Z) \ Z is simply the pseudo-inverse of Z so we know that Z (Z’ Z) \ Z = I and we have that b = b.

Eigen unaryExpr gotcha, need to set via assignment

Monday, June 23rd, 2014

I tried to use eigen’s unaryExpr with a function using references to alter a matrix:

MatrixXd X;
...
X.unaryExpr([](double & x){ x = 0});

But X was left unchanged. Thinking I might need to use a function with a return I tried:

X.unaryExpr([](double & x)->return{ return 0});

but still X was unchanged. It seems that unaryExpr is a const operation so I must assign the result back into X. This works:

X = X.unaryExpr([](double & x)->return{ return 0});

Continuously refresh markdown output

Tuesday, June 17th, 2014

I had a hard time finding a chrome plugin for a rendering markdown which supported LaTeX equations. Instead I’m using multimarkdown which supports equations with mathjax. However, to render the html output I need to open it in Chrome and refresh it when anything changes. So my pipeline looks like:

repeat
  edit .md files
  run multimarkdown command
  open/refresh .html file in chrome
end

I found this nice ruby/applescript script.
I’ve modified it to support markdown files and to run a command when a file changes:

#!/usr/bin/env ruby
# watch.rb by Brett Terpstra, 2011 <http://brettterpstra.com>
# with credit to Carlo Zottmann <https://github.com/carlo/haml-sass-file-watcher>

trap("SIGINT") { exit }

if ARGV.length < 2
  puts "Usage: #{$0} watch_folder keyword command"
  puts "Example: #{$0} . mywebproject"
  exit
end

dev_extension = 'dev'
filetypes = ['css','html','htm','php','rb','erb','less','js','md']
watch_folder = ARGV[0]
keyword = ARGV[1]
command = ARGV[2]
puts "Watching #{watch_folder} and subfolders for changes in project files..."

while true do
  first = true
  while true do
    files = []
    filetypes.each {|type|
      files += Dir.glob( File.join( watch_folder, "**", "*.#{type}" ) )
    }
    new_hash = files.collect {|f| [ f, File.stat(f).mtime.to_i ] }
    hash ||= new_hash
    diff_hash = new_hash - hash
    if not diff_hash.empty?
      if first and not command.empty?
        val=`#{command}`
        first = false
      else
        break
      end
    else
      sleep 1
    end
  end


  unless diff_hash.empty?
    hash = new_hash

    diff_hash.each do |df|
      puts "Detected change in #{df[0]}, refreshing"
      %x{osascript<<ENDGAME
            tell application "Google Chrome"
    set windowList to every window
    repeat with aWindow in windowList
        set tabList to every tab of aWindow
        repeat with atab in tabList
            if (URL of atab contains "#{keyword}") then
                tell atab to reload
            end if
        end repeat
    end repeat
        end tell
ENDGAME
}
    end
    sleep 1
  end

end

Save this in a file watch.rb and then call with something like:

watch.rb . readme "multimarkdown readme.md -o readme.html"

gdb, lldb not showing line numbers for binaries compiled from stdin

Tuesday, June 17th, 2014

I recently figured out why my self-compiling C++ files didn’t play nicely with debuggers. It seems that when compiling with gcc (from Macports) and reading in the C++ code from standard input (using the -x c++ - arguments), the debuggers gdb and lldb won’t show high level information like code snippets or line numbers even if the -g option is present. Seems that gcc isn’t really including that information in the binary, rather it’s looking it up at run-time. You can verify this by changing the source file after compiling and then running the debugger. clang++ on the otherhand seems to embedd information from stdin into the executable so that it can be properly debugged.

In the meantime, I’ll keep using gcc but for self-compiling routines I need to use auxiliary files.

Schur complement trick for positive semi-definite energies

Friday, June 13th, 2014

schur complement trick

I’ve posted a technical report which details a way to utilize the famous “Schur complement trick” for positive semi-definite energies.

The basic idea is to shave off enough rows and columns of the system matrix to make it non-singular, add just treat these rows and columns as if they were part of the blocks coming from the Lagrange multipliers.

This trick is useful for quadratic energy minimization subject to linear equality constraints. In particular, when you have a fixed energy with a small number of changing constraints. Especially if the number of constraints is small and also changing: constraints can be edited, added, or deleted. Then the bulk of the solving work can be done as precomputation and only substitution and small dense solve is needed at solve time.

Such situations arise in geometry processing when the system matrix is the Laplace or Laplace-Beltrami operator and the problem is minimizing Dirichlet energy subject to some yet to be determined boundary conditions or constraints. For a mesh with n vertices, the discrete Laplace operator is rank n-1, so only one row and column need to be moved.

Tricking latexmk into using -draftmode

Thursday, June 12th, 2014

A friend recently showed me latexmk, an alternative to my current setup of using make to compile complicated tex documents (calling bibtex and pdflatex). Latexmk seems cool because it’s really tracking all the dependencies and not just recompiling everything. However, it seems to always run pdflatex in “final draft” mode, even for early passes which might as well use the -draftmode option. On my thesis (218 page document with figures on roughly every other page), this meant latexmk took 50s and my makefile routine took 23s (assuming a cold start).

I guess the sad answer is that it’s impossible to know if the current run of pdflatex should be the last (and hence should not be using -draftmode). So I guess latexmk plays it safe and runs everything without -draftmode.

My makefile assumes that I only ever need 3 passes, which I guess is pretty common but by no means universal.

I came up with gnarly alternative, which almost needs a makefile itsel:

latexmk -f -pdf -pdflatex="touch thesis.pdf && pdflatex -draftmode" thesis.tex && rm thesis.pdf && latexmk -pdf thesis.tex

First it runs latexmk forcing pdflatex to use -draftmode, but also always touching the pdf so latexmk is convinced that it succeeded in making its targets, then before running a final pass with latexmk I need to remove the pdf so that latexmk thinks there’s something to do. Draftmode passes cost very little so this also runs at about 24s on my thesis.

Wonder if there’s a cleaner way. Especially if thesis.pdf could be inferred nicely from thesis.tex (I guess using basename) and whether I can safely wrap this into an alias:

alias latexmk="..."

Update: Here’s a better version, my friend came up with. It still needs the tex filename twice, but at least it’s using substitution in the pdflatex “command” and the -g option forces latexmk to run at least once.

latexmk -f -pdf -pdflatex='pdflatex -draftmode %O %S && touch %D' thesis && latexmk -pdf -g thesis