Tree data structure storing/retrieval/walk

Hi there,
I think I need a tree implementation for what I try to achieve.

Basically, I start to grow the tree (and visualize it).
First branch… growing… this is a polyline basically.
Then, first branching. It can be another polyline.
etc.
No problem.

BUT, if I want to replay the growth, I’d need to store some sorting feature.

I thought about creating a class having:

  • a ofPolyline or ofPath ( still not sure as there)
  • branching information like “at which percent of the polyline I have a new branch” AND “which is the index of the new branch in the Vector?”

I would have a Vector containing that structure and with that structure, I could redraw the whole tree.

Any ideas or opinions would be VERY appreciated.
That’s algorithmically interesting.

Julien

Hi there,
Did you consider using ofNode? maybe you could use that to apply transformations to branches. Each ofNode could draw an ofPolyline.

These days there is somebody interested on a similar topic:

1 Like

Hi @Jordi and many thanks for your answer.

I’d store all ofNode in a vector and that vector itself would be drawn to as the main branch… But I don’t want any branch to be the main one.

Maybe a specific class handling each crack + branching points.

example:

  • create a first polyline growing (I add a vertex, I add a second one and the line grow from the first point to the second etc… probably need interpolation for growing progressively)
  • at some point, a branch start. It is another polyline and the first one keep the trace of the which one is the child and which one is the parent and from which point it has started…
    etc.

I’d have a kind of mega class containing and handling a set of polylines.
wow. it makes sense.
maybe I don’t feel ok with ofNode, but that would help.

ofNode is really not useful for this, at least not for the data structure. it can be helpful to express the transformations relative to the parent branches but not for storing the data structure.

I gave an answer to the forum post jordi posts above in this github issue: https://github.com/openframeworks/openFrameworks/issues/5428

@julienbayle what you post is pretty much a tree data structure with the particularity that you need the pct at which the child starts. I would use something like:

class Branch{
struct Child{
    float pct;
    shared_ptr<Branch> ptr;
}

std::vector<Child> children;
}

then if you want to use ofNode to represent the transformations you can add it to the Branch class and parent every child to it’s parent using ofNode::setParent

1 Like

Thanks @arturo.
Actually, I think that’s exactly the way I need.
A branch would have children that would also be branches themselves, are we agree?
Basically, I’m seeking how to implement it. It seems very simple but I have to figure it out.

The idea is: each branch has to be a polyline (or path?) because I need to be able to draw it progressively.
For instance, at the beginning I have only one branch. at some point, branching occur. So if I want to keep the percent, I probably need to precalculate each branch’s dots and to draw them progressively using a polyline to which I add progressively vertices from the branch’s dots… the whole into a branch class…

A branch would have children that would also be branches themselves, are we agree?

Yes that’s it. From your other post and this i think something like this should work:

class Branch{
struct Child{
    float pct;
    shared_ptr<Branch> ptr;
}

std::vector<Child> children;
float pct;
ofPolyline polyline;
ofVbo vbo;

public:
void setup(){
    //initialize polyline
    vbo.setVertexData(polyline.getVertices().data(), polyline.size(), GL_STATIC_DRAW);
}

void update(float pct){
    this->pct = pct
    for(auto & child: children){
        if(pct>child.pct){
            child.ptr.update(pct-child.pct);
        }
    }
}

void draw(){
    auto pct = ofClamp(this->pct, 0, 1);
    vbo.draw(GL_LINE_STRIP, 0, polyline.size() * pct);
    for(auto &child: children){
        child.ptr->draw()
    }
}

of course the pct you input in update to the “root” the branch that contains everything else recursively has to go beyond 1

for generating the geometry of the children branches i think using ofNode would help to draw them relative to the parent so every branch doesn’t need to know it’s absolute position which could be tricky

@arturo, thanks again.
I think I got the vbo thing.
Now, I’m just trying to generate randomly (just for testing) some children (in the code, n is the maximum number of branches as I feel/guess that infinite depth problem as in recursive code…)
That’s give me an error.

How could I create new children ? Should I do it “outside” of the class in my main or my super class ?

    void update(float pct){
    this->pct = pct;
    for(auto & child: children){
        if(pct>child.pct){
            child.ptr->update(pct-child.pct);
        }
    }
    
    if (children.size() <n) {
        if (ofRandom(1000) < 10) children.push_back(* new Branch());
    }

}

Some progression :

main

void ofApp::update(){

if (curr < 100.)
{
    myBranch.update(curr++);
}
else curr = 0.;

}

Branch class

class Branch {
    
    struct Child{
        float pct;
    shared_ptr<Branch> ptr;
};

std::vector<Child> children;
float pct;
ofPolyline polyline;
ofVbo vbo;
int n;

public:

void setup(){
    polyline.addVertex(ofGetWidth()/2., ofGetHeight()/2.);
    for(int i = 1 ; i <100 ; i++)
    {
        polyline.addVertex(polyline[i-1].x+ofRandom(-5,50),polyline[i-1].y+ofRandom(-5,5));
    }
    //initialize polyline
    vbo.setVertexData(polyline.getVertices().data(), (int)polyline.size(), GL_STATIC_DRAW);
    
    n = 4;
    
    children.resize(10);
    
}

void update(float pct){
    this->pct = pct;
    for(auto & child: children){
        if(pct>child.pct){
            child.ptr->update(pct-child.pct);
        }
    }
    
    
    if (children.size() < 3 ) {
        if (ofRandom(1000) < 100) {
            children.push_back(* new Child());
            children[children.size()-1].pct = 0;
        }
    }
}

void draw(){
    auto pct = ofClamp(this->pct, 0, 1);
    vbo.draw(GL_LINE_STRIP, 0, polyline.size() * pct);
    for(auto &child: children){
        child.ptr->draw();
}

}
};

(some flaw including the code here but not {} error etc all is ok on that side)

It gives some debug stops with auto pct = ofClamp(this->pct, 0, 1); etc.
Seems something occurs bad with pct.

okay.
my problem is how to allocate a new Branch to the Child pointer…
confused.

@arturo, would you help me one more time about how to allocate a new branch ?
I mean, where and how I can create a new branch in my code ?
that shared ptr thing blurs me.

The problem is you are creating the children in update so you are creating children indefinitely and also you are not limiting the recursion somehow so every child is creating children which in turn are creating children, which in turn… without anything that stops it.

You should create children only once in setup and also set a limit where children stop being created, i would create a second setup method, a private one, that takes a level parameter, once that level is greater than some value you stop creating new children.

if (children.size() < 3 was intended to do that but I think my problem is the creation itself. how can I, basically, do that properly ? I’m still confused with the part.

yeah but if(children<3) will still add 3 children each of which will add 3 children which will in turn add 3 children without no condition to stop. you need somthing that makes it stop after a certain number of levels too

To create them in setup:

void setup(int level){
//setup polyline
this->level = level;

if(level<maxLevel){
    for(size_t i = 0;i<maxNumChildren;i++){
        children.emplace_back();
        children.back().pct = pct;
        children.back().ptr.reset(new Branch);
        children.back().ptr->setup(level+1);
    }
}

Thanks @arturo
Almost there.
I created a Branch method kill() that clear all of I want to reset the whole stuff.
BUT, I have all children starting at the pct = 0.
weird.

Ok.
I think I understood.
Actually, if I store pct “only”, that’s not enough.
I have to store the new coordinates (origin of each branch) too. By store, I mean… to use it in setup which means that maybe I cannot do this that way… Not sure.

The idea is branching over branching etc.

Maybe, I have to do that using another way.
That wouldn’t be that efficient but maybe… using different class and not using the shared_ptr.

My main ‘problem’ is : I’d like to specify the code to do only one cracking without branching, many with branching etc… I’d need to code a control layer changing the behavior of the whole system.
I should hire you on that project :slight_smile:

you can pass any information you need in setup or the constructor when you create the child, also you can avoid having to pass the origin if you use ofNode and just parent every child to it’s parent when creating it. that way the children don’t need to know their absolute position only start in 0,0

also you can (and should) avoid the shared pointer if you don’t need to pass the branches from outside but it shouldn’t make any difference in terms of what you can do with the children later or during setup

Branching !

Need more controls like Branch growth control (orientation, speed, etc) etc but the principle is validated, I think.

Still a small remaining problem: clearing the branch system.
If I clear the polyline vector, it doesn’t seem to be enough.
I run the code. It draws. At some point I want to reset it so I reset the master pct value then I clear polyline and I re-setup the whole. Weirdly, It is “as if” the system was keeping things in memory… I have some branches already drawn and static etc.

I have a “candid” kill() function:

void kill()
{
    polyline.clear();
    children.clear();
    vbo.clear();
    vbo.clearVertices();

    //pct = 0.;
}

And It doesn’t seem to be enough.