1 files changed, 100 insertions, 0 deletions
diff --git a/graphics/sketch/bsp.h b/graphics/sketch/bsp.h
new file mode 100644
index 0000000000..4659cd033d
--- /dev/null
+++ b/graphics/sketch/bsp.h
@@ -0,0 +1,100 @@
+/* bsp.h
+   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 */
+
+#ifndef __BSP_H
+#define __BSP_H
+
+#include "geometry.h"
+
+typedef enum bsp_node_type_t
+{
+  BSP_POLYGON,
+  BSP_POLYLINE,
+}
+BSP_NODE_TYPE;
+
+#define BASE_BSP_NODE_FIELDS  \
+  BSP_NODE_TYPE tag; \
+  struct bsp_node_t *prev, *next, *mark, *in, *on, *out; \
+  void *attr; \
+  BOX_3D extent[1]
+
+typedef struct bsp_node_t
+{
+  BASE_BSP_NODE_FIELDS;
+}
+BSP_NODE, *BSP_TREE;
+
+typedef struct bsp_vertex_attr_t
+{
+  int border_p;
+  int parent_vtx;
+  int cut_p;
+}
+BSP_VERTEX_ATTR;
+
+typedef struct bsp_polygon_attr_t
+{
+  DYNAMIC_ARRAY_FIELDS (BSP_VERTEX_ATTR, elt, n_elts);
+}
+BSP_POLYGON_ATTR;
+
+DECLARE_DYNAMIC_ARRAY_PROTOS (BSP_POLYGON_ATTR, BSP_VERTEX_ATTR,
+			      polygon_attr, elt, n_elts)
+     typedef struct bsp_polygon_node_t
+     {
+       BASE_BSP_NODE_FIELDS;
+       PLANE plane[1];
+       POLYGON_3D polygon[1];
+       BSP_POLYGON_ATTR polygon_attr[1];	// attributes of polygon vertices
+     }
+BSP_POLYGON_NODE;
+
+     typedef struct bsp_polyline_node_t
+     {
+       BASE_BSP_NODE_FIELDS;
+       POLYLINE_3D polyline[1];
+       int first_p, last_p;
+     }
+BSP_POLYLINE_NODE;
+
+     void add_polygon_to_bsp (BSP_TREE * bsp, POLYGON_3D * polygon,
+			      void *attr);
+
+     void add_polyline_to_bsp (BSP_TREE * bsp, POLYLINE_3D * polylines,
+			       void *attr);
+
+     typedef void (*BSP_NODE_FUNC) (BSP_NODE * node, void *env);
+
+     void traverse_bsp (BSP_NODE * bsp, BSP_NODE_FUNC func, void *env);
+
+     void traverse_depth_sort (BSP_NODE * bsp, BSP_NODE_FUNC func, void *env);
+
+     void print_bsp (FILE * f, BSP_NODE * bsp);
+
+     void add_polygon_to_sort (BSP_TREE * bsp, POLYGON_3D * polygon,
+			       void *attr);
+
+     void add_polyline_to_sort (BSP_TREE * bsp, POLYLINE_3D * polyline,
+				void *attr);
+
+     void sort_by_depth (BSP_TREE * bsp);
+
+#endif