# Chaman Singh Verma

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

 Major projects and Publications CV 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.

• Jaal: An Integrated Geometry Processing Toolkit:  This software integrates various geometric processing and meshing algorithms. It is written in C++ with an objectivity of multi-core parallelization with TBB,   CilkPlus, OpenMP and MPI libraries. More than 50 open-source software (CGAL, libIGL, diffusion geometry etc) have been integrated and interfaces simplified
• The objectives of the RelationNetwork are creation, manipulation, and study of the structure , dynamics of complex social networks. It integrates various functions of Boost Graph library, NetworKit, GraphChi, SNAP, and GraphViz software. This software uses in-memory BerkeleyDB as backend storage and extremely large graphs (order of Terabytes on a home desktop). Many hash-functions such has Cookoo hashing and Locally Sensitive hashing have been implemented to map graph entities to the database. Many expander graph generation, spectral clustering and graph analysis algorithms have been parallelized using TBB, CilkPlus, and Intel Performance library.
• This Applied Topology Network toolkit integrates algorithms in Dionysus, Gudhi, PHAT, CTL, Perseus, Chomp etc software. Many of the algorithms have been rewritten to take advantages of the latest C++14 features and the Boost library. Similar to RelNet software this software supports out-of-core computations using BerkeleyDB as a storage engine.
• JDebugging computational geometry algorithms can be very painful. This software is aimed to visualize geometric structures in all the three software listed above, in addition, to allowing debugging geometric algorithms in 2D and 3D by various slicing, cutting, coloring, and animation tools.
• The objective of this project is to rewrite, improve, provide better documentation and tutorial to useful but not upgraded software found on the Internet. This list also includes new software which require better software engineering in order to be useful to the developers.

### Publications:

 Project Short Description 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 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 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 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 Experimental studies on large-scale combinatorial multi-grid Laplace solvers: 7 2D mesh deformations: 8 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 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 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: 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.