8

I am working on a real-time terrain rendering engine. I have a QuadTree and Node classes. The QuadTree class expands/collapses a tree depending on where the camera is. So it makes sense that the QuadTree is responsible for the Node objects lifetime. The problem is that there is many data which needs to be associated with that lifetime and have nothing to do with the QuadTree. These data might not even be related to each others. I have been looking for a clean way to decouple my classes correctly without success. Every changes ( sometimes even minor ones ) required changes through several files, most of the time with files not related to it. I finally have something that seem to work, but I think I have been trying to decouple it too much, which increased the complexity for not much benefits. This is how I did it:

My QuadTree class should not deal with anything but the tree. But everytime I create a Node, I need to associate data with these nodes. Since this would pollute the class to do it in the QuadTree class, I added an interface to communicate between the QuadTree and the class whose job is to create these data. At this point, I think I have been doing it the correct way. Pseudo-code:

class QTInterface
{
    virtual void nodeCreated( Node& node ) = 0;
    virtual void nodeDestroyed( Node& node ) = 0;
};

class QuadTree
{
public:
    QuadTree( ...., QTInterface& i ) : i( i ) {}

    void update( Camera camera )
    {
        // ....
        i.nodeCreated( node );
        // ....
        i.nodeDestroyed( node );
    }

private:
    QTInterface& i;
    Node root;
};

Now I need to associate some random data to each of these Nodes. So in my class which implements QTInterface, I have a map doing exactly that:

class Terrain : public QTInterface
{
    void nodeCreated( Node node )
    {
        Data data;
        // ... create all the data associated to this node
        map[ node ] = data
        // One more thing, The QuadTree actually needs one field of Data to continue, so I fill it there
        node.xxx = data.xxx
    }

    void nodeDestroyed( Node node )
    {
        // ... destroy all the data associated to this node
        map.erase( node );
    }

};

Node and QuadTree are now independent from other parts of the code and if I have to got back there, is will only be because I have to change something in the QuadTree algorithm.

But that's where I think I have my first problem. Most of the time I do not worry about optimization until I see it, but I think that if I have to add this kind of overhead to decouple my classes properly, that's because the design has flaws.

Another problem with this, is that the data associated with the node will end up beeing a bag of a lot of data. For the same results with less pain I could have just used the Node class as a bag.

So, several questions here:

  • Am I overcomplicating things? Should I just have extended the Node class, making it a bag of data beeing used by some classes?

  • If no, how good is my alternative? Is there a better way?

  • I always have an hard time with how to decouple my classes correctly. Any advices to give that I could use later? ( Like what questions do I have to ask myself for example, or how do you process? Thinking about this on paper seems very abstract to me, and immediately code something results in later refactoring )

Note: I tried to simplify the problem as much as I could to avoid a very long question filled with unnecessary details. Hope I have not omitted important ones.

Edit: Some details has been asked:

The camera cannot only choose the visible nodes because it would mean I have to keep all the nodes in memory, which is not possible because the engine is supposed to render very large terrains with an high resolution. The depth of the tree would easily be 25+. Other than that it is also easier to know when new nodes have been created/destroyed ( basically as easier has: if the node has no children and the depth isn't 0, that's because the node needs to be created, if the node has children and the algorithm stops there, it means they were visible the frame before but not now so I have to delete them, and the data bound to it ).

Example of data that needs to be computed is the height and the normals of these nodes ( https://en.wikipedia.org/wiki/Heightmap and https://en.wikipedia.org/wiki/Normal_mapping ).

Creating these data involves:

  • sending Node data computed by the QuadTree to a multithreaded workqueue
  • Once the heightmap has been generated, update the only field of the Node that QuadTree needs to continue the algorithm: The min/max height.
  • After that, update the GPU textures using the heightmap and normalmap computed on the CPU.

But this is just he way of computing the data. I can also do it on the GPU, and it will require completely different steps. And that's a reason I want to decouple it from the QuadTree class, because I'd like to swap between the two easily ( for testing purposes ) without having to refactor all my code. design coupling

  • 1
    Why do you create and destroy nodes all the time? Shouldn't the camera simply choose which nodes of the tree should be displayed? Also, can you give a concrete example of the data that you want to add? – null Nov 12 '16 at 19:01
  • I've edited my post to answer your questions. – Aulaulz Nov 12 '16 at 19:51
2

For dynamically associating and disassociating data on the fly independent of a QT node's lifetime while the QT combined with the camera have the knowledge of when the data should be associated/disassociated on the fly, that's a bit tricky to generalize and I think your solution is actually not bad. That's a tough thing to design against in a very nice and generalized way. like, "uhh.... test it well and ship it!" Okay, little bit of a joke. I'll try to offer some train of thought to explore. One of the things that glared out to me most was here:

void nodeCreated(Node& node)
{
    ...
    // One more thing, The QuadTree actually needs one field of 
    // Data to continue, so I fill it there
    node.xxx = data.xxx
}

This tells me that a node ref/pointer isn't just used as a key into an external associative container. You're actually accessing and modifying internals of the quadtree node outside the quadtree itself. And there should be a fairly easy way to at least avoid that for starters. If that's the only place where you're modifying node internals outside the quadtree, then you might be able to do this (let's say xxx is a pair of floats):

std::pair<float, float> nodeCreated(const Node& node)
{
    Data data;
    ...
    map[&node] = data;
    ...
    return data.xxx;
}

At which point the quadtree can use the return value of this function to assign xxx. That already loosens up the coupling quite a bit when you're no longer accessing the internals of a tree node outside the tree.

Eliminating the need for Terrain to access quadtree internals would actually eliminate the only place where you're coupling things very unnecessarily. It's the only real PITA if you swap things out with a GPU implementation, for example, since the GPU implementation might use a totally different internal rep for nodes.

But for your performance concerns, and there I have a lot more thoughts than how you maximally achieve decoupling with this sort of thing, I would actually suggest a very different representation where you can turn data association/disassociation into a cheap constant-time operation. It's a little bit hard to explain to someone not used to constructing standard containers that require placement new to construct elements in place from pooled memory so I'll start with some data:

struct Node
{
    ....
    // Stores an index to the data being associated on the fly
    // or -1 if there's no data associated to the node.
    int32_t data;
};

class Quadtree
{
private:
    // Stores all the data being associated on the fly.
    std::vector<char> data;

    // Stores the size of the data being associated on the fly.
    int32_t type_size;

    // Stores an index to the first free index of data
    // to reclaim or -1 if the free list is empty.
    int32_t free_index;

    ...

public:
    // Creates a quadtree with the specified type size for the
    // data associated and disassociated on the fly.
    explicit Quadtree(int32_t itype_size): type_size(itype_size), free_data(-1)
    {
        // Make sure our data type size is at least the size of an integer
        // as required for the free list.
        if (type_size < sizeof(int32_t))
            type_size = sizeof(int32_t);
    }

    // Inserts a buffer to store a data element and returns an index
    // to that.
    int32_t alloc_data()
    {
        int32_t index = free_index;
        if (free_index != -1)
        {
            // If a free index is available, pop it off the
            // free list (stack) and return that.
            void* mem = data.data() + index * type_size;
            free_index = *static_cast<int*>mem;
        }
        else
        {
            // Otherwise insert the buffer for the data
            // and return an index to that.
            index = data.size() / type_size;
            data.resize(data.size() + type_size);
        }
        return index;
    }

    // Frees the memory for the nth data element. 
    void free_data(int32_t n)
    {
        // Push the nth index to the free list to make
        // it available for use in subsequent insertions.
        void* mem = data.data() + n * type_size;
        *static_cast<int*>(mem) = free_index;
        free_index = n;
    }

    ...
};

That's basically an "indexed free list". But when you use this rep for the associated data, you can do something like this:

class QTInterface
{
    virtual std::pair<float, float> createData(void* mem) = 0;
    virtual void destroyData(void* mem) = 0;
};

void Quadtree::update(Camera camera)
{
    ...
    node.data = alloc_data();
    node.xxx = i.createData(data.data() + node.data * type_size);
    ...
    i.destroyData(data.data() + node.data * type_size);
    free_data(node.data);
    node.data = -1;
    ...
}

class Terrain : public QTInterface
{
    // Note that we don't even need access to nodes anymore,
    // not even as keys to use. We've completely decoupled
    // terrains from tree internals.
    std::pair<float, float> createData(void* mem) override
    {
        // Construct the data (placement new) using the memory
        // allocated by the tree.
        Data* data = new(mem) Data(...);

        // Return data to assign to node.xxx.
        return data->xxx;
    }

    void destroyData(void* mem) override
    {
        // Destroy the data.
        static_cast<Data*>(mem)->~Data();
    }
};

Hopefully this all makes sense, and naturally it's a bit more decoupled from your original design since it doesn't require clients to have internal access to tree node fields (it now no longer even requires knowledge of nodes whatsoever, not even to use as keys), and it's considerably more efficient since you can associate and disassociate data to/from nodes in constant-time (and without using a hash table which would imply a much bigger constant). I'm hoping your data can be aligned using max_align_t (no SIMD fields, e.g.) and is trivially copyable, otherwise things get considerably more complex since we'd need an aligned allocator and might have to roll our own free list container. Well, if you just have non-trivially copyable types and don't need more than max_align_t, we can use a free list pointer implementation that pools and links unrolled nodes storing K data elements each to avoid the need to reallocate existing memory blocks. I can show that if you need such an alternative.

It is a bit advanced and very C++ specific, considering the idea of allocating and freeing memory for elements as a separate task from constructing and destroying them. But if you do it this way, Terrain absorbs the minimum responsibilities and requires no internal knowledge of the tree representation whatsoever anymore, not even handles to opaque nodes. Yet this level of memory control is typically what you need if you want to design the most efficient data structures.

The fundamental idea there is that you have the client using the tree pass in the type size of the data they want to associate/disassociate on the fly to the quadtree ctor. Then the quadtree has the responsibility of allocating and freeing memory using that type size. Then it passes on the responsibility of constructing and destroying the data to the client using QTInterface and dynamic dispatch. The only responsibility, therefore, outside of the tree that's still related to the tree, is constructing and destroying elements from memory that the quadtree allocates and deallocates itself. At that point the dependencies become like this:

enter image description here

Which is very reasonable considering the difficulty of what you're doing and the scale of the inputs. Basically your Terrain then only depends on Quadtree and QTInterface, and no longer the internals of the quadtree or its nodes. Previously you had this:

enter image description here

And of course a glaring problem with that, especially if you're considering trying out GPU implementations, is that dependency from Terrain to Node, since a GPU implementation would likely want to use a very different node rep. Of course if you want to go hardcore SOLID, you'd do something like this:

enter image description here

... along with possibly a factory. But IMO that's complete overkill (at the very least INode is total overkill IMO) and wouldn't be very helpful in a case as granular as a quadtree function if each one required a dynamic dispatch.

I always have an hard time with how to decouple my classes correctly. Any advices to give that I could use later? ( Like what questions do I have to ask myself for example, or how do you process? Thinking about this on paper seems very abstract to me, and immediately code something results in later refactoring )

Just generally and crudely speaking, decoupling often boils down to limiting the amount of information a particular class or function requires about something else to do its thing.

I'm assuming you're using C++ since no other language I know has that exact syntax, and in C++ a very effective decoupling mechanism for data structures is class templates with static polymorphism if you can use them. If you consider the standard containers like std::vector<T, Alloc>, vector isn't coupled to whatever you specify for T whatsoever. It only requires that T satisfy some basic interface requirements like that it's copy-constructible and has a default constructor for the fill constructor and fill resize. And it'll never require changes as a result of T changing.

So, tying it to the above, it allows the data structure to be implemented using the absolute bare minimal knowledge of what it contains, and that decouples it to the extent where it doesn't even need any type information in advance (advance here is talking in terms of code dependencies/coupling, not compile-time information) about what T is.

The second most practical way to minimize the amount of information required is to use dynamic polymorphism. For example, if you want to implement a reasonably generalized data structure that minimizes knowledge of what it stores, then you might capture the interface requirements for what it stores in one or more interfaces:

// Contains all the functions (pure virtual) required of the elements 
// stored in the container.
class IElement {...};

But either way it boils down to minimizing the amount of information you need in advance by coding to interfaces rather than to concrete details. Here the only big thing you're doing that seems to require a whole lot more information than required is that your Terrain has to have complete information about the internals of a Quadtree node, e.g. In such a case, assuming the only reason you need that is to assign a piece of data to a node, we can easily eliminate that dependency to a tree node's internals by merely returning the data that should be assigned to the node in that abstract QTInterface.

So if I want to decouple something, I just focus on what it needs to do it things and come up with an interface for it (either explicit using inheritance or implicit using static polymorphism and duck typing). And you already did that to some extent from the quadtree itself using QTInterface to allow the client to override its functions with a subtype and provide the concrete details required for the quadtree to do its thing. The only place where I think you fell short is that the client still requires access to the internals of the quadtree. You can avoid that by increasing what QTInterface does which is precisely what I suggested when I made it return a value to be assigned to node.xxx in the quadtree implementation itself. So it's just a matter of making things more abstract and interfaces more complete so that things don't require unnecessary information about each other.

And by avoiding that unnecessary information (Terrain having to know about Quadtree node internals), you're now more free to swap out the Quadtree with a GPU implementation, for example, without changing the Terrain implementation as well. What things don't know about each other is free to change without affecting each other. If you really want to swap out GPU quadtree implementations from CPU ones, you might go a little bit towards the SOLID route above with IQuadtree (making the quadtree itself abstract). That comes with a dynamic dispatch hit which might get a bit expensive with the tree depth and input sizes you're talking about. If not, at least it requires far less changes to the code if the things using the quadtree don't have to know about its internal node representation to work. You might be able to swap one with the other just updating a single line of code for a typedef, e.g., even if you don't use an abstract interface (IQuadtree).

But that's where I think I have my first problem. Most of the time I do not worry about optimization until I see it, but I think that if I have to add this kind of overhead to decouple my classes properly, that's because the design has flaws.

Not necessarily. Decoupling often implies shifting a dependency away from the concrete to the abstract. Abstractions tend to imply a runtime penalty unless the compiler is generating code at compile-time to basically eliminate the abstraction cost at runtime. In exchange you get much more breathing room to make changes without affecting other things, but that often extracts some kind of performance penalty unless you're using code generation.

Now you can do away with the need for a non-trivial associative data structure (map/dictionary, i.e.) to associate data to nodes (or anything else) on the fly. In the case above I just made the nodes directly store an index to the data which gets allocated/freed on the fly. Doing these types of things isn't so much related to studying how to decouple things effectively so much as how to utilize memory layouts for data structures effectively (more in the pure optimization realm).

Effective SE principles and performance are at odds with each other at sufficiently low levels. Often decoupling will split memory layouts apart for fields commonly accessed together, may involve more heap allocations, may involve more dynamic dispatch, etc. It becomes quickly trivialized as you work towards higher-level code (ex: operations applying to entire images, not per-pixel operations when looping through individual pixels), but it does have a cost which ranges from trivial to severe depending on how much those costs are incurred in your most critical, loopy code performing the lightest work in each iteration.

Am I overcomplicating things? Should I just have extended the Node class, making it a bag of data beeing used by some classes?

I personally don't think that's so bad if you are not trying to generalize your data structure too much, only using it in a very limited context, and you're dealing with an extremely performance-critical context for a kind of problem you haven't tackled before. In that case you would turn your quadtree into an implementation detail of your terrain, e.g., rather than something to be widely and publicly used, in a similar way someone might turn an octree into an implementation detail of their physics engine by no longer distinguishing the idea of "public interface" from "internals". Maintaining invariants related to the spatial index then turns into a responsibility of the class using it as a private implementation detail.

To design an effective abstraction (interface, i.e.) in a performance-critical context often requires you to thoroughly understand the bulk of the problem and a very effective solution for it upfront. It can actually turn into a counter-productive measure to try to generalize and abstract the solution while simultaneously trying to figure out the effective design over multiple iterations. One of the reasons is that performance-critical contexts require very efficient data representations and access patterns. Abstractions put a barrier between the code wanting to access the data: a barrier that's useful if you want the data to be free to change without affecting such code, but an obstacle if you're simultaneously trying to figure out the most effective way to represent and access such data in the first place.

But if you do it this way, again I'd err on the side of turning the quadtree into a private implementation detail of your terrains, not something to be generalized and used outside of their implementations. And you'd have to forego the idea of being able to so easily swap out GPU implementations from CPU implementations, since that would normally require coming up with an abstraction that works for both and not directly depending on the concrete details (like node reps) of either.

The Point of Decoupling

But maybe in some cases this might even be acceptable for more publicly-used things. Before people think I'm spouting crazy nonsense, consider image interfaces. How many of them would suffice for a video processor that needs to apply image filters on the video in realtime if the image didn't expose its internals (direct access to its underlying array of pixels in a specific pixel format)? There are none that I know of using something like an abstract/virtual getPixel here and setPixel there while doing pixel format conversions on a per-pixel basis. So in sufficiently performance-critical contexts where you have to access things on a very granular level (per-pixel, per-node, etc), you might sometimes have to expose the internals of the underlying structure. But inevitably you'll have to couple things tightly as a result, and it's not going to then be easy to change the underlying representation of images (change in image format, e.g.), so to speak, without affecting everything accessing its underlying pixels. But there might be fewer reasons to change in that case, since it might actually be easier to stabilize the data representation than the abstract interface. A video processor might be able to settle on the idea of using 32-bit RGBA pixel formats and that design decision might be unchanging for years to come. Meanwhile the operations that an image might need to provide might be highly unstable even in the following months after its conception.

Ideally you want the dependencies to flow towards stability (unchanging things) because changing something which has many dependencies multiplies in cost with the number of dependencies. That may or may not be abstractions in all cases. Of course that's ignoring the benefits of information hiding in maintaining invariants, but from a coupling standpoint, the main point of decoupling is to make things less costly to change. That means redirecting dependencies from things that could change to things that won't change, and that doesn't help in the slightest if your abstract interfaces are the most rapidly-changing parts of your data structure.

If you want to at least improve upon that slightly from an coupling perspective, then separate your node parts which clients need to access away from parts that don't. I'm assuming clients at least don't have to update the links of the node, for example, so there's no need to expose the links. You should at least be able to come up with some value aggregate that is separate from the entirety of what nodes represent for clients to access/modify, like NodeValue.

| improve this answer | |
3

Reading between the lines, it seems you are too focussed on your tree view. Your idea seems to be "I have this tree, with nodes, that I attach objects to and the tree has to tell the objects what to do". It should be the other way around though. After all, the tree is just a view that should follow your (problem domain) objects. The objects should have no knowledge/traces of the tree(nodes). It is the view that reads the objects and presents itself accordingly.

You may want to implement some events on your objects that the tree can subscribe to, so it knows when to collapse, expand, create or delete a node.

So, let the tree follow your model.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.