Imagination Technologies Interview Question for Graphics Programmers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * Draw Sierpinski triangles.
 * 
 * Compile: cc sierpinski.c -o sierpinski -lglut
 *
 * Usage: sierpinski level x1 y1 x2 y2 x3 y3
 *   level: number of times the triangle should be divided
 *   x*, y*: vertices of the initial triangle.
 * Example: sierpinski 1  -0.5 0  0.5 0  0 0.87
 *
 * Program uses OpenGL library.  On *Ubuntu, install:
 * freeglut3-dev
 * mesa-common-dev
 * 
 * OpenGL drawing function adapted from:
 * http colon slash slash www dot codeproject dot com slash Articles slash 182109 slash Setting-up-an-OpenGL-development-environment-in-Ub
 * Also see OpenGL Red Book:
 * http colon slash slash www dot glprogramming dot com slash red slash chapter01 dot html#name2
 */


#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <GL/freeglut.h>
#include <GL/gl.h>



/*
 * vertex: one vertex of a triangle.
 */

struct vertex {
        float  x;
        float  y;
};




/*
 * triangle: three vertices.
 */

typedef struct vertex triangle[3];




/*
 * tle: triangle list element
 * A linked list of triangles forming a Sierpinski triangle.
 */

struct tle {
        triangle     t;
        struct tle  *next;
};




/*
 * mid
 * 
 * Return the midpoint of two vertices.
 */

struct vertex
mid(const struct vertex *v1, const struct vertex *v2)
{
        assert(v1);
        assert(v2);

        struct vertex mid;
        mid.x = (v1->x + v2->x) / 2.0;
        mid.y = (v1->y + v2->y) / 2.0;
        return mid;
}





/*
 * sierpinski
 * 
 * Given a linked list representing a Sierpinski triangle,
 * revise the list to go one level deeper.
 */

struct tle *
sierpinski(struct tle *s)
{
        assert(s);

        struct tle *new = s;

        while (s) {
                /*
                 * Reuse the element in the original list and
                 * create two new elements.  The three will form
                 * the new triangles one level deeper.
                 */

                triangle st = {s->t[0], s->t[1], s->t[2]};

                triangle n1, n2;

                /*
                 * New triangles are as follows:
                 * 
                 *                  *
                 *                 * *
                 *                *   *
                 *               * n2  *
                 *              *       *
                 *             *---------*
                 *            * \       / *
                 *           *   \     /   *
                 *          * s   \   / n1  *
                 *         *       \ /       *
                 *        *********************
                 */

                n2[0] = mid(&st[0], &st[2]);
                n2[1] = n1[2] = mid(&st[1], &st[2]);
                n2[2] = st[2];

                n1[0] = mid(&st[0], &st[1]);
                n1[1] = st[1];

                s->t[1] = n1[0];
                s->t[2] = n2[0];

                /*
                 * Form a linked list comprising s, n1, and n2.
                 */
                struct tle *new1 = malloc(sizeof(struct tle));
                struct tle *new2 = malloc(sizeof(struct tle));
                assert(new1);
                assert(new2);
                int i;
                for (i = 0; i < 3; i++) {
                        new2->t[i] = n2[i];
                        new1->t[i] = n1[i];
                }
                new2->next = s->next;
                new1->next = new2;
                s->next = new1;

                s = new2->next;
        }  /* while (s) */

        return new;
}




/*
 * free_sierpinski
 * 
 * Given a linked list representing a Sierpinski triangle, free
 * all elements.
 */

void
free_sierpinski(struct tle *s)
{
        while (s) {
                struct tle *next = s->next;
                free(s);
                s = next;
        }
}




/*
 * render_sierpinski
 * 
 * Render a Sierpinski triangle using OpenGL.
 * Uses global variable sier for the Sierpinski triangle.
 */

const struct tle *sier;

void
render_sierpinski(void)
{
        glClearColor(0.0, 0.0, 0.0, 0.0);
        glClear(GL_COLOR_BUFFER_BIT);
        glColor3f(1.0, 1.0, 1.0);
        glOrtho(-1.0, 1.0, -1.0, 1.0, -1.0, 1.0);
        const struct tle *s = sier;
        while (s) {
                glBegin(GL_POLYGON);
                int i;
                for (i = 0; i < 3; i++)
                        glVertex2f(s->t[i].x, s->t[i].y);
                glEnd();
                s = s->next;
        }
        glFlush();
}




/*
 * draw_sierpinski
 * 
 * Use OpenGL to draw the Sierpinski triangle.
 * Does not return.
 */

void
draw_sierpinski(int argc, char *argv[ ], const struct tle *s)
{
        assert(s);
        sier = s;

        glutInit(&argc, argv);
        glutInitDisplayMode(GLUT_SINGLE);
        glutInitWindowSize(500, 500);
        glutInitWindowPosition(100, 100);
        glutCreateWindow("Sierpinski");
        glutDisplayFunc(render_sierpinski);
        glutMainLoop();
}




/*
 * main
 * 
 * Parse the command line arguments to create the first triangle.
 * Invoke sierpinski level number of times to divide up the
 * triangle.  Draw using OpenGL.
 */

int
main(int argc, char *argv[ ])
{
        if (argc != 8) {
                fprintf(stderr, "Usage: sierpinski n x1 y1 x2 y2 x3 y3\n");
                return 1;
        }

        struct tle *s = malloc(sizeof(struct tle));
        assert(s);
        s->next = 0;
        sscanf(argv[2], "%f", &s->t[0].x);
        sscanf(argv[3], "%f", &s->t[0].y);
        sscanf(argv[4], "%f", &s->t[1].x);
        sscanf(argv[5], "%f", &s->t[1].y);
        sscanf(argv[6], "%f", &s->t[2].x);
        sscanf(argv[7], "%f", &s->t[2].y);

        unsigned int level;
        sscanf(argv[1], "%u", &level);

        int i;
        for (i = 0; i < level; i++)
                s = sierpinski(s);

        draw_sierpinski(argc, argv, s);  /* does not return */

        free_sierpinski(s);

        return 0;
}

- Event horizon August 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets Presume these functions are given to you
1. GetPointFromPoints
2. getlen
3. Draw.

Then, the Basic code would be like the following.

void DrawTriangle(point A, point B, point C){
	int len =getlen(A,B);
	if(len<=MIN_LEN){
		return;
	}
	point D=GetPointFromPoints(A,B,len/2);
	point E=GetPointFromPoints(A,C,len/2);
	point F=GetPointFromPoints(C,B,len/2);
	
	Draw(D,E); Draw(E,F); Draw(F,D);
	
	DrawTriangle(A, D,E);
	DrawTriangle(B, D,F);
	DrawTriangle(C, E,F);
}

- coderishere May 22, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More