This is my PhD

I completed my doctorate in Engineering Science at the University of Oxford in 2017. A journey that lasted 4 long years.

Thesis

NEW DISTANCE ALGORITHMS FOR OPTIMISATION AND CONTACT MECHANICS PROBLEMS

My work presents new methods to compute the minimum distance between bodies in 3D. This is a very difficult problem that finds applications in computer graphics, robotics and engineering. I focused on computational mechanics where high accuracy is required and many geometrical primitives, often of different types, interact, deform and change topology. For these reasons, distance queries on arbitrary bodies are a major computational bottleneck to large engineering simulations. I designed a versatile framework that improves the speed and robustness at various level; firstly, by facilitating the coupling of different numerical methods, such as discrete and finite elements. Secondly, by exploiting spatial coherence and data caching. Lastly, by addressing the numerical instabilities caused by floating-point arithmetic. The contribution of this research is a set of three algorithms that can either work independently or combined into a hierarchical search. These are:

1. The Signed Volumes method: a new recursive procedure for point–simplex distance queries,
2. An improved version of the Gilbert-Johnson-Keerthi (GJK) algorithm for faster and more accurate distance queries between convex bodies; and,
3. A hybrid extrinsic-intrinsic hierarchy of bounding volumes for arbitrary representations of concave objects.

Download

Cite this research as:

Montanari, Mattia. 2017. 
“New distance algorithms for optimisation and contact mechanics problems” 
PhD thesis, University of Oxford.

and download from here.

Impact

Part of this research was referred for a technical note at SIGGRAPH 2017 by the Editor in Chief of ACM ToG. The publication and the video of the oral presentation are available at Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects. The paper was received well despite the presentation made by an inexperienced PhD student.

It is fair to say that the algorithms were also criticised later on and so, to promote transparency, I published the kernel in a library: openGJK which is freely available with interfaces for many languages. This relieved many objections and left a useful tool freely available - whilst some critics remain written in academic papers and leave no trace of code behind 😇.

Finite element solver

Here’s an example simulation of my algorithms in an in-house finite element method (FEM) engine.

This demonstrates the ability to handle large number of contacts, even self-collision on the knots, of deformable bodies. Note: The element used are the tetrahedrons, not shells, leading to a more accurate solution.

Comparison with commercial FEM code: LS-Dyna

The thesis describes the details of a simple comparison between the FEM in-house engine and LS-Dyna. The test case I picked is a simulation of particles (you can think of these as rocks, grains or weird pills). Below a side-by-side comparison of the two software - not that far after all.

If I had an army of professional software developers working for me over a decade, I could offer a fair runtime comparison between the two software. What I did compare is the scalability of the contact and the physics response.

The result that gave me confidence on the overall accuracy on such large-scale simulations, is the comparison of kinetic energy shown below. The curves are close to each other and therefore present a close representation of the physics.

Read more on this comparison in my thesis.