/******************************************************************************
 *
 * 9998sketch/scene.c
 *
 * (c) Eugene K. Ressler, Jr. 2004, 2005
 *
 * A program related to the book
 *
 * Fundamentals of Virtual World Simulation
 * by Eugene K. Ressler, Jr.
 *
 * No warranty of correctness or capability of any kind is expressed or implied.
 *
 * The author grants free use of this code for any purpose as long any text,
 * executable program, library file, or source code distributed to others 
 * and employing any portion of this code clearly cites the book named above.
 *
 ******************************************************************************/

#include <stdio.h>
#include <math.h>
#include "scene.h"
#include "emit.h"

DECLARE_DYNAMIC_2D_ARRAY_FUNCS(POINT_LIST_3D, POINT_3D, FLOAT, point_list_3d, v, n_pts, NO_OTHER_INIT)
DECLARE_DYNAMIC_2D_ARRAY_FUNCS(TRANSFORM_LIST, TRANSFORM, FLOAT, transform_list, xf, n_xfs, NO_OTHER_INIT)

// this must match the definition of OBJECT_TYPE
char *object_type_str[] = {
  "base",
  "tag",
  "option list",
  "scalar",
  "point",
  "vector",
  "transform",
  "dots",
  "line",
  "curve",
  "polygon",
  "special",
  "sweep",
  "repeat",
  "compound",
};

#define LAY_IN  0
#define LAY_OVER 1
#define LAY_UNDER -1

int lay_val(OPTS *opts, int lay_default)
{
  char *val = opt_val(opts, "lay");
  if (!val)
    return lay_default;
  if (strcmp(val, "over") == 0)
    return LAY_OVER;
  else if (strcmp(val, "under") == 0)
    return LAY_UNDER;
  else {
    warn(no_line, "lay=%s has been ignored", val);
    return lay_default;
  }
}

OBJECT *new_tag_def(void)
{
  TAG_DEF *r = safe_malloc(sizeof *r);
  r->tag = O_TAG_DEF;
  r->sibling = NULL;
  return (OBJECT*)r;
}

OBJECT *new_opts_def(char *opts_str, SRC_LINE line)
{
  OPTS_DEF *r = safe_malloc(sizeof *r);
  r->tag = O_OPTS_DEF;
  r->sibling = NULL;
  r->opts = new_opts(opts_str, line);
  return (OBJECT*)r;
}

OBJECT *new_scalar_def(FLOAT val)
{
  SCALAR_DEF *r = safe_malloc(sizeof *r);
  r->tag = O_SCALAR_DEF;
  r->sibling = NULL;
  r->val = val;
  return (OBJECT*)r;
}

OBJECT *new_point_def(POINT_3D p)
{
  POINT_DEF *r = safe_malloc(sizeof *r);
  r->tag = O_POINT_DEF;
  r->sibling =  NULL;
  copy_pt_3d(r->p, p);
  return (OBJECT*)r;
}

OBJECT *new_vector_def(VECTOR_3D v)
{
  VECTOR_DEF *r = safe_malloc(sizeof *r);
  r->tag = O_VECTOR_DEF;
  r->sibling = NULL;
  copy_vec_3d(r->v, v);
  return (OBJECT*)r;
}

OBJECT *new_transform_def(TRANSFORM xf)
{
  TRANSFORM_DEF *r = safe_malloc(sizeof *r);
  r->tag = O_TRANSFORM_DEF;
  r->sibling = NULL;
  copy_transform(r->xf, xf);
  return (OBJECT*)r;
}

void translate_points(POINT_LIST_3D *dst, OBJECT *src_obj)
{
  POINT_DEF *sibling,
            *src = (POINT_DEF*)src_obj;

  while (src) {
    copy_pt_3d(pushed_point_list_3d_v(dst), src->p);
    sibling = (POINT_DEF*)src->sibling;
    safe_free(src);
    src = sibling;
  }
}

DOTS_OBJECT *raw_dots(OPTS *opts)
{
  DOTS_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_DOTS;
  r->sibling = NULL;
  r->opts = opts;
  init_point_list_3d(r->pts);
  return r;
}

OBJECT *new_dots(OPTS *opts, OBJECT *pts)
{
  DOTS_OBJECT *r = raw_dots(opts);
  translate_points(r->pts, pts);
  return (OBJECT*)r;
}

OBJECT *copy_dots(OBJECT *obj)
{
  DOTS_OBJECT *org = (DOTS_OBJECT*)obj,
              *r = raw_dots(org->opts);
  copy_point_list_3d(r->pts, org->pts);
  return (OBJECT*)r;
}

LINE_OBJECT *raw_line(OPTS *opts)
{
  LINE_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_LINE;
  r->sibling = NULL;
  r->opts = opts;
  init_point_list_3d(r->pts);
  return r;
}

OBJECT *new_line(OPTS *opts, OBJECT *pts)
{
  LINE_OBJECT *r = raw_line(opts);
  translate_points(r->pts, pts);
  return (OBJECT*)r;
}

OBJECT *copy_line(OBJECT *obj)
{
  LINE_OBJECT *org = (LINE_OBJECT*)obj,
              *r = raw_line(org->opts);
  copy_point_list_3d(r->pts, org->pts);
  return (OBJECT*)r;
}

CURVE_OBJECT *raw_curve(OPTS *opts)
{
  CURVE_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_CURVE;
  r->sibling = NULL;
  r->opts = opts;
  init_point_list_3d(r->pts);
  return r;
}

OBJECT *new_curve(OPTS *opts, OBJECT *pts)
{
  CURVE_OBJECT *r = raw_curve(opts);
  translate_points(r->pts, pts);
  return (OBJECT*)r;
}

OBJECT *copy_curve(OBJECT *obj)
{
  CURVE_OBJECT *org = (CURVE_OBJECT*)obj,
               *r = raw_curve(org->opts);
  copy_point_list_3d(r->pts, org->pts);
  return (OBJECT*)r;
}

POLYGON_OBJECT *raw_polygon(OPTS *opts)
{
  POLYGON_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_POLYGON;
  r->sibling = NULL;
  r->opts = opts;
  init_point_list_3d(r->pts);
  r->border_p = 0;
  return r;
}

OBJECT *new_polygon(OPTS *opts, OBJECT *pts)
{
  POLYGON_OBJECT *r = raw_polygon(opts);
  translate_points(r->pts, pts);
  return (OBJECT*)r;
}

OBJECT *copy_polygon(OBJECT *obj)
{
  POLYGON_OBJECT *org = (POLYGON_OBJECT*)obj,
                 *r = raw_polygon(org->opts);
  copy_point_list_3d(r->pts, org->pts);
  return (OBJECT*)r;
}

static SPECIAL_OBJECT *raw_special(OPTS *opts)
{
  SPECIAL_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_SPECIAL;
  r->sibling = NULL;
  r->code = NULL;
  r->opts = opts;
  init_point_list_3d(r->pts);
  return r;
}

OBJECT *new_special(char *code, OPTS *opts, OBJECT *pts, SRC_LINE line)
{
  SPECIAL_OBJECT *r = raw_special(opts);
  r->code = code;
  translate_points(r->pts, pts);
  // syntax check
  process_special(NULL, r, line);
  return (OBJECT*)r;
}

OBJECT *copy_special(OBJECT *obj)
{
  SPECIAL_OBJECT *org = (SPECIAL_OBJECT*)obj,
                 *r = raw_special(org->opts);
  copy_point_list_3d(r->pts, org->pts);
  r->code = safe_strdup(org->code);
  return (OBJECT*)r;
}

SWEEP_OBJECT *raw_sweep(OPTS *opts)
{
  SWEEP_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_SWEEP;
  r->sibling = NULL;
  r->n_slices = 0;
  r->closed_p = 0;
  init_transform_list(r->xforms);
  r->opts = opts;
  r->swept = NULL;
  return r;
}

void translate_transforms(TRANSFORM_LIST *dst, OBJECT *src_obj)
{
  TRANSFORM_DEF *sibling,
                *src = (TRANSFORM_DEF*)src_obj;
  while (src) {
    copy_transform(pushed_transform_list_xf(dst), src->xf);
    sibling = (TRANSFORM_DEF*)src->sibling;
    safe_free(src);
    src = sibling;
  }
}

OBJECT *new_sweep(OPTS *opts, int n_slices, int closed_p, OBJECT *xfs, OBJECT *swept)
{
  SWEEP_OBJECT *r = raw_sweep(opts);
  r->n_slices = n_slices;
  r->closed_p = closed_p;
  translate_transforms(r->xforms, xfs);
  r->swept = swept;
  return (OBJECT*)r;
}

// this is a shallow copy
OBJECT *copy_sweep(OBJECT *obj)
{
  SWEEP_OBJECT *org = (SWEEP_OBJECT*)obj,
               *r = raw_sweep(org->opts);
  r->n_slices = org->n_slices;
  r->closed_p = org->closed_p;
  copy_transform_list(r->xforms, org->xforms);
  r->swept = org->swept;
  return (OBJECT*)r;
}

REPEAT_OBJECT *raw_repeat(void)
{
  REPEAT_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_REPEAT;
  r->sibling = NULL;
  r->n = 0;
  init_transform_list(r->xforms);
  r->repeated = NULL;
  return r;
}

OBJECT *new_repeat(int n, OBJECT *xfs, OBJECT *repeated)
{
  REPEAT_OBJECT *r = raw_repeat();
  r->n = n;
  translate_transforms(r->xforms, xfs);
  r->repeated = repeated;
  return (OBJECT*)r;
}

OBJECT *copy_repeat(OBJECT *obj)
{
  REPEAT_OBJECT *org = (REPEAT_OBJECT*)obj,
                *r = raw_repeat();
  r->n = org->n;
  copy_transform_list(r->xforms, org->xforms);
  r->repeated = org->repeated; // shallow copy
  return (OBJECT*)r;
}

OBJECT *new_compound(TRANSFORM xform, OBJECT *child)
{
  COMPOUND_OBJECT *r = safe_malloc(sizeof *r);
  r->tag = O_COMPOUND;
  r->sibling = NULL;
  copy_transform(r->xform, xform);
  r->child = child;
  return (OBJECT*)r;
}

// this is a shallow copy
OBJECT *copy_compound(OBJECT *obj)
{
  COMPOUND_OBJECT *org = (COMPOUND_OBJECT*)obj;
  return new_compound(org->xform, org->child);
}

typedef OBJECT *(*COPY_FUNC)(OBJECT *);

static COPY_FUNC copy_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  copy_dots,
  copy_line,
  copy_curve,
  copy_polygon,
  copy_special,
  copy_sweep,
  copy_repeat,
  copy_compound,
};

OBJECT *copy_drawable(OBJECT *obj)
{
  OBJECT *r = NULL;
  while (obj) {
    if (copy_tbl[obj->tag]) {
      OBJECT *copy = (*copy_tbl[obj->tag])(obj);
      copy->sibling = r;
      r = copy;
    }
    else {
      die(no_line, "copy_drawable: attempt to copy non-drawable %s", 
        object_type_str[obj->tag]);
    }
    obj = obj->sibling;
  }
  return sibling_reverse(r);
}

OBJECT *sibling_reverse(OBJECT *obj)
{
  OBJECT *p, *q, *t;

  // pop from p and push onto q until p is empty
  p = obj; q = NULL;
  while (p) {
    t = p; p = p->sibling; // pop
    t->sibling = q; q = t; // push
  }
  return q;
}

OBJECT *object_from_expr(EXPR_VAL *val)
{
  switch (val->tag) {
  case E_FLOAT:
    return new_scalar_def(val->val.flt);
  case E_POINT:
    return new_point_def(val->val.pt);
  case E_VECTOR:
    return new_vector_def(val->val.vec);
  case E_TRANSFORM:
    return new_transform_def(val->val.xf);
  default:
    die(no_line, "object_from_expr: unknown value tag %d", val->tag);
  }
  return NULL; // never occurs
}

void transform_points(POINT_LIST_3D *dst_pts, TRANSFORM xf, POINT_LIST_3D *src_pts)
{
  int i;

  setup_point_list_3d(dst_pts, src_pts->n_pts);
  for (i = 0; i < src_pts->n_pts; i++)
    transform_pt_3d(dst_pts->v[i], xf, src_pts->v[i]);
  dst_pts->n_pts = src_pts->n_pts;
}

static void fill_transform_accum(TRANSFORM_LIST *accum, TRANSFORM_LIST *inc)
{
  int i;

  setup_transform_list(accum, inc->n_xfs);
  accum->n_xfs = inc->n_xfs;
  for (i = 0; i < inc->n_xfs; i++)
    set_ident(accum->xf[i]);
}

static void advance_transform_accum(TRANSFORM_LIST *accum, TRANSFORM_LIST *inc)
{
  int i;
  for (i = 0; i < accum->n_xfs; i++)
    compose(accum->xf[i], accum->xf[i], inc->xf[i]);
}

static void compose_transform_accum(TRANSFORM xf, TRANSFORM_LIST *accum, TRANSFORM model_view_xf)
{
  int i;

  if (accum->n_xfs <= 0)
    die(no_line, "zero size accumulator");
  copy_transform(xf, accum->xf[0]);
  // left-multiply because accumulator is in "then" order
  for (i = 1; i < accum->n_xfs; i++)
    compose(xf, accum->xf[i], xf);
  if (model_view_xf)
    compose(xf, model_view_xf, xf);
}

OBJECT *flat_dots(OBJECT *obj, TRANSFORM xf)
{
  DOTS_OBJECT *s = (DOTS_OBJECT*)obj,
              *dots = raw_dots(s->opts); 
  transform_points(dots->pts, xf, s->pts);
  return (OBJECT*)dots;
}

OBJECT *flat_line(OBJECT *obj, TRANSFORM xf)
{
  LINE_OBJECT *s = (LINE_OBJECT*)obj,
              *line = raw_line(s->opts); 
	check_opts(s->opts, OPT_INTERNAL|OPT_LINE,
						 "unknown line option %s=%s will be ignored", 
						 global_env->output_language, no_line);
  transform_points(line->pts, xf, s->pts);
  return (OBJECT*)line;
}

OBJECT *flat_curve(OBJECT *obj, TRANSFORM xf)
{
  CURVE_OBJECT *s = (CURVE_OBJECT*)obj,
               *curve = raw_curve(s->opts); 
  transform_points(curve->pts, xf, s->pts);
  return (OBJECT*)curve;
}

OBJECT *flat_polygon(OBJECT *obj, TRANSFORM xf)
{
  POLYGON_OBJECT *s = (POLYGON_OBJECT*)obj,
               *polygon = raw_polygon(s->opts);
	check_opts(s->opts, OPT_INTERNAL|OPT_POLYGON|OPT_LINE,
						 "unknown polygon option %s=%s will be ignored",
						 global_env->output_language, no_line);
  transform_points(polygon->pts, xf, s->pts);
  return (OBJECT*)polygon;
}

OBJECT *flat_special(OBJECT *obj, TRANSFORM xf)
{
  SPECIAL_OBJECT *s = (SPECIAL_OBJECT*)obj,
                 *special = raw_special(s->opts);
  special->code = safe_strdup(s->code);
  transform_points(special->pts, xf, s->pts);
  return (OBJECT*)special;
}

#define MAX_WARP  1e-5

// return -1 if no split is necessary
// return 0 if best spilt is on the 0--2 line
// return 1 if best split is on the 1--3 line
static int best_triangle_split(POINT_3D v0, POINT_3D v1, POINT_3D v2, POINT_3D v3)
{
  VECTOR_3D n, d0, d1, e, e_max;
  FLOAT e_len_sqr, e_max_len_sqr, warp;

  sub_vecs_3d(d0, v2, v0);
  sub_vecs_3d(d1, v3, v1);
  cross(n, d0, d1);

  // if the cross product is zero length, the polygon is degenerate and can
  // be considered flat; no need to traingulate
  if (!find_unit_vec_3d(n, n))
    return -1;

  // find the edge of maximum length; probably not necessary
  sub_vecs_3d(e_max, v1, v0);
  e_max_len_sqr = dot_3d(e_max, e_max);

  sub_vecs_3d(e, v2, v1);
  e_len_sqr = dot_3d(e, e);
  if (e_len_sqr > e_max_len_sqr) {
    e_max_len_sqr = e_len_sqr;
    copy_vec_3d(e_max, e);
  }

  sub_vecs_3d(e, v3, v2);
  e_len_sqr = dot_3d(e, e);
  if (e_len_sqr > e_max_len_sqr) {
    e_max_len_sqr = e_len_sqr;
    copy_vec_3d(e_max, e);
  }

  sub_vecs_3d(e, v0, v3);
  e_len_sqr = dot_3d(e, e);
  if (e_len_sqr > e_max_len_sqr) {
    e_max_len_sqr = e_len_sqr;
    copy_vec_3d(e_max, e);
  }

  // flat if projection of edge on normal is small, else split on shortest diagonal
  warp = dot_3d(e_max, n);
  return 
    -MAX_WARP <= warp && warp <= MAX_WARP ? -1 :
    dot_3d(d0, d0) < dot_3d(d1, d1) ? 0 : 1;
}

// add triangular or quadrilateral faces to object list depending on flatness
static void make_faces(OBJECT **r, OPTS *opts, TRANSFORM xf, 
                       POINT_3D v0, POINT_3D v1, POINT_3D v2, POINT_3D v3,
                       int split_p)
{
  POLYGON_OBJECT *new_polygon;

  if (!split_p)
    goto no_split;

  switch (best_triangle_split(v0, v1, v2, v3)) {
  case -1:
no_split:
    new_polygon = raw_polygon(opts);
    setup_point_list_3d(new_polygon->pts, 4);
    transform_pt_3d(new_polygon->pts->v[0], xf, v0);
    transform_pt_3d(new_polygon->pts->v[1], xf, v1);
    transform_pt_3d(new_polygon->pts->v[2], xf, v2);
    transform_pt_3d(new_polygon->pts->v[3], xf, v3);
    new_polygon->pts->n_pts = 4;
    new_polygon->sibling = *r;
    *r = (OBJECT*)new_polygon;
    break;

  case 0:
    new_polygon = raw_polygon(opts);
    setup_point_list_3d(new_polygon->pts, 3);
    transform_pt_3d(new_polygon->pts->v[0], xf, v0);
    transform_pt_3d(new_polygon->pts->v[1], xf, v1);
    transform_pt_3d(new_polygon->pts->v[2], xf, v2);
    new_polygon->pts->n_pts = 3;
    new_polygon->sibling = *r;
    *r = (OBJECT*)new_polygon;
    new_polygon = raw_polygon(opts);
    setup_point_list_3d(new_polygon->pts, 3);
    transform_pt_3d(new_polygon->pts->v[0], xf, v2);
    transform_pt_3d(new_polygon->pts->v[1], xf, v3);
    transform_pt_3d(new_polygon->pts->v[2], xf, v0);
    new_polygon->pts->n_pts = 3;
    new_polygon->sibling = *r;
    *r = (OBJECT*)new_polygon;
    break;

  case 1:
    new_polygon = raw_polygon(opts);
    setup_point_list_3d(new_polygon->pts, 3);
    transform_pt_3d(new_polygon->pts->v[0], xf, v1);
    transform_pt_3d(new_polygon->pts->v[1], xf, v2);
    transform_pt_3d(new_polygon->pts->v[2], xf, v3);
    new_polygon->pts->n_pts = 3;
    new_polygon->sibling = *r;
    *r = (OBJECT*)new_polygon;
    new_polygon = raw_polygon(opts);
    setup_point_list_3d(new_polygon->pts, 3);
    transform_pt_3d(new_polygon->pts->v[0], xf, v3);
    transform_pt_3d(new_polygon->pts->v[1], xf, v0);
    transform_pt_3d(new_polygon->pts->v[2], xf, v1);
    new_polygon->pts->n_pts = 3;
    new_polygon->sibling = *r;
    *r = (OBJECT*)new_polygon;
    break;
  }
}

OBJECT *flat_sweep(OBJECT *obj, TRANSFORM xf)
{
  int i, j, jj, split_p;
  POINT_LIST_3D *a, *b, *t;
  OBJECT *swept, *r;
  TRANSFORM sweep_xf;
  POINT_LIST_3D pts_1[1], pts_2[1];
  TRANSFORM_LIST sweep_accum[1];

  SWEEP_OBJECT *s = (SWEEP_OBJECT*)obj;

  init_point_list_3d(pts_1);
  init_point_list_3d(pts_2);
  init_transform_list(sweep_accum);

  split_p = bool_opt_p(s->opts, "split", 1) && bool_opt_p(global_env->opts, "split", 1);

  r = NULL;

#define ADD_TO_OUTPUT(O)  do { \
  (O)->sibling = r; \
  r = (OBJECT*)(O); \
} while (0)

  // handle definitions first; a point becomes a single line or a polygon
  if (s->swept->tag == O_POINT_DEF) {
    fill_transform_accum(sweep_accum, s->xforms);
    for (swept = s->swept; swept; swept = swept->sibling) {
      POINT_DEF *pd = (POINT_DEF*)swept;
      if (s->closed_p) {
        POLYGON_OBJECT *polygon = raw_polygon(s->opts);
        for (i = 0; i < s->n_slices; i++) {
          compose_transform_accum(sweep_xf, sweep_accum, xf);
          transform_pt_3d(pushed_point_list_3d_v(polygon->pts), sweep_xf, pd->p);
          advance_transform_accum(sweep_accum, s->xforms);
        }
        ADD_TO_OUTPUT(polygon);
      }
      else {
        LINE_OBJECT *line = raw_line(s->opts);
        for (i = 0; i < s->n_slices + 1; i++) {
          compose_transform_accum(sweep_xf, sweep_accum, xf);
          transform_pt_3d(pushed_point_list_3d_v(line->pts), sweep_xf, pd->p);
          advance_transform_accum(sweep_accum, s->xforms);
        }
        ADD_TO_OUTPUT(line);
      }
    }
  }
  else {

    // it's drawable; recursively flatten swept object in its own coordinates
    for (swept = flat_scene(s->swept, NULL); swept; swept = swept->sibling) {

      // refill with identity for each swept object
      fill_transform_accum(sweep_accum, s->xforms);

      // now the different flavors of sweep depend on what's being swept and
      // the setting of the closure tag
      if (swept->tag == O_LINE) {
        // a line becomes a surface represented by a sequence of 4-sided polygons
        LINE_OBJECT *line = (LINE_OBJECT*)swept;

        // a is the trail buffer and b the lead
        a = pts_1;
        b = pts_2;
        copy_point_list_3d(a, line->pts);

        if (s->closed_p) {
          POLYGON_OBJECT *e1 = raw_polygon(s->opts);
          POLYGON_OBJECT *e2 = raw_polygon(s->opts);
          OPTS *face_opts = line->opts ? line->opts : s->opts;

          // set up in advance; e1 is filled in forward, e2 in reverse
          setup_point_list_3d(e1->pts, s->n_slices); 
          e1->pts->n_pts = s->n_slices;
          setup_point_list_3d(e2->pts, s->n_slices); 
          e2->pts->n_pts = s->n_slices;
          for (i = 0; i < s->n_slices - 1; i++) {
            advance_transform_accum(sweep_accum, s->xforms);
            compose_transform_accum(sweep_xf, sweep_accum, 0); // apply mv transform in make_faces
            transform_points(b, sweep_xf, line->pts);
            // copy first and last points for 'end caps'
            transform_pt_3d(e1->pts->v[i], xf, b->v[b->n_pts - 1]);
            transform_pt_3d(e2->pts->v[s->n_slices - 1 - i], xf, b->v[0]);
            for (jj = 0, j = 1; j < a->n_pts; jj = j++)
              make_faces(&r, face_opts, xf, b->v[jj], b->v[j], a->v[j], a->v[jj], split_p);
            t = a; a = b; b = t; // swap a and b for next pass
          }
          // closure: add last point of original line. first to ends, then as faces
          transform_pt_3d(e1->pts->v[i], xf, line->pts->v[line->pts->n_pts - 1]);
          transform_pt_3d(e2->pts->v[0], xf, line->pts->v[0]);
          for (jj = 0, j = 1; j < a->n_pts; jj = j++)
            make_faces(&r, face_opts, xf, line->pts->v[jj], line->pts->v[j], a->v[j], a->v[jj], split_p);

          // add ends to output
          ADD_TO_OUTPUT(e1);
          ADD_TO_OUTPUT(e2);
        }
        else {
          for (i = 0; i < s->n_slices; i++) {
            advance_transform_accum(sweep_accum, s->xforms);
            compose_transform_accum(sweep_xf, sweep_accum, 0);
            transform_points(b, sweep_xf, line->pts);
            for (jj = 0, j = 1; j < a->n_pts; jj = j++)
              make_faces(&r, s->opts, xf, b->v[jj], b->v[j], a->v[j], a->v[jj], split_p);
            t = a; a = b; b = t; // swap a and b for next pass
          }
        }
      }
      else if (swept->tag == O_POLYGON) {
        // a polygon becomes a surface represented by a sequence of 4-sided polygons (with "end caps")
        POLYGON_OBJECT *new_polygon, *polygon = (POLYGON_OBJECT*)swept;
        OPTS *end_opts = polygon->opts ? polygon->opts : s->opts;

        if (s->closed_p)
          warn(no_line, "closure tag on polygon sweep ignored (sorry, no line number)");

        a = pts_1;
        b = pts_2;
        copy_point_list_3d(a, polygon->pts);

        // initial end cap
        new_polygon = raw_polygon(end_opts);
        transform_points(new_polygon->pts, xf, a);
        ADD_TO_OUTPUT(new_polygon);

        for (i = 0; i < s->n_slices; i++) {
          advance_transform_accum(sweep_accum, s->xforms);
          compose_transform_accum(sweep_xf, sweep_accum, 0);
          transform_points(b, sweep_xf, polygon->pts);
          for (jj = a->n_pts - 1, j = 0; j < a->n_pts; jj = j++)
            make_faces(&r, s->opts, xf, b->v[jj], b->v[j], a->v[j], a->v[jj], split_p);
          t = a; a = b; b = t; // swap a and b for next pass
        }

        // final end cap is copy of a (note reverse point order)
        new_polygon = raw_polygon(end_opts);
        reverse_copy_point_list_3d(new_polygon->pts, a);
        transform_points(new_polygon->pts, xf, new_polygon->pts);
        ADD_TO_OUTPUT(new_polygon);
      }
      else {
        warn(no_line, "cannot sweep a %s; object ignored (sorry, no line number)", 
          object_type_str[swept->tag]);
      }
    }
  }

  clear_point_list_3d(pts_1);
  clear_point_list_3d(pts_2);
  clear_transform_list(sweep_accum);
  return r;
#undef ADD_TO_OUTPUT
}

// forward declaration
static OBJECT *rev_transformed_flat_scene(OBJECT *obj, TRANSFORM xf);

OBJECT *flat_repeat(OBJECT *obj, TRANSFORM xf)
{
  int i;
  REPEAT_OBJECT *s = (REPEAT_OBJECT*)obj;
  OBJECT *flat_repeated, *r;
  TRANSFORM_LIST repeat_accum[1];
  TRANSFORM child_xf;

  init_transform_list(repeat_accum);

  if (s->n <= 0)
    return NULL;

  // recursively flatten repeated object in its own coordinates
  flat_repeated = flat_scene(s->repeated, NULL);

  fill_transform_accum(repeat_accum, s->xforms);
  r = NULL;
  for (i = 0; i < s->n; i++) {
    compose_transform_accum(child_xf, repeat_accum, xf);
    r = cat_objects(rev_transformed_flat_scene(flat_repeated, child_xf), r);
    advance_transform_accum(repeat_accum, s->xforms);
  }
  // flat_repeated is a memory leak
  return r;
}

OBJECT *flat_compound(OBJECT *obj, TRANSFORM xf)
{
  COMPOUND_OBJECT *compound = (COMPOUND_OBJECT*)obj;
  TRANSFORM child_xf;
  compose(child_xf, xf, compound->xform);
  return rev_transformed_flat_scene(compound->child, child_xf);
}

typedef OBJECT *(*FLATTEN_FUNC)(OBJECT *, TRANSFORM);

static FLATTEN_FUNC flatten_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  flat_dots,
  flat_line,
  flat_curve,
  flat_polygon,
  flat_special,
  flat_sweep,
  flat_repeat,
  flat_compound,
};

OBJECT *cat_objects(OBJECT *lft, OBJECT *rgt)
{
  OBJECT *p;

  if (!lft)
    return rgt;
  for (p = lft; p->sibling; p = p->sibling)
    /* skip */ ;
  p->sibling = rgt;
  return lft;
}

static OBJECT *rev_transformed_flat_scene(OBJECT *obj, TRANSFORM xf)
{
  OBJECT *r = NULL;
  while (obj) {
    // flatten the object
    if (flatten_tbl[obj->tag] == NULL)
      die(no_line, "rev_transformed_flat_scene: bad tag %d", obj->tag);

    // join scene sibling lists
    r = cat_objects((*flatten_tbl[obj->tag])(obj, xf), r);

    // on to next object
    obj = obj->sibling;
  }
  return r;
}

// call with null env omits camera transformation
OBJECT *flat_scene(OBJECT *obj, GLOBAL_ENV *env)
{
  FLOAT *camera = env && global_env_is_set_p(env, GE_CAMERA) ? env->camera : identity;
  return sibling_reverse(rev_transformed_flat_scene(obj, camera));
}

// ---- overlay/underlay/depth sort flag --------------------------------------

static int dots_lay_val(OBJECT *obj)
{
  return lay_val(((DOTS_OBJECT*)obj)->opts, LAY_IN);
}

static int line_lay_val(OBJECT *obj)
{
  return lay_val(((LINE_OBJECT*)obj)->opts, LAY_IN);
}

static int curve_lay_val(OBJECT *obj)
{
  return lay_val(((CURVE_OBJECT*)obj)->opts, LAY_IN);
}

static int polygon_lay_val(OBJECT *obj)
{
  return lay_val(((POLYGON_OBJECT*)obj)->opts, LAY_IN);
}

static int special_lay_val(OBJECT *obj)
{
  return lay_val(((SPECIAL_OBJECT*)obj)->opts, LAY_OVER);
}

typedef int (*LAY_VAL_FUNC)(OBJECT *);

static LAY_VAL_FUNC lay_val_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  dots_lay_val,
  line_lay_val,
  curve_lay_val,
  polygon_lay_val,
  special_lay_val,
  NULL, // O_SWEEP (flattened)
  NULL, // O_REPEAT (flattened)
  NULL, // O_COMPOUND (flattened)
};

int object_lay_val(OBJECT *obj)
{
  if (!lay_val_tbl[obj->tag])
    die(no_line, "bad tag in object_lay_val");
  return (*lay_val_tbl[obj->tag])(obj);
}

// ---- binary space partition ------------------------------------------------

static void add_dots_object_to_bsp_pass_1(OBJECT *obj, BSP_TREE *bsp)
{
}

static void add_line_object_to_bsp_pass_1(OBJECT *obj, BSP_TREE *bsp)
{
}

static void add_curve_object_to_bsp_pass_1(OBJECT *obj, BSP_TREE *bsp)
{
}

static void add_polygon_object_to_bsp_pass_1(OBJECT *obj, BSP_TREE *bsp)
{
  int i;
  POLYGON_3D *polygon;
  POLYGON_OBJECT *polygon_obj = (POLYGON_OBJECT*)obj;
  PLANE plane[1];

  // copy point list to new polygon
  polygon = new_polygon_3d(polygon_obj->pts->n_pts);
  polygon->n_sides = polygon_obj->pts->n_pts;
  for (i = 0; i < polygon->n_sides; i++)
    copy_pt_3d(polygon->v[i], polygon_obj->pts->v[i]);

  find_polygon_plane(plane, polygon);

  // backface elimination
  // put the new polygon in the tree
  if (plane->n[Z] >= -FLOAT_EPS || 
      !bool_opt_p(polygon_obj->opts, "cull", 1) || 
      !bool_opt_p(global_env->opts,  "cull", 1)) {

    add_polygon_to_bsp(bsp, polygon, obj);
  }
  else {
    delete_polygon_3d(polygon);
  }
}

static void add_special_object_to_bsp_pass_1(OBJECT *obj, BSP_TREE *bsp)
{
}

typedef void (*BSP_INSERT_FUNC)(OBJECT *, BSP_TREE *);

static BSP_INSERT_FUNC insert_in_bsp_pass_1_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  add_dots_object_to_bsp_pass_1,
  add_line_object_to_bsp_pass_1,
  add_curve_object_to_bsp_pass_1,
  add_polygon_object_to_bsp_pass_1,
  add_special_object_to_bsp_pass_1,
  NULL, // O_SWEEP (flattened)
  NULL, // O_REPEAT (flattened)
  NULL, // O_COMPOUND (flattened)
};

static void add_dots_object_to_bsp_pass_2(OBJECT *obj, BSP_TREE *bsp)
{
  int i;
  DOTS_OBJECT *dots_obj = (DOTS_OBJECT*)obj;
  // insert each dot as a polyline with only one vertex
  for (i = 0; i < dots_obj->pts->n_pts; i++) {
    POLYLINE_3D *dot = new_polyline_3d(1);
    dot->n_vertices = 1;
    copy_pt_3d(dot->v[0], dots_obj->pts->v[i]);
    add_polyline_to_bsp(bsp, dot, obj);
  }
}

static void add_line_object_to_bsp_pass_2(OBJECT *obj, BSP_TREE *bsp)
{
  int i;
  POLYLINE_3D *polyline;
  LINE_OBJECT *line_obj = (LINE_OBJECT*)obj;

  // copy point list to new polyline
  polyline = new_polyline_3d(line_obj->pts->n_pts);
  polyline->n_vertices = line_obj->pts->n_pts;
  for (i = 0; i < line_obj->pts->n_pts; i++)
    copy_pt_3d(polyline->v[i], line_obj->pts->v[i]);

  // fprintf(stderr, "adding to bsp [%p(%d)]\n", line_obj->opts, line_obj->opts->list->n_elts); // DEBUG

  // put the new polyline in the tree
  add_polyline_to_bsp(bsp, polyline, obj);
}

static void add_curve_object_to_bsp_pass_2(OBJECT *obj, BSP_TREE *bsp)
{
}

static void add_polygon_object_to_bsp_pass_2(OBJECT *obj, BSP_TREE *bsp)
{
}

static void add_special_object_to_bsp_pass_2(OBJECT *obj,  BSP_TREE *bsp)
{
  SPECIAL_OBJECT *special_obj = (SPECIAL_OBJECT*)obj;
  POLYLINE_3D *special = new_polyline_3d(1);
  special->n_vertices = 1;
  copy_pt_3d(special->v[0], special_obj->pts->v[0]);
  add_polyline_to_bsp(bsp, special, obj);
}

static BSP_INSERT_FUNC insert_in_bsp_pass_2_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF  
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  add_dots_object_to_bsp_pass_2,
  add_line_object_to_bsp_pass_2,
  add_curve_object_to_bsp_pass_2,
  add_polygon_object_to_bsp_pass_2,
  add_special_object_to_bsp_pass_2,
  NULL, // O_SWEEP (flattened)
  NULL, // O_REPEAT (flattened)
  NULL, // O_COMPOUND (flattened)
};

// table functions are called in 
// OBJECT *hsr_scene_with_bsp(OBJECT *scene);

static void get_dots_from_polyline(OBJECT *src, OBJECT **output, BSP_POLYLINE_NODE *polyline_node)
{
  DOTS_OBJECT *dots_src = (DOTS_OBJECT*)src;
  DOTS_OBJECT *new_obj = raw_dots(dots_src->opts);
  copy_point_list_3d(new_obj->pts, (POINT_LIST_3D*)polyline_node->polyline);
  new_obj->sibling = *output;
  *output = (OBJECT*)new_obj;
}

static void get_line_from_polyline(OBJECT *src, OBJECT **output, BSP_POLYLINE_NODE *polyline_node)
{
  LINE_OBJECT *line_src = (LINE_OBJECT*)src;
  LINE_OBJECT *new_obj = raw_line(copy_line_opts(line_src->opts, 
																								 polyline_node->first_p, 
																								 polyline_node->last_p,
							 																	 global_env->output_language));
  copy_point_list_3d(new_obj->pts, (POINT_LIST_3D*)polyline_node->polyline);
  new_obj->sibling = *output;
  *output = (OBJECT*)new_obj;
}

static void get_curve_from_polyline(OBJECT *src, OBJECT **output, BSP_POLYLINE_NODE *polyline_node)
{
}

static void get_polygon_border_from_polyline(OBJECT *src, OBJECT **output, BSP_POLYLINE_NODE *polyline_node)
{
  // no longer used
  POLYGON_OBJECT *polygon_src = (POLYGON_OBJECT*)src;
	LINE_OBJECT *new_obj = raw_line(copy_opts(polygon_src->opts, OPT_LINE, global_env->output_language));
  copy_point_list_3d(new_obj->pts, (POINT_LIST_3D*)polyline_node->polyline);
  new_obj->sibling = *output;
  *output = (OBJECT*)new_obj;
}

static void get_special_from_polyline(OBJECT *src, OBJECT **output, BSP_POLYLINE_NODE *polyline_node)
{
  SPECIAL_OBJECT *special_src = (SPECIAL_OBJECT*)src;
	SPECIAL_OBJECT *new_obj = raw_special(copy_opts(special_src->opts, OPT_INTERNAL, global_env->output_language));
  copy_point_list_3d(new_obj->pts, special_src->pts);  // go back to original special since we didn't split
  new_obj->code = safe_strdup(special_src->code);
  new_obj->sibling = *output;
  *output = (OBJECT*)new_obj;
}

typedef void (*GET_OBJ_FROM_POLYLINE_FUNC)(OBJECT *src, OBJECT **output, BSP_POLYLINE_NODE *polyline_node);

static GET_OBJ_FROM_POLYLINE_FUNC get_obj_from_polyline_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF  
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  get_dots_from_polyline,
  get_line_from_polyline,
  get_curve_from_polyline,
  get_polygon_border_from_polyline,
  get_special_from_polyline,
  NULL, // O_SWEEP (flattened)
  NULL, // O_REPEAT (flattened)
  NULL, // O_COMPOUND (flattened)
};

void get_objects_from_bsp_node(BSP_NODE *bsp, void *env)
{
  int i, j, k, broken_border_p;
  OBJECT **output = (OBJECT**)env;

  if (bsp == NULL)
    return;

  if (bsp->tag == BSP_POLYGON) {
    OPTS *opts;
    LINE_OBJECT *new_line_obj = NULL;
    BSP_POLYGON_NODE *polygon_node = (BSP_POLYGON_NODE*)bsp;
    POLYGON_OBJECT *src = bsp->attr, *new_polygon_obj;

    broken_border_p = 0;
    for (i = 0; i < polygon_node->polygon->n_sides; i++) {
      if (!polygon_node->polygon_attr->elt[i].border_p) {
        broken_border_p = 1;
        break;
      }
    }
    if (broken_border_p) { 

      //  add these options if user didn't specify them
			opts = copy_opts(src->opts, OPT_POLYGON, global_env->output_language);
			add_no_edges_default_opt(&opts, global_env->output_language);
			add_solid_white_default_opt(&opts, global_env->output_language);

      new_polygon_obj = raw_polygon(opts);
      copy_point_list_3d(new_polygon_obj->pts, 
                         (POINT_LIST_3D*)polygon_node->polygon);
      new_polygon_obj->sibling = *output;
      *output = (OBJECT*)new_polygon_obj;

      // create the border from edges that did not result from splitting
      //
      // find a break in the border if there is one
      for (j = polygon_node->polygon->n_sides - 1, i = 0; 
           i < polygon_node->polygon->n_sides; 
           j = i++) {
        if (!polygon_node->polygon_attr->elt[j].border_p)
          break;
      }
      if (i == polygon_node->polygon->n_sides)
        i = 0;
      // j->i is now a border edge, which is what we want
      for (k = 0; 
           k < polygon_node->polygon->n_sides; 
           j = i, i = (i + 1) % polygon_node->polygon->n_sides, k++) {
        if (polygon_node->polygon_attr->elt[j].border_p) {
          if (new_line_obj == NULL) {
						opts = copy_opts(src->opts, OPT_LINE, global_env->output_language);
            new_line_obj = raw_line(opts);
            copy_pt_3d(pushed_point_list_3d_v(new_line_obj->pts), 
                       polygon_node->polygon->v[j]);
          }
          copy_pt_3d(pushed_point_list_3d_v(new_line_obj->pts), 
                     polygon_node->polygon->v[i]);
        }
        else if (new_line_obj) {
          new_line_obj->sibling = *output;
          *output = (OBJECT*)new_line_obj;
          new_line_obj = NULL;
        }
      }
      if (new_line_obj) {
        new_line_obj->sibling = *output;
        *output = (OBJECT*)new_line_obj;
        new_line_obj = NULL;
      }
    }
    else {
			opts = copy_opts(src->opts, OPT_POLYGON | OPT_LINE, global_env->output_language);
			add_solid_white_default_opt(&opts, global_env->output_language);

      new_polygon_obj = raw_polygon(opts);
      new_polygon_obj->border_p = 1;
      copy_point_list_3d(new_polygon_obj->pts, 
                         (POINT_LIST_3D*)polygon_node->polygon);
      new_polygon_obj->sibling = *output;
      *output = (OBJECT*)new_polygon_obj;
    }
  }
  else { // BSP_POLYLINE
    OBJECT *src = bsp->attr;
    (*get_obj_from_polyline_tbl[src->tag])(src, output, (BSP_POLYLINE_NODE*)bsp);
  }
}

OBJECT *hsr_scene_with_bsp(OBJECT *scene)
{
  OBJECT *p, *t, *underlay, *overlay, *sorted;
  BSP_TREE bsp;

  // two passes are needed to serve the bsp requirement
  // that polylines be inserted after all polygons are
  // already there
  // also take care of underlays and ovelays in the first pass
  bsp = NULL;
  underlay = overlay = sorted = NULL;
  for (p = scene; p; p = p->sibling) {
    switch (object_lay_val(p)) {
    case LAY_UNDER:
      t = copy_drawable(p);
      t->sibling = underlay;
      underlay = t;
      break;
    case LAY_IN:
      (*insert_in_bsp_pass_1_tbl[p->tag])(p, &bsp);
      break;
    case LAY_OVER:
      t = copy_drawable(p);
      t->sibling = overlay;
      overlay = t;
      break;
    default:
      die(no_line, "bad lay value in hsr_scene_with_bsp");
      break;
    }
  }
  for (p = scene; p; p = p->sibling)
    if (object_lay_val(p) == LAY_IN)
      (*insert_in_bsp_pass_2_tbl[p->tag])(p, &bsp);
  traverse_bsp(bsp, get_objects_from_bsp_node, &sorted);
  sorted = sibling_reverse(sorted);
  sorted = cat_objects(underlay, sorted);
  sorted = cat_objects(sorted, overlay);
  return sorted;
}

// ---- depth sort ------------------------------------------------------------

static void add_dots_object_to_sort(OBJECT *obj, BSP_TREE *bsp)
{
  int i;
  DOTS_OBJECT *dots_obj = (DOTS_OBJECT*)obj;
  POLYLINE_3D dot[1];

  init_polyline_3d(dot);
  setup_polyline_3d(dot, 1);
  dot->n_vertices = 1;

  // insert each dot as a polyline with only one vertex
  for (i = 0; i < dots_obj->pts->n_pts; i++) {
    copy_pt_3d(dot->v[0], dots_obj->pts->v[i]);
    add_polyline_to_sort(bsp, dot, obj);
  }
  clear_polyline_3d(dot);
}

static void add_line_object_to_sort(OBJECT *obj, BSP_TREE *bsp)
{
  LINE_OBJECT *line_obj = (LINE_OBJECT*)obj;
  // DANGER: assumes point list in polyline object is congruent to a geometry.h polyline
  add_polyline_to_sort(bsp, (POLYLINE_3D*)line_obj->pts, obj);
}

static void add_curve_object_to_sort(OBJECT *obj, BSP_TREE *bsp)
{
}

static void add_polygon_object_to_sort(OBJECT *obj, BSP_TREE *bsp)
{
  POLYGON_OBJECT *polygon_obj = (POLYGON_OBJECT*)obj;
  PLANE plane[1];

  // backface elimination
  // put the new polygon in the tree
  find_polygon_plane(plane, (POLYGON_3D*)polygon_obj->pts);
  if (plane->n[Z] >= -FLOAT_EPS ||
      !bool_opt_p(polygon_obj->opts, "cull", 1) ||
      !bool_opt_p(global_env->opts,  "cull", 1))
    add_polygon_to_sort(bsp, (POLYGON_3D*)polygon_obj->pts, obj);
}

static void add_special_object_to_sort(OBJECT *obj, BSP_TREE *bsp)
{
  SPECIAL_OBJECT *special_obj = (SPECIAL_OBJECT*)obj;
  POLYLINE_3D *special = new_polyline_3d(1);
  special->n_vertices = 1;
  copy_pt_3d(special->v[0], special_obj->pts->v[0]);
  add_polyline_to_sort(bsp, special, obj);
}

typedef void (*ADD_TO_DS_FUNC)(OBJECT*, BSP_TREE*);

static ADD_TO_DS_FUNC add_to_sort_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  add_dots_object_to_sort,
  add_line_object_to_sort,
  add_curve_object_to_sort,
  add_polygon_object_to_sort,
  add_special_object_to_sort,
  NULL, // O_SWEEP (flattened)
  NULL, // O_REPEAT (flattened)
  NULL, // O_COMPOUND (flattened)
};

OBJECT *hsr_scene_with_depth_sort(OBJECT *scene)
{
  OBJECT *p, *t, *underlay, *overlay, *sorted;
  BSP_TREE bsp;

  // two passes are needed to serve the bsp requirement
  // that polylines be inserted after all polygons are
  // already there
  // also take care of underlays and ovelays in the first pass
  bsp = NULL;
  underlay = overlay = sorted = NULL;
  for (p = scene; p; p = p->sibling) {
    switch (object_lay_val(p)) {
    case LAY_UNDER:
      t = copy_drawable(p);
      t->sibling = underlay;
      underlay = t;
      break;
    case LAY_IN:
      (*add_to_sort_tbl[p->tag])(p, &bsp);
      break;
    case LAY_OVER:
      t = copy_drawable(p);
      t->sibling = overlay;
      overlay = t;
      break;
    default:
      die(no_line, "bad lay value in hsr_scene_with_bsp");
      break;
    }
  }
  sort_by_depth(&bsp);
  traverse_depth_sort(bsp, get_objects_from_bsp_node, &sorted);
  sorted = sibling_reverse(sorted);
  sorted = cat_objects(underlay, sorted);
  sorted = cat_objects(sorted, overlay);
  return sorted;
}

// ---- extent finding --------------------------------------------------------

static void get_extent_of_points(POINT_LIST_3D *pts, BOX_3D *e)
{
  int i;

  for (i = 0; i < pts->n_pts; i++)
    fold_min_max_pt_3d(e, pts->v[i]);
}

static void get_extent_of_dots(OBJECT *obj, BOX_3D *e)
{
  DOTS_OBJECT *dots = (DOTS_OBJECT*)obj;
  get_extent_of_points(dots->pts, e);
}

static void get_extent_of_line(OBJECT *obj, BOX_3D *e)
{
  LINE_OBJECT *line = (LINE_OBJECT*)obj;
  get_extent_of_points(line->pts, e);
}

static void get_extent_of_curve(OBJECT *obj, BOX_3D *e)
{
  CURVE_OBJECT *curve = (CURVE_OBJECT*)obj;
  get_extent_of_points(curve->pts, e);
}

static void get_extent_of_polygon(OBJECT *obj, BOX_3D *e)
{
  POLYGON_OBJECT *polygon = (POLYGON_OBJECT*)obj;
  get_extent_of_points(polygon->pts, e);
}

static void get_extent_of_special(OBJECT *obj, BOX_3D *e)
{
  SPECIAL_OBJECT *special = (SPECIAL_OBJECT*)obj;
  fold_min_max_pt_3d(e, special->pts->v[0]);
}

typedef void (*EXTENT_FUNC)(OBJECT*, BOX_3D*);

static EXTENT_FUNC extent_tbl[] = 
{
  NULL, // O_BASE
  NULL, // O_TAG_DEF
  NULL, // O_OPTS_DEF
  NULL, // O_SCALAR_DEF
  NULL, // O_POINT_DEF
  NULL, // O_VECTOR_DEF
  NULL, // O_TRANSFORM_DEF
  get_extent_of_dots,
  get_extent_of_line,
  get_extent_of_curve,
  get_extent_of_polygon,
  get_extent_of_special,
  NULL, // O_SWEEP (flattened)
  NULL, // O_REPEAT (flattened)
  NULL, // O_COMPOUND (flattened)
};

void get_extent(OBJECT *obj, BOX_3D *e, int *n_obj)
{
  if (obj) {
    int n = 0;
    e->min[X] = e->min[Y] = e->min[Z] = FLOAT_MAX;
    e->max[X] = e->max[X] = e->max[X] = FLOAT_MIN;
    while (obj) {
      if (extent_tbl[obj->tag] == NULL)
        die(no_line, "get_extent: bad tag %d", obj->tag);
      (*extent_tbl[obj->tag])(obj, e);
      obj = obj->sibling;
      ++n;
    }
    *n_obj = n;
  }
  else {
    // reasonable empty box
    e->min[X] = e->min[Y] = e->min[Z] = 0;
    e->max[X] = e->max[X] = e->max[X] = 1;
    *n_obj = 0;
  }
}

int xy_overlap_p(OBJECT *obj, BOX_3D *e)
{
  BOX_3D e_obj[1];
  (*extent_tbl[obj->tag])(obj, e_obj);
  return 
    e_obj->max[X] > e->min[X] ||
    e_obj->min[X] < e->max[X] ||
    e_obj->max[Y] > e->min[Y] ||
    e_obj->min[Y] < e->max[Y];
}