CGAL Point in Polyhedron Algorithm

The “point in polygon” or “point in polyhedron” is a classic computer graphics problem. The goal is to determine whether a given point is inside a polygon (in 2D) or a polyhedron (in 3D).

One solution to the problem is shooting a ray originating from the said point to an arbitrary direction and determine the number of intersections of the ray with the polygon or polyhedron. If the ray intersects the shape an odd number of times, then the point is inside the shape. Otherwise it is outside the shape.

There are problems associated with this approach. An important edge case is when the point is on the surface of the shape. Also, it is commonly advisable to shoot multiple rays instead of just one, and then do a majority voting.

Luckily, in CGAL the point in polyhedron test is very simple and you don’t have to worry about the edge cases! You can do the test using the Side_of_triangle_mesh class. A code snippet is shown below:


You can also determine whether the point is on the surface of the polyhedron or not.

“Unresolved external symbol” Errors when Compiling CGAL 4.7 Under Windows with Visual Studio 2013

I spent hours trying to compile CGAL 4.7 with Visual Studio 2013. Everything compiled on the first try with Visual Studio 2010 but for some reason I was unable to get it working with VS2013. CMake would create the solution files just fine and was able to resolve everything. However, when I attempted to build the confiugured solution I would get lots of “unresolved external” errors like this:

unresolved external symbol "__declspec(dllimport) class boost::system::error_category const & __cdecl boost::system::generic_category(void)

I followed this guide to the letter. I was sure Boost was being discovered just fine. I had everything in my PATH. After a while I figured out what my problem was! Although I wanted to build 64-bit binaries, I was selecting Visual Studio 12 2013 as my generator!! I was skimming every time I was selecting it so I wasn’t paying attention! I should’ve in fact selected Visual Studio 12 2013 Win64 as my generator. Doing that solved the problems.

Carve Error : “didn’t manage to link up hole!”

Carve is a fast and robust library for performing Constructive Solid Geometry (CSG) operations (boolean operations) on meshes.

In case the mesh is corrupted or has self-intersections, Carve will refuse to perform operations on it and will terminate with this error: “didn’t manage to link up hole!”.

To solve that, simply open the mesh in a mesh software (such as netfabb) and repair it.

CImg does not store pixels in the interleaved format


Took me hours before I found and read the documentation.

CImg stores pixels in a planer format (RRRR…..GGGG…..BBBB). For most tasks in CUDA, it’s much better to store the pixel values in the interleaved format (RGBRGBRGB……).

In order to do that, just call the permute_axes method of the CImg object:


After permutation, the width, height,  spectrum and depth values that are reported for CImg will all change.  To permute back (for displaying or saving) do this:


Where the values, are previously saved values (before doing any kind of permutation on the axes). This will undo any changes and now you can safely save the image or display it.

CImg instance from interleaved array (bitmap):

Now imagine you want to initialize a CImg object with an interleaved bitmap (say an OpenGL texture or what have you). In this case, you need to know the width and height of the image as well as the number of components. Also imagine that the spectrum is 1. To create a CImg object using this array you can do ( imageArray is the bitmap pointer):