Chaman Singh Verma

Department of Computer Sciences,
University of Wisconsin-Madison
Madison, WI  53706.
E-mail(1)   : cverma@cs.wisc.edu
E-mail(2)   : csv610@yahoo.com
Phone        : 608-698-4729

logo


CV
 Major projects and Publications
 Short Projects
 Miscellaneous

Welcome:

I am currently a Ph.D. candidate in the department of computer science at UW-Madison. My primary advisor is Prof. Suresh Krishnan (Mechanical Engineering) and co-advisors are Prof. Vadim Shapiro (Computer Science) and Prof. Micheal Gleicher (Computer Science). I am expecting to graduate in July 2016. 

Research Interests:

  1. Parallel and Distributed Computing. Performance analysis, design of parallel algorithms, evaluation of various parallel programming languages and software libraries ( MPI, TBB, Cilk++ )
  2. Computational geometry : Mesh Generation and Processing. Applications of computational geometry algorithms in ad-hoc mobile networks and robotics.
  3. Applied Computational Topology : Topological data Analysis, Persistent homology calculations.
  4. Large Graphs Analysis and Data Mining : 
  5. Scientific visualization : (1) Visual tools to understand patterns in a large dataset and (2) Visual debugging tools for computational geometry algorithms.
  6. Computer Vision
  7. Machine Learning 

Major Projects (soon to be open-source):

For many years, I have been passionately exploring various sequential and parallel programming languages, reusable components, robust and reliable computations in computational geometry algorithms. The following four very large projects are being single-handedly developed by me.

Publications:


 Project
 Short Description
1
 allhex
 An All-Hex Meshing Strategy for Bifurcation Geometries in Vascular Flow Simulation
Chaman Singh Verma, Paul Fischer, Seung E. Lee, and F. Loth
14th International Meshing Roundtable, San Diego, 2006

Automatic hexahedral mesh generation is a notoriously hard problem. Currently, high-quality hex meshing is largely heuristic and require a customized solution. In this project, we provide an automatic hex generation in bifurcation geometries. We have used this method to generate hex meshes for Carotid arteries.




BioMesh Project 

Download Paper
3
 jaalpaper
 Jaal: Engineering a High-Quality All-Quadrilateral Mesh Generator:
Chaman Singh Verma, Tim Tautges
20th International Meshing Roundtable Conference, Paris, France, 2011

In this paper, we describe the implementation of an open source code (Jaal) for producing a high-quality, isotropic all-quadrilateral mesh for an arbitrary complex surface geometry. Two basic steps in this process are: (1) Triangle to quad mesh conversion using Suneeta Ramaswamy’s tree matching algorithm and (2) Global mesh cleanup operation using Guy Bunin’s one-defect remeshing to reduce irregular nodes in the mesh.These algorithms are fairly deterministic, very simple, require no input parameters, and fully automated yet produce an extremely high quality all-quadrilateral mesh (with very few 3 and 5 valence irregular nodes) for a large class of problems.




Download Paper
4
 FEA
 Towards FEA over Tangled Quads
Chaman Singh Verma, Krishnan Suresh
23th International Meshing Roundtable Conference, London, UK, 2014

Abstract:
In finite element analysis (FEA), a mesh is said to be tangled if it contains an element with negative Jacobin-determinant. Tangling can occur during mesh optimization and mesh morphing. Modern FEA, unfortunately, cannot handle such tangled meshes, i.e., it will lead to erroneous results. While significant progress has been made on untangling, there are no definitive untangling algorithms. Danczyk and Suresh recently proposed a theoretical extension to FEA such that one could accurately solve boundary value problems over such tangled meshes. However, their investigation was limited to simplicial meshes. In this paper, we consider the extension of the above framework to tangled quad meshes that pose additional challenges compared to simplicial meshes. These challenges are identified, and a tangling-framework is developed to address explicit quad tangling where quads are allowed to overlap but are required to be geometrically convex. Numerical examples illustrate the correctness of the proposed framework, opening new opportunities for meshing algorithms.

Download Paper
5
 mstpaper
 A robust Combinatorial Approach to Reduce Singularities in Quadrilateral Meshes:
Chaman Singh Verma, Krishnan Suresh,
24th International Meshing Roundtable, Austin, Texas, 2015

Journal Paper:   Special Issue on Mesh Generation, CAD

Abstract: There many automatic quadrilateral mesh generators that can produce high-quality mesh with low distortion. However, they typically generate a large number of singularities that could be detrimental to downstream applications. This paper introduces Minimum Singularity Templates (MST) to reduce the number of singularities in an existing pure quad mesh. These templates are easy to encode with high-level grammar rules for complete automation, or interactive control. The MST exploits two important properties of quadrilateral meshes: (1) every submesh has even number of quad edges on its boundary, and (2) every submesh with 3, 4 or 5 topological convex corners on its boundary has at most two interior singularities. The MST (1) does not change the boundary edges of the patch, (2) avoids corner picking on a patch and solving NP-hard internal matching algorithm to select divisions, (3) is extremely fast with time complexity of O(1) in template creation, and (4) has low memory footprint and is robust. To illustrate the concepts, we consider quadrilateral meshes generated using Abaqus, Gmsh, and Cubit, and reduce the singularities within these meshes.

Download Paper                                            
6
 cqmg
 CQMG: An Indirect Approach to Low Singularities and Bounded Distortion Quad Meshing:
Chaman Singh Verma, Krishnan Suresh

In the literature, many automatic quadrilateral mesh generation algorithms have been proposed and most of them produce a mesh with very high geometric qualities. However, very few algorithms control the number of singularities. In this paper, we are proposing a new indirect approach to quadrangulate a 2D domain with improved topological quality and bounded elements geometric distortions. In this method, we first transform a given triangle mesh into a low-quality quadrilateral mesh (which is trivial using 1-3 subdivision algorithm) and the apply three operations (1) Pillowing, which inserts new quadrilateral elements at the boundaries and (2) Dicing, which refine a chord in the quadrilateral mesh. If the chord is a boundary chord, or the dicing is partial, then four additional singularities are inserted into the mesh. (3) MST operations, reduce the singularities in the mesh. Usually, a few iterations of these steps results in a mesh with high topological and geometric qualities.



Download Paper : Waiting for approval from the publisher.
7
 amst
 Alpha-MST: A Robust Unified Algorithm for Quadrilateral Mesh Adaptation:
Chaman Singh Verma, Krishnan Suresh,

25th International Meshing Roundtable, Austin, Texas, 2016

Mesh adaptation plays a critical role in balancing computational eciency and numerical accuracy. Three types of mesh adaptation techniques exist today, namely, mesh improvement, mesh refinement and mesh simplification, and for each of these, several strategies have been proposed. Most of these strategies yield acceptable geometric mesh quality but provide limited control over topological quality.

In this paper, we introduce a unified algorithm for all three types of mesh adaptation for quadrilateral meshes. The algorithm builds upon the Minimum Singularity Templates (MST) idea proposed by the authors for improving the topological quality of a quadrilateral mesh. The MST is extended here to define the concept of an MST where a single parameter controls mesh adaptation: = 1 for mesh improvement, > 1 for mesh refinement, and < 1 for mesh simplification.The proposed algorithm generates mesh with high geometric and topological qualities. Further, it is non-hierarchical and stateless, and yet it provides an arbitrary level of mesh adaptation. Finally, since cyclic chords can play an important role in quadrilateral mesh adaptation, we provide a simple constructive algorithm to insert such chords using the MST. Several examples are presented that demonstrate the robustness, effectiveness, and versatility of the proposed concept and algorithm.


Download paper: Waiting for approval from the publisher.

Many high-quality quadrilateral meshes using our quad-mesh generator can be downloaded from here.

Short projects and Technical Reports:


 Project
 Short Description

untangle
Mesh Untangling:
Very often during mesh generation and mesh deformation mesh elements near the concave corners can get inverted i.e. the Jacobian of the element becomes negative. Such inversion can serious repercussions in graphics and FEM calculations. In the past, many non-linear optimization schemes were proposed to recover and/or avoid such inversions. However, most of these methods are computationally expensive and provide no guarantees on the convergence of the numerical methods.

In this project, we exploited two fundamental results from the theory (1) Any 2D curve can be deformed into a circular using curve shortening flow (Gregson' theorem) and (2) The harmonic map on a convex shape can be made inversion free.

Using these result, we have implemented a very simple mesh untangling algorithm. In the first phase of the algorithm, the boundary undergoes curve shortening flow until all the elements are inversion-free and in the second phase, a deformed shape in deformed back to the original mesh using the Locally-Injective-Mapping algorithm.

IMR24 Poster  Document     C++ Software   DataSet    Gallery
1
 compass
 OpenGL Compass:
While interactively modifying a shape precisely, we need to have some mechanism to provide the angle. Although it can be done using dialog box but it is elegant and simple if we can place a digital compass over the model. This software implements an OpenGL based digital compass which can be placed anywhere on the screen. To provide interaction, a user needs to place the mouse near the tip of the neddle.


Approximate shortest distance calculation in tangled meshes.

Classical Dijkstra's algorithm correctly calculates exact and approximate distances in a mesh only if the mesh in untangled. When the mesh contains even a few inverted elements, results are unpredictable. However, a slight modification in the FEM code, the limitation of using untangled mesh can be relaxed.

Document  C++ Software



Speculative Parallelization in Quadrilateral Mesh Clean-up Operations:

Singularities removal is essential to produce high-quality quadrilateral meshes. We had proposed Minimum Singularity Templates methods to reduce singularities using small topological convex patches. Very often, the input mesh has a large number of singularities and applying MST on smaller patches can be expensive. However, we can exploit the parallelism that exists among patches. If the patches do not overlap, many steps of MST can be performed in parallel. If patches overlap, then only one will be allowed to commit the changes and the remaining threads work is discarded.
3
 sproject3
 Transactional Memory in Parallel Delaunay Triangulation:

The sequential algorithm of Delaunay Triangulation is simple. It involves inserting vertices incrementally in the mesh. When a new vertex is inserted, the "Empty CircumCircle" property gets violated in a few triangles surrounding the vertex. Therefore, all such triangle which violates the Delaunay properties form a convex hole which must be remeshed. In large meshes such holes could be sparsely located which, indirectly, hide parallelism which could be efficiently allowing refilling  holes.






Download report
5
 rbf
 Large Scale Radial Basis functions and Iso-surface extraction.

Many radial basis functions generate dense matrices with a large condition number, therefore, is direct methods for solving the system of linear equations is the only way. However, solving dense large matrices can be prohibitively expensive both in terms of memory and execution time. To limit the size of the dense matrix, the geometric model must be sparsely sampled. How to choose such points which produce the least distance from the given point is often a non-trivial problem.

In this work, I implemented the  idea of "Geodesic Farthest Point Sampling (GFP)". In this approach, we start with fixed number of points sampled using  GFS and incrementally insert new points which produce the maximum deviation from the original point cloud set. After each selection, we solve the system of equations, extract the geometric surface from the RBF, and from the surface identify the points which are at the maximum distance. The whole process is computationally very expensive, but often it has to be done only once for a given model.

This application provides huge opportunities for parallelization on both shared and distributed memory machines. We use heterogeneous computational model using TBB and  GPU to solve the problem in reasonable time.
6
 sproject7
 Experimental studies on large-scale combinatorial multi-grid Laplace solvers:
7
 sproject8
 2D mesh deformations:
8
 project10
 Changing Chords Directions in a Quadrilateral mesh:

A theorem from Juvan, Malnic and Mohar says:

Let $F$ be a family of non-null homotopic closed curves on a surface $\sigma$ with $b \ge 0$ boundary components which are pairwise non-homotopic and pairwise disjoint. Then
\begin{center}
$\|F \|  \le max( 1, 2(g_\sigma-1) + 2b$
\end{center}

We provide a constructive algorithm to produce such curves which exploit chords in a quadrilateral mesh over the manifold. If two different chords intersect each other we apply Schwartz template to separate them. We iteratively apply this template until it becomes impossible to avoid intersections. Thereafter, we can choose different curves passing through the chords.
9
 project9
Curve Shortening Flows (CSF):

Two remarkable results of Gage-Hamilton-Grayson theorem are:

1. A non-intersecting planar curve will converge to a finite "round point".
2. If there are multiple curves in the domain undergoing CSF then they will never collide.

Although the mathematical proofs are difficult to understand, but we can visualize the result and understand the results quickly. I have implemented the Mokhtarian and Mackworth algorithm (may not be precise, but the final results are as per expectations) in C++.

CSF ( or Mean Curvature flow in 3D) can be used to solve one practical problem in "Mesh Untangling".
10
 project10
Catmull-Clark subdivision without modifying boundary.

The Catmull-Clark subdivision scheme is widely used in geometric modelling. It is also used to transform a quad-dominant mesh into an all-quad mesh. However, if there are boundary segments  in the model then this subdivision will subdivide the boundary segments also. Sometimes, we neither want to subdivide the boundary and still want to have an quadmesh. This is possible if we allow singularities in the mesh.

In this work, we first subdivide all the internal elements according to the standard Catmull-Clark scheme leaving elements adjacent to the boundary segments. This will create a quad-dominant mesh with non-quad elements will be adjacent to the boundary. In the second step, we have to find pairs of non-quad elements and create quad elements by collapsing them. The major challenge is to minimize the changes in the quad elements formed in the first stage because an arbitrary pairing could modify the global structure of the quad mesh. 




Disk Reorganization and File System Layout Visualization:

Schneider
Local Transformations in Hexahedral Meshing: A brief literature survey.


There are four common elements in numerical simulations today (1) Triangle (2) Quadrilateral (3) Tetrahedron (4) Hexahedron.  Trinagle and Tetrahedron are simplicial elements and quadrilaleral and hexahedron are  non-simplicial elements. While there have been significant advances in the generation of simplicial elements and only recently quadrilateral mesh generation algorithms showing maturity. Hexahedral mesh general is widely considered to the last "holy-grail" in the mesh generation community. In fact, very few concepts from 2D are extendable to 3D to generate hex meshes (surprisingly generating meshes in dimension higher than 3 are simpler).

In the left Figure, a famous problem of "Schneider Problem" is shown. It is a simple pyramid with a square base and four triangular sides.

Qs.  Divide the base into 4 quadrilaterals and each triangular face into 3 quadrilaterals. These quadrilaterals are called "boundary quadrilaterals". Now can we create hexahedral elements in this model without modifying the boundary quadrilaterals ?

It is conjectured that the "holy-grail" of hexahedral mesh generation can be resolved if we can find the solution to this simple problem. In the past, many attempts have been  made to create geometric valid hexahedral elements in this model, however, all known algorithms fail. Download 1529 elements solution and check yourself why hexahedral mesh generation is still an open problem even for toy examples.


Download my brief presentation on the hexahedral meshing.