Overall algorithm – bunny

关闭influence计算                                                             打开influence计算

 

Timer 插入位置:

FFAnalyzer::SeqPrint()

{

………

for (int l = 0; l < layer_size; l++)

{

    /*

    * Nl: number of dual verts in current layer

    * h : head for printing queue of the layer

    * t : tail for printing queue of the layer

    */

    layer_search.Reset();

    layer_search.Start();

    int Nl = layers_[l].size();

    int h = print_queue_.size();

    int t;

    if (l == 0)

    {

        t = Nl;

    }

    else

    {

        t = h + Nl;

    }

    if (h == t)

    {

        continue;

    }

    /* max_z_ and min_z_ in current layer */

    min_z_ = 1e20;

    max_z_ = -min_z_;

    for (int i = 0; i < Nl; i++)

    {

        WF_edge *e = layers_[l][i];

        point u = e->pvert_->Position();

        point v = e->ppair_->pvert_->Position();

        min_z_ = min(min_z_, (double)min(u.z(), v.z()));

        max_z_ = max(max_z_, (double)max(u.z(), v.z()));

    }

    if (!GenerateSeq(l, h, t))

    {

        fprintf(stderr,

            "All possible start edge at layer %d has been tried but no feasible sequence is obtained.\n",

            l + 1

            );

        bSuccess = false;

        break;

    }

    layer_search.Stop();

   

    string str = std::to_string(l) + ":";

    const char *msg = str.c_str();

    char* cstr = new char[str.length() + 1];

    strcpy(cstr, msg);

    layer_search.Print(cstr);

    printf("layer size: %d\n", Nl);

    printf("layer %d finished\n", l);

    printf("--------------\n");

}

……..

}

 

bool FFAnalyzer::GenerateSeq(int l, int h, int t)

{

    Timer ind_search;

    ind_search.Reset();

    ind_search.Start();

    /* last edge */

    assert(h != 0);                        // there must be pillars

    WF_edge *ei = print_queue_[h - 1];

    if (debug_)

    {

        fprintf(stderr, "-----------------------------------\n");

        fprintf(stderr, "Searching edge #%d in layer %d, head %d, tail %d\n",

            ei->ID() / 2, l + 1, h, t);

    }

    /* exit */

    if (h == t)

    {

        return true;

    }

    /* next choice */

    multimap<double, WF_edge*> choice;

    multimap<double, WF_edge*>::iterator it;

    /* next edge in current layer */

    int Nl = layers_[l].size();

    for (int j = 0; j < Nl; j++)

    {

        WF_edge *ej = layers_[l][j];

        /* cost weight */

        double cost = GenerateCost(ei, ej);

        if (cost != -1)

        {

            choice.insert(pair<double, WF_edge*>(cost, ej));

        }

    }

    ind_search.Stop();

    ind_search.Print("Single strut: ");

    /* ranked by weight */

    for (it = choice.begin(); it != choice.end(); it++)

    {

        WF_edge *ej = it->second;

        print_queue_.push_back(ej);

        /* update printed subgraph */

        UpdateStructure(ej);

        /* update collision */

        vector<vector<lld>> tmp_angle(3);

        UpdateStateMap(ej, tmp_angle);

        if (debug_)

        {

            fprintf(stderr, "Choose edge #%d in with cost %lf\n\n", ej->ID() / 2, it->first);

        }

        if (GenerateSeq(l, h + 1, t))

        {

            return true;

        }

        RecoverStateMap(ej, tmp_angle);

        RecoverStructure(ej);

        print_queue_.pop_back();

    }

    return false;

}