// Shave and a Haircut
// (c) 2019 Epic Games
// US Patent 6720962

#include <maya/MDagModifier.h>
#include <maya/MDagPath.h>
#include <maya/MDoubleArray.h>
#include <maya/MFloatMatrix.h>
#include <maya/MFloatPoint.h>
#include <maya/MFloatPointArray.h>
#include <maya/MFloatVector.h>
#include <maya/MFloatVectorArray.h>
#include <maya/MFn.h>
#include <maya/MFnDagNode.h>
#include <maya/MFnDependencyNode.h>
#include <maya/MFnDoubleIndexedComponent.h>
#include <maya/MFnLight.h>
#include <maya/MFnMeshData.h>
#include <maya/MFnNurbsSurface.h>
#include <maya/MFnSet.h>
#include <maya/MFnSingleIndexedComponent.h>
#include <maya/MFnSubd.h>
#include <maya/MFnSubdNames.h>
#include <maya/MGlobal.h>
#include <maya/MIntArray.h>
#include <maya/MItDag.h>
#include <maya/MItDependencyNodes.h>
#include <maya/MItMeshVertex.h>
#include <maya/MMatrix.h>
#include <maya/MObjectArray.h>
#include <maya/MPlug.h>
#include <maya/MPlugArray.h>
#include <maya/MPointArray.h>
#include <maya/MRenderUtil.h>
#include <maya/MSelectionList.h>
#include <maya/MTransformationMatrix.h>
#include <maya/MUint64Array.h>

#ifdef _WIN32
# include <process.h>
# include <stdlib.h>
# include <time.h>
# include <winsock2.h>
#else
# include <sys/times.h>
# include <unistd.h>
#endif

#include "shaveCheckObjectVisibility.h"
#include "shaveGlobals.h"
#include "shaveHairShape.h"
#include "shaveIO.h"
#include "shaveRender.h"
#include "shaveRenderer.h"
#include "shaveSDKTYPES.h"
#include "shaveUtil.h"

#if defined(OSMac_) && !defined(OSMac_MachO_)
#include "shaveMacCarbon.h"
#endif

std::vector<shaveUtil::LightInfo>	shaveUtil::globalLightList;
MDagPathArray						shaveUtil::mFields;
bool								shaveUtil::mFieldsDirty = true;
bool								shaveUtil::mIgnoreNextSelectionChange = false;
int									shaveUtil::mLoadDepth = 0;


void shaveUtil::buildLightList()
{
	MStatus	st;

	globalLightList.clear();

	//
	// Step through all the lights in the scene.
	//
	MItDag		iter(MItDag::kDepthFirst, MFn::kLight);
	LightInfo	info;

	for (; !iter.isDone(); iter.next())
	{
		iter.getPath(info.path);

		if (areObjectAndParentsVisible(info.path, false))
		{
			bool	addIt = false;

			//
			// If all lights are being used then add the light to the list.
			// Otherwise we only add it if it has had Shave shadow
			// attributes added to it.
			//
			if (useAllLightsGlob)
				addIt = true;
			else
			{
				MFnLight	lightFn(info.path);
				MPlug	plug = lightFn.findPlug("shaveShadowResolution", &st);

				if (st) addIt = true;
			}

			if (addIt)
			{
				//
				// In shaders, light info is passed in through attributes,
				// so we don't know which light it belongs to.  That makes
				// it difficult to determine the lightID to use in calls to
				// SHAVEilluminate_light.
				//
				// Fortunately, shaders are passed the light's blindData
				// pointer, which appears to be unique for each light.  So
				// by saving each light's blind data pointer, we can
				// provide a reverse lookup to give us the index into the
				// globalLightList.
				//
				MFnDagNode	nodeFn(info.path);
				MPlug		plug = nodeFn.findPlug("lightBlindData");

				info.blindData = getAddrPlugValue(plug);

				// We won't know the light IDs until we add register them
				// with Shave.
				//
				info.minId = -1;
				info.maxId = -1;

				globalLightList.push_back(info);
			}
		}
	}
}


void shaveUtil::classifyShaveNodes(
		const MObjectArray&	shaveHairShapes,
		bool&				haveHair,
		bool&				haveInstances
)
{
	haveHair = haveInstances = false;

	unsigned	i;

	for (i = 0; i < shaveHairShapes.length(); i++)
	{
		MFnDependencyNode	nodeFn(shaveHairShapes[i]);
		shaveHairShape*			nodePtr = (shaveHairShape*)nodeFn.userNode();

		if (nodePtr)
		{
			if (nodePtr->isInstanced())
				haveInstances = true;
			else
				haveHair = true;
		}
	}
}


int shaveUtil::compareShaveVersions(MString v1, MString v2)
{
	int	v1Parts[3];
	int	v2Parts[3];

	splitShaveVersion(v1, v1Parts);
	splitShaveVersion(v2, v2Parts);

	if (v1Parts[0] < v2Parts[0]) return -1;
	if (v1Parts[0] > v2Parts[0]) return 1;

	if (v1Parts[1] < v2Parts[1]) return -1;
	if (v1Parts[1] > v2Parts[1]) return 1;

	if (v1Parts[2] < v2Parts[2]) return -1;
	if (v1Parts[2] > v2Parts[2]) return 1;

	return 0;
}


//	Copy one full line of input to the output and return as much of it as
//	will fit in the buffer provided by the caller.
//
//	Returns false if there was no input left to read.
bool shaveUtil::fileCopyLine(
	FILE*			input,
	FILE*			output,
	char*			buffer,
	unsigned int	bufferSize
)
{
	if (!fgets(buffer, bufferSize, input)) return false;

	fputs(buffer, output);

	size_t	lineLen = strlen(buffer);

	//	Did we get a full line?
	//
	//	Note that CFM OSX uses '\r' for EOL, so we have to check for that
	//	as well.
	if ((lineLen > 0)
	&&	(buffer[lineLen-1] != '\n')
	&&	(buffer[lineLen-1] != '\r'))
	{
		int	c;

		//	Copy chars from the input to the output until we reach the end
		//	of the line or the end of the file.
		while ((c = fgetc(input)) != EOF)
		{
			fputc(c, output);
			if ((c == '\n') || (c == '\r')) break;
		}
	}

	return true;
}


// Whenever the user changes Shave component selection types we
// automatically convert the current selection to match the new type. So if
// there are currently several guides selected and the selection mode
// changes to "tip" then we replace the selected guides with selections of
// their tip vertices.
//
// Note that in "root" mode while we are using the root verts to guide the
// selection, it is actually guides which are being selected.
//
bool shaveUtil::convertComponentSelections(bool* pHiliteListChanged)
{
	if (pHiliteListChanged) *pHiliteListChanged = false;

	if (MGlobal::selectionMode() != MGlobal::kSelectComponentMode) return false;

	bool			currentIsHilited = true;
	MDagPath		currentShape;
	MSelectionList	hiliteList;
	unsigned		i;
	unsigned		j;
	unsigned		k;
	const int		tipIdx = SHAVE_VERTS_PER_GUIDE - 1;

	// The first shaveHairShape on the hilite list is the current node.
	//
	MGlobal::getHiliteList(hiliteList);
	currentShape = getFirstHairShape(hiliteList);

	// If no shaveHairShape was found on the hilite list, then grab the
	// first one which is on the selection list, or which has a component
	// on the selection list.
	//
	MSelectionList	selectionList;

	MGlobal::getActiveSelectionList(selectionList);

	if (!currentShape.isValid())
	{
		currentIsHilited = false;
		currentShape = getFirstHairShape(selectionList);

		//
		// If we still don't have a hair shape then there's nothing to be
		// done.
		//
		if (!currentShape.isValid()) return false;
	}

	// Get Shave's component selection mode.
	//
	MString			selModeStr;

	MGlobal::executeCommand(
		"optionVar -q shaveBrushSelectMode", selModeStr
	);

	unsigned char	selMode = *selModeStr.asChar();

	// Remove from the selection list any hair shapes other than the
	// current one and convert component selections for the current hair
	// shape to match the current component selection type.
	//
	MObject						comp;
	MFnSingleIndexedComponent	guideCompFn;
	bool						haveSelectedComponents = false;
	MDagPath					path;
	bool						selectionChanged = false;
	MFnDoubleIndexedComponent	vertCompFn;

	for (i = selectionList.length(); i > 0; i--)
	{
		unsigned	itemIdx = i - 1;

		if (selectionList.getDagPath(itemIdx, path, comp))
		{
			path.extendToShape();

			MFnDagNode	nodeFn(path);

			if (nodeFn.typeId() == shaveHairShape::id)
			{
				// If this is some other hair shape, remove it.
				//
				if (!(path == currentShape))
				{
					selectionList.remove(itemIdx);
					selectionChanged = true;
				}
				else if (!comp.isNull())
				{
					MFn::Type	compType = comp.apiType();
					MObject		newComp;

					if (compType == shaveHairShape::kShaveGuideComponent)
					{
						// Get the indices of the selected guides.
						//
						MIntArray	guides;

						guideCompFn.setObject(comp);
						guideCompFn.getElements(guides);

                        // If we're in tip selection mode then replace the
                        // selected guides with just their tip vertices.
                        //
						// If we're in vertex selection mode then replace
						// the selected guides with all of their vertices.
						//
						// If we're in guide, guide-by-root or guide-by-tip
						// mode then we're happy with the guide selections as
						// they are.
						//
						switch (selMode)
						{
                        case 't':
                            newComp = vertCompFn.create(
                                        shaveHairShape::kShaveGuideVertComponent
                                      );

                            for (j = 0; j < guides.length(); j++)
                            {
                                vertCompFn.addElement(guides[j], tipIdx);
                            }
                        break;

						case 'v':
							newComp = vertCompFn.create(
										shaveHairShape::kShaveGuideVertComponent
									);

							for (j = 0; j < guides.length(); j++)
							{
								for (k = 0; k < SHAVE_VERTS_PER_GUIDE; k++)
									vertCompFn.addElement(guides[j], k);
							}
						break;
						}

						haveSelectedComponents = true;
					}
					else if (compType == shaveHairShape::kShaveGuideVertComponent)
					{
						// Get the indices of the selected verts.
						//
						MIntArray	guides;
						MIntArray	verts;

						vertCompFn.setObject(comp);
						vertCompFn.getElements(guides, verts);

						// If we're in guide or guide-by-root selection
						// mode, then just select the corresponding guides.
						//
                        // If we're in tip selection mode, then select just
                        // the tip vert.
                        //
						// If we're in vert mode, we're happy with the
						// selection as-is.
						//
						switch (selMode)
						{
						case 'g':
						case 'r':
							newComp = guideCompFn.create(
										shaveHairShape::kShaveGuideComponent
									);
							guideCompFn.addElements(guides);
						break;

						case 't':
                            // If the verts are already all tips then we
                            // can leave the selection as-is.
                            //
                            for (j = 0; j < verts.length(); j++)
                            {
                                if (verts[j] != tipIdx) break;
                            }

                            if (j < verts.length())
                            {
                                newComp = vertCompFn.create(
                                            shaveHairShape::kShaveGuideVertComponent
                                          );

                                for (j = 0; j < verts.length(); j++)
                                {
                                    vertCompFn.addElement(guides[j], tipIdx);
                                }
                            }
						}

						haveSelectedComponents = true;
					}
					else
					{
						//
						// I don't know what type of item this is, but it
						// shouldn't be here, so remove it.
						//
						selectionList.remove(itemIdx);
						selectionChanged = true;
					}

					//
					// If we have a new component, replace the existing one
					// with it.
					//
					if (!newComp.isNull())
					{
						selectionList.replace(itemIdx, currentShape, newComp);
						selectionChanged = true;
					}
				}
			}
		}
	}

	//
	// If we didn't end up with any components selected, then select them
	// all.
	//
	if (!haveSelectedComponents)
	{
		MFnDependencyNode	nodeFn(currentShape.node());
		shaveHairShape*		nodePtr = (shaveHairShape*)nodeFn.userNode();
		unsigned			numGuides = nodePtr->getGuideCount();

		if (numGuides > 0)
		{
			if ((selMode == 'g') || (selMode == 'r'))
			{
				comp = guideCompFn.create(shaveHairShape::kShaveGuideComponent);
			}
			else
			{
				comp = vertCompFn.create(
							shaveHairShape::kShaveGuideVertComponent
						);
			}

			for (i = 0; i < numGuides; i++)
			{
				switch (selMode)
				{
					case 'g':
					case 'r':
						guideCompFn.addElement(i);
					break;

					case 't':
                        vertCompFn.addElement(i, tipIdx);
                    break;

					case 'v':
						for (j = 0; j < SHAVE_VERTS_PER_GUIDE; j++)
							vertCompFn.addElement(i, j);
					break;
				}
			}

			selectionList.add(currentShape, comp);
			selectionChanged = true;
		}
	}

	//
	// Remove all other hair shapes from the hilite list.
	//
	bool	hiliteChanged = false;

	for (i = hiliteList.length(); i > 0; i--)
	{
		hiliteList.getDagPath(i-1, path);
		path.extendToShape();

		if (!(path == currentShape))
		{
			hiliteList.remove(i-1);
			hiliteChanged = true;
		}
	}

	//
	// If the current node is not on the hilite list, add it.
	//
	if (!currentIsHilited)
	{
		hiliteList.add(currentShape);
		hiliteChanged = true;
	}

	//
	// Update the hilite lists, if it's changed.
	//
	if (hiliteChanged) MGlobal::setHiliteList(hiliteList);

	if (pHiliteListChanged) *pHiliteListChanged = hiliteChanged;

	//
	// Update the selection list, if it's changed.
	//
	// Note that this will cause the 'shave_selectionChanged' MEL proc
	// to run which will then call this method again.  Unfortunately,
	// the selectionChanged event does not fire until *after* we have
	// returned from this method, so methods to avoid recursion, such as
	// setting a static flag, won't work because we're not actually
	// recursing.  For now we just take the performance hit, since it
	// should be pretty small.
	//
	if (selectionChanged) MGlobal::setActiveSelectionList(selectionList);

	return selectionChanged;
}


MString shaveUtil::expandTempFileName(MString fileName)
{
	//
	// MEL is much better at handling cross-platform stuff, so let's
	// delegate this.
	//
	MGlobal::executeCommand(
		MString("shaveExpandTempFilePath(\"") + fileName + "\")",
		fileName
	);

	return fileName;
}


MString shaveUtil::expandStatFileName(MString fileName)
{
	//
	// MEL is much better at handling cross-platform stuff, so let's
	// delegate this.
	//
	MGlobal::executeCommand(
		MString("shaveExpandStatFilePath(\"") + fileName + "\")",
		fileName
	);

	return fileName;
}


void shaveUtil::fileDelete(MString fileName)
{
	//////// debug //////////
	//MGlobal::displayInfo( fileName);

	if ((fileName.length() > 0) && fileExists(fileName))
	{
		MGlobal::executeCommand(
			MString("sysFile -del \"") + fileName + "\""
		);
	}

	return;
}


bool shaveUtil::fileExists(MString fileName)
{
	int	exists;

	//////// debug //////////
	//MGlobal::displayInfo( fileName);

	MGlobal::executeCommand(
		MString("filetest -r \"") + fileName + "\"", exists
	);
	return (exists != 0);
}


bool shaveUtil::fileRename(MString oldName, MString newName)
{
	MStatus	st;

	if ((oldName.length() == 0)
	||	(newName.length() == 0)
	||	!fileExists(oldName))
	{
		return false;
	}

	st = MGlobal::executeCommand(
			MString("sysFile -ren \"") + newName + "\" \"" + oldName + "\""
		);

	return (bool)st;
}


MStatus shaveUtil::forceCompute(MObject shaveHairShape)
{
	MStatus				status;
	MFnDependencyNode	nodeFn(shaveHairShape, &status);

	if (status)
	{
		if (nodeFn.typeId() == shaveHairShape::id)
		{
			//
			// Since all of a shaveHairShape's inputs affect its output mesh,
			// all we need do is read the output mesh plug and if any of
			// the inputs have changed, the compute will be run.
			//
			MPlug	plug = nodeFn.findPlug(shaveHairShape::outputMesh);
			MObject	data;

			status = plug.getValue(data);

			if (status)
			{
				MFnMeshData	dataFn(data, &status);
			}
		}
		else
			status = MS::kInvalidParameter;
	}

	return status;
}


void shaveUtil::forceComputeAll()
{
	MObjectArray	shaveHairShapes;
	getShaveNodes(shaveHairShapes);

	unsigned int	numShaveNodes = shaveHairShapes.length();
	unsigned int	i;

	for (i = 0; i < numShaveNodes; i++)
		forceCompute(shaveHairShapes[i]);
}


MString shaveUtil::formatFrame(float frame)
{
	char frameStr[5];
	sprintf(frameStr, "%04d", (int)frame);

	return MString(frameStr);
}


//	There is no MPlug::getValue() for attributes of type kAddr. However
//	there is MDataHandle::asAddr(). So what we do is connect 'addrPlug'
//	to 'shaveGlobals.address', which was created specifically for this
//	purpose, and then ask shaveGlobals to read the value from its
//	datablock.
void* shaveUtil::getAddrPlugValue(const MPlug& addrPlug, MStatus* st)
{
	MObject	globalsNode = shaveGlobals::getDefaultNode();

	if (!globalsNode.isNull())
	{
		MFnDependencyNode	nodeFn(globalsNode);
		shaveGlobals*		globalsPtr = (shaveGlobals*)nodeFn.userNode();
		MPlug				globalsPlug = nodeFn.findPlug(shaveGlobals::aAddress);
		MDGModifier			dgmod;

		if (dgmod.connect(addrPlug, globalsPlug))
		{
			if (dgmod.doIt())
			{
				void*	addr = globalsPtr->getAddress();
				dgmod.undoIt();

				if (st) *st = MS::kSuccess;

				return addr;
			}
		}
	}

	if (st) *st = MS::kFailure;

	return NULL;
}


void shaveUtil::getDisplayNodes(MObjectArray& displayNodes)
{
	MObjectArray	shaveHairShapes;
	getShaveNodes(shaveHairShapes);

	unsigned int	numNodes = shaveHairShapes.length();
	unsigned int	i;

	displayNodes.clear();

	for (i = 0; i < numNodes; i++)
	{
		MFnDependencyNode	nodeFn(shaveHairShapes[i]);
		shaveHairShape*		nodePtr = (shaveHairShape*)nodeFn.userNode();
		MObject				displayNode = nodePtr->getDisplayShape();

		if (!displayNode.isNull()) displayNodes.append(displayNode);
	}
}


//	Returns the currently selected hair shape.
//
MDagPath shaveUtil::getCurrentHairShape(bool* pIsHilited)
{
	MDagPath		currentHairShape;
	bool			isHilited = false;
	MSelectionList	list;

	MGlobal::getHiliteList(list);
	currentHairShape = getFirstHairShape(list);

	if (!currentHairShape.isValid())
	{
		MGlobal::getActiveSelectionList(list);
		currentHairShape = getFirstHairShape(list);
	}
	else
		isHilited = true;

	if (pIsHilited) *pIsHilited = isHilited;

	return currentHairShape;
}


//	This is currently not used. The problem with sampling is that we only
//	sample at the pre-render vertices. However, displacements can produce
//	effects which are equivalent to adding new vertices. For example, we
//	have a plane with just 4 verts at the corners. Apply a displacement
//	shader with a hard ramp which in the middle of the plane jumps from a
//	displacement of 0 to 1. On render that will produce a step-like piece
//	of geometry.  But since we just sample the corners, we instead get a
//	smooth ramp.
//
//	For that reason, we use the 'displacementToPoly' command to generate
//	a suitably tesselated mesh, instead.  I'm just keeping this code around
//	to remind me how to sample displacements.
void shaveUtil::getDisplacedMeshVertices(
	MObject				mesh,
	MObject				shadingGroup,
	MFloatPointArray&	displacedVerts
)
{
	MStatus	st;

	enum
	{
		kNoDisplacement,
		kConstantDisplacement,
		kVariableDisplacement
	} displacementType = kNoDisplacement;

	MPlug	displacementPlug;
	float	constDisplacement = 0.0f;

	if (!shadingGroup.isNull())
	{
		//	Does the shading group have a displacement shader?
		MPlugArray			conns;
		MFnDependencyNode	sgFn(shadingGroup);
		displacementPlug = sgFn.findPlug("displacementShader");
		displacementPlug.connectedTo(conns, true, false);

		if (conns.length() > 0)
		{
			//	If the displacement shader is an actual Maya
			//	displacement shader *and* it's output is not being fed
			//	from another plug, then the displacement value is
			//	constant and we can save ourselves some effort by
			//	just grabbing that instead of sampling for all the
			//	points.
			//
			//	In fact, this isn't an option since sampling a displacement
			//	shader's 'displacement' plug directly seems to fail.
			if (conns[0].node().hasFn(MFn::kDisplacementShader)
			&&	(conns[0].partialName(false, false, false, false, false, true) == "displacement"))
			{
				displacementPlug = conns[0];
				displacementPlug.connectedTo(conns, true, false);

				if (conns.length() > 0)
				{
					displacementPlug = conns[0];
					displacementType = kVariableDisplacement;
				}
				else
				{
					displacementPlug.getValue(constDisplacement);
					displacementType = kConstantDisplacement;
				}
			}
			else
			{
				displacementPlug = conns[0];
				displacementType = kVariableDisplacement;
			}
		}
	}

	// Get the vertices and apply displacements.
	MItMeshVertex	vtxIter(mesh);
	unsigned int	numVerts = vtxIter.count();
	unsigned int	i;

	displacedVerts.setLength(numVerts);

	switch (displacementType)
	{
		case kNoDisplacement:
		{
			for (i = 0, vtxIter.reset();
				(i < numVerts) && !vtxIter.isDone();
				++i, vtxIter.next())
			{
				MPoint p = vtxIter.position(MSpace::kWorld);
				displacedVerts[i] = MFloatPoint((float)p.x, (float)p.y, (float)p.z);
			}
		}
		break;

		case kConstantDisplacement:
		{
			MVector	normal;

			for (i = 0, vtxIter.reset();
				(i < numVerts) && !vtxIter.isDone();
				++i, vtxIter.next())
			{
				MPoint 	p = vtxIter.position(MSpace::kWorld);

				vtxIter.getNormal(normal, MSpace::kWorld);
				
				p += normal * constDisplacement;
				displacedVerts[i] = MFloatPoint((float)p.x, (float)p.y, (float)p.z);
			}
		}
		break;

		case kVariableDisplacement:
		{
			//	Get the vertex positions, their normals, and anything
			//	else we need to sample a shading network.
			MVector				normal;
			MFloatVectorArray	normals(numVerts);
			MFloatArray			uCoords(numVerts);
			MFloatArray			vCoords(numVerts);
			float2				uv;

			for (i = 0, vtxIter.reset();
				(i < numVerts) && !vtxIter.isDone();
				++i, vtxIter.next())
			{
				MPoint 	p = vtxIter.position(MSpace::kWorld);
				displacedVerts[i] = MFloatPoint((float)p.x, (float)p.y, (float)p.z);

				vtxIter.getNormal(normal, MSpace::kWorld);
				normals[i] = MFloatVector((float)normal.x, (float)normal.y, (float)normal.z);

				vtxIter.getUV(uv);
				uCoords[i] = uv[0];
				vCoords[i] = uv[1];
			}


			//	Sample the displacements.
			MFloatVectorArray	displacements;
			MFloatVectorArray	dummyTransparencies;
			MFloatMatrix		dummyCamMatrix;

			st = MRenderUtil::sampleShadingNetwork(
				displacementPlug.name(),
				displacedVerts.length(),
				false,					// useShadowMaps
				false,					// reuseMaps
				dummyCamMatrix,
				&displacedVerts,
				&uCoords,
				&vCoords,
				&normals,
				&displacedVerts,
				0,						// tangentUs
				0,						// tangentVs
				0,						// filterSizes
				displacements,
				dummyTransparencies
			);

			//	Apply the displacements.
			for (i = 0; i < displacedVerts.length(); ++i)
			{
				displacedVerts[i] += normals[i] * displacements[i].x;
			}
		}
		break;
	}
}


const MDagPathArray& shaveUtil::getFields()
{
	if (mFieldsDirty)
	{
		mFields.clear();

		MItDag		iter(MItDag::kDepthFirst, MFn::kField);
		MDagPath	path;

		for (; !iter.isDone(); iter.next())
		{
			iter.getPath(path);
			mFields.append(path);
		}

		mFieldsDirty = false;
	}

	return mFields;
}


MDagPath shaveUtil::getFirstHairShape(MSelectionList& list)
{
	unsigned	i;
	MDagPath	path;

	for (i = 0; i < list.length(); i++)
	{
		list.getDagPath(i, path);
		path.extendToShape();

		MFnDagNode	nodeFn(path);

		if (nodeFn.typeId() == shaveHairShape::id) return path;
	}

	MDagPath	noPath;

	return noPath;
}


MString shaveUtil::getHostName()
{
	MString	hostName;

#if defined(OSMac_) && !defined(OSMac_MachO_)
	MGlobal::executeCommand("system(\"uname -n\")", hostName);

	//
	// There will be a newline at the end, so strip it off.
	//
	if (hostName.length() > 1)
		hostName = hostName.substring(0, hostName.length()-2);
#else
	char	temp[100];
	gethostname(temp, sizeof(temp));
	hostName.set(temp);
#endif

	return hostName;
}


//
// Get a light's index in the globalLightList, using its blind data value.
//
int shaveUtil::getLightIndex(const void* lightBlindData)
{
	if (lightBlindData == 0) return -1;

	size_t	numLights = globalLightList.size();
	size_t	i;

	for (i = 0; i < numLights; i++)
	{
		if (globalLightList[i].blindData == lightBlindData)
			return (int)i;
	}

	return -1;
}


//
// Get a light's index in the globalLightList, using its direction from a
// specified point.
//
int shaveUtil::getLightIndex(
	const MFloatVector& point, const MFloatVector& dirToLight
)
{
	unsigned int	numLights = (unsigned int)globalLightList.size();
	int				index = -1;
	unsigned int	i;
	float			minAngle = 10.0f;	// Must be > 2pi

	for (i = 0; i < numLights; i++)
	{
		MTransformationMatrix	mat(globalLightList[i].path.inclusiveMatrix());
		MFloatVector			pos(mat.translation(MSpace::kWorld));
		MFloatVector			dirToThisLight = pos - point;
		float					angle = (float)fabs(dirToThisLight.angle(dirToLight));

		if (angle < minAngle)
		{
			minAngle = angle;
			index = i;
		}
	}

	//
	// If the angular difference is too great, then this simply cannot be
	// the right light.  (0.01 radians is about 5.7 degrees)
	//
	if (minAngle > 0.01f) index = -1;

	return index;
}


int shaveUtil::getLightIndexFromID(int id)
{
	unsigned	i;

	for (i = 0; i < globalLightList.size(); i++)
	{
		if ((id >= globalLightList[i].minId)
		&&	(id <= globalLightList[i].maxId))
		{
			return i;
		}
	}

	return -1;
}


//	Returns the hair shape which is currently loaded into the Shave
//	engine. Normally this will be the same as that returned by
//	getCurrentShape() but they can be different, e.g. if the user has
//	selected a new shape but we've not yet loaded it into the engine.
//
shaveHairShape* shaveUtil::getLoadedHairShape()
{
	MDagPathArray nodes;
	getShaveNodes(nodes);

	for (unsigned int i = 0; i < nodes.length(); ++i)
	{
		MFnDagNode nodeFn(nodes[i]);
		shaveHairShape* nodePtr = dynamic_cast<shaveHairShape*>(nodeFn.userNode());

		if ((nodePtr != NULL) && nodePtr->isCurrent())
		{
			return nodePtr;
		}
	}

	return NULL;
}


//
// Tesselate a NURBS or subdivision surface into a poly mesh.
//
// To use the surface's default values for uTess, set it to -1.
// Ditto vTess.
//
MObject shaveUtil::getMesh(
	MDagPath& surface, 
		int uTess, 
		int vTess, 
		int	sDept,
		int	sSamp,
		bool includeDisplacements
)
{
	// Make sure that we're looking at the shape and not its transform.
	MDagPath	surfaceShape(surface);
	surfaceShape.extendToShape();

	//	Surfaces with displacement shaders require special handling.
	if (includeDisplacements && isSurfaceDisplaced(surface))
	{
		//	Since we have displacements, we must use the
		//	'displacementToPoly' command to generate a mesh representing
		//	the displaced surface.
		MSelectionList	savedSelection;
		MGlobal::getActiveSelectionList(savedSelection);

		MGlobal::select(
			surfaceShape, MObject::kNullObj, MGlobal::kReplaceList
		);

		MStringArray	results;
		MGlobal::executeCommand("displacementToPoly", results);

		//	Get the local mesh from the resulting mesh node.
		MSelectionList	list;
		list.add(results[0]);

		MDagPath	displacedMesh;
		list.getDagPath(0, displacedMesh);

		MFnMesh	meshFn(displacedMesh);
		MPlug	plug = meshFn.findPlug("worldMesh").elementByLogicalIndex(0);
		MObject	meshObj;
		plug.getValue(meshObj);

		//	We don't need the displaced mesh any more, so delete it.
		MDagModifier	dagMod;
		dagMod.deleteNode(displacedMesh.node());
		dagMod.doIt();

		//	Restore the selection list.
		MGlobal::setActiveSelectionList(savedSelection);

		//	Return the displaced mesh to the caller.
		return meshObj;
	}

	//
	// If this is already a mesh, then just return it.
	//
	if (surfaceShape.hasFn(MFn::kMesh)) return surfaceShape.node();

	//
	// If this is a NURBS or subdivision surface, we'll need to tesselate
	// it.
	//
	MFnMeshData	tessData;
	MObject		tempMesh = tessData.create();

	if (surfaceShape.hasFn(MFn::kNurbsSurface))
	{
		MTesselationParams tessParams;
		tessParams.setFormatType(MTesselationParams::kGeneralFormat);
		tessParams.setOutputType(MTesselationParams::kTriangles);
		tessParams.setUIsoparmType(MTesselationParams::kSpanEquiSpaced);
		tessParams.setVIsoparmType(MTesselationParams::kSpanEquiSpaced);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseFractionalTolerance, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseChordHeightRatio, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseMinEdgeLength, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseMaxEdgeLength, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseMaxNumberPolys, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseMaxSubdivisionLevel, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseMinScreenSize, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseMaxUVRectangleSize, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseTriangleEdgeSwapping, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseRelativeTolerance, false);
		tessParams.setSubdivisionFlag(MTesselationParams::kUseEdgeSmooth, false);

		//
		// If either of the tesselation parameters passed in to us is
		// invalid, then go get the explicit parameter from the surface
		// itself.
		//
		MFnNurbsSurface	nurbsFn(surfaceShape);

		if ((uTess < 1) || (vTess < 1))
		{
			MPlug			plug;

			if (uTess < 1)
			{
				plug = nurbsFn.findPlug("numberU");
				plug.getValue(uTess);
			}

			if (vTess < 1)
			{
				plug = nurbsFn.findPlug("numberV");
				plug.getValue(vTess);
			}
		}

		tessParams.setUNumber(uTess);
		tessParams.setVNumber(vTess);

		//
		// There's a bug in Maya such that immediately after file load, a
		// nurbsSurface node is in an inconsistent state.  This will be
		// rectified the first time that the node's geometry is retrieved
		// from one of its plugs.  However, if we try to tesselate the
		// surface, it will do so on the *inconsistent* geometry.
		//
		// So let's first retrieve the surface's geom to ensure that it is
		// in a consistent state before doing tesselation.
		//
		MPlug	geomPlug = nurbsFn.findPlug("local");
		MObject	surfaceGeom;
		geomPlug.getValue(surfaceGeom);

		//
		// Okay, now it's safe to tesselate.
		//
		tempMesh = nurbsFn.tesselate(tessParams, tempMesh);
	}
	else if (surfaceShape.hasFn(MFn::kSubdiv))
	{
		//
		// Get the object's tesselation parameters.
		//
		MStatus	status;
		MFnSubd	subdFn(surfaceShape);
		bool	uniform = true;
		int		depth =	sDept;  //0;
		int		samples = sSamp; //1;
		

#if 0	//this logic seems correct, get matching
		//shapes on rendering but not in viewport
		int		format;
		MPlug	plug = subdFn.findPlug("format");

		plug.getValue(format);
		uniform = (format == 0);

		if (uniform)
		{
			plug = subdFn.findPlug("depth");
			plug.getValue(depth);
		}
		else
		{
			depth = 0;
		}

		plug = subdFn.findPlug("sampleCount");
		plug.getValue(samples);
#endif

#if 0	//levels does not match on rendering
		MPlug	plug = subdFn.findPlug("dispResolution",&status);
		if(status == MS::kSuccess)
			plug.getValue(depth);
#endif
		//
		// Do the tesselation.
		//
		////// debug ////////
		//MGlobal::displayInfo(MString("tesselate ") + depth + " " + samples);
		/////////////////////

		tempMesh = subdFn.tesselate(uniform, depth, samples, tempMesh, &status);

		if (!status)
		{
			MGlobal::displayError(
				MString("tesselating subd: ") + status.errorString()
			);
		}
	}

	tessData.setMatrix(surface.inclusiveMatrix());
	tessData.setObject(tempMesh);

	return tempMesh;
}

MObject shaveUtil::getNode(MString nodeName)
{
	MSelectionList	list;
	MObject			node;

	list.add(nodeName);
	list.getDependNode(0, node);

	return node;
}


void shaveUtil::getNodesByTypeId(MTypeId nodeType, MObjectArray& nodes)
{
	MItDependencyNodes	iter;

	nodes.clear();

	for (; !iter.isDone(); iter.next())
	{
		MObject				node = iter.item();
		MFnDependencyNode	nodeFn(node);

		if (nodeFn.typeId() == nodeType) nodes.append(node);
	}
}


void shaveUtil::getPathsByTypeId(MTypeId nodeType, MDagPathArray& paths)
{
	MItDag		iter;
	MDagPath	path;

	paths.clear();

	for (; !iter.isDone(); iter.next())
	{
		iter.getPath(path);

		MFnDagNode	nodeFn(path);

		if (nodeFn.typeId() == nodeType) paths.append(path);
	}
}


long shaveUtil::getpid()
{
#if defined(OSMac_) && !defined(OSMac_MachO_)
	ProcessSerialNumber	psn;
	GetCurrentProcess(&psn);

	return psn.lowLongOfPSN;
#else
#   ifdef _WIN32
        return _getpid();
#   else
	    return ::getpid();
#   endif
#endif
}


void shaveUtil::getShadingGroups(
	const MDagPath& path, MObjectArray& shadingGroups
)
{
	MFnDagNode	dagFn(path);

	shadingGroups.clear();

	MPlug		plug = dagFn.findPlug("instObjGroups");

	plug = plug.elementByLogicalIndex(path.instanceNumber());
	appendConnectedShadingGroups(plug, shadingGroups);

	MObject	objectGroupsAttr = dagFn.attribute("objectGroups");

	plug = plug.child(objectGroupsAttr);

	unsigned int	i;
	unsigned int	numElements = plug.evaluateNumElements();

	for (i = 0; i < numElements; i++)
	{
		appendConnectedShadingGroups(
			plug.elementByPhysicalIndex(i), shadingGroups
		);
	}
}


void shaveUtil::getShaveGlobalsNodes(MObjectArray& nodes)
{
	getNodesByTypeId(shaveGlobals::id, nodes);
}


void shaveUtil::getShaveNodes(MDagPathArray& paths)
{
	getPathsByTypeId(shaveHairShape::id, paths);
}


void shaveUtil::getShaveNodes(MObjectArray& nodes)
{
	getNodesByTypeId(shaveHairShape::id, nodes);
}


void shaveUtil::getSubdQuads(
	MDagPath&		subdPath,
	MUint64Array&	quadIDs,
	MPointArray&	verts,
	MIntArray&		vertIndices,
	MDoubleArray*	vertUs,
	MDoubleArray*	vertVs
)
{
	MFnSubd		subdFn(subdPath);
	MPlug		worldSubdivArray = subdFn.findPlug("worldSubdiv");
	MPlug		subdivPlug = worldSubdivArray.elementByLogicalIndex(subdPath.instanceNumber());
	MObject		subdData;

	subdivPlug.getValue(subdData);

	getSubdQuads(subdData, quadIDs, verts, vertIndices, vertUs, vertVs);
}


void shaveUtil::getSubdQuads(
	MObject			subdData,
	MUint64Array&	quadIDs,
	MPointArray&	verts,
	MIntArray&		vertIndices,
	MDoubleArray*	vertUs,
	MDoubleArray*	vertVs
)
{
	MFnSubd		subdFn(subdData);
	int			i, j, k;
	MIntArray	level0FirstSubfaceIndices;
	int			numLevel0Polys = subdFn.polygonCount(0);

	level0FirstSubfaceIndices.clear();
	quadIDs.clear();
	verts.clear();
	vertIndices.clear();

	for (i = 0; i < numLevel0Polys; i++)
	{
		MUint64			level0FaceID;
		MUint64Array	level1Polys;

		MFnSubdNames::toMUint64(level0FaceID, i, 0, 0, 0, 0);

		level0FirstSubfaceIndices.append(quadIDs.length());
		subdFn.polygonChildren(level0FaceID, level1Polys);

		for (j = 0; j < (int)level1Polys.length(); j++)
		{
			//
			// Add this quad's face ID to the list.
			//
			quadIDs.append(level1Polys[j]);

			//
			// Get the IDs for its four vertices.
			//
			MUint64Array	vertIDs;
			MDoubleArray	uValues;
			MDoubleArray	vValues;

			subdFn.polygonVertices(level1Polys[j], vertIDs);

			if (vertUs || vertVs)
				subdFn.polygonGetVertexUVs(level1Polys[j], uValues, vValues);

			MPoint	p;

			for (k = 0; k < 4; k++)
			{
				//
				// Get the components which make up the vertex ID.
				//
				int	level0Idx;
				int	level1Idx;
				int	level;		// Should come back as 1.
				int	path;		// Unused.
				int	corner;

				MFnSubdNames::fromMUint64(
					vertIDs[k], level0Idx, level1Idx, level, path, corner
				);

				//
				// The vertex ID will be based on the lowest-numbered quad
				// which uses it.  If that's us, then we must create an
				// entry for the vert.  Otherwise we use the entry already
				// created by that lower-number quad.
				//
				if ((level0Idx == i) && (level1Idx == j))
				{
					vertIndices.append(verts.length());

					subdFn.vertexPositionGet(vertIDs[k], p, MSpace::kWorld);
					verts.append(p);

					if (vertUs) vertUs->append(uValues[k]);
					if (vertVs) vertVs->append(vValues[k]);
				}
				else
				{
					int	overallQuadIdx = level0FirstSubfaceIndices[level0Idx] + level1Idx;
					int	overallVertIdx = overallQuadIdx *4 + corner;

					vertIndices.append(vertIndices[overallVertIdx]);
				}
			}
		}
	}
}


unsigned shaveUtil::getThreadSettings(
	unsigned numItems, unsigned* pItemsPerThread
)
{
	int			itemsPerThread;
	unsigned	numThreads;

	if (threadPerProcessorGlob)
		numThreads = (unsigned)SHAVEnum_processors();
	else
		numThreads = maxThreadsGlob;

	if (numThreads >= numItems)
	{
		itemsPerThread = 1;
		numThreads = numItems;
	}
	else if (numThreads > 1)
	{
		itemsPerThread = numItems / numThreads + 1;
	}
	else
	{
		itemsPerThread = numItems;
		numThreads = 0;
	}

	if (pItemsPerThread) *pItemsPerThread = itemsPerThread;

	return numThreads;
}


bool shaveUtil::isSurfaceDisplaced(const MDagPath& surface)
{
	// Make sure that we're looking at the shape and not its transform.
	MDagPath	surfaceShape(surface);
	surfaceShape.extendToShape();

	//	Search all the surface's shading groups for displacement shaders.
	MObjectArray	shadingGroups;
	getShadingGroups(surface, shadingGroups);

	unsigned int	i;

	for (i = 0; i < shadingGroups.length(); ++i)
	{
		//	Does the shading group have a displacement shader?
		MPlugArray			conns;
		MFnDependencyNode	sgFn(shadingGroups[i]);
		MPlug				displacementPlug;

		displacementPlug = sgFn.findPlug("displacementShader");
		displacementPlug.connectedTo(conns, true, false);

		if (conns.length() > 0) return true;
	}

	return false;
}


MString shaveUtil::makeStatFileName(MString nodeName, float frame)
{
	//	The node name may contain ':' which are bad in filenames so replace
	//	them all with '_'.
	nodeName = substituteAll(nodeName, ':', '_');

	return	expandStatFileName(
				MString("shaveStatFile_") + nodeName + "."
				+ formatFrame(frame) + ".stat"
			);
}


MString shaveUtil::makeTempStatFileName(
	MString nodeName, MString suffix, float frame
)
{
	//	The node name may contain ':' which are bad in filenames so replace
	//	them all with '_'.
	nodeName = substituteAll(nodeName, ':', '_');

	return	expandTempFileName(
				MString("shaveStatFile_") + suffix + "_" + nodeName + "."
				+ formatFrame(frame) + ".stat"
			);
}


//	This function is not thread-safe!
MString shaveUtil::makeUniqueTempFileName(
	MString directory, MString prefix, MString suffix
)
{
	FILE*	fp;
	int		i;
	MString	fileName;
	MString	templ;

	//	Include the host name and process ID in the file name to avoid
	//	conflicts with other systems and processes generating files into
	//	the same directory.
	templ = prefix + "_" + getHostName() + "_" + shaveUtil::getpid() + "_";

	unsigned int l = directory.length();

	if (l == 0)
		templ = expandTempFileName(templ);
	else if (directory.substring(l-1, l-1) == "/")
		templ = directory + templ;
	else
		templ = directory + "/" + templ;

	//	Pick a random starting point from 0 to 999 to reduce the likelihood
	//	of a collision.
#ifdef _WIN32
	int	randStart = (int)(1000.0 * rand() / (RAND_MAX + 1.0));
#else
	int	randStart = (int)(1000.0 * random() / (RAND_MAX + 1.0));
#endif

	for (i = 0; i < 1000; i++)
	{
		fileName = templ + ((randStart + i) % 1000) + suffix;

		//	There is still a race condition here between fileExists()
		//	and fopen(). Because the fileName is unique to a given system
		//	and process, this is only a problem when threading.
		//
		//	Note that on Unix systems each thread is assigned its own
		//	process ID so in that case this function is thread-safe.
		if (!fileExists(fileName))
		{
#if defined(OSMac_) && !defined(OSMac_MachO_)
			MString	hfsFileName = shaveMacCarbon::makeMacFilename(fileName);

			fp = fopen(hfsFileName.asChar(), "w");
#else
			fp = fopen(fileName.asChar(), "w");
#endif
			if (fp != NULL)
			{
				fclose(fp);
				break;
			}
		}
	}
	/////// debug /////
	//MGlobal::displayInfo("------------temp file---------");
	//MGlobal::displayInfo(fileName);

	return fileName;
}


//
// Reverse the byte order of a 4-byte int value for those platforms which
// use a different endian.
//
int shaveUtil::reorderInt(int inVal)
{
	int				outVal;
	unsigned char*	pIn = (unsigned char*)&inVal;
	unsigned char*	pOut = (unsigned char*)&outVal;

	if (sizeof(int) == 2)
	{
		pOut[0] = pIn[1];
		pOut[1] = pIn[0];
	}
	else if (sizeof(int) == 4)
	{
		pOut[0] = pIn[3];
		pOut[1] = pIn[2];
		pOut[2] = pIn[1];
		pOut[3] = pIn[0];
	}

	return outVal;
}


MStatus shaveUtil::sampleCurves(
	const MObjectArray& curves, unsigned int samplesPerCurve, WFTYPE& sampleData
)
{
	MStatus		 st;
	unsigned int numCurves = curves.length();

	init_geomWF(&sampleData);

	sampleData.totalfaces = (int)numCurves;
	sampleData.totalverts = (int)(numCurves * samplesPerCurve);
	sampleData.totalfverts = sampleData.totalverts;

	alloc_geomWF(&sampleData);

	unsigned int i, j;
	int	numVerts = 0;

	for (i = 0; i < numCurves; i++)
	{
		// Sample the curve at samplesPerCurve equally spaced
		// points along its length and store the resulting points
		// into a WFTYPE.
		MFnNurbsCurve	curveFn(curves[i]);
		double			curveLen = curveFn.length();
		double			maxParam;
		double			minParam;
		MPoint			point;
		double			sampleLen = 0.0;
		double			sampleParam = 0.0;
		double			segmentLen;

		curveFn.getKnotDomain(minParam, maxParam);

		segmentLen = curveLen / (double)(samplesPerCurve-1);

		sampleData.face_start[i] = numVerts;

		for (j = 0; j < samplesPerCurve; j++)
		{
			if (j == 0)
				sampleParam = minParam;
			else if (j == samplesPerCurve-1)
				sampleParam = maxParam;
			else
				sampleParam = curveFn.findParamFromLength(sampleLen);

			curveFn.getPointAtParam(sampleParam, point, MSpace::kWorld);

			sampleData.v[numVerts].x = (float)point.x;
			sampleData.v[numVerts].y = (float)point.y;
			sampleData.v[numVerts].z = (float)point.z;

			sampleData.facelist[numVerts] = numVerts;

			numVerts++;
			sampleLen += segmentLen;
		}

		sampleData.face_end[i] = numVerts;
	}

	return st;
}


void shaveUtil::setFrame(float newFrame)
{
	MGlobal::executeCommand(MString("currentTime ") + newFrame);
}


void shaveUtil::setLoadingFile(bool nowLoading)
{
	if (nowLoading)
		mLoadDepth++;
	else
		mLoadDepth--;
}

void shaveUtil::setWFTYPEVelocities(WFTYPE* wf1, WFTYPE* wf2)
{
	int	i;
	int	numVerts = wf1->totalverts;

	if (wf2->totalverts < numVerts) numVerts = wf2->totalverts;

	for (i = 0; i < numVerts; i++)
	{
		wf1->velocity[i].x = wf2->v[i].x - wf1->v[i].x;
		wf1->velocity[i].y = wf2->v[i].y - wf1->v[i].y;
		wf1->velocity[i].z = wf2->v[i].z - wf1->v[i].z;
	}

	for (; i < wf1->totalverts; i++)
		wf1->velocity[i].x = wf1->velocity[i].y = wf1->velocity[i].z = 0.0f;
}


void shaveUtil::splitFileName(
	MString fileName, MString& baseName, MString& extension
)
{
	baseName = fileName;
	extension = "";

	int		dotPos = fileName.rindex('.');

	if ((dotPos >= 0)
	&&	(dotPos > fileName.rindex('/'))
	&&	(dotPos > fileName.rindex('\\')))
	{
		if (dotPos + 1 < (int)fileName.length())
			extension = fileName.substring(dotPos+1, fileName.length()-1);

		if (dotPos > 0)
			baseName = fileName.substring(0, dotPos-1);
		else
		{
			//
			// Whoops!
			//
			baseName = "";
		}
	}
}


bool shaveUtil::splitShaveVersion(const MString versionStr, int versionParts[3])
{
	MStringArray	strParts;

	versionStr.split('.', strParts);

	if (strParts.length() == 2)
	{
		MStringArray	tempParts;

		strParts[1].split('v', tempParts);

		if (tempParts.length() == 2)
		{
			versionParts[0] = strParts[0].asInt();
			versionParts[1] = tempParts[0].asInt();
			versionParts[2] = tempParts[1].asInt();
			return true;
		}
	}

	//	If we reach here then the version string is malformed, so assume
	//	that it is 4.5v9 (the last version without scene versioning) and
	//	return false.
	versionParts[0] = 4;
	versionParts[1] = 5;
	versionParts[2] = 9;

	return false;
}


MString shaveUtil::substituteAll(const MString& str, char oldChar, char newChar)
{
	if (newChar == oldChar) return str;

	char*	strBuff = new char[str.length()+1];

	strcpy(strBuff, str.asChar());

	for (char* c = strBuff; *c; ++c)
		if (*c == oldChar) *c = newChar;

	MString	newStr(strBuff);
	delete [] strBuff;

	return newStr;
}


MString shaveUtil::substituteAll(
	const MString& str, const MString& oldSubstr, const MString& newSubstr
)
{
	if ((oldSubstr.length() == 0) || (newSubstr == oldSubstr)) return str;

	unsigned int	i;
	MString			newStr = str;

	for (i = 0; i < newStr.length() - oldSubstr.length() + 1; i++)
	{
		if (newStr.substring(i, i + oldSubstr.length() - 1) == oldSubstr)
		{
			if (i == 0)
			{
				newStr = newSubstr
					+ newStr.substring(oldSubstr.length(), newStr.length());
			}
			else
			{
				newStr = newStr.substring(0, i-1) + newSubstr
					+ newStr.substring(i + oldSubstr.length(), newStr.length());
			}

			i += newSubstr.length() - 1;
		}
	}

	return newStr;
}


void shaveUtil::timestamp(const MString& msg)
{
#ifdef _WIN32
	clock_t	time = clock();
#else
	clock_t	time = times(0);
#endif

#if defined(OSMac_) && (MAYA_API_VERSION >= 201600) && (MAYA_API_VERSION < 201700)
	cout << time << ": " << msg.asChar() << endl;
#else
	cout << time << ": " << msg << endl;
#endif
}


//*****************************************************
//
//		Internal Utility Methods
//
//*****************************************************

void shaveUtil::appendConnectedShadingGroups(
	const MPlug& plug, MObjectArray& shadingGroups
)
{
	MPlugArray	conns;

	plug.connectedTo(conns, false, true);

	unsigned int	numConns = conns.length();
	unsigned int	i;

	for (i = 0; i < numConns; i++)
	{
		if (conns[i].node().hasFn(MFn::kSet))
		{
			MFnSet	setFn(conns[i].node());

			if (setFn.restriction() == MFnSet::kRenderableOnly)
				shadingGroups.append(setFn.object());
		}
	}
}