bee8e9711a9fd5272612b852266143db076e5783
[blender.git] / intern / bsp / intern / BSP_Triangulate.h
1 /**
2  * $Id$
3  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30  */
31
32 #ifndef TRIANGULATE_H
33
34
35 #define TRIANGULATE_H
36
37 /*****************************************************************/
38 /** Static class to triangulate any contour/polygon efficiently **/
39 /** You should replace Vector2d with whatever your own Vector   **/
40 /** class might be.  Does not support polygons with holes.      **/
41 /** Uses STL vectors to represent a dynamic array of vertices.  **/
42 /** This code snippet was submitted to FlipCode.com by          **/
43 /** John W. Ratcliff (jratcliff@verant.com) on July 22, 2000    **/
44 /** I did not write the original code/algorithm for this        **/
45 /** this triangulator, in fact, I can't even remember where I   **/
46 /** found it in the first place.  However, I did rework it into **/
47 /** the following black-box static class so you can make easy   **/
48 /** use of it in your own code.  Simply replace Vector2d with   **/
49 /** whatever your own Vector implementation might be.           **/
50 /*****************************************************************/
51
52
53 #include <vector>  // Include STL vector class.
54 #include "MT_Point3.h"
55 #include "BSP_MeshPrimitives.h"
56
57 class MT_Plane3;
58
59 class BSP_Triangulate
60 {
61 public:
62
63         BSP_Triangulate(
64         );
65
66         // triangulate a contour/polygon, places results in STL vector
67         // as series of triangles. IT uses the major axis of the normal
68         // to turn it into a 2d problem.
69
70         // Should chaange this to accept a point array and a list of 
71         // indices into that point array. Result should be indices of those
72         // indices.
73         //
74         // MT_Point3 global_array
75         // vector<BSP_VertexInd> polygon
76         // result is vector<int> into polygon.
77
78                 bool
79         Process(
80                 const std::vector<BSP_MVertex> &verts,
81                 const BSP_VertexList &contour,
82                 const MT_Plane3 &normal,
83                 std::vector<int> &result
84         );
85         
86         // compute area of a contour/polygon
87                 MT_Scalar 
88         Area(
89                 const std::vector<BSP_MVertex> &verts,
90                 const BSP_VertexList &contour
91         );
92
93         // decide if point Px/Py is inside triangle defined by
94         // (Ax,Ay) (Bx,By) (Cx,Cy)
95
96                 bool 
97         InsideTriangle(
98                 MT_Scalar Ax, MT_Scalar Ay,
99                 MT_Scalar Bx, MT_Scalar By,
100                 MT_Scalar Cx, MT_Scalar Cy,
101                 MT_Scalar Px, MT_Scalar Py
102         );
103
104         ~BSP_Triangulate(
105         );
106
107 private:
108
109                 bool 
110         Snip(
111                 const std::vector<BSP_MVertex> &verts,
112                 const BSP_VertexList &contour,
113                 int u,
114                 int v,
115                 int w,
116                 int n,
117                 int *V
118         );
119
120         int m_xi;
121         int m_yi;
122
123         // Temporary storage
124
125         std::vector<int> m_V;
126
127 };
128
129
130 #endif
131
132