I am working on a triangulation application where I can click inside a frame triangle in a window to subdivide it in 3 triangles and so on. Therefore, everytime I add a point, I add two triangles to a structure defined as the class Triangle (see Triangle.h and .cpp). For each object triangle, I keep track of its ID, the indices of its 3 vertices and the indices of its 3 adjacent triangles where first vertex and first adjacent triangle are opposite.
I then draw every points and every triangles with GL_POINTS and GL_LINE_LOOP.
If I use glClear(GL_COLOR_BUFFER_BIT), the lines are flickering. If I don't use it, the flickering does not happen.
My main problem is that the triangle drawing is not consistent. When I click a new point inside a triangle, lines should be drawn between this point and the 3 points forming the triangle containing the said point. Sometimes it happens as it should, sometimes additional lines appear. I checked my structure and there is no error in my class Triangle. I verified each attributes individually for every point added and every update of the triangulation.
When I use drawTriangle function, I call 3 times glVertex2i(x1, y1) to correctly draw the triangle. I don't understand why 4-5 lines can be drawn at the same time. It also don't understand why it sometimes happen and sometimes not.
I think there is a conflict with my use of openGL... like I would be making calculations and updating my triangulation structure and openGL would draw partial results... I don't seem to have perfect control on the redisplay of the drawing with glutPostRedisplay...
Would double buffering solve my problem? Is there a way I can manage to call myself for an update of the drawing instead of relying on glutPostRedisplay and glutMainLoop and those sort of things.
/*-----------------------------------------
Name: main
Author: Michael Landry
Description: main program
Date: 2018-02-22
Version: 1.00
-------------------------------------------*/
#include <GL/glut.h>
#include <iostream>
#include <vector>
#include "functions.h"
#include "Point.h"
#include "Triangle.h"
GLfloat BLUE[3] = { 0,0,1 };
std::vector <Point> pointList;
std::vector <Triangle> triangleList;
int main(int argc, char **argv)
{
// Give directions to user
std::cout << "*** Welcome to the Delaunay Triangulation tool ***" << std::endl << std::endl;
std::cout << "Left click to insert a point to the triangulation or right click to exit." << std::endl << std::endl;
// Create the boundary triangle
Frame();
// Initialize GLUT display window
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize(SCREEN_WIDTH, SCREEN_HEIGHT);
glutInitWindowPosition(0, 0);
glutCreateWindow("Delaunay Triangulation");
// Call the display function for drawing
glutDisplayFunc(display);
glutReshapeFunc(reshape);
// Call the mouse callback function
glutMouseFunc(mouse);
glutIdleFunc(spindisplay);
glutMainLoop();
return 0;
}
/*-----------------------------------------
Name: functions
Author: Michael Landry
Description: functions for second lab
Date: 2018-02-22
Version: 1.00
-------------------------------------------*/
#ifndef FUNCTIONS_H_
#define FUNCTIONS_H_
#include "Point.h"
#include "Triangle.h"
const int SCREEN_WIDTH = 1366;
const int SCREEN_HEIGHT = 768;
void drawPoint(void);
void drawTriangle(void);
void display(void);
void reshape(int w, int h);
void spindisplay(void);
void mouse(int btn, int state, int x, int y);
void Frame(void);
bool inTriangle(const Point&);
void insert(const int);
int walk(const Point&);
#endif
/*-----------------------------------------
Name: functions
Author: Michael Landry
Description: functions for second lab
Date: 2018-02-22
Version: 1.00
-------------------------------------------*/
#include <GL/glut.h>
#include "Point.h"
#include "Triangle.h"
#include "functions.h"
#include <iostream>
#include <vector>
extern GLfloat BLUE[3];
extern std::vector <Point> pointList;
extern std::vector <Triangle> triangleList;
/*
Name: drawTriangle
Description: draw the triangulation
*/
void drawTriangle(void)
{
glColor3fv(BLUE);
glBegin(GL_LINE_LOOP);
for (size_t i = 0; i < triangleList.size(); i++)
{
// Extract the coordinates of the first point of the triangle
int x1 = pointList[triangleList[i].getS1() - 1].getX(); // -1 because the vector starts at 0
int y1 = pointList[triangleList[i].getS1() - 1].getY();
// Extract the coordinates of the second point of the triangle
int x2 = pointList[triangleList[i].getS2() - 1].getX();
int y2 = pointList[triangleList[i].getS2() - 1].getY();
// Extract the coordinates of the third point of the triangle
int x3 = pointList[triangleList[i].getS3() - 1].getX();
int y3 = pointList[triangleList[i].getS3() - 1].getY();
// Draw the triangle formed by the 3 points
glVertex2i(x1, y1);
glVertex2i(x2, y2);
glVertex2i(x3, y3);
}
glEnd();
glFlush();
}
/*
Name: drawPoint
Description: draw points in the window
*/
void drawPoint(void)
{
glColor3fv(BLUE);
glBegin(GL_POINTS);
for (size_t i = 0; i < pointList.size(); i++)
{
// Extract the coordinates of the point
int x = pointList[i].getX();
int y = pointList[i].getY();
// Draw the point
glVertex2i(x, y);
}
glEnd();
glFlush();
}
/*
Name: display
Description: prepare the window for display
*/
void display(void)
{
glClearColor(0.0, 0.0, 0.0, 1.0);
// glClear(GL_COLOR_BUFFER_BIT); // command is disabled to stop flickering
glLoadIdentity();
glPointSize(5);
drawPoint();
drawTriangle();
glFlush();
}
/*
Name: reshape
Description: reshape the window
*/
void reshape(int w, int h)
{
glViewport(0, 0, (GLsizei)w, (GLsizei)h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0.0, SCREEN_WIDTH, SCREEN_HEIGHT, 0, -1.0, 1.0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
}
/*
Name: spindisplay
Description: prepare for a redisplay
*/
void spindisplay(void)
{
glutPostRedisplay();
}
/*
Name: mouse
Description: detect left button click on mouse
*/
void mouse(int btn, int state, int x, int y)
{
if (btn == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
{
// Generate a new object point with the cursor coordinates on click event
Point newPoint(x, y, 1);
// Verify if the point is inside the boundary triangle and if it does not already exists in the list
if ((inTriangle(newPoint) == 1) && ((newPoint == pointList) == 0))
{
// Only add the point to the list if it is inside the boundary triangle
pointList.push_back(newPoint);
std::cout << "New point added" << std::endl;
std::cout << "x : " << x << " " << "y : " << y << std::endl;
std::cout << "Total number of points : " << pointList.size() << std::endl << std::endl;
// Find the triangle containing the new point
int triangleIndex = walk(newPoint);
std::cout << "Divide triangle number " << triangleIndex + 1 << std::endl << std::endl;
// Insert the new point in the triangulation
insert(triangleIndex);
std::cout << "ID S1 S2 S3 T1 T2 T3" << std::endl;
for (size_t i = 0; i < triangleList.size(); i++)
{
std::cout << triangleList[i].getID() << " " << triangleList[i].getS1() << " " << triangleList[i].getS2() << " " << triangleList[i].getS3() << " " << triangleList[i].getT1() << " " << triangleList[i].getT2() << " " << triangleList[i].getT3() << " " << std::endl;
}
std::cout << std::endl;
}
glutPostRedisplay();
}
if (btn == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
{
exit(1); // Exit the program
}
}
/*
Name: Frame
Description: create the initial boundary triangle
*/
void Frame(void)
{
// First point
Point myPoint1(SCREEN_WIDTH / 2, 100, 1);
pointList.push_back(myPoint1);
// Second point
Point myPoint2(100, SCREEN_HEIGHT - 100, 1);
pointList.push_back(myPoint2);
// Third point
Point myPoint3(SCREEN_WIDTH - 100, SCREEN_HEIGHT - 100, 1);
pointList.push_back(myPoint3);
// Create the first triangle of the list
Triangle triangleFrame(1, 1, 2, 3, 0, 0, 0);
triangleList.push_back(triangleFrame);
}
/*
Name: getDeterminant
Description: calculate the determinant of a 3 x 3 matrix
*/
int getDeterminant(const Point &point1, const Point &point2, const Point &point3)
{
// Form a 5 x 3 matrix containing the 3 triangle points
std::vector <Point> pointTriangle;
pointTriangle.push_back(point1);
pointTriangle.push_back(point2);
pointTriangle.push_back(point3);
pointTriangle.push_back(point1);
pointTriangle.push_back(point2);
// Calculate the determinant with the shoelace method
int detTriangle = 0;
int detTrianglePart;
for (int j = 0; j < 3; j++)
{
detTrianglePart = ((pointTriangle[j].getX() * pointTriangle[j + 1].getY() * pointTriangle[j + 2].getZ()) - (pointTriangle[j + 2].getX() * pointTriangle[j + 1].getY() * pointTriangle[j].getZ()));
detTriangle = detTriangle + detTrianglePart;
}
return detTriangle;
}
/*
Name: inTriangle
Description: test if a point is inside a triangle
*/
bool inTriangle(const Point& newPoint)
{
// Pre loop conditions
int k = 0; // counter
int detTriangle = -1;
int row = 3; // 3 points
int col = 3; // 3 coordinates
// Loop on all the points if the determinant stays negative
while ((k < row) && (detTriangle < 0))
{
// Initialize an object the 3 points
Point point1;
Point point2;
Point point3;
// Extract 2 points from the list of points
if (k == row - 1)
{
point1 = pointList[k];
point2 = pointList[k - row + 1];
point3 = newPoint;
}
else
{
point1 = pointList[k];
point2 = pointList[k + 1];
point3 = newPoint;
}
// Get the determinant of the triangle
detTriangle = getDeterminant(point1, point2, point3);
// Incrementation of the counter
k++;
}
// Output the position of the point
bool isInside = 0;
(detTriangle < 0) ? (isInside = 1) : (isInside = 0);
return isInside;
}
/*
Name: insert
Description: insert the new point and create 3 new triangles
*/
void insert(const int triangleIndex)
{
// Extract the Index of the new point
int newPointIndex = pointList.size();
// Create the line of the second new triangle
Triangle triangle2(triangleList.size() + 1, newPointIndex, triangleList[triangleIndex].getS3(), triangleList[triangleIndex].getS1(), triangleList[triangleIndex].getT2(), triangleList.size() + 2, triangleIndex + 1);
// Create the line of the third new triangle
Triangle triangle3(triangleList.size() + 2, newPointIndex, triangleList[triangleIndex].getS1(), triangleList[triangleIndex].getS2(), triangleList[triangleIndex].getT3(), triangleIndex + 1, triangleList.size() + 1);
// Get the adjacent triangles of the base triangle
int T1 = triangleList[triangleIndex].getT1();
int T2 = triangleList[triangleIndex].getT2();
int T3 = triangleList[triangleIndex].getT3();
// Update the line of first new triangle
triangleList[triangleIndex].setS1(newPointIndex);
triangleList[triangleIndex].setT2(triangleList.size() + 1);
triangleList[triangleIndex].setT3(triangleList.size() + 2);
// Update the adjacent triangles
if (T2 != 0 && T3 != 0)
{
triangleList[T2 - 1].setT3(triangleList.size() + 1); // T-1 because vector starts at 0
triangleList[T3 - 1].setT2(triangleList.size() + 2);
}
// Insert the new triangles in the triangulation
triangleList.push_back(triangle2);
triangleList.push_back(triangle3);
}
/*
Name: inCircle
Description: determine if a point is inside a circle
*/
bool inCircle(const Point& newPoint, const int triangleIndex)
{
// Get the coordinates of the new point
int x = newPoint.getX();
int y = newPoint.getY();
int z = newPoint.getZ();
// Get the coordinates of the first point
int x1 = pointList[triangleList[triangleIndex].getS1()].getX();
int y1 = pointList[triangleList[triangleIndex].getS1()].getY();
int z1 = pointList[triangleList[triangleIndex].getS1()].getZ();
// Get the coordinates of the second point
int x2 = pointList[triangleList[triangleIndex].getS2()].getX();
int y2 = pointList[triangleList[triangleIndex].getS2()].getY();
int z2 = pointList[triangleList[triangleIndex].getS2()].getZ();
// Get the coordinates of the third point
int x3 = pointList[triangleList[triangleIndex].getS3()].getX();
int y3 = pointList[triangleList[triangleIndex].getS3()].getY();
int z3 = pointList[triangleList[triangleIndex].getS3()].getZ();
// Create the 4 x 4 matrix
int pointArray[4][4] = { { x,y,z,1 }, {x1,y1,z1,1}, {x2,y2,z2,1}, {x3,y3,z3,1} };
// Create the 3 points of the first block A
Point pointA1(pointArray[1][1], pointArray[1][2], pointArray[1][3]);
Point pointA2(pointArray[2][1], pointArray[2][2], pointArray[2][3]);
Point pointA3(pointArray[3][1], pointArray[3][2], pointArray[3][3]);
// Create the 3 points of the second block B
Point pointB1(pointArray[1][0], pointArray[1][2], pointArray[1][3]);
Point pointB2(pointArray[2][0], pointArray[2][2], pointArray[2][3]);
Point pointB3(pointArray[3][0], pointArray[3][2], pointArray[3][3]);
// Create the 3 points of the third block C
Point pointC1(pointArray[1][0], pointArray[3][1], pointArray[1][3]);
Point pointC2(pointArray[2][0], pointArray[2][1], pointArray[2][3]);
Point pointC3(pointArray[3][0], pointArray[1][1], pointArray[3][3]);
// Create the 3 points of the fourth block D
Point pointD1(pointArray[1][0], pointArray[3][1], pointArray[1][2]);
Point pointD2(pointArray[2][0], pointArray[2][1], pointArray[2][2]);
Point pointD3(pointArray[3][0], pointArray[1][1], pointArray[3][2]);
// Find the determinant
int determinant = pointArray[0][0] * getDeterminant(pointA1, pointA2, pointA3) - pointArray[0][1] * getDeterminant(pointB1, pointB2, pointB3) + pointArray[0][2] * getDeterminant(pointC1, pointC2, pointC3) - pointArray[0][3] * getDeterminant(pointD1, pointD2, pointD3);
// Return the test value (1 if the point is inside the circle, 0 if not)
bool isInside;
(determinant < 0) ? (isInside = 1) : (isInside = 0);
return isInside;
}
/*
Name: walk
Description: find the triangle containing the new point
*/
int walk(const Point& newPoint)
{
// First triangle to test by default
int triangleToTest = 0;
int triangleIndex = -1;
do
{
// Define the points forming the first line to test
Point point1 = pointList[triangleList[triangleToTest].getS1() - 1];
Point point2 = pointList[triangleList[triangleToTest].getS2() - 1];
// Get the determinant
int determinant = getDeterminant(point1, point2, newPoint);
// Test if the point is on the left side of the line
if (determinant < 0)
{
// Define the points forming the second line to test
point1 = pointList[triangleList[triangleToTest].getS2() - 1];
point2 = pointList[triangleList[triangleToTest].getS3() - 1];
determinant = getDeterminant(point1, point2, newPoint);
// Test if the point is on the left side of the line
if (determinant < 0)
{
// Define the points forming the third line to test
point1 = pointList[triangleList[triangleToTest].getS3() - 1];
point2 = pointList[triangleList[triangleToTest].getS1() - 1];
determinant = getDeterminant(point1, point2, newPoint);
// Test if the point is on the left side of the line
if (determinant < 0)
{
triangleIndex = triangleToTest;
}
else
{
triangleToTest = triangleList[triangleToTest].getT2() - 1;
}
}
else
{
triangleToTest = triangleList[triangleToTest].getT1() - 1;
}
}
else
{
triangleToTest = triangleList[triangleToTest].getT3() - 1;
}
} while (triangleIndex == -1);
return triangleIndex;
}
/*-----------------------------------------
Name: Point
Author: Michael Landry
Description: Declaration of class Point
Date: 2018-02-15
Version: 1.00
-------------------------------------------*/
#ifndef POINT_H_
#define POINT_H_
#include <iostream>
#include <vector>
class Point
{
public:
// Default constructor
Point();
// Constructor with parameters
Point(int, int, int);
// Setters
void setPoint(int p_X, int p_Y, int p_Z);
void setX(int p_X);
void setY(int p_Y);
void setZ(int p_Z);
// Getters
int getX() const;
int getY() const;
int getZ() const;
// Overloaded operator
bool Point::operator==(const std::vector <Point> & p_pointList) const;
private:
// 3D coordinates as attributes
int m_X;
int m_Y;
int m_Z;
};
#endif /* POINT_H_ */
/*-----------------------------------------
Name: Point
Author: Michael Landry
Description: Implementation of class Point
Date: 2018-02-15
Version: 1.00
-------------------------------------------*/
#include "Point.h"
#include <iostream>
#include <vector>
// Default constructor initialises (0,0,0) as coordinates
Point::Point() : m_X(0), m_Y(0), m_Z(0)
{
}
// Constructor with parameters
Point::Point(int p_X, int p_Y, int p_Z) : m_X(p_X), m_Y(p_Y), m_Z(p_Z)
{
}
// Setter for the 3 coordinates
void Point::setPoint(int p_X, int p_Y, int p_Z)
{
m_X = p_X;
m_Y = p_Y;
m_Z = p_Z;
}
// Setter for each coordinate
void Point::setX(int p_X)
{
m_X = p_X;
}
void Point::setY(int p_Y)
{
m_Y = p_Y;
}
void Point::setZ(int p_Z)
{
m_Y = p_Z;
}
// Getter for each coordinate
int Point::getX() const
{
return m_X;
}
int Point::getY() const
{
return m_Y;
}
int Point::getZ() const
{
return m_Z;
}
// Overloaded operator
bool Point::operator==(const std::vector <Point> & p_pointList) const
{
// Initialize a counter
size_t i = 0;
bool isEqual = true;
do
{
isEqual = (m_X == p_pointList[i].getX()) && (m_Y == p_pointList[i].getY()) && (m_Z == p_pointList[i].getZ());
i++;
} while ((i < p_pointList.size()) && (isEqual == false));
return isEqual;
}
/*-----------------------------------------
Name: Triangle
Author: Michael Landry
Description: Declaration of class Triangle
Date: 2018-02-23
Version: 1.00
-------------------------------------------*/
#ifndef TRIANGLE_H_
#define TRIANGLE_H_
class Triangle
{
public:
// Constructor with no parameter
Triangle::Triangle();
// Constructor with parameters
Triangle::Triangle(int, int, int, int, int, int, int);
// Setters
void Triangle::setTriangle(int p_ID, int p_S1, int p_S2, int p_S3, int p_T1, int p_T2, int p_T3);
void Triangle::setID(int p_ID);
void Triangle::setS1(int p_S1);
void Triangle::setS2(int p_S2);
void Triangle::setS3(int p_S3);
void Triangle::setT1(int p_T1);
void Triangle::setT2(int p_T1);
void Triangle::setT3(int p_T1);
// Getters
int Triangle::getID() const;
int Triangle::getS1() const;
int Triangle::getS2() const;
int Triangle::getS3() const;
int Triangle::getT1() const;
int Triangle::getT2() const;
int Triangle::getT3() const;
private:
// The ID of the triangle
int m_ID;
// The 3 vertices forming the triangle
int m_S1;
int m_S2;
int m_S3;
// The 3 adjacent triangles
int m_T1;
int m_T2;
int m_T3;
};
#endif /* TRIANGLE_H_ */
/*-----------------------------------------
Name: Triangle
Author: Michael Landry
Description: Implementation of class Triangle
Date: 2018-02-23
Version: 1.00
-------------------------------------------*/
#include "Triangle.h"
// Constructor with no parameter
Triangle::Triangle() : m_ID(0), m_S1(0), m_S2(0), m_S3(0), m_T1(0), m_T2(0), m_T3(0)
{
}
// Constructor with parameters
Triangle::Triangle(int p_ID, int p_S1, int p_S2, int p_S3, int p_T1, int p_T2, int p_T3) : m_ID(p_ID), m_S1(p_S1), m_S2(p_S2), m_S3(p_S3), m_T1(p_T1), m_T2(p_T2), m_T3(p_T3)
{
}
// Global setter
void Triangle::setTriangle(int p_ID, int p_S1, int p_S2, int p_S3, int p_T1, int p_T2, int p_T3)
{
m_ID = p_ID;
m_S1 = p_S1;
m_S2 = p_S2;
m_S3 = p_S3;
m_T1 = p_T1;
m_T2 = p_T2;
m_T3 = p_T3;
}
// Setter for each individual parameter
void Triangle::setID(int p_ID)
{
m_ID = p_ID;
}
void Triangle::setS1(int p_S1)
{
m_S1 = p_S1;
}
void Triangle::setS2(int p_S2)
{
m_S2 = p_S2;
}
void Triangle::setS3(int p_S3)
{
m_S3 = p_S3;
}
void Triangle::setT1(int p_T1)
{
m_T1 = p_T1;
}
void Triangle::setT2(int p_T2)
{
m_T2 = p_T2;
}
void Triangle::setT3(int p_T3)
{
m_T3 = p_T3;
}
// Getter for each individual parameter
int Triangle::getID() const
{
return m_ID;
}
int Triangle::getS1() const
{
return m_S1;
}
int Triangle::getS2() const
{
return m_S2;
}
int Triangle::getS3() const
{
return m_S3;
}
int Triangle::getT1() const
{
return m_T1;
}
int Triangle::getT2() const
{
return m_T2;
}
int Triangle::getT3() const
{
return m_T3;
}
