Archive for October, 2013

GCC parameter order causes segmentation fault in embree 2.0

Tuesday, October 29th, 2013

I was trying to compile and link against embree 2.0 (checked out from svn yesterday) on a Mac OS X 10.7.5 iMac with a 3.4 GHz Intel Core i7. I compiled Embree as per the instructions on the website using cmake and make. My default c/c++ compiler is gcc 4.7.2.

Upon trying to compile and run with embree I found that certain gcc parameter orders cause embree’s rtcinit function to crash at runtime. Here is a minimal C++ program to reproduce the problem, save it in bug.cpp:

#include <embree/include/embree.h>
#include <iostream>

class EmbreeIntersector
{
  public:
    EmbreeIntersector()
    {
      using namespace std;
      cout<<"EmbreeIntersector(): before rtcInit()"<<endl;
      embree::rtcInit();
      cout<<"EmbreeIntersector(): after rtcInit()"<<endl;
    }
} ei;

int main()
{
  using namespace std;

  return 0;
}

If I compile with:

g++ \
  -I/usr/local/igl/libigl/external/embree/embree \
  -I/usr/local/igl/libigl/external/embree/ \
  -L/usr/local/igl/libigl/external/embree/bin \
  -o bug \
  -lembree \
  bug.cpp  \
  -lsys

then running ./bug seems to execute correctly. I see as output:

EmbreeIntersector(): before rtcInit()
EmbreeIntersector(): after rtcInit()

However, if I compile with:

g++ \
  -I/usr/local/igl/libigl/external/embree/embree \
  -I/usr/local/igl/libigl/external/embree/ \
  -L/usr/local/igl/libigl/external/embree/bin \
  -o bug \
  bug.cpp  \
  -lembree \
  -lsys

then running ./bug I see:

EmbreeIntersector(): before rtcInit()
Segmentation fault: 11

I’m guessing that this will be chalked up to a GCC bug. But is there any reason to expect this sort of behavior from gcc or embree?

Update: Seems to also happen in a separated compile and link build. Compile first with:

g++ \
  -I/usr/local/igl/libigl/external/embree/embree \
  -I/usr/local/igl/libigl/external/embree/ \
  -o bug.o \
  -c bug.cpp

Then this parameter order for linking produces a good binary:

g++ \
  -o bug \
  -L/usr/local/igl/libigl/external/embree/bin \
  -lembree \
  bug.o \
  -lsys

And equivalently here’s the bad order:

g++ \
  -o bug \
  -L/usr/local/igl/libigl/external/embree/bin \
  bug.o \
  -lembree \
  -lsys

Update: I emailed embree support and immediately got a helpful response:

You are calling the rtcInit function from the constructor of a global variable “ei”. This causes problems, as other global variables that Embree needs have to be initialized before your global variable. Using Embree this way is not supported. Create an instance of your EmbreeInstersector function using the new operator in the main function fixes the problem.

Seems that the GCC link order also determines the order of initializations for global variables. Indeed, dynamically instantiating my EmbreeIntersector class using new EmbreeIntersector() resolves this issue.

Patch for GLUT on Mac OS X for horizontal scrolling and command key modifier

Thursday, October 24th, 2013

I recently found out about a patch for the GLUT framework on Mac OS X to provide support for mouse wheel scrolling. This is great, because I was really getting tired of the X11 windows that freeGLUT uses.

I followed these instructions for building from source: grab the source from Apple and apply the 3 patches.

Unfortunately I still got compilation errors on Mac OS X 10.7.5 with Xcode 4.

Type 'id <NSMenuItem>' does not conform to the 'NSCopying' protocol

I fixed this, I changed the line in GLUTApplication.m that looks like:

- (BOOL)validateMenuItem:(id <NSMenuItem>)menuItem

to

- (BOOL)validateMenuItem:(NSMenuItem *)menuItem

Now it compiles. These patches only add support for vertical scrolling. To add horizontal scrolling I changed the scrollWheel function in GLUTView.m to this:

- (void)scrollWheel: (NSEvent *)theEvent
{
   if(_mouseFunc) {
      NSPoint location = [self convertMouseLocationToBacking: [theEvent locationInWindow]];

      float deltaY = [theEvent deltaY];
      float deltaX = [theEvent deltaX];
      int buttonID = GLUT_WHEEL_UP;
      if(deltaY < 0) {
         deltaY = -deltaY;
         buttonID = GLUT_WHEEL_DOWN;
      }else if(deltaY > 0)
      {
         buttonID = GLUT_WHEEL_UP;
      }else if(deltaX < 0)
      {
         deltaY = -deltaX;
         buttonID = GLUT_WHEEL_RIGHT;
      }else if(deltaX > 0)
      {
         deltaY = deltaX;
         buttonID = GLUT_WHEEL_LEFT;
      }

      int x = rint(location.x);
      int y = rint(location.y);

      __glutSetWindow(self);
      int i;
      for(i = 0; i < deltaY; i++) {
//       (*_mouseFunc)(buttonID, GLUT_DOWN, x, y);
         (*_mouseFunc)(buttonID, GLUT_UP, x, y);
      }
   }
}

and add the following definitions in glut.h:

#define GLUT_WHEEL_LEFT 5
#define GLUT_WHEEL_RIGHT 6

While I was at it, I also added support for catching the command (aka apple, aka ⌘) key. To do this I add the following lines to glutGetModifiers in macx_modifier.m:

   if(__glutModifierMask & NSCommandKeyMask)
      modifiers |= GLUT_ACTIVE_COMMAND;

and again added a respective definition in glut.h:

#define GLUT_ACTIVE_COMMAND             8

Now I compile and replace the GLUT.framework directory in /System/Library/Frameworks/ and I’m reading to go!

Download xcodeproject of patched glut

Update: On 10.9 OS X Mavericks, I’m getting complaints from Xcode that garbage collection is no longer supported and that I should switch to ARC. I chose “Not now”, but then got a compile error complaining:

error: garbage collection is no longer supported

I fixed this, following this advice, by removing lines like

                           GCC_ENABLE_OBJC_GC = supported;

from GLUT_External.xcodeproj/project.pbxproj. I’ve updated the zipped project appropriately.

Update: On 10.10 OS X Yosemite my hack for getting modifier keys during mouse move and scroll events with Carbon “expired”. Rather than figure out how to continue using Carbon, I’ve patched Glut again to reveal modifier flags during mouse move and mouse scroll events. This means that you can call glutGetModifiers during your glutPassiveMotionFunc, glutMotionFunc and when glutMouseFunc fires on a scroll event. I’ve updated the zipped project by appropriately enclosing these function calls between:

__glutModifierMask = [theEvent modifierFlags];
... // call func
__glutModifierMask = ~0;

**Update: ** Based on another patch I’ve updated mine to enable easy access to the core profile.

**Update: ** I’ve basically been tracking my changes via a .zip file hosted on this blog. That’s not very safe. Now, I’ve uploaded all of the code to a github repo. You can still download everything as a zip or just clone the repo.

Shiny lights with flare in OpenGL

Monday, October 21st, 2013

I ripped apart this OpenGL demo to add a few C++ functions to our libigl library for rendering shiny lights with lens flare. In version ≥ 0.3.5, check out the example in examples/flare-eyes. This all began because I wanted to render small lights (like LEDs) into my OpenGL scene. I first tried just showing little brightly colored circles.

beast with colored circles for eyes

But this is (un)imaginably lame.

Turns out to make something really look like a shiny light you need a bit more. I didn’t want to go as far as physically-based rendering or even screen space post-processing. Rather I opted for a simple pure openGL approach with textures. I use the glDepthMask(GL_FALSE) to be sure that the layers of textures I paint for each shiny light correctly hid behind seen objects but don’t occlude anything or each other. This gives a rather nice, and cheap, effect:

beast with shiny lights with flare for eyes

“Exposing Photo Manipulation with Inconsistent Shadows” on Tram 13

Thursday, October 17th, 2013

In our seminar today we discussed “Exposing Photo Manipulation with Inconsistent Shadows” by Eric Kee, James F. O’Brien, and Hany Farid. After the presentation I showed an extra example I’d witnessed in an advertisement on the Zurich Tram.

zurich tram mond original

Our drivers make this trip over 90 times a year.

The crux of “Exposing Photo Manipulation with Inconsistent Shadows” is that if you identify enough correspondences between points on shadows silhouettes and objects that may have cast them, then you can determine a feasible region where the light source is. Any correspondences that are inconsistent with the others are evidence of image forgery.

So I walked through the algorithm on this image marking plausible shadow correspondences as wedges or half-planes. The intersection of the consistent ones form a non-empty feasible region for the light source. The suspicious shadow of the tram sign is inconsistent as it does not intersect with that region.

zurich tram add exposed

In my searching for the original ad, I also found this album cover.

tuba on the moon "Tears of the tuba"

It uses the same image of the moon! Looks like the tuba’s shadows are a bit more realistic that the tram sign’s. Maybe there’s a tuba on the moon?

Scrape 3D model from Sketchfab

Wednesday, October 16th, 2013

SketchFab has many 3D models, like this bulldog. Open up their webgl viewer and extract the following Javascript variables to recover the model vertices and faces.

// Copy result of this:
view3D._scene.children[2].children[0].children[0].children[0].children[0].children[0].children[0].children[1].attributes.Vertex._elements
// to U


for each primitive p
  // Copy result of this
  view3D._scene.children[2].children[0].children[0].children[0].children[0].children[0].children[0].children[1].primitives[p].indices._elements
  // to P{p+1}.indices, and 
  view3D._scene.children[2].children[0].children[0].children[0].children[0].children[0].children[0].children[1].primitives[p].mode // 5 means TRIANGLE_STRIP, 4 means TRIANGLES
  // to P{p+1}.mode

Then in matlab you can issue:

V = reshape(U,3,[])';
F = [];
for p = 1:numel(P)
  switch P{p}.mode
  case 4
    F = [F;reshape(P{p}.indices+1,3,[])'];
  case 5
    pF = triangles_from_strip(P{p}.indices+1);
    dblA = doublearea(V,pF);
    F = [F;pF(dblA>0,:)];
  end
end

Then you can save it to a obj, off or stl file or just render it in MATLAB:

sketchfab bulldog in matlab

3D printed Halbach array holder

Monday, October 14th, 2013

I had some magnets lying around and as I was playing with them I remembered about the Halbach array, a special arrangement of permanent magnets such that you get a very strong field on one side and weak field on the other. The only issue is that permanent magnets do not want to stay arranged this way: they’ll quickly rotate and snap together in an aligned direction.

So I quickly mocked up a little Halbach array holder, which I (3d) printed. Here it is next to a Swiss 2 CHF coin:

halbach array holder empty

And here again with 5 1/2-cm magnets loaded inside.

halbach array holder filled

Here’s a video of me loading the magnets. Starting with a stack of aligned magnets, I push them in one-by-one, rotating between each accordingly.

Here’s a video testing the different magnetic strengths of each side against my metal desk frame.

You can download the STL model of the Halbach array holder. I “modeled” it in matlab generating first a hollow box and then adding a small 3-sided lip at one end to make it easier to load in the magnets.

halbach array holder blueprint

I also generated these blueprint-style images in matlab.

Ambient occlusion for matlab pseudo-color plots

Sunday, October 13th, 2013

I’m often plotting scalar functions on surfaces using the trisurf routine of matlab. This has basic per-vertex, per-face coloring. And with some hassle you could even set up lights. Instead I’ve settled on a better way to convey the shape of the surface and the function by multiply the colors with the inverse of the mesh’s ambient occlusion. I wrote a matlab wrapper mex function for our libigl function. Find it in libigl/examples/ambient-occlusion-mex (version ≥0.3.4). Once compiled you can call from matlab it like this:

S = ambient_occlusion(V,F,P,N,num_samples);

Where (V,F) is your triangle mesh, P are the evaluation points and N are the normals (defining a hemisphere).

Here’s an example of multiplying it against some pseudo-color values:

ambient occlusion over pseudo color plot matlab

For computing ambient occlusion per-vertex and then applying it to per-vertex colors, use:

AO = ambient_occlusion(V,F,V,per_vertex_normals(V,F),1000);
tsurf(F,V,'FaceVertexCData',bsxfun(@times,(1-AO),C),fphong,'EdgeColor','none');

Update: If you have a scalar field and you’d like to visualize it using ambient occlusion on top of a pseudo-color, try:

tsurf(F,V,'FaceVertexCData',bsxfun(@times,1-AO,squeeze(ind2rgb(floor(matrixnormalize(Wbh(:,1))*256),jet(256)))),fphong,'EdgeColor','none');

Convex hull volume ratios on closed shapes in SHREC database

Sunday, October 13th, 2013

I wrote a script to compute the ratio of volume inside a given model to the volume of its convex hull. This ratio may be used for various things such as a measure of weak convexity. Here’re the average results applied the SHREC target models database.

Ideally I would have a database of solid meshes (closed, self-intersection free). Then I could simply compute the volume inside the shape and divide by the volume of the convex hull. Unfortunately, of the ~720 SHREC models only 91 are closed and of those only 13 are self-intersection free.

So in the absence of a large set of solid meshes, I opted to consider this convex hull volume ratio for closed meshes. Here are the 91 closed meshes in the shrec dataset:

closed shrec meshes

In the presence of self-intersections determining the interior volume is tricky. We could create a conforming Delaunay tessellation of the convex hull, then for each tetrahedron determine if it is inside (say by checking that the winding number is 0). Unfortunately, no truly robust algorithm for conforming delaunay tessellations exists.

Instead, I sampled a regular grid scaled to the bounding box of the shape, throughout those outside the convex hull and then determined which samples were inside the input shape (by checking that winding number is 0).

inner volume method

inner volume method

inner volume method

Undoubtedly this will be only an approximation, but given that this input shapes are discrete and finite it should converge as the regular grid resolution increases.

Here’s a plot of the average ratio of inner volume to convex hull volume as a function of the number of grid points in a semi-log plot:

average ratio of inner volume to convex hull volume

So, for this set of shapes (which spans quite a variety) the ratio is roughly 30%.

Here’s a histogram for the finest resolution I tested (256x256x256 = 16777216 samples):

average ratio of inner volume to convex hull volume

Update: Here’re the results from the watertight models in the Princeton Surface Correspondence Benchmark. There the average is more like 38%. Here’re the same plots.

average ratio of inner volume to convex hull volume

average ratio of inner volume to convex hull volume

Check yo’ stencil bits in GLUT

Friday, October 11th, 2013

I just wasted a lot of time wondering why I couldn’t get any interesting combinations of glStenilOp and glStencilFunc to work correctly. Turns out I did not have the stencil buffer enabled in my GLUT application. I found this out by adding:

int i;
glGetIntegerv(GL_STENCIL_BITS, &i);
cout<<"GL_STENCIL_BITS: "<<i<<endl;

which displayed:

GL_STENCIL_BITS: 0

I fixed this by changing

glutInitDisplayString( "rgba depth double samples>=8");

to

glutInitDisplayString( "rgba depth double samples>=8 stencil"); 

Now things are working as expected.

Ambient occlusion proof of concept demo in libigl

Tuesday, October 8th, 2013

The libigl “extra” for the Embree ray tracing library made it super easy to whip up an ambient occlusion demo. Check out the example in the libigl source under libigl/examples/ambient-occlusion (version ≥0.3.3).

beast ambient occlusion in libigl

The demo just shoots rays in random directions in the hemisphere of each mesh vertex and aggregates a hit ratio. Then it colors the mesh with these values per-vertex using GL_COLOR_MATERIAL. The program shoots a few more rays per point every draw frame (except when the users dragging the camera around).

There are plenty of ways to be fancier about ambient occlusion, but this demonstrates the basic idea.