how to link classes using pointers of their derived classes

I

ivan.leben

I want to write a Mesh class using half-edges. This class uses three
other classes: Vertex, HalfEdge and Face. These classes should be
linked properly in the process of building up the mesh by calling Mesh
class functions. Let's say they point to each other like this:

class Vertex {
HalfEdge *edge;
};
class HalfEdge {
Vertex* vert;
HalfEdge *twin;
HalfEdge *next;
Face* face;
};
class Face {
HalfEdge *edge;
};

Now I want to be able to derive from these classes in order to add more
functionality to them (e.g. normal). However, I want that as I derive
from a class, all the pointers among the three classes use the new
derived class instead of base one, so I don't have to cast Vertex* to
MyVertex* everytime I search for an edge->next->vert vertex of next
edge in the loop.

What I try to achieve would look like the three classes being nested
inside the Mesh class, which is a template class and takes template
arguments for both three classes. Let me illustrate:

templace <class VertType, class HalfEdgeType, class FaceType>
class Mesh {
public:
class Vertex {
HalfEdgeType *edge;
};
class HalfEdge {
VertType *vert;
HalfEdgeType *next;

[and so on....]
};

Now, even though this code compiles perfectly it is impossible to use
it as I want because in order to use any of the three nested classes I
would have to specify template arguments for the Mesh class first, but
these arguments have to be the same nested classes I am trying to
instantiate at the same time.

Of course I could solve this by defining base Vertex, HalfEdge and Face
classes outside the Mesh class, then make Mesh class template and
define nested "iterator" classes, that would walk over links and
automatically cast pointers to my derived classes that I pass as
template arguments to the Mesh class. But I see no practical sense in
constructing and using an "iterator" just to jump from one edge to its
next edge.

Is there any other possibility of how I could inter-link several
classes by using pointers of their derives? Or do I have no other way
than to either perform annoying casting of pointer types or construct
and "++" an iterator each time I follow an edge's next link?
 
B

Bart

I want to write a Mesh class using half-edges.

Any immediate solutions you're going to find to this will be ugly hacks
(as your template example demonstrates). Your problem is a fundamental
flaw in your design. Let's review:
This class uses three
other classes: Vertex, HalfEdge and Face. These classes should be
linked properly in the process of building up the mesh by calling Mesh
class functions. Let's say they point to each other like this:

class Vertex {
HalfEdge *edge;
};
class HalfEdge {
Vertex* vert;
HalfEdge *twin;
HalfEdge *next;
Face* face;
};
class Face {
HalfEdge *edge;
};

See, your problem begins right there. You treat these "classes" as
merely containers for data and delegate the real work to a supervisor
Mesh class. That in itself defeats the purpose of using classes and is
not an object-oriented solution. But that's not all.
Now I want to be able to derive from these classes in order to add more
functionality to them (e.g. normal). However, I want that as I derive
from a class, all the pointers among the three classes use the new
derived class instead of base one, so I don't have to cast Vertex* to
MyVertex* everytime I search for an edge->next->vert vertex of next
edge in the loop.

Okay, so you want to derive new classes and add new operations, but you
really want to use the derived classes not the base. So why use
inheritance at all? You see, the point of using inheritance is so that
you can create an abstraction without specifying explicitly which
implementation of this abstraction will be used, and leave the details
of the implementation to a small portion of the code. But what you're
really trying to do here is to commit to a specific implementation.
That's not an abstraction anymore, and it doesn't mandate the use of
inheritance.

If your code relies on the presence of an operation in a derived class
then that operation should really be part of the abstract interface
which is the base class. The derived class should be the actual
container of the data and the implementor of the abstract interface.

Don't be afraid to use lots of classes with good abstractions and
delegate the real work to the smaller classes rather than have
super-mumbo-jumbo classes that do all the work. The point of OOP is
exactly to create small self-reliant cells of code that don't need to
depend on things outside of them.

Regards,
Bart.
 
S

Salt_Peter

I want to write a Mesh class using half-edges. This class uses three
other classes: Vertex, HalfEdge and Face. These classes should be
linked properly in the process of building up the mesh by calling Mesh
class functions. Let's say they point to each other like this:

class HalfEdge;
class Vertex {
HalfEdge *edge;
};
class HalfEdge {
Vertex* vert;
HalfEdge *twin;
HalfEdge *next;
Face* face;
};
class Face {
HalfEdge *edge;
};

Now I want to be able to derive from these classes in order to add more
functionality to them (e.g. normal). However, I want that as I derive
from a class, all the pointers among the three classes use the new
derived class instead of base one, so I don't have to cast Vertex* to
MyVertex* everytime I search for an edge->next->vert vertex of next
edge in the loop.

What I try to achieve would look like the three classes being nested
inside the Mesh class, which is a template class and takes template
arguments for both three classes. Let me illustrate:

templace <class VertType, class HalfEdgeType, class FaceType>
class Mesh {
public:
class Vertex {
HalfEdgeType *edge;
};
class HalfEdge {
VertType *vert;
HalfEdgeType *next;

[and so on....]
};

Now, even though this code compiles perfectly it is impossible to use
it as I want because in order to use any of the three nested classes I
would have to specify template arguments for the Mesh class first, but
these arguments have to be the same nested classes I am trying to
instantiate at the same time.

isn't the relationship between Vertex and VertType an "is_a"
relationship?
Vertex is_a VertType

template < class VertType, class HalfEdgeType, class FaceType >
class Mesh
{
class Vertex : public VertType
{
HalfEdgeType *edge;
};
class Face : public FaceType
{
HalfEdgeType *edge
};
class HalfEdge : public HalfEdgeType
{
VertType *vert;
HalfEdgeType *next;
HalfEdgeType *twin;
Face* face; // or FaceType ???
};
};

Take note that i'm completely ignoring ctors and d~tors, which are
going to be crtical in the case you plan to use base pointers to Mesh
elements to provide allocations / deallocations (see discussion below).
The three class parameters will probably have to be classes with
virtual destructors. So the *embedded* class Vertex will look something
like this:

class Vertex : public VertType
{
HalfEdgeType *edge;
public:
Vertex() : edge(0) { }
Vertex(..., HalfEdgeType* p) : VertType(...), edge(p) { }
~Vertex() { } // through inheritance, this d~tor will be virtual
};

Don't ignore the ctors, they are a cornerstone of C++. They'll prevent
some client to come along and destroy your system.
Which can be good news since now you'll be able to create a complete
Mesh in one sweep.

template < typename VertType, typename HalfEdgeType, typename FaceTypeclass Mesh
{
... // embedded members and whatever
public:
Mesh() { } // default ctor invokes default embedded ctors
Mesh(..., ..., ...) : Vertex(...), HalfEdge(...), Face(...) { }
virtual ~Mesh() { }
};

You need to pay attention to what happens when a Mesh element gets
destroyed. If a base class does not have a virtual destructor, you'll
end up leaking memory because only the derived portion of the class
gets deallocated.

So while you are developing this idea, use std::cout << "~Vertex()\n";
outputs in d~tors to verify that your entire object(s) is/are indeed
deallocated.
Of course I could solve this by defining base Vertex, HalfEdge and Face
classes outside the Mesh class, then make Mesh class template and
define nested "iterator" classes, that would walk over links and
automatically cast pointers to my derived classes that I pass as
template arguments to the Mesh class. But I see no practical sense in
constructing and using an "iterator" just to jump from one edge to its
next edge.

Is there any other possibility of how I could inter-link several
classes by using pointers of their derives? Or do I have no other way
than to either perform annoying casting of pointer types or construct
and "++" an iterator each time I follow an edge's next link?

In polymorphism, when properly setup, it doesn't matter whether you are
using a pointer to base or derived. What you do not want is to use
dynamic_casts to convert a base pointer into its derived pointer. The
compiler does this "conversion" automatically with the appropriate
offset applied to the base pointer.

The best way to explain this is to imagine an abstract Shape class.

class Shape
{
public:
Shape() { }
virtual ~Shape() { }
virtual double area() = 0; // pure virtual
}

pure-virtual means area() must be defined in derived classes and hence
you can't create an instance of Shape itself.

You derive from Shape to create a Triangle class, a Rectangle class and
a Circle class. If i then declare a container like this:

std::vector< Shape* > shapes;

That dumb container can store a *mixture* of Triangles, Rectangles and
Circles and still call the correct area() function depending on which
element is accessed. The same goes when you delete each element -
appropriate derived ctor is invoked, which itself invokes the Shape
d~tor. At least one virtual function means you get the magic vtable -
polymorphism. That man - is your goal.

shapes.push_back( new Triangle; ); // a default triangle
shapes.push_back( new Rectangle; );
shapes.push_back( new Circle; );
....
for ( size_t n = 0; n < shapes.size(); ++n)
{
std::cout << shape->area(); // the derived area() !!!
delete *(shapes[n]); // the derived d~tor, which itself invokes
~Shape()
}

Now think about what happens when you start deriving from Mesh.
 
I

ivan.leben

Thanks for the tips, but I'm still not satisfied with replies. What you
told be about ctors and dtors and abstraction and virtual functions
I've known for a long time and I've written thousands of abstract
classes in my lifetime. This Mesh class in fact is already written and
of course the Vertex,HalfEdge and Face classes do have ctors and dtors
etc.

Bart: you are talking about my "abstract" code relying on operations in
derived classes and that it should be part of the abstract interface.
But it doesn't really make sense in this case. I do want the next/prev
pointers of edges and so on to be inside the base classes, because it
doesn't make any sense to leave the user of the Mesh class to write and
maintain these links. All the user wants to do is to be able to specify
where the vertices of the mesh are and how they are connected. This is
done through the mesh construction functions of Mesh class like:

Mesh::addVertex(float x, float y, float z) - returns a pointer to a
newly created Vertex class containing the given coordinates

Mesh::addFace(Vertex **verts, int size) - creates a face having the
[size] number of specified vertices and returns the newly created face.
all the other required topology is constructed as well (edges between
the vertices that don't exist yet etc.)

How the vertices and edges and faces are linked together is not the
work of a user of the Mesh class but instead this should be taken care
of automatically by the Mesh class. However as I create a face by
specifying which its vertices are, I want to get returned (and I want
the mesh to create) a face of my derived type so that it includes my
"normal" member along with the basic stuff needed to link it with other
mesh entities. The trick is I want at the same the pointers of the mesh
entities to become of my derived class types so I can walk around the
mesh in a comfortable way. Of course I already implemented the
adjacency iterators like VertEdgeIter (iterates over edges connected to
a vertex), VertFaceIter (iterates over adjacent faces of a vertex),
FaceEdgeIter (iterate over edges of a face) etc. But I don't want to
use a FaceEdgeIter everytime I just want to pick the next edge (I'm
talking about the "client" code, the code that an end-user of class
Mesh writes). That's why I thought would be nice to have the prev/next
pointers to become of my derived type as I specify these derived
classes as templates arguments of the Mesh class.

Look at these implementations, they all use classes structured in the
same way I am talking about:

http://w3.impa.br/~esdras/tops/classMesh_1_1Surf.html

http://www.ee.surrey.ac.uk/Research...Tree/Ravl.API.Core.Graphs.Half_Edge_Mesh.html

http://www.openmesh.org/

This last one resembles the most what I am trying to achieve. And here
we come to the solution that Peter suggested - that the nested classes
of Mesh class should be derives of the base classes provided through
the template arguments instead of the contrary. This could make sense
if I expose it to the Mesh class user like this:

- Mesh class takes template arguments for each of the basic mesh
entities
- These template arguments are "traits" (<-- these is the main trick!)
of the final mesh entity classes.
- The classes finally used by the user are the "final mesh classes"
(this is mainly the trick that OpenMesh implementation uses)

The only unnatural thing is that each of the traits has to be given
even if we don't want to add any functionallity. But this could be
solved by defining empty base trait classes to use them if
derivation is not needed. See this example:

//////////MESH_CLASS_CODE/////////////

template <class PointType, class VertTraits, class HalfEdgeTraits,
class FaceTraits>
class Mesh {
//forward declaration of class HalfEdge so we can inter-link them
class HalfEdge;

//final vertex class
class Vertex : public VertTraits {
PointType point;
HalfEdge *edge;
};

//final face class
class Face : public FaceTraits {
HalfEdge *edge;
};

//final half-edge class
class HalfEdge : public HalfEdgeTraits {
Vertex *vert;
Face *face;
HalfEdge *next;
HalfEdge *twin;
};

//implementation of functions follows
//....
};

class BaseVertTraits {
};

class BaseHalfEdgeTraits {
};

class BaseFaceTraits {
};

//////////END::MESH_CLASS_CODE/////////////

Now, when the user of the class wants to add a normal member to a face
it does so like this:

class MyFaceTraits {
float normal;
};

typedef Mesh <
Vector3,
BaseVertTraits, //<---- base traits used
BaseHalfEdgeTraits, //<---- base traits used
MyFaceTraits, //<---- custom traits used
> MyMesh;

And then all the links inside the final classes and all the classes
returned by functions of Mesh class use the final nested classes like
this:

void calcTriangleNormal(MyMesh::Face *f) {
MyMesh::Vertex *v1 = f->edge->vert;
MyMesh::Vertex *v2 = f->edge->next->vert;
MyMesh::Vertex *v3 = f->edge->next->next->vert;
Vector2 side1 = v2->point - v1->point;
Vector2 side2 = v3->point - v1->point;
f->normal = normalize(cross(side1,side2));
}

int main (int argc, char ** argv) {

MyMesh mesh;
MyMesh::Vertex *v1 = mesh.addVertex(Vector3(-1,0,0));
MyMesh::Vertex *v2 = mesh.addVertex(Vector3(1,0,0));
MyMesh::Vertex *v3 = mesh.addVertex(Vector3(0,1,0));
MyMesh::Face *f = mesh.addFace(v1, v2, v3);
calcTriangleNormal(f);
};


Of course this would be extended to faces with arbitrary number of
vertices. What do you think about this kind of implementation?
 
B

Bart

Bart: you are talking about my "abstract" code relying on operations in
derived classes and that it should be part of the abstract interface.
But it doesn't really make sense in this case. I do want the next/prev
pointers of edges and so on to be inside the base classes, because it
doesn't make any sense to leave the user of the Mesh class to write and
maintain these links.

Indeed. But it doesn't make sense to make the Mesh class responsible
for it either. My point was that each class should be responsible for
its own links.
All the user wants to do is to be able to specify
where the vertices of the mesh are and how they are connected.

So specify this by exposing methods in the Vertex, Face, and HalfEdge
class.
- Mesh class takes template arguments for each of the basic mesh
entities
- These template arguments are "traits" (<-- these is the main trick!)
of the final mesh entity classes.
- The classes finally used by the user are the "final mesh classes"
(this is mainly the trick that OpenMesh implementation uses)

Using traits is okay, but why do you want to expose data members like
this. If you want to use the traits to specify types then just add
template parameters to them as well - say, Vertex<float> or something.
But don't inherit from those classes because that doesn't make sense.

Regards,
Bart.
 
I

ivan.leben

I think that links between mesh entities should be managed by Mesh
class because there is no sane way to put it all into Vertex, Edge and
Face classes and it's not type-safe either. For example, when you want
to create a new face, you have to create all it's edges, make them
point to that face and next-prev-link-them, plus make vertices and face
point to their first adjacent edge. Now look at this example:

template<class PointType=Vector2>
class Vertex {
PointType point;
HalfEdge *edge;
};

class HalfEdge {
Vertex<> *vert; // <----- we don't know the type of vert so we can
only use default
[othe members...]
};

Now if a half-edge would have a function "assignVert()" and in this
function it would set its vert pointer to given vertex and set that
vertex's "edge" pointer back to itself, the type-unsafeness would cause
a part of the "point" member of Vertex to get overwritten by the edge
pointer data if the actual type of Vertex would be Vertex<Vector3>
instead of Vertex<Vector2>. This is because the actual "edge" pointer
in the Vertex<Vector3> has offset 4 bytes more than Vertex<Vector2> off
the base address of the class, considering that Vector2 and Vector3 use
floats as their coordinates. You get the problem?

And even if the vertex itself would have a function named setEdge()
that would set its edge pointer, again a wrong type of that function
would get instantiated when an edge would dereference its Vertex<>*
pointer and call setEdge function. But if I leave end-user call all
these functions than what did he gain by using the classes? Nothing...
all the work is on him.

Now I could make HalfEdge class have a template argument for PointType
too, but then I should do the same for Face class and that all too much
and it looks awfully ugly! :(

That's why I think that it should all be handled on a global scale by a
single class, that would know of all the actual types of Vertexes and
Edges and Faces you are using and properly use the pointers. You got
any smarter solution here?
 
B

Bart

template<class PointType=Vector2>
class Vertex {
PointType point;
HalfEdge *edge;
};

class HalfEdge {
Vertex<> *vert; // <----- we don't know the type of vert so we can
only use default
[othe members...]
};

The HalfEdge class should also have a template parameter in this case.
And even if the vertex itself would have a function named setEdge()
that would set its edge pointer, again a wrong type of that function
would get instantiated when an edge would dereference its Vertex<>*
pointer and call setEdge function. But if I leave end-user call all
these functions than what did he gain by using the classes? Nothing...
all the work is on him.

I didn't say the end-user would do these calls. The Mesh class can make
the calls and expose something else to the user.
Now I could make HalfEdge class have a template argument for PointType
too, but then I should do the same for Face class and that all too much
and it looks awfully ugly! :(

How is your solution less ugly? You wanted to use traits, so either use
them everywhere or not at all. Making a hybrid that uses traits in some
cases but not others is much more ugly.
That's why I think that it should all be handled on a global scale by a
single class, that would know of all the actual types of Vertexes and
Edges and Faces you are using and properly use the pointers.

That's why I said your solution is not object-oriented. If you just
want to have a huge class that handles everything then there's no point
in having all the sub-classes and forcing yourself to use inheritance
like you do.
You got any smarter solution here?

A smarter solution would be to review your design and abandon some of
the things that you forced yourself to use because of preconceived
notions. I glanced at the OpenMesh site very quickly but stoped right
at the point where they said that they want to avoid the overhead of
virtual functions. I mean come on! These guys seem to be stuck in 1996.

Regards,
Bart.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top