Implementation of Queue

                This project explains the implementation of Queue using a triangle as an element. The queue is a data structure which works on FIFO (First In First Out) technique. The triangles are inserted as elements by assigning color and side to each element(triangle). Triangles will be placed one above another by keeping first inserted triangle at the bottom and the successive elements on top of it. When Delete operation is selected using mouse button the triangle from the front end will be taken out first from the Queue. By using various OpenGL functions the project has been implemented.

· Computer Graphics:

Computer Graphics is concerned with all aspects of producing pictures or images using a computer. The field began humbly almost 150 years ago, with a display of few lines on a cathode ray tube (CRT); now we can create images by a computer that are indistinguishable from photographs of real objects. We routinely train pilots with simulated airplanes, generating graphical displays of a virtual environment in real time. Feature-length movies made entirely by computer have been successful, both critically and financially. Massive multiplayer games can involve tens of thousands of concurrent participants.

A computer graphics system is a computer system; as such, it must have all the components of a general-purpose computer system. There are five major elements in our system:

1. Input devices
2. Processor
3. Memory
4. Frame buffer
5. Output dev

This model is general enough to include workstations and personal computers, interactive game systems and sophisticated image-generation systems. Although all the components, with the possible exception of the frame buffer, are present in a standard computer.

There are many applications of computer graphics; however, we divide them into four major areas as follows:

1. Display of information
2. Design
3. Simulation and Animation
4. User Interface

The combination of computers, networks, and the complex human visual system, through computer graphics, has led to new ways of displaying information, seeing virtual worlds, and communicating with people and machines.

Introduction to OpenGL:

We introduce a particular graphics software system, OpenGL, which has become a widely accepted standard for developing graphics applications. OpenGL is easy to learn and it possesses most of the characteristics of other popular graphics systems. OpenGL’s structure is similar to that of most modern APIs including java3D and DirectX.

Most of our applications will be designed to access OpenGL directly through functions in three libraries. Functions in the main GL (or OpenGL in windows) library have names that begin with letters gl and are stored in a library usually referred to as  GL (or OpenGL in windows). The second is the OpenGL Utility Library(GLU). This library uses only GL functions but contains code for creating common objects and simplifying viewing. All functions in GLU can be created from the core GL library but application programmers prefer not to write the code repeatedly. The GLU library is available in all OpenGL implementations; functions in the GLU library begin with the letters glu. We use a readily available library called the OpenGL Utility Toolkit (GLUT), which provides the minimum functionality that should be expected in any modern windowing system.

Problem Definition and Description:

Definition: A queue is an abstract data type in computer programming that supports the following two operations:

• Insert: add an element to the queue at the rear end.
• Get Next: remove the element from the queue from the front end.
• Description:

Triangles of different colors are inserted one above another. Thus the elements are pushed onto the Queue. User will be presented with insert and delete option. The triangles with inserted into the queue at the rear end. The triangles with deleted from the queue at the first end. Thus the elements are deleted based on the FIFO technique. The project is implemented using OpenGL functions.

Requirements:

·  Software Requirements:

The project can be implemented using the following softwares :

1. KDevelop C/C++
2. Developer C++
3. Fedora Core 7

·  Hardware Requirements:

The following hardware is required for the implementation of the project:

1. Pentium, Intel or AMD Processor
2. 256MB of RAM
3. 40GB HDD

Implementation:
Algorithm:

Input: Mouse events generated by the user.
Output: Insertion or Deletion of triangles as according to the mouse clicks.
Description: Implementation of data structure ‚QUEUE using openGL

Step 1:

Define an event handling function which can handle the mouse click.

• When a click event is computed, a call to the function is generated which handles the selection.
• The event handling function consists of two operations Insert and Delete.

Step 2:

Functions of each operation:

o Insert: The insert() operation is used both to initialize the queue and to display the elements. It is responsible for inserting (copying) the Triangle into the queue and incrementing the element counter(size). In a responsible  OPENGL implementation, when an Insert operation is selected, the draw() is called which displays the triangle onto the window.

o Delete: The delete() operation is responsible for removing a triangle(object) from the queue, and decrementing the value of element counter(size).  In a responsible  OPENGL implementation, when a delete() operation is selected, the delt() is called which removes the front  triangle from the queue.

Step 3:

Define a selection function, which does the following:

• Initialize a selection buffer, which does the insert and delete operation.
• Save somewhere the info about the current viewport
• Switch to GL_SELECT mode.
• Initialize the queue.
• Relative to the mouse clicks, insert/delete the respective number of Elements(triangles).

Step 4:

Launch your application and wait for user interaction .

Step 5:

Stop.

Snapshots:

How to Execute OPENGL programs:

1. Download C supported Eclipse and launch it.
2. Create a new C++ project: Select “File” menu ⇒ New ⇒ Project ⇒ C/C++ ⇒ C++ Project ⇒ Next.
   In “Project name”, enter “Hello” ⇒ In “Project type”, select “Executable”, “Empty Project” ⇒ In “Toolchain”, select “Cygwin GCC” or “MinGW GCC” (depending on your setup) ⇒ Next ⇒ Finish.
3. Create a new Source file: Right-click on the project node ⇒ New ⇒ Other… ⇒ C/C++ ⇒ Source file ⇒ Next.
   In “Source file”, enter “GLHello.c” ⇒ Finish.
4. In the editor panel for “GLHello.c“, type the following source codes:
           NOTE: For Windows, you should include “windows.h” header before the OpenGL headers.

The Coding part:

#include<stdio.h>
#include<GL/glut.h>
#include<GL/gl.h>
#include<math.h>
#include<stdlib.h>
#define STRINGLOCX 100.0
#define STRINGLOCY 100.0

int items,side=30,ndel,diff,k,h=5,count=0,i=0,d=0,del=0,m,full=0;
float m1[20],m2[20],m3[20];
void drawString (void *font, float x, float y, char *str);

 
void draw()
{
	int t;
	if(d==15)
	{
		glColor3f(1.0,0.0,0.0);
		drawString(GLUT_BITMAP_HELVETICA_18, 75,100,”Queue Full”);
		//full=1;
	}
	if(d>15)
	{
		d–;
		full=1;
		glColor3f(1.0,0.0,0.0);
		drawString(GLUT_BITMAP_HELVETICA_18, 75,100,”Queue Full”);
	}
	if(!full)
	{
		for(m=0,del=0;m<count;m++)
		del+=4;
		printf(“count=%d\n”,d);
		for(t=count;t<d;t++)
		{
			glColor3f(m1[t],m2[t],m3[t]);
			del++;
			glBegin(GL_TRIANGLES);
			glVertex2i(10,(h*del+10));
			glVertex2i(10+side,h*del+10);
			del+=3;
			glVertex2i(10+(side*0.5),h*del+10);
			glEnd();
			glFlush();
		}
	}
}

void delt()
{
	full=0;
	if(count==d-1 && d!=15)
	{
	glColor3f(1.0,0.0,0.0);
	drawString(GLUT_BITMAP_HELVETICA_18, 75,80,”Queue empty”);
	}
	glFlush();
	int t,m;
	if(d>=15)
	{
	glColor3f(1.0,0.0,0.0);
	drawString(GLUT_BITMAP_HELVETICA_18, 75,100,”Queue Full”);
	}
	count++;
	for(m=0,del=0;m<count;m++)
	del+=4;
	for(t=count;t<d;t++)
	{
		glColor3f(m1[t],m2[t],m3[t]);
		del++;
		glBegin(GL_TRIANGLES);
		glVertex2i(10,(h*del+10));
		glVertex2i(10+side,h*del+10);
		del+=3;
		glVertex2i(10+(side*0.5),h*del+10);
		glEnd();
		glFlush();
	}
}

// TO DRAW A STRING ON THE DISPLAY
void drawString (void *font, float x, float y, char *str)
{
	/* Draws string ‘str’ in font ‘font’, at world (x,y,0) */
	char *ch;
	glRasterPos3f(x, y, 0.0);// TO POINT POINTER TO SPECIFIED POSITION
	for (ch= str; *ch; ch++)//*CH = CH!=0
	{
	glutBitmapCharacter(font, *ch);
	}
}
void display(void)
{
	if(i==0)
	{
	glFlush();
	}
	i++;
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	glColor3f(0.0,0.3,1.0);
	drawString(GLUT_BITMAP_HELVETICA_18, 175,475,”Implementation of Queue”);
}

void myinit()
{
	glClearColor(1.0,1.0,1.0,1.0);
	glColor3f(1.0,0.0,0.0);
	glPointSize(1.0);
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluOrtho2D(0.0,499.0,0.0,499.0);
}

void demo_menu(int id)
{
	switch(id)
	{
	case(1):
	{
	d++;
	draw();
	break;
	}
	case(2):
	{
	delt();
	break;
	}
	case(3):
	{
	i=0;
	glColor3f(0.0,0.0,1.0);
	drawString(GLUT_BITMAP_HELVETICA_18, STRINGLOCX,STRINGLOCY,”Developed by Timmesh.K and Rakesh.c w 6th sem cs”);
	break;
	}
	}
	glutPostRedisplay();
}

int main(int argc,char ** argv)
{
	int i;
	printf(“\nIMPLEMENTATION OF STACK USING TRINGLE AS ELEMENT \n”);
	glutInit(&argc,argv);
	glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB|GLUT_DEPTH);
	
	for(m=0;m<20;m++)
	{
		m1[m]=(float)(rand()%9)/(m+7);
		m2[m]=(float)(rand()%9)/(m+7);
		m3[m]=(float)(rand()%9)/(m+7);
	}
	glutInitWindowSize(700,700);
	glutInitWindowPosition(0,0);
	glutCreateWindow(“Implementation of Queue”);
	glutDisplayFunc(display);
	myinit();
	glutCreateMenu(demo_menu);
	glutAddMenuEntry(“Push”,1);
	glutAddMenuEntry(“Pop”,2);
	glutAddMenuEntry(“About”,3);
	glutAttachMenu(GLUT_RIGHT_BUTTON);
	glutMainLoop();
}

OpenGL functions used are:

void glVertex[234][sifd](TYPE xcoordinate, TYPE ycoordinate,.)

void glVertex[234][sifd]v(TYPE *coor-dinates)

specifies the position of a vertex in 2,3 or 4 dimensions. The coordinates can be specifies as shorts s, int i, floats f or doubles d. If the v is present, the argument is a pointer to an array containing the coordinates.

void glBegin(glEnum mode)

initiates a new primitive of type mode and starts the collection of vertices. Values of mode include GL_POINTS, GL_LINES and GL_POLYGON.

void glEnd()

terminates a list of vertices.

void glColor3[b i f ub us ui](TYPE r,TYPE g, TYPE b)

sets the present RGB(or RGBA) colors. Valid types are bytes (b), int (i), float (f), double (d) ,unsigned byte (ub), unsigned short (us), unsigned int (ui). The maximum and minimum values of the floating-point types are 1.0, 0.0 respectively.

void glClearColor(GLcLampf r, GLclampf g, GLclampf b, Glclampf a)

sets the present RGBA clear color used when clearing the color buffer. Variables of type GLclampf are floating-point numbers between 0.0 and 1.0.

void glPointSize(GLfloat size)

sets the point size attribute in pixels.

void glFlush()

forces any buffered OpenGL commands to execute.

void glutInit(int *argc, char **argv)

initializes GLUT. The arguments from main are passed in and can be used by the application.

int glutCreateWindow(char *title)

creates a window on the display. The string title can be used to label the window. The return value provides a reference to the window that can be used when there are multiple windows.

void glutInitDisplayMode(unsigned int mode)

requests a display with the properties in mode. The value of mode is determined by the logical OR of options including the color model(GLUT_RGB, GLUT_INDEX) and buffering (GLUT_SINGLE, GLUT_DOUBLE).

void glutInitWindowSize(int width, int height)

specifies the initial height and width of the window in pixels.

void glutInitWindowPosition(int x, int y)

specifies the initial position of the top-left corner of the window in pixels.

void glutMainLoop()

cause the program to enter an event-processing loop. It should be the last statement in main.

void glutDisplayFunc(void(*func)(void))

registers the display function func that is  executed when the window needs to be redrawn.

void glutAddMenuEntry(char *name, int value)

adds an entry with the string name display to the current menu. Value is returned to the menu callback when the entry is selected.

void glMatrixMode(GLenum mode)

specifies which matrix will be affected by subsequent transformations. Mode can be GL_MODELVIEW, GL_PROJECTION, or GL_TEXTURE.

void glLoadIdentity()

sets the current transformation matrix to an identity matrix.