2014 SciVis paper “Fast and Memory-Efficient Topological Denoising of 2D and 3D Scalar Fields”

September 22nd, 2014

David Günther, Jan Reininghaus, Hans-Peter Seidel, Olga Sorkine-Hornung, Tino Weinkauf and I will publish our paper
“Fast and Memory-Efficient Topological Denoising of 2D and 3D Scalar Fields” in TVCG and David will present the work at SciVis this year. This paper is a much-needed extension of our earlier SGP paper on optimizing over monotonic functions. This new paper provides two new heuristics: 1) a plaided domain decomposition enables efficient optimization on much larger datasets (notably 3D images, e.g. voxel grids), and 2) iterating on our convexification of the monotonicity constraint. This iteration idea greatly improves the quality of solutions when the gradient direction of the harmonic initial guess is far from matching the optimal solution, particularly important in the case of data smoothing. In some sense, one could view this as a sort of trust-region-ish algorithm, but our problem specific knowledge allows us to make much better progress.

Download the paper.

Using embree compiled with gcc from a program compiled with clang

September 12th, 2014

I compiled Embree using my standard compiler gcc 4.7 (I’m holding out on clang for openmp support), but for a specific project I need to use clang. When I try to link against libembree.a and libsys.a I get this sort of error:

  "std::string::find(char, unsigned long) const", referenced from:
      embree::AccelRegistry::create(std::string, embree::RTCGeometry*) in libembree.a(registry_accel.o)
      embree::BuilderRegistry::build(std::string, embree::TaskScheduler::Event*, embree::Accel*) in libembree.a(registry_builder.o)
      embree::IntersectorRegistry<embree::Intersector1>::get(std::string, std::string, embree::Accel*) in libembree.a(registry_intersector.o)
      embree::IntersectorRegistry<embree::Intersector4>::get(std::string, std::string, embree::Accel*) in libembree.a(registry_intersector.o)
  "std::string::compare(char const*) const", referenced from:
      embree::AccelRegistry::create(std::string, embree::RTCGeometry*) in libembree.a(registry_accel.o)
      embree::BuilderRegistry::build(std::string, embree::TaskScheduler::Event*, embree::Accel*) in libembree.a(registry_builder.o)
      embree::IntersectorRegistry<embree::Intersector1>::get(std::string, std::string, embree::Accel*) in libembree.a(registry_intersector.o)
      embree::IntersectorRegistry<embree::Intersector4>::get(std::string, std::string, embree::Accel*) in libembree.a(registry_intersector.o)
...

I tried using the flag -stdlib=libc++ but this doesn’t fix the problem. Using -stdlib=libstdc++ most errors go away except for:

  "std::ctype<char>::_M_widen_init() const", referenced from:
      embree::rtcBuildAccel(embree::RTCGeometry*, char const*) in libembree.a(embree.o)
      embree::BVHStatisticsT<embree::BVH2>::print() in libembree.a(bvh2.o)
      embree::BVHStatisticsT<embree::BVH4>::print() in libembree.a(bvh4.o)
      embree::BVHBuilderT<embree::BVH4, embree::HeuristicBinning<0> >::createLeafNode(unsigned long, embree::atomic_set<embree::PrimRefBlock>&, embree::HeuristicBinning<0>::PrimInfo const&) in libembree.a(bvh4.o)
      embree::BVHBuilderT<embree::BVH4, embree::HeuristicBinning<2> >::createLeafNode(unsigned long, embree::atomic_set<embree::PrimRefBlock>&, embree::HeuristicBinning<2>::PrimInfo const&) in libembree.a(bvh4.o)
      embree::BVHBuilderT<embree::BVH4, embree::HeuristicSpatial<0> >::createLeafNode(unsigned long, embree::atomic_set<embree::PrimRefBlock>&, embree::HeuristicSpatial<0>::PrimInfo const&) in libembree.a(bvh4.o)
      embree::BVHBuilderT<embree::BVH4, embree::HeuristicSpatial<2> >::createLeafNode(unsigned long, embree::atomic_set<embree::PrimRefBlock>&, embree::HeuristicSpatial<2>::PrimInfo const&) in libembree.a(bvh4.o)

This error seems trickier and to remove it I explicitly link against libgcc_s.a found in my gcc’s libraries: add the linker argument /opt/local/lib/gcc47/libstdc++.a. This gets me close, but there’s a new error:

  "___emutls_get_address", referenced from:
      ___cxa_get_globals_fast in libstdc++.a(eh_globals.o)
      ___cxa_get_globals in libstdc++.a(eh_globals.o)

Turns out that I need another library from gcc making the arguments now: /opt/local/lib/gcc47/libstdc++.a /opt/local/lib/gcc47/libgcc_s.1.dylib. And this finally works.

Update: Oddly it seems on the static libstdc++.a has the final problem. Linking to the dymnamic library libstdc++.dylib in the same directory works fine (maybe because I’m just avoiding the issue with this example).

Eigen + C++11′s auto gotcha

September 10th, 2014

Today marks the second time running into this gotcha involving Eigen and C++11′s auto. It may even be a bug.

Here’s the little example program:

Eigen::MatrixXd X(2,2);                                                    
X<<1,2,
   3,4;                                                                    
const auto mid = (X.colwise().maxCoeff()+X.colwise().minCoeff()).eval()*0.5;  
cout<<mid<<endl;                                                           
X.setZero();                                                               
cout<<mid<<endl;
cout<<(X.colwise().maxCoeff()+X.colwise().minCoeff()).eval()*0.5<<endl;    

First I initialize a little matrix and then take the average of it’s column-wise max and min vectors and store that in mid. I’m being careful to use .eval() because this should truly evaluate the expression. Then I print mid, zap X to zero, print mid again and—to double check—print the expression applied to the new all-zero X:

With clang this produces:

2 3
  1 1.5
0 0

With gcc I get:

2 3
-6.44115e-232  1.34339e+154
0 0

So it seems that after X is set to zeros, mid contains some random bad value.

Changing auto above to char and reading the compiler error message I can reveal the true type of the expression

const ScalarMultipleReturnType {aka const Eigen::CwiseUnaryOp<Eigen::internal::scalar_multiple_op<double>, const Eigen::Matrix<double, 1, -1> >}

Okay, so definitely not something simple like Eigen::RowVector<...> which I’d expected. Not sure why this is returning junk when the values of X change. For now, and for this simple example, the easy solution is to explicitly cast to the type I want:

const RowVector2d mid = (X.colwise().maxCoeff()+X.colwise().minCoeff()).eval()*0.5;

Compiling C++ with C++11 support on bluehost servers

September 8th, 2014

I asked bluehost to install a modern version of gcc with C++11 support. They told me that only gcc4.3 was deemed stable.

So then I tried to compile gcc4.7 and gcc4.9 from scratch. This seemed promising but eventually I hit some apparent bug in the make routine of gcc giving me the error:

"cp: cannot stat `libgcc_s.so.1': No such file or directory"

Manually copying the file for make did not help.

So then I switched to trying to compile clang. This worked. I followed the instructions in this answer.

Namely, I added this to my .bashrc

export LD_LIBRARY_PATH=/usr/lib/gcc/x86_64-redhat-linux/4.4.7/:$LD_LIBRARY_PATH
export CC=/usr/bin/gcc
export CXX=/usr/bin/g++

Then issued the following:

source .bashrc
wget http://llvm.org/releases/3.3/cfe-3.3.src.tar.gz
tar xzf llvm-3.3.src.tar.gz && cd llvm-3.3.src/tools/ && tar xzf ../../cfe-3.3.src.tar.gz
cd llvm-3.3.src
mv tools/cfe-3.3.src tools/clang
./configure --prefix=$HOME/llvm-3.3.src/llvm
make -j8
make install

Now to test it out, I created a file test.cpp with this inside:

#include <iostream>
int main(int argc, char *argv[])
{
  const auto & hello = []()
  {
    std::cout<<"Hello, world."<<std::endl;
  };
  hello();
}

Then I could try to compile with:

llvm-3.3.src/llvm/bin/clang++ -std=c++11 test.cpp -o test

But I get the error:

In file included from test.cpp:1:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/iostream:40:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/ostream:40:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/ios:40:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/exception:148:
/usr/lib/gcc/x86_64-redhat-linux/4.4.7/../../../../include/c++/4.4.7/exception_ptr.h:143:13: error: unknown type name
      'type_info'
      const type_info*
            ^
1 error generated.

This seems to be a known bug with old “stable” versions of gcc’s standard library. The fix is to add a class declaration before the #include <iostream>:

#ifdef __clang__
    class type_info;
#endif
#include <iostream>
int main(int argc, char *argv[])
{
  const auto & hello = []()
  {
    std::cout<<"Hello, world."<<std::endl;
  };
  hello();
}

This compiles and runs.

Compile Embree without GLUT

September 8th, 2014

Trying to compile embree on a server, I was notified that I didn’t have GLUT installed:

CMake Error at /home2/alecjaco/share/cmake-2.8/Modules/FindPackageHandleStandardArgs.cmake:97 (MESSAGE):
  Could NOT find GLUT (missing: GLUT_glut_LIBRARY GLUT_INCLUDE_DIR)

I shouldn’t need this because I don’t care about visualizing the results. To get around this requirement I simply comment out the following line in the top level CMakeLists.txt:

ADD_SUBDIRECTORY(examples)

becomes

#ADD_SUBDIRECTORY(examples)

CGAL function pointer callback in isosurface example

September 4th, 2014

I really struggled with the CGAL templating madness in their isosurface example today. The following example contours the 0-level isosurface given an implicit function of a sphere (i.e. a pointer to a function sphere_function):

#include <CGAL/Surface_mesh_default_triangulation_3.h>
#include <CGAL/Complex_2_in_triangulation_3.h>
#include <CGAL/make_surface_mesh.h>
#include <CGAL/Implicit_surface_3.h>
// default triangulation for Surface_mesher
typedef CGAL::Surface_mesh_default_triangulation_3 Tr;
// c2t3
typedef CGAL::Complex_2_in_triangulation_3<Tr> C2t3;
typedef Tr::Geom_traits GT;
typedef GT::Sphere_3 Sphere_3;
typedef GT::Point_3 Point_3;
typedef GT::FT FT;
typedef FT (*Function)(Point_3);
typedef CGAL::Implicit_surface_3<GT, Function> Surface_3;
FT sphere_function (Point_3 p) {
  const FT x2=p.x()*p.x(), y2=p.y()*p.y(), z2=p.z()*p.z();
  return x2+y2+z2-1;
}
int main() {
  Tr tr;            // 3D-Delaunay triangulation
  C2t3 c2t3 (tr);   // 2D-complex in 3D-Delaunay triangulation
  // defining the surface
  Surface_3 surface(sphere_function,             // pointer to function
                    Sphere_3(CGAL::ORIGIN, 2.)); // bounding sphere
  // Note that "2." above is the *squared* radius of the bounding sphere!
  // defining meshing criteria
  CGAL::Surface_mesh_default_criteria_3<Tr> criteria(30.,  // angular bound
                                                     0.1,  // radius bound
                                                     0.1); // distance bound
  // meshing surface
  CGAL::make_surface_mesh(c2t3, surface, criteria, CGAL::Non_manifold_tag());
  std::cout << "Final number of points: " << tr.number_of_vertices() << "\n";
}

I wanted to adapt this example to use a different implicit function, so I tried creating a sphere function that also took another parameter (x-axis scaling):

FT scale_sphere_function (double a,Point_3 p) {
  const FT x2=a*p.x()*p.x(), y2=p.y()*p.y(), z2=p.z()*p.z();
  return x2+y2+z2-1;
}

Then my idea was to use std::bind to bind a local variable or value to the first argument so I could pass it to Surface_3. Something like

double a = 2.0;
Surface_3 surface(
  std::bind(&scale_sphere_function,a,std::placeholders::_1),
  Sphere_3(CGAL::ORIGIN, 2.)); // bounding sphere

But I get compiler errors because it’s trying to convert the std::bind output (std::function<>) to a function pointer:

/opt/local/include/CGAL/Implicit_surface_3.h:50:5: note: CGAL::Implicit_surface_3<GT, Function_>::Implicit_surface_3(CGAL::Implicit_surface_3<GT, Function_>::Function, CGAL::Implicit_surface_3<GT, Function_>::Sphere_3, CGAL::Implicit_surface_3<GT, Function_>::FT, CGAL::Implicit_surface_3<GT, Function_>::Geom_traits) [with GT = CGAL::Robust_circumcenter_traits_3<CGAL::Epick>; Function_ = double (*)(CGAL::Point_3<CGAL::Epick>); CGAL::Implicit_surface_3<GT, Function_>::Function = double (*)(CGAL::Point_3<CGAL::Epick>); CGAL::Implicit_surface_3<GT, Function_>::Sphere_3 = CGAL::Sphere_3<CGAL::Epick>; CGAL::Implicit_surface_3<GT, Function_>::FT = double; CGAL::Implicit_surface_3<GT, Function_>::Geom_traits = CGAL::Robust_circumcenter_traits_3<CGAL::Epick>]
/opt/local/include/CGAL/Implicit_surface_3.h:50:5: note:   no known conversion for argument 1 from 'std::_Bind_helper<false, double (&)(double, CGAL::Point_3<CGAL::Epick>), int, const std::_Placeholder<1>&>::type {aka std::_Bind<double (*(int, std::_Placeholder<1>))(double, CGAL::Point_3<CGAL::Epick>)>}' to 'CGAL::Implicit_surface_3<CGAL::Robust_circumcenter_traits_3<CGAL::Epick>, double (*)(CGAL::Point_3<CGAL::Epick>)>::Function {aka double (*)(CGAL::Point_3<CGAL::Epick>)}'
/opt/local/include/CGAL/Implicit_surface_3.h:34:9: note: constexpr CGAL::Implicit_surface_3<CGAL::Robust_circumcenter_traits_3<CGAL::Epick>, double (*)(CGAL::Point_3<CGAL::Epick>)>::Implicit_surface_3(const CGAL::Implicit_surface_3<CGAL::Robust_circumcenter_traits_3<CGAL::Epick>, double (*)(CGAL::Point_3<CGAL::Epick>)>&)
/opt/local/include/CGAL/Implicit_surface_3.h:34:9: note:   candidate expects 1 argument, 2 provided
/opt/local/include/CGAL/Implicit_surface_3.h:34:9: note: constexpr CGAL::Implicit_surface_3<CGAL::Robust_circumcenter_traits_3<CGAL::Epick>, double (*)(CGAL::Point_3<CGAL::Epick>)>::Implicit_surface_3(CGAL::Implicit_surface_3<CGAL::Robust_circumcenter_traits_3<CGAL::Epick>, double (*)(CGAL::Point_3<CGAL::Epick>)>&&)
/opt/local/include/CGAL/Implicit_surface_3.h:34:9: note:   candidate expects 1 argument, 2 provided

I tried all sorts of conversions and casts and uses of target() (which is pointless and only works when you originally started with a function pointer) to twist my std::bind into a function pointer. But the problem turned out to be very simple. The example had defined Surface_3 to use a function pointer:

typedef FT (*Function)(Point_3);
typedef CGAL::Implicit_surface_3<GT, Function> Surface_3;

I can just define it to use a std::function<> instead:

typedef std::function<FT (Point_3)> Function;
typedef CGAL::Implicit_surface_3<GT, Function> Surface_3;

Then I can create a Surface_3 with std::bind:

double a = 2.0;
Surface_3 surface(
  std::bind(&sphere_function,a,std::placeholders::_1),
  Sphere_3(CGAL::ORIGIN, 2.)); // bounding sphere

or even an inline lambda with capturing:

Surface_3 surface(
  [&a](Point_3 p)->FT{ return sphere_function(a,p);},
  Sphere_3(CGAL::ORIGIN, 2.)); // bounding sphere

I’m apparently not the only one with problem. Probably CGAL should just use std::function or boost::function in the example since it’s easy to convert to those from a function pointer (but as I learned it’s impossible the other way).

Skinning.org Siggraph 2014 Course Notes

August 12th, 2014

skinning course at siggraph

Zhigang Deng, Ladislav Kavan, JP Lewis and I are teaching a course this week at siggraph.

We’ll cover a wide variety of skinning related techniques and we’re hosting our notes at skinning.org. Check it out and tell us what you think!

Emoji in LaTeX documents

August 5th, 2014

Update: Hilariously, it turns out that either wordpress or my wordpress markdown plugin is choking on the emoji inserted into this post. Thus, to see the actually emoji commands see this plaintext version


We were recently joking around about using emoji in math equations. The idea was to satire of the bad rap exterior calculus symbols like the the Hodge star operator (★) and the “musical isomorphisms” (♭,♯) get in the computer graphics community.

I found a solution for upTeX. This works by first extracting all of the emojis as pdfs and then including the pdfs via (includegraphics) whenever a \coloremoji{...} command is found. This unfortunately did not work with my TexLive pdflatex setup. With some help, I’ve redesigned a coloremoji.sty stylesheet that allows you to directly include emoji in your LaTeX documents.

A Hello, EmojiWorld LaTeX document would look like this:

WordPress dies on emoji, see plaintext version

This produces something that should look like:

hello world emoji

You can also use emoji in mathmode:

WordPress dies on emoji, see plaintext version

alligator power integral math emoji latex

Download the coloremoji package and simply add \usepackage{coloremoji} to the top of your document.

Actually, Nobuyuki Umetani gave a talk where he used graphic icons in math (I believe successfully!) to explain Sensitive Couture (change in clothing with respect to change in mouse interaction):

Nobuyuki's emoji math

Small typo in “Shape Decomposition Using Modal Analysis”

July 30th, 2014

Upon implementing the modal analysis part of “Shape Decomposition Using Modal Analysis” [Huang et al. 2009], I noticed a small typo in the derivation.

However, I ran into a small issue regarding the construction of matrix C in Equation 6. C_i is responsible for the quadratic terms involving c_i. Namely,

∑j_N(i) wij || c_i x (pi - pj) ||^2

The squared norm of a cross product can be written as the sum of the product of individual squared norms and the squared dot product: ||a x b||^2 = ||a||^2 ||b||^2 - (a.b)^2. Or in our case:

∑j_N(i) wij || c_i ||^2 || pi - pj ||^2 + wij (ci . (pi-pj) )^2

Now, in the 2009 paper only the latter term is included in C_i as it is equivalent to the covariance matrix (sum of outerproducts):

ci' C_i ci = ci' ( ∑j_N(i) wij (pi-pj) (pi - pj)' ) ci

where a’ is the transpose of a.

C_i should also contain a diagonal term accounting for ∑j_N(i) wij || c_i ||^2 || pi - pj ||^2. This is of course easy to add to C_i.

Update: Huang replied to me with another way to rewrite the construction C_i correctly and using a notation more familiar to the original paper:

∑j wij (p_{i}-p_{j})_x (p_{i}-p_{j})_x',

where a_x is the matrix representing cross product with a and it follows that a_x a_x' = ||a||^2 - (aa').

And then it’s working. Here’re some modes of a cow:

cow arap eigen modes

Linksys router + Motorola Surfboard + Time Warner needs reset after power outage

July 26th, 2014

Our vacuum keeps blowing the fuse in our apartment and each time the internet goes down. I haven’t tracked down why this happens, but here’s my solution after a couple times.

  1. Open http://192.168.1.1/WanMAC.asp (router’s configuration page) and note down MAC Address currently cloning
  2. Unplug power to router and modem and wait 15 seconds
  3. Plug power to router and modem in again
  4. Unplug ethernet from the linksys router
  5. Connect original computer (with MAC address above) directly to router using ethernet, check that some page loads
  6. Restore Linksys to factory settings using little button on back
  7. Connect to restored wireless router (it should have name linksys)
  8. Open http://192.168.1.1/WanMAC.asp and enable MAC address cloning with previously noted address
  9. Open http://192.168.1.1/Wireless_Basic.asp and restore wireless name exactly
  10. Reconnect to router wireless router using new name
  11. Open http://192.168.1.1/WL_WPATable.asp and set up password again exactly: choose WEP, then type password as Key 1
  12. Once again reconnect to wireless router using new name, your machine should remember that it used to remember this password if it’s the same