#include "mesh.h"

Include dependency graph for geom.h:

This graph shows which files directly or indirectly include 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))

◆ EdgeEval

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

◆ EdgeGoesLeft

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

◆ EdgeGoesRight

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

◆ EdgeSign

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

◆ TransEval

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

◆ TransLeq

#define TransLeq	(	u,
		v
	)

Value:

(((u)->t < (v)->t) || \

((u)->t == (v)->t && (u)->s <= (v)->s))

◆ TransSign

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

◆ VertCCW

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

◆ VertEq

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

◆ VertL1dist

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

◆ VertLeq

#define VertLeq	(	u,
		v
	)

Value:

(((u)->s < (v)->s) || \

((u)->s == (v)->s && (u)->t <= (v)->t))

Function Documentation

◆ __gl_edgeEval()

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

{
  /* Given three vertices u,v,w such that VertLeq(u,v) && VertLeq(v,w),
   * evaluates the t-coord of the edge uw at the s-coord of the vertex v.
   * Returns v->t - (uw)(v->s), ie. the signed distance from uw to v.
   * If uw is vertical (and thus passes thru v), the result is zero.
   *
   * The calculation is extremely accurate and stable, even when v
   * is very close to u or w.  In particular if we set v->t = 0 and
   * let r be the negated result (this evaluates (uw)(v->s)), then
   * r is guaranteed to satisfy MIN(u->t,w->t) <= r <= MAX(u->t,w->t).
   */
  GLdouble gapL, gapR;
 
  assert( VertLeq( u, v ) && VertLeq( v, w ));
  
  gapL = v->s - u->s;
  gapR = w->s - v->s;
 
  if( gapL + gapR > 0 ) {
    if( gapL < gapR ) {
      return (v->t - u->t) + (u->t - w->t) * (gapL / (gapL + gapR));
    } else {
      return (v->t - w->t) + (w->t - u->t) * (gapR / (gapL + gapR));
    }
  }
  /* vertical line */
  return 0;
}

References GLUvertex::s, GLUvertex::t, and VertLeq.

◆ __gl_edgeIntersect()

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

{
  GLdouble z1, z2;
 
  /* This is certainly not the most efficient way to find the intersection
   * of two line segments, but it is very numerically stable.
   *
   * Strategy: find the two middle vertices in the VertLeq ordering,
   * and interpolate the intersection s-value from these.  Then repeat
   * using the TransLeq ordering to find the intersection t-value.
   */
 
  if( ! VertLeq( o1, d1 )) { Swap( o1, d1 ); }
  if( ! VertLeq( o2, d2 )) { Swap( o2, d2 ); }
  if( ! VertLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); }
 
  if( ! VertLeq( o2, d1 )) {
    /* Technically, no intersection -- do our best */
    v->s = (o2->s + d1->s) / 2;
  } else if( VertLeq( d1, d2 )) {
    /* Interpolate between o2 and d1 */
    z1 = EdgeEval( o1, o2, d1 );
    z2 = EdgeEval( o2, d1, d2 );
    if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
    v->s = Interpolate( z1, o2->s, z2, d1->s );
  } else {
    /* Interpolate between o2 and d2 */
    z1 = EdgeSign( o1, o2, d1 );
    z2 = -EdgeSign( o1, d2, d1 );
    if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
    v->s = Interpolate( z1, o2->s, z2, d2->s );
  }
 
  /* Now repeat the process for t */
 
  if( ! TransLeq( o1, d1 )) { Swap( o1, d1 ); }
  if( ! TransLeq( o2, d2 )) { Swap( o2, d2 ); }
  if( ! TransLeq( o1, o2 )) { Swap( o1, o2 ); Swap( d1, d2 ); }
 
  if( ! TransLeq( o2, d1 )) {
    /* Technically, no intersection -- do our best */
    v->t = (o2->t + d1->t) / 2;
  } else if( TransLeq( d1, d2 )) {
    /* Interpolate between o2 and d1 */
    z1 = TransEval( o1, o2, d1 );
    z2 = TransEval( o2, d1, d2 );
    if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
    v->t = Interpolate( z1, o2->t, z2, d1->t );
  } else {
    /* Interpolate between o2 and d2 */
    z1 = TransSign( o1, o2, d1 );
    z2 = -TransSign( o1, d2, d1 );
    if( z1+z2 < 0 ) { z1 = -z1; z2 = -z2; }
    v->t = Interpolate( z1, o2->t, z2, d2->t );
  }
}

References EdgeEval, EdgeSign, Interpolate, GLUvertex::s, Swap, GLUvertex::t, TransEval, TransLeq, TransSign, and VertLeq.

Referenced by CheckForIntersect().

Here is the caller graph for this function:

◆ __gl_edgeSign()

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

{
  /* Returns a number whose sign matches EdgeEval(u,v,w) but which
   * is cheaper to evaluate.  Returns > 0, == 0 , or < 0
   * as v is above, on, or below the edge uw.
   */
  GLdouble gapL, gapR;
 
  assert( VertLeq( u, v ) && VertLeq( v, w ));
  
  gapL = v->s - u->s;
  gapR = w->s - v->s;
 
  if( gapL + gapR > 0 ) {
    return (v->t - w->t) * gapL + (v->t - u->t) * gapR;
  }
  /* vertical line */
  return 0;
}