To use a linked list, or not?

[mike_g]

To give you a bit of background on this I'm making a project which draws lines and filled triangles. I then have an abstract Polygon struct that draws different shapes according to its properties. Each polygon needs to contain a set of Points. Up until now I had given each polygon a static array of points. I decided to change it so that each Polygon contains a linked list of points, but I'm not sure if its a good idea. Heres what I have come up with so far on it:

Benefits

• Scalable
• Fast to insert / remove points

Disadvantages

• Memory leak if Polygon object goes out of scope. and points arent freed.
• Before drawing points need to be copied to arrays.

With the first disadvantage. Is there anyway I can do some sort of garbage collection to remove points where their polygon has gone out of scope? Or is there another way to avoid this?

With the second, points on the list need to be copied to arrays so the values can be passed to the relevant drawing functions. Is there a way I could aoid this. Heres the code as an example:

int DrawPolygon(Uint32 buffer[], Polygon p)
{
	// Using a linked list content must be copied across first?
	float x[p.size];
	float y[p.size];
	Point *ptr = p.pt;
	int i=0;
	while(ptr)
	{
		x[i] = ptr->x;
		y[i] = ptr->y;
		i++; 
		ptr = ptr->next;
	}

	//if(p.flags & POLYGON_IS_SPLINE)
	//	return DrawSpline(p);

	switch(p.size)
	{
		case 1: 
			DrawPixel(buffer, x[0], y[0], p.color);
			break;
		case 2: 
			DrawLine(buffer, x[0], y[0], x[1], y[1], p.color);
			break;
		case 3:
			if(p.flags & POLYGON_IS_FILLED)	
				DrawTriangle(buffer, x[0], y[0], x[1], y[1], x[2], y[2], p.color, 1);
			else if(p.flags & POLYGON_IS_CLOSED)
				DrawTriangle(buffer, x[0], y[0], x[1], y[1], x[2], y[2], p.color, 0);
			else 			
			{
				DrawLine(buffer, x[0], y[0], x[1], y[1], p.color);
				DrawLine(buffer, x[1], y[1], x[2], y[2], p.color);
			}
			break;
		case 4:
			if(p.flags & POLYGON_IS_FILLED)
				DrawRhombus(buffer, x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3], p.color, 1);
			else if(p.flags & POLYGON_IS_CLOSED)
				DrawRhombus(buffer, x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3], p.color, 0);
			else
			{
				DrawLine(buffer, x[0], y[0], x[1], y[1], p.color);
				DrawLine(buffer, x[1], y[1], x[2], y[2], p.color);
				DrawLine(buffer, x[2], y[2], x[3], y[3], p.color);
			}
			break;
		default: 

			break;
	}
	return 0;	
}

[noops]

Why do you have different functions for drawing different shapes? All polygons should be drawn the same right?

Your current method is not very scalable. Are you going to write a switch case for 6 sides? 8 sides?

Also, I am not sure what you mean by "remove points when their polygon has gone out of scope".

[mike_g]

Your current method is not very scalable. Are you going to write a switch case for 6 sides? 8 sides?

No then its just a matter of connecting the dots. The only problem I can see is how Im going to be able to fill it. A floodfill wont guarantee filling the entire polygon, so I might have to find a way of splitting it into triangles. but thats a different matter. When theres only two points its more appropriate to draw a line; when theres 3 a triangle. Or, how would you do it?

Also, I am not sure what you mean by "remove points when their polygon has gone out of scope".

The polygons are structs which each contain a linked list of malloced points. If a polygon goes out of scope w/o freeing the points on its list it will result in a memory leak.

[noops]

No then its just a matter of connecting the dots. The only problem I can see is how Im going to be able to fill it. A floodfill wont guarantee filling the entire polygon, so I might have to find a way of splitting it into triangles. but thats a different matter. When theres only two points its more appropriate to draw a line; when theres 3 a triangle. Or, how would you do it?

I don't know anything about filling methods. But for just drawing the polygons I would think a single function would suffice. If you can assume that the list of coordinates is in the order they should be drawn then the only question is whether to close the loop or not. Is drawing a triangle really any different than drawing a square? To me it just sounds like one more iteration in a loop.

The polygons are structs which each contain a linked list of malloced points. If a polygon goes out of scope w/o freeing the points on its list it will result in a memory leak.

Do you free the polygon when it goes out of scope?

[mike_g]

I don't know anything about filling methods. But for just drawing the polygons I would think a single function would suffice. If you can assume that the list of coordinates is in the order they should be drawn then the only question is whether to close the loop or not. Is drawing a triangle really any different than drawing a square? To me it just sounds like one more iteration in a loop.

The rhombus was stuck in there because its easy to split into two triangles and fill for now. The other conditional statements are required whether its in a generic function or not. The drawing functions are called from another source file that I wrote which is independant of the polygons module and i would like to keep it that way. Look I really cant be bothered to argue about this - its not what the thread was about.

Do you free the polygon when it goes out of scope?

No because its a struct and its not malloced. I might make it malloced so that its more obvious that the cleanup function needs to be called when finishing with the object.

[dwks]

About catching leaked polygons -- you could implement a reference counter. It's pretty easy.

Every time you allocate a block of memory, you record that you have done so. You also record a number indicating the number of pointers that reference this particular block of memory -- just after you allocate memory, of course, it should be 1 (or 0 if you want).

Every time you make another pointer point to a block of memory, you increment the counter. Every time a pointer goes out of scope or you free it, you decrement the counter.

Periodically, you can get the reference counter to go through the list of blocks and free the ones that have a reference count of 0. Or you could free the blocks as soon as the count reaches zero, which is probably a better idea.

Finally, at the end of the program, you examine the list for any blocks of memory that weren't freed. Those are memory leaks.

This doesn't help you very much while the program is running, of course -- although it lets you create shallow copies very easily -- but it lets you debug memory leaks very easily.

Note that under Linux, Valgrind does much the same thing as this, but more thoroughly. (You get stack traces indicating where memory leaks originated.) Of course, running a program under Valgrind is pretty slow; a reference counter can be very fast.

I've implemented a reference counter in xuni, if you want to have a look at it. Grab the xuni-0.3.0-git-a1422f8-src.tar.gz archive, or any -src archive (I don't think it's changed recently), and look at src/memory.c and .h. http://sourceforge.net/project/showf...kage_id=269611

It's not the prettiest, but it does everything I've described and a few more things as well. For example, it can record the name of the function where the block was allocated, which can aid in debugging.

[noops]

The rhombus was stuck in there because its easy to split into two triangles and fill for now. The other conditional statements are required whether its in a generic function or not. The drawing functions are called from another source file that I wrote which is independant of the polygons module and i would like to keep it that way. Look I really cant be bothered to argue about this - its not what the thread was about.

Ok. I thought it was relevant because you could eliminate the need to copy the linked list into an array first.

You pointed out the benefit that a linked list is scalable but you have no way to take advantage of that.

[dwks]

About filling polygons with an arbitrary number of vertices:

I've heard good things about the scanline flood fill algorithm. As far as I know, it handles polygons of any shape. http://student.kuleuven.be/~m0216922/CG/floodfill.html

I've implemented the ordinary recursive floodfill before. http://en.wikipedia.org/wiki/Flood_fill
It works for any shape at all, but you quickly run out of stack space.

I wrote a paint program called paint2 which allowed you to draw circles, lines, polygons, etc. The floodfill worked for any shape you could possibly imagine. Of course, I was using recursive floodfill, but scanline should be the same way.

I don't see how you're restricted to flood filling triangles. I guess you're using a different algorithm.

But you really should look into the scanline algorithm. Or use what I did.

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.

(That's from Wikipedia.)

[mike_g]

DWKS: I installed valgrind the other day, but havent got around to playing with that. The reference counter thing sounds like what I could do with. I downloaded the xuni source and will go over it. thanks.

Ok. I thought it was relevant because you could eliminate the need to copy the linked list into an array first.

For < 5 points I'll be happy to live with copying the data across. For > 4 points it looks like I will still have to copy it if I'm filling the poly. If I'm not I can just keep track of two pointers and draw lines between the locations they point to.

You pointed out the benefit that a linked list is scalable but you have no way to take advantage of that.

Yes I do, the function for drawing 5+ points just is not implemented yet. The function will be called on the default case. I already explained this.

[mike_g]

About filling polygons with an arbitrary number of vertices:

I've heard good things about the scanline flood fill algorithm. As far as I know, it handles polygons of any shape. http://student.kuleuven.be/~m0216922/CG/floodfill.html

I've implemented the ordinary recursive floodfill before. http://en.wikipedia.org/wiki/Flood_fill
It works for any shape at all, but you quickly run out of stack space.

I wrote a paint program called paint2 which allowed you to draw circles, lines, polygons, etc. The floodfill worked for any shape you could possibly imagine. Of course, I was using recursive floodfill, but scanline should be the same way.

I don't see how you're restricted to flood filling triangles. I guess you're using a different algorithm.

But you really should look into the scanline algorithm. Or use what I did.

Yeah scanline floodfill is the fast one. I have only made a bog-standard recursive one myself which is too slow for realtime drawing.

The problem with polygons is that filling from one point might not fill the whole polygon (depending on its shape) also with a four way floodfill you can miss out odd pixels stuck on the diagonals of narrow angles.

The way I plan on doing it is by drawing scanline filled triangles which fill from the top (faster for pointer arithmetic). I already have the code set up for it and it would be guaranteed to fill everything. Only problem is that its going to be a headache splitting the polygon into a set of triangles. I'll probably have to use a floodfill on splines though.

[dwks]

DWKS: I installed valgrind the other day, but havent got around to playing with that. The reference counter thing sounds like what I could do with. I downloaded the xuni source and will go over it. thanks.

Hmm, thanks. You've unwittingly confirmed my suspicions about the download counter on SourceForge. It's not working at the moment. It's not just xuni, either . . . .

The problem with polygons is that filling from one point might not fill the whole polygon (depending on its shape) also with a four way floodfill you can miss out odd pixels stuck on the diagonals of narrow angles.

Hmm, yes, that makes sense. However, I think you could write your code so that it would avoid the latter problem, as long as the size of the polygon never reaches zero.

The way I plan on doing it is by drawing scanline filled triangles. I already have the code set up for it and it would be guaranteed to fill everything. Only problem is that its going to be a headache splitting the polygon into a set of triangles.

I think what you need to do is to have only continuous polygons. You were describing problems with floodfilling shapes that, like an hourglass or a figure eight, might not have one solid area to fill, right?

You should be able to guarantee only continuous polygons arbitrarily. It's not a very big restriction -- you can use more than one contiguous polygon to make up a non-contiguous polygon.

Would that work?

(Note that I've made up this use of the word "contiguous". There might be a real term for it, but I don't know what it is.)

[mike_g]

I think what you need to do is to have only continuous polygons. You were describing problems with floodfilling shapes that, like an hourglass or a figure eight, might not have one solid area to fill, right?

You should be able to guarantee only continuous polygons arbitrarily. It's not a very big restriction -- you can use more than one contiguous polygon to make up a non-contiguous polygon.

Would that work?

Yeah I guess it would not be too hard to make sure the lines dont cross or touch. Not sure if I'd want that tho. And this is all a little way down the line from here

Cheers.

[dwks]

What I meant was, don't support non-contiguous polygons. It's not a very big restriction on the part of the user of your code to disallow them.

But you're right, of course. I can't see it being too difficult to find line intersections etc.

Good luck.

[mike_g]

Yeah they will definitely be contiguos, but floodfills would have a problem with overlapping lines. Also, with the sourceforge D/L counter it might just be that it takes a while for the results to come through. I know that with google analytics it usually takes about an hour between stat updates.

[noops]

Sounds like a fun project. How did you get started on it? I am curious to try some graphics projects but I am not sure where to start. Are you using opengl?