diff options
Diffstat (limited to 'intern/bsp/intern/BSP_Triangulate.h')
-rwxr-xr-x | intern/bsp/intern/BSP_Triangulate.h | 132 |
1 files changed, 132 insertions, 0 deletions
diff --git a/intern/bsp/intern/BSP_Triangulate.h b/intern/bsp/intern/BSP_Triangulate.h new file mode 100755 index 00000000000..bee8e9711a9 --- /dev/null +++ b/intern/bsp/intern/BSP_Triangulate.h @@ -0,0 +1,132 @@ +/** + * $Id$ + * ***** BEGIN GPL/BL DUAL LICENSE BLOCK ***** + * + * 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. The Blender + * Foundation also sells licenses for use in proprietary software under + * the Blender License. See http://www.blender.org/BL/ for information + * about this. + * + * 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 for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL/BL DUAL LICENSE BLOCK ***** + */ + +#ifndef TRIANGULATE_H + + +#define TRIANGULATE_H + +/*****************************************************************/ +/** Static class to triangulate any contour/polygon efficiently **/ +/** You should replace Vector2d with whatever your own Vector **/ +/** class might be. Does not support polygons with holes. **/ +/** Uses STL vectors to represent a dynamic array of vertices. **/ +/** This code snippet was submitted to FlipCode.com by **/ +/** John W. Ratcliff (jratcliff@verant.com) on July 22, 2000 **/ +/** I did not write the original code/algorithm for this **/ +/** this triangulator, in fact, I can't even remember where I **/ +/** found it in the first place. However, I did rework it into **/ +/** the following black-box static class so you can make easy **/ +/** use of it in your own code. Simply replace Vector2d with **/ +/** whatever your own Vector implementation might be. **/ +/*****************************************************************/ + + +#include <vector> // Include STL vector class. +#include "MT_Point3.h" +#include "BSP_MeshPrimitives.h" + +class MT_Plane3; + +class BSP_Triangulate +{ +public: + + BSP_Triangulate( + ); + + // triangulate a contour/polygon, places results in STL vector + // as series of triangles. IT uses the major axis of the normal + // to turn it into a 2d problem. + + // Should chaange this to accept a point array and a list of + // indices into that point array. Result should be indices of those + // indices. + // + // MT_Point3 global_array + // vector<BSP_VertexInd> polygon + // result is vector<int> into polygon. + + bool + Process( + const std::vector<BSP_MVertex> &verts, + const BSP_VertexList &contour, + const MT_Plane3 &normal, + std::vector<int> &result + ); + + // compute area of a contour/polygon + MT_Scalar + Area( + const std::vector<BSP_MVertex> &verts, + const BSP_VertexList &contour + ); + + // decide if point Px/Py is inside triangle defined by + // (Ax,Ay) (Bx,By) (Cx,Cy) + + bool + InsideTriangle( + MT_Scalar Ax, MT_Scalar Ay, + MT_Scalar Bx, MT_Scalar By, + MT_Scalar Cx, MT_Scalar Cy, + MT_Scalar Px, MT_Scalar Py + ); + + ~BSP_Triangulate( + ); + +private: + + bool + Snip( + const std::vector<BSP_MVertex> &verts, + const BSP_VertexList &contour, + int u, + int v, + int w, + int n, + int *V + ); + + int m_xi; + int m_yi; + + // Temporary storage + + std::vector<int> m_V; + +}; + + +#endif + + |