# ! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 5)."
# Contents: 2DClip 2DClip/Makefile 2DClip/box.h 2DClip/line.h AALines
# AALines/00README AALines/AALines.h AALines/AAMain.c
# AALines/LongConst.h AALines/Makefile AALines/utah.h BinRec.c
# CircleRect.c DigitalLine.c FastJitter.c FixedTrig.c HSLtoRGB.c
# Hash3D.c HypotApprox.c MANIFEST MatrixOrtho.c PixelInteger.c
# PolyScan PolyScan/Makefile README RGBTo4Bits.c RayBox.c
# RayPolygon.c Sturm Sturm/Makefile Sturm/solve.h Sturm/util.c
# TransBox.c ViewTrans.c
# Wrapped by craig@weedeater on Wed Dec 12 20:45:12 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test ! -d '2DClip' ; then
echo shar: Creating directory \"'2DClip'\"
mkdir '2DClip'
fi
if test -f '2DClip/Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'2DClip/Makefile'\"
else
echo shar: Extracting \"'2DClip/Makefile'\" \(212 characters\)
sed "s/^X//" >'2DClip/Makefile' <<'END_OF_FILE'
XLIBFILE = ../gemslib.a
X
XCFLAGS = $(GENCFLAGS) -I..
X
XOFILES = clip.o bio.o cross.o
X
X$(LIBFILE): $(OFILES)
X ar rcs $(LIBFILE) $(OFILES)
X
Xclean:
X /bin/rm -f clip.o bio.o cross.o
X
X$(OFILES): line.h ../GraphicsGems.h
END_OF_FILE
if test 212 -ne `wc -c <'2DClip/Makefile'`; then
echo shar: \"'2DClip/Makefile'\" unpacked with wrong size!
fi
# end of '2DClip/Makefile'
fi
if test -f '2DClip/box.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'2DClip/box.h'\"
else
echo shar: Extracting \"'2DClip/box.h'\" \(186 characters\)
sed "s/^X//" >'2DClip/box.h' <<'END_OF_FILE'
X
X/*
X * file box.h
X * a short include file is better then no include file
X */
Xtypedef struct { /* guess what this is */
X long _lowx;
X long _lowy;
X long _highx;
X long _highy;
X} BOX;
X
X
END_OF_FILE
if test 186 -ne `wc -c <'2DClip/box.h'`; then
echo shar: \"'2DClip/box.h'\" unpacked with wrong size!
fi
# end of '2DClip/box.h'
fi
if test -f '2DClip/line.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'2DClip/line.h'\"
else
echo shar: Extracting \"'2DClip/line.h'\" \(1795 characters\)
sed "s/^X//" >'2DClip/line.h' <<'END_OF_FILE'
X
X/*
XTwo-Dimensional Clipping: A Vector Based Approach
Xby Hans Spoelder and Fons Ullings
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X
X/*
X * file line.h
X * contains major definitions for the clipping routines
X *
X */
X#define NFAC 10 /* discrete measure */
X
X#define SCALE (1 << NFAC) /* 1024 points/cm */
X#define TO_INT(X) ((int)((X)*SCALE))
X#define TO_FLT(X) (((float)(X))/SCALE)
X
X#define COINCIDE 1 /* what do the lines do */
X#define PARALLEL 2
X#define CROSS 3
X#define NO_CROSS 4
X
X#define STD 0 /* crossing types */
X#define DELAY 1
X
X#define CLIP_NORMAL 1
X
Xtypedef struct { /* holds a point */
X long _x; /* holds x coordinate */
X long _y; /* holds y coordinate */
X} POINT;
X
Xtypedef struct { /* holds a cross point */
X POINT _p; /* holds the solution */
X short _type; /* more information */
X} CLIST;
X
Xstruct segment { /* holds a segment */
X POINT _from; /* start coordinates */
X POINT _to; /* stop coordinates */
X struct segment *_next;
X struct segment *_prev;
X};
X
X
X#define SEGMENT struct segment
X
Xstruct contour { /* holds a contour */
X short _no; /* contour counter */
X short _status; /* holds information */
X short _cnt; /* number of elements */
X SEGMENT *_s; /* the segments */
X struct contour *_next; /* linked list */
X long _minx; /* coordinates of box */
X long _miny;
X long _maxx;
X long _maxy;
X};
X
X#define CONTOUR struct contour
X
X#define ACTIVE 01 /* polygon attributes */
X#define NORMAL 02
X
X#define SET_ON(p) ((p)->_status |= ACTIVE)
X#define SET_NORMAL(p) ((p)->_status |= NORMAL)
X
X#define SET_OFF(p) ((p)->_status &= ~ACTIVE)
X#define SET_INVERSE(p) ((p)->_status &= ~NORMAL)
X
X#define IS_ON(p) ((p)->_status & ACTIVE)
X#define IS_NORMAL(p) ((p)->_status & NORMAL)
X
Xextern CONTOUR *CL;
X
XCONTOUR *get_contour_ptr();
X
Xextern short C_COUNT;
X
END_OF_FILE
if test 1795 -ne `wc -c <'2DClip/line.h'`; then
echo shar: \"'2DClip/line.h'\" unpacked with wrong size!
fi
# end of '2DClip/line.h'
fi
if test ! -d 'AALines' ; then
echo shar: Creating directory \"'AALines'\"
mkdir 'AALines'
fi
if test -f 'AALines/00README' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'AALines/00README'\"
else
echo shar: Extracting \"'AALines/00README'\" \(1074 characters\)
sed "s/^X//" >'AALines/00README' <<'END_OF_FILE'
XThis group of files is a simple demonstration of an anti-aliased line
Xrenderer from _Grahpics_Gems_. Files in the release are:
X
X 00README -- This information file.
X
X Makefile -- Makefile for creating the demo executable.
X
X AALines.h -- Include file for demo source files.
X
X AALines.c -- Rendering code from _Grahpics_Gems_ pages 690-693.
X
X AATables.c -- Initialization code for frame buffer and lookup tables.
X
X AAMain.c -- Calling routine for the renderer.
X
X utah.h -- Include file for friendly Utah RLE front end.
X
X utah.c -- Source for friendly Utah RLE front end.
X
XAs it is written, the program dumps its frame buffer to a Utah RLE
Xfile. You need to obtain the Utah RLE library from another source;
Xtry the following FTP sites:
X
X cs.utah.edu (128.110.4.21)
X weedeater.math.yale.edu (130.132.23.17)
X freebie.engin.umich.edu (35.2.68.23)
X
XIt should be fairly easy to dump the frame buffer to another type
Xof file, or straight to a display device. See AAMain.c.
X
XHave fun.
X
X -- Kelvin Thompson, 18 August 1990
X kelvin@cs.utexas.edu
END_OF_FILE
if test 1074 -ne `wc -c <'AALines/00README'`; then
echo shar: \"'AALines/00README'\" unpacked with wrong size!
fi
# end of 'AALines/00README'
fi
if test -f 'AALines/AALines.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'AALines/AALines.h'\"
else
echo shar: Extracting \"'AALines/AALines.h'\" \(1371 characters\)
sed "s/^X//" >'AALines/AALines.h' <<'END_OF_FILE'
X/* FILENAME: AALines.h [revised 17 AUG 90]
X
X AUTHOR: Kelvin Thompson
X
X DESCRIPTION: Symbols and globals for the anti-aliased line
X renderer.
X
X #INCLUDED IN:
X AAMain.c -- Calling routine for renderer.
X AATables.c -- Initialization routines for lookup tables.
X AALines.c -- Rendering code.
X*/
X
X/* frame buffer to hold the anti-aliased line */
X#define xpix 60
X#define ypix 60
Xextern char *fbuff;
X
X/* macros to access the frame buffer */
X#define PIXADDR(xx,yy) (fbuff+(yy)*xpix+(xx))
X#define PIXINC(dx,dy) ((dy)*xpix+(dx))
X
X/* fixed-point data types and macros */
Xtypedef int FX;
Xtypedef unsigned int UFX;
X#define FX_FRACBITS 16 /* bits of fraction in FX format */
X#define FX_0 0 /* zero in fixed-point format */
X#define FLOAT_TO_FX(flt) ((FX)((flt)*(1<<FX_FRACBITS)+0.5))
X
X/* some important constants */
X#define PI 3.1415926535897932384626433832795028841971693993751
X#define SQRT_2 1.4142135623730950488016887242096980785696718753769
X
X/* square-root function globals */
Xextern UFX *sqrtfunc;
Xextern int sqrtcells;
Xextern int sqrtshift;
X#define SQRTFUNC(fxval) (sqrtfunc[ (fxval) >> sqrtshift ])
X
X/* AA globals */
Xextern float line_r; /* line radius */
Xextern float pix_r; /* pixel radius */
Xextern FX *coverage;
Xextern int covercells;
Xextern int covershift;
X#define COVERAGE(fxval) (coverage[ (fxval) >> covershift ])
END_OF_FILE
if test 1371 -ne `wc -c <'AALines/AALines.h'`; then
echo shar: \"'AALines/AALines.h'\" unpacked with wrong size!
fi
# end of 'AALines/AALines.h'
fi
if test -f 'AALines/AAMain.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'AALines/AAMain.c'\"
else
echo shar: Extracting \"'AALines/AAMain.c'\" \(1578 characters\)
sed "s/^X//" >'AALines/AAMain.c' <<'END_OF_FILE'
X/* FILENAME: AAMain.c [revised 17 AUG 90]
X
X AUTHOR: Kelvin Thompson
X
X DESCRIPTION: Calling routine for anti-aliased line renderer.
X This routine calls the line renderer to draw a single
X anti-aliased line into a small frame buffer. The
X routine then dumps the frame buffer to a Utah RLE file
X 'anti.rle'.
X
X LINK WITH:
X utah.h -- Definitions for friendly Utah RLE front end.
X AALines.h -- Shared tables, symbols, etc. for renderer.
X AALines.c -- Rendering code.
X AATables.c -- Table initialization.
X*/
X
X#include <stdio.h>
X#include <math.h>
X#include "AALines.h"
X#include "utah.h"
X
X
X
Xmain ( argc, argv )
Xint argc;
Xchar *argv[];
X{
Xint i;
Xchar *scanptr;
Xint x1,y1,x2,y2;
X
X/* initialize frame buffer and look-up tables */
XAnti_Init();
X
X/* set line endpoints */
Xx1 = 2; y1 = 2;
Xx2 = 25; y2 = 55;
X
X/* render anti-aliased line to a frame buffer */
XAnti_Line( x1,y1, x2,y2 );
X
X
X/* The code below dumps the frame buffer to a Utah RLE file.
X** It should be pretty easy to rewrite so that it dumps to
X** any other kind of output file...or straight to a display
X** device. The frame buffer is an array of characters
X** starting at 'fbuff' with size 'xpix' by 'ypix'. */
X
X {
X /* thanks to A.T. Campbell for the friendly front end */
X UTAH_FILE *picout;
X picout = utah_write_init( "anti.rle", xpix, ypix );
X if ( picout == NULL )
X { perror("anti.rle"); exit(1); }
X for ( i=0; i<ypix; i++ )
X {
X scanptr = &fbuff[i*xpix];
X utah_write_rgb( picout, scanptr, scanptr, scanptr );
X }
X utah_write_close(picout);
X }
X}
END_OF_FILE
if test 1578 -ne `wc -c <'AALines/AAMain.c'`; then
echo shar: \"'AALines/AAMain.c'\" unpacked with wrong size!
fi
# end of 'AALines/AAMain.c'
fi
if test -f 'AALines/LongConst.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'AALines/LongConst.h'\"
else
echo shar: Extracting \"'AALines/LongConst.h'\" \(1701 characters\)
sed "s/^X//" >'AALines/LongConst.h' <<'END_OF_FILE'
X/* FILENAME: LongConst.h [revised 18 AUG 90]
X
X AUTHOR: Kelvin Thompson
X
X DESCRIPTION: High-precision constants. If this file is included
X in the same file as GraphicsGems.h, this file must come *after*
X GraphicsGems.h. (It's okay to use this file without GraphicsGems.h.)
X
X The standard _Graphics_Gems_ include file has some constants
X that do not have full double-precision accuracy. This file
X has the constants to a ridiculously high precision. See pages
X 434-435 of _Graphics_Gems_. I got the constants from Mathematica.
X
X Also, this file has a constant and macro for finding the base-two
X logarithm of a number.
X*/
X
X/* prevent multiple inclusion */
X#ifndef __LONGCONST_H__
X#define __LONGCONST_H__
X
X/* first get rid of stuff from GraphicsGems.h */
X#undef PI
X#undef PITIMES2
X#undef PIOVER2
X#undef E
X#undef SQRT2
X#undef SQRT3
X#undef GOLDEN
X#undef DTOR
X#undef RTOD
X
X/* re-define basic constants with high precision */
X#define PI 3.141592653589793238462643383279502884197169399375105820975
X#define E 2.718281828459045235360287471352662497757247093699959574967
X#define SQRT2 1.414213562373095048801688724209698078569671875376948073177
X#define SQRT3 1.732050807568877293527446341505872366942805253810380628056
X#define GOLDEN 1.618033988749894848204586834365638117720309179805762862135
X
X/* re-define derived constants */
X#define PITIMES2 (2.0*PI)
X#define PIOVER2 (0.5*PI)
X#define DTOR (PI/180.0)
X#define RTOD (180.0/PI)
X
X/* macro and constant for base 2 logarithm */
X#define LN2 0.693147180559945309417232121458176568075500134360255254121
X#define LOG2(val) (log(val)*(1.0/LN_2))
X
X#endif /* __LONGCONST_H__ */
END_OF_FILE
if test 1701 -ne `wc -c <'AALines/LongConst.h'`; then
echo shar: \"'AALines/LongConst.h'\" unpacked with wrong size!
fi
# end of 'AALines/LongConst.h'
fi
if test -f 'AALines/Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'AALines/Makefile'\"
else
echo shar: Extracting \"'AALines/Makefile'\" \(462 characters\)
sed "s/^X//" >'AALines/Makefile' <<'END_OF_FILE'
X# FILENAME: Makefile [revised 18 AUG 90]
X#
X# AUTHOR: Kelvin Thompson
X#
X# DESCRIPTION: Makefile for anti-aliased line rendering demo.
X
X# locations of Utah RLE information
XUTAH_RLE_INCLUDE_DIR = /public/graphics/rle/include
XUTAH_RLE_LIB_FILE = /p/lib/librle.a
X
XCFLAGS = -I$(UTAH_RLE_INCLUDE_DIR)
X
XOBJS = AAMain.o AALines.o AATables.o utah.o
X
X%.o : %.c
X $(CC) -c $(CFLAGS) $(CPPFLAGS) $<
X
XAALine : $(OBJS)
X cc $(CFLAGS) -o $@ $(OBJS) $(UTAH_RLE_LIB_FILE) -lm
END_OF_FILE
if test 462 -ne `wc -c <'AALines/Makefile'`; then
echo shar: \"'AALines/Makefile'\" unpacked with wrong size!
fi
# end of 'AALines/Makefile'
fi
if test -f 'AALines/utah.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'AALines/utah.h'\"
else
echo shar: Extracting \"'AALines/utah.h'\" \(877 characters\)
sed "s/^X//" >'AALines/utah.h' <<'END_OF_FILE'
X/*
X file: utah.h
X description: interface to Utah RLE toolkit
X author: A. T. Campbell
X date: October 30, 1989
X*/
X
X#ifndef UTAH_H
X#define UTAH_H
X
X/******************************************************************************/
X
X/* include files */
X#include "svfb_global.h"
X
X/******************************************************************************/
X
X/* type definitions */
Xtypedef struct sv_globals UTAH_FILE;
X
X/******************************************************************************/
X
X/* return values */
Xextern int utah_read_close();
Xextern UTAH_FILE *utah_read_init();
Xextern int utah_read_pixels();
Xextern int utah_read_rgb();
Xextern int utah_write_close();
Xextern UTAH_FILE *utah_write_init();
Xextern int utah_write_pixels();
Xextern int utah_write_rgb();
X
X/******************************************************************************/
X
X#endif UTAH_H
END_OF_FILE
if test 877 -ne `wc -c <'AALines/utah.h'`; then
echo shar: \"'AALines/utah.h'\" unpacked with wrong size!
fi
# end of 'AALines/utah.h'
fi
if test -f 'BinRec.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'BinRec.c'\"
else
echo shar: Extracting \"'BinRec.c'\" \(1171 characters\)
sed "s/^X//" >'BinRec.c' <<'END_OF_FILE'
X/*
X * Recording Animation in Binary Order for Progressive Temporal Refinement
X * by Paul Heckbert
X * from "Graphics Gems", Academic Press, 1990
X */
X
X/*
X * binrec.c: demonstrate binary recording order
X *
X * Paul Heckbert Jan 90
X */
X
X#include <stdio.h>
X
Xmain(ac, av)
Xint ac;
Xchar **av;
X{
X int nframes, i, start_frame, repeat_count;
X if (ac!=2) {
X fprintf(stderr, "Usage: binrec <nframes>\n");
X exit(1);
X }
X nframes = atoi(av[1]);
X
X printf("step startframe repeatcount\n");
X for (i=0; i<nframes; i++) {
X inside_out(nframes, i, &start_frame, &repeat_count);
X printf(" %2d %2d %2d\n", i, start_frame, repeat_count);
X }
X}
X
X/*
X * inside_out: turn a number "inside-out": a generalization of bit-reversal.
X * For n = power of two, this is equivalent to bit-reversal.
X *
X * Turn the number a inside-out, yielding b. If 0<=a<n then 0<=b<n.
X * Also return r = min(n-b, largest power of 2 dividing b)
X */
X
Xinside_out(n, a, b, r)
Xint n, a, *b, *r;
X{
X int k, m;
X
X *r = m = n;
X for (*b=0, k=1; k<n; k<<=1)
X if (a<<1>=m) {
X if (*b==0) *r = k;
X *b += k;
X a -= m+1>>1;
X m >>= 1;
X }
X else m = m+1>>1;
X if (*r>n-*b) *r = n-*b;
X}
END_OF_FILE
if test 1171 -ne `wc -c <'BinRec.c'`; then
echo shar: \"'BinRec.c'\" unpacked with wrong size!
fi
# end of 'BinRec.c'
fi
if test -f 'CircleRect.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'CircleRect.c'\"
else
echo shar: Extracting \"'CircleRect.c'\" \(1513 characters\)
sed "s/^X//" >'CircleRect.c' <<'END_OF_FILE'
X/*
XFast Circle-Rectangle Intersection Checking
Xby Clifford A. Shaffer
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X#include "GraphicsGems.h"
X
Xboolean Check_Intersect(R, C, Rad)
X
X/* Return TRUE iff rectangle R intersects circle with centerpoint C and
X radius Rad. */
X Box2 *R;
X Point2 *C;
X double Rad;
X{
X double Rad2;
X
X Rad2 = Rad * Rad;
X /* Translate coordinates, placing C at the origin. */
X R->max.x -= C->x; R->max.y -= C->y;
X R->min.x -= C->x; R->min.y -= C->y;
X
X if (R->max.x < 0) /* R to left of circle center */
X if (R->max.y < 0) /* R in lower left corner */
X return ((R->max.x * R->max.x + R->max.y * R->max.y) < Rad2);
X else if (R->min.y > 0) /* R in upper left corner */
X return ((R->max.x * R->max.x + R->min.y * R->min.y) < Rad2);
X else /* R due West of circle */
X return(ABS(R->max.x) < Rad);
X else if (R->min.x > 0) /* R to right of circle center */
X if (R->max.y < 0) /* R in lower right corner */
X return ((R->min.x * R->min.x) < Rad2);
X else if (R->min.y > 0) /* R in upper right corner */
X return ((R->min.x * R->min.x + R->min.y + R->min.y) < Rad2);
X else /* R due East of circle */
X return (R->min.x < Rad);
X else /* R on circle vertical centerline */
X if (R->max.y < 0) /* R due South of circle */
X return (ABS(R->max.y) < Rad);
X else if (R->min.y > 0) /* R due North of circle */
X return (R->min.y < Rad);
X else /* R contains circle centerpoint */
X return(TRUE);
X}
END_OF_FILE
if test 1513 -ne `wc -c <'CircleRect.c'`; then
echo shar: \"'CircleRect.c'\" unpacked with wrong size!
fi
# end of 'CircleRect.c'
fi
if test -f 'DigitalLine.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'DigitalLine.c'\"
else
echo shar: Extracting \"'DigitalLine.c'\" \(943 characters\)
sed "s/^X//" >'DigitalLine.c' <<'END_OF_FILE'
X/*
X * Digital Line Drawing
X * by Paul Heckbert
X * from "Graphics Gems", Academic Press, 1990
X */
X
X/*
X * digline: draw digital line from (x1,y1) to (x2,y2),
X * calling a user-supplied procedure at each pixel.
X * Does no clipping. Uses Bresenham's algorithm.
X *
X * Paul Heckbert 3 Sep 85
X */
X
X#include "GraphicsGems.h"
X
Xdigline(x1, y1, x2, y2, dotproc)
Xint x1, y1, x2, y2;
Xvoid (*dotproc)();
X{
X int d, x, y, ax, ay, sx, sy, dx, dy;
X
X dx = x2-x1; ax = ABS(dx)<<1; sx = SGN(dx);
X dy = y2-y1; ay = ABS(dy)<<1; sy = SGN(dy);
X
X x = x1;
X y = y1;
X if (ax>ay) { /* x dominant */
X d = ay-(ax>>1);
X for (;;) {
X (*dotproc)(x, y);
X if (x==x2) return;
X if (d>=0) {
X y += sy;
X d -= ax;
X }
X x += sx;
X d += ay;
X }
X }
X else { /* y dominant */
X d = ax-(ay>>1);
X for (;;) {
X (*dotproc)(x, y);
X if (y==y2) return;
X if (d>=0) {
X x += sx;
X d -= ay;
X }
X y += sy;
X d += ax;
X }
X }
X}
END_OF_FILE
if test 943 -ne `wc -c <'DigitalLine.c'`; then
echo shar: \"'DigitalLine.c'\" unpacked with wrong size!
fi
# end of 'DigitalLine.c'
fi
if test -f 'FastJitter.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'FastJitter.c'\"
else
echo shar: Extracting \"'FastJitter.c'\" \(1720 characters\)
sed "s/^X//" >'FastJitter.c' <<'END_OF_FILE'
X/*
X * Efficient Generation of Sampling Jitter Using Look-up Tables
X * by Joseph M. Cychosz
X * from "Graphics Gems", Academic Press, 1990
X */
X
X/* Jitter.c - Sampling jitter generation routines.
X/*
X/* Description:
X/* Jitter.c contains the routines for generation of sampling
X/* jitter using look-up tables.
X/*
X/* Contents:
X/* Jitter1 Generate random jitter function 1.
X/* Jitter2 Generate random jitter function 2.
X/* JitterInit Initialize look-up tables.
X/* */
X
X#define NRAN 1024 /* Random number table length */
X
Xstatic double URANX[NRAN], /* Random number tables */
X URANY[NRAN];
Xstatic int IRAND[NRAN]; /* Shuffle table */
Xstatic int MASK = NRAN-1; /* Mask for jitter mod function */
Xextern double xranf(); /* Random number generator pro- */
X /* ducing uniform numbers 0 to 1 */
X
X/* Jitter1 - Generate random jitter. */
X
Xvoid Jitter1 (x,y,s,xj,yj)
X int x, y; /* Pixel location */
X int s; /* Sample number for the pixel */
X double *xj, *yj; /* Jitter (x,y) */
X{
X *xj = URANX[ (x + (y<<2) + IRAND[(x+s)&MASK]) & MASK ];
X *yj = URANY[ (y + (x<<2) + IRAND[(y+s)&MASK]) & MASK ];
X}
X
X
X
X/* Jitter2 - Generate random jitter. */
X
Xvoid Jitter2 (x,y,s,xj,yj)
X int x, y; /* Pixel location */
X int s; /* Sample number for the pixel */
X double *xj, *yj; /* Jitter (x,y) */
X{
X *xj = URANX[ ((x | (y<<2)) + IRAND[(x+s)&MASK]) & MASK ];
X *yj = URANY[ ((y | (x<<2)) + IRAND[(y+s)&MASK]) & MASK ];
X}
X
X
X/* JitterInit - Initialize look-up tables. */
X
Xvoid JitterInit ()
X{
X int i;
X
X for ( i = 0 ; i < NRAN ; i++ ) URANX[i] = xranf();
X for ( i = 0 ; i < NRAN ; i++ ) URANY[i] = xranf();
X for ( i = 0 ; i < NRAN ; i++ ) IRAND[i] = (int) (NRAN *
X xranf());
X}
END_OF_FILE
if test 1720 -ne `wc -c <'FastJitter.c'`; then
echo shar: \"'FastJitter.c'\" unpacked with wrong size!
fi
# end of 'FastJitter.c'
fi
if test -f 'FixedTrig.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'FixedTrig.c'\"
else
echo shar: Extracting \"'FixedTrig.c'\" \(1725 characters\)
sed "s/^X//" >'FixedTrig.c' <<'END_OF_FILE'
X/*
XFixed-Point Trigonometry with CORDIC Iterations
Xby Ken Turkowski
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X#define COSCALE 0x22c2dd1c /* 0.271572 */
X#define QUARTER ((int)(3.141592654 / 2.0 * (1 << 28)))
Xstatic long arctantab[32] = { /* MS 4 integral bits for radians */
X 297197971, 210828714, 124459457, 65760959, 33381290, 16755422,
X 8385879, 4193963, 2097109, 1048571, 524287, 262144, 131072,
X 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64,
X 32, 16, 8, 4, 2, 1, 0, 0,
X};
X
XCordicRotate(px, py, theta)
Xlong *px, *py;
Xregister long theta; /* Assume that abs(theta) <= pi */
X{
X register int i;
X register long x = *px, y = *py, xtemp;
X register long *arctanptr = arctantab;
X
X /* The -1 may need to be pulled out and done as a left shift */
X for (i = -1; i <= 28; i++) {
X if (theta < 0) {
X xtemp = x + (y >> i);
X y = y - (x >> i);
X x = xtemp;
X theta += *arctanptr++;
X } else {
X xtemp = x - (y >> i);
X y = y + (x >> i);
X x = xtemp;
X theta -= *arctanptr++;
X }
X }
X
X *px = frmul(x, COSCALE); /* Compensate for CORDIC enlargement */
X *py = frmul(y, COSCALE); /* frmul(a,b)=(a*b)>>31, high part */
X /* of 64-bit product */
X}
X
X
X
X
XCordicPolarize(argx, argy)
Xlong *argx, *argy; /* We assume these are already in the */
X /* right half plane */
X{
X register long theta, yi, i;
X register long x = *argx, y = *argy;
X register long *arctanptr = arctantab;
X for (i = -1; i <= 28; i++) {
X if (y < 0) { /* Rotate positive */
X yi = y + (x >> i);
X x = x - (y >> i);
X y = yi;
X theta -= *arctanptr++;
X } else { /* Rotate negative */
X yi = y - (x >> i);
X x = x + (y >> i);
X y = yi;
X theta += *arctanptr++;
X }
X }
X
X *argx = frmul(x, COSCALE);
X *argy = theta;
X}
END_OF_FILE
if test 1725 -ne `wc -c <'FixedTrig.c'`; then
echo shar: \"'FixedTrig.c'\" unpacked with wrong size!
fi
# end of 'FixedTrig.c'
fi
if test -f 'HSLtoRGB.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'HSLtoRGB.c'\"
else
echo shar: Extracting \"'HSLtoRGB.c'\" \(1736 characters\)
sed "s/^X//" >'HSLtoRGB.c' <<'END_OF_FILE'
X/*
XA Fast HSL-to-RGB Transform
Xby Ken Fishkin
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X#include <math.h>
X#include <stdio.h>
X#include "GraphicsGems.h"
X
X /*
X * RGB-HSL transforms.
X * Ken Fishkin, Pixar Inc., January 1989.
X */
X
X /*
X * given r,g,b on [0 ... 1],
X * return (h,s,l) on [0 ... 1]
X */
Xvoid
XRGB_to_HSL (r,g,b,h,s,l)
Xdouble r,g,b;
Xdouble *h, *s, *l;
X{
X double v;
X double m;
X double vm;
X double r2, g2, b2;
X
X v = MAX(r,g);
X v = MAX(v,b);
X m = MIN(r,g);
X m = MIN(m,b);
X
X if ((*l = (m + v) / 2.0) <= 0.0) return;
X if ((*s = vm = v - m) > 0.0) {
X *s /= (*l <= 0.5) ? (v + m ) :
X (2.0 - v - m) ;
X } else
X return;
X
X
X r2 = (v - r) / vm;
X g2 = (v - g) / vm;
X b2 = (v - b) / vm;
X
X if (r == v)
X *h = (g == m ? 5.0 + b2 : 1.0 - g2);
X else if (g == v)
X *h = (b == m ? 1.0 + r2 : 3.0 - b2);
X else
X *h = (r == m ? 3.0 + g2 : 5.0 - r2);
X
X *h /= 6;
X }
X
X /*
X * given h,s,l on [0..1],
X * return r,g,b on [0..1]
X */
Xvoid
XHSL_to_RGB(h,sl,l,r,g,b)
Xdouble h,sl,l;
Xdouble *r, *g, *b;
X{
X double v;
X
X v = (l <= 0.5) ? (l * (1.0 + sl)) : (l + sl - l * sl);
X if (v <= 0) {
X *r = *g = *b = 0.0;
X } else {
X double m;
X double sv;
X int sextant;
X double fract, vsf, mid1, mid2;
X
X m = l + l - v;
X sv = (v - m ) / v;
X h *= 6.0;
X sextant = h;
X fract = h - sextant;
X vsf = v * sv * fract;
X mid1 = m + vsf;
X mid2 = v - vsf;
X switch (sextant) {
X case 0: *r = v; *g = mid1; *b = m; break;
X case 1: *r = mid2; *g = v; *b = m; break;
X case 2: *r = m; *g = v; *b = mid1; break;
X case 3: *r = m; *g = mid2; *b = v; break;
X case 4: *r = mid1; *g = m; *b = v; break;
X case 5: *r = v; *g = m; *b = mid2; break;
X }
X }
X}
X
X
END_OF_FILE
if test 1736 -ne `wc -c <'HSLtoRGB.c'`; then
echo shar: \"'HSLtoRGB.c'\" unpacked with wrong size!
fi
# end of 'HSLtoRGB.c'
fi
if test -f 'Hash3D.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Hash3D.c'\"
else
echo shar: Extracting \"'Hash3D.c'\" \(1454 characters\)
sed "s/^X//" >'Hash3D.c' <<'END_OF_FILE'
X/*
XA 3D Grid Hashing Frunction
Xby Brian Wyvill
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X/* Test Program for 3D hash function.
XIn C the hash function can be defined in a macro which
Xavoids a function call
Xand the bit operations are defined in the language.
X*/
X
X#include <stdio.h>
X#include <math.h>
X#include "GraphicsGems.h"
X
X#define RANGE 256
X#define NBITS 4
X#define RBITS 4
X#define MASK 0360
X#define HASH(a,b,c) ((((a&MASK)<<NBITS|b&MASK)<<NBITS|c&MASK)>>RBITS)
X#define HSIZE 1<<NBITS*3
X#define IABS(x) (int)((x) < 0 ? -(x) : (x))
X
Xtypedef struct {
X double x,y,z;
X} Triple, *RefTriple;
X
Xtypedef struct { /* linked list of objects to be stored */
X Triple origin;
X struct Object *link;
X} Object, *RefObject;
X
Xtypedef struct { /* linked list of voxels (object pointers) */
X RefObject objectList;
X struct Voxel *link;
X} Voxel, *RefVoxel;
X
XRefVoxel table[HSIZE]; /* Table of pointers to Voxels */
X
X
Xcheckrange(z) double z;
X{
X if (z < 0 || z >= RANGE)
X fprintf(stderr,"%f out of range\n",z), exit();
X}
X
Xdouble getcoord()
X{
X char buf[80];
X double z;
X scanf("%s",buf);
X z = atof(buf);
X checkrange(z);
X return z;
X}
X
Xmain()
X{
X Triple a;
X while (TRUE) {
X printf("Enter object position x y z ===> ");
X a.x = getcoord();
X a.y = getcoord();
X a.z = getcoord();
X printf("\ncoord: %d %d %d Hashes to %d\n",IABS(a.x),IABS(a.y),IABS(a.z),
X HASH(IABS(a.x), IABS(a.y), IABS(a.z) ));
X };
X}
END_OF_FILE
if test 1454 -ne `wc -c <'Hash3D.c'`; then
echo shar: \"'Hash3D.c'\" unpacked with wrong size!
fi
# end of 'Hash3D.c'
fi
if test -f 'HypotApprox.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'HypotApprox.c'\"
else
echo shar: Extracting \"'HypotApprox.c'\" \(1545 characters\)
sed "s/^X//" >'HypotApprox.c' <<'END_OF_FILE'
X/*
XA Fast Approximation to the Hypotenuse
Xby Alan Paeth
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
Xint idist(x1, y1, x2, y2)
X int x1, y1, x2, y2;
X {
X/*
X * gives approximate distance from (x1,y1) to (x2,y2)
X * with only overestimations, and then never by more
X * than (9/8) + one bit uncertainty.
X */
X if ((x2 -= x1) < 0) x2 = -x2;
X if ((y2 -= y1) < 0) y2 = -y2;
X return (x2 + y2 - (((x2>y2) ? y2 : x2) >> 1) );
X }
X
Xint PntOnCirc(xp, yp, xc, yc, r)
X int xp, yp, xc, yc, r;
X {
X/* returns true IFF a test point (xp, yp) is to within a
X * pixel of the circle of center (xc, yc) and radius r.
X * "d" is an approximate length to circle's center, with
X * 1.0*r < dist < 1.12*r < (9/8)*r used for coarse testing.
X * The 9/8 ratio suggests the code: (x)<<3 and ((x)<<3)-(x).
X * Variables xp, yp, r and d should be of 32-bit precision.
X *
X * Note: (9/8) forms a very tight, proper inner bound but
X * must be slackened by one pixel for the outside test (#2)
X * to account for the -1/2 pixel absolute error introduced
X * when "idist" halves an odd integer; else rough clipping
X * will trim occasional points on the circle's perimeter.
X */
X int d = idist(xp, yp, xc, yc);
X if ( r > d) return(0); /* far-in */
X if (9*r < 8*(d-1)) return(0); /* far-out */
X/* full test: r < hypot(xp-xc,yp-yc) < r+1 */
X xp -= xc;
X yp -= yc;
X d = xp*xp + yp*yp;
X if (d < r*r) return(0); /* near-in */
X r += 1;
X if (d > r*r) return(0); /* near-out */
X return(1); /* WITHIN */
X }
END_OF_FILE
if test 1545 -ne `wc -c <'HypotApprox.c'`; then
echo shar: \"'HypotApprox.c'\" unpacked with wrong size!
fi
# end of 'HypotApprox.c'
fi
if test -f 'MANIFEST' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(4705 characters\)
sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
X File Name Archive # Description
X-----------------------------------------------------------
X 2DClip 1 2D Clipping: A Vector-Based Approach
X 2DClip/Makefile 1 Makefile
X 2DClip/bio.c 2 Basic operations
X 2DClip/box.h 1 BOX definition
X 2DClip/clip.c 2 Clipping routines
X 2DClip/cross.c 4 Intersection calculation
X 2DClip/line.h 1 Major definitions
X AALines 1 Rendering Anti-Aliased Lines
X AALines/00README 1 Information about AALines Gem
X AALines/AALines.c 4 Code to render an anti-aliased line
X AALines/AALines.h 1 Symbols & globals
X AALines/AAMain.c 1 Calling routine
X AALines/AATables.c 4 Initialization of tables and frame buffer
X AALines/FastMatMul.c 5 Fast routines to multiply 4x4 matrices
X AALines/LongConst.h 1 High-precision constants
X AALines/Makefile 1 Makefile
X AALines/utah.c 3 Interface to Utah Raster Toolkit
X AALines/utah.h 1 Declarations for URT interface
X AAPolyScan.c 4 Fast Anti_aliasing Polygon Scan Conversion
X Albers.c 3 Albers Equal-Area Conic Map Projection
X BinRec.c 1 Recording Animation in Binary Order
X BoundSphere.c 3 An Efficient Bounding Sphere
X BoxSphere.c 2 Box-Sphere Intersection Checking
X CircleRect.c 1 Fast Circle-Rectangle Intersection Checking
X ConcaveScan.c 4 Concave Polygon Scan Conversion
X DigitalLine.c 1 Digital Line Drawing
X Dissolve.c 3 A Digital "Dissolve" Effect
X DoubleLine.c 3 Symmetric Double Step Line Algorithm
X FastJitter.c 1 Efficient Generation of Sampling Jitter
X FitCurves.c 5 Automatically Fit Digitized Curves
X FixedTrig.c 1 Fixed-Point Trig with CORDIC Iterations
X Forms.c 4 Forms, Vectors, and Transformations
X GGVecLib.c 5 2D and 3D Vector C Library
X GraphicsGems.h 3 Graphics Gems header file
X HSLtoRGB.c 1 A Fast HSL-to-RGB Transform
X Hash3D.c 1 3D Grid Hashing Function
X HypotApprox.c 1 A Fast Approximation to the Hypotenuse
X Interleave.c 4 Bit Interleaving for Quad- or Octrees
X Label.c 2 Nice Numbers for Graph Labels
X LineEdge.c 3 Fast Line-Edge Intersections on a Uniform Grid
X MANIFEST 1 This shipping list
X Makefile 2 Makefile for the whole shebang
X MatrixInvert.c 3 Matrix Inversion
X MatrixOrtho.c 1 Matrix Orthogonalization
X MatrixPost.c 2 Efficient Post-Concatenation of Trans. Matrices
X Median.c 2 Median Finding on a 3x3 Grid
X NearestPoint.c 5 Nearest-Point-On-Curve and Bezier Root-Finder
X OrderDither.c 2 Ordered Dithering
X PixelInteger.c 1 Proper Treatment of Pixels As Integers
X PntOnLine.c 2 A Fast 2D Point-On-Line Test
X PolyScan 1 Convex Polygon Scan Conversion & Clipping
X PolyScan/Makefile 1 Makefile
X PolyScan/fancytest.c 2 Phong-shading a Texture mapping test
X PolyScan/poly.c 2 Simple utilities for polygon data structure
X PolyScan/poly.h 2 Definitions for polygon package
X PolyScan/poly_clip.c 3 Homogeneous 3D polygon clipper
X PolyScan/poly_scan.c 3 Convex polygon point-sampled scan conversion
X PolyScan/scantest.c 2 Gouraud shading and Z-buffer demo
X Quaternions.c 2 Using Quaternions for Coding 3D Transformations
X README 1 General information
X RGBTo4Bits.c 1 Mapping RGB Triples Onto Four Bits
X RayBox.c 1 Fast Ray-Box Intersection
X RayPolygon.c 1 An Efficient Ray-Polygon Intersection
X Roots3And4.c 3 Cubic and Quartic Roots
X SeedFill.c 2 A Seed Fill Algorithm
X SquareRoot.c 2 A High-Speed, Low-Precision Square Root
X Sturm 1 Using Sturm Sequences to Bracket Real Roots
X Sturm/Makefile 1 Makefile
X Sturm/main.c 2 Sample driver program
X Sturm/solve.h 1 Useful constants and types
X Sturm/sturm.c 4 Functions to build and evaluate Sturm sequence
X Sturm/util.c 1 Root polishing and evaluating utilities
X TransBox.c 1 Transforming Axis-Aligned Bounding Boxes
X TriPoints.c 2 Generating Random Points in Triangles
X ViewTrans.c 1 3D Viewing and Rotation using Orthonormal Bases
END_OF_FILE
if test 4705 -ne `wc -c <'MANIFEST'`; then
echo shar: \"'MANIFEST'\" unpacked with wrong size!
fi
# end of 'MANIFEST'
fi
if test -f 'MatrixOrtho.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'MatrixOrtho.c'\"
else
echo shar: Extracting \"'MatrixOrtho.c'\" \(1335 characters\)
sed "s/^X//" >'MatrixOrtho.c' <<'END_OF_FILE'
X/*
XMatrix Orthogonalization
XEric Raible
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X/*
X * Reorthogonalize matrix R - that is find an orthogonal matrix that is
X * "close" to R by computing an approximation to the orthogonal matrix
X *
X * T -1/2
X * RC = R(R R)
X * T -1
X * [RC is orthogonal because (RC) = (RC) ]
X * -1/2
X * To compute C, we evaluate the Taylor expansion of F(x) = (I + x)
X * (where x = C - I) about x=0.
X * This gives C = I - (1/2)x + (3/8)x^2 - (5/16)x^3 + ...
X */
X
X#include "GraphicsGems.h"
X
Xstatic float coef[10] = /* From mathematica */
X { 1, -1/2., 3/8., -5/16., 35/128., -63/256.,
X 231/1024., -429/2048., 6435/32768., -12155/65536. };
X
XMATRIX_reorthogonalize (R, limit)
X Matrix R;
X{
X Matrix I, Temp, X, X_power, Sum;
X int power;
X
X limit = MAX(limit, 10);
X
X MATRIX_transpose (R, Temp); /* Rt */
X MATRIX_multiply (Temp, R, Temp); /* RtR */
X MATRIX_identify (I);
X MATRIX_subtract (Temp, I, X); /* RtR - I */
X MATRIX_identify (X_power); /* X^0 */
X MATRIX_identify (Sum); /* coef[0] * X^0 */
X
X for (power = 1; power < limit; ++power)
X {
X MATRIX_multiply (X_power, X, X_power);
X MATRIX_constant_multiply (coef[power], X_power, Temp);
X MATRIX_add (Sum, Temp, Sum);
X }
X
X MATRIX_multiply (R, Sum, R);
X}
END_OF_FILE
if test 1335 -ne `wc -c <'MatrixOrtho.c'`; then
echo shar: \"'MatrixOrtho.c'\" unpacked with wrong size!
fi
# end of 'MatrixOrtho.c'
fi
if test -f 'PixelInteger.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'PixelInteger.c'\"
else
echo shar: Extracting \"'PixelInteger.c'\" \(1534 characters\)
sed "s/^X//" >'PixelInteger.c' <<'END_OF_FILE'
X/*
XProper Treatment of Pixels as Integers
Xby Alan Paeth
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X#define Min code[2]
X#define Med code[1]
X#define Max code[0]
X#define NCODE 3
X
X/*
X * A call to getplanes of the form:
X * getplanes(&red, &green, &blue, 256, "grb");
X *
X * fills the first three integer pointers with (near) identical
X * values which maximize red*green*blue <= 256. The final parameter
X * string defines tie-break order, here green>=red>=blue (the usual
X * default). The present code procedure calls "err(string, arg)"
X * given bad parameters; it is a simple task to rewrite the code as
X * a function which returns a success/failure code(s), as needed.
X *
X * In the example given above the code fills in the values
X * red = 6, green = 7, blue = 6.
X */
X
Xgetplanes(r, g, b, n, bias)
X int *r, *g, *b;
X char *bias;
X {
X int i, code[NCODE];
X if(strlen(bias) != NCODE )
X err("bias string \"%s\" wrong length",bias);
X Min = Med = Max = 0;
X *r = *g = *b = 0;
X while(Min*Min*Min <= n) Min++;
X Min--;
X while(Med*Med*Min <= n) Med++;
X Med--;
X Max = n/(Min*Med);
X for( i = 0; i < NCODE; i++ )
X {
X switch(bias[i])
X {
X case 'r': case 'R': *r = code[i]; break;
X case 'g': case 'G': *g = code[i]; break;
X case 'b': case 'B': *b = code[i]; break;
X default: err("bad bias character: \'%c\'",bias[i]); break;
X }
X }
X if (!(*r && *g && *b)) err("bias string \"%s\" deficient", bias);
X }
X
END_OF_FILE
if test 1534 -ne `wc -c <'PixelInteger.c'`; then
echo shar: \"'PixelInteger.c'\" unpacked with wrong size!
fi
# end of 'PixelInteger.c'
fi
if test ! -d 'PolyScan' ; then
echo shar: Creating directory \"'PolyScan'\"
mkdir 'PolyScan'
fi
if test -f 'PolyScan/Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'PolyScan/Makefile'\"
else
echo shar: Extracting \"'PolyScan/Makefile'\" \(380 characters\)
sed "s/^X//" >'PolyScan/Makefile' <<'END_OF_FILE'
X# Makefile for scantest, test program for generic convex polygon scan conversion
X#
X# Note: fancytest.c needs a main routine and several auxiliary routines
X# in order to be compiled.
X
XCFLAGS = $(GENCFLAGS)
X
Xscantest: scantest.o poly_scan.o poly.o
X $(CC) $(CFLAGS) -o scantest scantest.o poly_scan.o poly.o -lm
X
Xclean:
X /bin/rm -f scantest.o poly_clip.o poly_scan.o poly.o scantest
END_OF_FILE
if test 380 -ne `wc -c <'PolyScan/Makefile'`; then
echo shar: \"'PolyScan/Makefile'\" unpacked with wrong size!
fi
# end of 'PolyScan/Makefile'
fi
if test -f 'README' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(5838 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
X[ This package last updated Wed Dec 12 20:45:09 EST 1990. ]
X
XREADME
X
XThis package contains the most up-to-date versions of the C source
Xfiles from the book "Graphics Gems" (Editor Andrew S. Glassner,
XAcademic Press, 1990 ISBM 0-12-286165-5, 833 pgs.).
X
XAll known bugs have been fixed, formatting problems have been
Xcorrected, and enchancements to some of the original Gems have
Xbeen made.
X
XMakefiles are provided that create stand-alone programs, many object
Xfiles, and "gemlib.a". This Graphics Gem Library is created for
Xcompilation-testing only, and is not intended to be a usable library
X(although it may become so in the future). Indeed, many of the Gems
Xwill not compile or run properly without the addition of functions,
Xtables, and the like. See the book and the Makefile for more details.
X
XEach Gem is made available on an as-is basis; although
Xconsiderable effort has been expended to check the programs
Xas originally designed and their release in electronic form,
Xthe authors and the publisher make no guarantees or
Xwarrantees about the correctness of any of these programs or
Xalgorithms.
X
XThe authors and the publisher hold no copyright restrictions
Xon any of these files; this source code is public domain, and
Xis freely available to the entire computer graphics community
Xfor study, use, and modification. We do request that the
Xcomment at the top of each file, identifying the original
Xauthor and its original publication in the book Graphics
XGems, be retained in all programs that use these files.
X
XAn archive of the most current versions of all the Gems is maintained
Xon weedeater.math.yale.edu (130.132.23.17) and is available via
Xanonymous ftp in pub/GraphicsGems/src.
X
XYou are encouraged to submit bug fixes, skeleton programs, and the like
Xto Craig Kolb (kolb@yale.edu).
X
XAndrew Glassner / Craig Kolb
X
X================
X
XThe table below gives the correspondence between each source
Xfile in this directory and the name of the Gem it implements.
XEach implementation illustrates one way to realize the
Xtechniques described by the accompanying Gem in the book.
XThe files here contain only the source code for that
Xrealization. For a more complete description of the
Xalgorithms and their applications see the Gems of the same
Xname in the first 11 Chapters of the book.
X
X---------- header files ----------
XGraphicsGems.h / Graphics Gems C Header File
X
X---------- C code ----------
X2DClip/* / Two-Dimensional Clipping:
X A Vector-Based Approach
XAALines/* / Rendering Anti-Aliased Lines
XAAPolyScan.c / Fast Anti-Aliasing Polygon
X Scan Conversion
XAlbers.c / Albers Equal-Area Conic Map
X Projection
XBinRec.c / Recording Animation in Binary Order
X For Progressive Temporal Refinement
XBoundSphere.c / An Efficient Bounding Sphere
XBoxSphere.c / A Simple Method for Box-Sphere
X Intersection Checking
XCircleRect.c / Fast Circle-Rectangle Intersection
X Checking
XConcaveScan.c / Concave Polygon Scan Conversion
XDigitalLine.c / Digital Line Drawing
XDissolve.c / A Digital "Dissolve" Effect
XDoubleLine.c / Symmetric Double Step Line Algorithm
XFastJitter.c / Efficient Generation of Sampling
X Jitter Using Look-up Tables
XFitCurves.c / An Algorithm for Automatically
X Fitting Digitized Curves
XFixedTrig.c / Fixed-Point Trigonometry with
X CORDIC Iterations
XForms.c / Forms, Vectors, and Transforms
XGGVecLib.c / 2D And 3D Vector C Library
XHSLtoRGB.c / A Fast HSL-to-RGB Transform
XHash3D.c / 3D Grid Hashing Function
XHypotApprox.c / A Fast Approximation to
X the Hypotenuse
XInterleave.c / Bit Interleaving for Quad-
X or Octrees
XLabel.c / Nice Numbers for Graph Labels
XLineEdge.c / Fast Line-Edge Intersections On
X A Uniform Grid
XMatrixInvert.c / Matrix Inversion
XMatrixOrtho.c / Matrix Orthogonalization
XMatrixPost.c / Efficient Post-Concatenation of
X Transformation Matrices
XMedian.c / Median Finding on a 3x3 Grid
XNearestPoint.c / Solving the
X Nearest-Point-On-Curve Problem
X and
X A Bezier Curve-Based Root-Finder
XOrderDither.c / Ordered Dithering
XPixelInteger.c / Proper Treatment of Pixels
X As Integers
XPntOnLine.c / A Fast 2D Point-On-Line Test
XPolyScan/* / Generic Convex Polygon
X Scan Conversion and Clipping
XQuaternions.c / Using Quaternions for Coding
X 3D Transformations
XRGBTo4Bits.c / Mapping RGB Triples Onto Four Bits
XRayBox.c / Fast Ray-Box Intersection
XRayPolygon.c / An Efficient Ray-Polygon
X Intersection
XRoots3And4.c / Cubic and Quartic Roots
XSeedFill.c / A Seed Fill Algorithm
XSquareRoot.c / A High-Speed, Low-Precision
X Square Root
XSturm/* / Using Sturm Sequences to Bracket
X Real Roots of Polynomial Equations
XTransBox.c / Transforming Axis-Aligned
X Bounding Boxes
XTriPoints.c / Generating Random Points
X In Triangles
XViewTrans.c / 3D Viewing and Rotation Using
X Orthonormal Bases
END_OF_FILE
if test 5838 -ne `wc -c <'README'`; then
echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'RGBTo4Bits.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'RGBTo4Bits.c'\"
else
echo shar: Extracting \"'RGBTo4Bits.c'\" \(1448 characters\)
sed "s/^X//" >'RGBTo4Bits.c' <<'END_OF_FILE'
X/*
XMapping RGB Triples onto Four Bits
Xby Alan Paeth
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
Xremap8(R, G, B, R2, G2, B2)
X float R, G, B, *R2, *G2, *B2;
X {
X/*
X * remap8 maps floating (R,G,B) triples onto quantized
X * (R2,B2,B2) triples and returns the code (vertex)
X * value/color table entry for the quantization. The
X * points (eight) are the vertices of the cube.
X */
X int code;
X *R2 = *G2 = *B2 = 0.0;
X code = 0;
X if (R >= 0.5) { *R2 = 1.0; code |= 1; }
X if (G >= 0.5) { *G2 = 1.0; code |= 2; }
X if (B >= 0.5) { *B2 = 1.0; code |= 4; }
X return(code);
X }
X
X/*
X * remap14 maps floating (R,G,B) triples onto quantized
X * (R2,B2,B2) triples and returns the code (vertex)
X * value/color table entry for the quantization. The
X * points (fourteen) are the vertices of the cuboctahedron.
X */
X
Xfloat rval[] = { 0.,.5 ,.5 , 1.,.0 , 0., 0.,.5,
X .5 , 1., 1., 1., 0.,.5 ,.5 , 1.};
Xfloat gval[] = { 0.,.5 , 0., 0.,.5 , 1., 0.,.5,
X .5 , 1., 0.,.5 , 1., 1.,.5 , 1.};
Xfloat bval[] = { 0., 0.,.5 , 0.,.5 , 0., 1.,.5,
X .5 , 0., 1.,.5 , 1.,.5 , 1., 1.};
X
Xint remap14(R, G, B, R2, G2, B2)
X float R, G, B, *R2, *G2, *B2;
X {
X int code = 0;
X if ( R + G + B > 1.5) code |= 8;
X if (-R + G + B > 0.5) code |= 4;
X if ( R - G + B > 0.5) code |= 2;
X if ( R + G - B > 0.5) code |= 1;
X *R2 = rval[code];
X *G2 = gval[code];
X *B2 = bval[code];
X return(code);
X }
END_OF_FILE
if test 1448 -ne `wc -c <'RGBTo4Bits.c'`; then
echo shar: \"'RGBTo4Bits.c'\" unpacked with wrong size!
fi
# end of 'RGBTo4Bits.c'
fi
if test -f 'RayBox.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'RayBox.c'\"
else
echo shar: Extracting \"'RayBox.c'\" \(1793 characters\)
sed "s/^X//" >'RayBox.c' <<'END_OF_FILE'
X/*
XFast Ray-Box Intersection
Xby Andrew Woo
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X#include "GraphicsGems.h"
X
X#define NUMDIM 3
X#define RIGHT 0
X#define LEFT 1
X#define MIDDLE 2
X
Xchar HitBoundingBox(minB,maxB, origin, dir,coord)
Xdouble minB[NUMDIM], maxB[NUMDIM]; /*box */
Xdouble origin[NUMDIM], dir[NUMDIM]; /*ray */
Xdouble coord[NUMDIM]; /* hit point */
X{
X char inside = TRUE;
X char quadrant[NUMDIM];
X register int i;
X int whichPlane;
X double maxT[NUMDIM];
X double candidatePlane[NUMDIM];
X
X /* Find candidate planes; this loop can be avoided if
X rays cast all from the eye(assume perpsective view) */
X for (i=0; i<NUMDIM; i++)
X if(origin[i] < minB[i]) {
X quadrant[i] = LEFT;
X candidatePlane[i] = minB[i];
X inside = FALSE;
X }else if (origin[i] > maxB[i]) {
X quadrant[i] = RIGHT;
X candidatePlane[i] = maxB[i];
X inside = FALSE;
X }else {
X quadrant[i] = MIDDLE;
X }
X
X /* Ray origin inside bounding box */
X if(inside) {
X coord = origin;
X return (TRUE);
X }
X
X
X /* Calculate T distances to candidate planes */
X for (i = 0; i < NUMDIM; i++)
X if (quadrant[i] != MIDDLE && dir[i] !=0.)
X maxT[i] = (candidatePlane[i]-origin[i]) / dir[i];
X else
X maxT[i] = -1.;
X
X /* Get largest of the maxT's for final choice of intersection */
X whichPlane = 0;
X for (i = 1; i < NUMDIM; i++)
X if (maxT[whichPlane] < maxT[i])
X whichPlane = i;
X
X /* Check final candidate actually inside box */
X if (maxT[whichPlane] < 0.) return (FALSE);
X for (i = 0; i < NUMDIM; i++)
X if (whichPlane != i) {
X coord[i] = origin[i] + maxT[whichPlane] *dir[i];
X if ((quadrant[i] == RIGHT && coord[i] < minB[i]) ||
X (quadrant[i] == LEFT && coord[i] > maxB[i]))
X return (FALSE); /* outside box */
X }else {
X coord[i] = candidatePlane[i];
X }
X return (TRUE); /* ray hits box */
X}
X
END_OF_FILE
if test 1793 -ne `wc -c <'RayBox.c'`; then
echo shar: \"'RayBox.c'\" unpacked with wrong size!
fi
# end of 'RayBox.c'
fi
if test -f 'RayPolygon.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'RayPolygon.c'\"
else
echo shar: Extracting \"'RayPolygon.c'\" \(1553 characters\)
sed "s/^X//" >'RayPolygon.c' <<'END_OF_FILE'
X/*
XAn Efficient Ray/Polygon Intersection
Xby Didier Badouel
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X/* the value of t is computed.
X * i1 and i2 come from the polygon description.
X * V is the vertex table for the polygon and N the
X * associated normal vectors.
X */
XP[0] = ray.O[0] + ray.D[0]*t;
XP[1] = ray.O[1] + ray.D[1]*t;
XP[2] = ray.O[2] + ray.D[2]*t;
Xu0 = P[i1] - V[0][i1]; v0 = P[i2] - V[0][i2];
Xinter = FALSE; i = 2;
Xdo {
X /* The polygon is viewed as (n-2) triangles. */
X u1 = V[i-1][i1] - V[0][i1]; v1 = V[i-1][i2] - V[0][i2];
X u2 = V[i ][i1] - V[0][i1]; v2 = V[i ][i2] - V[0][i2];
X
X if (u1 == 0) {
X beta = u0/u2;
X if ((beta >= 0.)&&(beta <= 1.)) {
X alpha = (v0 - beta*v2)/v1;
X inter = ((alpha >= 0.)&&(alpha+beta) <= 1.));
X }
X } else {
X beta = (v0*u1 - u0*v1)/(v2*u1 - u2*v1);
X if ((beta >= 0.)&&(beta <= 1.)) {
X alpha = (u0 - beta*u2)/u1;
X inter = ((alpha >= 0)&&((alpha+beta) <= 1.));
X }
X }
X} while ((!inter)&&(++i < poly.n));
X
Xif (inter) {
X /* Storing the intersection point. */
X ray.P[0] = P[0]; ray.P[1] = P[1]; ray.P[2] = P[2];
X /* the normal vector can be interpolated now or later. */
X if (poly.interpolate) {
X gamma = 1 - (alpha+beta);
X ray.normal[0] = gamma * N[0][0] + alpha * N[i-1][0] +
X beta * N[i][0];
X ray.normal[1] = gamma * N[0][1] + alpha * N[i-1][1] +
X beta * N[i][1];
X ray.normal[2] = gamma * N[0][2] + alpha * N[i-1][2] +
X beta * N[i][2];
X }
X}
Xreturn (inter);
END_OF_FILE
if test 1553 -ne `wc -c <'RayPolygon.c'`; then
echo shar: \"'RayPolygon.c'\" unpacked with wrong size!
fi
# end of 'RayPolygon.c'
fi
if test ! -d 'Sturm' ; then
echo shar: Creating directory \"'Sturm'\"
mkdir 'Sturm'
fi
if test -f 'Sturm/Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Sturm/Makefile'\"
else
echo shar: Extracting \"'Sturm/Makefile'\" \(211 characters\)
sed "s/^X//" >'Sturm/Makefile' <<'END_OF_FILE'
X#
X# Makefile
X#
X# command file for make to compile the solver.
X
Xsolve: main.o sturm.o util.o
X cc -o solve main.o sturm.o util.o -lm
X
Xclean:
X /bin/rm -f main.o sturm.o util.o solve
X
Xmain.o sturm.o util.o: solve.h
END_OF_FILE
if test 211 -ne `wc -c <'Sturm/Makefile'`; then
echo shar: \"'Sturm/Makefile'\" unpacked with wrong size!
fi
# end of 'Sturm/Makefile'
fi
if test -f 'Sturm/solve.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Sturm/solve.h'\"
else
echo shar: Extracting \"'Sturm/solve.h'\" \(710 characters\)
sed "s/^X//" >'Sturm/solve.h' <<'END_OF_FILE'
X
X/*
X * solve.h
X *
X * some useful constants and types.
X */
X#define MAX_ORDER 12
X/* maximum order for a polynomial */
X
X#define RELERROR 1.0e-14
X/* smallest relative error we want */
X
X#define MAXPOW 32
X/* max power of 10 we wish to search to */
X
X#define MAXIT 800
X/* max number of iterations */
X
X/* a coefficient smaller than SMALL_ENOUGH is considered to
X be zero (0.0). */
X
X#define SMALL_ENOUGH 1.0e-12
X
X
X/*
X * structure type for representing a polynomial
X */
Xtypedef struct p {
X int ord;
X double coef[MAX_ORDER];
X} poly;
X
Xextern int modrf();
Xextern int numroots();
Xextern int numchanges();
Xextern int buildsturm();
X
Xextern double evalpoly();
X
X
END_OF_FILE
if test 710 -ne `wc -c <'Sturm/solve.h'`; then
echo shar: \"'Sturm/solve.h'\" unpacked with wrong size!
fi
# end of 'Sturm/solve.h'
fi
if test -f 'Sturm/util.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Sturm/util.c'\"
else
echo shar: Extracting \"'Sturm/util.c'\" \(1768 characters\)
sed "s/^X//" >'Sturm/util.c' <<'END_OF_FILE'
X
X/*
X * util.c
X *
X * some utlity functions for root polishing and evaluating
X * polynomials.
X */
X#include <math.h>
X#include <stdio.h>
X#include "solve.h"
X
X/*
X * evalpoly
X *
X * evaluate polynomial defined in coef returning its value.
X */
Xdouble
Xevalpoly (ord, coef, x)
X int ord;
X double *coef, x;
X{
X double *fp, f;
X
X fp = &coef[ord];
X f = *fp;
X
X for (fp--; fp >= coef; fp--)
X f = x * f + *fp;
X
X return(f);
X}
X
X
X/*
X * modrf
X *
X * uses the modified regula-falsi method to evaluate the root
X * in interval [a,b] of the polynomial described in coef. The
X * root is returned is returned in *val. The routine returns zero
X * if it can't converge.
X */
Xint
Xmodrf(ord, coef, a, b, val)
X int ord;
X double *coef;
X double a, b, *val;
X{
X int its;
X double fa, fb, x, lx, fx, lfx;
X double *fp, *scoef, *ecoef;
X
X scoef = coef;
X ecoef = &coef[ord];
X
X fb = fa = *ecoef;
X for (fp = ecoef - 1; fp >= scoef; fp--) {
X fa = a * fa + *fp;
X fb = b * fb + *fp;
X }
X
X /*
X * if there is no sign difference the method won't work
X */
X if (fa * fb > 0.0)
X return(0);
X
X if (fabs(fa) < RELERROR) {
X *val = a;
X return(1);
X }
X
X if (fabs(fb) < RELERROR) {
X *val = b;
X return(1);
X }
X
X lfx = fa;
X lx = a;
X
X
X for (its = 0; its < MAXIT; its++) {
X
X x = (fb * a - fa * b) / (fb - fa);
X
X fx = *ecoef;
X for (fp = ecoef - 1; fp >= scoef; fp--)
X fx = x * fx + *fp;
X
X if (fabs(x) > RELERROR) {
X if (fabs(fx / x) < RELERROR) {
X *val = x;
X return(1);
X }
X } else if (fabs(fx) < RELERROR) {
X *val = x;
X return(1);
X }
X
X if ((fa * fx) < 0) {
X b = x;
X fb = fx;
X if ((lfx * fx) > 0)
X fa /= 2;
X } else {
X a = x;
X fa = fx;
X if ((lfx * fx) > 0)
X fb /= 2;
X }
X
X lx = x;
X lfx = fx;
X }
X
X fprintf(stderr, "modrf overflow %f %f %f\n", a, b, fx);
X
X return(0);
X}
X
X
X
END_OF_FILE
if test 1768 -ne `wc -c <'Sturm/util.c'`; then
echo shar: \"'Sturm/util.c'\" unpacked with wrong size!
fi
# end of 'Sturm/util.c'
fi
if test -f 'TransBox.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'TransBox.c'\"
else
echo shar: Extracting \"'TransBox.c'\" \(1672 characters\)
sed "s/^X//" >'TransBox.c' <<'END_OF_FILE'
X/*
XTransforming Axis-Aligned Bounding Boxes
Xby Jim Arvo
Xfrom "Graphics Gems", Academic Press, 1990
X*/
X
X#include "GraphicsGems.h"
X/* Transforms a 3D axis-aligned box via a 3x3 matrix and a translation
X * vector and returns an axis-aligned box enclosing the result. */
X
Xvoid Transform_Box( M, T, A, B )
XMatrix3 M; /* Transform matrix. */
XVector3 T; /* Translation matrix. */
XBox3 A; /* The original bounding box. */
XBox3 *B; /* The transformed bounding box. */
X {
X float a, b;
X float Amin[3], Amax[3];
X float Bmin[3], Bmax[3];
X int i, j;
X
X /*Copy box A into a min array and a max array for easy reference.*/
X
X Amin[0] = A.min.x; Amax[0] = A.max.x;
X Amin[1] = A.min.y; Amax[1] = A.max.y;
X Amin[2] = A.min.z; Amax[2] = A.max.z;
X
X /* Take care of translation by beginning at T. */
X
X Bmin[0] = Bmax[0] = T.x;
X Bmin[1] = Bmax[1] = T.y;
X Bmin[2] = Bmax[2] = T.z;
X
X /* Now find the extreme points by considering the product of the */
X /* min and max with each component of M. */
X
X for( i = 0; i < 3; i++ )
X for( j = 0; j < 3; j++ )
X {
X a = M.element[i][j] * Amin[j];
X b = M.element[i][j] * Amax[j];
X if( a < b )
X
X {
X Bmin[i] += a;
X Bmax[i] += b;
X }
X else
X {
X Bmin[i] += b;
X Bmax[i] += a;
X }
X }
X
X /* Copy the result into the new box. */
X
X B->min.x = Bmin[0]; B->max.x = Bmax[0];
X B->min.y = Bmin[1]; B->max.y = Bmax[1];
X B->min.z = Bmin[2]; B->max.z = Bmax[2];
X
X }
END_OF_FILE
if test 1672 -ne `wc -c <'TransBox.c'`; then
echo shar: \"'TransBox.c'\" unpacked with wrong size!
fi
# end of 'TransBox.c'
fi
if test -f 'ViewTrans.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'ViewTrans.c'\"
else
echo shar: Extracting \"'ViewTrans.c'\" \(1575 characters\)
sed "s/^X//" >'ViewTrans.c' <<'END_OF_FILE'
X/*
X3D Viewing and Rotation Using Orthonormal Bases
Xby Steve Cunningham
Xfrom "Grahics Gems", Academic Press, 1990
X*/
X
X/*
X * Transformations are presented as 4 by 3 matrices, omitting the
X * fourth column to save memory.
X *
X * Functions are used from the Graphics Gems vector C library
X */
X
X
X#include "GraphicsGems.h"
X
Xtypedef float Transform[4][3];
X
Xvoid BuildViewTransform( VRP, EP, UP, T )
X Point3 VRP, EP, UP;
X Transform T;
X{
X Vector3 U, V, N;
X float dot;
X
X /*
X * Compute vector N = EP - VRP and normalize N
X */
X N.x = EP.x - VRP.x; N.y = EP.y - VRP.y; N.z = EP.z - VRP.z;
X V3Normalize(&N);
X
X /*
X * Compute vector V = UP - VRP
X * Make vector V orthogonal to N and normalize V
X */
X V.x = UP.x - VRP.x; V.y = UP.y - VRP.y; V.z = UP.z - VRP.z;
X dot = V3Dot(&V,&N);
X V.x -= dot * N.x; V.y -= dot * N.y; V.z -= dot * N.z;
X V3Normalize(&V);
X
X
X /*
X * Compute vector U = V x N (cross product)
X */
X V3Cross(&V,&N,&U);
X
X /*
X * Write the vectors U, V, and N as the first three rows of the
X * first, second, and third columns of T, respectively
X */
X T[0][0] = U.x; /* column 1 , vector U */
X T[1][0] = U.y;
X T[2][0] = U.z;
X T[0][1] = V.x; /* column 2 , vector V */
X T[1][1] = V.y;
X T[2][1] = V.z;
X T[0][2] = N.x; /* column 3 , vector N */
X T[1][2] = N.y;
X T[2][2] = N.z;
X
X /*
X * Compute the fourth row of T to include the translation of
X * VRP to the origin
X */
X T[3][0] = - U.x * VRP.x - U.y * VRP.y - U.z * VRP.z;
X T[3][1] = - V.x * VRP.x - V.y * VRP.y - V.z * VRP.z;
X T[3][2] = - N.x * VRP.x - N.y * VRP.y - N.z * VRP.z;
X
X return;
X}
X
X
END_OF_FILE
if test 1575 -ne `wc -c <'ViewTrans.c'`; then
echo shar: \"'ViewTrans.c'\" unpacked with wrong size!
fi
# end of 'ViewTrans.c'
fi
echo shar: End of archive 1 \(of 5\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 3 4 5 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked all 5 archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0
| file: /Techref/method/io/graphics/Part01.sh, 58KB, , updated: 1999/6/25 09:58, local time: 2024/11/15 14:48,
18.118.26.209:LOG IN
|
| ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://massmind.ecomorder.com/techref/method/io/graphics/Part01.sh"> method io graphics Part01</A> |
| Did you find what you needed? |
Welcome to ecomorder.com! |
Welcome to massmind.ecomorder.com! |
.