Skip to content

sparse marching cubes in core lib#1687

Merged
alecjacobson merged 4 commits intomasterfrom
sparse-mc
Feb 8, 2021
Merged

sparse marching cubes in core lib#1687
alecjacobson merged 4 commits intomasterfrom
sparse-mc

Conversation

@alecjacobson
Copy link
Copy Markdown
Contributor

Continues the migration of marching_cubes out of copyleft. (Now the only feature left in copyleft is root-finding).

This is probably not yet ready to merge. Notice that it's including march_cube.h in the middle of the two functions in marching_cubes.h (for dense and sparse grids respectively). I tried to pull this out properly as a function but I always get a performance hit (~1.25x).

I vaguely convinced it has to do with inlining, but I'm really not sure. I don't like including this implementation like this. I guess it's marginally better than copy-pasting duplicate code in each function.

Anyone care to take a look?

@alecjacobson
Copy link
Copy Markdown
Contributor Author

At the top of march_cube.h I have a minimal benchmark. I'll repeat here for convenience:

#include <igl/grid.h>
#include <igl/marching_cubes.h>
#include <igl/get_seconds.h>
#include <Eigen/Core>
#include <cstdio>
int main(int argc, char * argv[])
{
  const auto & tictoc = []()
  {
    static double t_start = igl::get_seconds();
    double diff = igl::get_seconds()-t_start;
    t_start += diff;
    return diff;
  };
  tictoc();
  Eigen::MatrixXd GV;
  const int s = 256;
  igl::grid(Eigen::RowVector3i(s,s,s),GV);
  GV.array() *= 2.0;
  GV.array() -= 1.0;
  const auto f = [&](const double x, const double y, const double z)->double
  {
    const double R = sqrt(x*x+y*y+z*z);
    const double s = atan2(sqrt(x*x+y*y),z);
    const double p = atan2(y,x);
    return pow(sin(s),2.)*(pow(cos(12.*s),3.)*0.1+pow(sin(6.*p),2)*0.2)+(R-0.5);
  };
  Eigen::VectorXd S(GV.rows());
  for(int i = 0;i<GV.rows();i++) { S(i) = f(GV(i,0),GV(i,1),GV(i,2)); }
  Eigen::MatrixXd SV;
  Eigen::MatrixXi SF;
  igl::marching_cubes(S,GV,s,s,s,0,SV,SF);
  tictoc();
  const int MAX_RUNS = 10;
  for(int r = 0;r<MAX_RUNS;r++) { igl::marching_cubes(S,GV,s,s,s,0,SV,SF); }
  printf("mc: %g secs\n",tictoc()/MAX_RUNS);
}

@jdumas
Copy link
Copy Markdown
Collaborator

jdumas commented Dec 28, 2020

Honestly I'd rather take a 1.25x performance hit and have a separate function, than keep the #include the way it is.

For the benchmark it might be worth to use Catch2's benchmark functionalities so we can run that the same way we run other unit tests.

@alecjacobson
Copy link
Copy Markdown
Contributor Author

The other easy option is copying-and-pasting the code. Ironically, that's exactly what #include is originally invented to prevent, but we have such a convention now that #include should have function definitions that any other use feels confusing.

Ideally, we could figure out how to wrap this up in function call (or maybe class?). I get the sense the performance hit might be compiler specific. My main hunch is that this has to do with inlining.

@jdumas
Copy link
Copy Markdown
Collaborator

jdumas commented Dec 29, 2020

I know that #include is just copying code around, but there are issues with readability and maintainability that outweigh the 1.25x performance hit imho. I'd rather have a shared function and take the performance hit, then optimize later on. If you really think having the best performance is key, then let's spend time on it and:

  1. Integrate the benchmark into our unit tests,
  2. Profile using available tools such as orbit, tracy or vtune,
  3. Compare with alternative implementations (the fastest implementation I've seen is the Flying Edge algorithm that is implemented in VTK/Paraview -- OpenVDB implementation is also pretty fast).

Maybe there's a low hanging fruit the function inlining, but imho this could be due to some other optimization that the compiler is doing when the code is "copied", like moving the lambda definition outside the for loop, etc. Hard to say without profiling for hotspots really.

@alecjacobson alecjacobson mentioned this pull request Dec 31, 2020
@alecjacobson alecjacobson merged commit c20c124 into master Feb 8, 2021
@alecjacobson alecjacobson deleted the sparse-mc branch February 8, 2021 19:36
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants