#ifndef lint
static char *sccsid = "@(#)extent.c	1.2 (Steve Hill) 3/9/90";
#endif

/* extent.c
 *
 * Routines to determine if given points lie within or without
 * a solid.  The filter routine applies this to all entries in
 * a hit_list_t.
 */


#include <stdio.h>

#include "basetype.h"
#include "cartesian.h"
#include "error.h"
#include "matrix.h"
#include "point.h"
#include "vector.h"
#include "indexlist.h"
#include "ray.h"
#include "quadric.h"
#include "colour.h"
#include "surface.h"
#include "bitmap.h"
#include "pattern.h"
#include "solid.h"
#include "bbox.h"
#include "list.h"
#include "hitlist.h"
#include "extent.h"


/* QuadricInside
 *
 * Determine is the point lies within the quadric.  
 *
 * We instantiate the quadric, and test its value.
 */

bool_t
QuadricInside(point, quadric)
point_t		*point;
quadric_t	*quadric;
{
	return(QuadricInstantiate(quadric, point->x, point->y, point->z)
	       <= REAL_ZERO);
}


/* QuadricOutside
 *
 * Does a point lie outside a quadric?  Simply the negation of
 * QuadricInside.
 */

bool_t
QuadricOutside(point, quadric)
point_t		*point;
quadric_t	*quadric;
{
	return(!QuadricInside(point, quadric));
}


/* SolidInside
 *
 * Is the point inside the solid?
 *
 * A point is within a join if it is within either of the sub-solids.
 * A point is within a meer only if it is within both of the sub-solids.
 * A point is within an atom if it is within the quadric.
 */

bool_t
SolidInside(point, solid)
point_t	*point;
solid_t	*solid;
{
	solid_body_t	*body;

	body = &solid->body;

	switch (solid->type)
	{
	case JOIN:
		return(SolidInside(point, body->join.left) ||
		       SolidInside(point, body->join.right));

	case MEET:
		return(SolidInside(point, body->join.left) &&
		       SolidInside(point, body->join.right));

	case ATOM:
		return(QuadricInside(point, body->atom.quadric));

	default:
		FatalError(__FILE__, __LINE__, "SolidInside: Bad solid");
	}
	/*NOTREACHED*/
}


/* SolidOutside
 *
 * Test if a point is outside a solid.  Simply negate SolidInside.
 */

bool_t
SolidOutside(point, solid)
point_t	*point;
solid_t	*solid;
{
	return(!SolidInside(point, solid));
}


/* HitListFilter
 *
 * This is a generic function for filtering a hitlist with respect to a
 * given solid.
 *
 * Each entry in the hitlist is tested by the predicate function (which
 * is passed a solid as its argument).  If the predicate returns true,
 * then the entry is retained.  Otherwise it is discarded (and freed).
 */

hit_list_t *
HitListFilter(hit_list, solid, predicate)
hit_list_t	*hit_list;
solid_t		*solid;
bool_t		(*predicate)();
{
	hit_list_t	*ptr, **ptrptr, *tmp;

	ptrptr = &hit_list;
	ptr    = *ptrptr;

	while (ptr != HitListNull)
	{
		hit_info_t	*info;

		info = ptr->elem;

		if ((*predicate)(info->point, solid))
			ptrptr = &ptr->ptr;
		else
		{
			tmp = ptr->ptr;
			ptr->ptr = HitListNull;
			HitListFree(ptr);
			*ptrptr = tmp;
		}

		ptr = *ptrptr;
	}
	return(hit_list);
}


/* FilterInside
 *
 * Instance of HitListFilter.  Discards all entries in a hitlist that
 * are not within the solid.
 */

hit_list_t *
FilterInside(hit_list, solid)
hit_list_t	*hit_list;
solid_t		*solid;
{
	return(HitListFilter(hit_list, solid, SolidInside));
}


/* FilterOutside
 *
 * Instance of HitListFilter.  Discards all entries in a hitlist that
 * are not outside the solid.
 */

hit_list_t *
FilterOutside(hit_list, solid)
hit_list_t	*hit_list;
solid_t		*solid;
{
	return(HitListFilter(hit_list, solid, SolidOutside));
}