1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
|
/****************************************************************************
* VCGLib o o *
* Visual and Computer Graphics Library o o *
* _ O _ *
* Copyright(C) 2004-2016 \/)\/ *
* Visual Computing Lab /\/| *
* ISTI - Italian National Research Council | *
* \ *
* All rights reserved. *
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License (http://www.gnu.org/licenses/gpl.txt) *
* for more details. *
* *
****************************************************************************/
/****************************************************************************
History
$Log: not supported by cvs2svn $
****************************************************************************/
#ifndef VCG_MT_H
#define VCG_MT_H
#include <vector>
#include <queue>
#include <map>
#include <vcg/space/sphere3.h>
#include <vcg/space/point3.h>
#include <wrap/gui/frustum.h>
namespace vcg {
/** \addtogroup mt */
/*@{*/
/**
The templated class for representing a mt structure.
The class is templated over the Cell class which MUST implement this functions:
float Error();
float Distance(Cell &c, Point3f &p);
see mt_file.h for an example.
*/
template <class C> class MT {
public:
typedef C Cell;
private:
class Frag:public std::vector<Cell *> {};
struct Node {
std::vector<Node *> in;
std::vector<Node *> out;
std::vector<Frag> frags;
float error;
bool visited;
};
std::vector<Node> nodes;
public:
/** Update class for defining the history.
Notice how the Update class holds pointers.
You are responsible of holding the Cell structure and rebuild the structure
if the pointers change.
*/
class Update {
public:
std::vector<Cell *> erased;
std::vector<Cell *> created;
};
///build mt strucure from a sequence of updates.
void Load(std::vector<Update> &updates) {
//The last update erases everything.
assert(updates[0].erased.size() == 0);
//maps cell -> node containing it
std::map<Cell *, unsigned int> cell_node;
nodes.resize(updates.size());
//building fragments and nodes.
unsigned int current_node = 0;
std::vector<Update>::iterator u;
for(u = updates.begin(); u != updates.end(); u++) {
Node &node = nodes[current_node];
node.error = 0;
//created cells belong to this node, we look also for max error.
for(unsigned int i = 0; i < (*u).created.size(); i++) {
Cell *cell = (*u).created[i];
if(cell->Error() > node.error)
node.error = cell->Error();
cell_node[cell] = current_node;
}
//Every erased cell already belonged to a node.
//we record for each node its cells.
std::map<unsigned int, std::vector<Cell *> > node_erased;
for(unsigned int i = 0; i < (*u).erased.size(); i++) {
Cell *cell = (*u).erased[i];
assert(cell_node.count(cell));
node_erased[cell_node[cell]].push_back(cell);
}
//for every node with erased cells we build a frag and put the corresponding cells in it.
std::map<unsigned int, std::vector<Cell *> >::iterator e;
for(e = node_erased.begin(); e != node_erased.end(); e++) {
//Build a new Frag.
Frag fr;
float max_err = -1;
//Fill it with erased cells.
std::vector<Cell *> &cells = (*e).second;
std::vector<Cell *>::iterator k;
for(k = cells.begin(); k != cells.end(); k++) {
Cell *cell = (*k);
fr.push_back(cell);
if(cell->Error() > max_err)
max_err = cell->Error();
}
//Add the new Frag to the node.
unsigned int floor_node = (*e).first;
Node &oldnode = nodes[floor_node];
oldnode.frags.push_back(fr);
if(node.error < max_err)
node.error = max_err;
//Update in and out of the nodes.
node.in.push_back(&oldnode);
oldnode.out.push_back(&node);
}
current_node++;
}
}
void Clear() {
nodes.clear();
}
///error based extraction
template <class CONT> void Extract(CONT &selected, float error) {
std::vector<Node>::iterator n;
for(n = nodes.begin(); n != nodes.end(); n++)
(*n).visited = false;
std::queue<Node *> qnodo;
qnodo.push(&nodes[0]);
nodes[0].visited = true;
for( ; !qnodo.empty(); qnodo.pop()) {
Node &node = *qnodo.front();
std::vector<Frag>::iterator fragment;
std::vector<Node *>::iterator on;
for(on = node.out.begin(), fragment = node.frags.begin(); on != node.out.end(); ++on, ++fragment) {
if((*on)->visited) continue;
if(error < (*on)->error) { //need to expand this node.
qnodo.push(*on);
(*on)->visited = 1;
} else {
vector<Cell *>::iterator cell;
for(cell=(*fragment).begin(); cell != (*fragment).end(); ++cell)
selected.push_back(*cell);
}
}
}
}
//custom extraction
template <class CONT, class POLICY> void Extract(CONT &selected, POLICY &policy) {
std::vector<Node>::iterator n;
for(n = nodes.begin(); n != nodes.end(); n++)
(*n).visited = false;
std::queue<Node *> qnodo;
qnodo.push(&nodes[0]);
nodes[0].visited = true;
for( ; !qnodo.empty(); qnodo.pop()) {
Node &node = *qnodo.front();
std::vector<Frag>::iterator i;
std::vector<Node *>::iterator on;
for(i = node.frags.begin(), on = node.out.begin(); i != node.frags.end(); i++, on++) {
if((*on)->visited) continue;
Frag &frag = (*i);
std::vector<Cell *>::iterator cell;
for(cell = frag.begin(); cell != frag.end(); cell++) {
if(policy.Expand(*cell))
visit(*on, qnodo);
}
}
}
Extract(selected);
}
//extract using a user class which must provides:
//bool refineCell(Cell *cell, Frustum &frustum);
//void addCell(Cell *cell);
//void removeCell(Cell *cell);
//template <class CONT> void extract(std::vector<Cell *> &selected, Frustum &frustum, T &error);
///extract using the visited flag in nodes to a STL container of Cell *
template <class CONT> void Extract(CONT &selected) {
selected.clear();
std::vector<Node>::iterator i;
for(i = nodes.begin(); i != nodes.end(); i++) {
Node &node = *i;
if(!node.visited)
continue;
std::vector<Node *>::iterator n;
std::vector<Frag>::iterator f;
for(n = node.out.begin(), f = node.frags.begin(); n != node.out.end(); n++, f++) {
if(!(*n)->visited || (*n)->error == 0) {
vector<Cell *>::iterator c;
Frag &frag = (*f);
for(c = frag.begin(); c != frag.end(); c++)
selected.insert(selected.end(), *c);
}
}
}
}
///add a node to the queue recursively mantaining coherence.
void Visit(Node *node, std::queue<Node *> &qnode) {
std::vector<Node *>::iterator n;
for(n = node->in.begin(); n != node->in.end(); n++)
if(!(*n)->visited)
visit(*n, qnode);
node->visited = true;
qnode.push(node);
}
};
template <class C> class FrustumPolicy {
public:
typedef C Cell;
Frustumf frustum;
///target error in screen space (pixels)
float error;
bool Expand(Cell *cell) {
if(cell->Error() == 0) return false;
float dist = Distance(*cell, frustum.ViewPoint());
/*Point3f line = frustum.viewPoint() - cell->sphere.center;
float dist = line.Norm() - cell->sphere.radius; */
if(dist < 0) return true;
dist = pow(dist, 1.2);
float res = cell->Error() / (frustum.Resolution()*dist);
return res;
}
};
///really simple example policy
template <class C> class DiracPolicy {
public:
typedef C Cell;
Point3f focus;
///max error in object space at distance 0
float error;
DiracPolicy(Point3f &f = Point3f(0, 0, 0), float e = 0): focus(f), error(e) {}
bool Expand(Cell *cell) {
if(cell->Error() == 0) return false;
float dist = Distance(*cell, focus);
if(dist > 0) return true;
return false;
}
};
}//namespace vcg
#endif
|