#! /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 16 (of 19)."
# Contents:  Doc/Guide/objects.tex etc/rsconvert/yacc.y
#   libray/libobj/hf.c
# Wrapped by cek@oyoy on Sun Feb  9 21:56:51 1992
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'Doc/Guide/objects.tex' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'Doc/Guide/objects.tex'\"
else
echo shar: Extracting \"'Doc/Guide/objects.tex'\" \(16473 characters\)
sed "s/^X//" >'Doc/Guide/objects.tex' <<'END_OF_FILE'
X\chapter{Object Definition}
X
XObjects in {\rayshade} are composed of relatively simple {\em primitive}
Xobjects.  These primitives may be used by themselves, or they
Xmay be combined to form more complex objects known as {\em aggregates}.
XA special family of aggregate objects,
X{\em Constructive Solid Geometry} or CSG
Xobjects, are the result of a boolean operations applied to
Xprimitive, aggregate, or CSG objects.
X
XThis chapter describes objects from a strictly geometric point of
Xview.  Later chapters on surfaces, textures, and shading describe
Xhow object appearances are defined.
X
XAn {\em instance} is an object that has optionally been transformed
Xand
Xtextured.  They are the entities that are actually rendered by
X{\rayshade}; when you specify that, for example, a textured
Xsphere is to be rendered, you are said to be instantiating
Xthe textured sphere.
XAn instance
Xis specified as a primitive, aggregate, or CSG object that
Xis followed by optional transformation and texturing information.
XTransformations and textures are described in Chapters 7 and 8 respectively.
X
X\section{The World Object}
X
XWriting a {\rayshade} input file is principally
Xa matter of defining a special aggregate object, the World object,
Xwhich is a list of the objects in the scene.  When writing a {\rayshade}
Xinput file, all objects that are instantiated outside of object-definition
Xblocks are added to the World object; you need not (nor should you)
Xdefine the World object explicitly in the input file.
X
X\section{Primitives}
X
XPrimitive objects are the building box with which other objects are
Xcreated.  Each primitive type has associated with it specialized
Xmethods for
Xcreation,
Xintersection with a ray,
Xbounding box calculation,
Xsurface normal calculation,
Xray enter/exit classification,
Xand for the computation 2D texture coordinates termed {\em u-v}
Xcoordinates.
XThis latter method is often referred to as the {\em inverse mapping}
Xmethod.
X
XWhile most of these methods should be of little concern to you, the
Xinverse mapping methods
Xwill affect the way in which certain textures are applied to primitives.
XInverse mapping is a matter of computing normalized $u$ and $v$ coordinates
Xfor a given point on the surface of the primitive.  For planar objects,
Xthe $u$ and $v$ coordinates of a point are computed
Xby linear interpolation based upon the $u$ and $v$ coordinates assigned
Xto vertices or other known points on the primitive.  For non-planar
Xobjects, $uv$ computation can be considerably more involved.
X
XThis section briefly describes each primitive and
Xthe syntax that should be used to create an instance of the primitive.
XIt also describes the inverse mapping method, if any, for each type.
X
X\begin{defprim}{blob}{{\em thresh st r} \evec{p} [{\em st r} \evec{p} \ldots]}
X	Defines a blob with consisting of a threshold equal to {\em thresh},
X	and a
X	group of one or more metaballs.  Each metaball is defined by 
X	its position \evec{p}, radius {\em r}, and strength {\em st}.
X\end{defprim}
XThe metaballs affect each other according to a superimposed
Xdensity distribution:
X\[
XF(x,y,z) = \sum_{i=0}^n b_{i}e^{-d_{i}} - T = 0
X\]
XThere is no inverse mapping method for blobs.
X
X\begin{defprim}{box}{\evec{corner1} \evec{corner2}}
X	Creates an axis-aligned box
X	which has \evec{corner1} and \evec{corner2} as
X	opposite corners.
X\end{defprim}
XTransformations may be applied to the box if a non-axis-aligned instance
Xis required.  There is no inverse mapping method for boxes.
X
X\begin{defprim}{sphere}{{\em radius} \evec{center}}
X	Creates a sphere with the given {\em radius} and centered at the
X	given position.
X\end{defprim}
XNote that ellipsoids may be created by applying the proper scaling
Xto a sphere.  Inverse mapping on the sphere is accomplished
Xby computing the longitude and latitude of the point on the sphere,
Xwith the $u$ value corresponding to longitude and $v$ to latitude.
XOn an untransformed sphere, the $z$ axis defines the poles, and the
X$x$ axis intersects the sphere at $u = 0$, $v = 0.5$.  There are
Xdegeneracies at the poles: the south pole contains all points of
Xlatitude 0., the north all points of latitude 1.
X
X\begin{defprim}{torus}{{\em rmajor rminor} \evec{center} \evec{up}}
X	Creates a torus centered at \evec{center} by rotating
X	a circle with the given minor radius around the center
X	point at a distance equal to the major radius. 
X\end{defprim}
XIn tori inverse mapping,
Xthe $u$ value is computed using the angle of rotation about the
Xup vector, and the $v$ value is computing the angle of rotation
Xaround the tube, with $v=0$ occuring on the innermost point of the tube.
X
X\begin{defprim}{triangle}{\evec{p1} \evec{p2} \evec{p3}}
X	Creates a triangle with the given vertices.
X\end{defprim}
X
X\begin{defprim}{triangle}{\evec{p1} \evec{n1} \evec{p2} \evec{n2}
X	\evec{p3} \evec{n3}}
X	Creates a Phong-shaded triangle with the given vertices and
X	vertex normals.
X\end{defprim}
XFor both Phong- and flat-shaded triangles, the $u$ axis is the
Xvector from \evec{p1} to \evec{p2}, and the $v$ axis the vector
Xfrom \evec{p1} to \evec{p3}.  There is a degeneracy at
X\evec{p3}, which contains all points with $v = 1.0$.  This default
Xmapping may be modified using the {\tt triangleuv} primitive described
Xbelow.
X
X\begin{defprim}{triangleuv}{\evec{p1} \evec{n1} \evec{uv1}
X  \evec{p2} \evec{n2} \evec{uv2}
X  \evec{p3} \evec{n3} \evec{uv3}}
X	Creates a Phong-shaded triangle with the given vertices,
X	vertex normals.  When performing texturing, the
X	{\em uv} given for each vertex are used instead of the
X	default values.
X\end{defprim}
XWhen computing $uv$ coordinates within the interior of the
Xtriangle, linear interpolation of the coordinates associated with
Xeach triangle vertex is used.
X
X\begin{defprim}{poly}{\evec{p1} \evec{p2} \evec{p3} [\evec{p4} \ldots ]}
X	Creates a polygon with the given vertices. The vertices
X	should be given in counter-clockwise order as one is
X	looking at the ``front'' side of the polygon.  The number of
X	vertices in a polygon is limited only by available memory.
X\end{defprim}
XInverse mapping for arbitrary polygons is problematical.
X{\Rayshade}
Xpunts and equates $u$ with the $x$ coordinate of the point of intersection,
Xand $v$ with the $y$ coordinate.
X
X\begin{defprim}{heightfield}{{\em file}}
X	Creates a height field defined by the altitude data stored
X	in the named {\em file}.  The height field is based upon
X	perturbations of the unit square in the $z=0$ plane, and is
X	rendered as a surface tessellated by right isosceles triangles.
X\end{defprim}
XSee Appendix C for a discussion of the format of a height field file.
XHeight field inverse mapping is straight-forward:  $u$ is the
X$x$ coordinate of the point of intersection, $v$ the $y$ coordinate.
X
X\begin{defprim}{plane}{\evec{point} \evec{normal}}
X	Creates a plane that passes through the given point and
X	has the specified normal.
X\end{defprim}
XInverse mapping on the plane is identical to polygonal inverse mapping.
X
X\begin{defprim}{cylinder}{{\em radius} \evec{bottom} \evec{top}}
X	Creates a cylinder that extends from \evec{bottom} to \evec{top}
X	and has the indicated {\em radius}.  Cylinders are rendered
X	{\em without} endcaps.
X\end{defprim}
XThe cylinder's axis defines the $v$ axis.  The $u$ axis wraps around the
Xcylinder, with $u=0$ dependent upon the orientation of the cylinder.
X
X
X\begin{defprim}{cone}{$rad_{bottom}$ \evec{bottom} $rad_{top}$ \evec{top}}
X	Creats a (truncated) cone that extends from \evec{bottom} to
X	\evec{top}.  The cone will have a radius of $rad_{bottom}$ at
X	\evec{bottom} and a radius of $rad_{top}$ at \evec{top}.
X	Cones are rendered {\em without} endcaps.
X\end{defprim}
XCone inverse mapping is analogous to cylinder mapping.
X
X\begin{defprim}{disc}{{\em radius} \evec{pos} \evec{normal}}
X	Creates a disc centered at the given position and with the
X	indicated surface normal.
X\end{defprim}
XDiscs are useful for placing
Xendcaps on cylinders and cones.
XInverse mapping for the disc is based on the computation of the
Xnormalized polar coordinates of the point of intersection.  The
Xnormalized radius
Xof the point of intersection is assigned to $u$, while the normalized angle
Xfrom a reference vector is assigned to $v$.
X
X\section{Aggregate Objects}
X
XAn aggregate is a collection of primitives, aggregate, and CSG
Xobjects.  An aggregate, once defined, may be instantiated at will,
Xwhich means that
Xcopies that are optionally transformed and textured may be made.
XIf a scene calls for the presence of many geometrically identical
Xobjects, only one such object need be defined; the one defined object
Xmay then be instantiated many times.
X
XAn aggregate is one of several possible types.  These aggregate types
Xare differentiated by the type of ray/aggregate intersection algorithm
X(often termed an {\em acceleration technique} or {\em efficiency scheme})
Xthat is used.
X
XAggregates are defined by giving a keyword that defines the
Xtype of the aggregate, followed by
Xa series of object instantiations and
Xsurface definitions, and terminated using the {\tt end} keyword.
XIf a defined object contains no instantiations, a warning message
Xis printed.
X
XThe most basic type of aggregate, the {\em list}, performs
Xintersection testing in the simplest possible way:  Each object in the
Xlist is tested for intersection with the ray in turn, and the closest
Xintersection is returned.
X
X\begin{defkey}{list}{\ldots {\tt end}}
X	Create a List object containing those objects instantiated between
X	the {\tt list}/{\tt end} pair.
X\end{defkey}
X
XThe {\em grid} aggregate
Xdivides the region of space it occupies into a number of discrete
Xbox-shaped
Xvoxels.  Each of these voxels contains a list of the objects that
Xintersect the voxel.  This discretization makes it possible to
Xrestrict the objects
Xtested for intersection to those that are likely to hit the ray,
Xand to test
Xthe objects in nearly ``closest-first'' order.
X
X\begin{defkey}{grid}{{\em xvox yvox zvox} \ldots {\tt end}}
X	Create a Grid objects composed of {\em xvox} by {\em yvox} by
X	{\em zvox} voxels containing those objects
X	instantiated between the {\tt grid}/{\tt end} pair.
X\end{defkey}
XIt is usually only worthwhile to ``engrid'' rather large,
Xcomplex collections of objects.  Grids also use a great deal more
Xmemory than List objects.
X
X\section {Constructive Solid Geometry}
X
XConstructive Solid Geometry is
Xthe process of building solid objects from other solids.
XThe three CSG
Xoperators are Union, Intersection, and Difference.  Each operator
Xacts upon two objects and produces a single object result.
XBy combining multiple levels of CSG operators, complex
Xobjects can be produced from simple primitives.
X
XThe union of two objects results in an
Xobject that encloses the space occupied by the two given objects.
XIntersection results in an object that encloses the space where the two
Xgiven objects overlap.  Difference is an order dependent operator; it
Xresults in the
Xfirst given object minus the space where the second intersected
Xthe first.
X
X\subsection{CSG in {\Rayshade}}
X
XCSG in {\rayshade} will generally operate properly when applied to
Xconjunction with
Xon boxes, spheres,
Xtori, and blobs.
XThese primitives are by nature consistent, as they all
Xenclose a portion of space (no hole from the ``inside'' to the
X``outside''), have surface normals which point outward (they
Xare not ``inside-out''), and do not have any extraneous surfaces.
X
XCSG objects may also be constructed from aggregate objects.
XThese aggregates contain
Xwhatever is listed inside, and may therefore be inconsistent.
XFor example, an object which contains a single triangle will not
Xproduce correct results in CSG models, because the triangle does not enclose
Xspace.  However, a collection of four triangles which form a pyramid
Xdoes enclose space, and if the triangle normals
Xare oriented correctly,
Xthe CSG operators should work correctly on the pyramid.
X
XCSG objects are specified by surrounding the objects upon
Xwhich to operate, as well as any associated surface-binding commands,
Xby the operator verb on one side and the {\tt end}
Xkeyword on the other:
X
X\begin{defkey}{union}{$<${\em Object}$>$ $<${\em Object}$>$
X[$<${\em Object}$>$ \ldots] {\tt end}}
X	Specify a new object defined as the union of the
X	given objects.
X\end{defkey}
X
X\begin{defkey}{difference}{$<${\em Object}$>$ $<${\em Object}$>$ 
X[$<${\em Object}$>$ \ldots] {\tt end}}
X	Specify a new object defined as the difference of the
X	given objects.
X\end{defkey}
X
X\begin{defkey}{intersect}{$<${\em Object}$>$ $<${\em Object}$>$
X[$<${\em Object}$>$ \ldots] {\tt end}}
X	Specify a new object defined as the intersection of the
X	given objects.
X\end{defkey}
X
XNote that the current implementation does not support more that two
Xobjects in a CSG list (but it is planned for a future version).
X
X% The following aren simple CSG objects using the four consistent
X% primitives:
X% 
X% union box ... difference ...
X
X\subsection{Potential CSG Problems}
X
XA consistent CSG model is one which is made
Xup of solid objects with no dangling surfaces.  In {\rayshade},
Xit is quite easy to construct inconsistent models, which will usually
Xappear incorrect in the final images.
XIn {\rayshade}, CSG is implemented by maintaining
Xthe tree structure of the CSG operations.  This tree is traversed,
Xand the operators therein applied, on a per-ray basis.
XIt is therefore difficult to verify the consistency of
Xthe model ``on the fly.''
X
XOne class of CSG problems occur when
Xsurfaces of objects being operated upon
Xcoincide.  For example, when subtracting a box from another box to make a
Xsquare cup, the result will be wrong if the tops of the two boxes
Xcoincide.  To correct this, the inner box should be made
Xslightly taller than the outer box.
XA related problem that must be
Xavoided occurs when two coincident surfaces are assigned
Xdifferent surface properties.
X
XIt may seem that the union operator is unnecessary, since
Xlisting two objects together in an aggregate results
Xin an image that appears to be the same.
XWhile the result of such a short-cut
Xmay appear the same on the exterior, the interior
Xof the resulting object will contain
Xextraneous surfaces.
XThe following examples show this quite clearly.
X
X\begin{verbatim}
X    difference
X      box -2 0 -3  2 3 3
X      union  /* change to list; note bad internal surfaces */
X        sphere 2 1 0 0
X        sphere 2 -1 0 0
X      end
X    end rotate 1 0 0 -40  rotate 0 0 1 50
X\end{verbatim}
X
XThe visual evidence of an inconsistent CSG object varies depending
Xupon the operator being used.
XWhen subtracting a consistent object from and
Xinconsistent one, the resulting object will appear to be
Xthe union of the two objects, but the shading will be incorrect.
XIt will appear to be inside-out in places, while correct
Xin other places.  The inside-out sections indicate the areas
Xwhere the problems occur.
XSuch problems are often caused by
Xpolygons with incorrectly specified
Xnormals, or by surfaces that exactly coincide (which
Xappear as partial ``Swiss cheese'' objects).
X
XThe following example illustrates an attempt to subtract a sphere from
Xa pyramid defined using an incorrectly facing triangle.  Note
Xthat the resulting image obviously points to which triangle is
Xreversed.
X
X\begin{verbatim}
X    name pyramid list
X        triangle 1 0 0  0 1 0  0 0 1
X        triangle 1 0 0  0 0 0  0 1 0
X        triangle 0 1 0  0 0 0  0 0 1
X        triangle 0 0 1  1 0 0  0 0 0  /* wrong order */
X    end
X
X    difference
X        object pyramid scale 3 3 3 rotate 0 0 1 45
X            rotate 1 0 0 -30 translate 0 -3.5 0
X        sphere 2.4 0 0 0
X    end
X\end{verbatim}
X
XBy default, cylinders and cones do not have end caps, and thus
Xare not consistent primitives.  One must usually
Xadd endcaps by listing the
Xcylinder or cone with (correctly-oriented) endcap discs in an aggregate.
X
X\section {Named Objects}
X
XA name may be associated with any primitive, aggregate, or CSG
Xobject through the use of the {\tt name}
Xkeyword:
X
X\begin{defkey}{name}{{\em objname} $<${\em Instance\/}$>$}
X	Associate {\em objname} with the given object.  The
X	specified object is not actually instantiated; it
X	is only stored under the given name.
X\end{defkey}
X
XAn object thus named may then be instantiated (with possible
Xadditional transforming and texturing) via the {\tt object} keyword:
X
X\begin{defkey}{object}{{\em objname} [$<$Transformations$>$] [$<$Textures$>$]}
X	Instantiate a copy of the object associated with {\em objname}.
X	If given, the transformations and textures are composed
X	with any already associated with
X	the object being instantiated.
X\end{defkey}
END_OF_FILE
if test 16473 -ne `wc -c <'Doc/Guide/objects.tex'`; then
    echo shar: \"'Doc/Guide/objects.tex'\" unpacked with wrong size!
fi
# end of 'Doc/Guide/objects.tex'
fi
if test -f 'etc/rsconvert/yacc.y' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'etc/rsconvert/yacc.y'\"
else
echo shar: Extracting \"'etc/rsconvert/yacc.y'\" \(14099 characters\)
sed "s/^X//" >'etc/rsconvert/yacc.y' <<'END_OF_FILE'
X/* yacc.y								   */
X/*									   */
X/* Copyright (C) 1989, 1991, Craig E. Kolb				   */
X/* All rights reserved.							   */
X/*									   */
X/* This software may be freely copied, modified, and redistributed,	   */
X/* provided that this copyright notice is preserved on all copies.	   */
X/*									   */
X/* You may not distribute this software, in whole or in part, as part of   */
X/* any commercial product without the express consent of the authors.      */
X/* 									   */
X/* There is no warranty or other guarantee of fitness of this software	   */
X/* for any purpose.  It is provided solely "as is".			   */
X/* $Id: yacc.y,v 4.0.1.3 92/02/07 11:05:21 cek Exp Locker: cek $ */
X%{
X#include <stdio.h>
X#include "libcommon/common.h"
X
X#define NEWLINE()	WriteNewline()
X/*#define NEWLINE()	printf("\n")*/
X#define LIST	0
X#define GRID	1
Xchar yyfilename[BUFSIZ];
Xextern int yylineno;
X%}
X%union {
X	char *c;
X	int i;
X	double d;
X	Color col;
X	Vector v;
X};
X%token <d> tFLOAT
X%token <c> tSTRING tHASHTHING
X%token <i> tINT
X%type <d> Fnumber sFnumber
X%type <col> sColor
X%type <v> sVector
X%type <i> sInt
X%type <c> sString
X%token tADAPTIVE tAPERTURE
X%token tBACKGROUND tBLOTCH tBOX tBUMP tCONE tCYL tDIRECTIONAL
X%token tENDDEF tEXTENDED tEYEP tFBM tFBMBUMP tFOCALDIST tFOG tFOV tGLOSS tGRID
X%token tHEIGHTFIELD tJITTERED tLIGHT tLIST tLOOKP tMARBLE tMAXDEPTH tMIST
X%token tOBJECT tOUTFILE
X%token tPLANE tPOINT tPOLY tROTATE tSAMPLES
X%token tSCALE tSCREEN tSPHERE tSTARTDEF tSUPERQ tSURFACE tRESOLUTION
X%token tTHRESH tTRANSLATE tTRANSFORM tTRIANGLE tUP tENDFILE
X%token tTEXTURE tCHECKER tWOOD tCONTRAST tCUTOFF
X%%
XItems		: /* empty */
X		| Items Item
X		;
XItem		: Eyep
X		| Lookp
X		| Up
X		| Fov
X		| Screen
X		| Aperture
X		| Focaldist
X		| Maxdepth
X		| Samples
X		| Jittered
X		| Adaptive
X		| Contrast
X		| Cutoff
X		| Background
X		| Light
X		| Primitive
X		| Child
X		| Surface
X		| Outfile
X		| List
X		| Grid
X		| Object
X		| Fog
X		| Mist
X		| Hashthing
X		| ENDFILE		/* For backward compatibility */
X		;
XHashthing	: tHASHTHING
X		{
X			WriteVerbatim("\n#");
X			WriteVerbatim($1);
X			WriteNewline();
X		};
XList		: LIST
X		{
X			NEWLINE();
X		}
X		;
XGrid		: GRID
X		{
X			NEWLINE();
X		}
X		;
XPrimitive	: Prim Textures
X		;
XPrim		: Primtype Transforms
X		;
XPrimtype	: Plane
X		| Sphere
X		| Box
X		| Triangle
X		| Cylinder
X		| Cone
X		| Superq
X		| Poly
X		| HeightField
X		;
XObject		: Objectdef Textures
X		{
X			NEWLINE();
X		}
X		;
XObjectdef	: Startdef Objdefs ENDDEF
X		;
XStartdef	: STARTDEF
X		/*
X		 * define <name>
X		 */
X		{
X			NEWLINE();
X		}
X		;
XObjdefs		: Objdefs Objdef
X		|
X		;
XObjdef		: Primitive
X		| Surface
X		| Child
X		| List
X		| Grid
X		| Object
X		;
XTextures	: Textures Texture
X		|
X		;
XTexture		: TEXTURE Texturetype Transforms
X		{
X			NEWLINE();
X		}
X		;
XTexturetype	: CHECKER String
X		{
X			NEWLINE();
X		}
X		| BLOTCH Fnumber String
X		{
X			NEWLINE();
X		}
X		| BUMP Fnumber
X		{
X			NEWLINE();
X		}
X		| MARBLE
X		{
X			NEWLINE();
X		}
X		| MARBLE String
X		{
X			NEWLINE();
X		}
X		| FBM Fnumber Fnumber Fnumber Fnumber Int Fnumber
X		{
X			NEWLINE();
X		}
X		| FBM Fnumber Fnumber Fnumber Fnumber Int Fnumber String
X		{
X			NEWLINE();
X		}
X		| FBMBUMP Fnumber Fnumber Fnumber Fnumber Int
X		{
X			NEWLINE();
X		}
X		| WOOD
X		{
X			NEWLINE();
X		}
X		| GLOSS Fnumber
X		{
X			NEWLINE();
X		}
X		;
XChild		: Childdef Textures
X		{
X			NEWLINE();
X		}
X		;
XChilddef	: OBJECT String Transforms
X		{
X			NEWLINE();
X		}
X		;
XTransforms	: Transforms Transform
X		| /* empty */
X		;
XTransform	: TRANSLATE Vector
X		{
X			NEWLINE();
X		}
X		| ROTATE Vector sFnumber
X		{
X			WriteFloat(-$3);
X			NEWLINE();
X		}
X		| SCALE Fnumber Fnumber Fnumber
X		{
X			NEWLINE();
X		}
X		| TRANSFORM sFnumber sFnumber sFnumber
X				sFnumber sFnumber sFnumber
X				sFnumber sFnumber sFnumber
X		{
X			/* have to transpose... */
X			WriteFloat($2); WriteFloat($5); WriteFloat($8);
X			WriteFloat($3); WriteFloat($6); WriteFloat($9);
X			WriteFloat($4); WriteFloat($7); WriteFloat($10);
X			NEWLINE();
X		}
X		| TRANSFORM sFnumber sFnumber sFnumber
X				sFnumber sFnumber sFnumber
X				sFnumber sFnumber sFnumber
X				sFnumber sFnumber sFnumber
X		{
X			/* transpose it */
X			WriteFloat($2); WriteFloat($5); WriteFloat($8);
X			WriteFloat($3); WriteFloat($6); WriteFloat($9);
X			WriteFloat($4); WriteFloat($7); WriteFloat($10);
X			WriteFloat($11); WriteFloat($12); WriteFloat($13);
X			NEWLINE();
X		}
X		;
XEyep		: EYEP Vector Transforms
X		{
X			NEWLINE();
X		}
X		;
XLookp		: LOOKP Vector
X		{
X			NEWLINE();
X		}
X		;
XUp		: UP Vector
X		{
X			NEWLINE();
X		}
X		;
XFov		: FOV Fnumber Fnumber
X		{
X			NEWLINE();
X		}
X		| FOV Fnumber
X		{
X			NEWLINE();
X		}
X		;
XSamples		: SAMPLES Int
X		{
X			NEWLINE();
X		}
X		;
XAdaptive	: ADAPTIVE sInt
X		{
X			WriteFloat((Float)($2+1));
X			NEWLINE();
X		}
X		;
XContrast	: CONTRAST Fnumber Fnumber Fnumber
X		{
X			NEWLINE();
X		}
X		;
XCutoff		: CUTOFF Fnumber
X		{
X			NEWLINE();
X		}
X		;
XJittered	: JITTERED
X		{
X			NEWLINE();
X		}
X		;
XScreen		: SCREEN Int Int
X		{
X			NEWLINE();
X		}
X		| RESOLUTION Int Int
X		{
X			NEWLINE();
X		}
X		;
XAperture	: APERTURE Fnumber
X		{
X			NEWLINE();
X		}
X		;
XFocaldist	: FOCALDIST Fnumber
X		{
X			NEWLINE();
X		}
X		;
XMaxdepth	: MAXDEPTH Int
X		{
X			NEWLINE();
X		}
X		;
XBackground	: BACKGROUND Color
X		{
X			NEWLINE();
X		}
X		;
XLight		: Lightdef POINT Vector
X		{
X			NEWLINE();
X		}
X		| Lightdef DIRECTIONAL Vector
X		{
X			NEWLINE();
X		}
X		| Lightdef EXTENDED sVector sFnumber
X		{
X			WriteFloat($4);
X			WriteVector(&$3);
X			NEWLINE();
X		}
X		;
XLightdef	: LIGHT Fnumber
X		{
X			NEWLINE();
X		}
X		| LIGHT Color
X		{
X			NEWLINE();
X		}
X		;
XSurface		: SURFACE String
X			sColor sColor sColor
X			sFnumber sFnumber sFnumber sFnumber
X		{
X			if ($3.r || $3.g || $3.b) {
X				WriteString("\tambient");
X				WriteColor(&$3);
X				WriteNewline();
X			}
X			if ($4.r || $4.g || $4.b) {
X				WriteString("\tdiffuse");
X				WriteColor(&$4);
X				WriteNewline();
X			}
X			if ($5.r || $5.g || $5.b) {
X				WriteString("\tspecular");
X				WriteColor(&$5);
X				WriteNewline();
X				if ($6) {
X					WriteString("\tspecpow");
X					WriteFloat($6);
X					WriteNewline();
X				}
X			}
X			if ($7) {
X				WriteString("\treflect");
X				WriteFloat($7);
X				WriteNewline();
X			}
X			if ($8) {
X				WriteString("\ttransp");
X				WriteFloat($8);
X				WriteString("index");
X				WriteFloat($9);
X				WriteNewline();
X			}
X		}
X		| SURFACE String sColor sColor sColor
X			sFnumber sFnumber sFnumber sFnumber sFnumber sFnumber
X		{
X			if ($3.r || $3.g || $3.b) {
X				WriteString("\tambient");
X				WriteColor(&$3);
X				WriteNewline();
X			}
X			if ($4.r || $4.g || $4.b) {
X				WriteString("\tdiffuse");
X				WriteColor(&$4);
X				WriteNewline();
X			}
X			if ($5.r || $5.g || $5.b) {
X				WriteString("\tspecular");
X				WriteColor(&$5);
X				WriteNewline();
X				if ($6) {
X					WriteString("\tspecpow");
X					WriteFloat($6);
X					WriteNewline();
X				}
X			}
X			if ($7) {
X				WriteString("\treflect");
X				WriteFloat($7);
X				WriteNewline();
X			}
X			if ($8) {
X				WriteString("\ttransp");
X				WriteFloat($8);
X				WriteString("index");
X				WriteFloat($9);
X				WriteNewline();
X			}
X			if ($10) {
X				WriteString("\ttranslu");
X				WriteFloat($10);
X				WriteString("1 1 1");
X				WriteFloat($11);
X				WriteNewline();
X			}
X		}
X		;
XHeightField	: HEIGHTFIELD String String
X		{
X			NEWLINE();
X		}
X		;
XPoly		: POLY String Polypoints
X		{
X			NEWLINE();
X		}
X		;
XPolypoints	: /* empty */
X		| Polypoints Polypoint
X		;
XPolypoint	: Vector
X		{
X			NEWLINE();
X		}
X		;
XCone		: CONE String sVector sVector sFnumber sFnumber
X		{
X			/* Radii now precede points */
X			WriteFloat($5);
X			WriteVector(&$3);
X			WriteFloat($6);
X			WriteVector(&$4);
X			NEWLINE();
X		}
X		;
XCylinder	: CYL sString sVector sVector sFnumber
X		{
X			Vector tmp;
X
X			WriteString($2);
X			/* Radius now goes first */
X			WriteFloat($5);
X			WriteVector(&$3);
X			WriteVector(&$4);
X			NEWLINE();
X			WriteVerbatim("#ifdef ENDCAPS\n");
X				VecSub($3, $4, &tmp);
X				WriteVerbatim("disc ");
X				WriteString($2);
X				WriteFloat($5);	/* radius */
X				WriteVector(&$3); /* pos */
X				WriteVector(&tmp);
X				WriteVerbatim("\ndisc ");
X				WriteString($2);
X				VecScale(-1, tmp, &tmp);
X				WriteFloat($5);	/* radius */
X				WriteVector(&$4); /* pos */
X				WriteVector(&tmp);
X			WriteVerbatim("\n#endif\n");
X		}
X		;
XSphere		: SPHERE String Fnumber Vector
X		{
X			NEWLINE();
X		}
X		;
XBox		: BOX String
X			sFnumber sFnumber sFnumber
X			sFnumber sFnumber sFnumber
X		{
X			/* give box corners */
X			WriteFloat($3 - $6);
X			WriteFloat($4 - $7);
X			WriteFloat($5 - $8);
X			WriteFloat($3 + $6);
X			WriteFloat($4 + $7);
X			WriteFloat($5 + $8);
X			NEWLINE();
X		}
X		;
XTriangle	: TRIANGLE String Vector Vector Vector
X		{
X			NEWLINE();
X		}
X		| TRIANGLE String Vector Vector Vector Vector Vector Vector
X		{
X			NEWLINE();
X		}
X		;
XSuperq		: SUPERQ String
X			Fnumber Fnumber Fnumber
X			Fnumber Fnumber Fnumber
X			Fnumber
X		{
X			WriteVerbatim("*/");
X			NEWLINE();
X		}
X		;
XPlane		: PLANE String sVector sVector
X		{
X			/* reverse order of point/normal */
X			WriteVector(&$4);
X			WriteVector(&$3);
X			NEWLINE();
X		}
X		;
XOutfile		: OUTFILE String
X		{
X			NEWLINE();
X		}
X		;
XMist		: MIST Color Color Fnumber Fnumber
X		{
X			NEWLINE();
X		}
X		;
XFog		: FOG sFnumber sColor
X		{
X			WriteColor(&$3);
X			WriteFloat($2); WriteFloat($2); WriteFloat($2);
X			NEWLINE();
X		}
X		;
XColor		: Fnumber Fnumber Fnumber
X		;
XsColor		: sFnumber sFnumber sFnumber
X		{
X			$$.r = $1; $$.g = $2; $$.b = $3;
X		}
X		;
XVector		: Fnumber Fnumber Fnumber
X		;
XsVector		: sFnumber sFnumber sFnumber
X		{
X			$$.x = $1; $$.y = $2; $$.z = $3;
X		}
X		;
XFnumber		: tFLOAT
X		{ WriteFloat($1); }
X		| tINT
X		{ WriteFloat((Float)$1); }
X		;
XInt		: tINT
X		{ WriteFloat((Float)$1); };
XsInt		: tINT
X		{ $$ = (int)$1; };
XsFnumber	: tFLOAT
X		| tINT
X		{ $$ = (double)$1; }
X		;
XString		: tSTRING
X		{ WriteString($1); }
XsString		: tSTRING
X		{ $$ = $1; }
XADAPTIVE	: tADAPTIVE	{ WriteString("samples"); }
XAPERTURE	: tAPERTURE	{ WriteString("aperture"); }
XBACKGROUND	: tBACKGROUND	{ WriteString("background"); }
XBLOTCH		: tBLOTCH	{ WriteString("blotch"); }
XBOX		: tBOX		{ WriteString("box"); }
XBUMP		: tBUMP		{ WriteString("bump"); }
XCONE		: tCONE		{ WriteString("cone"); }
XCYL		: tCYL		{ WriteString("cylinder"); }
XDIRECTIONAL	: tDIRECTIONAL	{ WriteString("directional"); }
XENDDEF		: tENDDEF	{ EndDefine(); }
XEXTENDED	: tEXTENDED	{ WriteString("extended"); }
XEYEP		: tEYEP		{ WriteString("eyep"); }
XFBM		: tFBM		{ WriteString("fbm"); }
XFBMBUMP		: tFBMBUMP	{ WriteString("fbmbump"); }
XFOCALDIST	: tFOCALDIST	{ WriteString("focaldist"); }
XFOG		: tFOG		{ WriteString("atmosphere fog"); }
XFOV		: tFOV		{ WriteString("fov"); }
XGLOSS		: tGLOSS	{ WriteString("gloss"); }
XGRID		: tGRID	tINT tINT tINT	{ SetTypeGrid($2,$3,$4); }
XHEIGHTFIELD	: tHEIGHTFIELD	{ WriteString("heightfield"); }
XJITTERED	: tJITTERED	{ WriteString("jittered"); }
XLIGHT		: tLIGHT	{ WriteString("light"); }
XLIST		: tLIST		{ SetTypeList(); }
XLOOKP		: tLOOKP	{ WriteString("lookp"); }
XMARBLE		: tMARBLE	{ WriteString("marble"); }
XMAXDEPTH	: tMAXDEPTH	{ WriteString("maxdepth"); }
XMIST		: tMIST		{ WriteString("atmosphere mist"); }
XOBJECT		: tOBJECT	{ WriteString("object"); }
XOUTFILE		: tOUTFILE	{ WriteString("outfile"); }
XPLANE		: tPLANE	{ WriteString("plane"); }
XPOINT		: tPOINT	{ WriteString("point"); }
XPOLY		: tPOLY		{ WriteString("poly"); }
XROTATE		: tROTATE	{ WriteString("rotate"); }
XSAMPLES		: tSAMPLES	{ WriteString("samples"); }
XSCALE		: tSCALE	{ WriteString("scale"); }
XSCREEN		: tSCREEN	{ WriteString("screen"); }
XSPHERE		: tSPHERE	{ WriteString("sphere"); }
XSTARTDEF	: tSTARTDEF tSTRING	{ StartDefine($2); }
XSUPERQ		: tSUPERQ	{ WriteString("/* superq"); }
XSURFACE		: tSURFACE	{ WriteString("surface"); }
XRESOLUTION	: tRESOLUTION	{ WriteString("resolution"); }
XTRANSLATE	: tTRANSLATE	{ WriteString("translate"); }
XTRANSFORM	: tTRANSFORM	{ WriteString("transform"); }
XTRIANGLE	: tTRIANGLE	{ WriteString("triangle"); }
XUP		: tUP		{ WriteString("up"); }
XENDFILE		: tENDFILE	{ /* Don't do a thing. */ }
XTEXTURE		: tTEXTURE	{ WriteString("texture"); }
XCHECKER		: tCHECKER	{ WriteString("checker"); }
XWOOD		: tWOOD		{ WriteString("wood"); }
XCONTRAST	: tCONTRAST	{ WriteString("contrast"); }
XCUTOFF		: tCUTOFF	{ WriteString("cutoff"); }
X%%
X
X#define STARTBUFSIZ	(1 << 18)
X
Xtypedef struct db {
X	int bufsiz, curpos;
X	int type, x, y, z;
X	char *name;
X	struct db *next;
X	char *memory;
X} DefBuf;
X
XDefBuf *defbuf = NULL;
X
Xyyerror(s)
X{
X	fprintf(stderr,"rsconvert: %s, line %d: %s \n",
X			yyfilename[0] ? yyfilename : "stdin",
X			yylineno, s);
X}
X
XStartDefine(name)
Xchar *name;
X{
X	DefBuf *new;
X	/*
X	 * Push new buffer onto define stack.
X	 */	
X	new = (DefBuf *)Malloc(sizeof(DefBuf));
X	new->bufsiz = STARTBUFSIZ;
X	new->type = LIST;
X	new->curpos = 0;
X	new->name = name;
X	new->memory = (char *)Calloc(new->bufsiz, sizeof(char));
X	new->next = defbuf;
X	defbuf = new;
X}
X
XEndDefine()
X{
X	char buf[BUFSIZ];
X	DefBuf *old;
X
X	old = defbuf;
X	defbuf = defbuf->next;
X	if (old->type == LIST) {
X		sprintf(buf, "name %s list", old->name);
X	} else {
X		sprintf(buf, "name %s grid %d %d %d", old->name,
X				old->x, old->y, old->z);
X	}
X	/*
X	 * dump goodies
X	 */
X	WriteVerbatim(buf);
X	WriteVerbatim(old->memory);
X	WriteVerbatim("end");
X	free((voidstar)old->memory);
X	free((voidstar)old);
X	
X}
X
XWriteString(str)
Xchar *str;
X{
X	WriteVerbatim(str);
X	WriteChar(' ');
X}
X
XWriteVerbatim(str)
Xchar *str;
X{
X	int n;
X
X	for (n = strlen(str); n; n--)
X		WriteChar(*(str++));
X}
X
XWriteChar(c)
Xchar c;
X{
X	if (defbuf) {
X		if (defbuf->curpos == defbuf->bufsiz -1) {
X			defbuf->bufsiz *= 2;
X			defbuf->memory = (char *)realloc(defbuf->memory,
X				defbuf->bufsiz * sizeof(char));
X			if (defbuf->memory == (char *)NULL) {
X				fprintf(stderr,"realloc failed!\n");
X				exit(-1);
X			}
X		}
X		defbuf->memory[defbuf->curpos++] = c;
X		defbuf->memory[defbuf->curpos] = (char)NULL;
X	} else
X		putchar(c);
X}
X
XWriteVector(v)
XVector *v;
X{
X	WriteFloat(v->x);
X	WriteFloat(v->y);
X	WriteFloat(v->z);
X}
X
XWriteFloat(x)
XFloat x;
X{
X	char buf[BUFSIZ];
X	sprintf(buf, "%g ", x);
X	WriteVerbatim(buf);
X}
X
XWriteNewline()
X{
X	WriteVerbatim("\n");
X}
X
XSetTypeList()
X{
X	if (defbuf)
X		defbuf->type = LIST;
X	/* else set world type */
X}
X
XSetTypeGrid(x,y,z)
Xint x, y, z;
X{
X	if (defbuf) {
X		defbuf->type = GRID;
X		defbuf->x = x; defbuf->y = y; defbuf->z = z;
X	} /* else set world type */
X}
X
XWriteColor(c)
XColor *c;
X{
X	WriteFloat(c->r);
X	WriteFloat(c->g);
X	WriteFloat(c->b);
X}
END_OF_FILE
if test 14099 -ne `wc -c <'etc/rsconvert/yacc.y'`; then
    echo shar: \"'etc/rsconvert/yacc.y'\" unpacked with wrong size!
fi
chmod +x 'etc/rsconvert/yacc.y'
# end of 'etc/rsconvert/yacc.y'
fi
if test -f 'libray/libobj/hf.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'libray/libobj/hf.c'\"
else
echo shar: Extracting \"'libray/libobj/hf.c'\" \(17433 characters\)
sed "s/^X//" >'libray/libobj/hf.c' <<'END_OF_FILE'
X/*
X * hf.c
X *
X * Copyright (C) 1989, 1991, Craig E. Kolb
X * All rights reserved.
X *
X * This software may be freely copied, modified, and redistributed
X * provided that this copyright notice is preserved on all copies.
X *
X * You may not distribute this software, in whole or in part, as part of
X * any commercial product without the express consent of the authors.
X *
X * There is no warranty or other guarantee of fitness of this software
X * for any purpose.  It is provided solely "as is".
X *
X * $Id: hf.c,v 4.0.1.1 91/09/29 15:44:53 cek Exp Locker: cek $
X *
X * $Log:	hf.c,v $
X * Revision 4.0.1.1  91/09/29  15:44:53  cek
X * patch1: Error messages missing newline.
X * 
X * Revision 4.0  91/07/17  14:38:15  kolb
X * Initial version.
X * 
X */
X#include "geom.h"
X#include "hf.h"
X
Xstatic Methods *iHfMethods = NULL;
Xstatic char hfName[] = "heighfield";
X
Xstatic void integrate_grid(), QueueTri();
Xstatic int DDA2D(), CheckCell();
Xstatic Float intHftri();
Xstatic float minalt(), maxalt();
X
Xtypedef struct {
X	int stepX, stepY;
X	Float tDX, tDY;
X	float minz, maxz;
X	int outX, outY;
X	Vector cp, pDX, pDY;
X} Trav2D;
X
XhfTri *CreateHfTriangle(), *GetQueuedTri();
X
Xunsigned long HFTests, HFHits;
X
XHf *
XHfCreate(filename)
Xchar *filename;
X{
X	Hf *hf;
X	FILE *fp;
X	float val, *maxptr, *minptr;
X	int i, j;
X
X	fp = fopen(filename, "r");
X	if (fp == (FILE *)NULL) {
X		RLerror(RL_ABORT, "Cannot open heightfield file \"%s\".\n",
X				filename);
X		return (Hf *)NULL;
X	}
X
X	hf = (Hf *)Malloc(sizeof(Hf));
X	/*
X	 * Make the following an option someday.
X	 */
X	hf->BestSize = BESTSIZE;
X	/*
X	 * Store the inverse for faster computation.
X	 */
X	hf->iBestSize = 1. / (float)hf->BestSize;
X	/*
X	 * Get HF size.
X	 */
X	if (fread((char *)&hf->size, sizeof(int), 1, fp) == 0) {
X		RLerror(RL_ABORT, "Cannot read height field size.\n");
X		return (Hf *)NULL;
X	}
X		
X	hf->data = (float **)share_malloc(hf->size * sizeof(float *));
X	for (i = 0; i < hf->size; i++) {
X		hf->data[i] = (float *)share_malloc(hf->size * sizeof(float));
X		/*
X		 * Read in row of HF data.
X		 */
X		if (fread((char *)hf->data[i],sizeof(float),hf->size,fp)
X		    != hf->size) {
X			RLerror(RL_ABORT, "Not enough heightfield data.\n");
X			return (Hf *)NULL;
X		}
X		for (j = 0; j < hf->size; j++) {
X			val = hf->data[i][j];
X			if (val <= HF_UNSET) {
X				hf->data[i][j] = HF_UNSET;
X				/*
X				 * Don't include the point in min/max
X				 * calculations.
X				 */
X				continue;
X			}
X			if (val > hf->maxz)
X				hf->maxz = val;
X			if (val < hf->minz)
X				hf->minz = val;
X		}
X	}
X	(void)fclose(fp);
X	/*
X	 * Allocate levels of grid.  hf->levels = log base BestSize of hf->size
X	 */
X	for (i = hf->size, hf->levels = 0; i > hf->BestSize; i /= hf->BestSize,
X				hf->levels++)
X			;
X	hf->levels++;
X	hf->qsize = CACHESIZE;
X	hf->q = (hfTri **)Calloc((unsigned)hf->qsize, sizeof(hfTri *));
X	hf->qtail = 0;
X
X	hf->lsize = (int *)share_malloc(hf->levels * sizeof(int));
X	hf->spacing = (float *)share_malloc(hf->levels * sizeof(float));
X	hf->boundsmax = (float ***)share_malloc(hf->levels * sizeof(float **));
X	hf->boundsmin = (float ***)share_malloc(hf->levels * sizeof(float **));
X
X	hf->spacing[0] = hf->size -1;
X	hf->lsize[0] = (int)hf->spacing[0];
X	hf->boundsmax[0] = (float **)share_malloc(hf->lsize[0]*sizeof(float *));
X	hf->boundsmin[0] = (float **)share_malloc(hf->lsize[0]*sizeof(float *));
X	/*
X	 * Compute initial bounding boxes
X	 */
X	for (i = 0; i < hf->lsize[0]; i++) {
X		hf->boundsmax[0][i]=(float *)share_malloc(hf->lsize[0]*sizeof(float));
X		hf->boundsmin[0][i]=(float *)share_malloc(hf->lsize[0]*sizeof(float));
X		maxptr = hf->boundsmax[0][i];
X		minptr = hf->boundsmin[0][i];
X		for (j = 0; j < hf->lsize[0]; j++) {
X			*maxptr++ = maxalt(i, j, hf->data) + EPSILON;
X			*minptr++ = minalt(i, j, hf->data) - EPSILON;
X		}
X	}
X
X	for (i = 1; i < hf->levels; i++) {
X		hf->spacing[i] = hf->spacing[i-1] * hf->iBestSize;
X		hf->lsize[i] = (int)hf->spacing[i];
X		if ((Float)hf->lsize[i] != hf->spacing[i])
X			hf->lsize[i]++;
X		hf->boundsmax[i]=(float **)share_malloc(hf->lsize[i]*sizeof(float *));
X		hf->boundsmin[i]=(float **)share_malloc(hf->lsize[i]*sizeof(float *));
X		for (j = 0; j < hf->lsize[i]; j++) {
X			hf->boundsmax[i][j] = (float *)share_malloc(hf->lsize[i] *
X							sizeof(float));
X			hf->boundsmin[i][j] = (float *)share_malloc(hf->lsize[i] *
X							sizeof(float));
X		}
X		integrate_grid(hf, i);
X	}
X
X	hf->boundbox[LOW][X] = hf->boundbox[LOW][Y] = 0;
X	hf->boundbox[HIGH][X] = hf->boundbox[HIGH][Y] = 1;
X	hf->boundbox[LOW][Z] = hf->minz;
X	hf->boundbox[HIGH][Z] = hf->maxz;
X
X	return hf;
X}
X
XMethods *
XHfMethods()
X{
X	if (iHfMethods == (Methods *)NULL) {
X		iHfMethods = MethodsCreate();
X		iHfMethods->create = (GeomCreateFunc *)HfCreate;
X		iHfMethods->methods = HfMethods;
X		iHfMethods->name = HfName;
X		iHfMethods->intersect = HfIntersect;
X		iHfMethods->normal = HfNormal;
X		iHfMethods->uv = HfUV;
X		iHfMethods->bounds = HfBounds;
X		iHfMethods->stats = HfStats;
X		iHfMethods->checkbounds = TRUE;
X		iHfMethods->closed = FALSE;
X	}
X	return iHfMethods;
X}
X
X/*
X * Intersect ray with height field.
X */
Xint
XHfIntersect(hf, ray, mindist, maxdist)
XHf *hf;
XRay *ray;
XFloat mindist, *maxdist;
X{
X	Vector hitpos;
X	Float offset;
X	Trav2D trav;
X
X	HFTests++;
X
X	/*
X	 * Find where we hit the hf cube.
X	 */
X	VecAddScaled(ray->pos, mindist, ray->dir, &hitpos);
X	if (OutOfBounds(&hitpos, hf->boundbox)) {
X		offset = *maxdist;
X		if (!BoundsIntersect(ray, hf->boundbox, mindist, &offset))
X			return FALSE;
X		hitpos.x = ray->pos.x + ray->dir.x * offset;
X		hitpos.y = ray->pos.y + ray->dir.y * offset;
X		hitpos.z = ray->pos.z + ray->dir.z * offset;
X	} else
X		hitpos = ray->pos;
X	/*
X	 * Find out in which cell "hitpoint" is.
X	 */
X	if (equal(hitpos.x, 1.))
X		hitpos.x -= EPSILON;
X	if (equal(hitpos.y, 1.))
X		hitpos.y -= EPSILON;
X
X	if (ray->dir.x < 0.) {
X		trav.stepX = trav.outX = -1;
X		trav.tDX = -1. / (ray->dir.x * hf->spacing[hf->levels -1]);
X	} else if (ray->dir.x > 0.) {
X		trav.stepX = 1;
X		trav.outX = hf->lsize[hf->levels -1];
X		/*
X		 * (1./size) / ray
X		 */
X		trav.tDX = 1. / (ray->dir.x * hf->spacing[hf->levels -1]);
X	}
X
X	if (ray->dir.y < 0.) {
X		trav.stepY = trav.outY = -1;
X		trav.tDY = -1. / (ray->dir.y * hf->spacing[hf->levels -1]);
X	} else if (ray->dir.y > 0.) {
X		trav.stepY = 1;
X		trav.outY = hf->lsize[hf->levels -1];
X		trav.tDY = 1. / (ray->dir.y * hf->spacing[hf->levels -1]);
X	}
X
X	trav.pDX.x = ray->dir.x * trav.tDX;
X	trav.pDX.y = ray->dir.y * trav.tDX;
X	trav.pDX.z = ray->dir.z * trav.tDX;
X	trav.pDY.x = ray->dir.x * trav.tDY;
X	trav.pDY.y = ray->dir.y * trav.tDY;
X	trav.pDY.z = ray->dir.z * trav.tDY;
X
X	trav.cp = hitpos;
X	trav.minz = hf->minz;
X	trav.maxz = hf->maxz;
X	if (DDA2D(hf, &ray->pos, &ray->dir, hf->levels -1, &trav, maxdist)) {
X		HFHits++;
X		return TRUE;
X	}
X	return FALSE;
X}
X
X/*
X * Traverse the grid using a modified DDA algorithm.  If the extent of
X * the ray over a cell intersects the bounding volume defined by the
X * four corners of the cell, either recurse or perform ray/surface
X * intersection test.
X */
Xstatic int
XDDA2D(hf, pos, ray, level, trav, maxdist)
XHf *hf;
XVector *pos, *ray;
Xint level;
XTrav2D *trav;
XFloat *maxdist;
X{
X	int x, y, size, posZ;
X	float **boundsmin, **boundsmax, spacing;
X	Float tX, tY;
X	Trav2D newtrav;
X	Vector nxp, nyp;
X
X	size = hf->lsize[level];
X	spacing = hf->spacing[level];
X
X	posZ = (ray->z > 0.);
X
X	x = trav->cp.x * hf->spacing[level];
X	if (x == size)
X		x--;
X	y = trav->cp.y * hf->spacing[level];
X	if (y == size)
X		y--;
X	boundsmax = hf->boundsmax[level];
X	boundsmin = hf->boundsmin[level];
X
X	if (trav->outX > size) trav->outX = size;
X	if (trav->outY > size) trav->outY = size;
X	if (trav->outX < 0) trav->outX = -1;
X	if (trav->outY < 0) trav->outY = -1;
X
X	if (ray->x < 0.) {
X		tX = (x /spacing - trav->cp.x) / ray->x;
X	} else if (ray->x > 0.)
X		tX = ((x+1)/spacing - trav->cp.x) / ray->x;
X	else
X		tX = FAR_AWAY;
X	if (ray->y < 0.) {
X		tY = (y /spacing - trav->cp.y) / ray->y;
X	} else if (ray->y > 0.)
X		tY = ((y+1)/spacing - trav->cp.y) / ray->y;
X	else
X		tY = FAR_AWAY;
X
X	nxp.x = trav->cp.x + tX * ray->x;
X	nxp.y = trav->cp.y + tX * ray->y;
X	nxp.z = trav->cp.z + tX * ray->z;
X
X	nyp.x = trav->cp.x + tY * ray->x;
X	nyp.y = trav->cp.y + tY * ray->y;
X	nyp.z = trav->cp.z + tY * ray->z;
X
X	do {
X		if (tX < tY) {
X			if ((posZ && trav->cp.z <= boundsmax[y][x] &&
X			     nxp.z >= boundsmin[y][x]) ||
X			    (!posZ && trav->cp.z >= boundsmin[y][x] &&
X			     nxp.z <= boundsmax[y][x])) {
X				if (level) {
X					/*
X					 * Recurse -- compute constants
X					 * needed for next level.
X					 * Nicely enough, this just
X					 * involves a few multiplications.
X					 */
X					newtrav = *trav;
X					newtrav.tDX *= hf->iBestSize;
X					newtrav.tDY *= hf->iBestSize;
X					newtrav.maxz = boundsmax[y][x];
X					newtrav.minz = boundsmin[y][x];
X					if (ray->x < 0.)
X						newtrav.outX=hf->BestSize*x-1;
X					else
X						newtrav.outX=hf->BestSize*(x+1);
X					if (ray->y < 0.)
X						newtrav.outY=hf->BestSize*y-1;
X					else
X						newtrav.outY=hf->BestSize*(y+1);
X					newtrav.pDX.x *= hf->iBestSize;
X					newtrav.pDX.y *= hf->iBestSize;
X					newtrav.pDX.z *= hf->iBestSize;
X					newtrav.pDY.x *= hf->iBestSize;
X					newtrav.pDY.y *= hf->iBestSize;
X					newtrav.pDY.z *= hf->iBestSize;
X					if (DDA2D(hf,pos,ray,level-1,
X						&newtrav, maxdist))
X						return TRUE;
X				} else if (CheckCell(x,y,hf,ray,pos,maxdist))
X					return TRUE;
X			}
X			x += trav->stepX;		/* Move in X */
X			if (*maxdist < tX || x == trav->outX)
X				/* If outside, quit */
X				return FALSE;
X			tX += trav->tDX;	/* Update position on ray */
X			trav->cp = nxp;		/* cur pos gets next pos */
X			nxp.x += trav->pDX.x;	/* Compute next pos */
X			nxp.y += trav->pDX.y;
X			nxp.z += trav->pDX.z;
X		} else {
X			if ((posZ && trav->cp.z <= boundsmax[y][x] &&
X			     nyp.z >= boundsmin[y][x]) ||
X			    (!posZ && trav->cp.z >= boundsmin[y][x] &&
X			     nyp.z <= boundsmax[y][x])) {
X				if (level) {
X					/* Recurse */
X					newtrav = *trav;
X					newtrav.tDX *= hf->iBestSize;
X					newtrav.tDY *= hf->iBestSize;
X					newtrav.maxz = boundsmax[y][x];
X					newtrav.minz = boundsmin[y][x];
X					if (ray->x < 0.)
X						newtrav.outX=hf->BestSize*x-1;
X					else
X						newtrav.outX=hf->BestSize*(x+1);
X					if (ray->y < 0.)
X						newtrav.outY=hf->BestSize*y-1;
X					else
X						newtrav.outY=hf->BestSize*(y+1);
X					newtrav.pDX.x *= hf->iBestSize;
X					newtrav.pDX.y *= hf->iBestSize;
X					newtrav.pDX.z *= hf->iBestSize;
X					newtrav.pDY.x *= hf->iBestSize;
X					newtrav.pDY.y *= hf->iBestSize;
X					newtrav.pDY.z *= hf->iBestSize;
X					if (DDA2D(hf,pos,ray,level-1,
X							&newtrav, maxdist))
X						return TRUE;
X				} else if (CheckCell(x,y,hf,ray,pos,maxdist))
X					return TRUE;
X			}
X			y += trav->stepY;
X			if (*maxdist < tY || y == trav->outY)
X				return FALSE;
X			tY += trav->tDY;
X			trav->cp = nyp;
X			nyp.x += trav->pDY.x;
X			nyp.y += trav->pDY.y;
X			nyp.z += trav->pDY.z;
X		}
X	} while ((trav->cp.x <= 1. && trav->cp.y <= 1.) &&
X		 ((posZ && trav->cp.z <= trav->maxz) ||
X		 (!posZ && trav->cp.z >= trav->minz)));
X
X		/*
X		 * while ((we're inside the horizontal bounding box)
X		 *		(usually caught by outX & outY, but
X		 *		 it's possible to go "too far" due to
X		 *		 the fact that our levels of grids do
X		 *		 not "nest" exactly if gridsize%BestSize != 0)
X		 *	  and
X		 *	  ((if ray->z is positive and we haven't gone through
X		 *	   the upper bounding plane) or
X		 *	  (if ray->z is negative and we haven't gone through
X		 *	   the lower bounding plane)));
X		 */
X
X	return FALSE;
X}
X
X/*
X * Check for ray/cell intersection
X */
Xstatic int
XCheckCell(x, y, hf, ray, pos, maxdist)
Xint x, y;
XHf *hf;
XVector *ray, *pos;
XFloat *maxdist;
X{
X	hfTri *tri1, *tri2;
X	Float d1, d2;
X
X	d1 = d2 = FAR_AWAY;
X
X	if (tri1 = CreateHfTriangle(hf, x, y, x+1, y, x, y+1, TRI1))
X		d1 = intHftri(ray, pos, tri1);
X	if (tri2 = CreateHfTriangle(hf, x+1, y, x+1, y+1, x, y+1, TRI2))
X		d2 = intHftri(ray, pos, tri2);
X
X	if (d1 == FAR_AWAY && d2 == FAR_AWAY)
X		return FALSE;
X
X	if (d1 < d2) {
X		if (d1 < *maxdist) {
X			hf->hittri = *tri1;
X			*maxdist = d1;
X			return TRUE;
X		}
X		return FALSE;
X	}
X
X	if (d2 < *maxdist) {
X		hf->hittri = *tri2;
X		*maxdist = d2;
X		return TRUE;
X	}
X	return FALSE;
X}
X
Xstatic hfTri *
XCreateHfTriangle(hf, x1, y1, x2, y2, x3, y3, which)
XHf *hf;
Xint x1, y1, x2, y2, x3, y3, which;
X{
X	hfTri *tri;
X	Float xid, yid;
X	Vector tmp1, tmp2;
X
X	/*
X	 * Don't use triangles with "unset" vertices.
X	 */
X	if (hf->data[y1][x1] == HF_UNSET ||
X	    hf->data[y2][x2] == HF_UNSET ||
X	    hf->data[y3][x3] == HF_UNSET)
X		return (hfTri *)0;
X
X	xid = (Float)x1 / (Float)(hf->size -1);
X	yid = (Float)y1 / (Float)(hf->size -1);
X
X	if ((tri = GetQueuedTri(hf, xid, yid, which)) != (hfTri *)0)
X		return tri;
X
X	tri = (hfTri *)Malloc(sizeof(hfTri));
X
X	tri->type = which;
X	tri->v1.x = xid;
X	tri->v1.y = yid;
X	tri->v1.z = hf->data[y1][x1];
X	tri->v2.x = (Float)x2 / (Float)(hf->size-1);
X	tri->v2.y = (Float)y2 / (Float)(hf->size-1);
X	tri->v2.z = hf->data[y2][x2];
X	tri->v3.x = (Float)x3 / (Float)(hf->size-1);
X	tri->v3.y = (Float)y3 / (Float)(hf->size-1);
X	tri->v3.z = hf->data[y3][x3];
X
X	tmp1.x = tri->v2.x - tri->v1.x;
X	tmp1.y = tri->v2.y - tri->v1.y;
X	tmp1.z = tri->v2.z - tri->v1.z;
X	tmp2.x = tri->v3.x - tri->v1.x;
X	tmp2.y = tri->v3.y - tri->v1.y;
X	tmp2.z = tri->v3.z - tri->v1.z;
X
X	(void)VecNormCross(&tmp1, &tmp2, &tri->norm);
X
X	tri->d = -dotp(&tri->v1, &tri->norm);
X
X	QueueTri(hf, tri);
X	return tri;
X}
X
X/*
X * Intersect ray with right isoscoles triangle, the hypotenuse of which
X * has slope of -1.
X */
Xstatic Float
XintHftri(ray, pos, tri)
XhfTri *tri;
XVector *pos, *ray;
X{
X	Float u, v, dist, xpos, ypos;
X
X	u = dotp(&tri->norm, pos) + tri->d;
X	v = dotp(&tri->norm, ray);
X
X	if ((u <= 0. || v > -EPSILON) && (u >= 0. && v < EPSILON))
X		return FAR_AWAY;
X
X	dist = -u / v;
X
X	if (dist < EPSILON)
X		return FAR_AWAY;
X
X	xpos = pos->x + dist*ray->x;
X	ypos = pos->y + dist*ray->y;
X
X	if (tri->type == TRI1 && xpos >= tri->v1.x && ypos >= tri->v1.y &&
X		xpos + ypos <= tri->v2.x + tri->v2.y)
X		return dist;
X	if (tri->type == TRI2 && xpos <= tri->v2.x && ypos <= tri->v2.y &&
X		xpos + ypos >= tri->v1.x + tri->v1.y)
X		return dist;
X	return FAR_AWAY;
X}
X
X/*
X * Compute normal to height field.
X */
X/*ARGSUSED*/
Xint
XHfNormal(hf, pos, nrm, gnrm)
XHf *hf;
XVector *pos, *nrm, *gnrm;
X{
X	*gnrm = *nrm = hf->hittri.norm;
X	return FALSE;
X}
X
X/*ARGSUSED*/
Xvoid
XHfUV(hf, pos, norm, uv, dpdu, dpdv)
XHf *hf;
XVector *pos, *norm, *dpdu, *dpdv;
XVec2d *uv;
X{
X	uv->u = pos->x;
X	uv->v = pos->y;
X	if (dpdu) {
X		dpdu->x = 1.;
X		dpdu->y = dpdv->z = 0.;
X		dpdv->x = dpdv->z = 0.;
X		dpdv->y = 1.;
X	}
X}
X
X/*
X * Compute heightfield bounding box.
X */
Xvoid
XHfBounds(hf, bounds)
XHf *hf;
XFloat bounds[2][3];
X{
X	/*
X	 * By default, height fields are centered at (0.5, 0.5, 0.)
X	 */
X	bounds[LOW][X] = bounds[LOW][Y] = 0;
X	bounds[HIGH][X] = bounds[HIGH][Y] = 1;
X	bounds[LOW][Z] = hf->minz;
X	bounds[HIGH][Z] = hf->maxz;
X}
X
X/*
X * Build min/max altitude value arrays for the given grid level.
X */
Xstatic void
Xintegrate_grid(hf, level)
XHf *hf;
Xint level;
X{
X	int i, j, k, l, ii, ji;
X	float max_alt, min_alt;
X	float **maxinto, **mininto, **frommax, **frommin, *minptr, *maxptr;
X	int insize, fromsize, fact;
X
X	maxinto = hf->boundsmax[level];
X	mininto = hf->boundsmin[level];
X	insize = hf->lsize[level];
X	frommax = hf->boundsmax[level-1];
X	frommin = hf->boundsmin[level-1];
X	fact = hf->BestSize;
X	fromsize = hf->lsize[level-1];
X
X	ii = 0;
X
X	for (i = 0; i < insize; i++) {
X		ji = 0;
X		for (j = 0; j < insize; j++) {
X			max_alt = HF_UNSET;
X			min_alt = -HF_UNSET;
X			for (k = 0; k <= fact; k++) {
X				if (ii+k >= fromsize)
X					continue;
X				maxptr = &frommax[ii+k][ji];
X				minptr = &frommin[ii+k][ji];
X				for (l = 0; l <= fact; l++,maxptr++,minptr++) {
X					if (ji+l >= fromsize)
X						continue;
X					if (*maxptr > max_alt)
X						max_alt = *maxptr;
X					if (*minptr < min_alt)
X						min_alt = *minptr;
X				}
X			}
X			maxinto[i][j] = max_alt + EPSILON;
X			mininto[i][j] = min_alt - EPSILON;
X			ji += fact;
X		}
X		ii += fact;
X	}
X}
X
X/*
X * Place the given triangle in the triangle cache.
X */
Xstatic void
XQueueTri(hf, tri)
XHf *hf;
XhfTri *tri;
X{
X	if (hf->q[hf->qtail])		/* Free old triangle data */
X		free((voidstar)hf->q[hf->qtail]);
X	hf->q[hf->qtail] = tri;		/* Put on tail */
X	hf->qtail = (hf->qtail + 1) % hf->qsize;	/* Increment tail */
X}
X
X/*
X * Search list of cached trianges to see if this triangle has been
X * cached.  If so, return a pointer to it.  If not, return null pointer.
X */
Xstatic hfTri *
XGetQueuedTri(hf, x, y, flag)
XHf *hf;
XFloat x, y;
Xint flag;
X{
X	register int i;
X	register hfTri **tmp;
X
X	for (i = 0, tmp = hf->q; i < hf->qsize; i++, tmp++) {
X		if (*tmp && (*tmp)->v1.x == x && (*tmp)->v1.y == y &&
X		    (*tmp)->type == flag)
X			return *tmp;	/* vertices & flag match, return it */
X	}
X
X	return (hfTri *)0;
X}
X
X/*
X * Return maximum height of cell indexed by y,x.  This could be done
X * as a macro, but many C compliers will choke on it.
X */
Xstatic float
Xminalt(y,x,data)
Xint x, y;
Xfloat **data;
X{
X	float  min_alt;
X
X	min_alt = min(data[y][x], data[y+1][x]);
X	min_alt = min(min_alt, data[y][x+1]);
X	min_alt = min(min_alt, data[y+1][x+1]);
X	return min_alt;
X}
X
X/*
X * Return maximum cell height, as above.
X */
Xstatic float
Xmaxalt(y,x,data)
Xint x, y;
Xfloat **data;
X{
X	float  max_alt;
X
X	max_alt = max(data[y][x], data[y+1][x]);
X	max_alt = max(max_alt, data[y][x+1]);
X	max_alt = max(max_alt, data[y+1][x+1]);
X	return max_alt;
X}
X
Xchar *
XHfName()
X{
X	return hfName;
X}
X
Xvoid
XHfStats(tests, hits)
Xunsigned long *tests, *hits;
X{
X	*tests = HFTests;
X	*hits = HFHits;
X}
X
Xvoid
XHfMethodRegister(meth)
XUserMethodType meth;
X{
X	if (iHfMethods)
X		iHfMethods->user = meth;
X}
END_OF_FILE
if test 17433 -ne `wc -c <'libray/libobj/hf.c'`; then
    echo shar: \"'libray/libobj/hf.c'\" unpacked with wrong size!
fi
# end of 'libray/libobj/hf.c'
fi
echo shar: End of archive 16 \(of 19\).
cp /dev/null ark16isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ; do
    if test ! -f ark${I}isdone ; then
	MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 19 archives.
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0