/******************************************************************************
 *
 * 9998sketch/bsp.h
 *
 * (c) Eugene K. Ressler, Jr. 2004, 2005
 *
 * A program related to the book
 *
 * Fundamentals of Virtual World Simulation
 * by Eugene K. Ressler, Jr.
 *
 * No warranty of correctness or capability of any kind is expressed or implied.
 *
 * The author grants free use of this code for any purpose as long any text,
 * executable program, library file, or source code distributed to others 
 * and employing any portion of this code clearly cites the book named above.
 *
 ******************************************************************************/

#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