Minkowski Portal Refinement References 2014-06-09

Original Reference

The Minkowski Portal Refinement method, also known as XenoCollide was developed by Gary Snethen (Xeno). As far as I know the original implementation in 3D is only described in Game Programming Gems 7 where working source code was also provided.

Source Code

As of this writing these are the main implementations that I found online:

LibCCD

Library for collision detection between two convex shapes

Jitter Physics

Jitter physics is a realtime physics engine for .Net

MPR2D

Convergence Behavior of Several Solvers in GAMS and Matlab 2014-06-05

In this post I wanted to document the behavior of several different numerical methods using a set of benchmark test problems.

Test Problems

  • Ball sliding on plane
  • Block sliding on plane
  • Block sliding from rest on incline
  • Block coming to resting on incline
  • Ball falling on stack of 20 balls

Solvers

Solver (Matlab)   Solver (Gams)
Nesterov   Conopt
Barzilai-Borwein   IPopt
Jacobi   Path

OpenGL text without any external libraries 2014-05-30

In the world of OpenGL, dealing with text is not always straightforward. GLUT is one method but it’s becoming old and in some cases deprecated (OSX 10.9). The freetype2 library is one method for generating text, using this library isn’t difficult but getting the best performance requires generating an “Atlas” for your font. An atlas is essentially a texture that contains every single character for a font at a given font size along with information on how to access that character. There are a few libraries that can generate an atlas for you, freetype-gl being one of them.

There is an alternative that in my mind is more portable and easier to use. freetype-gl comes with several awesome little demos on how to use the library, it also comes with a small executable called makefont that generates a header file with all of the needed information.

Provide it with a path for a .ttf font, the name of the header file, the font size and the variable name in the header that you will access it with.

makefont [--help] --font <font file> --header <header file> --size <font size> --variable <variable name>

If you find that the texture size is too small go into the code for makefont.c and change the following line so that it has the size you require. the default was set to 128x128 and I changed it to 256x256 . If your texture size cannot contain the full font, characters will be missing. Look at the output of the makefont command to make sure that characters are not missing.

texture_atlas_t * atlas = texture_atlas_new( 256, 256, 1 );

There is a demo called demo-makefont that demonstrates usage of this file for classic GL, modern GL usage with shaders is slightly different.

Shaders

Lets begin with the shaders and that get that out of the way

Vertex:

OpenGL GLSL shader as a string 2014-05-29

One annoyance that I have with GLSL shaders is that the vertex and fragment shader files must be placed into the directory with the binaries (or some other path accessible by the program). There are alternatives that involve using a resource manager but for smaller programs this seems like overkill.

One solution is to make a string out of the shader and include it with the code. The major problem with this is that editing the shader becomes a bit more tedious. One solution which I will discuss here involves converting the shader at compile time into a header and including it into the binary/library. I am using CMake for my build system which makes it trivial to do this.

References

GLSL Shader to Header

Cmake Embed Resources

Using these two posts you should be able to figure everything out but I wanted to describe in detail the full process.

Cmake

Cmake takes care of the heavy lifting and determines whether not not the header file needs to be generated. In my build system I have the shaders stored in a “resource” folder in my ${CMAKE_SOURCE_DIR} and the header files will be generated in the ${CMAKE_BINARY_DIR}.

embedfile.cpp

This awesome little piece of code was written by the user ScottManDeath from this post. I made a small modification and got rid of the debug wait for user input and made the char array a const.

The program takes three arguments:

Complementarity Frictional Contact In GAMS 2014-05-19

The purpose of this post is to detail work done by Dan Melanz and I on the topic of solving frictional contact problems using the General Algebraic Modeling System (GAMS)

The best way to describe GAMS is that it is a language and framework for writing mathematical programming and optimization problems. GAMS can solve many different classes of problems, in this post the Nonlinear Programming (NLP), Quadratically Constrained Program (QCP) and Extended Mathematical Program (EMP) problem types will be discussed.

References

These papers provide more details about the various formulations used in this post.

Primal Model:

V. Acary and F. Cadoux, “Applications of an Existence Result for the Coulomb Friction Problem,” Recent Advances in Contact Mechanics, pp. 45–66, 2013.

V. Acary, F. Cadoux, C. Lemaréchal, and J. Malick, “A formulation of the linear discrete Coulomb friction problem via convex optimization,” Z. angew. Math. Mech., vol. 91, no. 2, pp. 155–175, Feb. 2011.

F. Bertails-Descoubes, F. Cadoux, G. Daviet, and V. Acary, “A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies,” ACM Transactions on Graphics, vol. 30, no. 1, pp. 1–14, Jan. 2011.

Dual Model:

M. Anitescu and G. D. Hart, “A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction,” Int. J. Numer. Meth. Engng., vol. 60, no. 14, pp. 2335–2371, Aug. 2004.

A. Tasora and M. Anitescu, “A complementarity-based rolling friction model for rigid contacts,” Meccanica, vol. 48, no. 7, pp. 1643–1659, Sep. 2013.