00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #ifndef VCG_MT_H
00031 #define VCG_MT_H
00032
00033 #include <vector>
00034 #include <queue>
00035 #include <map>
00036
00037 #include <vcg/space/sphere3.h>
00038 #include <vcg/space/point3.h>
00039 #include <wrap/gui/frustum.h>
00040
00041 namespace vcg {
00042
00053 template <class C> class MT {
00054 public:
00055 typedef C Cell;
00056
00057 private:
00058
00059 class Frag:public std::vector<Cell *> {};
00060
00061 struct Node {
00062 std::vector<Node *> in;
00063 std::vector<Node *> out;
00064 std::vector<Frag> frags;
00065 float error;
00066 bool visited;
00067 };
00068
00069 std::vector<Node> nodes;
00070
00071 public:
00072
00078 class Update {
00079 public:
00080 std::vector<Cell *> erased;
00081 std::vector<Cell *> created;
00082 };
00083
00085 void Load(std::vector<Update> &updates) {
00086
00087 assert(updates[0].erased.size() == 0);
00088
00089
00090 std::map<Cell *, unsigned int> cell_node;
00091 nodes.resize(updates.size());
00092
00093
00094 unsigned int current_node = 0;
00095 std::vector<Update>::iterator u;
00096 for(u = updates.begin(); u != updates.end(); u++) {
00097
00098 Node &node = nodes[current_node];
00099 node.error = 0;
00100
00101
00102 for(unsigned int i = 0; i < (*u).created.size(); i++) {
00103 Cell *cell = (*u).created[i];
00104 if(cell->Error() > node.error)
00105 node.error = cell->Error();
00106
00107 cell_node[cell] = current_node;
00108 }
00109
00110
00111
00112 std::map<unsigned int, std::vector<Cell *> > node_erased;
00113
00114 for(unsigned int i = 0; i < (*u).erased.size(); i++) {
00115 Cell *cell = (*u).erased[i];
00116 assert(cell_node.count(cell));
00117 node_erased[cell_node[cell]].push_back(cell);
00118 }
00119
00120
00121 std::map<unsigned int, std::vector<Cell *> >::iterator e;
00122 for(e = node_erased.begin(); e != node_erased.end(); e++) {
00123
00124 Frag fr;
00125 float max_err = -1;
00126
00127
00128 std::vector<Cell *> &cells = (*e).second;
00129 std::vector<Cell *>::iterator k;
00130 for(k = cells.begin(); k != cells.end(); k++) {
00131 Cell *cell = (*k);
00132 fr.push_back(cell);
00133 if(cell->Error() > max_err)
00134 max_err = cell->Error();
00135 }
00136
00137
00138 unsigned int floor_node = (*e).first;
00139 Node &oldnode = nodes[floor_node];
00140 oldnode.frags.push_back(fr);
00141 if(node.error < max_err)
00142 node.error = max_err;
00143
00144
00145 node.in.push_back(&oldnode);
00146 oldnode.out.push_back(&node);
00147 }
00148 current_node++;
00149 }
00150 }
00151 void Clear() {
00152 nodes.clear();
00153 }
00154
00156 template <class CONT> void Extract(CONT &selected, float error) {
00157 std::vector<Node>::iterator n;
00158 for(n = nodes.begin(); n != nodes.end(); n++)
00159 (*n).visited = false;
00160
00161 std::queue<Node *> qnodo;
00162 qnodo.push(&nodes[0]);
00163 nodes[0].visited = true;
00164
00165 for( ; !qnodo.empty(); qnodo.pop()) {
00166 Node &node = *qnodo.front();
00167
00168 std::vector<Frag>::iterator fragment;
00169 std::vector<Node *>::iterator on;
00170 for(on = node.out.begin(), fragment = node.frags.begin(); on != node.out.end(); ++on, ++fragment) {
00171 if((*on)->visited) continue;
00172
00173 if(error < (*on)->error) {
00174 qnodo.push(*on);
00175 (*on)->visited = 1;
00176 } else {
00177 vector<Cell *>::iterator cell;
00178 for(cell=(*fragment).begin(); cell != (*fragment).end(); ++cell)
00179 selected.push_back(*cell);
00180 }
00181 }
00182 }
00183 }
00184
00185
00186 template <class CONT, class POLICY> void Extract(CONT &selected, POLICY &policy) {
00187 std::vector<Node>::iterator n;
00188 for(n = nodes.begin(); n != nodes.end(); n++)
00189 (*n).visited = false;
00190
00191 std::queue<Node *> qnodo;
00192 qnodo.push(&nodes[0]);
00193 nodes[0].visited = true;
00194
00195 for( ; !qnodo.empty(); qnodo.pop()) {
00196 Node &node = *qnodo.front();
00197
00198 std::vector<Frag>::iterator i;
00199 std::vector<Node *>::iterator on;
00200 for(i = node.frags.begin(), on = node.out.begin(); i != node.frags.end(); i++, on++) {
00201 if((*on)->visited) continue;
00202 Frag &frag = (*i);
00203 std::vector<Cell *>::iterator cell;
00204 for(cell = frag.begin(); cell != frag.end(); cell++) {
00205 if(policy.Expand(*cell))
00206 visit(*on, qnodo);
00207 }
00208 }
00209 }
00210 Extract(selected);
00211 }
00212
00213
00214
00215
00216
00217
00218
00220 template <class CONT> void Extract(CONT &selected) {
00221 selected.clear();
00222 std::vector<Node>::iterator i;
00223 for(i = nodes.begin(); i != nodes.end(); i++) {
00224 Node &node = *i;
00225 if(!node.visited)
00226 continue;
00227
00228 std::vector<Node *>::iterator n;
00229 std::vector<Frag>::iterator f;
00230 for(n = node.out.begin(), f = node.frags.begin(); n != node.out.end(); n++, f++) {
00231 if(!(*n)->visited || (*n)->error == 0) {
00232 vector<Cell *>::iterator c;
00233 Frag &frag = (*f);
00234 for(c = frag.begin(); c != frag.end(); c++)
00235 selected.insert(selected.end(), *c);
00236 }
00237 }
00238 }
00239 }
00240
00242 void Visit(Node *node, std::queue<Node *> &qnode) {
00243 std::vector<Node *>::iterator n;
00244 for(n = node->in.begin(); n != node->in.end(); n++)
00245 if(!(*n)->visited)
00246 visit(*n, qnode);
00247
00248 node->visited = true;
00249 qnode.push(node);
00250 }
00251
00252
00253 };
00254
00255 template <class C> class FrustumPolicy {
00256 public:
00257 typedef C Cell;
00258
00259 Frustumf frustum;
00261 float error;
00262
00263 bool Expand(Cell *cell) {
00264 if(cell->Error() == 0) return false;
00265 float dist = Distance(*cell, frustum.ViewPoint());
00266
00267
00268 if(dist < 0) return true;
00269 dist = pow(dist, 1.2);
00270 float res = cell->Error() / (frustum.Resolution()*dist);
00271 return res;
00272 }
00273 };
00274
00276 template <class C> class DiracPolicy {
00277 public:
00278 typedef C Cell;
00279
00280 Point3f focus;
00282 float error;
00283
00284 DiracPolicy(Point3f &f = Point3f(0, 0, 0), float e = 0): focus(f), error(e) {}
00285
00286 bool Expand(Cell *cell) {
00287 if(cell->Error() == 0) return false;
00288 float dist = Distance(*cell, focus);
00289 if(dist > 0) return true;
00290 return false;
00291 }
00292 };
00293
00294 }
00295
00296 #endif