/*
	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License version 2 
	as published by the Free Software Foundation.

	This program 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 this program; if not, write to the Free Software
	Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA


	Copyright (C) 2006  Thierry Berger-Perrin <tbptbp@gmail.com>
*/
#include "specifics.h"

#include "kdlib.h"
#include "kdlib_internal.h"

#include "sys_clock.h"

#include "kdlib_score.h"

int check_stuff();


namespace kdlib {


	/*
	template<> lbox_t sided_list_t<side_left>::dummy;
	template<> lbox_t sided_list_t<side_right>::dummy;
	*/
	template <sideness_t side> lbox_t sided_list_t<side>::dummy;

	// tag all those list elements according to the split.
	void list_categorize(const lbox_t::ptr_t head, const uint_t axis, const float split, const sideness_t planar_side) {
		// only consider triangles once.
		sideness_t side;
		lbox_t * __restrict p = head.extract(side);
		for (; p; p = p->dim[axis][side].next.extract(side)) {
			if (side == side_left)
				p->set_category(axis, split, planar_side);
		}
	}

	void list_enumerate(const lbox_t::ptr_t head, const uint_t axis, int &num_l, int &num_r, int &num_clip, int &num_planar) {
		num_l = 0;
		num_r = 0;
		num_clip = 0;
		num_planar = 0;

		int pair_l = 0, pair_r = 0;
		sideness_t side;
		const lbox_t * __restrict p = head.extract(side);
		for (; p; p = p->dim[axis][side].next.extract(side)) {
			if (side == side_left) {
				++pair_l;
				if (!p->flags.tag_clipped) {
					if (!p->flags.tag_planar) {
						num_l += p->flags.tag_side == side_left  ? 1 : 0;
						num_r += p->flags.tag_side == side_right ? 1 : 0;
					}
					else
						++num_planar;
					/*
					num_l += p->flags.tag_side == side_left  ? 1 : 0;
					num_r += p->flags.tag_side == side_right ? 1 : 0;
					num_planar += p->flags.tag_planar ? 1 : 0;
					*/
				}
				else
					++num_clip;
			}
			else
				++pair_r;
		}

		if (pair_l != pair_r) {
			sys::log("list_enumerate: pair_l/pair_r mismatch. debug.\n");
			BREAKPOINT();
		}
	}



	/*
		~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
												Scoring.
		~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	*/

	/*
		MLRTA
		1.	We always create an empty cell if its volume with respect to the original cell
			is greater than some threshold (10% in our implementation).  
		2.	If there is a possible split plane which is completely covered by co-planar triangles,
			it will be selected and  these triangles will be included in the smaller sub-cell. 
			This heuristic sits well with the axis-aligned nature of kd- traversal process.
		3.	In addition to termination criteria based solely on a cost function (cost of splitting > cost of non-splitting),
			we also avoid creating very small cells, as measured by the ratio of the cell area to the area of the bounding box scene.
	*/


	template <uint_t axis>
	//static FINLINE
	static NOINLINE
	//void do_score_axis(const aabb_t &cell, const boundary_t * __restrict const left, const boundary_t * __restrict const right, const int_t tcount, score_t &best) throw()
	void do_score_axis(const SAH::heuristic_t &sah, const lbox_t::ptr_t head, const int_t tcount, const aabb_t &cell, score_t &best) throw()
	{
		enum { ku = (axis+1)%3, kv = (axis+2)%3 };
		const vec_t cell_extent(cell.pmax - cell.pmin); //FIX: work already done in get_area()

		//KLUDGE: detect if we're trying to split a dimension that is waaaaay smaller than the others.
		// should be moved into try_split, that should compute a mask of axis to inspect.
		// check for mlrta rules too, microscopic cells.
		if (0) {
			const double
				max = double(maxf(maxf(cell_extent.x,cell_extent.y), cell_extent.z)),
				dim = double(cell_extent[axis]),
				min_ratio = 1e-4;

			if (dim < (max*min_ratio))
				return;
		}

		const double
			cell_area = cell.get_area(),
			cell_area_rcp = 1/cell_area,

			// area = x*(y+z) + y*z = x*area_mul + area_add
			area_mul = double(cell_extent[ku])+double(cell_extent[kv]),
			area_add = double(cell_extent[ku])*double(cell_extent[kv]),

			score_term_add = sah.cost_traversal,
			score_term_mul = cell_area_rcp*sah.cost_intersection;

		const float
			cell_min = cell.pmin[axis],
			cell_max = cell.pmax[axis];


		//debug_boundary_list(left->next[axis], left->prev[axis], axis);

		// evaluate all candidates
		{
			int pair_l = 0, pair_r = 0; //debug:

			int open = 0, close = 0, local_open = 0, local_close = 0, num_planars = 0;
			//const boundary_t * __restrict p;
			sideness_t side;
			const lbox_t * __restrict p = head.extract(side);
			for (; p; p = p->dim[axis][side].next.extract(side)) {
				/*
					Beancounting time.
				*/
				open  += local_open + num_planars;
				close += local_close + num_planars;
				local_open = 0;  local_close = 0; num_planars = 0;
				// load some info upfront.
				const float coord = p->dim[axis][side].pos;
				{
					const bool_t 
						is_left		= (side == side_left),
						is_planar	= p->is_planar<axis>(coord);

					pair_l += is_left; pair_r += !is_left;

					if (!is_planar) {
						local_open	+= is_left ? 1 : 0;
						local_close	+= is_left ? 0 : 1;
					}
					else
						num_planars += is_left ? 1 : 0;	// only count it once
				}
				// tmp kludge for flat cells & lack of clipping.
				if (coord <= cell_min) continue;
				if (coord >= cell_max) break;

				// look ahead for split candidates sharing the same coordinate.
				// basically, we can't start crossings at this point.
				{
					sideness_t q_side;
					const lbox_t * __restrict q = p->dim[axis][side].next.extract(q_side);
					for (; q; q = q->dim[axis][q_side].next.extract(q_side)) {
						if (q->dim[axis][q_side].pos != coord) break;

						const bool_t 
							is_left		= q_side == side_left,
							is_planar	= q->is_planar<axis>(coord);

						pair_l += is_left; pair_r += !is_left;	//debug:

						if (!is_planar) {
							local_open	+= is_left ? 1 : 0;
							local_close	+= is_left ? 0 : 1;
						}
						else
							num_planars += is_left ? 1 : 0;	// only count it once

						p = q;
						side = q_side;
					}
				}
				
				/*
					Scoring, per se.
					
					Ok, now we know how many segments are completly on the left,crossing or embedded into the split plane.
					Populations expressed in triangles, not boundaries.

					Triangles, which are completely contained in a split 
					plane, go into the smaller sub-cell, except for the 
					case when we can create an empty cell by moving 
					these triangles to the bigger sub-cell. 
				*/
				{
					/*
					const int
						tmp_num_l		= open,
						tmp_num_r		= tcount - (close+local_close),
						num_cross		= open - (close+local_close);

					int
						num_l			= tmp_num_l-num_cross,
						num_r			= tmp_num_r-num_cross - num_planars,
						embedded_side	= -1;
					*/

					const double
						extent_l = double(coord) - cell_min,
						extent_r = cell_max - double(coord),
						area_l = extent_l*area_mul + area_add,
						area_r = extent_r*area_mul + area_add;

					const int
						num_l		= close+local_close,							// completly on the left side.
						num_cross	= open - num_l,									// local_open(s) end up on the right side.
						num_r		= tcount - (num_l + num_cross + num_planars);	// completly on the right side.


					// Now we decide where we should stuff planar triangles.
					//
					// into the smaller voxel.
					sideness_t planar_side = area_l < area_r ? side_left : side_right;	
					// unless one side is empty (implied there's no crossing).
					if ((num_l+num_cross == 0) | (num_r+num_cross == 0))
						planar_side = num_l == 0 ? side_right : side_left;

					const int
						num_planar_left		= planar_side == side_left ? num_planars : 0,
						num_planar_right	= planar_side == side_right ? num_planars : 0;


					const int
						score_num_left	= num_l+num_cross+num_planar_left,
						score_num_right	= num_r+num_cross+num_planar_right;
					const double
						//nl = double(score_num_left), nr = double(score_num_right),
						factor = 1, // .85, //.5, //
						nl = double(num_l+num_planar_left) + factor*(num_cross),
						nr = double(num_r+num_planar_right) + factor*(num_cross),

						//mul = ((nl == 0.) | (nr == 0.)) ? score_term_mul*factor : score_term_mul,
						//score = score_term_add + mul*(nl*area_l + nr*area_r);
						score = score_term_add + score_term_mul*(nl*area_l + nr*area_r);
						


					/* verif */
					if (0) {
						list_categorize(head, axis, coord, planar_side);
						int dbg_nl = 0, dbg_nr = 0, dbg_nclip = 0, dbg_nplanar = 0;
						list_enumerate(head, axis, dbg_nl, dbg_nr, dbg_nclip, dbg_nplanar);

						const int
							d_l = num_l-dbg_nl,
							d_r = num_r-dbg_nr,
							d_c = num_cross-dbg_nclip,
							d_p = num_planars-dbg_nplanar,
							diff = d_l|d_r|d_c|d_p,

							total = num_l+num_r+num_cross+num_planars;

						if (diff) {
							sys::log("mismatch between categorize & verif while scoring.\n");
							list_enumerate(head, axis, dbg_nl, dbg_nr, dbg_nclip, dbg_nplanar);
							BREAKPOINT();
						}

						if (total != tcount) {
							sys::log("total (%d) != tcount (%d) while scoring.\n", total, tcount);
							BREAKPOINT();
						}
						int zzzz = 0;
					}



					if (
						((score_num_left > 0) | (score_num_right > 0)) &
						//((score_num_left > 0) & (score_num_right > 0)) &	// shouldn't happen, and in any case should be produced by the space cut heuristic earlier.
						(score < best.score))
					{
						best.score			= score;
						best.split_coord	= coord;
						best.axis			= axis;

						best.num_l			= num_l;			// completly on the left
						best.num_r			= num_r;			// completly on the right
						best.num_cross		= num_cross;		// crossing
						best.num_planar		= num_planars;		// embedded
						best.scored_lefts	= score_num_left;	// and what was really scored.
						best.scored_rights	= score_num_right;

						best.planar_side	= planar_side;

						++best.updates;

						//if ((best.scored_lefts <= 0) || (best.scored_rights <= 0)) BREAKPOINT();
					}
				} // scoring
			} // for all split candidates.
		}
	}


	// void do_score_axis(const boundary_t * __restrict const left, const aabb_t &cell , const int_t tcount, score_t &best) throw()
	static void split_try(const SAH::heuristic_t &sah, const list3d_t &l3, const int_t tcount, const aabb_t &cell, score_t &best) {
		// early rejectal goes here.
		// <---
		if (uint_t(tcount) <= sah.leaf_count_min) return;

		//
		// try to find some void either on the left or right of each axis.
		// if a threshold is met, immediatly split.
		//
		//  mlrta:	We always create an empty cell if its volume with respect 
		//			to the original cell is greater than some threshold (10% in 
		//			our implementation).

		//
		//TODO: could also check if we can cheaply embed stuff in the splitting plane.
#if 0
		if (1) {
			const vec_t cell_extent(cell.max - cell.min);
			const double
				minimal_ratio = sah.microscopic_cell_ratio, //0.25, // 0.1,
				volume_cell = double(cell_extent.x) *  double(cell_extent.y) *  double(cell_extent.z);

			double best_volume = volume_cell * minimal_ratio;
			bool_t and_the_winner_is = false;
			if (volume_cell > 0.) {
				for (int_t axis = 0; axis < 3; ++axis) {
					if (hp.next[axis] && hp.prev[axis]) {
						const float
							cell_min = cell.min[axis],
							cell_max = cell.max[axis],
							content_min = hp.next[axis]->get_clip_box()->box.min[axis],
							content_max = hp.prev[axis]->get_clip_box()->box.max[axis],
							solid_min = maxf(content_min, cell_min),
							solid_max = minf(content_max, cell_max);

						vec_t extent_l(cell_extent), extent_r(cell_extent);
						// emptyness on the left, content on the right
						extent_l[axis] = solid_min - cell_min;

						extent_r[axis] = cell_max - solid_max;

						const double 
							volume_cell_l = double(extent_l.x) *  double(extent_l.y) *  double(extent_l.z),
							volume_cell_r = double(extent_r.x) *  double(extent_r.y) *  double(extent_r.z);

						if (volume_cell_l > best_volume) {
							and_the_winner_is = true;
							best_volume = volume_cell_l;
							
							best.axis			= axis;
							best.num_l			= 0;
							best.num_r			= tcount;
							best.scored_lefts	= 0;
							best.scored_rights	= tcount;
							best.num_cross		= 0;
							best.num_planar		= 0;
							best.planar_side	= -1;
							best.score			= -1;
							best.split_coord	= solid_min;
							best.zone_begin		= hp.next[axis];
							best.zone_end		= hp.next[axis];	// we only define a zone #3
							best.is_space_cut	= true;
							++best.updates;
						}
						if (volume_cell_r > best_volume) {
							and_the_winner_is = true;
							best_volume = volume_cell_l;
							
							best.axis			= axis;
							best.num_l			= tcount;
							best.num_r			= 0;
							best.scored_lefts	= tcount;
							best.scored_rights	= 0;
							best.num_cross		= 0;
							best.num_planar		= 0;
							best.planar_side	= -1;
							best.score			= -1;
							best.split_coord	= solid_max;
							best.zone_begin		= 0;
							best.zone_end		= 0;				// we only define a zone #1
							best.is_space_cut	= true;
							++best.updates;
						}
					}
				}
				if (and_the_winner_is) return;
			}
		}
#endif


		//
		// score each axis.
		//
		for (int_t axis = 0; axis < 3; ++axis) {
			/*
			if (verbosity >= 5) {
				sys::log("split_try: dump axis %d\n", axis);
				debug_boundary_list(hp.next[axis], hp.prev[axis], axis);
				const int sl = boundary_t::size(hp.next[axis], true, axis);
				sys::log("len %d\n", sl);
			}
			*/
			switch (axis) {
				case 0: do_score_axis<0>(sah, l3.heads[axis], tcount, cell, best); break;
				case 1: do_score_axis<1>(sah, l3.heads[axis], tcount, cell, best); break;
				case 2: do_score_axis<2>(sah, l3.heads[axis], tcount, cell, best); break;
			}
		}
	}


	static void do_build(compiler_t &compiler, const SAH::heuristic_t &sah, list3d_t &l3, const uint_t tcount, node_t &node, const int lvl, const uint64_t addr) throw() {
		//if (verbosity >= 5) sys::log("\n\n\nkdlib::do_build: addr %s (0x%llx).\n", debug_addr(addr),addr);
		compiler.stats.max_lvl = std::max(compiler.stats.max_lvl, lvl);
		score_t best;

		// if we can't beat that cost, make a leaf instead.
		best.score = 1. * double(tcount) * sah.cost_intersection;


		if (uint_t(lvl) < sah.depth_max)
			split_try(sah, l3, tcount, node.cell, best);

		//sys::log("score: %f, axis %d, coord %f, updates %d.\n", best.score, best.axis, best.split_coord, best.updates);
		if (!best.is_valid()) {
			//
			// make a leaf and be done.
			//

			//if (verbosity >= 5) sys::log("making a leaf with %d triangles.\n", tcount);
			//max_stuffed_leaf = max_stuffed_leaf > int_t(tcount) ? max_stuffed_leaf : tcount;
			node.is_leaf = true;
			node.items	= l3.heads[0];
			node.count	= tcount;

			//node.cell	= cell;	// debug, dump etc...

			compiler.stats.num_ids += tcount;
			compiler.stats.num_max_ids = std::max(compiler.stats.num_max_ids, int(tcount));

			++compiler.stats.num_leaves;
			if (tcount == 0)
				++compiler.stats.num_leaves_empty;
		}
		else {
			//
			// split and spawn 2 children.
			//

			const int k = best.axis, ku = get_other_axis(k), kv = get_other_axis(k+1);
			// split, build 2 nodes, recurse
			aabb_t cell_l(node.cell);
			aabb_t cell_r(node.cell);
			cell_l.pmax[k] = best.split_coord;
			cell_r.pmin[k] = best.split_coord;

#if 0
			{
				/*
					First pass on the winning axis where we tag with the side they'll end up in 
					each 'triangle', or better said, their lbox_t proxy, exactly like it was done when scoring.

					We do not modify anything else. Yet.
				*/
				const float			split = best.split_coord;
				const sideness_t	planar_side(sideness_t(best.planar_side));
				const uint_t		axis = best.axis;

				list_categorize(l3.heads[axis], axis, split, planar_side);
				// debug
			}
#endif
#if 0
			if (1) {
				// verif.
				enum { axis = 0 };
				int num_l = 0, num_r = 0, num_clip = 0, num_plan = 0;
				sideness_t side;
				const lbox_t * __restrict p = l3.heads[axis].extract(side);
				for (; p; p = p->dim[axis][side].next.extract(side)) {
					if (side == side_left) {
						num_l += p->flags.tag_side == side_left  ? 1 : 0;
						num_r += p->flags.tag_side == side_right ? 1 : 0;
						num_clip += p->flags.tag_clipped ? 1 : 0;
						num_plan += p->flags.tag_planar ? 1 : 0;
					}
				}
				num_r += num_clip;

				sys::log("count %d, axis %d, score: %d/%d/c%d/p%d tag: %d/%d/c%d/p%d\n",
					tcount, best.axis, 
					best.scored_lefts,
					best.scored_rights,
					best.num_cross,
					best.num_planar,

					num_l, num_r, num_clip, num_plan);


				// exit(0);
			}
#endif


			list3d_t l3_left, l3_right;
			std::memset(&l3_left, 0, sizeof(list3d_t));
			std::memset(&l3_right, 0, sizeof(list3d_t));


			int nl = 0, nr = 0;

			const bool_t
				empty_left = (best.scored_lefts == 0),
				empty_right = (best.scored_rights == 0),
				has_empty_side = empty_left | empty_right;

			// shortcut.
			if (has_empty_side) {
				if (empty_left) {
					for (uint_t axis=0; axis<3; ++axis)
						l3_right.heads[axis] = l3.heads[axis];

					nl = 0;
					nr = tcount;
				}
				else {
					for (uint_t axis=0; axis<3; ++axis)
						l3_left.heads[axis] = l3.heads[axis];

					nl = tcount;
					nr = 0;
				}
			}
			else {
				/*
					First pass on the winning axis where we tag with the side they'll end up in 
					each 'triangle', or better said, their lbox_t proxy, exactly like it was done when scoring.

					We do not modify anything else. Yet.
				*/
				{
					const float			split = best.split_coord;
					const sideness_t	planar_side(sideness_t(best.planar_side));
					//const uint_t		axis = best.axis;

					const float
						clamp_low = node.cell.pmin[k],
						clamp_mid = split,
						clmap_high = node.cell.pmax[k];
					
					// sys::log("lvl %2d: axis %d, count %5d, %d/%d/c %d/p %d.\n", lvl, axis, tcount, best.num_l, best.num_r, best.num_cross, best.num_planar);

					sideness_t side, prev_side(side_left);
					lbox_t * __restrict p = l3.heads[k].extract(side);

					// for triangles crossing the clip plane...
					sided_list_t<side_right>	park_left_end;	// store the clipped right side ending in the left node
					//sided_list_t<side_left>		park_right;		// store the clipped left side ending in the right node

					while (p) {
						// the left side *must* appear first.
						if (side == side_left) {
							// categorize, once.
							p->set_category(k, split, planar_side);

							if (1) {
								p->dim[k][side_left].pos	= maxf(p->dim[k][side_left].pos, node.cell.pmin[k]);
								p->dim[k][side_right].pos	= minf(p->dim[k][side_right].pos, node.cell.pmax[k]);

								p->dim[ku][side_left].pos	= maxf(p->dim[ku][side_left].pos, node.cell.pmin[ku]);
								p->dim[ku][side_right].pos	= minf(p->dim[ku][side_right].pos, node.cell.pmax[ku]);

								p->dim[kv][side_left].pos	= maxf(p->dim[kv][side_left].pos, node.cell.pmin[kv]);
								p->dim[kv][side_right].pos	= minf(p->dim[kv][side_right].pos, node.cell.pmax[kv]);
							}

							if (p->flags.tag_clipped) {
								// first, clone it.
								lbox_t *r = compiler.pools.lboxen.allocate();
								*r = *p;

								// rewire other axis
								r->dim[ku][side_left].next = p->dim[ku][side_left].next;
								p->dim[ku][side_left].next.set(r, side_left);
								r->dim[ku][side_right].next = p->dim[ku][side_right].next;
								p->dim[ku][side_right].next.set(r, side_right);

								r->dim[kv][side_left].next = p->dim[kv][side_left].next;
								p->dim[kv][side_left].next.set(r, side_left);
								r->dim[kv][side_right].next = p->dim[kv][side_right].next;
								p->dim[kv][side_right].next.set(r, side_right);

								// p's right side wasn't yet treated, it's going to be stuffed at the end of the left node list
								// we'll substitute the cloned right side instead, on the right node list.
								// that's why we need a ref.
								p->dim[k][side_right].pos = split;
								p->clone = r;	

								r->dim[k][side_left].pos = split;
								r->flags.tag_side = side_right;


								l3_left.append(k,  p, side_left);		// left side of the initial lbox on the left node
								l3_right.append(k, r, side_left);		// left side of the cloned lbox on the right node

								// at this point, there's still the right side of the original lbox sitting in this axis list,
								// we'll come to it later, and the right side of the cloned lbox isn't yet hooked.
							}
							else if (p->flags.tag_side == side_left) {
								l3_left.append(k, p, side_left);
							}
							else {
								l3_right.append(k, p, side_left);
							}

							// next!
							p = p->dim[k][side_left].next.extract(side);
						}
						// right side
						else {
							if (p->flags.tag_clipped) {
								// tada!
								// must be tagged as side_left as side_right never got linked into this axis.
								// substitute the cloned/clipped right side, park the original.
								park_left_end.append(k, p);
								l3_right.append(k, p->clone, side_right);
							}
							else if (p->flags.tag_side == side_left) {
								l3_left.append(k, p, side_right);
							}
							else {
								l3_right.append(k, p, side_right);
							}

							// next!
							p = p->dim[k][side_right].next.extract(side);
						}
					}

					// join what we've parked for the left node and close those lists.
					park_left_end.stopgap(k);
					l3_left.append(k, park_left_end.head, side_right);
					
					l3_right.stopgap(k);
				}


				//
				//	Other axis.
				//
				for (uint_t i=1; i<3; ++i) {
					const int axis = (k+i)%3;

					sideness_t side, tail_l_side = side_left, tail_r_side = side_left;
					lbox_t::ptr_t	head_l, head_r;

					head_l.set_null();
					head_r.set_null();

					int pop_l = 0, pop_r = 0;
					
					lbox_t 
						* __restrict p = l3.heads[axis].extract(side),
						* __restrict tail_l = 0,
						* __restrict tail_r = 0;
					for (; p; p = p->dim[axis][side].next.extract(side)) {
						if (p->flags.tag_side == side_left) {
							if (head_l.is_null()) 
								head_l.set(p, side);
							if (tail_l)
								tail_l->dim[axis][tail_l_side].next.set(p, side);

							tail_l = p;
							tail_l_side = side;
							++pop_l;
						}
						else {
							if (head_r.is_null()) 
								head_r.set(p, side);
							if (tail_r)
								tail_r->dim[axis][tail_r_side].next.set(p, side);

							tail_r = p;
							tail_r_side = side;
							++pop_r;
						}
					}

					if (tail_l)
						tail_l->dim[axis][tail_l_side].next.set_null();
					if (tail_r)
						tail_r->dim[axis][tail_r_side].next.set_null();

					l3_left.heads[axis] = head_l;
					l3_right.heads[axis] = head_r;

					nl = pop_l/2;
					nr = pop_r/2;
				}
			}

			//not true until we duplicate clipped tri, 
			// const int nl = best.scored_lefts , nr = best.scored_rights;

			//
			// let's pretend we got it right.
			//

			//static void do_build(hot_potato_t &hp, const uint_t tcount, const aabb_t &cell) throw() {

			//FIXSMP: nein. pools should be a per cpu/thread thing.
			node_t 
				*node_left	= compiler.pools.nodes.allocate(),
				*node_right	= compiler.pools.nodes.allocate();
			node_left->cell = cell_l;
			node_right->cell = cell_r;

			node.is_leaf		= false;
			node.split_axis		= best.axis;
			node.split_coord	= best.split_coord;
			node.left			= node_left;
			node.right			= node_right;

			compiler.stats.num_space_cuts += best.is_space_cut ? 1 : 0;
			compiler.stats.num_nodes += 2;


			// for now we don't remove any triangle, so...
			do_build(compiler,sah, l3_left,		nl,	*node_left,		lvl+1,	(addr<<1)|1ull);
			do_build(compiler,sah, l3_right,	nr,	*node_right,	lvl+1,	(addr<<1)|0ull);
		}
	}







	int compiler_t::compile(const SAH::heuristic_t &sah) {
		stats.max_lvl			= 0;
		stats.num_ids			= 0;
		stats.num_leaves		= 0;
		stats.num_leaves_empty	= 0;
		stats.num_space_cuts	= 0;
		stats.num_max_ids		= 0;
		stats.num_nodes			= 1;
		stats.num_ids			= 0;

		// sys::log("kdlib::compiler_t::compile:\n");
		
		const sys::laps_t laps;

		root.cell = state.scene_bbox;
		do_build(*this, sah, state.l3, state.tcount, root, 0, 1);

		const double 
			dt(sys::laps_t::to_time(laps.elapsed())),

			leaves = double(stats.num_leaves),
			leaves_empty = double(stats.num_leaves_empty),
			leaves_non_empty = double(stats.num_leaves-stats.num_leaves_empty),
			ratio_empty = leaves_empty / leaves,
			avg_elements = double(stats.num_ids) / leaves_non_empty;

		sys::log("compiler_t::compile(): %.0f ms\n\tmax_lvl %d\n\tnum_nodes %d\n\tnum_max_ids %d (%.2f avg/leaf)\n\tnum_leaves %d\n\tnum_leaves_empty %d (%.1f %%)\n\tnum_space_cuts %d\n\tnum_ids %d\n",
			dt,
			stats.max_lvl,
			stats.num_nodes,
			stats.num_max_ids, avg_elements,
			stats.num_leaves,
			stats.num_leaves_empty, 100.*ratio_empty,
			stats.num_space_cuts,
			stats.num_ids);

		return -1;
	}

}



