Back to posts.

Delaunay Triangulation

There are many delaunay triangulation libraries, but not all have a good cross platform build sytem, some have memory leaks or others are just buggy. I've tested and worked with several libraries that provide triangulation, like:

From this list I found Triangle to work best for me because it's compact, is fast, compiles easily and doesn't have any dependencies. It takes some time to read through the documentation, which is mostly found in the triangle.h file.

Triangle comes ase a library and as a application. To use Triangle as a library and not as a command line tool, you need to add the triangle.c to your project. It's also important to know that you need to define some compiler flags when you want to embed the triangle.c in your project. I'm using single floating point precision and therefore added these definitions:

-DTRILIBRARY
-DSINGLE

Even when you use Triangle as a library and not as a command line tool you need to pass certain "flags" to the library. I found these the most important ones:

z: will use indices which start at 0 instead of 1.
Q: quiet, not verbose output
p: creates constrained delaunay (use this when you want to triangulate finger like shapes)
a: imposes a maximum triangle area constraint.

Some examples with flags:

zpa100

zp10000

za100

There are known issues with Triangle and the author is aware of this. The code below is a workaround for these issues. Below you can find the Triangulate class which is a thin wrapper around Triangle. The comments in Triangulate.h show an example of how to use the generated triangles. See this gist for an example of how to use this wrapper.

Triangulate.h

/*
---------------------------------------------------------------------------------
 
                                               oooo
                                               `888
                oooo d8b  .ooooo.  oooo    ooo  888  oooo  oooo
                `888""8P d88' `88b  `88b..8P'   888  `888  `888
                 888     888   888    Y888'     888   888   888
                 888     888   888  .o8"'88b    888   888   888
                d888b    `Y8bod8P' o88'   888o o888o  `V88V"V8P'
 
                                                  www.roxlu.com
                                             www.apollomedia.nl
                                          www.twitter.com/roxlu
 
---------------------------------------------------------------------------------
*/
 
#ifndef ROXLU_TRIANGULATE_H
#define ROXLU_TRIANGULATE_H
 
/*
 
  Triangulate
  ---------------------------------------
 
  - ! ADD THESE TO YOUR PREPROCESSOR FLAGS:
 
         -DTRILIBRARY
         -DSINGLE
 
  - ! AFTER CALLING `Triangulate::triangulate()` MAKE SURE TO CALL `Triangulate::free(out)` TO CLEAN MEMORY!
 
  - ! TRIANGLE MAY CRASH, SEE THIS PAGE: http://www.cs.cmu.edu/~quake/triangle.trouble.html
      WHEN YOU WANT TO TRIANGULATE A CONTOUR, A QUICK FIX WOULD BE TO NOT ADD EVERY 
      POINT, BUT E.G. EVERY 5TH ELEMENT.
 
  <example>
 
        Triangulate tri;
        struct triangulateio out;
        tri.triangulate("zpQ", out);
 
        std::vector<vec2> vertices;
 
        // Extract the triangles (you could use a GL element buffer 
        for(int i = 0; i < out.numberoftriangles; ++i) {
 
           int a = out.trianglelist[i * 3 + 0];
           int b = out.trianglelist[i * 3 + 1];
           int c = out.trianglelist[i * 3 + 2];
 
           vec2 pa(out.pointlist[(a * 2) + 0], out.pointlist[(a * 2) + 1]);
           vec2 pb(out.pointlist[(b * 2) + 0], out.pointlist[(b * 2) + 1]);
           vec2 pc(out.pointlist[(c * 2) + 0], out.pointlist[(c * 2) + 1]);
 
           vertices.push_back(pa);
           vertices.push_back(pb);
           vertices.push_back(pc);
        }
 
        tri.free(out);
 
  </example>
 
  Very thin wrapper around the [Triangle library](http://www.cs.cmu.edu/~quake/triangle.html).
 
     Important:
     ----------
 
     After calling Triangualate::triangulate(out), make sure to call Triangulate::free(out)
     to free up all allocated memory. Of course call Triangulate::free(out), after you've used
     the data.
 
     Usefull options
     ---------------
 
     The triangulate() options expects a string with a couple of characters; where each character 
     defines how the triangulation is done. These are the ones I use most often:
 
     - Q         Suppress verbose output
     - p         Use this when you want to create "hand" like shapes instead; it will fit the contour basically
     - a         Imposes a maximum triangle area. 
 
     See: http://www.cs.cmu.edu/~quake/triangle.switch.html for more infor.
 
     Examples:   
     ---------
     - tri.triangulate("zpQ", out);             See: http://farm6.staticflickr.com/5504/11995424136_da15c9c991.jpg
     - tri.triangulate("zpa100", out);          See: http://farm6.staticflickr.com/5530/11994959684_43678280ea.jpg
     - tri.triangulate("zpa10000", out);        See: http://farm4.staticflickr.com/3814/11994889643_2d5275765e.jpg
     - tri.triangulate("za100", out);           See: http://farm4.staticflickr.com/3828/11994889833_05cf0984a6.jpg
 
     Notes:
     -----
     You need to look into the source to figure out how to use the triangulation library in an application 
     as an library and not just the executable. Before you include the `triangle.h` file, you need to set some
     #defines, so include like this:
 
     <code>
         extern "C" {
         # define REAL float
         # define ANSI_DECLARATORS
         # define VOID void
         # include "triangle.h"
         }
     </code>
 
     Also add these to you compiler flags:
 
     <code>
     -DTRILIBRARY
     -DSINGLE
     <code>
 
     References:
     -----------
     [0] http://www.cs.cmu.edu/~quake/triangle.html
     [1] http://www.cs.cmu.edu/~quake/triangle.switch.html
     [2] http://www.math.umbc.edu/~rouben/2011-01-math625/triangle-demo2.c
 
 */
 
extern "C" {
# define REAL float
# define ANSI_DECLARATORS
# define VOID void
# include "triangle.h"
}
 
#include <vector>
#include <string>
 
#ifndef TRIANGULATE_MIN_DIST 
# define TRIANGULATE_MIN_DIST 10
#endif
 
#define TRIANGULATE_MIN_DIST_SQ (TRIANGULATE_MIN_DIST * TRIANGULATE_MIN_DIST)
 
namespace rx { 
 
// ----------------------------------------------------
 
struct segment_point { 
  segment_point(float x, float y, size_t dx) : x(x), y(y), dx(dx) { }
  float x;
  float y;
  size_t dx; 
};
 
struct tri_point {
  tri_point(float x, float y) : x(x), y(y) { }
  float x;
  float y;
};
 
bool is_equal(const segment_point& p1, const segment_point& p2);
bool lex_equal(const segment_point& p1, const segment_point& p2);
bool segment_sort(const segment_point& p1, const segment_point& p2);
 
// ----------------------------------------------------
 
class Triangulate {
 
 public:
  Triangulate();
 
  void add(float x, float y);                                     /* Add a point that you want to use to triangulate */
  bool triangulate(std::string opt, struct triangulateio& out);   /* Triangulate the points you added. We set the `struct triangulateio& out`. See Triangle documentation for the data which is set; or you see the example above */
  void free(struct triangulateio& out);                           /* Free the `struct triangulateio` that you passed to `triangulate()`. Make sure to call this!! */
  size_t size();                                                  /* Return the number of points added */
  void clear();                                                   /* Clear the points you've added */
 
 public:
  std::vector<segment_point> in_points;
};
 
inline size_t Triangulate::size() {
  return in_points.size();
}
 
inline void Triangulate::clear() {
  in_points.clear();
}
 
inline bool is_equal(const segment_point& p1, const segment_point& p2) {
 
  float dx = p1.x - p2.x;
  float dy = p1.y - p2.y;
  float d = (dx * dx) + (dy * dy);
 
  if(d < TRIANGULATE_MIN_DIST_SQ) {
    return true;
  }
 
  return false;
}
 
inline bool lex_equal(const segment_point& p1, const segment_point& p2) {
  return  (p1.x < p2.x) || ((p1.x == p2.x) && (p1.y < p2.y) ); 
}
 
inline bool segment_sort(const segment_point& p1, const segment_point& p2) {
  return p1.dx < p2.dx;
}
 
} // namespace rx 
 
#endif

Triangulate.cpp

#include <Triangulate.h>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <set>
 
namespace rx { 
 
// ---------------------------------------------------------------
 
Triangulate::Triangulate() {
}
 
void Triangulate::add(float x, float y) {
 
  segment_point p(x, y, in_points.size());
  in_points.push_back(p);
}
 
bool Triangulate::triangulate(std::string opt, struct triangulateio& out) {
 
  if(!in_points.size()) {
    return false;
  }
 
  std::vector<segment_point> sorted_points;
  std::vector<segment_point> clean_points;
 
  // sort + unique will remove lots of points we don't want
  std::sort(in_points.begin(), in_points.end(), lex_equal);
  std::vector<segment_point>::iterator it_unique = std::unique(in_points.begin(), in_points.end(), is_equal);
  std::copy(in_points.begin(), it_unique, std::back_inserter(sorted_points));
 
  // now remove other points which are still to close 
  for(size_t i = 0; i < sorted_points.size(); ++i) {
 
    bool can_add = true;
    segment_point& a = sorted_points[i];
 
    for(size_t j = 0; j < clean_points.size(); ++j) {
 
      segment_point& b = clean_points[j];
      float dx = a.x - b.x;
      float dy = a.y - b.y;
      float d = (dx * dx) + (dy * dy);
 
      if(d < TRIANGULATE_MIN_DIST_SQ) {
        can_add = false;
        break;
      }
    }
 
    if(can_add) {
      clean_points.push_back(a);
    }
  }
 
  // sort again, now on segment again.
  std::sort(clean_points.begin(), clean_points.end(), segment_sort);
 
  in_points.clear();
  std::vector<tri_point> tri_points;
 
  for(size_t i = 0; i < clean_points.size(); ++i) {
    segment_point& p = clean_points[i];
    tri_points.push_back(tri_point(p.x, p.y));
    in_points.push_back(segment_point(p.x, p.y, in_points.size()));
  }
 
  if(tri_points.size() < 3) {
    printf("Not enough points to triangulate.\n");
    return false;
  }
 
  std::vector<int> edges;
  for(size_t i = 0; i < tri_points.size() - 1; ++i) {
    edges.push_back(i);
    edges.push_back(i + 1);
  }
 
  edges.push_back(edges.back());
  edges.push_back(0);
 
  struct triangulateio in = { 0 } ;
 
  // initialize a nice clean out list
  out.pointlist = NULL;
  out.pointattributelist = NULL;
  out.pointmarkerlist = NULL;
  out.numberofpoints = 0;
  out.numberofpointattributes = 0;
  out.trianglelist = NULL;
  out.triangleattributelist = NULL;
  out.trianglearealist = NULL;
  out.neighborlist = NULL;
  out.numberoftriangles = 0;
  out.numberofcorners = 0;
  out.numberoftriangleattributes = 0;
  out.segmentlist = NULL;
  out.segmentmarkerlist = NULL;
  out.numberofsegments = 0;
  out.holelist = NULL;
  out.numberofholes = 0;
  out.regionlist = NULL;
  out.numberofregions = 0;
  out.edgelist = NULL;
  out.edgemarkerlist = NULL;
  out.normlist = NULL;
  out.numberofedges = 0;
  out.pointlist = NULL;
  out.pointmarkerlist = NULL;
 
  in.pointlist = (float*)&tri_points[0].x; 
  in.numberofpoints = int(tri_points.size());
 
  if(edges.size()) {
    in.segmentlist = &edges.front();
    in.numberofsegments = edges.size() / 2;
  }
 
  ::triangulate((char*)opt.c_str(), &in, &out, NULL);
 
  return true;
}
 
#define TRIANGULATE_FREE(e) { if (e) { ::free(e); e = NULL; } }
 
void Triangulate::free(struct triangulateio& out) {
 
  TRIANGULATE_FREE(out.pointlist);
  TRIANGULATE_FREE(out.pointmarkerlist);
  TRIANGULATE_FREE(out.pointattributelist);
  TRIANGULATE_FREE(out.trianglelist);                                         
  TRIANGULATE_FREE(out.triangleattributelist);
  TRIANGULATE_FREE(out.trianglearealist);
  TRIANGULATE_FREE(out.neighborlist);
  TRIANGULATE_FREE(out.segmentlist);
  TRIANGULATE_FREE(out.segmentmarkerlist);
  TRIANGULATE_FREE(out.holelist);
  TRIANGULATE_FREE(out.regionlist);
  TRIANGULATE_FREE(out.edgelist);
  TRIANGULATE_FREE(out.edgemarkerlist);
  TRIANGULATE_FREE(out.normlist);
 
  out.numberofpoints = 0;
  out.numberofpointattributes = 0;
  out.numberoftriangles = 0;
  out.numberofcorners = 0;
  out.numberoftriangleattributes = 0;
  out.numberofsegments = 0;
  out.numberofholes = 0;
  out.numberofregions = 0;
  out.numberofedges = 0;
}
 
} // namespace rx

NAT Types This is so exciting, in this article I dive into some of the different ways a NAT device translates addresses which is important for peer-to-peer connections.
Building Cabinets In this post I dive into the design and construction of a cabinet with an interact LED strip. I also explain how I dynamically change the colors of the LEDs over TCP/UDP.
Compiling GStreamer from source on Windows How to compile GStreamer on Windows from Source using Visual Studio 2019 and the meson build system.
Debugging CMake Issues In this post I explain a process you can follow to debug issues with CMake by focusing on a specific target and making the output verbose.
Dual Boot Arch Linux and Windows 10 How to install Arch Linux and Windows 10 Pro as dual boot. A step by step tutorial how to create bootable installers, partition and setup a dual boot menu.
Mindset Updated Edition, Carol S. Dweck (Book Notes) Paragraphs I marked from the book "Mindset" from Carol S. Dweck.
How to setup a self-hosted Unifi NVR with Arch Linux A step by step HOW-TO that explain show to setup a Unifi Video Controller with an NFS share with Arch Linux.
Blender 2.8 How to use Transparent Textures Follow this node setup when you want to use an image with transparency as a "sticker".
Compiling FFmpeg with X264 on Windows 10 using MSVC A couple of steps to compile FFmpeg on Windows using MSVC.
Blender 2.8 OpenGL Buffer Exporter The following Blender script creates a [name].h and [name].cpp for the selected object and stores the positions, normals and UVs.
Blender 2.8 Baking lightmaps Light maps are a cheap way to add a lot of realism to you static scenes and have been used forever.
Blender 2.8 Tips and Tricks Use Environment Map only for reflections; create a floor plane for a Product Render, diffuse texture for roughness and more!
Setting up a Bluetooth Headset on Arch Linux Learn how to setup a Sennheiser PXC 550 Bluetooth headset on Arch Linux.
Compiling x264 on Windows with MSVC Compile the excellent x264 source on Windows using MSYS2 and MSVC.
C/C++ Snippets Is a number divisible by four?
Reading Chunks from a Buffer Some thoughts on reading bytes from a file; handy for reading NALs.
Handy Bash Commands Bash scripts: removing white space, lowercase filenames, backup using tar, etc.
Building a zero copy parser Simple solution to parse data in a pretty performant way. Used this for a RTSP protocol parser.
Kalman Filter A very simple yet powerful filter which works great when you have to smooth noisy data. Used for the Nike Rise 2.0 project.
Saving pixel data using libpng Do you have raw RGBA data that you want to save? Use this snippet to save it into a PNG file.
Compile Apache, PHP and MySQL on Mac 10.10 Setup you own PHP, MySQL and Apache and with virtual document roots.
Fast Pixel Transfers with Pixel Buffer Objects Using Pixel Buffer Objects (PBO) for fast asynchronous data transfers and OpenGL.
High Resolution Timer function in C/C++ Wait...... wait.. fast high resolution timer funtions (Windows, Linux, Mac)
Rendering text with Pango, Cairo and Freetype My never ending obsession with font rendering. A complex beast to do well. Use Pango and FreeType for the heavy lifting.
Fast OpenGL blur shader Make things look blurry ... and fast using this OpenGL blur shader.
Spherical Environment Mapping with OpenGL An old trick to get great lighting effects using Environment Maps and OpenGL.
Using OpenSSL with memory BIOs OpenSSL is a great library with lots of abstractions. In this post I discuss how to break some of these abstractions and use your own memory buffers.
Attributeless Vertex Shader with OpenGL A simple way to render a fullscreen quad without a vertex buffer with OpenGL.
Circular Image Selector Some thoughts on a different way to select images from a huge collection in a compact UI.
Decoding H264 and YUV420P playback Using libav to demux and playback with OpenGL.
Fast Fourier Transform Analyse your audio using the Fastest Fourier Transform in the West.
OpenGL Rim Shader Pretty glowy edges using a GLSL rim shader.
Rendering The Depth Buffer Render the non-linear OpenGL Depth Buffer.
Delaunay Triangulation Do you need to triangulate some shape: use the “Triangle” library.
RapidXML RapidXML is a versatile and fast XML parser with a simple API. Check out these examples.
Git Snippets Some simple GIT snippets; added here to remind myself.
Basic Shading With OpenGL A couple of basic GLSL shaders with explanation.
Open Source Libraries For Creative Coding Collection of great open source libraries for you creative programming projects.
Bouncing particle effect Snippet that can be used to create a bouncy particle effect; basic, effective, simple but nice.
OpenGL Instanced Rendering Want to render thousands and thousands of objects? Use OpenGL instanced rendering. The solution...the only solution.
Mapping a texture on a disc Ever heard about projective interpolation related to texture mapping? Learn about this intertesting issue with OpenGL and texture mapping.
Download HTML page using CURL When you want a quick solution to perform a HTTP(S) request CURL is always a quick an simple solution. Check out this example code.
Height Field Simulation on GPU Although not a Navier-Stokes implementation ... still a very nice and enjoyable effect.
OpenCV Optical Flow: when doing anything with tracking you've probably heard of it. See this simple example code using OpenCV and OpenGL.
Some notes on OpenGL FBOs and Depth Testing, using different Attachment Points, a YUV420p shader, ...
Math Meaning of the Dot Product in 3D graphics, calculating a perpendicular vector using Sam Hocevar's solution, orientation matrix and more.
Gists to remember Some gists that I want to remember, often use, etc...
Reverse SSH Do you want to login, into a remote PC but the remote PC is behind a firewall? Then use this simple reverse SSH trick which doesn't require changing your firewall rules.
Working Set Having issues with your compiler? Or during linking? Check these common issues and their solutions. I also list several tools that you can use to get a some useful info.
Consumer + Producer model with libuv Example of a common Multi Threaded Consumer/Producer Model using LibUV.
Parsing binary data Learn about the basic of a binary protocol and how to create one easily yourself.
C++ file operation snippets Reading a file into a string, vector, checking the file size, change to a position, etc. A collection of C++ file operation snippets.
Importance of blur with image gradients Do you want to experiment with OpenGL and aligning Brush Strokes along Image Gradients? Then check out this post about the importance of blurring.
Real-time oil painting with openGL Code snippet for fake "oil painting" effect with OpenGL using instanced rendering.
x264 encoder Basic example on how to use libx264 to encode image data using libav
Generative helix with openGL Screenshots of a project I worked on with that generates a DNA helix.
Mini test with vector field Screenshots while experimenting with a vector field; nothing much to see here.
Protractor gesture recognizer Testing the amazing One Dollar $1 gesture recognizer. The simplest and very good gesture recognizer.
Hair simulation Example code that implements the "Fast Simulation of Inextensible Hair and Fur" paper from M. Müller, T.Y. Kim and N.Chentanez.
Some glitch screenshots Glitch screenshots.
Working on video installation Screenshots of some experiments of a video installation.
Generative meshes I enjoy creating physics based simulations and render them on high res. Here are some experiments I did a time ago.
Converting video/audio using avconv Examples that show you how to use avconv to manipulate video and audio files.
Auto start terminal app on mac Automatically start you application whe Mac boots and make sure that it restarts your app when it exists. Handy for interactive installations.
Export blender object to simple file format Export the selected object in Blender into a .h and .cpp file that prepresents the buffer.