Posts Tagged ‘mesh’

Background computation threads with igl::viewer::Viewer

Sunday, December 4th, 2016

Here’s a minimal example showing how to launch background computation threads for each mesh in a list of meshes. Meanwhile the main thread runs a mesh viewer with all meshes concatenated into one huge multi-component mesh. Whenever a computation thread signals that an update to the mesh needs to be made, the main thread will re-concatenate the meshes and update the viewer. In this example, the “computation” is determining how much to move a clock “hand” (random mesh).

Here’s the program running on the cow, cheburashka and knight models:

// Tiny example to demonstrate spawning a background computation thread for
// each mesh in a list and update the viewer when computation results in a
// change to (one of) the meshes.
// In this example, three meshes are read in and interpreted as "hands" of a
// clock. The "computation" is just a busy-wait until the hand should move
// (after one second, one minute, one hour). This is, of course, a terrible way
// to implement a clock.
// ./test libigl/tutorial/shared/{,,}
#include <igl/read_triangle_mesh.h>
#include <igl/point_mesh_squared_distance.h>
#include <igl/combine.h>
#include <igl/viewer/Viewer.h>
#include <Eigen/Geometry>
#include <thread>
int main(int argc, char * argv[])
  using namespace std;
  using namespace Eigen;
  // Read in k meshes (<=3 will be used)
  std::vector<Eigen::MatrixXd> VV(argc-1);
  std::vector<Eigen::MatrixXi> FF(argc-1);
  for(int i = 1;i<argc;i++)
    VV[i-1].col(0).array() -= VV[i-1].col(0).mean();
    VV[i-1].col(1).array() -= VV[i-1].col(1).minCoeff();
  bool continue_computing = true;
  // Flag to redraw and mutex to guard it
  bool redraw = false;
  std::mutex m;
  // After waiting `tic` seconds, rotate `V` by `deg` degrees
  const auto rot = [&continue_computing,&redraw,&m](
    const double tic, const double deg, Eigen::MatrixXd& V)
      // Let's watch this at 500x: Real clocks are slow.
      V *= Eigen::AngleAxisd(deg/180.*igl::PI,
        std::lock_guard<std::mutex> lock(m);
        redraw = true;
  // Launch background "computation" threads for each "hand" of the clock
  // std::ref is important, otherwise std::bind passes by copy
  std::vector<std::thread> threads;
    case 3:
    case 2:
    case 1:
    default: break;
  igl::viewer::Viewer v;;
  // Helper function to view k meshes
  const auto & set_meshes = [](
    const std::vector<Eigen::MatrixXd> & VV,
    const std::vector<Eigen::MatrixXi> & FF,
    igl::viewer::Viewer & v)
    Eigen::MatrixXd V;
    Eigen::MatrixXi F;
  // Continuous draw loop. TODO: trigger draws using glfwPostEmptyEvent
  v.core.is_animating = true;
  // Before every draw check if the meshes have changed. 
  v.callback_pre_draw = 
    [&redraw,&m,&VV,&FF,&set_meshes](igl::viewer::Viewer & v)->bool
          std::lock_guard<std::mutex> lock(m);
          redraw = false;
      return false;
  // Tell computation threads to stop
  continue_computing = false;
  // Join with computation threads: return to serial main thread.
  for(auto & t : threads) if(t.joinable()) t.join();

mesh clock igl viewer threads

This is pretty hacky, but it will allow me to use the standard libigl viewer for making comparisons of mesh-editing methods whose performances are very different.

Thingi10K: A Dataset of 10,000 3D-Printing Models

Tuesday, May 17th, 2016

thingi dataset

Qingnan “James” Zhou and I have released a technical report detailing the contents and methodology behind our ten thousand model thingi10k dataset.

Empirically validating new 3D-printing related algorithms and implementations requires testing data representative of inputs encountered in the wild. An ideal benchmarking dataset should not only draw from the same distribution of shapes people print in terms of class (e.g., toys, mechanisms, jewelry), representation type (e.g., triangle soup meshes) and complexity (e.g., number of facets), but should also capture problems and artifacts endemic to 3D printing models (e.g., self-intersections, non-manifoldness). We observe that the contextual and geometric characteristics of 3D printing models differ significantly from those used for computer graphics applications, not to mention standard models (e.g., Stanford bunny, Armadillo, Fertility). We present a new dataset of 10,000 models collected from an online 3D printing model-sharing database. Via analysis of both geometric (e.g., triangle aspect ratios, manifoldness) and contextual (e.g., licenses, tags, classes) characteristics, we demonstrate that this dataset represents a more concise summary of real-world models used for 3D printing compared to existing datasets. To facilitate future research endeavors, we also present an online query interface to select subsets of the dataset according to project-specific characteristics. The complete dataset and per-model statistical data are freely available to the public.

Boolean operations using generalized winding numbers

Tuesday, 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.

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

Wednesday, 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;
  if(FTC.size() == 0)
    FTC = F;
  Eigen::MatrixXi 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);

Write a triangle mesh to xml file in libigl using Eigen matrix templated on CGAL’s Exact Kernel

Thursday, December 17th, 2015

Lately I’ve been working with CGAL and its arbitrary precision kernel. These are convenient, but writing to standard floating point precision mesh file formats requires rounding. Here’s a relatively straightforward way of using libigl‘s existing xml serialization routines to write an Eigen matrix tempalated on the CGAL Exact kernels number type (e.g. a matrix of vertex positions) to an xml file (using ASCII or base64 binary encoding).

Notice that there’s a bit of gnarly template specialization that needs to be done inside the igl::xml::serialization_xml namespace. The structure of the libigl xml serialization code is unfortunately not very flexible.

#include <igl/xml/serialize_xml.h>
#include <Eigen/Core>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <iostream>

typedef CGAL::Epeck::FT EScalar;
typedef Eigen::Matrix<EScalar,Eigen::Dynamic,Eigen::Dynamic> MatrixXE;

namespace igl
  namespace xml
    namespace serialization_xml
      template <> inline void serialize(
        const MatrixXE & obj,
        tinyxml2::XMLDocument* doc,
        tinyxml2::XMLElement* element,
        const std::string& name)
        const std::function<std::string(const MatrixXE::Scalar &) > to_string = 
          [](const MatrixXE::Scalar & v)->std::string
      template <> inline void deserialize(
        MatrixXE & obj,
        const tinyxml2::XMLDocument* doc,
        const tinyxml2::XMLElement* element,
        const std::string& name)
        const std::function<void(const std::string &,MatrixXE::Scalar &)> & 
          from_string = 
          [](const std::string & s, MatrixXE::Scalar & v)

int main(int argc, char * argv[])
  using namespace std;
  using namespace Eigen;
  // Little 4-vertex, 2-face mesh with rational coordinates
  MatrixXE V(4,3),W;
    EScalar(1)/EScalar(3),  EScalar(1)/EScalar(13), EScalar(1)/EScalar(7),
    EScalar(1)/EScalar(7),  EScalar(1)/EScalar(3),  EScalar(1)/EScalar(13),
    EScalar(1)/EScalar(13), EScalar(1)/EScalar(7),  EScalar(1)/EScalar(3),
    EScalar(1)/EScalar(13), EScalar(1)/EScalar(7), -EScalar(1)/EScalar(3);
  MatrixXi F(2,3),G;

  // Write mesh
  const bool binary = false;
  // Write vertices, overwriting file (true)
  // Write faces to same file, appending (false)

  // Read mesh

  // Verify 
  cout<<"V "<<(V.isApprox(W,0) ? "equals" : "does not equal")<<" W"<<endl;

Here’s a little feeling for the overhead of this format on a big single-precision mesh cast to the exact kernel (the expressions are simple and short, so this is sort of a best case scenario):

|           | .ply|.xml ascii|.xml binary| .obj|
|File size: |172MB|     511MB|      330MB|288MB|
|Zip size:  |  68M|     134MB|       74MB| 81MB|
|Read time: |   8s|      270s|         9s|  32s|
|Write time:|  13s|       46s|        13s|  28s|

Nested Cages project page

Friday, October 2nd, 2015

nested cages bunny

We’ve posted a project page for our upcoming SIGGRAPH Asia paper Nested Cages, a collaboration between Leonardo Sacht, Etienne Vouga and myself.

Abstract: Many tasks in geometry processing and physical simulation benefit from multiresolution hierarchies. One important characteristic across a variety of applications is that coarser layers strictly encage finer layers, nesting one another. Existing techniques such as surface mesh decimation, voxelization, or contouring distance level sets do not provide sufficient control over the quality of the output surfaces while maintaining strict nesting. We propose a solution that enables use of application-specific decimation and quality metrics. The method constructs each next-coarsest level of the hierarchy, using a sequence of decimation, flow, and contact-aware optimization steps. From coarse to fine, each layer then fully encages the next while retaining a snug fit. The method is applicable to a wide variety of shapes of complex geometry and topology. We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for elastic simulation, and cage-based geometric modeling.

Mesh untangling in gptoolbox

Thursday, June 11th, 2015

I’ve reimplemented the first half of our paper, “Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces” [Sacht et al. 2013] as the untangle function in my gptoolbox. Our paper expands on the idea of “Interference-Aware Geometric Modeling” [Harmon et al. 2011]: given a self-intersecting mesh, run a mean-curvature flow until all self-intersections disappear and then reverse the flow but activate collision detection and response. My new implementation uses the conformalized mean curvature flow of “Can Mean-Curvature Flow Be Made Non-Singular?” [Kazhdan et al. 2012] and then reverse the flow using el topo, “Robust Topological Operations for Dynamic Explicit Surfaces” [Brochu & Bridson 2009]. For the reverse steps, I’m simply filtering the reversed flow “velocities”, then once returned to it’s original state, I run some iterations of ARAP gradient descent (with collision detection and response via el topo) to restore the intrinsic shape of the mesh.

Here’s the result on an example with a rather drastic self-intersection.

hand ok shrink inflate, untangle

For simpler models with lots of little self-intersections (like an otherwise nice subdivision surface), this method works very well. Unlike meshfix, this will not delete or remesh any part of the model.

Writing a mesh to an .obj file in a single line with Eigen

Wednesday, April 29th, 2015

I was recently revisiting our igl::writeOBJ code and realized that for simple meshes, the code for writing an .obj file can be really simple:

  V.format(IOFormat(FullPrecision,0," ","\n","v ","","","\n"))<<
  (F.array()+1).format(IOFormat(FullPrecision,0," ","\n","f ","","","\n"));

Update: And because why not, here’s a .off writer:

  "OFF\n"<<V.rows()<<" "<<F.rows()<<" 0\n"<<
  V.format(IOFormat(FullPrecision,0," ","\n","","","","\n"))<<
  (F.array()).format(IOFormat(FullPrecision,0," ","\n","3 ","","","\n"));

Edge collapse and mesh decimation in libigl

Thursday, April 16th, 2015

Libigl purposefully does not build itself around complicated mesh data-structures. This is freeing for many reasons: it’s very easy to include our code in an arbitrary project, functions are not artificially limited to manifold meshes, array based data structures are easily serialized and fast, matrix operations on vertex positions are directly exposed, etc.

mesh decimation in libigl

But our choice is also limiting. In particular, combinatorial changes to the mesh are potentially expensive and difficult to implement. Recently, I took a first stab at implementing an efficient edge-collapse routine for libigl. Indeed I’m seeing good performance: O(1) constant time for a single edge collapse and O(log m) time for cost-priority-queue-based collapses. The data structures are a little “messy” in the sense that when edges or faces disappear their rows are not deleted, but rather just redacted: entries are replaced with NULL values. This is because my approach is array-based and constant resizing would ruin performance. Luckily for edge-collapse, the number of elements only decreases. For edge-split I’ll have to think about amortized costs…

For now, check out the updated tutorial entry for libigl’s new mesh decimation and edge collapse features.

The code is “programmable” in the sense I expose function handles for computing edge costs and merged vertex placements. Though the default functions I currently provide are quite naive, this should support rather advanced “Progressive Meshes” style simplification with creases, sharp features, adaptivity, etc.

A Simple Method for Correcting Facet Orientations in Polygon Meshes Based on Ray Casting

Sunday, November 23rd, 2014

correct facet orientations on a bike, cell phone, chair, and truck

We’ve finally published our paper A Simple Method for Correcting Facet Orientations in Polygon Meshes Based on Ray Casting in the Journal of Computer Graphics Tools. The paper was written by Kenshi Takayama, Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung.

Abstract: We present a method for fixing incorrect orientations of facets in an input polygon mesh, a problem often seen in popular 3D model repositories, such that the front side of facets is visible from viewpoints outside of a solid shape represented or implied by the mesh. As opposed to previously proposed methods which are rather complex and hard to reproduce, our method is very simple, only requiring sampling visibilities by shooting many rays. We also propose a simple heuristic to handle interior facets that are invisible from exterior viewpoints. Our method is evaluated extensively with the SHREC Generic 3D Warehouse dataset containing 3168 manually designed meshes, and is demonstrated to be very effective.

You can find an implementation of this method in the embree extension of libigl: igl/embree/reorient_facets_raycast.h. If you store your mesh by its vertices in rows of a #V by 3 matrix V and triangle indices in the rows of a #F by 3 matrix F. Then you can quickly reorient your triangles to all point outward consistently with a single function call:

#include <igl/embree/reorient_facets_raycast.h>
Eigen::MatrixXI FF; // #F by 3 list of output triangle indices, some rows potentially reversed
Eigen::VectorXi I; // #F list of booleans revealing whether facet was reversed

As a preprocessor to our generalized winding numbers, this forms a powerful tool for determining the inside from outside for arbitrary meshes. This is especially important for creating volumetric tetrahedral meshes.