ElliottOti.com

# Ocaml implementation of zlib Inflate algorithm

## Posted on 29.12.07 Programming Ocaml Graphics OpenGL Projects

In between the social duties usual during this time of the year I’ve been trying to work on and off on GLCaml. I’ve had some feedback from the (not very large) user base over the past few months and it’s clear that some changes are needed.

For instance, the use of enumerations is a pain, because OpenGL mixes enumerations and integers willy-nilly, and having to convert back-and-forth in Ocaml is just not worth the hassle. Also, although the use of Bigarrays is in my opinion mostly unavoidable, I’m trying to minimize usage where it is not strictly necessary.

A couple of weeks ago, Jon Harrop mailed that he had gotten GL shaders to work, albeit with some difficulty and hand tweaking. I’m taking the opportunity to test shaders and related bindings more thoroughly, but this will take some time.

I think the next release of GLCaml will have some fairly major changes; some cosmetic, some fundamental. Basically GL constants (glenums in GLcaml) will become ints, and as a result GL_ALL_CAPS notation will have to become gl_lower_case notation. But before I release it I’d like to test it reasonably well. Revise and revamp the documentation, examples and website as well. This might take a month or so, depending on free time.

What does all this have to do with Zlib’s inflate algorithm? Nothing. But about a month ago I implemented an Ocaml-only implementation of Zlib’s inflate algorithm (RFC 1951). It’s not the first one: Extlib has one, but using it requires pulling in a lot of other stuff as well. I was writing a pure-Ocaml PNG decoder (mostly done but very buggy, will finish it when I have the time), and needed a simple zlib decoder.

So I wrote one. The source code is available (under the BSD licence). It’s pretty compact: about 250 lines of code, including comments. Usage is very simple: pass a string containing data compressed with the zlib deflate algorithm, and a string large enough to contain the decompressed data, and it returns the same string with the decompressed data. `uncompress -> string -> string -> string`. I added a small, simple example to uncompress gzipped files.

The code is based more or less on the specs, with a peek every now and then at Andrew Church’s tinflate.c when I got stuck on some ambiguity or other. It’s pretty compact - 200 lines of code - and pretty slow: gunzip beats it by a factor of 10 to 100. Maybe if I have time I’ll try and optimize it. First I have to find the time to finish the PNG decoder. And GLCaml, of course.

# Collision detection: triangle-triangle intersection

## Posted on 08.08.07 Programming Ocaml Graphics

Collision detection is an important part of any physical simulation. The basis is formed by the intersection of primitives, and the triangle-triangle intersection test is one of the most commonly used tests.

As described in the CGA FAQ:

Let the two triangles be $T_1$ and $T_2$. If $T_1$ lies strictly to one side of the plane containing $T_2$, or $T_2$ lies strictly to one side of the plane containing $T_1$, the triangles do not intersect. Otherwise, compute the line of intersection $L$ between the planes. Let $I_k = T_k cap L$, for $k = 1$ and $2$, denote the interval of intersections between the triangles and the line. Either interval may be empty. $T_1$ and $T_2$ intersect if and only if $I_1$ and $I_2$ overlap.

The Ocaml implementation of this test can be viewed online. Compiling with the command `ocamlopt graphics.cmxa unix.cmxa collision.ml -o collision ` produces the following program:

A quick comparison with the canonical implementation by Thomas Moeller shows that my straightforward Ocaml implementation runs roughly 5 times as slowly as Moeller’s implementation in C.

My implementation currently handles coplanar triangles rather erratically, so I will either have to add a special function to check and handle coplanar triangles, or possibly check triangle normals for parallelism and perturb one of the triangles slightly to bring it out of plane before applying the normal test.

# Bead on wire hoop demo

## Posted on 29.07.07 Programming Ocaml Graphics

Previously, I had written a simple 1d spring demo.. The next logical step was extension to three dimensions (wholly trivial) and the addition of constraints.

To start with, I begin with the canonical problem: a bead on a round frictionless wire hoop. (This is also equivalent to modeling the bob of a simple rigid pendulum). This is a path constraint. Movement is free along the path, but prohibited in any other direction. This can be represented by a constraint vector and a path. The constraint vector is the local radius of curvature and is perpendicular to the free path. The path represents all the positions in space a particle under that constraint may occupy.

For a bead on a hoop, the constraint vector is simply the radius of curvature, and for a hoop this is a vector of constant magnitude pointing towards the center of the hoop.

Any force acting on the bead produces an acceleration and over a period of time dt a displacement dx. This displacement causes the particle to travel in a straight line to x0, and (often) deviate from the path. So a vector can be constructed starting at the (deviated) position x0 along the constraint vector. This vector will intersect the path at a point x1. At this position a new velocity vector can be constructed tangent to the path (i.e. perpendicular to the constraint vector), with the same magnitude as the velocity vector at x0 (with, however, a different direction).

Source code can be viewed online. Compile with `ocamlopt unix.cmxa graphics.cmxa physics.ml -o physics` or `ocamlc unix.cma graphics.cma physics.ml -o physics`

# Simple 1d spring demo

## Posted on 21.07.07 Programming Ocaml Graphics

While playing around with a number of simple integrators I wrote a quick 1 dimensional spring demo. Four point spring unit masses are animated using various methods of evaluation (simple Euler, Newton-Stormer-Verlet, 4th order Runge-Kutta and a simple explicit Verlet integrator.

All four methods have the tendency to explode over time, although the Euler integrator does that the easiest. Somewhat to my surprise both Verlet integrators are more stable than the 4th order Runge Kutta integrator.

Source code can be viewed online. Compile with `ocamlopt unix.cmxa graphics.cmxa physics.ml -o physics ` or `ocamlc unix.cma graphics.cma physics.ml -o physics `

# Using OpenGL with native OCaml Graphics

## Posted on 12.02.07 Programming Ocaml Graphics OpenGL

I’ve always thought it would be nice if it were possible to use OpenGL calls in a window created with the Ocaml Graphics module. This would prevent the need to require external toolkits such as SDL or GLUT.

The Ocaml Graphics module is quite limited compared to SDL or GLUT, and also fills a slightly different niche, but it does come with a number of useful functions for drawing text, various graphics primitives, and for polling mouse and keyboard events. Simple standalone programs or demos can be created and distributed without requiring that the SDL or GLUT shared library be present on those systems.

To get an Ocaml window working with OpenGL I wrote a stub file in C and a few lines of ML code. When the test program is compiled and linked (download a gzipped tar file containing all necessary files here) it results in a program that runs as seen in the screenshot below.

The file win_stub.c and the few lines of ML code in the prologue of win_test.ml is all that is needed to use OpenGL within an Ocaml application. For the actual OpenGL bindings either GLCaml or lablgl will suffice.

Compiling:

For the provided examples, extract the files contained in glgraphics.tar.gz, and run make. Edit the makefile if necessary, to ensure that the line `CLIB=GL` is uncommented on Linux, and the line `CLIB=opengl32 gdi32` is uncommented if compiling on Windows with MinGW.

You need the file win_stub.c and the ML code contained in this section, specifically the function init_opengl () and the external functions init_gl’(), find_window() and swap_buffers (). Link the resultant executable with libGL.a on X11, opengl32.lib and gdi32.lib on Windows.

Usage:

• First set up your caml window with Graphics.open_graph ()
• Next, call the function init_gl ()
• After this you can (re)set the window title (if you set it previously it will be empty)
• Feel free to call any OpenGL calls you wish. lablgl, glcaml and camlgl may all be used.
• You may mix the Ocaml graphics functions with OpenGL.
• Call swap_buffers () any time you need to flip the contents of your back buffer to the screen.

How does it work?

The method used is similar, but not identical, on both Windows and X11. Ocaml does not expose the internals of the window (understandably, because they are highly platform-specific), so they have to be obtained via other means. On both X11 and Win32 you can obtain pointers to internal rendering surfaces of windows provided you can identify them by name. After opening the window with Graphics.open_graph (), the function init_opengl () has to be called. This function gives the current window a (hopefully) unique title Then C code is called which searches through all available windows for a window with that particular name, gets pointers to its internal structure (both Win32 and Xlib allow this) and sets it up for use as an OpenGL surface. This method works on Windows and X11; it may work on OS-X (with a little tweaking in the #defines) but I have not tested that.

# GLCaml moved to SourceForge

## Posted on 26.01.07 Programming Ocaml Graphics OpenGL

The GLCaml and SDLCaml bindings proved to be more popular than I had thought they would be, averaging a frenzied 2 downloads per day. (Really, people, restrain yourselves). Still, that’s been around 350 downloads since I first put it up in June ‘06.

So I’ve moved the project to glcaml.sourceforge.net. It’s now got its own website and project page. I’ve updated GLCaml to include support for OpenGL 2.1, which came out in August ‘06. The generated code has been cleaned up, and a minor bug fixed.

Why GLCaml instead of lablgl? Well, GLCaml consists of only three files (two, if you want to forego the .mli file), without any dependencies whatsoever, so you can drop them into whatever project you’re working on, and you’re ready to go. It supports OpenGL up to the latest version (2.1 at the moment), whereas lablgl only supports OpenGL 1.2. It’s a very thin wrapper, so it’s fast. The nomenclature is exactly the same as the native ‘C’ OpenGL API, so you can copy and paste code from books, tutorials and C/C++ projects without trouble.

Why not GLCaml? Well lablgl is elegant, typesafe, it’s been written by smarter people than I (you might want to take that into account before rushing to ship 50K copies of your GLCaml-powered 3D shooter), and it’s been around longer - thus better tested.

GLCaml had a companion library, SDLCaml, which was a similar compact binding to SDL (and in fact somewhat pre-dates GLCaml, since I’d worked on it on-and-off since April ‘06). I’ve decided not to make a separate project page for SDLCaml, but to leave it as a supported, optional library within the GLCaml project. I will continue to maintain and update it, but it won’t be as visible as GLCaml: I do think it’s incredibly handy, but the OCaml landscape is littered with good SDL bindings (like OcamlSDL and Jean-Christophe Filliatre’s ocamlsdl) and mine doesn’t add extremely much value, aside from being very compact.

# Ocaml bindings for OpenGL and SDL

## Posted on 30.06.06 Programming Ocaml Graphics OpenGL Projects

UPDATE: This project has moved to glcaml.sourceforge.net.

In the interests of reinventing the wheel where possible, I wrote OCaml bindings for the SDL libraries and OpenGL libraries over a couple of weekends.

The (automatically generated) OpenGL bindings cover OpenGL 1.1, 1.2, 1.3, 1.4, 1.5, 2.0 and most current non-platform-specific extensions. There are no dependencies whatsoever: the system opengl shared library is loaded dynamically, and the functions are called dynamically, so there is no need to link against import libraries.

The SDL bindings are fairly but not wholly complete; they are hand-written and functions are bound on an as-needed-by me basis. They are only dependent on the SDL main library and not on the mixer, ttf or image libraries. Because I wanted to have basic sound capabilities, the SDL_Audio modules are implemented, along with extra functions for panning and pitch shifting audio buffers.

This has been tested and works on Windows 2000, Windows XP, and Ubuntu Linux running on AMD64.
On Windows I use the mingw Ocaml compiler suite along with the msys shell; the source tarball contains makefiles that work as-is on the Windows mingw/msys port and under Linux. It will probably work as-is for the cygwin port of Ocaml, and will definitely need some tweaking to work under the Visual-C port.

# Cell Texture

## Posted on 12.05.06 Programming Ocaml Graphics

I saw this article on cellular textures and wrote an Ocaml cellular texture generator (source code, public domain).
Compile with
`ocamlc graphics.cma celltexture.ml -o cell`
or
`ocamlopt graphics.cmxa celltexture.ml -o cell`

The end result looks like this:

# Ocaml/GLFW silhouette demo

## Posted on 07.03.05 Programming Ocaml Graphics OpenGL

Adapted from the ObjectLine demo at frustum.org (great website, by the way), an example using Ocaml and GLFW to render a silhouette around an object (using the stencil buffer).