ReactOS 0.4.15-dev-7889-g76290a6
geom.h File Reference
#include "mesh.h"
Include dependency graph for geom.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define VertEq(u, v)   ((u)->s == (v)->s && (u)->t == (v)->t)
 
#define VertLeq(u, v)
 
#define EdgeEval(u, v, w)   __gl_edgeEval(u,v,w)
 
#define EdgeSign(u, v, w)   __gl_edgeSign(u,v,w)
 
#define TransLeq(u, v)
 
#define TransEval(u, v, w)   __gl_transEval(u,v,w)
 
#define TransSign(u, v, w)   __gl_transSign(u,v,w)
 
#define EdgeGoesLeft(e)   VertLeq( (e)->Dst, (e)->Org )
 
#define EdgeGoesRight(e)   VertLeq( (e)->Org, (e)->Dst )
 
#define ABS(x)   ((x) < 0 ? -(x) : (x))
 
#define VertL1dist(u, v)   (ABS(u->s - v->s) + ABS(u->t - v->t))
 
#define VertCCW(u, v, w)   __gl_vertCCW(u,v,w)
 

Functions

int __gl_vertLeq (GLUvertex *u, GLUvertex *v)
 
GLdouble __gl_edgeEval (GLUvertex *u, GLUvertex *v, GLUvertex *w)
 
GLdouble __gl_edgeSign (GLUvertex *u, GLUvertex *v, GLUvertex *w)
 
GLdouble __gl_transEval (GLUvertex *u, GLUvertex *v, GLUvertex *w)
 
GLdouble __gl_transSign (GLUvertex *u, GLUvertex *v, GLUvertex *w)
 
int __gl_vertCCW (GLUvertex *u, GLUvertex *v, GLUvertex *w)
 
void __gl_edgeIntersect (GLUvertex *o1, GLUvertex *d1, GLUvertex *o2, GLUvertex *d2, GLUvertex *v)
 

Macro Definition Documentation

◆ ABS

#define ABS (   x)    ((x) < 0 ? -(x) : (x))

Definition at line 69 of file geom.h.

◆ EdgeEval

#define EdgeEval (   u,
  v,
  w 
)    __gl_edgeEval(u,v,w)

Definition at line 54 of file geom.h.

◆ EdgeGoesLeft

#define EdgeGoesLeft (   e)    VertLeq( (e)->Dst, (e)->Org )

Definition at line 65 of file geom.h.

◆ EdgeGoesRight

#define EdgeGoesRight (   e)    VertLeq( (e)->Org, (e)->Dst )

Definition at line 66 of file geom.h.

◆ EdgeSign

#define EdgeSign (   u,
  v,
  w 
)    __gl_edgeSign(u,v,w)

Definition at line 55 of file geom.h.

◆ TransEval

#define TransEval (   u,
  v,
  w 
)    __gl_transEval(u,v,w)

Definition at line 61 of file geom.h.

◆ TransLeq

#define TransLeq (   u,
  v 
)
Value:
(((u)->t < (v)->t) || \
((u)->t == (v)->t && (u)->s <= (v)->s))
const GLdouble * v
Definition: gl.h:2040
GLdouble s
Definition: gl.h:2039
GLdouble GLdouble t
Definition: gl.h:2047
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240

Definition at line 59 of file geom.h.

◆ TransSign

#define TransSign (   u,
  v,
  w 
)    __gl_transSign(u,v,w)

Definition at line 62 of file geom.h.

◆ VertCCW

#define VertCCW (   u,
  v,
  w 
)    __gl_vertCCW(u,v,w)

Definition at line 72 of file geom.h.

◆ VertEq

#define VertEq (   u,
  v 
)    ((u)->s == (v)->s && (u)->t == (v)->t)

Definition at line 49 of file geom.h.

◆ VertL1dist

#define VertL1dist (   u,
  v 
)    (ABS(u->s - v->s) + ABS(u->t - v->t))

Definition at line 70 of file geom.h.

◆ VertLeq

#define VertLeq (   u,
  v 
)
Value:
(((u)->s < (v)->s) || \
((u)->s == (v)->s && (u)->t <= (v)->t))

Definition at line 50 of file geom.h.

Function Documentation

◆ __gl_edgeEval()

GLdouble __gl_edgeEval ( GLUvertex u,
GLUvertex v,
GLUvertex w 
)

Definition at line 47 of file geom.c.

48{
49 /* Given three vertices u,v,w such that VertLeq(u,v) && VertLeq(v,w),
50 * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
51 * Returns v->t - (uw)(v->s), ie. the signed distance from uw to v.
52 * If uw is vertical (and thus passes thru v), the result is zero.
53 *
54 * The calculation is extremely accurate and stable, even when v
55 * is very close to u or w. In particular if we set v->t = 0 and
56 * let r be the negated result (this evaluates (uw)(v->s)), then
57 * r is guaranteed to satisfy MIN(u->t,w->t) <= r <= MAX(u->t,w->t).
58 */
59 GLdouble gapL, gapR;
60
61 assert( VertLeq( u, v ) && VertLeq( v, w ));
62
63 gapL = v->s - u->s;
64 gapR = w->s - v->s;
65
66 if( gapL + gapR > 0 ) {
67 if( gapL < gapR ) {
68 return (v->t - u->t) + (u->t - w->t) * (gapL / (gapL + gapR));
69 } else {
70 return (v->t - w->t) + (w->t - u->t) * (gapR / (gapL + gapR));
71 }
72 }
73 /* vertical line */
74 return 0;
75}
#define assert(x)
Definition: debug.h:53
#define VertLeq(u, v)
Definition: geom.h:50
double GLdouble
Definition: gl.h:163
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102

◆ __gl_edgeIntersect()

void __gl_edgeIntersect ( GLUvertex o1,
GLUvertex d1,
GLUvertex o2,
GLUvertex d2,
GLUvertex v 
)

Definition at line 203 of file geom.c.

210{
211 GLdouble z1, z2;
212
213 /* This is certainly not the most efficient way to find the intersection
214 * of two line segments, but it is very numerically stable.
215 *
216 * Strategy: find the two middle vertices in the VertLeq ordering,
217 * and interpolate the intersection s-value from these. Then repeat
218 * using the TransLeq ordering to find the intersection t-value.
219 */
220
221 if( ! VertLeq( o1, d1 )) { Swap( o1, d1 ); }
222 if( ! VertLeq( o2, d2 )) { Swap( o2, d2 ); }
223 if( ! VertLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); }
224
225 if( ! VertLeq( o2, d1 )) {
226 /* Technically, no intersection -- do our best */
227 v->s = (o2->s + d1->s) / 2;
228 } else if( VertLeq( d1, d2 )) {
229 /* Interpolate between o2 and d1 */
230 z1 = EdgeEval( o1, o2, d1 );
231 z2 = EdgeEval( o2, d1, d2 );
232 if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
233 v->s = Interpolate( z1, o2->s, z2, d1->s );
234 } else {
235 /* Interpolate between o2 and d2 */
236 z1 = EdgeSign( o1, o2, d1 );
237 z2 = -EdgeSign( o1, d2, d1 );
238 if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
239 v->s = Interpolate( z1, o2->s, z2, d2->s );
240 }
241
242 /* Now repeat the process for t */
243
244 if( ! TransLeq( o1, d1 )) { Swap( o1, d1 ); }
245 if( ! TransLeq( o2, d2 )) { Swap( o2, d2 ); }
246 if( ! TransLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); }
247
248 if( ! TransLeq( o2, d1 )) {
249 /* Technically, no intersection -- do our best */
250 v->t = (o2->t + d1->t) / 2;
251 } else if( TransLeq( d1, d2 )) {
252 /* Interpolate between o2 and d1 */
253 z1 = TransEval( o1, o2, d1 );
254 z2 = TransEval( o2, d1, d2 );
255 if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
256 v->t = Interpolate( z1, o2->t, z2, d1->t );
257 } else {
258 /* Interpolate between o2 and d2 */
259 z1 = TransSign( o1, o2, d1 );
260 z2 = -TransSign( o1, d2, d1 );
261 if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
262 v->t = Interpolate( z1, o2->t, z2, d2->t );
263 }
264}
#define Interpolate(a, x, b, y)
Definition: geom.c:179
#define Swap(a, b)
Definition: geom.c:201
#define TransEval(u, v, w)
Definition: geom.h:61
#define TransLeq(u, v)
Definition: geom.h:59
#define EdgeSign(u, v, w)
Definition: geom.h:55
#define TransSign(u, v, w)
Definition: geom.h:62
#define EdgeEval(u, v, w)
Definition: geom.h:54
GLdouble t
Definition: mesh.h:122
GLdouble s
Definition: mesh.h:122

Referenced by CheckForIntersect().

◆ __gl_edgeSign()

GLdouble __gl_edgeSign ( GLUvertex u,
GLUvertex v,
GLUvertex w 
)

Definition at line 77 of file geom.c.

78{
79 /* Returns a number whose sign matches EdgeEval(u,v,w) but which
80 * is cheaper to evaluate. Returns > 0, == 0 , or < 0
81 * as v is above, on, or below the edge uw.
82 */
83 GLdouble gapL, gapR;
84
85 assert( VertLeq( u, v ) && VertLeq( v, w ));
86
87 gapL = v->s - u->s;
88 gapR = w->s - v->s;
89
90 if( gapL + gapR > 0 ) {
91 return (v->t - w->t) * gapL + (v->t - u->t) * gapR;
92 }
93 /* vertical line */
94 return 0;
95}

◆ __gl_transEval()

GLdouble __gl_transEval ( GLUvertex u,
GLUvertex v,
GLUvertex w 
)

Definition at line 102 of file geom.c.

103{
104 /* Given three vertices u,v,w such that TransLeq(u,v) && TransLeq(v,w),
105 * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
106 * Returns v->s - (uw)(v->t), ie. the signed distance from uw to v.
107 * If uw is vertical (and thus passes thru v), the result is zero.
108 *
109 * The calculation is extremely accurate and stable, even when v
110 * is very close to u or w. In particular if we set v->s = 0 and
111 * let r be the negated result (this evaluates (uw)(v->t)), then
112 * r is guaranteed to satisfy MIN(u->s,w->s) <= r <= MAX(u->s,w->s).
113 */
114 GLdouble gapL, gapR;
115
116 assert( TransLeq( u, v ) && TransLeq( v, w ));
117
118 gapL = v->t - u->t;
119 gapR = w->t - v->t;
120
121 if( gapL + gapR > 0 ) {
122 if( gapL < gapR ) {
123 return (v->s - u->s) + (u->s - w->s) * (gapL / (gapL + gapR));
124 } else {
125 return (v->s - w->s) + (w->s - u->s) * (gapR / (gapL + gapR));
126 }
127 }
128 /* vertical line */
129 return 0;
130}

◆ __gl_transSign()

GLdouble __gl_transSign ( GLUvertex u,
GLUvertex v,
GLUvertex w 
)

Definition at line 132 of file geom.c.

133{
134 /* Returns a number whose sign matches TransEval(u,v,w) but which
135 * is cheaper to evaluate. Returns > 0, == 0 , or < 0
136 * as v is above, on, or below the edge uw.
137 */
138 GLdouble gapL, gapR;
139
140 assert( TransLeq( u, v ) && TransLeq( v, w ));
141
142 gapL = v->t - u->t;
143 gapR = w->t - v->t;
144
145 if( gapL + gapR > 0 ) {
146 return (v->s - w->s) * gapL + (v->s - u->s) * gapR;
147 }
148 /* vertical line */
149 return 0;
150}

◆ __gl_vertCCW()

int __gl_vertCCW ( GLUvertex u,
GLUvertex v,
GLUvertex w 
)

Definition at line 153 of file geom.c.

154{
155 /* For almost-degenerate situations, the results are not reliable.
156 * Unless the floating-point arithmetic can be performed without
157 * rounding errors, *any* implementation will give incorrect results
158 * on some degenerate inputs, so the client must have some way to
159 * handle this situation.
160 */
161 return (u->s*(v->t - w->t) + v->s*(w->t - u->t) + w->s*(u->t - v->t)) >= 0;
162}

◆ __gl_vertLeq()

int __gl_vertLeq ( GLUvertex u,
GLUvertex v 
)

Definition at line 40 of file geom.c.

41{
42 /* Returns TRUE if u is lexicographically <= v. */
43
44 return VertLeq( u, v );
45}

Referenced by InitPriorityQ().