Geant4 Cross Reference

Cross-Referencing   Geant4
Geant4/externals/g4tools/include/tools/glutess/geom

Version: [ ReleaseNotes ] [ 1.0 ] [ 1.1 ] [ 2.0 ] [ 3.0 ] [ 3.1 ] [ 3.2 ] [ 4.0 ] [ 4.0.p1 ] [ 4.0.p2 ] [ 4.1 ] [ 4.1.p1 ] [ 5.0 ] [ 5.0.p1 ] [ 5.1 ] [ 5.1.p1 ] [ 5.2 ] [ 5.2.p1 ] [ 5.2.p2 ] [ 6.0 ] [ 6.0.p1 ] [ 6.1 ] [ 6.2 ] [ 6.2.p1 ] [ 6.2.p2 ] [ 7.0 ] [ 7.0.p1 ] [ 7.1 ] [ 7.1.p1 ] [ 8.0 ] [ 8.0.p1 ] [ 8.1 ] [ 8.1.p1 ] [ 8.1.p2 ] [ 8.2 ] [ 8.2.p1 ] [ 8.3 ] [ 8.3.p1 ] [ 8.3.p2 ] [ 9.0 ] [ 9.0.p1 ] [ 9.0.p2 ] [ 9.1 ] [ 9.1.p1 ] [ 9.1.p2 ] [ 9.1.p3 ] [ 9.2 ] [ 9.2.p1 ] [ 9.2.p2 ] [ 9.2.p3 ] [ 9.2.p4 ] [ 9.3 ] [ 9.3.p1 ] [ 9.3.p2 ] [ 9.4 ] [ 9.4.p1 ] [ 9.4.p2 ] [ 9.4.p3 ] [ 9.4.p4 ] [ 9.5 ] [ 9.5.p1 ] [ 9.5.p2 ] [ 9.6 ] [ 9.6.p1 ] [ 9.6.p2 ] [ 9.6.p3 ] [ 9.6.p4 ] [ 10.0 ] [ 10.0.p1 ] [ 10.0.p2 ] [ 10.0.p3 ] [ 10.0.p4 ] [ 10.1 ] [ 10.1.p1 ] [ 10.1.p2 ] [ 10.1.p3 ] [ 10.2 ] [ 10.2.p1 ] [ 10.2.p2 ] [ 10.2.p3 ] [ 10.3 ] [ 10.3.p1 ] [ 10.3.p2 ] [ 10.3.p3 ] [ 10.4 ] [ 10.4.p1 ] [ 10.4.p2 ] [ 10.4.p3 ] [ 10.5 ] [ 10.5.p1 ] [ 10.6 ] [ 10.6.p1 ] [ 10.6.p2 ] [ 10.6.p3 ] [ 10.7 ] [ 10.7.p1 ] [ 10.7.p2 ] [ 10.7.p3 ] [ 10.7.p4 ] [ 11.0 ] [ 11.0.p1 ] [ 11.0.p2 ] [ 11.0.p3, ] [ 11.0.p4 ] [ 11.1 ] [ 11.1.1 ] [ 11.1.2 ] [ 11.1.3 ] [ 11.2 ] [ 11.2.1 ] [ 11.2.2 ] [ 11.3.0 ]

  1 // see license file for original license.
  2 
  3 #ifndef tools_glutess_geom
  4 #define tools_glutess_geom
  5 
  6 #include "mesh"
  7 
  8 #define VertEq(u,v) ((u)->s == (v)->s && (u)->t == (v)->t)
  9 #define VertLeq(u,v)  (((u)->s < (v)->s) || ((u)->s == (v)->s && (u)->t <= (v)->t))
 10 
 11 #define EdgeEval(u,v,w) __gl_edgeEval(u,v,w)
 12 #define EdgeSign(u,v,w) __gl_edgeSign(u,v,w)
 13 
 14 /* Versions of VertLeq, EdgeSign, EdgeEval with s and t transposed. */
 15 
 16 #define TransLeq(u,v) (((u)->t < (v)->t) || \
 17                          ((u)->t == (v)->t && (u)->s <= (v)->s))
 18 #define TransEval(u,v,w)  __gl_transEval(u,v,w)
 19 #define TransSign(u,v,w)  __gl_transSign(u,v,w)
 20 
 21 
 22 #define EdgeGoesLeft(e)   VertLeq( (e)->Dst, (e)->Org )
 23 #define EdgeGoesRight(e)  VertLeq( (e)->Org, (e)->Dst )
 24 
 25 #define VertL1dist(u,v) (GLU_ABS(u->s - v->s) + GLU_ABS(u->t - v->t))
 26 
 27 #define VertCCW(u,v,w)  __gl_vertCCW(u,v,w)
 28 
 29 ////////////////////////////////////////////////////////
 30 /// inlined C code : ///////////////////////////////////
 31 ////////////////////////////////////////////////////////
 32 
 33 inline int __gl_vertLeq( GLUvertex *u, GLUvertex *v )
 34 {
 35   /* Returns TOOLS_GLU_TRUE if u is lexicographically <= v. */
 36 
 37   return VertLeq( u, v );
 38 }
 39 
 40 inline GLUdouble __gl_edgeEval( GLUvertex *u, GLUvertex *v, GLUvertex *w )
 41 {
 42   /* Given three vertices u,v,w such that VertLeq(u,v) && VertLeq(v,w),
 43    * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
 44    * Returns v->t - (uw)(v->s), ie. the signed distance from uw to v.
 45    * If uw is vertical (and thus passes thru v), the result is zero.
 46    *
 47    * The calculation is extremely accurate and stable, even when v
 48    * is very close to u or w.  In particular if we set v->t = 0 and
 49    * let r be the negated result (this evaluates (uw)(v->s)), then
 50    * r is guaranteed to satisfy MIN(u->t,w->t) <= r <= MAX(u->t,w->t).
 51    */
 52   GLUdouble gapL, gapR;
 53 
 54   assert( VertLeq( u, v ) && VertLeq( v, w ));
 55   
 56   gapL = v->s - u->s;
 57   gapR = w->s - v->s;
 58 
 59   if( gapL + gapR > 0 ) {
 60     if( gapL < gapR ) {
 61       return (v->t - u->t) + (u->t - w->t) * (gapL / (gapL + gapR));
 62     } else {
 63       return (v->t - w->t) + (w->t - u->t) * (gapR / (gapL + gapR));
 64     }
 65   }
 66   /* vertical line */
 67   return 0;
 68 }
 69 
 70 inline GLUdouble __gl_edgeSign( GLUvertex *u, GLUvertex *v, GLUvertex *w )
 71 {
 72   /* Returns a number whose sign matches EdgeEval(u,v,w) but which
 73    * is cheaper to evaluate.  Returns > 0, == 0 , or < 0
 74    * as v is above, on, or below the edge uw.
 75    */
 76   GLUdouble gapL, gapR;
 77 
 78   /*
 79 #define VertLeq(u,v)  (((u)->s < (v)->s) ||     \
 80                          ((u)->s == (v)->s && (u)->t <= (v)->t))
 81   */
 82   assert( VertLeq( u, v ) && VertLeq( v, w ));
 83   
 84   gapL = v->s - u->s;
 85   gapR = w->s - v->s;
 86 
 87   if( gapL + gapR > 0 ) {
 88     return (v->t - w->t) * gapL + (v->t - u->t) * gapR;
 89   }
 90   /* vertical line */
 91   return 0;
 92 }
 93 
 94 
 95 /***********************************************************************
 96  * Define versions of EdgeSign, EdgeEval with s and t transposed.
 97  */
 98 
 99 inline GLUdouble __gl_transEval( GLUvertex *u, GLUvertex *v, GLUvertex *w )
100 {
101   /* Given three vertices u,v,w such that TransLeq(u,v) && TransLeq(v,w),
102    * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
103    * Returns v->s - (uw)(v->t), ie. the signed distance from uw to v.
104    * If uw is vertical (and thus passes thru v), the result is zero.
105    *
106    * The calculation is extremely accurate and stable, even when v
107    * is very close to u or w.  In particular if we set v->s = 0 and
108    * let r be the negated result (this evaluates (uw)(v->t)), then
109    * r is guaranteed to satisfy MIN(u->s,w->s) <= r <= MAX(u->s,w->s).
110    */
111   GLUdouble gapL, gapR;
112 
113   assert( TransLeq( u, v ) && TransLeq( v, w ));
114   
115   gapL = v->t - u->t;
116   gapR = w->t - v->t;
117 
118   if( gapL + gapR > 0 ) {
119     if( gapL < gapR ) {
120       return (v->s - u->s) + (u->s - w->s) * (gapL / (gapL + gapR));
121     } else {
122       return (v->s - w->s) + (w->s - u->s) * (gapR / (gapL + gapR));
123     }
124   }
125   /* vertical line */
126   return 0;
127 }
128 
129 inline GLUdouble __gl_transSign( GLUvertex *u, GLUvertex *v, GLUvertex *w )
130 {
131   /* Returns a number whose sign matches TransEval(u,v,w) but which
132    * is cheaper to evaluate.  Returns > 0, == 0 , or < 0
133    * as v is above, on, or below the edge uw.
134    */
135   GLUdouble gapL, gapR;
136 
137   assert( TransLeq( u, v ) && TransLeq( v, w ));
138   
139   gapL = v->t - u->t;
140   gapR = w->t - v->t;
141 
142   if( gapL + gapR > 0 ) {
143     return (v->s - w->s) * gapL + (v->s - u->s) * gapR;
144   }
145   /* vertical line */
146   return 0;
147 }
148 
149 
150 inline int __gl_vertCCW( GLUvertex *u, GLUvertex *v, GLUvertex *w )
151 {
152   /* For almost-degenerate situations, the results are not reliable.
153    * Unless the floating-point arithmetic can be performed without
154    * rounding errors, *any* implementation will give incorrect results
155    * on some degenerate inputs, so the client must have some way to
156    * handle this situation.
157    */
158   return (u->s*(v->t - w->t) + v->s*(w->t - u->t) + w->s*(u->t - v->t)) >= 0;
159 }
160 
161 /* Given parameters a,x,b,y returns the value (b*x+a*y)/(a+b),
162  * or (x+y)/2 if a==b==0.  It requires that a,b >= 0, and enforces
163  * this in the rare case that one argument is slightly negative.
164  * The implementation is extremely stable numerically.
165  * In particular it guarantees that the result r satisfies
166  * MIN(x,y) <= r <= MAX(x,y), and the results are very accurate
167  * even when a and b differ greatly in magnitude.
168  */
169 #define Interpolate(a,x,b,y)      \
170   (a = (a < 0) ? 0 : a, b = (b < 0) ? 0 : b,    \
171   ((a <= b) ? ((b == 0) ? ((x+y) / 2)     \
172                         : (x + (y-x) * (a/(a+b))))  \
173             : (y + (x-y) * (b/(a+b)))))
174 
175 //#define Swap(a,b) if (1) { GLUvertex *t = a; a = b; b = t; } else
176 #define Swap(a,b) do { GLUvertex *t = a; a = b; b = t; } while(false)
177 
178 inline void __gl_edgeIntersect( GLUvertex *o1, GLUvertex *d1,
179        GLUvertex *o2, GLUvertex *d2,
180        GLUvertex *v )
181 /* Given edges (o1,d1) and (o2,d2), compute their point of intersection.
182  * The computed point is guaranteed to lie in the intersection of the
183  * bounding rectangles defined by each edge.
184  */
185 {
186   GLUdouble z1, z2;
187 
188   /* This is certainly not the most efficient way to find the intersection
189    * of two line segments, but it is very numerically stable.
190    *
191    * Strategy: find the two middle vertices in the VertLeq ordering,
192    * and interpolate the intersection s-value from these.  Then repeat
193    * using the TransLeq ordering to find the intersection t-value.
194    */
195 
196   if( ! VertLeq( o1, d1 )) { Swap( o1, d1 ); }
197   if( ! VertLeq( o2, d2 )) { Swap( o2, d2 ); }
198   if( ! VertLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); }
199 
200   if( ! VertLeq( o2, d1 )) {
201     /* Technically, no intersection -- do our best */
202     v->s = (o2->s + d1->s) / 2;
203   } else if( VertLeq( d1, d2 )) {
204     /* Interpolate between o2 and d1 */
205     z1 = EdgeEval( o1, o2, d1 );
206     z2 = EdgeEval( o2, d1, d2 );
207     if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
208     v->s = Interpolate( z1, o2->s, z2, d1->s );
209   } else {
210     /* Interpolate between o2 and d2 */
211     z1 = EdgeSign( o1, o2, d1 );
212     z2 = -EdgeSign( o1, d2, d1 );
213     if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
214     v->s = Interpolate( z1, o2->s, z2, d2->s );
215   }
216 
217   /* Now repeat the process for t */
218 
219   if( ! TransLeq( o1, d1 )) { Swap( o1, d1 ); }
220   if( ! TransLeq( o2, d2 )) { Swap( o2, d2 ); }
221   if( ! TransLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); }
222 
223   if( ! TransLeq( o2, d1 )) {
224     /* Technically, no intersection -- do our best */
225     v->t = (o2->t + d1->t) / 2;
226   } else if( TransLeq( d1, d2 )) {
227     /* Interpolate between o2 and d1 */
228     z1 = TransEval( o1, o2, d1 );
229     z2 = TransEval( o2, d1, d2 );
230     if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
231     v->t = Interpolate( z1, o2->t, z2, d1->t );
232   } else {
233     /* Interpolate between o2 and d2 */
234     z1 = TransSign( o1, o2, d1 );
235     z2 = -TransSign( o1, d2, d1 );
236     if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
237     v->t = Interpolate( z1, o2->t, z2, d2->t );
238   }
239 }
240 
241 #endif