// K-3D
// Copyright (c) 1995-2004, Timothy M. Shead
//
// Contact: tshead@k-3d.com
//
// This program 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 2 of the License, or (at your option) any later version.
//
// 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#include "mesh.h"
#include "result.h"
#include "utility.h"

#include <algorithm>

namespace k3d
{

/////////////////////////////////////////////////////////////////////////////
// point

point::point(const vector3& Position) :
	position(Position)
{
}

point::point(const double X, const double Y, const double Z) :
	position(X, Y, Z)
{
}

/////////////////////////////////////////////////////////////////////////////
// point_group

point_group::point_group() :
	material(0)
{
}

/////////////////////////////////////////////////////////////////////////////
// split_edge

/////////////////////////////////////////////////////////////////////////////
// face

face::face(split_edge* FirstEdge) :
	first_edge(FirstEdge)
{
}

/////////////////////////////////////////////////////////////////////////////
// normal

vector3 normal(const split_edge* const Loop)
{
	/// Calculates the normal for an edge loop using the summation method, which is more robust than the three-point methods (handles zero-length edges)
	vector3 result(0, 0, 0);

	for(const split_edge* edge = Loop; edge && edge->face_clockwise; edge = edge->face_clockwise)
		{
			const vector3& i = edge->vertex->position;
			const vector3& j = edge->face_clockwise->vertex->position;

			result[0] += (i[1] + j[1]) * (j[2] - i[2]);
			result[1] += (i[2] + j[2]) * (j[0] - i[0]);
			result[2] += (i[0] + j[0]) * (j[1] - i[1]);

			if(Loop == edge->face_clockwise)
				break;
		}

	return 0.5 * result;
}

vector3 normal(const face& Face)
{
	return normal(Face.first_edge);
}

/////////////////////////////////////////////////////////////////////////////
// polyhedron

polyhedron::polyhedron() :
	type(POLYGONS),
	material(0)
{
}

polyhedron::~polyhedron()
{
	std::for_each(faces.begin(), faces.end(), delete_object());
	std::for_each(edges.begin(), edges.end(), delete_object());
}

std::ostream& operator<<(std::ostream& Stream, const polyhedron::type_t& RHS)
{
	switch(RHS)
		{
			case polyhedron::POLYGONS:
				Stream << "polygons";
				break;
			case polyhedron::CATMULL_CLARK_SUBDIVISION_MESH:
				Stream << "catmull_clark";
				break;
		}

	return Stream;
}

std::istream& operator>>(std::istream& Stream, polyhedron::type_t& RHS)
{
	std::string buffer;
	Stream >> buffer;

//std::cerr << debug << __PRETTY_FUNCTION__ << " " << buffer << std::endl;

	if(buffer == "polygons")
		RHS = polyhedron::POLYGONS;
	else if(buffer == "catmull_clark")
		RHS = polyhedron::CATMULL_CLARK_SUBDIVISION_MESH;
	else
		std::cerr << error << "Unknown polyhedron type [" << buffer << "]" << std::endl;

	return Stream;
}

/////////////////////////////////////////////////////////////////////////////
// linear_curve

/////////////////////////////////////////////////////////////////////////////
// linear_curve_group

linear_curve_group::linear_curve_group() :
	wrap(false),
	material(0)
{
}

linear_curve_group::~linear_curve_group()
{
	std::for_each(curves.begin(), curves.end(), delete_object());
}

/////////////////////////////////////////////////////////////////////////////
// cubic_curve

/////////////////////////////////////////////////////////////////////////////
// cubic_curve_group

cubic_curve_group::cubic_curve_group() :
	wrap(false),
	material(0)
{
}

cubic_curve_group::~cubic_curve_group()
{
	std::for_each(curves.begin(), curves.end(), delete_object());
}

/////////////////////////////////////////////////////////////////////////////
// nucurve

nucurve::nucurve() :
	order(2)
{
}

/////////////////////////////////////////////////////////////////////////////
// nucurve_group

nucurve_group::nucurve_group() :
	material(0)
{
}

nucurve_group::~nucurve_group()
{
	std::for_each(curves.begin(), curves.end(), delete_object());
}

/////////////////////////////////////////////////////////////////////////////
// bilinear_patch

bilinear_patch::bilinear_patch() :
	material(0)
{
}

/////////////////////////////////////////////////////////////////////////////
// bicubic_patch

bicubic_patch::bicubic_patch() :
	material(0)
{
}

/////////////////////////////////////////////////////////////////////////////
// nupatch

nupatch::nupatch() :
	u_order(2),
	v_order(2),
	material(0)
{
}

/////////////////////////////////////////////////////////////////////////////
// blobby

blobby::blobby(opcode* Opcode) :
	root(Opcode),
	material(0)
{
}

blobby::~blobby()
{
	delete root;
}

void blobby::accept(visitor& Visitor)
{
	if(root)
		root->accept(Visitor);
}

/////////////////////////////////////////////////////////////////////////////
// blobby::constant

blobby::constant::constant(double Value) :
	value(Value)
{
}

blobby::opcode* blobby::constant::clone()
{
	return new constant(*this);
}

void blobby::constant::accept(visitor& Visitor)
{
	Visitor.visit_constant(*this);
}

/////////////////////////////////////////////////////////////////////////////
// blobby::ellipsoid

blobby::ellipsoid::ellipsoid(point* Origin, const matrix4& Transformation) :
	origin(Origin),
	transformation(Transformation)
{
}

blobby::opcode* blobby::ellipsoid::clone()
{
	return new ellipsoid(*this);
}

void blobby::ellipsoid::accept(visitor& Visitor)
{
	Visitor.visit_ellipsoid(*this);
}

////////////////////////////////////////////////////////////////////////////
// blobby::segment

blobby::segment::segment(point* Start, point* End, double Radius, const matrix4& Transformation) :
	start(Start),
	end(End),
	radius(Radius),
	transformation(Transformation)
{
}

blobby::opcode* blobby::segment::clone()
{
	return new segment(*this);
}

void blobby::segment::accept(visitor& Visitor)
{
	Visitor.visit_segment(*this);
}

/////////////////////////////////////////////////////////////////////////////
// blobby::subtract

blobby::subtract::subtract(opcode* Subtrahend, opcode* Minuend) :
	subtrahend(Subtrahend),
	minuend(Minuend)
{
}

blobby::subtract::~subtract()
{
	delete subtrahend;
	delete minuend;
}

blobby::opcode* blobby::subtract::clone()
{
	return new subtract(subtrahend->clone(), minuend->clone());
}

void blobby::subtract::accept(visitor& Visitor)
{
	Visitor.visit_subtract(*this);
}

////////////////////////////////////////////////////////////////////////////
// blobby::divide

blobby::divide::divide(opcode* Dividend, opcode* Divisor) :
	dividend(Dividend),
	divisor(Divisor)
{
}

blobby::divide::~divide()
{
	delete dividend;
	delete divisor;
}

blobby::opcode* blobby::divide::clone()
{
	return new divide(dividend->clone(), divisor->clone());
}

void blobby::divide::accept(visitor& Visitor)
{
	Visitor.visit_divide(*this);
}

////////////////////////////////////////////////////////////////////////////////////////
// blobby::variable_operands

void blobby::variable_operands::add_operand(blobby::opcode* Operand)
{
	operands.push_back(Operand);
}

void blobby::variable_operands::operands_accept(visitor& Visitor)
{
	for(operands_t::iterator operand = operands.begin(); operand != operands.end(); ++operand)
		(*operand)->accept(Visitor);
}

blobby::variable_operands::~variable_operands()
{
	std::for_each(operands.begin(), operands.end(), delete_object());
}

void blobby::variable_operands::clone_operands()
{
	for(operands_t::iterator operand = operands.begin(); operand != operands.end(); ++operand)
		(*operand) = (*operand)->clone();
}

////////////////////////////////////////////////////////////////////////////////////////
// blobby::add

blobby::opcode* blobby::add::clone()
{
	add* result = new add(*this);
	result->clone_operands();
	return result;
}

void blobby::add::accept(visitor& Visitor)
{
	Visitor.visit_add(*this);
}

////////////////////////////////////////////////////////////////////////////////////////
// blobby::multiply

blobby::opcode* blobby::multiply::clone()
{
	multiply* result = new multiply(*this);
	result->clone_operands();
	return result;
}

void blobby::multiply::accept(visitor& Visitor)
{
	Visitor.visit_multiply(*this);
}

////////////////////////////////////////////////////////////////////////////////////////
// blobby::max

blobby::opcode* blobby::max::clone()
{
	max* result = new max(*this);
	result->clone_operands();
	return result;
}

void blobby::max::accept(visitor& Visitor)
{
	Visitor.visit_max(*this);
}

////////////////////////////////////////////////////////////////////////////////////////
// blobby::min

blobby::opcode* blobby::min::clone()
{
	min* result = new min(*this);
	result->clone_operands();
	return result;
}

void blobby::min::accept(visitor& Visitor)
{
	Visitor.visit_min(*this);
}

/////////////////////////////////////////////////////////////////////////////
// mesh

mesh::mesh()
{
}

mesh::~mesh()
{
	std::for_each(bicubic_patches.begin(), bicubic_patches.end(), delete_object());
	std::for_each(bilinear_patches.begin(), bilinear_patches.end(), delete_object());
	std::for_each(cubic_curve_groups.begin(), cubic_curve_groups.end(), delete_object());
	std::for_each(linear_curve_groups.begin(), linear_curve_groups.end(), delete_object());
	std::for_each(polyhedra.begin(), polyhedra.end(), delete_object());
	std::for_each(point_groups.begin(), point_groups.end(), delete_object());
	std::for_each(points.begin(), points.end(), delete_object());
}

/////////////////////////////////////////////////////////////////////////////
// add_unit_cube

void add_unit_cube(mesh& Mesh, polyhedron& Polyhedron)
{
	// Create points ...
	boost::multi_array<point*, 3> points(boost::extents[2][2][2]);
	points[0][0][0] = new point(-0.5, -0.5, -0.5);
	points[1][0][0] = new point(0.5, -0.5, -0.5);
	points[1][1][0] = new point(0.5, 0.5, -0.5);
	points[0][1][0] = new point(-0.5, 0.5, -0.5);
	points[0][0][1] = new point(-0.5, -0.5, 0.5);
	points[1][0][1] = new point(0.5, -0.5, 0.5);
	points[1][1][1] = new point(0.5, 0.5, 0.5);
	points[0][1][1] = new point(-0.5, 0.5, 0.5);

	for(unsigned long i = 0; i != 2; ++i)
		for(unsigned long j = 0; j != 2; ++j)
			for(unsigned long k = 0; k != 2; ++k)
				Mesh.points.push_back(points[i][j][k]);

	// Create edges ...
	boost::multi_array<split_edge*, 2> edges(boost::extents[6][4]);
	edges[0][0] = new split_edge(points[0][1][0]);
	edges[0][1] = new split_edge(points[1][1][0]);
	edges[0][2] = new split_edge(points[1][0][0]);
	edges[0][3] = new split_edge(points[0][0][0]);

	edges[1][0] = new split_edge(points[1][1][0]);
	edges[1][1] = new split_edge(points[1][1][1]);
	edges[1][2] = new split_edge(points[1][0][1]);
	edges[1][3] = new split_edge(points[1][0][0]);

	edges[2][0] = new split_edge(points[1][1][1]);
	edges[2][1] = new split_edge(points[0][1][1]);
	edges[2][2] = new split_edge(points[0][0][1]);
	edges[2][3] = new split_edge(points[1][0][1]);

	edges[3][0] = new split_edge(points[0][1][1]);
	edges[3][1] = new split_edge(points[0][1][0]);
	edges[3][2] = new split_edge(points[0][0][0]);
	edges[3][3] = new split_edge(points[0][0][1]);

	edges[4][0] = new split_edge(points[0][1][1]);
	edges[4][1] = new split_edge(points[1][1][1]);
	edges[4][2] = new split_edge(points[1][1][0]);
	edges[4][3] = new split_edge(points[0][1][0]);

	edges[5][0] = new split_edge(points[0][0][0]);
	edges[5][1] = new split_edge(points[1][0][0]);
	edges[5][2] = new split_edge(points[1][0][1]);
	edges[5][3] = new split_edge(points[0][0][1]);

	edges[0][0]->companion = edges[4][2];
	edges[0][1]->companion = edges[1][3];
	edges[0][2]->companion = edges[5][0];
	edges[0][3]->companion = edges[3][1];

	edges[1][0]->companion = edges[4][1];
	edges[1][1]->companion = edges[2][3];
	edges[1][2]->companion = edges[5][1];
	edges[1][3]->companion = edges[0][1];

	edges[2][0]->companion = edges[4][0];
	edges[2][1]->companion = edges[3][3];
	edges[2][2]->companion = edges[5][2];
	edges[2][3]->companion = edges[1][1];

	edges[3][0]->companion = edges[4][3];
	edges[3][1]->companion = edges[0][3];
	edges[3][2]->companion = edges[5][3];
	edges[3][3]->companion = edges[2][1];

	edges[4][0]->companion = edges[2][0];
	edges[4][1]->companion = edges[1][0];
	edges[4][2]->companion = edges[0][0];
	edges[4][3]->companion = edges[3][0];

	edges[5][0]->companion = edges[0][2];
	edges[5][1]->companion = edges[1][2];
	edges[5][2]->companion = edges[2][2];
	edges[5][3]->companion = edges[3][2];

	for(unsigned long i = 0; i != 6; ++i)
		for(unsigned long j = 0; j != 4; ++j)
			edges[i][j]->face_clockwise = edges[i][(j+1)%4];

	for(unsigned long i = 0; i != 6; ++i)
		for(unsigned long j = 0; j != 4; ++j)
			Polyhedron.edges.push_back(edges[i][j]);

	// Create faces ...
	for(unsigned long i = 0; i != 6; ++i)
		Polyhedron.faces.push_back(new face(edges[i][0]));
}

/////////////////////////////////////////////////////////////////////////////
// add_grid

grid_results_t add_grid(mesh& Mesh, polyhedron& Polyhedron, const unsigned long Rows, const unsigned long Columns, const bool StitchTop, const bool StitchSide)
{
	// Sanity checks ...
	assert(Rows);
	assert(Columns);

	// Calculate the number of faces to create along each axis ...
	const unsigned long face_rows = Rows;
	const unsigned long face_columns = Columns;

	// Calculate the number of points that need to be created along each axis ...
	unsigned long point_rows = face_rows + (StitchTop ? 0 : 1);
	unsigned long point_columns = face_columns + (StitchSide ? 0 : 1);

	// Create points ...
	boost::multi_array<point*, 2> points(boost::extents[point_rows][point_columns]);
	for(unsigned long row = 0; row != point_rows; ++row)
		{
			for(unsigned long column = 0; column != point_columns; ++column)
				{
					points[row][column] = new point(0, 0, 0);
					Mesh.points.push_back(points[row][column]);
				}
		}

	// Create edges ...
	boost::multi_array<split_edge*, 3> edges(boost::extents[face_rows][face_columns][4]);
	for(unsigned long row = 0; row != face_rows; ++row)
		{
			for(unsigned long column = 0; column != face_columns; ++column)
				{
					edges[row][column][0] = new split_edge(points[row][column]);
					edges[row][column][1] = new split_edge(points[row][(column+1) % point_columns]);
					edges[row][column][2] = new split_edge(points[(row+1) % point_rows][(column+1) % point_columns]);
					edges[row][column][3] = new split_edge(points[(row+1) % point_rows][column]);

					for(unsigned long i = 0; i != 4; ++i)
						edges[row][column][i]->face_clockwise = edges[row][column][(i+1)%4];

					for(unsigned long i = 0; i != 4; ++i)
						Polyhedron.edges.push_back(edges[row][column][i]);
				}
		}

	// Join edges ...
	const unsigned long edge_rows = face_rows - (StitchTop ? 0 : 1);
	const unsigned long edge_columns = face_columns - (StitchSide ? 0 : 1);

	for(unsigned long row = 0; row != edge_rows; ++row)
		{
			for(unsigned long column = 0; column != face_columns; ++column)
				join_edges(*edges[row][column][2], *edges[(row+1) % face_rows][column][0]);
		}

	for(unsigned long column = 0; column != edge_columns; ++column)
		{
			for(unsigned long row = 0; row != face_rows; ++row)
				join_edges(*edges[row][column][1], *edges[row][(column+1) % face_columns][3]);
		}

	// Create faces ...
	boost::multi_array<face*, 2> faces(boost::extents[face_rows][face_columns]);
	for(unsigned long row = 0; row != face_rows; ++row)
		{
			for(unsigned long column = 0; column != face_columns; ++column)
				{
					face* const new_face = new face(edges[row][column][0]);
					Polyhedron.faces.push_back(new_face);
				}
		}

	return boost::make_tuple(points, edges, faces);
}

namespace detail
{

/// Provides a mapping of old-to-new points that can be used with std::transform
struct point_map_t :
	public std::map<point*, point*>,
	public blobby::visitor
{
	virtual ~point_map_t()
	{
	}

	point* operator()(point* Key)
	{
		return operator[](Key);
	}

	void visit_constant(blobby::constant& Constant)
	{
	}

	void visit_ellipsoid(blobby::ellipsoid& Ellipsoid)
	{
		Ellipsoid.origin = operator[](Ellipsoid.origin);
	}

	void visit_segment(blobby::segment& Segment)
	{
		Segment.start = operator[](Segment.start);
		Segment.end = operator[](Segment.end);
	}

	void visit_subtract(blobby::subtract& Subtract)
	{
		Subtract.subtrahend->accept(*this);
		Subtract.minuend->accept(*this);
	}

	void visit_divide(blobby::divide& Divide)
	{
		Divide.dividend->accept(*this);
		Divide.divisor->accept(*this);
	}

	void visit_add(blobby::add& Add)
	{
		Add.operands_accept(*this);
	}

	void visit_multiply(blobby::multiply& Multiply)
	{
		Multiply.operands_accept(*this);
	}

	void visit_min(blobby::min& Min)
	{
		Min.operands_accept(*this);
	}

	void visit_max(blobby::max& Max)
	{
		Max.operands_accept(*this);
	}
};

} // namespace detail

/////////////////////////////////////////////////////////////////////////////
// deep_copy

void deep_copy(const mesh& Input, mesh& Output)
{
	// Duplicate points ...
	detail::point_map_t point_map;
	point_map[0] = 0;
	for(mesh::points_t::const_iterator p = Input.points.begin(); p != Input.points.end(); ++p)
		{
			Output.points.push_back(new point(**p));
			point_map.insert(std::make_pair(*p, Output.points.back()));
		}

	// Duplicate point clouds ...
	for(mesh::point_groups_t::const_iterator pt_group = Input.point_groups.begin(); pt_group != Input.point_groups.end(); ++pt_group)
		{
			point_group* const new_point_group = new point_group(**pt_group);
			std::transform(new_point_group->points.begin(), new_point_group->points.end(), new_point_group->points.begin(), point_map);
			Output.point_groups.push_back(new_point_group);
		}

	// Duplicate polyhedra ...
	for(mesh::polyhedra_t::const_iterator pn = Input.polyhedra.begin(); pn != Input.polyhedra.end(); ++pn)
		{
			polyhedron* const new_polyhedron = new polyhedron(**pn);

			// Duplicate edges ...
			typedef std::map<split_edge*, split_edge*> edge_map_t;
			edge_map_t edge_map;
			edge_map[0] = 0;
			for(polyhedron::edges_t::iterator edge = new_polyhedron->edges.begin(); edge != new_polyhedron->edges.end(); ++edge)
				{
					split_edge* const new_edge = new split_edge(**edge);
					edge_map.insert(std::make_pair(*edge, new_edge));
					*edge = new_edge;
				}

			// Re-link edges ...
			for(edge_map_t::iterator edge = edge_map.begin(); edge != edge_map.end(); ++edge)
				{
					if(!edge->first)
						continue;

					edge->second->vertex = point_map[edge->second->vertex];
					edge->second->face_clockwise = edge_map.find(edge->second->face_clockwise)->second;
					edge->second->companion = edge_map.find(edge->second->companion)->second;
				}

			// Duplicate faces ...
			for(polyhedron::faces_t::iterator f = new_polyhedron->faces.begin(); f != new_polyhedron->faces.end(); ++f)
				{
					face* const new_face = new face(**f);
					new_face->first_edge = edge_map[new_face->first_edge];

					// Duplicate holes ...
					for(face::holes_t::iterator hole = new_face->holes.begin(); hole != new_face->holes.end(); ++hole)
						*hole = edge_map.find(*hole)->second;

					*f = new_face;
				}

			Output.polyhedra.push_back(new_polyhedron);
		}

	// Duplicate linear curve groups ...
	for(mesh::linear_curve_groups_t::const_iterator group = Input.linear_curve_groups.begin(); group != Input.linear_curve_groups.end(); ++group)
		{
			linear_curve_group* const new_group = new linear_curve_group(**group);

			for(linear_curve_group::curves_t::iterator curve = new_group->curves.begin(); curve != new_group->curves.end(); ++curve)
				{
					*curve = new linear_curve(**curve);
					std::transform((*curve)->control_points.begin(), (*curve)->control_points.end(), (*curve)->control_points.begin(), point_map);
				}

			Output.linear_curve_groups.push_back(new_group);
		}

	// Duplicate cubic curve groups ...
	for(mesh::cubic_curve_groups_t::const_iterator group = Input.cubic_curve_groups.begin(); group != Input.cubic_curve_groups.end(); ++group)
		{
			cubic_curve_group* const new_group = new cubic_curve_group(**group);

			for(cubic_curve_group::curves_t::iterator curve = new_group->curves.begin(); curve != new_group->curves.end(); ++curve)
				{
					*curve = new cubic_curve(**curve);
					std::transform((*curve)->control_points.begin(), (*curve)->control_points.end(), (*curve)->control_points.begin(), point_map);
				}

			Output.cubic_curve_groups.push_back(new_group);
		}

	// Duplicate nucurve groups ...
	for(mesh::nucurve_groups_t::const_iterator group = Input.nucurve_groups.begin(); group != Input.nucurve_groups.end(); ++group)
		{
			nucurve_group* const new_group = new nucurve_group(**group);

			for(nucurve_group::curves_t::iterator curve = new_group->curves.begin(); curve != new_group->curves.end(); ++curve)
				{
					*curve = new nucurve(**curve);
					for(nucurve::control_points_t::iterator control_point = (*curve)->control_points.begin(); control_point != (*curve)->control_points.end(); ++control_point)
						control_point->position = point_map[control_point->position];
				}

			Output.nucurve_groups.push_back(new_group);
		}

	// Duplicate bilinear patches ...
	for(mesh::bilinear_patches_t::const_iterator patch = Input.bilinear_patches.begin(); patch != Input.bilinear_patches.end(); ++patch)
		{
			bilinear_patch* const new_patch = new bilinear_patch(**patch);
			std::transform(new_patch->control_points.begin(), new_patch->control_points.end(), new_patch->control_points.begin(), point_map);

			Output.bilinear_patches.push_back(new_patch);
		}

	// Duplicate bicubic patches ...
	for(mesh::bicubic_patches_t::const_iterator patch = Input.bicubic_patches.begin(); patch != Input.bicubic_patches.end(); ++patch)
		{
			bicubic_patch* const new_patch = new bicubic_patch(**patch);
			std::transform(new_patch->control_points.begin(), new_patch->control_points.end(), new_patch->control_points.begin(), point_map);

			Output.bicubic_patches.push_back(new_patch);
		}

	// Duplicate nupatches ...
	for(mesh::nupatches_t::const_iterator patch = Input.nupatches.begin(); patch != Input.nupatches.end(); ++patch)
		{
			nupatch* const new_patch = new nupatch(**patch);
			for(nupatch::control_points_t::iterator control_point = new_patch->control_points.begin(); control_point != new_patch->control_points.end(); ++control_point)
				control_point->position = point_map[control_point->position];

			Output.nupatches.push_back(new_patch);
		}

	// Duplicate blobbies ...
	for(mesh::blobbies_t::const_iterator blob = Input.blobbies.begin(); blob != Input.blobbies.end(); blob++)
		{
			blobby* const new_blobby = new blobby((*blob)->root->clone());
			new_blobby->accept(point_map);

			Output.blobbies.push_back(new_blobby);
		}
}

/////////////////////////////////////////////////////////////////////////////
// is_valid

bool is_valid(const polyhedron& Polyhedron)
{
	// For every face ...
	for(polyhedron::faces_t::const_iterator face = Polyhedron.faces.begin(); face != Polyhedron.faces.end(); ++face)
		{
			// This is obviously wrong!!!
			return_val_if_fail(*face, false);
		}

	// For every edge ...
	for(polyhedron::edges_t::const_iterator edge = Polyhedron.edges.begin(); edge != Polyhedron.edges.end(); ++edge)
		{
			// This is obviously wrong!!!
			return_val_if_fail(*edge, false);

			// Every edge should have a vertex ...
			return_val_if_fail((*edge)->vertex, false);

			// Every edge should have a neighbor ...
			return_val_if_fail((*edge)->face_clockwise, false);

			// For edges with companions ...
			if((*edge)->companion)
				{
					// Companions had better point to each other ...
					return_val_if_fail((*edge)->companion->companion == (*edge), false);

					// Companions had better NOT share the same vertex ...
					return_val_if_fail((*edge)->vertex != (*edge)->companion->vertex, false);
				}
		}

	return true;
}

/////////////////////////////////////////////////////////////////////////////
// is_valid

bool is_valid(const nucurve& Curve)
{
	// Order must always be at least 2 (i.e. a linear curve)
	return_val_if_fail(Curve.order >= 2, false);

	// The number of control points must be >= order
	return_val_if_fail(Curve.control_points.size() >= Curve.order, false);

	// The number of knots must be equal to the number of control points plus the order
	return_val_if_fail(Curve.knots.size() == Curve.control_points.size() + Curve.order, false);

	// Knot vector values must always be in ascending order
	for(unsigned long i = 1; i != Curve.knots.size(); ++i)
		return_val_if_fail(Curve.knots[i] >= Curve.knots[i-1], false);

	return true;
}

/////////////////////////////////////////////////////////////////////////////
// is_valid

bool is_valid(const nupatch& Patch)
{
	// Order must always be at least 2 (i.e. linear curves), in each parametric direction
	return_val_if_fail(Patch.u_order >= 2 && Patch.v_order >= 2, false);

	// The number of control points must be >= order, in each parametric direction

	// The number of knots must be equal to the number of control points plus the order, in each parametric direction

	// Knot vector values must always be in ascending order, in each parametric direction
	for(unsigned long i = 1; i != Patch.u_knots.size(); ++i)
		return_val_if_fail(Patch.u_knots[i] >= Patch.u_knots[i-1], false);

	for(unsigned long i = 1; i != Patch.v_knots.size(); ++i)
		return_val_if_fail(Patch.v_knots[i] >= Patch.v_knots[i-1], false);

	return true;
}

/////////////////////////////////////////////////////////////////////////////
// is_solid

bool is_solid(const polyhedron& Polyhedron)
{
	if(!is_valid(Polyhedron))
		return false;

	if(Polyhedron.edges.empty())
		return false;

	for(polyhedron::edges_t::const_iterator edge = Polyhedron.edges.begin(); edge != Polyhedron.edges.end(); ++edge)
		{
			if(0 == (**edge).companion)
				return false;
		}

	return true;
}

/////////////////////////////////////////////////////////////////////////////
// bounds

const bounding_box bounds(const mesh& Mesh)
{
	bounding_box results;
	for(mesh::points_t::const_iterator point = Mesh.points.begin(); point != Mesh.points.end(); ++point)
		results.insert((*point)->position);

	return results;
}

} // namespace k3d