/* scene.c
  Copyright (C) 2005,2006,2007 Eugene K. Ressler, Jr.

This file is part of Sketch, a small, simple system for making
3d drawings with LaTeX and the PSTricks or TikZ package.

Sketch is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

Sketch is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Sketch; see the file COPYING.txt.  If not, see
http://www.gnu.org/copyleft */

#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 if (strcmp (val, "in") == 0)
   return LAY_IN;
 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;
     init_box_3d(e);
     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[Y] = e->max[Z] = 1;
     *n_obj = 0;
   }
}

int
xy_overlap_p (OBJECT * obj, BOX_3D * e)
{
 BOX_3D e_obj[1];

 init_box_3d(e_obj);
 (*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]);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.