Solid angle at mesh vertices

February 3rd, 2016

The solid angle (aka generalized winding number) at a point lying on a surface can be defined to be the signed area of the surface of the mesh projected onto the unit sphere centered at that point.

For triangle meshes, we can always theoretically compute this as sum of the signed solid angles of each individual triangle. Since the point lies on the mesh, we should be careful about possible numerical pitfalls. In particular, we should ignore any (potentially erroneous) contribution from faces incident on the point. For example, if summing solid angles for the barycenter of some face f we should omit the contribution of f since we know its projection ought to be exactly zero: it projects to a curve on the sphere. Theoretically we only need to ignore contributions from faces intersecting the evaluation point, but one could play it safe and ignore each face for which the evaluation point lies on its plane.

If the mesh is a closed, embedded manifold then the solid angle is a local computation involving the dihedral angles of the incident faces.

For points in the middle of a face f (i.e., not at an edge or vertex), the solid angle is as the face’s plane cuts the sphere in half. Anything projecting on the outside half must double-back on itself to cancel out since the surface is closed and embedded. For points along the middle of the edge between two faces f and g (i.e., not at a vertex) the solid angle is proportional to dihedral angle. The incident faces cut a wedge from the sphere with surface area (assuming Φ runs from 0 to . Finally, for the solid angle at a vertex, we can utilize the spherical excess formula, stating that the solid angle :

      N
Ω = ( ∑ Φi ) - (N-2)π
     i=1

Or using gptoolbox

[AD,C] = adjacency_dihedral_angle_matrix(V,F);
AF = AD~=0;
[AFI,~,AFV] = find(AF);
[~,~,CV] = find(C);
[ADI,~,ADV] = find(AD);
D = sparse( F(sub2ind(size(F),[ADI;ADI],mod([CV;CV+1],3)+1)), 1, 1*repmat(ADV,2,1),size(V,1),1)/2;
SD = D - (N-2)*pi;

Pseudocoloring the solid angle per-vertex has an interesting effect: one can interpret the solid angle as a sort of cheap-o local ambient occlusion. Indeed it’s revealing how much of the immediate surface is occluding any incoming light.

knight solid angle ambient occlusion

Of course it only works at edges and vertices (where there could be any curvature).

Boolean operations using generalized winding numbers

February 2nd, 2016

booleans using generalized winding number

I posted a little tech report about how to use the generalized winding number for constructive-solid geometry (CSG) style boolean operations (union, intersection, difference etc.) on nasty meshes.

Code implementing this has existed for a little while now in the mesh_boolean_winding_number function of gptoolbox.

Code and presentation slides for Nested Cages

February 1st, 2016

nested cages teaser

We’ve released the source code and presentation slides for our paper Nested Cages, presented last November at SIGGRAPH Asia 2015.

List of 3D model repositories, databases

January 24th, 2016

Here’s a table of Model repos with some notes about prices/free-ness.

Make the most recent tex document in the current directory and open it

January 13th, 2016

Here’s a little bash script to compile (pdflatex, bitex, 2*pdflatex,etc.) the most recent .tex file in your current directory that contains begin{document} (i.e. the main document):

#!/bin/bash
if [ -z "$LMAKEFILE" ]; then
  echo "Error: didn't find LMAKEFILE environment variable"
  exit 1
fi
TEX=$( \
  grep -Il1dskip "begin{document}" *.tex | \
  xargs stat -f "%m %N" | \
  sort -r | \
  head -n 1 | \
  sed -e "s/^[^ ]* //")
BASE="${TEX%.*}"
if [ -z "$TEX" ]; then
  echo "Error: Didn't find begin{document} in any .tex files"
  exit 1
fi
make -f $LMAKEFILE $BASE && open $BASE.pdf

Simply use it:

texmake

list of C++11 lambda’s gotcha when capturing by reference

January 11th, 2016

Here’s a little example that produces an (at first glance) unintuitive result.

#include <vector>
#include <iostream>
int main(int argc, char * argv[])
{
  std::vector<std::function<int(void)> > index(10);
  for(int i = 0;i<index.size();i++)
  {
    index[i] = [&i]()
      {
        return i;
      };
  }
  for(int i = 0;i<index.size();i++)
  {
    std::cout<<i<<" "<<index[i]()<<std::endl;
  }
}

I’m constructing a list of lambda functions that simply print their own index in the list. I define each lambda to capture the index i. But actually I’m capturing a reference to a locally scoped variable. I’m pretty sure the behavior here is undefined. The output seems to just pick up the last data in that location i=10 at the end of the loop. So this program prints:

0 10
1 10
2 10
3 10
4 10
5 10
6 10
7 10
8 10
9 10

To get the intended result, I should either maintain another list with the data for each lambda from which I can safely use references if it is in the same scope as the lambda, or I should just pass by value:

...
index[i] = [i]()
...

Wouldn’t a compiler warning when capturing locally scoped references be possible/desired?

Hacky texture map editor using libigl

January 7th, 2016

Here’s a little program that reads a texture mapped mesh from an .obj with UVs and a texture map from a .png and visualizes them.

Before every frame is drawn, I reload the .png file. So if you’ve saved a newly edited version, say in photoshop with a window open next to the viewer window, then it will be loaded. The bottleneck currently is for sure me hitting the save key.

#include <igl/readOBJ.h>
#include <igl/viewer/Viewer.h>
#include <igl/unzip_corners.h>
#include <YImage.hpp>
#include <iostream>
int main(int argc, char * argv[])
{
  using namespace std;
  Eigen::MatrixXd V, TC, N;
  Eigen::MatrixXi F,FTC,FN;
  igl::readOBJ(argv[1],V,TC,N,F,FTC,FN);
  if(FTC.size() == 0)
  {
    FTC = F;
  }
  igl::viewer::Viewer viewer;
  typedef Eigen::Matrix<unsigned char,Eigen::Dynamic,Eigen::Dynamic> MatrixXuc;
  MatrixXuc R,G,B;
  const auto & update_texture = [&]()
  {
    YImage yimg;
    yimg.load(argv[2]);
    R.resize(yimg.width(),yimg.height());
    B.resize(R.rows(),R.cols());
    G.resize(R.rows(),R.cols());
    for(int i = 0;i<yimg.width();i++)
    {
      for(int j = 0;j<yimg.height();j++)
      {
        const auto & p = yimg.at(i,j);
        R(i,yimg.height()-1-j) = p.r;
        G(i,yimg.height()-1-j) = p.g;
        B(i,yimg.height()-1-j) = p.b;
      }
    }
  };
  viewer.callback_pre_draw = [&](igl::viewer::Viewer &)->bool
  {
    update_texture();
    viewer.data.set_texture(R,G,B);
    return false;
  };
  viewer.data.set_mesh(V,F);
  viewer.data.set_colors((Eigen::MatrixXd(1,3) << 1,1,1).finished());
  viewer.data.set_uv(TC,FTC);
  viewer.core.show_texture = true;
  viewer.core.is_animating = true;
  viewer.launch();
}

Unzip OBJ-style mesh into a per-vertex attribute mesh

January 6th, 2016

The .obj mesh file format allows corners of triangles to pull attributes from different sources. The triangle:

v 0 0 0
v 1 0 0
v 0 0 0
vn 1 0 0
vn 0 1 0
vt 0 0 0
f 1/1/1 2/1/1 3/1/2

pulls vertex positions from entries (1,2,3) in the v ... vertex position list, texture coordinates from entries (1,1,1) in the vt ... list, and normals from entries (1,2,2) in the vn normals list.

If we think of corners being described by all attributes there are potentially #F*3 distinct corners. Often information is shared, and in the best case the position/texture/normal indices are all the same, so #V distinct corners. Usually it’s some mixture in between.

I added igl::unzip_corners to libigl which “unzips” an OBJ-style mesh into per-vertex attribute mesh: each new vertex is a distinct corner, so the new face list indexes all attributes in lock step (ideal for OpenGL). I was careful to determine uniqueness combinatorially so, for example, combinatorially distinct input vertices happening to share the same attributes (two vertices at the same position, etc.) don’t get merged (you could always use igl::remove_duplicate_vertices if you wanted to do that).

Here’s a little demo program:

  Eigen::MatrixXd V, TC, N;
  Eigen::MatrixXi F,FTC,FN;
  igl::readOBJ(argv[1],V,TC,N,F,FTC,FN);
  if(FTC.size() == 0)
  {
    FTC = F;
  }
  Eigen::MatrixXi U,G,J;
  igl::unzip_corners<Eigen::MatrixXi>({F,FTC},U,G,J);
  // New mesh vertices and texture coordinates indexed by G
  GV = igl::slice(Eigen::MatrixXd(V),U.col(0),1);
  GTC = igl::slice(Eigen::MatrixXd(TC),U.col(1),1);

Save As Optimized PDF using Acrobat Pro via the command line

January 2nd, 2016

Here’s a tremendously hacky way to automate the procedure of optimizing a PDF using Acrobat Pro (with default settings) from the command line. It’s an applescript sending mouse clicks and keyboard signals so don’t get too excited.

However, I’m doing this all the time and it will hopefully save clicking through menus.

#!/usr/bin/osascript
on run argv
    if (count of argv) < 2 then
        do shell script "echo " & "\"optimizepdf path/to/input.pdf simple-output-name\""
    else
        set p to item 1 of argv
        set out_name to item 2 of argv
        set abs to do shell script "[[ \"" & p & "\" = /* ]] && echo \"" & p & "\" || echo \"$PWD/\"" & p & "\"\""
        set a to POSIX file abs
        tell application "Adobe Acrobat Pro"
            activate
            open a
            tell application "System Events"
                click menu item "Optimized PDF..." of ((process "Acrobat")'s (menu bar 1)'s ¬
                    (menu bar item "File")'s (menu "File")'s ¬
                    (menu item "Save As")'s (menu "Save As"))
                tell process "Acrobat"
                    keystroke return
                    keystroke out_name
                    keystroke return
                    keystroke "r" using {command down}
                end tell
            end tell
            close document 1
        end tell
    end if
end run

Then you can run this with something like:

optimizepdf path/to/input.pdf simple-output-name

overwrite warning: this will overwrite the output file (and potentially files named similarly if the keystrokes fail or get garbled).

Oddly, it seems to work fastest if the input document is not already open in acrobat pro.

This code above is written for Acrobat Pro Version 10.1.16.

Update: Here’s a legacy version for Acrobat Pro Version 9.5.1

#!/usr/bin/osascript
on run argv
    if (count of argv) < 2 then
        do shell script "echo " & "\"optimizepdf path/to/input.pdf simple-output-name\""
    else
        set p to item 1 of argv
        set out_name to item 2 of argv
        set abs to do shell script "[[ \"" & p & "\" = /* ]] && echo \"" & p & "\" || echo \"$PWD/\"" & p & "\"\""
        set a to POSIX file abs
        tell application "Adobe Acrobat Pro"
            activate
            open a
            tell application "System Events"
                click menu item "PDF Optimizer..." of ((process "Acrobat")'s (menu bar 1)'s ¬
                    (menu bar item "Advanced")'s (menu "Advanced"))
                tell process "Acrobat"
                    keystroke return
                    keystroke out_name
                    keystroke return
                    keystroke "r" using {command down}
                end tell
            end tell
            close document 1
        end tell
    end if
end run

Run executable in debugger immediately, return if successful

January 2nd, 2016

Here’re the flags for the lldb debugger to run a binary my_bin in the debugger immediately and return to the prompt if there were no errors. But if, say, an assertion fires, then it will stop as usual:

lldb -b -o r my_bin