1 /*************************************************************************************
2 * Copyright (C) 2012 by Percy Camilo T. Aucahuasi <percy.camilo.ta@gmail.com> *
3 * *
4 * This program is free software; you can redistribute it and/or *
5 * modify it under the terms of the GNU General Public License *
6 * as published by the Free Software Foundation; either version 2 *
7 * of the License, or (at your option) any later version. *
8 * *
9 * This program is distributed in the hope that it will be useful, *
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
12 * GNU General Public License for more details. *
13 * *
14 * You should have received a copy of the GNU General Public License *
15 * along with this program; if not, write to the Free Software *
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
17 *************************************************************************************/
18
19 #include "marchingsquares.h"
20 #include <QDebug>
21 #include <QPolygon>
22 #include <QVector2D>
23
evaluar_cubo(const Square & cubo)24 sMarching_Square MarchingSquares::evaluar_cubo(const Square& cubo)
25 {
26 sMarching_Square res;
27 res.centro = cubo.center();
28 res.medio_lado = cubo.halfEdge();
29
30 double x = res.centro.x();
31 double y = res.centro.y();
32 double hedge = res.medio_lado;
33
34 res.vertices[0] = evalScalarField(x-hedge, y-hedge);
35 res.vertices[1] = evalScalarField(x-hedge, y+hedge);
36 res.vertices[2] = evalScalarField(x+hedge, y-hedge);
37 res.vertices[3] = evalScalarField(x+hedge, y+hedge);
38
39
40 // -----
41 // |1|3|
42 // -----
43 // |0|2|
44 // -----
45
46 res.tipo = 0;
47
48 if (res.vertices[1]>0)
49 res.tipo += 8;
50
51 if (res.vertices[3]>0)
52 res.tipo += 4;
53
54 if (res.vertices[2]>0)
55 res.tipo += 2;
56
57 if (res.vertices[0]>0)
58 res.tipo += 1;
59
60 return res;
61 }
62
breadth_rec(int cubos_lado)63 QList<Square> MarchingSquares::breadth_rec(int cubos_lado) {
64 Square cubo;
65 sMarching_Square m_cubo;
66 bool salir = false;
67 QList<Square> cubos;
68 cubo.setHalfEdge(largo_mundo/(2*cubos_lado));
69
70 double x = 0;
71 double y = 0;
72
73 static const double iteration_square_val = 0.5;
74
75 for(double i=mundo.minX; i<=mundo.maxX; i+=iteration_square_val)
76 {
77 x = (2*i+1)*cubo.halfEdge();
78
79 for(double j=mundo.minY; j<=mundo.maxY; j+=iteration_square_val)
80 {
81 y = (2*j+1)*cubo.halfEdge();
82 cubo.setCenter(x,y);
83 m_cubo = evaluar_cubo(cubo);
84 if(m_cubo.tipo != 0 && m_cubo.tipo != 15) {
85 //Esta dentro del cubo. Detener busqueda
86 salir = true;
87 cubos.append(cubo);
88 }
89 }
90 }
91
92 if(!salir && 2*cubo.halfEdge() > min_grid)
93 cubos.append(breadth_rec(cubos_lado*2));
94
95 return cubos;
96 }
97
depth_rec(Quadtree * arbol,QNode * nodo)98 QList<sMarching_Square> MarchingSquares::depth_rec(Quadtree *arbol, QNode *nodo) {
99 QList<sMarching_Square> cubos;
100 sMarching_Square m_cubo;
101
102 m_cubo = evaluar_cubo(nodo->cubo);
103
104 if(m_cubo.tipo != 0 && m_cubo.tipo != 15) {
105 if(m_cubo.medio_lado*2 > min_grid) {
106 arbol->bajarNivel(nodo);
107 for(unsigned int i=0; i<4; i++) {
108 cubos.append(depth_rec(arbol,nodo->nodos[i]));
109 }
110 } else {
111 cubos.append(m_cubo);
112 }
113 }
114 return cubos;
115 }
116
MarchingSquares()117 MarchingSquares::MarchingSquares(/*double min_grid, double arista_mundo, sLimitesEspacio2D limites*/
118
119 ) {
120 }
121
~MarchingSquares()122 MarchingSquares::~MarchingSquares() {
123 }
124
ejecutar()125 QList<sMarching_Square> MarchingSquares::ejecutar() {
126 QList<sMarching_Square> cubos;
127 QList<Square> encontrados;
128 Square iterador;
129 Quadtree *arbol;
130
131 encontrados = breadth_rec(largo_mundo);
132 if(encontrados.isEmpty()) {
133 return cubos;
134 }
135
136 foreach(iterador, encontrados) {
137 arbol = new Quadtree(iterador);
138 cubos.append(depth_rec(arbol, arbol->get_raiz()));
139 delete arbol;
140 }
141
142 return cubos;
143 }
144
_addTri(const QPointF & a,const QPointF & b)145 void MarchingSquares::_addTri(const QPointF& a, const QPointF& b)
146 {
147 QPair<QPointF,QPointF> _f = qMakePair(a,b);
148 _faces_.append(_f);
149
150 }
151
calcular_cortes(const sMarching_Square & cubo)152 QList<sArista2D> MarchingSquares::calcular_cortes(const sMarching_Square &cubo) {
153 QList<sArista2D> aristas;
154 sArista2D temp;
155 // -----
156 // |1|3|
157 // -----
158 // |0|2|
159 // -----
160
161 //0-1
162 if(signo_opuesto(cubo.vertices[0],cubo.vertices[1])) {
163 //al primero luego sumale
164 temp.corte = QPointF(cubo.centro.x()-cubo.medio_lado,
165 cubo.centro.y()-cubo.medio_lado+2*cubo.medio_lado*lineal(cubo.vertices[0],cubo.vertices[1]));
166 temp.vertices[0] = 0;
167 temp.vertices[1] = 1;
168 aristas.append(temp);
169 }
170
171 //1-3
172 if(signo_opuesto(cubo.vertices[1],cubo.vertices[3])) {
173 temp.corte = QPointF(cubo.centro.x()-cubo.medio_lado+2*cubo.medio_lado*lineal(cubo.vertices[1],cubo.vertices[3]),
174 cubo.centro.y()+cubo.medio_lado);
175 temp.vertices[0] = 1;
176 temp.vertices[1] = 3;
177 aristas.append(temp);
178 }
179
180 //2-3
181 if(signo_opuesto(cubo.vertices[2],cubo.vertices[3])) {
182 temp.corte = QPointF(cubo.centro.x()+cubo.medio_lado,
183 cubo.centro.y()-cubo.medio_lado+2*cubo.medio_lado*lineal(cubo.vertices[2],cubo.vertices[3]));
184 temp.vertices[0] = 2;
185 temp.vertices[1] = 3;
186 aristas.append(temp);
187 }
188
189 // -----
190 // |1|3|
191 // -----
192 // |0|2|
193 // -----
194
195 //0-2
196 if(signo_opuesto(cubo.vertices[0],cubo.vertices[2])) {
197 temp.corte = QPointF(cubo.centro.x()-cubo.medio_lado+2*cubo.medio_lado*lineal(cubo.vertices[0],cubo.vertices[2]),
198 cubo.centro.y()-cubo.medio_lado);
199 temp.vertices[0] = 0;
200 temp.vertices[1] = 2;
201 aristas.append(temp);
202 }
203
204 return aristas;
205 }
206
signo_opuesto(double a,double b)207 bool MarchingSquares::signo_opuesto(double a, double b) {
208 return ((a > 0 && b <= 0) || (a <= 0 && b > 0));
209 }
210
lineal(double vert_1,double vert_2)211 double MarchingSquares::lineal(double vert_1, double vert_2) {
212 return qAbs(vert_1/(vert_1 - vert_2));
213 }
214
agregar_triangulos(QList<QPointF> & lista_triangulos)215 void MarchingSquares::agregar_triangulos(QList<QPointF> &lista_triangulos) {
216
217 for(int i=0; i<lista_triangulos.count(); i+=2) {
218
219 if (lista_triangulos.size()-2 < i)
220 continue;
221
222 _addTri(lista_triangulos.at(i),lista_triangulos.at(i+1));
223
224 }
225 }
226
identificar_tipo(const sMarching_Square & cubo)227 void MarchingSquares::identificar_tipo(const sMarching_Square &cubo) {
228
229 QList<sArista2D> aristas;
230 QList<unsigned int> vertices;
231
232 aristas = calcular_cortes(cubo);
233
234 unsigned short int type = cubo.tipo;
235
236 switch (type)
237 {
238 case 1:
239 case 2:
240 case 3:
241 case 4:
242 case 6:
243 case 7:
244 case 8:
245 case 9:
246 case 11:
247 case 12:
248 case 13:
249 case 14:
250 {
251 tipo01(aristas);
252
253 break;
254 }
255 case 5:
256 case 10:
257 {
258 tipo05(aristas, cubo);
259
260 break;
261 }
262 }
263 }
264
tipo01(QList<sArista2D> aristas)265 void MarchingSquares::tipo01(QList<sArista2D> aristas)
266 {
267
268 if (aristas.size()<2) return;
269
270 QList<QPointF> triangulos;
271
272 triangulos << aristas[0].corte << aristas[1].corte;
273
274 agregar_triangulos(triangulos);
275 }
276
tipo05(QList<sArista2D> aristas,const sMarching_Square & cubo)277 void MarchingSquares::tipo05(QList<sArista2D> aristas,const sMarching_Square &cubo)
278 {
279 if (aristas.isEmpty()) return;
280
281 QList<QPointF> triangulos;
282
283 // -----
284 // |1|3|
285 // -----
286 // |0|2|
287 // -----
288
289
290 if (cubo.tipo == 5)
291 triangulos << aristas[0].corte << aristas[2].corte;
292 else if (cubo.tipo == 10)
293 triangulos << aristas[1].corte << aristas[3].corte;
294
295 agregar_triangulos(triangulos);
296 }
buildGeometry()297 void MarchingSquares::buildGeometry()
298 {
299 _faces_.clear();
300
301 QList<sMarching_Square> cubos;
302 sMarching_Square cubo;
303
304 cubos = ejecutar();
305
306 foreach(cubo,cubos) {
307 identificar_tipo(cubo);
308 }
309
310 }
setWorld(double minx,double maxx,double miny,double maxy)311 void MarchingSquares::setWorld(double minx, double maxx, double miny, double maxy)
312 {
313 sLimitesEspacio2D _esp;
314
315 _esp.minX = minx;
316 _esp.maxX = maxx;
317 _esp.minY = miny;
318 _esp.maxY = maxy;
319
320 largo_mundo = 1;
321
322 min_grid = qMin(fabs(maxx-minx), fabs(maxy-miny))/256;
323
324 if (min_grid>0.05 && min_grid < 1)
325 min_grid = 0.05;
326
327 mundo = _esp;
328 }
329