Back to General and Gameplay Programming

Polymorphism with Linked Lists

General and Gameplay Programming Programming

Started by tmarques4 October 26, 2011 07:08 PM

20 comments, last by tmarques4 12 years, 5 months ago

tmarques4

189

Author

October 26, 2011 07:08 PM

I'm testing an implementation which comprises a linked list of objects, each called Geometry, which stores information about vertices, UVcoordinates and normals in a GeometryData array.
The problem is that a geometry object can be either one of the primitive types: points, lines, triangles and quads so; in essence, the data structure is a list of objects which contain one of the aforementioned types, not following any precondition to linking objects.

The workaround implemented by me for this would have generic pointers and a type variable which specifies what type it is so proper cast is done.



struct point{...};

struct line{...};

struct triangle{...};

struct quad{...};

class Geometry

{

  short type; //POINT, LINE, TRIANGLE OR QUAD

  void *geometryData;  //Pointer to structure of type specified.

  Geometry *next;

}

Is this a good approach or is there a better one for working with polymorphism, maybe using templates?

Appreciate all help given.
Best regards!

Tiago.MWeb Developer - Aspiring CG Programmer

Juliean

7,343

October 26, 2011 07:20 PM

You could inherit all your geometric objects from a base struct

Struct Geometry
{}

Struct Point : public Geometriy
{}

Struct Line : public Geometry
{}

...

Then you can use Geometry as type for the linked list and store eg lines without having to cast anything.

tmarques4

189

Author

October 26, 2011 08:01 PM

@The King2

I've just tried one simple code which doesn't seem to work.



#include <stdio.h>



struct Object

{

	int object;

};



struct Point : public Object

{

	int point;

};

struct Quad : public Object

{

	int quad;

};

int main()

{

	Object *hum = new Quad;

	hum->quad = 10;

	return 0;

}

However, if I try to access quad int by casting ((Quad *)hum)->quad, the above example works.
Is there anything wrong?

Tiago.MWeb Developer - Aspiring CG Programmer

ApochPiQ

23,138

October 26, 2011 09:11 PM

hum is an Object*. When you access it, you can only access members which are defined in Object. If hum were to be a Quad*, your code would work as shown. However, that kind of defeats the purpose of polymorphism!

Unfortunately, the situation as we know it is too simple to actually offer a real solution. Typically when you use this sort of design, you will write virtual functions which are defined in Object and then implemented in Quad/etc. Those functions will do the actual work of processing the various types of geometry. However, it can be tricky to set things up that way, and it depends a lot on the sort of work your program is trying to do.

Moreover, there may be better alternatives, but they are only useful in certain situations. Without knowing a lot more about your program's purpose it's hard to suggest options.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

ChaosEngine

5,385

October 26, 2011 09:18 PM

@The King2

I've just tried one simple code which doesn't seem to work.

#include <stdio.h> struct Object { int object; }; struct Point : public Object { int point; }; struct Quad : public Object { int quad; }; int main() { Object *hum = new Quad; hum->quad = 10; return 0; }

However, if I try to access quad int by casting ((Quad *)hum)->quad, the above example works.
Is there anything wrong?

I don't think you really understand the concept of polymorphism. Object doesn't know anything about Quads.
You can only access the Object members though the Object pointer.

What do you want to do with all your different geometry types that they have in common?

if you think programming is like sex, you probably haven't done much of either.-------------- - capn_midnight

Antheus

2,410

October 26, 2011 09:21 PM

The above example is broken anyway, it's the canonical case of how inheritance is taught incorrectly.

Line, Point, Quad, etc. are all geometric shapes, but are not descendants. One possible definition is:



typedef std::vector<Point> GeometricShape;



bool is_triangle(GeometricShape s);

bool is_equilateral_triangle(GeometricShape s);

bool is_rectangle(...

Then, classify them based on how many points they contain and other properties. Which is exactly what the geometric definitions are.

Example of a problem: Take triangle with coordinates: (1,1)(1,1)(1,1) and another with (1,1),(2,1),(3,1).

Its class will say: "Triangle". But the first is a point and second is a line. And it's a degenerate triangle at best, if it's a triangle at all. The type system is ok, it actually says: this doesn't work.

And there's the problem of covariance: every square is a rectangle and a polygon, but not vice versa. So asking for type of (0,0)(0,1)(1,1)(1,0), would need to return (Square, Rectangle, Polygon, maybe_a_few_other_things), yet such typing systems only allow single type association.

A geometric shape is a composition of points with implied order. What shape they represent depends and is not statically typed, especially with such simple typing systems that C family languages offer, where type is unrelated to values. Even the most trivial examples quickly lead to exceptions, where a line is suddenly being called a triangle, just because.

tmarques4

189

Author

October 26, 2011 11:17 PM

Line, Point, Quad, etc. are all geometric shapes, but are not descendants. One possible definition is:typedef std::vector<Point> GeometricShape; bool is_triangle(GeometricShape s); bool is_equilateral_triangle(GeometricShape s); bool is_rectangle(...

Then, classify them based on how many points they contain and other properties. Which is exactly what the geometric definitions are.

The problem is that a "GeometricShape" have other variants, mainly UVcoordinates and normals, so they differ from each other, so problem can't be solved just by adding a Point data type.

-------------------------------------------------------------------

@Apoch

The problem is fairly simple to understand but not so easy to implement.

The data structure is as follows.



struct point

{

  float vertex[3];

}

struct line

{

  float vertex[2][3];

}

struct triangle

{

  float vertex[3][3];

  float UVcoord[3][2];

  float normal[3][3];

}

struct quad

{

  float vertex[4][3];

  float UVcoord[4][2];

  float normal[4][3];

}

As you can see, points and lines differ from triangles and quads. Off course, vertex is common to all of them so a proper hierarchy can be designed but, it does not solve the problem of having a generic linked list, which is a linked list that can link to any of the geometry above.

What I basically want is a linked list like the following:

quad->point->point->triangle->quad->line->point->quad->NULL

Since The King2 proposition is not the proper one, the problem doesn't have anything to do with OOD, I may be wrong and, what I want to implement is a polymorphic linked list I suppose.

Tiago.MWeb Developer - Aspiring CG Programmer

rip-off

11,000

October 26, 2011 11:26 PM

You don't have to use inheritance. Why not store them in four different containers?

blog | twitter

ApochPiQ

23,138

October 27, 2011 12:08 AM

The question isn't about what form the data takes. The question is, what do you do with the data? That really changes the best approach.

I guess what I'm getting at is, why do you want all of these different objects in a single linked list? What will that gain you that alternatives will not? What sort of processing are you doing on the list?

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

alvaro

21,604

October 27, 2011 01:19 AM

If you can put enough methods in Object to make it a useful interface, polymorphism might work for you. Geometric figures might have a method to draw themselves in a window, they might be able to return a bounding box... Perhaps then you can have a linked list of your objects, but it needs to be the case that most of the code can handle objects just using the Object interface. The sample of code you posted where you tried to set hum->quad is an example of code that needs to know more than the Object interface.

I use polymorphism in very few places. I do it when I can have a factory function that returns a pointer to the base class and no other part of the code needs to know what exact type was returned. If I ever find the need to use dynamic_cast (which is what would allow you to get a more specific pointer from a pointer to Object), I reconsider my design, because the abstraction is not working.

Polymorphism with Linked Lists

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Polymorphism with Linked Lists

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines