/* 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