Problem in GLU Tessellation

I’ve faced a problem in GLU utility library. I’m using Qt 4.3.2 with OpenGL. The Compiler what I’m using is MinGW 5.1.0. The GLU tessellation logic is not detecting some self intersecting polygons.

Find below the sample tessellation program which takes the self intersecting polygon vertices as input. But it is not printing that the polygon is self intersecting. The pictorial representation of the invalid polygon is attached.

Please guide me what is wrong in the Tessellation logic.


/* main.cpp */

#include <QApplication>
#include <QObject>

#include "Tessellator.h"

int main (int argc, char *argv[])
{
   QApplication app (argc, argv);

   Tessellator_class tessellator;

   return app.exec ();
}


/*  Tessellator.h  */
#ifndef _TESSELLATOR_H_
#define _TESSELLATOR_H_

#include <QGLWidget>
#include <GL/gl.h>
#include <GL/glu.h>
#include <vector>

// For platform-independence of callback function declaration.
#ifndef CALLBACK
#define CALLBACK
#endif

class Tessellator_class: public QGLWidget
{

public:

   // Enums defining the types of original polygons.
   typedef enum
   {
      CONVEX_POLYGON = 0,
      NON_CONVEX_POLYGON,
      SELF_INTERSECTING_POLYGON,
      INVALID_POLYGON // Impossible polygons, or polygons with colinear points.
   } Polygon_type_enum;

   /////////////////////////////////////////////////////////////////////////////
   //
   // FUNCTION NAME: Tessellator_class
   //
   // PURPOSE:
   // Does nothing. Should not be called.
   //
   // PARAMETERS: (none)
   //
   /////////////////////////////////////////////////////////////////////////////
   Tessellator_class ();

   /////////////////////////////////////////////////////////////////////////////
   //
   // FUNCTION NAME: tessellate
   //
   // PURPOSE:
   // To tessellate the specified polygon, if non-convex. Otherwise, does
   // nothing.
   //
   // PARAMETERS:
   // vertex_ptr: Specifies the original vertices of the polygon to be
   //    tessellated; Contains x, y, and z coordinates per vertex.
   // vertex_count: The number of vertices specified in "vertex";
   //
   // RETURN VALUES:
   // CONVEX_POLYGON: if "vertex" specified a convex polygon;
   // NON_CONVEX_POLYGON: if "vertex" specified a non-convex polygon, and
   //    it was tessellated successfully;
   // INVALID_POLYGON: if "vertex_count" is less than 3, "vertex_ptr" is NULL or
   //    specifies an impossible polygon or a polygon with colinear points;
   //    or, if unsuccessful;
   /////////////////////////////////////////////////////////////////////////////
   static Polygon_type_enum tessellate (GLdouble * vertex_ptr, 
      unsigned int vertex_count);

   /////////////////////////////////////////////////////////////////////////////
   //
   // FUNCTION NAME: find_polygon_type
   //
   // PURPOSE:
   // To determine the type of the specified polygon. This is used chiefly to
   // determine if the specified polygon needs tessellation or not.
   //
   // PARAMETERS:
   // vertex_ptr: Specifies the original vertices of the polygon to be
   //    tessellated; Contains x, y, and z coordinates per vertex.
   // vertex_count: The number of vertices specified in "vertex";
   //
   // RETURN VALUES:
   // CONVEX_POLYGON: if "vertex" specified a convex polygon;
   // NON_CONVEX_POLYGON: if "vertex" specified a non-convex polygon, and
   //    it was tessellated successfully;
   // INVALID_POLYGON: if "vertex_count" is less than 3, "vertex_ptr" is NULL or
   //    specifies an impossible polygon or a polygon with colinear points;
   //    or, if unsuccessful;
   //
   // NOTES:
   // Call this function only if the polygon was tessellated (i.e., if
   // "tessellate ()" had returned NON_CONVEX_POLYGON.
   //
   /////////////////////////////////////////////////////////////////////////////
   static Polygon_type_enum find_polygon_type (
      const GLdouble * vertex_ptr, unsigned int vertex_count);

   /////////////////////////////////////////////////////////////////////////////
   //
   // FUNCTION NAME: ~Tessellator_class
   //
   // PURPOSE:
   // To destrory this object and deallocates all owned memory.
   //
   /////////////////////////////////////////////////////////////////////////////
   ~Tessellator_class ();

protected:

   void initializeGL ();

private:

   // A structure for 3D vertices.
   typedef struct
   {
      float x;
      float y;
      float z;
   } Vertex3_type;

   // The Tesselator object required for tessellation using GLU.
   static GLUtesselator * s_tess_obj_ptr;

   static void CALLBACK begin_callback (GLenum which);

   static void CALLBACK end_callback (void);

   static void CALLBACK vertex_callback (GLvoid * vertex_ptr);

   static void CALLBACK error_callback (GLenum errorCode);

   static void CALLBACK combine_callback (GLdouble coords [3],
      void * vertex_data [4],
      GLfloat weight [4],
      void * * out_data);

   static bool s_is_self_intersecting_polygon;
};

#endif // _TESSELLATOR_H_


/*  Tessellator.cpp  */
#include "Tessellator.h"

#include <vector>
#include <QGLWidget>
#include <GL/gl.h>
#include <GL/glu.h>
#include <math.h>

// For platform-independence of callback function declaration.
#ifndef CALLBACK
#define CALLBACK
#endif

GLUtesselator * Tessellator_class::s_tess_obj_ptr = NULL;
bool Tessellator_class::s_is_self_intersecting_polygon = false;

//public static std::vector <Vertex3_type *> vertices;

Tessellator_class::Tessellator_class () : 
   QGLWidget ()
{
   // Create a GLUtesselator object, if not already created.
   if (s_tess_obj_ptr == NULL)
   {
      // Creating a GLUtesselator object, if not already created.
      s_tess_obj_ptr = gluNewTess ();

      if (s_tess_obj_ptr != NULL)
      {
         // Registering the GLU Tessellation callback functions.

         gluTessCallback (s_tess_obj_ptr, GLU_TESS_BEGIN,
            (void (__stdcall *) (void)) begin_callback);
         gluTessCallback (s_tess_obj_ptr, GLU_TESS_END,
            (void (__stdcall *) (void)) end_callback);
         gluTessCallback (s_tess_obj_ptr, GLU_TESS_VERTEX,
            (void (__stdcall *) (void)) vertex_callback);

         gluTessCallback (s_tess_obj_ptr, GLU_TESS_COMBINE,
            (void (__stdcall *) (void)) combine_callback);
         
         gluTessCallback (s_tess_obj_ptr, GLU_TESS_ERROR,
            (void (__stdcall *) (void)) error_callback);

         gluTessProperty (s_tess_obj_ptr, GLU_TESS_BOUNDARY_ONLY, GL_FALSE);
      }
   }

   //const int VERTEX_COUNT = 4;
   const int VERTEX_COUNT = 11;

   // Polygon Data.
   GLdouble * vertex3_ptr = new GLdouble [VERTEX_COUNT * 3];

   /*vertex3_ptr [0] = 200.0f; vertex3_ptr [1] = 500.0f; vertex3_ptr [2] = 0.0f;
   vertex3_ptr [3] = 200.0f; vertex3_ptr [4] = 100.0f; vertex3_ptr [5] = 0.0f;
   vertex3_ptr [6] = 400.0f; vertex3_ptr [7] = 100.0f; vertex3_ptr [8] = 0.0f;
   vertex3_ptr [9] = 100.0f; vertex3_ptr [10] = 250.0f; vertex3_ptr [11] = 0.0f;*/

   /*vertex3_ptr [0] = 50.0f; vertex3_ptr [1] = 50.0f; vertex3_ptr [2] = 0.0f;
   vertex3_ptr [3] = 200.0f; vertex3_ptr [4] = 50.0f; vertex3_ptr [5] = 0.0f;
   vertex3_ptr [6] = 50.0f; vertex3_ptr [7] = 200.0f; vertex3_ptr [8] = 0.0f;
   vertex3_ptr [9] = 200.0f; vertex3_ptr [10] = 200.0f; vertex3_ptr [11] = 0.0f;*/

   /*vertex3_ptr [0] = 100.0f; vertex3_ptr [1] = 500.0f; vertex3_ptr [2] = 0.0f;
   vertex3_ptr [3] = 500.0f; vertex3_ptr [4] = 500.0f; vertex3_ptr [5] = 0.0f;
   vertex3_ptr [6] = 100.0f; vertex3_ptr [7] = 100.0f; vertex3_ptr [8] = 0.0f;
   vertex3_ptr [9] = 500.0f; vertex3_ptr [10] = 100.0f; vertex3_ptr [11] = 0.0f;*/

   vertex3_ptr [0] = 200.0f; vertex3_ptr [1] = 200.0f; vertex3_ptr [2] = 0.0f;
   vertex3_ptr [3] = 180.0f; vertex3_ptr [4] = 150.0f; vertex3_ptr [5] = 0.0f;
   vertex3_ptr [6] = 400.0f; vertex3_ptr [7] = 180.0f; vertex3_ptr [8] = 0.0f;
   vertex3_ptr [9] = 400.0f; vertex3_ptr [10] = 400.0f; vertex3_ptr [11] = 0.0f;
   vertex3_ptr [12] = 180.0f; vertex3_ptr [13] = 400.0f; vertex3_ptr [14] = 0.0f;
   vertex3_ptr [15] = 80.0f; vertex3_ptr [16] = 200.0f; vertex3_ptr [17] = 0.0f;
   vertex3_ptr [18] = 150.0f; vertex3_ptr [19] = 80.0f; vertex3_ptr [20] = 0.0f;
   vertex3_ptr [21] = 450.0f; vertex3_ptr [22] = 100.0f; vertex3_ptr [23] = 0.0f;
   vertex3_ptr [24] = 500.0f; vertex3_ptr [25] = 400.0f; vertex3_ptr [26] = 0.0f;
   vertex3_ptr [27] = 450.0f; vertex3_ptr [28] = 500.0f; vertex3_ptr [29] = 0.0f;
   vertex3_ptr [30] = 50.0f; vertex3_ptr [31] = 490.0f; vertex3_ptr [32] = 0.0f;

   // Tessellate Polygon.
   Polygon_type_enum polygon_type = tessellate (vertex3_ptr, VERTEX_COUNT);

   if (polygon_type == Tessellator_class::CONVEX_POLYGON)
   {
      printf ("
Convex Polygon");
   }
   else if (polygon_type == Tessellator_class::NON_CONVEX_POLYGON)
   {
      printf ("
Non Convex Polygon");
   }
   else if (polygon_type == Tessellator_class::SELF_INTERSECTING_POLYGON)
   {
      printf ("
Self Intersecting Polygon");
   }
   else if (polygon_type == Tessellator_class::INVALID_POLYGON)
   {
      printf ("
Invalid Polygon");
   }
}

Tessellator_class::Polygon_type_enum 
Tessellator_class::tessellate (GLdouble * vertex_ptr, unsigned int vertex_count)
{
   if ((vertex_ptr == NULL) || (vertex_count < 3u))
   {
      return (INVALID_POLYGON);
   }

   // Determining if tessellation is required, and tessellating if required.
   Polygon_type_enum type = find_polygon_type (vertex_ptr, vertex_count);

   if (type == NON_CONVEX_POLYGON)
   {
      gluTessBeginPolygon (s_tess_obj_ptr, NULL);
         gluTessBeginContour (s_tess_obj_ptr);
            for (unsigned int i = 0u; 
               (!s_is_self_intersecting_polygon) && (i < (vertex_count * 3u)); i += 3u) // * 3u gives coords count
            {
               gluTessVertex (s_tess_obj_ptr, & (vertex_ptr [i]), & (vertex_ptr [i]));
            }
         gluTessEndContour (s_tess_obj_ptr);
      gluTessEndPolygon (s_tess_obj_ptr);
   }

   // Checking if the polygon is self-intersecting.
   if (s_is_self_intersecting_polygon)
   {
      gluDeleteTess (s_tess_obj_ptr);
      s_tess_obj_ptr = NULL;
      return (Tessellator_class::SELF_INTERSECTING_POLYGON);
   }

   /*// Checking for any OpenGL errors that occured during tessellation.
   GLenum error = glGetError ();
   if (error != GL_NO_ERROR)
   {
      printf ("
OpenGL error %d in tessellate (). Tessellation might have failed.", error);

      return (INVALID_POLYGON);
   }*/

   return (type);
}

// To determine the type of the specified polygon.
Tessellator_class::Polygon_type_enum 
Tessellator_class::find_polygon_type (
   const GLdouble * vertex_ptr, unsigned int vertex_count)
{
   if ((vertex_ptr == NULL) || (vertex_count < 3u))
   {
      return (INVALID_POLYGON);
   }

   // A flag that indicates the type of the polygon through the course of the
   // loop below.
   int flag = 0;

   for (unsigned int i = 0u; i < vertex_count; ++ i)
   {
      Vertex3_type p0 = {vertex_ptr [i * 3 + 0], vertex_ptr [i * 3 + 1], 0.0f};
      const unsigned int I_P1 = (i + 1u) % vertex_count;
      Vertex3_type p1 = {vertex_ptr [I_P1 * 3 + 0], vertex_ptr [I_P1 * 3 + 1], 0.0f};
      const unsigned int I_P2 = (i + 2u) % vertex_count;
      Vertex3_type p2 = {vertex_ptr [I_P2 * 3 + 0], vertex_ptr [I_P2 * 3 + 1], 0.0f};

      Vertex3_type p1_p0 = {p1.x - p0.x, p1.y - p0.y, p1.z - p0.z}; // p1-p0
      Vertex3_type p2_p1 = {p2.x - p1.x, p2.y - p1.y, p2.z - p1.z}; // p2-p1
      const Vertex3_type & u = p1_p0; // Shorthand
      const Vertex3_type & v = p2_p1; // Shorthand

      // Calculating the Z aspect of the cross product of the adjacent edges.
      float pz = (u.x * v.y) - (u.y * v.x);

      if (pz < 0.0f)
      {
         flag |= 1;
      }
      else if (pz >= 0.0f)
      {
         flag |= 2;
      }
      if ((flag & 1) && (flag & 2))
      {
         return (NON_CONVEX_POLYGON);
      }
   }

   if ((flag == 1) || (flag == 2))
   {
      float exterior_angle_sum = 0.0f;
      const double PI = 3.14159265;

      for (unsigned int i = 0u; i < vertex_count; ++ i)
      {
         Vertex3_type A = {0.0f, 0.0f, 0.0f};
         Vertex3_type B = {0.0f, 0.0f, 0.0f};
         Vertex3_type C = {0.0f, 0.0f, 0.0f};

         if (i < vertex_count - 2)
         {
            A.x = vertex_ptr [(i + 1) * 3 + 0];
            A.y = vertex_ptr [(i + 1) * 3 + 1];
            A.z = 0.0f;

            B.x = vertex_ptr [i * 3 + 0];
            B.y = vertex_ptr [i * 3 + 1];
            B.z = 0.0f;

            C.x = vertex_ptr [(i + 2) * 3 + 0];
            C.y = vertex_ptr [(i + 2) * 3 + 1];
            C.z = 0.0f;
         }
         else if (i == vertex_count - 2)
         {
            A.x = vertex_ptr [(vertex_count - 1) * 3 + 0];
            A.y = vertex_ptr [(vertex_count - 1) * 3 + 1];
            A.z = 0.0f;

            B.x = vertex_ptr [(vertex_count - 2) * 3 + 0];
            B.y = vertex_ptr [(vertex_count - 2) * 3 + 1];
            B.z = 0.0f;

            C.x = vertex_ptr [0];
            C.y = vertex_ptr [1];
            C.z = 0.0f;
         }
         else if (i == vertex_count - 1)
         {
            A.x = vertex_ptr [0];
            A.y = vertex_ptr [1];
            A.z = 0.0f;

            B.x = vertex_ptr [(vertex_count - 1) * 3 + 0];
            B.y = vertex_ptr [(vertex_count - 1) * 3 + 1];
            B.z = 0.0f;

            C.x = vertex_ptr [3];
            C.y = vertex_ptr [4];
            C.z = 0.0f;
         }

         // Direction Vectors.
         Vertex3_type AB = {B.x - A.x, B.y - A.y, B.z - A.z};
         Vertex3_type AC = {C.x - A.x, C.y - A.y, C.z - A.z};

         // Dot product of AB and AC (AB.AC)
         double AB_AC_dot_product = AB.x * AC.x + AB.y * AC.y + AB.z * AC.z;

         // ||AB||
         double p1 = sqrt (AB.x * AB.x + AB.y * AB.y + AB.z * AB.z);
         // ||AC||
         double p2 = sqrt (AC.x * AC.x + AC.y * AC.y + AC.z * AC.z);
         // ||AB|| * ||AC||
         double p3 = p1 * p2;

         double cos_value = AB_AC_dot_product / p3;

         // acos (value) will give in radians.
         // Convert radians to degrees by multiplying it with 180 / PI.
         float interior_angle = acos (cos_value) * 180 / PI;

         float exterior_angle = 180 - interior_angle;

         exterior_angle_sum = exterior_angle_sum + exterior_angle;
      }

      if (exterior_angle_sum == 360.0f)
      {
         return (CONVEX_POLYGON);
      }
      else
      {
         return (INVALID_POLYGON);
      }
   }
   else
   {
      return (INVALID_POLYGON);
   }
}

// Callback function for beginning a contour.
void CALLBACK Tessellator_class::begin_callback (GLenum /*which*/)
{
}

// Callback function for defining new vertex of contour.
void CALLBACK Tessellator_class::vertex_callback (GLvoid * /*vertex_ptr*/)
{
}

// Callback function for ending a contour.
void CALLBACK Tessellator_class::end_callback (void)
{
}

// Callback function to handle self-intersecting polygons.
// It is an error if the polygon is self-intersecting.
// This function detects and reports this error.
void CALLBACK Tessellator_class::combine_callback (GLdouble coords [3],
      void * [4],
      GLfloat [4],
      void * *)
{
   s_is_self_intersecting_polygon = true;
}

// Callback function to report GLU tessellation errors.
void CALLBACK Tessellator_class::error_callback (GLenum /*errorCode*/)
{
   /*const GLubyte * errString = gluErrorString (errorCode);

   printf ("
GLU Tessellation Error: %s", errString);*/
}

void Tessellator_class::initializeGL ()
{
   glClearColor (0.0, 0.0, 0.0, 0.0);

   // Specifying byte packing for memory read by OpenGL.
   glPixelStorei (GL_UNPACK_ALIGNMENT, 1);

   // The initially-enabled smooth shading is currently not required.
   // Disabling it will improve performance.
   glShadeModel (GL_FLAT);
}

Tessellator_class::~Tessellator_class ()
{
   gluDeleteTess (s_tess_obj_ptr);
   s_tess_obj_ptr = NULL;
}