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