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.
Posts Tagged ‘mesh’
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.
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.
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:
ofstream("test.obj")<< 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:
ofstream("test.off")<< "OFF\n"<<V.rows()<<" "<<F.rows()<<" 0\n"<< V.format(IOFormat(FullPrecision,0," ","\n","","","","\n"))<< (F.array()).format(IOFormat(FullPrecision,0," ","\n","3 ","","","\n"));
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.
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.
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 igl::reorient_facets_raycast(V,F,FF,I);
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.
Here’s a little chuck of matlab code I use to make a surface mesh out of an image:
% load image as grayscale im = rgb2gray(imresize(im2double(imread('hans-hass.jpg')),0.75)); % create triangle mesh grid [V,F] = create_regular_grid(size(im,2),size(im,1),0,0); % Scale (X,Y) to fit image V(:,1) = V(:,1)*size(im,2); V(:,2) = (1-V(:,2))*size(im,1); V(:,3) = im(:);
This is code I end up re-writing every once in a while to demonstrate k-harmonic deformation on a simple 2d domain. The domain is just a square. This codes meshes the domain so that two inner circles show up in the edge set. Then I can select the vertices on and outside the outer circle and on and inside the inner circle to create a bump.
R = 1; r = 0.15; outer_sam = 200; inner_sam = ceil(outer_sam/R*r); inner_theta = linspace(0,2*pi,inner_sam+1)'; outer_theta = linspace(0,2*pi,outer_sam+1)'; P_inner = r*[cos(inner_theta(2:end)) sin(inner_theta(2:end))]; P_outer = R*[cos(outer_theta(2:end)) sin(outer_theta(2:end))]; E_inner = [1:size(P_inner,1);2:size(P_inner,1) 1]'; E_outer = [1:size(P_outer,1);2:size(P_outer,1) 1]'; P_bb = 1.1*[-R -R;-R R;R R;R -R]; E_bb = [1 2;2 3;3 4;4 1]; [P_bb,E_bb] = resample_polygon(P_bb,E_bb,2*pi*R/outer_sam); P = [P_inner;P_outer;P_bb]; E = [E_inner;size(P_inner,1)+[E_outer;size(P_outer,1)+E_bb]]; [V,F] = triangle(P,E,,'Flags',sprintf('-Yq32a%0.17f',(2*pi*R/outer_sam)^2),'Quiet'); tsurf(F,V)
I add the self-intersection computation code from our winding numbers project to libigl. I made a small example (
libigl/examples/intersections) that will compute and visualize all triangles participating in self-intersections in red. Here are the self-intersections of the Klein bottle:
I also wrote up a function to compute intersections between two meshes. Here’s that same example run on two meshes:
Here’s a very compact algorithm for determining the manifold patches of a given triangle mesh (V,F). I’m defining a manifold patch to be a collection of neighboring facets in F such that they’re union forms an edge-manifold submesh. A mesh is edge-manifold if no edge is shared by more than 2 facets.
Save this in a file called
function [C,A] = manifold_patches(F) % Compute connected components of facets connected by manifold edges. % % Inputs: % F #F by simplex-size list of facets % Outputs: % C #F list of component ids % % simplex size ss = size(F,2); assert(ss == 3); % List of all "half"-edges: 3*#F by 2 allE = [F(:,[2 3]); F(:,[3 1]); F(:,[1 2])]; % Sort each row sortallE = sort(allE,2); % IC(i) tells us where to find sortallE(i,:) in uE: % so that sortallE(i,:) = uE(IC(i),:) [uE,~,IC] = unique(sortallE,'rows'); % uE2F(e,f) = 1 means face f is adjacent to unique edge e uE2F = sparse(IC(:),repmat(1:size(F,1),1,ss)',1); % kill non-manifold edges uE2F(sum(uE2F,2)>2,:) = 0; % Face-face Adjacency matrix A = uE2F'*uE2F; % All ones A = A>0; % Connected components are patches %C = components(A); % alternative to graphconncomp from matlab_bgl [~,C] = graphconncomp(A); end
The “trick” if there is one, is that we first build an undirected edge to facet adjacency matrix. We zap-out any rows corresponding to edges with more than two incident facts. Then we “square” this matrix to give use a facet to facet adjacency matrix where two facets are neighbors iff the edge they share have only two incident facets. Finally we use a library call to compute the connected components of the graph induced by this adjacency matrix.
Here’s the result on an example, all manifold patches visualized with a unique pseudocolor:
And for comparison here’s a visualization of the graph connected components (defined per vertex, neighboring vertices share an edge).
I typically deal with piecewise linear functions defined over a triangle mesh (values defined per vertex). I can plot this over a 2d triangle mesh domain using the
I wrap this into my own function
tsurf to make it easier to call since I call them so often:
Sometimes I deal with piecewise constant functions (values defined per triangle). To plot this I use:
Or broken down:
% positions of all "Corners" C = V(F(:),:); % Scalar field defined at corners SC = repmat(S,size(F,2),1); % new disjoint triangle indices into C for each original triangle FC = bsxfun(@plus,size(F,1)*(0:size(F,2)-1),(1:size(F,1))'); % plot each triangle as piecewise linear function (each of which happens to be constant) tsurf(FC,[C SC]);