1 | /************************************************************** ggt-head beg |
---|
2 | * |
---|
3 | * GGT: Generic Graphics Toolkit |
---|
4 | * |
---|
5 | * Original Authors: |
---|
6 | * Allen Bierbaum |
---|
7 | * |
---|
8 | * ----------------------------------------------------------------- |
---|
9 | * File: Tri.h,v |
---|
10 | * Date modified: 2004/11/12 01:28:44 |
---|
11 | * Version: 1.13 |
---|
12 | * ----------------------------------------------------------------- |
---|
13 | * |
---|
14 | *********************************************************** ggt-head end */ |
---|
15 | /*************************************************************** ggt-cpr beg |
---|
16 | * |
---|
17 | * GGT: The Generic Graphics Toolkit |
---|
18 | * Copyright (C) 2001,2002 Allen Bierbaum |
---|
19 | * |
---|
20 | * This library is free software; you can redistribute it and/or |
---|
21 | * modify it under the terms of the GNU Lesser General Public |
---|
22 | * License as published by the Free Software Foundation; either |
---|
23 | * version 2.1 of the License, or (at your option) any later version. |
---|
24 | * |
---|
25 | * This library is distributed in the hope that it will be useful, |
---|
26 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
27 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
28 | * Lesser General Public License for more details. |
---|
29 | * |
---|
30 | * You should have received a copy of the GNU Lesser General Public |
---|
31 | * License along with this library; if not, write to the Free Software |
---|
32 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
---|
33 | * |
---|
34 | ************************************************************ ggt-cpr end */ |
---|
35 | #ifndef _GMTL_TRI_H_ |
---|
36 | #define _GMTL_TRI_H_ |
---|
37 | |
---|
38 | #include <gmtl/Point.h> |
---|
39 | #include <gmtl/Vec.h> |
---|
40 | #include <gmtl/VecOps.h> |
---|
41 | |
---|
42 | namespace gmtl |
---|
43 | { |
---|
44 | /** |
---|
45 | * This class defines a triangle as a set of 3 points order in CCW fashion. |
---|
46 | * |
---|
47 | * Triangle points are tri(s,t) = b+s*e0+t*e1 where 0 <= s <= 1, |
---|
48 | * 0 <= t <= 1, and 0 <= s+t <= 1. |
---|
49 | * @ingroup Types |
---|
50 | */ |
---|
51 | template< class DATA_TYPE > |
---|
52 | class Tri |
---|
53 | { |
---|
54 | public: |
---|
55 | /** |
---|
56 | * Constructs a new triangle with all vertices at the origin. |
---|
57 | */ |
---|
58 | Tri() {} |
---|
59 | |
---|
60 | /** |
---|
61 | * Constructs a new triangle with the given points. The points must be passed |
---|
62 | * in in CCW order. |
---|
63 | * |
---|
64 | * @param p1 vertex0 |
---|
65 | * @param p2 vertex1 |
---|
66 | * @param p3 vertex2 |
---|
67 | * |
---|
68 | * @pre p1, p2, p3 must be in CCW order |
---|
69 | */ |
---|
70 | Tri( const Point<DATA_TYPE, 3>& p1, const Point<DATA_TYPE, 3>& p2, |
---|
71 | const Point<DATA_TYPE, 3>& p3) |
---|
72 | { |
---|
73 | mVerts[0] = p1; |
---|
74 | mVerts[1] = p2; |
---|
75 | mVerts[2] = p3; |
---|
76 | } |
---|
77 | |
---|
78 | /** |
---|
79 | * Constructs a duplicate of the given triangle. |
---|
80 | * |
---|
81 | * @param tri the triangle to copy |
---|
82 | */ |
---|
83 | Tri( const Tri<DATA_TYPE>& tri ) |
---|
84 | { |
---|
85 | mVerts[0] = tri[0]; |
---|
86 | mVerts[1] = tri[1]; |
---|
87 | mVerts[2] = tri[2]; |
---|
88 | } |
---|
89 | |
---|
90 | /** |
---|
91 | * Gets the nth vertex in the triangle. |
---|
92 | * |
---|
93 | * @param idx the index to the vertex in the triangle |
---|
94 | * @pre 0 <= idx <= 2 |
---|
95 | * |
---|
96 | * @return the nth vertex as a point |
---|
97 | */ |
---|
98 | //@{ |
---|
99 | Point<DATA_TYPE, 3>& operator[]( const unsigned idx ) |
---|
100 | { |
---|
101 | gmtlASSERT( idx <= 2 ); |
---|
102 | return mVerts[idx]; |
---|
103 | } |
---|
104 | const Point<DATA_TYPE, 3>& operator[]( const unsigned idx ) const |
---|
105 | { |
---|
106 | gmtlASSERT( idx <= 2 ); |
---|
107 | return mVerts[idx]; |
---|
108 | } |
---|
109 | //@} |
---|
110 | |
---|
111 | /** |
---|
112 | * Gets the nth edge of the triangle where edge0 corresponds to the vector |
---|
113 | * from vertex 0 to 1, edge1 corresponds to the vector from vertex 1 to 2 and |
---|
114 | * edge2 corresponsds to the vector from vertex 2 to vertex 0. |
---|
115 | * |
---|
116 | * @param idx the ordered edge index |
---|
117 | * @pre 0 <= idx <= 2 |
---|
118 | * |
---|
119 | * @return a vector from vertex idx to vertex (idx+1)mod size |
---|
120 | */ |
---|
121 | Vec<DATA_TYPE, 3> edge( int idx ) const |
---|
122 | { |
---|
123 | gmtlASSERT( (0 <= idx) && (idx <= 2) ); |
---|
124 | int idx2 = ( idx == 2 ) ? 0 : idx + 1; |
---|
125 | return (mVerts[idx2] - mVerts[idx]); |
---|
126 | } |
---|
127 | |
---|
128 | /** get edge vec from two verts |
---|
129 | * |
---|
130 | * @param idx,idy the ordered vertex indicies |
---|
131 | * @pre 0 <= id <= 2 |
---|
132 | * |
---|
133 | * @return a vector from vertex idx to vertex idy |
---|
134 | */ |
---|
135 | Vec<DATA_TYPE, 3> edge( int idx, int idy ) const |
---|
136 | { |
---|
137 | gmtlASSERT( (0 <= idx) && (idx <= 2) ); |
---|
138 | gmtlASSERT( (0 <= idy) && (idy <= 2) ); |
---|
139 | return (mVerts[idy] - mVerts[idx]); |
---|
140 | } |
---|
141 | |
---|
142 | |
---|
143 | |
---|
144 | /** |
---|
145 | * Set the triangle with the given points. The points must be passed |
---|
146 | * in in CCW order. |
---|
147 | * |
---|
148 | * @param p1 vertex0 |
---|
149 | * @param p2 vertex1 |
---|
150 | * @param p3 vertex2 |
---|
151 | * |
---|
152 | * @pre p1, p2, p3 must be in CCW order |
---|
153 | */ |
---|
154 | void set( const Point<DATA_TYPE, 3>& p1, const Point<DATA_TYPE, 3>& p2, |
---|
155 | const Point<DATA_TYPE, 3>& p3 ) |
---|
156 | { |
---|
157 | mVerts[0] = p1; |
---|
158 | mVerts[1] = p2; |
---|
159 | mVerts[2] = p3; |
---|
160 | } |
---|
161 | |
---|
162 | private: |
---|
163 | /** |
---|
164 | * The vertices of the triangle. |
---|
165 | */ |
---|
166 | Point<DATA_TYPE, 3> mVerts[3]; |
---|
167 | }; |
---|
168 | |
---|
169 | // convenience typedefs |
---|
170 | typedef Tri<float> Trif; |
---|
171 | typedef Tri<double> Trid; |
---|
172 | typedef Tri<int> Trii; |
---|
173 | } |
---|
174 | |
---|
175 | /* |
---|
176 | // Finds the point on the seg nearest to pt. |
---|
177 | // on the perimeter of the triangle. |
---|
178 | // Returns the nearest point in nearPt |
---|
179 | inline |
---|
180 | void sgTri::findNearestEdgePt(const sgVec3& pt, sgVec3& nearPt) const |
---|
181 | { |
---|
182 | // find all the closest pts on the segs that make the tri |
---|
183 | // return the closest one |
---|
184 | |
---|
185 | sgSeg seg1; seg1.makePts(_v1, _v2); |
---|
186 | sgSeg seg2; seg2.makePts(_v2, _v3); |
---|
187 | sgSeg seg3; seg3.makePts(_v3, _v1); |
---|
188 | |
---|
189 | sgVec3 pt1; seg1.findNearestPt(pt, pt1); |
---|
190 | sgVec3 pt2; seg2.findNearestPt(pt, pt2); |
---|
191 | sgVec3 pt3; seg3.findNearestPt(pt, pt3); |
---|
192 | |
---|
193 | float dist1 = SG_SQUARE(pt1[0]-pt[0]) + SG_SQUARE(pt1[1]-pt[1]) + SG_SQUARE(pt1[2]-pt[2]); |
---|
194 | float dist2 = SG_SQUARE(pt2[0]-pt[0]) + SG_SQUARE(pt2[1]-pt[1]) + SG_SQUARE(pt2[2]-pt[2]); |
---|
195 | float dist3 = SG_SQUARE(pt3[0]-pt[0]) + SG_SQUARE(pt3[1]-pt[1]) + SG_SQUARE(pt3[2]-pt[2]); |
---|
196 | |
---|
197 | if((dist1 < dist2) && (dist1 < dist3)) // dist1 is min |
---|
198 | nearPt = pt1; |
---|
199 | else if(dist2 < dist3) // dist2 is min |
---|
200 | nearPt = pt2; |
---|
201 | else |
---|
202 | nearPt = pt3; // dist3 is min |
---|
203 | } |
---|
204 | |
---|
205 | |
---|
206 | |
---|
207 | // Returns wether the pt is in the triangle |
---|
208 | inline |
---|
209 | int sgTri::ptIn(const sgVec3& pt) const |
---|
210 | { |
---|
211 | // Graphic Gems I: Page 392 |
---|
212 | int i0, i1, i2; // Axis indices |
---|
213 | float u0, u1, u2, v0, v1, v2, alpha, beta; |
---|
214 | i0 = 0; |
---|
215 | |
---|
216 | sgVec3 triNormal = (_v2-_v1).cross((_v3-_v1)); |
---|
217 | //sgPlane triPlane; |
---|
218 | //triPlane.makePts(_v1, _v2, _v3); |
---|
219 | |
---|
220 | // Find max index |
---|
221 | // NOTE: note the fabs. I added because of bug in GG code with negative normals |
---|
222 | for(int index=0;index<3;index++) |
---|
223 | if (fabs(triNormal.vec[index]) > fabs(triNormal.vec[i0])) |
---|
224 | i0 = index; |
---|
225 | |
---|
226 | if(i0 == 0) |
---|
227 | { i1 = 1; i2 = 2; } |
---|
228 | else if (i0 == 1) |
---|
229 | { i1 = 2; i2 = 0; } |
---|
230 | else |
---|
231 | { i1 =0; i2 = 1; } |
---|
232 | |
---|
233 | u0 = pt[i1] - _v1[i1]; |
---|
234 | v0 = pt[i2] - _v1[i2]; |
---|
235 | u1 = _v2[i1] - _v1[i1]; |
---|
236 | u2 = _v3[i1] - _v1[i1]; |
---|
237 | v1 = _v2[i2] - _v1[i2]; |
---|
238 | v2 = _v3[i2] - _v1[i2]; |
---|
239 | if(u1 == 0) |
---|
240 | { |
---|
241 | beta = (u0/u2); |
---|
242 | if((beta >= 0) && (beta<= 1)) |
---|
243 | alpha = (v0 - (beta*v2))/v1; |
---|
244 | } |
---|
245 | else |
---|
246 | { |
---|
247 | beta = ((v0*u1) - (u0*v1))/((v2*u1) - (u2*v1)); |
---|
248 | if((beta >= 0) && (beta<= 1)) |
---|
249 | alpha = (u0 - (beta*u2))/u1; |
---|
250 | } |
---|
251 | |
---|
252 | return ((alpha >= 0) && (beta >= 0) && ((alpha+beta) <= 1)); |
---|
253 | } |
---|
254 | |
---|
255 | |
---|
256 | |
---|
257 | // Finds the point on the seg nearest to pt. |
---|
258 | // Returns the nearest point in nearPt |
---|
259 | void sgTri::findNearestPt(const sgVec3& pt, sgVec3& nearPt) const |
---|
260 | { |
---|
261 | // find nearest pt on plaane. |
---|
262 | // if it is in the tri, return it. |
---|
263 | // Otherwise return the pt closest on the edge of the tri |
---|
264 | |
---|
265 | sgPlane triPlane; |
---|
266 | triPlane.makePts(_v1, _v2, _v3); |
---|
267 | triPlane.findNearestPt(pt, nearPt); |
---|
268 | |
---|
269 | if(!ptIn(nearPt)) |
---|
270 | findNearestEdgePt(pt, nearPt); |
---|
271 | } |
---|
272 | */ |
---|
273 | |
---|
274 | #endif |
---|
275 | |
---|