Initial revision
[blender.git] / intern / bsp / intern / BSP_Triangulate.cpp
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 #include <stdio.h>
33
34 #include <stdlib.h>
35 #include "MT_Plane3.h"
36 #include "BSP_Triangulate.h"
37 #include "MT_assert.h"
38
39 static const MT_Scalar EPSILON = MT_Scalar(1e-10);
40
41 using namespace std;
42
43 BSP_Triangulate::
44 BSP_Triangulate(
45 ):
46         m_xi(0),
47         m_yi(1)
48 {
49 }
50
51 BSP_Triangulate::
52 ~BSP_Triangulate(
53 ){
54 }
55
56
57         MT_Scalar 
58 BSP_Triangulate::
59 Area(
60         const vector<BSP_MVertex> &verts,
61         const BSP_VertexList &contour
62 ){
63
64   int n = contour.size();
65
66   MT_Scalar A(0.0);
67
68   for(int p=n-1,q=0; q<n; p=q++)
69   {
70     A+= verts[contour[p]].m_pos[m_xi]*verts[contour[q]].m_pos[m_yi] - 
71                 verts[contour[q]].m_pos[m_xi]*verts[contour[p]].m_pos[m_yi];
72   }
73   return A*MT_Scalar(0.5);
74 }
75
76 /*
77  InsideTriangle decides if a point P is Inside of the triangle
78  defined by A, B, C.
79  Or within an epsilon of it.
80 */
81
82         bool 
83 BSP_Triangulate::
84 InsideTriangle(
85         MT_Scalar Ax, MT_Scalar Ay,
86     MT_Scalar Bx, MT_Scalar By,
87     MT_Scalar Cx, MT_Scalar Cy,
88     MT_Scalar Px, MT_Scalar Py
89 ){
90   MT_Scalar ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
91   MT_Scalar cCROSSap, bCROSScp, aCROSSbp;
92
93   ax = Cx - Bx;  ay = Cy - By;
94   bx = Ax - Cx;  by = Ay - Cy;
95   cx = Bx - Ax;  cy = By - Ay;
96   apx= Px - Ax;  apy= Py - Ay;
97   bpx= Px - Bx;  bpy= Py - By;
98   cpx= Px - Cx;  cpy= Py - Cy;
99
100   aCROSSbp = ax*bpy - ay*bpx;
101   cCROSSap = cx*apy - cy*apx;
102   bCROSScp = bx*cpy - by*cpx;
103
104   return ((aCROSSbp >= -EPSILON) && (bCROSScp >= -EPSILON) && (cCROSSap >= -EPSILON));
105 };
106
107         bool 
108 BSP_Triangulate::
109 Snip(
110         const vector<BSP_MVertex> &verts,
111         const BSP_VertexList &contour,
112         int u,int v,
113         int w,int n,
114         int *V
115 ){
116   int p;
117   MT_Scalar Ax, Ay, Bx, By, Cx, Cy, Px, Py;
118
119   Ax = verts[contour[V[u]]].m_pos[m_xi];
120   Ay = verts[contour[V[u]]].m_pos[m_yi];
121
122   Bx = verts[contour[V[v]]].m_pos[m_xi];
123   By = verts[contour[V[v]]].m_pos[m_yi];
124
125   Cx = verts[contour[V[w]]].m_pos[m_xi];
126   Cy = verts[contour[V[w]]].m_pos[m_yi];
127
128   // Snip is passes if the area of the candidate triangle is
129   // greater  than 2*epsilon
130   // And if none of the remaining vertices are inside the polygon
131   // or within an epsilon of the boundary,
132
133   if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false;
134
135   for (p=0;p<n;p++)
136   {
137     if( (p == u) || (p == v) || (p == w) ) continue;
138     Px = verts[contour[V[p]]].m_pos[m_xi];
139     Py = verts[contour[V[p]]].m_pos[m_yi];
140     if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
141   }
142
143   return true;
144 }
145
146         bool 
147 BSP_Triangulate::
148 Process(
149         const vector<BSP_MVertex> &verts,
150         const BSP_VertexList &contour,
151         const MT_Plane3 &normal,
152         std::vector<int> &result
153 ){
154
155         // Choose major axis of normal and assign 
156         // 'projection' indices m_xi,m_yi;
157
158         int maj_axis = normal.Normal().closestAxis();
159
160         if (maj_axis == 0) {
161                 m_xi = 1; m_yi = 2;
162         } else 
163         if (maj_axis == 1) {
164                 m_xi = 0; m_yi = 2;
165         } else {
166                 m_xi = 0; m_yi = 1;
167         }
168
169   /* initialize list of Vertices in polygon */
170
171   int n = contour.size();
172   if ( n < 3 ) return false;
173
174   /* we want a counter-clockwise polygon in V */
175   /* to true but we also nead to preserve the winding order
176          of polygons going into the routine. We keep track of what
177          we did with a little bool */
178   bool is_flipped = false;
179
180   if ( 0.0f < Area(verts,contour) ) {
181     for (int v=0; v<n; v++) m_V.push_back(v);
182   } else {
183     for(int v=0; v<n; v++) m_V.push_back((n-1)-v);
184         is_flipped = true;
185   }
186
187   int nv = n;
188
189   /*  remove nv-2 Vertices, creating 1 triangle every time */
190   int count = 2*nv;   /* error detection */
191
192   for(int m=0, v=nv-1; nv>2; )
193   {
194     /* if we loop, it is probably a non-simple polygon */
195     if (0 >= (count--))
196     {
197 #if 0
198           int deb = 0;
199           for (deb= 0; deb < contour.size(); deb++) {
200                 cout << verts[contour[deb]].m_pos << "\n";
201           }
202           cout.flush(); 
203 #endif
204       //** Triangulate: ERROR - probable bad polygon!
205           m_V.clear();
206       return false;
207     }
208
209     /* three consecutive vertices in current polygon, <u,v,w> */
210     int u = v  ; if (nv <= u) u = 0;     /* previous */
211     v = u+1; if (nv <= v) v = 0;     /* new v    */
212     int w = v+1; if (nv <= w) w = 0;     /* next     */
213
214         /* Try and snip this triangle off from the 
215            current polygon.*/
216
217     if ( Snip(verts,contour,u,v,w,nv,m_V.begin()) )
218     {
219       int a,b,c,s,t;
220
221       /* true names of the vertices */
222       a = m_V[u]; b = m_V[v]; c = m_V[w];
223
224       /* output Triangle indices*/
225           if (is_flipped) {
226                   result.push_back( c );
227                   result.push_back( b );
228                   result.push_back( a );
229           } else {
230                   result.push_back( a );
231                   result.push_back( b );
232                   result.push_back( c );
233           }
234
235       m++;
236
237       /* remove v from remaining polygon */
238       for(s=v,t=v+1;t<nv;s++,t++) m_V[s] = m_V[t]; nv--;
239
240       /* resest error detection counter */
241       count = 2*nv;
242     }
243   }
244
245   m_V.clear();
246   return true;
247 }
248
249