summaryrefslogtreecommitdiff
path: root/graphics/sketch/scene.c
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /graphics/sketch/scene.c
Initial commit
Diffstat (limited to 'graphics/sketch/scene.c')
-rw-r--r--graphics/sketch/scene.c1646
1 files changed, 1646 insertions, 0 deletions
diff --git a/graphics/sketch/scene.c b/graphics/sketch/scene.c
new file mode 100644
index 0000000000..3e5d8740f5
--- /dev/null
+++ b/graphics/sketch/scene.c
@@ -0,0 +1,1646 @@
+/* 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]);
+}