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 #ifndef MARCHINGSQUARES_H
20 #define MARCHINGSQUARES_H
21 
22 #include "quadtree.h"
23 
24 #include <QList>
25 #include <QPair>
26 #include <QVector>
27 #include <qmath.h>
28 #include <QLineF>
29 
30 struct sLimitesEspacio2D {
31     double minX;
32     double maxX;
33     double minY;
34     double maxY;
35 };
36 
37 struct sMarching_Square {
38     QPointF centro;
39     double medio_lado;
40     unsigned short int tipo;
41     double vertices[4];
42 };
43 
44 struct sArista2D {
45     QPointF corte;
46     unsigned int vertices[2];
47 };
48 
49 //TODO very bad implementation ... we need to use interval arithmetic plus root finding
50 //to know if a 0 belongs to f(square)
51 
52 class MarchingSquares
53 {
54 public:
55     virtual double evalScalarField(double x, double y) = 0;
56 
57     void setWorld(double minx, double maxx, double miny, double maxy);
58 
59 public:
60 private:
61     double largo_mundo;
62     double min_grid;
63     sLimitesEspacio2D mundo;
64     //Evaluar un cubo
65     sMarching_Square evaluar_cubo(const Square& cubo);
66 
67     //Busqueda recursiva (breadth search)
68     QList<Square> breadth_rec(int cubos_lado);
69 
70     //Busqueda recursiva (depth search)
71     QList<sMarching_Square> depth_rec(Quadtree *arbol, QNode *nodo);
72 
73 public:
74     MarchingSquares(/*double min_grid, double arista_mundo, sLimitesEspacio2D limites*/);
75 
76     virtual ~MarchingSquares();
77 
78     QList<sMarching_Square> ejecutar();
79 
80     friend class ImplicitSurf;
81 public:
82     void buildGeometry();
83 
84     QVector< QPair< QPointF, QPointF > > _faces_;
85 
86     void _addTri(const QPointF &a, const QPointF &b);
87 
88 private:
89     QList<sArista2D> calcular_cortes(const sMarching_Square &cubo);
90     bool signo_opuesto(double a, double b);
91     double lineal(double vert_1, double vert_2);
92     void agregar_triangulos(QList<QPointF> &lista_triangulos);
93     void identificar_tipo(const sMarching_Square &cubo);
94     void tipo01(QList<sArista2D> aristas);
95     void tipo05(QList<sArista2D> aristas, const sMarching_Square &cubo);
96 
97 private:
98     double fixed_x;
99     double fixed_y;
100 
fy(double y)101     double fy(double y) { return evalScalarField(fixed_x, y); }
fx(double x)102     double fx(double x) { return evalScalarField(x, fixed_y); }
103 };
104 
105 #endif
106