diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /graphics/sketch/scene.c |
Initial commit
Diffstat (limited to 'graphics/sketch/scene.c')
-rw-r--r-- | graphics/sketch/scene.c | 1646 |
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]); +} |