primitive.cpp

使用stl技术,(还没看,是听说的)

// ---------------------------------------------------------------------------------------------------------------------------------
//             _           _ _   _                                 
//            (_)         (_) | (_)                                
//  _ __  _ __ _ _ __ ___  _| |_ ___   __ ___      ___ _ __  _ __  
// | '_ \| '__| | '_ ` _ \| | __| \ \ / // _ \    / __| '_ \| '_ \ 
// | |_) | |  | | | | | | | | |_| |\ V /|  __/ _ | (__| |_) | |_) |
// | .__/|_|  |_|_| |_| |_|_|\__|_| \_/  \___|(_) \___| .__/| .__/ 
// | |                                                | |   | |    
// |_|                                                |_|   |_|    
//
// Description:
//
//   Octree class -- need I say more?
//
// Notes:
//
//   Best viewed with 8-character tabs and (at least) 132 columns
//
// History:
//
//   06/25/2001 by Paul Nettle: Original creation
//
// Restrictions & freedoms pertaining to usage and redistribution of this software:
//
//   This software is 100% free. If you use this software (in part or in whole) you must credit the author. This software may not be
//   re-distributed (in part or in whole) in a modified form without clear documentation on how to obtain a copy of the original
//   work. You may not use this software to directly or indirectly cause harm to others. This software is provided as-is and without
//   warrantee -- Use at your own risk. For more information, visit HTTP://www.FluidStudios.com/
//
// Copyright 2002, Fluid Studios, Inc., all rights reserved.
// ---------------------------------------------------------------------------------------------------------------------------------
//
// 09/25/2003 - removed <windows.h> include [Stephan Kaiser]
// ---------------------------------------------------------------------------------------------------------------------------------

#include "../../include/geom/geom"
using namespace geom;

// ---------------------------------------------------------------------------------------------------------------------------------

static	const	float	EPSILON = 1.0e-5f;

// ---------------------------------------------------------------------------------------------------------------------------------

int	Primitive::calcPrimaryAxisIndex() const
{
	// Calculate |normal|

	Vector3	absNormal = plane().normal();
	absNormal.abs();

	// Primary axis == X

	if (absNormal.x() >= absNormal.y() && absNormal.x() >= absNormal.z())
	{
		return 0;
	}

	// Primary axis == Y

	else if (absNormal.y() >= absNormal.x() && absNormal.y() >= absNormal.z())
	{
		return 1;
	}

	// Primary axis == Z

	else
	{
		return 2;
	}
}

// ---------------------------------------------------------------------------------------------------------------------------------

void	Primitive::setWorldTexture(const float uScale, const float vScale)
{
	// Primary axis index

	int	paIndex = calcPrimaryAxisIndex();

	// Primary axis == X

	if (paIndex == 0)
	{
		for (unsigned int i = 0; i < uv().size(); ++i)
		{
	        	uv()[i].x() =  xyz()[i].z() * uScale;
			uv()[i].y() = -xyz()[i].y() * vScale;
		}
	}

	// Primary axis == Y

	else if (paIndex == 1)
	{
		for (unsigned int i = 0; i < uv().size(); ++i)
		{
	        	uv()[i].x() =  xyz()[i].x() * uScale;
			uv()[i].y() = -xyz()[i].z() * vScale;
		}
	}

	// Primary axis == Z

	else if (paIndex == 2)
	{
		for (unsigned int i = 0; i < uv().size(); ++i)
		{
	        	uv()[i].x() =  xyz()[i].x() * uScale;
			uv()[i].y() = -xyz()[i].y() * vScale;
		}
	}
}

// ---------------------------------------------------------------------------------------------------------------------------------

const	Point3	Primitive::calcCenterOfMass() const
{
	Point3	center(0.0f, 0.0f, 0.0f);
	if (xyz().size() < 1) return center;

	for (unsigned int i = 0; i < xyz().size(); ++i)
	{
		center += xyz()[i];
	}

	return center / static_cast<float>(xyz().size());
}

// ---------------------------------------------------------------------------------------------------------------------------------

void	Primitive::calcPlane(const bool counterClock)
{
	plane().origin() = xyz()[0];
	Vector3	v0 = xyz()[1] - xyz()[0];
	Vector3	v1 = xyz()[2] - xyz()[1];
	plane().vector() = v1 % v0;
	if (!counterClock) plane().vector() = -plane().vector();
}

// ---------------------------------------------------------------------------------------------------------------------------------
// This calcArea() routine works for convex & concave polygons. It was adapted from a 2D algorithm presented in Computer Graphics
// Principles & Practice 2ed (Foley/vanDam/Feiner/Hughes) p. 477
// ---------------------------------------------------------------------------------------------------------------------------------

float	Primitive::calcArea() const
{
	float	xyArea = 0.0f;
	float	yzArea = 0.0f;
	float	zxArea = 0.0f;

	unsigned int	v0 = xyz().size() - 1;
	for (unsigned int v1 = 0; v1 < xyz().size(); v0 = v1, ++v1)
	{
		const Point3	&p0 = xyz()[v0];
		const Point3	&p1 = xyz()[v1];

		xyArea += (p0.y() + p1.y()) * (p1.x() - p0.x()) / 2.0f;
		yzArea += (p0.z() + p1.z()) * (p1.y() - p0.y()) / 2.0f;
		zxArea += (p0.x() + p1.x()) * (p1.z() - p0.z()) / 2.0f;
	}

	return static_cast<float>(sqrt(xyArea * xyArea + yzArea * yzArea + zxArea * zxArea));
}

// ---------------------------------------------------------------------------------------------------------------------------------

bool	Primitive::inside(const Point3 &p, const float epsilon) const
{
	int	pos = 0;
	int	neg = 0;
	Point3	center = calcCenterOfMass();
	Point3	normal = plane().normal();

	unsigned int	v0 = xyz().size() - 1;
	for (unsigned int v1 = 0; v1 < xyz().size(); v0 = v1, ++v1)
	{
		const Point3	&p0 = xyz()[v0];
		const Point3	&p1 = xyz()[v1];

		// Generate a normal for this edge

		Vector3	n = (p1 - p0) % normal;

		// Which side of this edge-plane is the point?

		float	halfPlane = (p ^ n) - (p0 ^ n);

		// Keep track of positives & negatives (but not zeros -- which means it's on the edge)

		if (halfPlane > epsilon) pos++;
		else if (halfPlane < -epsilon) neg++;

		// Early-out

		if (pos && neg) return false;
	}

	// If they're ALL positive, or ALL negative, then it's inside

	if (!pos || !neg) return true;

	// Must not be inside, because some were pos and some were neg

	return false;

}

// ---------------------------------------------------------------------------------------------------------------------------------
// This one is less accurate and slower, but considered "standard"
// ---------------------------------------------------------------------------------------------------------------------------------

bool	Primitive::inside2(const Point3 &p, const float epsilon) const
{
	float	total = -2.0f * fstl::pi<float>();

	Point3	p0 = p - xyz()[xyz().size() - 1];
	p0.normalize();

	for (unsigned int i = 0; i < xyz().size(); ++i)
	{
		Point3	p1 = p - xyz()[i];
		p1.normalize();
		float	t = p0 ^ p1;
		// Protect acos() input
		if (t < -1) t = -1;
		if (t > 1) t = 1;
		total += static_cast<float>(acos(t));
		p0 = p1;
	}

	if (fabs(total) > epsilon) return false;
	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

bool	Primitive::isConvex(const float epsilon) const
{
	// Center point

	Point3	center = calcCenterOfMass();

	// Visit each edge, make a plane, and verify that all vertices are on the same side of the plane

	int	v0 = xyz().size() - 1;
	for (unsigned int v1 = 0; v1 < xyz().size(); v0 = v1, ++v1)
	{
		const Point3 &	p0 = xyz()[v0];
		const Point3 &	p1 = xyz()[v1];

		// Generate an edge normal

		Plane3	edgePlane(p0, (p1 - p0) % plane().normal());

		// Make sure it points inward

		if (edgePlane.distance(center) < 0) edgePlane.vector() = -edgePlane.vector();

		// Test all vertices against this plane

		for (unsigned int i = 0; i < xyz().size(); ++i)
		{
			// Don't bother testing against the same points tha formed the plane

			if (i == v0 || i == v1) continue;

			// Is this point on the wrong side of the plane?

			float	dist  = edgePlane.distance(xyz()[i]);
			if (dist < -epsilon) return false;
		}
	}

	// If we made it here, we're convex

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

bool	Primitive::isPlanar(const float epsilon) const
{
	// Visit each vertex and verify that it is on the plane

	for (unsigned int i = 0; i < xyz().size(); ++i)
	{
		const Point3 &	p = xyz()[i];
		if (plane().distance(p) > epsilon) return false;
	}

	// If we made it here, we're planar

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

void	Primitive::removeLinearVertices(const float epsilon)
{
	if (xyz().size() < 3) return;

	// We wind around the polygon, looking for linear edges. Note that the edge (n-1, 0, 1) to be a linear edge, since most
	// ngons are fanned from the base (0) vertex, and removing that vertex would not be good. :)

	geom::Point3Array	newXYZ;
	geom::Point2Array	newUV;

	newXYZ += xyz()[0];
	newUV += uv()[0];

	for (unsigned int v0 = 0; v0 < xyz().size() - 1; ++v0)
	{
		unsigned int	v1 = v0 + 1;
		unsigned int	v2 = v1 + 1; if (v2 >= xyz().size()) v2 = 0;

		geom::Vector3	longEdge = xyz()[v1] - xyz()[v0];
		longEdge.normalize();
		geom::Vector3	shrtEdge = xyz()[v2] - xyz()[v1];
		shrtEdge.normalize();

		if ((longEdge ^ shrtEdge) <= (1-epsilon))
		{
			newXYZ += xyz()[v1];
			newUV += uv()[v1];
		}
	}

	xyz() = newXYZ;
	uv() = newUV;
}

// ---------------------------------------------------------------------------------------------------------------------------------

Point3	Primitive::closestPointOnPerimeter(const Point3 &p, Point3 &e0, Point3 &e1, bool &edgeFlag) const
{
	bool	found = false;
	float	closestDistance = 0.0f;
	Point3	closestPoint = Point3::zero();
	Point3	closestP0, closestP1;
	int	closestIndex;

	unsigned int	v0 = xyz().size() - 1;
	int	index = 0;
	for (unsigned int v1 = 0; v1 < xyz().size(); ++v1, index++)
	{
		const Point3	&p0 = xyz()[v0];
		const Point3	&p1 = xyz()[v1];

		bool	edge;
		Point3	cp = closestPointOnLineSegment(p0, p1, p, edge);
		float	d = cp.distance(p);

		if (!found || d < closestDistance)
		{
			closestDistance = d;
			closestPoint = cp;
			closestP0 = p0;
			closestP1 = p1;
			edgeFlag = edge;
			closestIndex = index;
			found = true;
		}

		v0 = v1;
	}

	if (!edgeFlag)
	{
		int	a = closestIndex - 1; if (a < 0) a = xyz().size() - 1;
		int	b = closestIndex + 1; if (b >= static_cast<int>(xyz().size())) b = 0;
		e0 = xyz()[a];