how to link classes using pointers of their derived classes

Discussion in 'C++' started by ivan.leben@gmail.com, Sep 6, 2006.

  1. Guest

    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?
     
    , Sep 6, 2006
    #1
    1. Advertising

  2. Bart Guest

    wrote:
    > 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.
     
    Bart, Sep 6, 2006
    #2
    1. Advertising

  3. Salt_Peter Guest

    wrote:
    > 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 FaceType
    >

    class 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.
     
    Salt_Peter, Sep 6, 2006
    #3
  4. Guest

    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?
     
    , Sep 6, 2006
    #4
  5. Bart Guest

    wrote:
    <snip>
    > 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.
     
    Bart, Sep 6, 2006
    #5
  6. Guest

    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?
     
    , Sep 6, 2006
    #6
  7. Bart Guest

    wrote:
    <snip>
    > 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.
     
    Bart, Sep 7, 2006
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    336
  2. Replies:
    1
    Views:
    405
    myork
    May 23, 2007
  3. Replies:
    1
    Views:
    395
    Victor Bazarov
    May 23, 2007
  4. bgold
    Replies:
    12
    Views:
    1,030
    James Kanze
    Jan 1, 2008
  5. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    695
Loading...

Share This Page