// ===========================================================================
// Copyright 2018 Autodesk, Inc. All rights reserved.
//
// Use of this software is subject to the terms of the Autodesk license
// agreement provided at the time of installation or download, or which
// otherwise accompanies this software in either electronic or hard copy form.
// ===========================================================================
// This is the master script for the crack shatter effect.
// See the routine createCracks for an important assumption about the poly tools.
//

includeEffectsGlobals();
includeShatterEffectsGlobals();

global int    $gSelectedVertexId = 0;
global string $gLastSelectionList[];


proc int selectionValidForCrackShatter()
//
// Returns true if the selection is valid for crack shatter, false otherwise.
// consists of either a vertex or a cv. Only one object at a time
// can be shattered and the vertex/cv where the crack is supposed
// to originate is supposed to be selected.
{
	int $result = false;
	string $selectionList[] = `ls -sl`;
	int           $listCount       = size( $selectionList );
	if ($listCount == 1)
	{
		string $tokenList[];

		tokenize( $selectionList[0], ".[]", $tokenList );

		if (( $tokenList[1] == "vtx" ) || ( $tokenList[1] == "cv" ))
		{
			$result = true;
		}
	}
	return $result;
}

proc int getSelectedVertex( string $object, int $verbose )
//
// This procedure assumes that $object is a mesh.
// If $gLastSelectionList is a vtx, we return the index of that vertex.
// If $glastSelectionList is a cv, we return the vertex of $object which
// is closest to that vertex.  Only the first item in $gLastSelectionList is used.
// If neither a vertex nor a cv is selected, we return -1.
{
	global string $gLastSelectionList[];
	string        $selectionList[] = $gLastSelectionList;
	int           $listCount       = size( $selectionList );
	int 		  $vertexIndex     = -1;

	if ( $listCount > 0 )
	{
		string $tokenList[];

		tokenize( $selectionList[0], ".[]", $tokenList );

		if ( $tokenList[1] == "vtx" ) 
		{
			string $vertexList[] = getVertexList( $selectionList[0] );

			$listCount = size( $vertexList );

			if ( $listCount > 0 )
			{
				$vertexIndex = getIndex( $vertexList[0] );

				if ( $verbose )
				{
					string $fmt = (uiRes("m_crackShatter.kSelectedVertex"));
					print( `format -s $vertexList[0] $fmt` );
				}
			}
		}
		// We are dealing with a CV.
		//
		else if ( $tokenList[1] == "cv" )
		{
			float $pos[] = `pointPosition -world $selectionList[0]`;

			$vertexIndex = findClosestVertex( $object, <<$pos[0], $pos[1], $pos[2]>> );
		}
	}

	return $vertexIndex;
}

proc assignShardIndex( string $face, int $shardIndex, int $shardIndexList[] )
//
// This procedure recrusively assigns shard indices to faces surrounding the
// given face.
//
{
	string $faceList[] = getSurroundingFaces( $face );
	int    $faceCount  = size( $faceList );

	// For each face surrounding the input face, assign
	// the given shard index.
	//
	for ( $i = 0; $i < $faceCount; $i++ )
	{
		$face = $faceList[$i];

		int $faceIndex = getIndex( $face );

		if ( $shardIndexList[ $faceIndex ] == 0 ) 
		{
			$shardIndexList[ $faceIndex ] = $shardIndex;

			assignShardIndex( $face, $shardIndex, $shardIndexList );
		}
	}
}


proc processRemainingFacets( string $object, int $shardIndexList[], string $crackEdgeList[],
							 int $verbose )
//
// This procedure assigns the unassigned facets to shards.
//
{
	string $edge;
	string $face;
	string $edgeList[];
	string $edgeFaceList[];
	int    $faceIndexList[];
	int    $edgeCount;
	int    $faceCount;
	int    $edgeFaceCount;
	int    $faceIndex;
	int    $shardIndex;
	string $crackEdges[];
	int    $crackCount = size( $crackEdgeList );

	for ( $i = 0; $i < $crackCount; $i++ )
	{
		tokenize( $crackEdgeList[ $i ], " ", $crackEdges );

		$edgeCount = size( $crackEdges );

		if ( $verbose )
		{
			int $crackId = $i + 1;
			string $fmt = (uiRes("m_crackShatter.kProcessingFaces"));
			print( `format -s $crackId $fmt` );
		}

		string $buffer[];
		tokenize( $crackEdges[0], ".", $buffer );
		string $baseName = $buffer[0];

		for ( $j = 0; $j < $edgeCount; $j++ )
		{
			$edge          = $crackEdges[$j];
			$edgeFaceList  = getFaceList( $edge );
			$edgeFaceCount = size( $edgeFaceList );

			for ( $k = 0; $k < $edgeFaceCount; $k++ )
			{
				$face          = $edgeFaceList[$k];
				$faceIndexList = getUniqueSurroundingFaces( $face, $edge, $crackEdgeList );
				$faceCount     = size( $faceIndexList );
				$shardIndex    = $shardIndexList[$faceIndexList[0]];

				// Determine the index associated with this face.
				//
				for ( $ii = 0; $ii < $faceCount; $ii++ )
				{
					$faceIndex = $faceIndexList[$ii];

					if ( $shardIndexList[$faceIndex] != 0 )
					{
						$shardIndex = $shardIndexList[$faceIndex];
						break;
					}
				}

				if ( $shardIndex != 0 )
				{
					$face = $baseName + ".f[" + $faceIndex + "]";
					assignShardIndex( $face, $shardIndex, $shardIndexList );
				}
			}
		}
	}
}


proc string[] createFirstEdgeList( string $crackEdgeList[] )
//
// This procedure determines the edges about the origin of the crack.
// Returns a string array containing a list of all the edges which belong to cracks and are
// incident to the origin.  These are in form <object>.e[<index>].
//
{
	string $firstEdge[];
	int    $edgeCount;
	int    $shardEdgeCount = size( $crackEdgeList );

	// For each shard edge, create a list of the first edge off
	// the vertex origin.
	//
	for ( $i = 0; $i < $shardEdgeCount; $i++ )
	{
		string $crackEdges[];

		tokenize( $crackEdgeList[ $i ], " ", $crackEdges );

		$edgeCount = size( $crackEdges );

		// Determine the first edge in the crack.
		//
		if ( $edgeCount > 0 )
		{
			$firstEdge[ $i ] = $crackEdges[0];
		}
	}

	return $firstEdge;
}


proc string[] orderOriginFaceList( string $originEdgeList[] )
//
// This procedure orders the faces associated with the origin.
//
{
	string $orderedFaces[];
	int    $edgeCount  = size( $originEdgeList );
	string $faceList[] = getFaceList( $originEdgeList[0] );
	int    $faceCount  = size( $faceList );
	int    $faceIndex  = 0;

	// We need to number the first face.  The way we number it will depend
	// on if the first edge is associated with more then one face.
	//
	if ( $faceCount == 1 )
	{
		$orderedFaces[0] = $faceList[0];
	}
	// If we have more then one face in the list then we need to
	// determine which face should be first.  We want to but the
	// face which does not share the next face as the first face.
	//
	else if ( $faceCount > 1 )
	{
		int    $commonFaceIndex = -1;
		string $nextFaceList[] = getFaceList( $originEdgeList[1] );
		int    $nextFaceCount  = size( $nextFaceList );

		// Find the common face.
		//
		for ( $i = $faceCount - 1; $i >= 0; $i-- )
		{
			for ( $j = 0; $j < $nextFaceCount; $j++ )
			{
				if ( $faceList[$i] == $nextFaceList[$j] )
				{
					$commonFaceIndex = $i;
					break;
				}
			}

			if ( $commonFaceIndex != -1 )
			{
				break;
			}
		}

		// If the first face in the list is the shared face
		// between the first and second edge then that face
		// is the second face.  Otherwise it is the first.
		//
		if ( $commonFaceIndex == 0 )
		{
			$orderedFaces[0] = $faceList[1];
			$orderedFaces[1] = $faceList[0];
		}
		else
		{
			$orderedFaces[0] = $faceList[0];
			$orderedFaces[1] = $faceList[1];
		}

		$faceIndex = 1;
	}

	if ( $faceIndex == 1 )
	{
		$edgeCount = $edgeCount - 1;
	}

	for ( $i = 1; $i < $edgeCount; $i++ )
	{
		$faceList  = getFaceList( $originEdgeList[$i] );
		$faceCount = size( $faceList );

		for ( $j = 0; $j < $faceCount; $j++ )
		{
			if ( $faceList[$j] != $orderedFaces[ $faceIndex ] )
			{
				$faceIndex++;
				$orderedFaces[ $faceIndex ] = $faceList[$j];
				break;
			}
		}
	}

	return $orderedFaces;
}


proc string[] orderOriginEdgeList( string $origin, string $vertexEdgeList[], int $startEdgeIndex )
//
// This procedure orders the edges, associated with the origin,
// in a clockwise fashion.
//
{
	int    $vertexEdgeCount = size( $vertexEdgeList );
	int    $edgeCount;
	string $faceEdgeList[];

	// Pick an edge and a face to start.
	//
	string $edge = $vertexEdgeList[$startEdgeIndex];

	// Clear the vertex edge list so we can reorder it.
	//
	clear( $vertexEdgeList );
	$vertexEdgeList[0] = $edge;

	string $edgeFaceList[] = getFaceList( $edge );
	string $face           = $edgeFaceList[0];

	// Create the edge list so it is in order going around the
	// vertex.
	//
	for ( $i = 1; $i < $vertexEdgeCount; $i++ )
	{
		int $found    = false;

		// Get the edge list for the starting face.
		//
		$faceEdgeList = getEdgeList( $face );
		$edgeCount    = size( $faceEdgeList );

		// Walk through the vertex edge list to determine 
		// the order of the face and then the edges.  Save
		// the edges in the vertex edge list.
		//
		for ( $j = 0; $j < $edgeCount; $j++ )
		{
			// If the face edge is not the current edge then determine if
			// it is an edge associated with the origin.  If so, this
			// is the next edge.
			//
			if ( $edge != $faceEdgeList[$j] )
			{
				$vertexList = getVertexList( $faceEdgeList[$j] );

				for ( $k = 0; $k < 2; $k++ )
				{
					if ( $origin == $vertexList[$k] ) 
					{
						$edge  = $faceEdgeList[$j];
						$found = true;
					}
				}
			}

			// If we found the next edge then find the next face.
			//
			if ( $found == true )
			{
				$edgeFaceList = getFaceList( $edge );

				for ( $k = 0; $k < 2; $k++ )
				{
					if ( $edgeFaceList[$k] != $face )
					{
						$face = $edgeFaceList[$k];
						break;
					}
				}

				// Save the next edge in the list.
				//
				$vertexEdgeList[ $i ] = $edge;
				break;
			}
		}
	}

	return $vertexEdgeList;
}


proc int processOriginFaces( string $object, string $crackEdgeList[], int $shardIndexList[] )
//
// This procedure process the edges/faces about the origin of the crack.
// It first determines the edges about the origin and then orders them in a
// clockwise fashion about the origin.  This is done so we can easily assign
// the shards off the origin an index.  Final, this procedure assigns the
// faces off the origin a shard index.
//
{
	string $edge;
	int    $isCrackEdge;
	int    $faceIndex;
	int    $edgeFaceCount;
	string $edgeFaceList[];
	global int $gSelectedVertexId;

	// Get the list of edges off the origin.
	//
	string $firstEdge[]    = createFirstEdgeList( $crackEdgeList );
	int    $firstEdgeCount = size( $firstEdge );

	// Get the origin vertex and its associated edges.
	//
	string $origin           = $object + ".vtx[" + $gSelectedVertexId + "]";
	string $originEdgeList[] = getEdgeList( $origin );
	int    $originEdgeCount  = size( $originEdgeList );
	int    $edgeIndex        = 0;
	int    $edgeOrigin       = false;

	// Determine if the origin vertex is on a non shared edge.  If
	// it is, make sure we start processing on one of the non shared
	// edges.  This is so we process all the edges.
	//
	for ( $i = 0; $i < $originEdgeCount; $i++ )
	{
		// Check to see if the crack starts on a non shared edge.
		//
		$faceList  = getFaceList( $originEdgeList[$i] );
		int $count = size( $faceList );

		if ( $count == 1 )
		{
			$edgeIndex  = $i;
			$edgeOrigin = true;
			$originEdgeCount = $originEdgeCount - 1;
			break;
		}
	}

	// Order the origin edge list.  We do this so we can number the shards
	// off the origin.
	//
	$originEdgeList = orderOriginEdgeList( $origin, $originEdgeList, $edgeIndex );
	$edgeFaceList   = orderOriginFaceList( $originEdgeList );

	int $shardId    = 1;
	int $maxShardId = 1;

	int $index = 0;
	int $firstEdgeIsCrackEdge = false;

	// For each edge off the origin, determine which shard it belongs to.
	//
	for ( $i = 0; $i < $originEdgeCount; $i++ )
	{
		$isCrackEdge = false;
		$edge        = $originEdgeList[$i];

		// First determine if the edge is a crack edge.
		//
		for ( $j = 0; $j < $firstEdgeCount; $j++ )
		{
			if ( $edge == $firstEdge[$j] )
			{
				$isCrackEdge = true;
				break;
			}
		}

		if ( $edgeOrigin )
		{
			// If this is not the first edge in the list and the
			// edge is a crack edge then increament the shard id.
			//
			if ( $i != 0 ) 
			{
				if ( $isCrackEdge )
				{
					$shardId++;
				}
			}

			$faceIndex = getIndex( $edgeFaceList[ $index ] );
			$shardIndexList[ $faceIndex ] = $shardId;
			$index++;
		}
		else
		{
			$faceIndex = getIndex( $edgeFaceList[ $index ] );
			$shardIndexList[ $faceIndex ] = $shardId;
			$index++;

			// If this is not the first edge in the list and the
			// edge is a crack edge then increament the shard id.
			//
			if ( $isCrackEdge )
			{
				if ( $i == 0 )
				{
					$firstEdgeIsCrackEdge = true;
				}
				else
				{
					// Reset the shard ID if we have crossed the last edge.
					//
					if ( $shardId == $firstEdgeCount )
					{
						$shardId = 1;
					}
					else
					{
						$shardId++;
					}
				}
			}
		}

		$maxShardId = max( $maxShardId, $shardId );
	}

	// If the first edge was a crack we need to assign it 
	// the last shard index.
	//
	if ( $firstEdgeIsCrackEdge )
	{
		$faceIndex = getIndex( $edgeFaceList[ 0 ] );
		$shardIndexList[ $faceIndex ] = $shardId;
	}

	return $maxShardId;
}


proc int processOriginFaces0( string $object, string $crackEdgeList[], int $shardIndexList[] )
//
// This procedure process the edges/faces about the origin of the crack.
// It first determines the edges about the origin and then orders them in a
// clockwise fashion about the origin.  This is done so we can easily assign
// the shards off the origin an index.  Final, this procedure assigns the
// faces off the origin a shard index.
//
{
	string $edge;
	int    $isCrackEdge;
	int    $faceIndex;
	int    $edgeFaceCount;
	string $edgeFaceList[];
	global int $gSelectedVertexId;


	// Get the list of edges off the origin.
	//
	string $firstEdge[]    = createFirstEdgeList( $crackEdgeList );
	int    $firstEdgeCount = size( $firstEdge );

	// Get the origin vertex and its associated edges.
	//
	string $origin           = $object + ".vtx[" + $gSelectedVertexId + "]";
	string $vertexEdgeList[] = getEdgeList( $origin );
	int    $vertexEdgeCount  = size( $vertexEdgeList );
	int    $edgeIndex        = 0;
	int    $edgeOrigin       = false;

	// Determine if the origin vertex is on a non shared edge.  If
	// it is, make sure we start processing on one of the non shared
	// edges.  This is so we process all the edges.
	//
	for ( $i = 0; $i < $vertexEdgeCount; $i++ )
	{
		// Check to see if the crack starts on a non shared edge.
		//
		$faceList  = getFaceList( $vertexEdgeList[$i] );
		int $count = size( $faceList );

		if ( $count == 1 )
		{
			$edgeIndex  = $i;
			$edgeOrigin = true;
			break;
		}
	}

	// Order the origin edge list.  We do this so we can number the shards
	// off the origin.
	//
	$vertexEdgeList = orderOriginEdgeList( $origin, $vertexEdgeList, $edgeIndex );

	int $shardId    = 1;
	int $maxShardId = 1;

	// For each edge off the origin, determine which shard it belongs to.
	//
	for ( $i = 0; $i < $vertexEdgeCount; $i++ )
	{
		$isCrackEdge = false;
		$edge        = $vertexEdgeList[$i];

		// First determine if the edge is a crack edge.
		//
		for ( $j = 0; $j < $firstEdgeCount; $j++ )
		{
			if ( $edge == $firstEdge[$j] )
			{
				$isCrackEdge = true;
				break;
			}
		}

		// Get the edge face list and assign the faces to a shard.
		//
		$edgeFaceList  = getFaceList( $edge );
		$edgeFaceCount = size( $edgeFaceList );

		for ( $j = 0; $j < $edgeFaceCount; $j++ )
		{
			$faceIndex = getIndex( $edgeFaceList[$j] );

			$shardIndexList[ $faceIndex ] = $shardId;

			// If the edge is a shard edge then increament the
			// shard edge id.
			//
			if ( $isCrackEdge == true )
			{
				$shardId++;

				$maxShardId = max( $maxShardId, $shardId );

				// Reset the shard ID if we are working with a non shared origin
				// vertex (i.e. the origin vertex is not on an edge).
				//
				if ( ($edgeOrigin == false) && ($shardId == $firstEdgeCount+1) )
				{
					$shardId = 1;
				}

				$isCrackEdge = false;
			}
		}
	}

	return $maxShardId;
}


proc assignShardIndicesAlongCracks( string $crackEdgeList[], int $shardIndexList[], 
								    int $maxShardId, int $verbose )
{
	string $edge;
	string $edgeFaceList[];

	int $crackCount = size( $crackEdgeList );

	if ( $verbose == true )
	{
		print( (uiRes("m_crackShatter.kAssigningFacets")) );
	}

	int    $crossed;
	int    $count  = 0;
	int    $cracksHaveCrossed = false;
	int    $crossedCrackList[];
	int    $crossedEdgeCount;
	string $crossedEdges[];

	// For each crack edge, walk the crack and place the facets 
	// along the edges into there respective shards.
	//
	for ( $i = 0; $i < $crackCount; $i++ )
	{
		string $crackEdges[];

		// Assume the crack has not crossed another crack.
		//
		$crossed = false;

		// Get individual edge list for the crack.
		//
		tokenize( $crackEdgeList[ $i ], " ", $crackEdges );

		int $edgeCount = size( $crackEdges );

		// Determine the shard which the facet along the crack edges
		// belong.  There is no need to check the first edge again.
		//
		for ( $j = 1; $j < $edgeCount; $j++ )
		{
			// For this edge, get its face list.
			//
			$edge         = $crackEdges[$j];
			$edgeFaceList = getFaceList( $edge );

			// For each face, assign it a shard id.  We determine the shard id 
			// by look at the surrounding faces shard ids.
			//
			for ( $k = 0; $k < 2; $k++ )
			{
				int $surroundingIndices[];

				$face = $edgeFaceList[$k];

				$surroundingIndices = getUniqueSurroundingFaces( $face, $edge, $crackEdgeList );
				int    $surroundingFaceCount = size( $surroundingIndices );
				int    $index = ($k == 0) ? 1 : 0;

				for ( $ii = 0; $ii < $surroundingFaceCount; $ii++ )
				{
					$faceIndex = $surroundingIndices[$ii];

					// If two cracks have crossed then we need to assign the face
					// a new shard id.
					//
					if ( $cracksHaveCrossed == true )
					{
						int $edgeFaceIndex = getIndex( $face );

						if ( $shardIndexList[$edgeFaceIndex] == 0 )
						{
							$shardIndexList[ $edgeFaceIndex ] = $maxShardId;
						    $cracksHaveCrossed = false;
							$maxShardId++;
						}

						break;
					}

					// If the shard id for a sorrounding face is not zero
					// then assign the id to this face.
					//
					else if ( $shardIndexList[ $faceIndex ] != 0 )
					{
						int $update = true;
						int $edgeFaceIndex = getIndex( $face );

						// If the shard id has been assigned then make sure
						// we assign the smallest id to the face.
						//
						if ( $shardIndexList[ $edgeFaceIndex ] != 0 )
						{
							if ( $shardIndexList[$faceIndex] > $shardIndexList[$edgeFaceIndex] )
							{ 
								$update = false;
							}
						}

						if ( $update )
						{
							$shardIndexList[ $edgeFaceIndex ] = $shardIndexList[ $faceIndex ];
						}
					}
				}
			}

			// Check to see if this edge is crossing another crack.
			//
			$cracksHaveCrossed = checkCrackCrossing( $j, $crackEdges, $i, $crackEdgeList );

			if ( $cracksHaveCrossed == true )
			{
				$crossed = true;
		     	$crossedEdges[ $crossedEdgeCount ] = $edge;
				$crossedEdgeCount++;
			}
		}

		if ( $crossed == true )
		{
			$crossedCrackList[$count] = $i;
			$count++;
		}
	}

	if ( $verbose )
	{
		print( (uiRes("m_crackShatter.kCrackCrossCheck")) );
	}

	// If two or more cracks have crossed then make sure the cracks have the
	// proper shard indices.
	//
	for ( $i = 0; $i < $count; $i++ )
	{
		string $crackEdges[];
		int    $crackIndex = $crossedCrackList[$i];

		$cracksHaveCrossed = false;

		// Get individual edge list for the crack.
		//
		tokenize( $crackEdgeList[ $crackIndex ], " ", $crackEdges );

		int $edgeCount = size( $crackEdges );

		// Determine the shard which the facet along the crack edges
		// belong.  There is no need to check the first edge again.
		//
		for ( $j = 1; $j < $edgeCount; $j++ )
		{
			// Skip the crossed cracks.
			//
			if ( $cracksHaveCrossed == true )
			{
				 $cracksHaveCrossed = false;
				 continue;
			}

			// For this edge, get its face list.
			//
			$edge         = $crackEdges[$j];
			$edgeFaceList = getFaceList( $edge );

			// For each face, make sure it has the smallest shard id of its
			// surrounding faces.
			//
			for ( $k = 0; $k < 2; $k++ )
			{
				int $surroundingIndices[];
				$face = $edgeFaceList[$k];

				// Get only faces which are not across cracks.
				//
				$surroundingIndices = getUniqueSurroundingFaces( $face, $edge, $crackEdgeList );

				int $surroundingFaceCount = size( $surroundingIndices );

				int $index = ($k == 0) ? 1 : 0;
				int $minIndex = $maxShardId;

				for ( $ii = 0; $ii < $surroundingFaceCount; $ii++ )
				{
					$faceIndex = $surroundingIndices[$ii];

					if ( $shardIndexList[ $faceIndex ] != 0 )
					{
						$minIndex = min( $minIndex, $shardIndexList[ $faceIndex ] );
					}
				}

				int $edgeFaceIndex = getIndex( $face );
				$shardIndexList[ $edgeFaceIndex ] = $minIndex;
			}

			// Check the edge against the crossed edge list to determine
			// if the edge crosses a crack.
			//
			for ( $k = 0; $k < $crossedEdgeCount; $k++ )
			{
				if ( $edge == $crossedEdges[$k] )
				{
					$cracksHaveCrossed = true;
					break;
				}
			}
		}
	}
}


proc int[] determineShardIndices( string $object, string $crackEdgeList[], int $verbose )
//
// Returns an integer array identifying the shard to which each facet belongs.
// There is one array position for each facet, storing its shard index.  
// $crackEdgeList is a list of strings identifying all the edges which belong
// to any crack, in format <object>.e[ <index> ].
//
// Algorithm: 
// first assign the facets about the origin shard indices.  Then the facets along
// each crack are assign shard indices.  Final, the remaining facets are assigned 
// indices according to which cracks they lie between.
//
{
	int $shardIndexList[];
	int $totalFaceCount[] = `polyEvaluate -face $object`;

	// Clear the shard index list.  This list will store which shard
	// each facet goes into.
	//
	for ( $i = 0; $i < $totalFaceCount[0]; $i++ )
	{
		$shardIndexList[ $i ] = 0;
	}

	// First process the edges about the origin.  This will assign the
	// faces about the origin a shard index.
	//
	int $maxShardId = processOriginFaces( $object, $crackEdgeList, $shardIndexList );

	// Assign shard indices to the faces along the cracks.
	//
	assignShardIndicesAlongCracks( $crackEdgeList, $shardIndexList, $maxShardId, $verbose );

	// Now we need to process the rest of the facets and determine which 
	// shards then belong to.  We may have to iterate over the face list a few
	// times to determine where all the facets belong.
	//
	processRemainingFacets( $object, $shardIndexList, $crackEdgeList, $verbose );

	return $shardIndexList;
}


proc vector projectSplit( vector $splitVector, string $face, string $edge )
//
// This proc projects the given vector onto a face.
//
{
	vector $projectedVector = $splitVector;
	string $vertexList[]    = getVertexList( $edge );
	string $faceList[]      = getFaceList( $edge );

	if ( size( $vertexList ) > 0 )
	{
		vector $normal0;
		vector $normal1;

		// Determine the axis we want to rotate the split vector about.  This
		// is the start edge.
		//

		// Get the normals of the two faces along the edge.  This will
		// help us determine the angle for the projection and the axis
		// we want to project the split about.  Note that order is important.
		// We always want the axis to be:
		//
		//		cross( previousSplitFace, faceWeAreSplitting );
		//
		if ( $faceList[0] == $face )
		{
			$normal0 = getFaceNormal( $faceList[1] );
			$normal1 = getFaceNormal( $faceList[0] );
		}
		else
		{
			$normal0 = getFaceNormal( $faceList[0] );
			$normal1 = getFaceNormal( $faceList[1] );
		}

		// Determine the axis to project the split about.
		//
		vector $axis = cross( $normal0, $normal1 );

		float $radianAngle = angle( $normal0, $normal1 );

		// If the projection angle is greater then 0 then project the
		// split.
		//
		if ( $radianAngle != 0.0 &&
			 abs($radianAngle - 3.141592654) > 0.000001 )
		{
			$projectedVector = rot( $splitVector, $axis, $radianAngle ); 
		}
	}

	return $projectedVector;
}

proc float addRandomPerturbation( float $returnParam, float $perturb )
//
// Description:
//   Adds a random offset to $returnParam in the range (-$perturb, +$perturb)
// and returns the resulting value.  However, always returns a result in the
// range [0.001, 0.999], clamping if necessary.
{
	// Determine the perturbation of the edge.  This is done by taking the perturbation
	// factor and randomly choosing a value within its range.  Then factor is 
	// then applied to the edge parameterization.  If the parameter is not within
	// range (0-1) then we first try to perturb the parameter in the opposite 
	// direction.  If we cannot do that we clamp it to 0.0 - 1.0;
	//
	//
	float $offset = rand( -$perturb, $perturb );
	
	float $testSum = $returnParam + $offset;
	if ( ($testSum <= 0.0) || ($testSum >= 1.0) )
	{
		$offset = - $offset;
	}

	$returnParam += $offset;

	// We do not want the split to be at exactly 0.0 or 1.0.  
	// We cannot accurately determine the crack length if we do.
	//
	if ($returnParam <= 0.001)
	{
		$returnParam = 0.001;
	}
	else if ($returnParam >= 0.999)
	{
		$returnParam = 0.999;
	}

	return $returnParam;
}

proc float[] getNextSplit( vector $lastSplit, string $startEdge, vector	$startPoint, string $face, float $perturb )			   
//
// This proc determines the next split for the crack.
// It returns an array with two elements: element 0 is the index of the next edge to split,
// and elememt 1 is the param for the polySplit.
//
// Input parameters:
//  $startEdge is the edge on which the next split is to start ???
//  $face is the face which is being split.
//  $perturb is the random perturbation factor the user wants us to use in creating the split. 
//     If this is zero, each split should be a straight line.
//  $startPoint is the point on $startEdge where the split begins.
//  $lastSplit is the direction of the split of the previous polygon in the crack.
//
{
	// return value 0 is the index into the edge list of the end edge
	// return value 1 is the corresponding endParam value
	//
	float $splitInfo[2];
	float $edgeAngle[2];

	// Vector passed to us was in the plane of the last polygon.
	// Modify it to a vector in the plane of the new polygon.
	// This involves projecting it into that plane.
	//
	$lastSplit = projectSplit( $lastSplit, $face, $startEdge );
	vector $splitVector = $startPoint - $lastSplit;

	// Get the vector 0 parameter of the start edge.
	//
	vector $startEdgeV0 = getEdgeVertex( $startEdge, 0.0 );
	vector $edgeVec     = $startPoint - $startEdgeV0;

	float $endParam    = 0.0;
	float $returnParam = 0.0;

	// Get the edges of the face so we can determine the next 
	// edge to split.
	// $edgeList stores the list of indices (into the object's
	// edge list) which define the current face).
	//
	string $edgeList[]  = getEdgeList( $face );
	int $edgeIndex = -1;
	int $edgeCount = size( $edgeList );

	int $startEdgeIndex = 0;

	// Determine which edge and param value to use.
	//
	for ( $i = 0; $i < $edgeCount; $i++ )
	{
		if ( $edgeList[$i] != $startEdge )
		{
			vector $edgeVector[] = getEdgeVertices( $edgeList[$i] );

			// See if $splitVector intersects the line segment ($edgeVector[0], $edgeVector[1]).
			// If so, that is the edge we want, and $endParam is the split value for
			// the polySplit command.
			//
			$endParam = getLineIntersection( $splitVector, $startPoint, 
											 $edgeVector[0], $edgeVector[1] );

			if ( ($endParam >= 0.0) && ($endParam <= 1.0) )
			{
				$edgeIndex   = $i;
				$returnParam = $endParam;
				break;
			}
	 	}
		else
		{
			$startEdgeIndex = $i;
		}
	}

	// Did we get a valid edge?  If not (i.e. if edge index is -1),
	// then pick a random edge and parameterization.
	//
	if ( $edgeIndex == -1 )
	{
		$edgeIndex = $startEdgeIndex;

		while ($edgeIndex == $startEdgeIndex )
		{
			$edgeIndex = rand( 0, $edgeCount );
		}

		// Generate a random split parameter.  This is different from the perturbation;
		// we are generating both edge and parameter randomly because our algorithm
		// for choosing them failed.  
		// Note that we do not want the split to be at exactly 0.0 or 1.0, 
		// because we cannot accurately determine the crack length if we do.
		// 
		//
		$returnParam = rand( 0.001, 0.999 );

//		print( "Bad Split : " + $edgeList[$startEdgeIndex] + " " + 
//							    $edgeList[$edgeIndex]      + " " + 		$returnParam + "\n" );
	}
	else
	{
		// Add the user's random perturbation factor to whatever split was generated.
		// Also, clamp the value to the range [0.001, 0.999].
		// 
		$returnParam = addRandomPerturbation( $returnParam, $perturb );
	}

	$splitInfo[0] = getIndex( $edgeList[ $edgeIndex ] );
	$splitInfo[1] = $returnParam;
	
	return $splitInfo;
}

global string $gShatteredObject;

proc string getShatteredObject()
{
	global string $gShatteredObject;

	return $gShatteredObject;
}

global int $gOriginalEdgeCount;

proc string getOriginalEdgeCount()
{
	global int $gOriginalEdgeCount;

	return $gOriginalEdgeCount;
}

global int $gOriginalFaceCount;

proc string getOriginalFaceCount()
{
	global int $gOriginalFaceCount;

	return $gOriginalFaceCount;
}

proc string crackShatterObject( string $object, string $name, int $crackCount, int $crackLength, 
							    int $triangulate, float $perturb, float $extrude, int $original,
								string $postOp, int $makeRigid, int $verbose )
//
// This procedure actually does the shattering of the given
// object.  We can assume that the object is either of
// nurbsSurface shape or a polygonal mesh shape, because the
// procedure that calls it will only do so for those types
// of objects.
//
{
	int     	  $count[];
	global string $gShatteredObject;
	global int    $gOriginalEdgeCount;
	global int    $gOriginalFaceCount;

	string $shapeList[] = `ls -type shape`;

    string $newObject = "";

    // I want to know that parent transform of this
    // shape, so that I can use its name whae I name
    // my new objects.
    //
    string $parent[] = `listRelatives -parent $object`;

    // First, get a polygonal version of this shape.
    //
    string $type = `nodeType $object`;
    if( $type == "nurbsSurface" )
    {
        // If this shape is a nurbsSurface shape, then I
        // need to convert it into a polygonal mesh.
        //
        nurbsToPoly -ch 0 $object;
        $newObject = getSelectedObject( 0 );
    }
    else
    {
        // If this shape is a polygonal mesh shape, then
        // I just duplicate it to get a version that I
        // will shatter, since I do not want to change
        // the original object.
        //
        string $duplicate[] = `duplicate $object`;
        select $duplicate[0];


		// If this object/hierarchy contained a rigid body or bodies, 	
	    // the rigid body nodes have also be duplicated. We do not want those
	    // copies.  Delete them now.  The ls command used here returns all
	    // rigidBody nodes at or below this level in the hierarchy.
	    //
	    delete `ls -objectsOnly -dag -allPaths -type rigidBody $duplicate[0]`;		
    }

	// Name the shattered object.
	//
	if ( size( $name ) > 0 )
	{
       	rename ( $name );
	}
	else
	{
       	rename ("shattered_"+$parent[0]);
	}

	// Store the facet and edge information for the original
	// tesselated object.
	//
    $newObject = getSelectedObject( 0 );

	$gShatteredObject = $newObject;
	$count = `polyEvaluate -edge $newObject`;
	$gOriginalEdgeCount =  $count[0];
	$count = `polyEvaluate -face $newObject`;
	$gOriginalFaceCount =  $count[0];

    // Now, make sure that the polygonal mesh is made up of
    // only triangles.
    //
    if ( $triangulate == true )
	{
        polyTriangulate -ch 1 ($newObject+".f[0:"+($count[0]-1)+"]");
	}

	// Create the cracks on the surface.
	//
	string $crackEdges[];
	clear( $crackEdges );

	// Turn down the perturbation factor a bit.
	//
	$perturb = $perturb * 0.7;

	$crackEdges = createCracks( $newObject, $crackCount, $crackLength, $perturb, $verbose);

	int $crackEdgeCount = size( $crackEdges );

	// Make sure we processed the cracks.
	//
	if ( $crackEdgeCount < 1 )
	{
		delete $newObject;
		$newObject = "";
		return $newObject;
	}

 	processOriginalObject( $object, $newObject, $original, $postOp, $makeRigid );

	// break surface into shards, unless post operation is "cracks on surface."
	//
	if ( $postOp != "cracks on surface" )
	{
		int    $shardIndexList[];
		string $shardList[];

		$shardIndexList = determineShardIndices( $newObject, $crackEdges, $verbose );

		if ( strcmp( $postOp, "sets" ) )
		{
			extractShards( $newObject, $shardIndexList, $verbose );

			// Separate the shard and indicate we do not want to keep 
			// the original object.
			//
			$shardList = separateShards( $newObject, false, $verbose );
		}

 		int $makeConnections = false;

        if ( $original == 4 )
        {
            $makeConnections = true;
        }

		postProcessShards( $newObject, $shardList, $shardIndexList, $extrude, $triangulate,
						   $postOp, $shapeList, $object, $makeConnections, $verbose );
	}


//	objectDisplay( $object, $original );

	if (size($newObject)>0)
		print( (uiRes("m_crackShatter.kShatterSucceeded")) );

    return $newObject;
}


global proc verifyCrackEdges( string $crackList[] )
// 
// This proc check each crack to see if all the edges are in the
// crack list.  The crack may have been split and a new edge added.
//
{
	int    $crackCount = size( $crackList );
	int    $found;
	string $edge;
	string $nextEdge;
	string $crackEdgeList[];
	

	// For each crack, verify that the crack has not been split.  If
	// it has, determine the new edge.
	//
	for ( $i = 0; $i < $crackCount; $i++ )
	{
		string $newEdge;

		clear( $crackEdgeList );

		tokenize( $crackList[$i], " ", $crackEdgeList );

		int $crackLength = size( $crackEdgeList );

		// Walk the crack and make sure adjacent edges have shard vertices.
		//
		for ( $j = 0; $j < $crackLength-1; $j++ )
		{
			$found    = false;
			$edge     = $crackEdgeList[$j];
			$nextEdge = $crackEdgeList[$j+1];
		
			string $edgeVertexList[]     = getVertexList( $edge );
			string $nextEdgeVertexList[] = getVertexList( $nextEdge );

			// Find the common vertex.
			//
			for ( $k = 0; $k < 2; $k++ )
			{
				for ( $ii = 1; $ii >= 0; $ii-- )
				{
					if ( $edgeVertexList[$k] == $nextEdgeVertexList[$ii] )
					{
						$found = true;
						break;
					}
				}

				if ( $found == true )
				{
					break;
				}
			}

			// A common vertex was not found.  We need to find the edge which separates
			// these edges.
			//
			if ( $found == false )
			{
				// Get the edge list for the first edges vertices.
				//
				string $vertexEdgeList0[] = getEdgeList( $edgeVertexList[0] );
				string $vertexEdgeList1[] = getEdgeList( $edgeVertexList[1] );

				// For each of the next edges vertices, get an edge list and
				// check the edge list against the other edges vertex edge list.
				// We are trying to find a common edge.
				//
				for ( $k = 0; $k < 2; $k++ )
				{
					string $edgeList[] = getEdgeList( $nextEdgeVertexList[$k] );
					int    $edgeCount  = size( $edgeList );

					for ( $ii = 0; $ii < $edgeCount; $ii++ )
					{
						int $vertexEdgeCount = size( $vertexEdgeList1 );
	
						for ( $jj = 0; $jj < $vertexEdgeCount; $jj++ )
						{
							if ( $edgeList[$ii] == $vertexEdgeList0[$jj] )
							{
								$newEdge = $edgeList[$ii];
								$found = true;
								break;
							}
						}
	
						if ( $found == true )
						{
							break;
						}
	
						// Check the other edge list.
						//
						$vertexEdgeCount = size( $vertexEdgeList0 );
	
						for ( $jj = 0; $jj < $vertexEdgeCount; $jj++ )
						{
							if ( $edgeList[$ii] == $vertexEdgeList1[$jj] )
							{
								$newEdge = $edgeList[$ii];
								$found = true;
								break;
							}
						}
	
						if ( $found == true )
						{
							break;
						}
					}
	
					if ( $found == true )
					{
						break;
					}
				}

				// If the edge was found then add it to the crack list.
				//
				if ( $found == true )
				{
					string $newCrack = "";

					for ( $k = 0; $k < $crackLength; $k++ )
					{
						$newCrack += $crackEdgeList[$k] + " ";

						if ( $k == $j )
						{
							$newCrack += $newEdge + " ";
						}
					}

					$crackList[$i] = $newCrack;
					clear( $crackEdgeList );
					tokenize( $crackList[$i], " ", $crackEdgeList );
					$crackLength++;
				}
			}
		}
	}
}


global proc int checkCrackCrossing( int $edgeIndex, string $crackEdges[], 
								    int $crackIndex, string $crackList[]  )
{
	string $nextEdge;

	// Get the edge to check for another edge crossing.
	//
	string $edge      = $crackEdges[ $edgeIndex ];
	int    $edgeCount = size( $crackEdges );

	// We need to check the edge against the next edge in the crack.  If
	// this edge is at the edge of the crack then there is no need to 
	// check it.
	//
	if ( $edgeIndex < ($edgeCount - 1) )
	{
		// Get the next edge.
		//
		$nextEdge = $crackEdges[ $edgeIndex + 1 ];

		// We need to find the common vertex between the edges.
		//
		int    $found = false;
		string $commonVertex;
		string $edgeVertexList[]     = getVertexList( $edge );
		string $nextEdgeVertexList[] = getVertexList( $nextEdge );

		// Find a common vertex for the edges.
		//
		for ( $i = 0; $i < 2; $i++ )
		{
			for ( $j = 1; $j >= 0; $j-- )
			{
				// If the vertices are the same then we have found the
				// common vertex.
				//
				if ( $edgeVertexList[$i] == $nextEdgeVertexList[$j] )
				{
					$commonVertex = $edgeVertexList[$i];
					$found = true;
					break;
				}
			}

			if ( $found == true )
			{
				break;
			}
		}

		// If a common vertex for the edges was found then see it that
		// vertex is in any of the other edges.  If so, we found a 
		// crossing point.
		//
		if ( $found == true )
		{
			int    $crackListCount = size( $crackList );
			string $crackEdgeList[];
			string $vertices[];
			int    $vertexCount;
	
			// For each crack, check for a cross with this edge.
			//
			for ( $i = 0; $i < $crackListCount; $i++ )
			{
				// Do not check the crack this edge belongs to.
				//
				if ( $i != $crackIndex )
				{
					tokenize( $crackList[$i], " ", $crackEdgeList );
	
					int $crackEdgeCount = size( $crackEdgeList );
	
					// For each of the cracks edges check its vertices
					// against the common vertex.
					//
					for ( $j = 0; $j < $crackEdgeCount; $j++ )
					{
						clear( $vertices );

						$vertices = getVertexList( $crackEdgeList[$j] );

						for ( $k = 0; $k < 2; $k++ )
						{
							if ( $vertices[$k] == $commonVertex )
							{
								return true;
							}
						}
					}
				}
			}
		}
	}

	return false;
}


global proc int[] getUniqueSurroundingFaces( string $face, string $edge, string $crackList[] )
//
// This procedure returns a list of faces which surround the given face.  The
// returned faces will be unique to a give shard (i.e. the face do not cross
// cracks).
//
{
	int    $faceIndexList[];
	string $edgeList[] = getEdgeList( $face );
	int    $edgeCount  = size( $edgeList );
	int    $faceCount  = 0;
	int    $faceIndex  = getIndex( $face );

	clear( $faceIndexList );

	// For each edge associated with the face get the faces and
	// added them to the face list (if the face is not the face
	// passed into this procedure).
	//
	for ( $i = 0; $i < $edgeCount; $i++ )
	{
		int $isEdgeInCrack = edgeInCrack( $edgeList[$i], $crackList );

		// If the edge is not a crack edge and the edge is not the
		// one passed in to this proc then process it.
		//
		if ( ($isEdgeInCrack == false) && ($edgeList[$i] != $edge) )
		{
			int $edgeFaceIndexList[] = getFaceIndexList( $edgeList[$i] );
			int $edgeFaceIndexCount  = size( $edgeFaceIndexList );
	
			// Check the face list against the center face.  If it is
			// unique then and it to the list.
			//
			for ( $j = 0; $j < $edgeFaceIndexCount; $j++ )
			{
				if ($edgeFaceIndexList[$j] != $faceIndex )
				{
					$faceIndexList[ $faceCount ] = $edgeFaceIndexList[$j];
					$faceCount++;
					break;
				}
			}
		}
	}

	return $faceIndexList;
}


global proc int edgeInCrack( string $edge, string $crackList[] )
//
// This proc returns true if the given edge is on a crack.
// Otherwise it returns false.
//
{
	int    $crackCount = size( $crackList );
	int    $crackEdgeCount;
	string $crackEdges[];

	// First get the number of edges in the shattered object and
	// check to see if the edge index is less then the edge count 
	// for the object.
	//
	int $edgeCount = getOriginalEdgeCount();
	int $edgeIndex = getIndex( $edge );

	// If the edge index is greater then or equal to the
	// original edge count then we know the edge is not a new
	// crack edge.
	//
	if ( $edgeIndex >= $edgeCount )
	{
		for ( $i = 0; $i < $crackCount; $i++ )
		{
			tokenize( $crackList[$i], " ", $crackEdges );
	
			$crackEdgeCount = size( $crackEdges );
	
			for ( $j = 0; $j < $crackEdgeCount; $j++ )
			{
				if ( $edge == $crackEdges[$j] )
				{
					return true;
				}
			}
		}
	}

	return false;
}

global proc string getNextFaceToSplit( string $startEdge, string $previousFaceSplit )
//
// Description:
//  returns the name of a face adjacent to $startEdge which is 
// not $previousFaceSplit.  If no such face exists, returns empty string.
{	
	string $nextFace = "";

	// Store the index of the last face split.  We do not
	// want to split this one again.
	//
	int $lastFaceIndex = getIndex( $previousFaceSplit );
	
	// Get all faces associated with the new start edge.
	//
	string $faceList[]  = getFaceList( $startEdge );
	
	// Get the next face to split.  We want to make sure we
	// do not split the face we just split.
	//
	int $j;
	int $faceCount = size( $faceList );
	for ( $j = 0; $j < $faceCount; $j++ )
	{
		$faceIndex = getIndex( $faceList[ $j ] );
		if ( $faceIndex != $lastFaceIndex )
		{
			$nextFace = $faceList[ $j ];
			break;
		}
	}

	return $nextFace;
}

global string $gUsedFaceList[];
global int    $gUsedFaceCount = 0;

global proc string[] createCracks( string $object, int $crackCount, int	$crackLength, float $perturb, int $verbose )

//
// Creates approximately $crackCount cracks.  Returns a string array with number of entries
// equal to the number of cracks created.  Each entry contains the edges in that crack, in
// <object>.e[ <index> ] format, with spaces in between.
// Each crack is created by picking a succession of vertices and
// calling polySplit.  The crack will edge end when either the
// the maximum crack length $crackLength is reached or the crack hits 
// the edge of the surface.
// Assigns the value of global variables $gSelectedVertexId, $gUsedFaceList, and $gUsedFaceCount.
{
	global string $gUsedFaceList[];
	global int    $gUsedFaceCount;
	global int    $gSelectedVertexId;

	// the return data, a list of strings identifying edges.
	// Each string is in form <objectName>.e[ <edge index> ]
	//
	string $crackEdgeList[];

	clear( $gUsedFaceList );
	$gUsedFaceCount = 0;

	// These items are arrays simply because that is what polyEvaluate
	// returns.  Only the 0 positions are meaningful.  They store the
	// object's original vertex, face, and edge count respectively.
	// 
	int $vertexCount[]     = `polyEvaluate -vertex $object`;
	int $maxFaceCount[]    = `polyEvaluate -face   $object`;
	int $startEdgeCount[]  = `polyEvaluate -edge   $object`;
	int $originalEdgeCount = $startEdgeCount[0];

	// Get the vertex to start the crack from.
	// This is selected by the user before running the effect.
	//
	int $vertexIndex = getSelectedVertex( $object, $verbose );
	// If no vertex was selected, can't go any further.
	//
	if ( $vertexIndex == -1 )
	{
		return $crackEdgeList;
	}

	$gSelectedVertexId = $vertexIndex;

	// Determine the world space position of the initial vertex.
	//
	string $originVertex     = $object + ".vtx[" + $vertexIndex + "]";
	float  $vertexPosition[] = `xform -ws -q -t $originVertex`;

	if ( $verbose )
	{
		string $fmt = (uiRes("m_crackShatter.kCreatingCracks"));
		print( `format -s $crackCount $fmt` );
	}

	// We record the vertex count at the end of making each crack.
	// This willl et us figure out which edges belong to which cracks.
	// We also record the starting vertex count.
	//
	int $originalVertexCount = getVertexCount( $object );
	int $vertexCountAfterCrack[];

	// For each crack, create and execute the polySplit command.
	//
	for( $k = 0; $k < $crackCount; $k++ )
	{
		// Create the first split off the origin for this crack.
		//
		select $originVertex;
		refresh;
		string $firstSplit[] = createFirstSplit( $originVertex, $originalEdgeCount );

		// Build the first part of the split command, for the first split.
		//
		string $splitCmd = $firstSplit[0];

		// Tokenize the split command so we can determine the first split parameters.
		//
		string $cmdList[];
		tokenize( $splitCmd, " ", $cmdList );

		// $startIndex and $endIndex are indices of the next split in
		// the object's edge list.  
		// $endParam is the end param parameter for polysplit, corresponding to $endIndex.
		// $startEdge is the starting edge for the current segment of the crack
		//
		int    $startIndex = (int)   $cmdList[4]; 
		int    $endIndex   = (int)   $cmdList[7];
		float  $endParam   = (float) $cmdList[8];
		string $startEdge  = $object + ".e[" + $startIndex + "]";
		select -add $startEdge;

		// Get the face which was split.
		//
		string $face = $firstSplit[1];

		// Initialize the list of edges we have split.  We will use this
		// list to determine if the crack has wrapped upon itself.
		//
		int    $splitEdges[];
		clear( $splitEdges );
		$splitEdges[0] = $startIndex;
		$splitEdges[1] = $endIndex;

		int    $listIndex;
    	int    $actualCrackSize = 1;

	    vector $startVertex =  << $vertexPosition[0], $vertexPosition[1],  $vertexPosition[2] >>;
		vector $endVertex;

		// Create a list of edges and edge parameters for the polySplit command.
		// This list defines one crack.  Stop when we reach maximum $crackLength
		// or can't go any further.  Index == -1 signals the latter condition.
		//
		while( ($actualCrackSize < $crackLength) && ($endIndex >= 0) )
		{
			float  $splitInfo[2];

			// Determine end edge and vertex of the most recent split.
			//
			string $endEdge    = $object + ".e[" + $endIndex + "]";
			select -add $endEdge;
			refresh;
			$endVertex = getEdgeVertex( $endEdge, $endParam );

			// $splitVector is a Mel vector lying along the direction of the split.
			// Determine the direction of the split using the previous start
			// and end vertices.  This is used to propogate the split to the 
			// next facet.
			//

			vector $splitVector = $endVertex - $startVertex;

			// The previous end edge/vertex become the new start edge/vertex.
			//
			$startEdge   = $endEdge;
			$startVertex = $endVertex;
			$startIndex  = getIndex( $startEdge );

			$face = getNextFaceToSplit( $startEdge, $face );

			if (size($face) == 0)
			{
				break;
			}
			
			// Given the previous split ($splitVector), the start edge for the next split,
			// the $face we are splitting, and the user's $perturb val, determine
			// the edge index ($splitInfo[0]) and the parameterization of the split ($splitInfo[1])
			// for the next split. $splitInfo[0] may be -1; we handle that correctly.
			//
			$splitInfo = getNextSplit( $splitVector, $startEdge, $startVertex, $face, $perturb );

			$endIndex = (int) $splitInfo [0];
			$endParam = (float) $splitInfo[1];

			// If we are trying to split an edge which is already in the 
			// split list then we cannot go any further.
			//
			if ( indexInIntegerList( $endIndex, $splitEdges ) >= 0 )
			{
				$endIndex = -1;
			}

			if ($endIndex >= 0)
			{
				$splitCmd += " -ep " + $endIndex + " " + $endParam;
				$actualCrackSize++;

				// Add this edge to the split edge list.
				//
				$splitEdges[ size($splitEdges) ] = $endIndex;
			}
		}

		// Complete the split command and execute it.
		//
		$splitCmd += " " + $object;

		// Evaluate the split command to make the crack.
		//
		eval( $splitCmd );

		if ( $verbose )
		{
			int $crackId = $k + 1;

			string $fmtId = (uiRes("m_crackShatter.kCrackId"));
			print( `format -s $crackId -s $splitCmd $fmtId` );

			string $fmtLen = (uiRes("m_crackShatter.kCrackLength"));
			print( `format -s $actualCrackSize $fmtLen` );

		}

		// Obtain and store the new edge list. $allNewEdges stores all the new edges for this crack.
		// IMPORTANT ASSUMPTION: We are assuming here that all new vertices added by the polySplit
		// command are appended to the end of the vertex list.  We have been assured that this will
		// always be the case. In 2.5, new edges were also appended to the end of the edge list.
		// This latter is *not* true in 3.0.
		// Index of the first new edge is equal to the number of vertices before polySplit.
		// We obtained and stored this right before calling polySplit.  We walk in order through
		// the new vertices, except that the first new edge starts at the crack origin.
		//
		$vertexCountAfterCrack[ $k ] = getVertexCount( $object );
	}

	// Form the crack edge lists.  We must do this OUTSIDE the loop which creates cracks,
	// because the polySplit operations which create each crack change the edge numbering.
	// We iterate over the cracks and form the edge list for each.
	// $crackFirstVertex is the first new vertex that was added for the current crack.
	//
	clear( $crackEdgeList );
	int $crackFirstVertex = $originalVertexCount;
	for ($k = 0; $k < size( $vertexCountAfterCrack ); $k++)
	{
		// Iterate over the vertices of the crack.  
		// $fromVertexIndex and $toVertex edges are the start and
		// and vertices for the current edge.  Each crack starts at $vertexIndex.
		// The end vertex for the first edge is the first new vertex that was added for that crack.
		//
		int $fromVertexIndex = $vertexIndex;
		int $toVertexIndex   = $crackFirstVertex;

		string $allNewEdges = "";
		
		for ( $j = $crackFirstVertex; $j < $vertexCountAfterCrack[ $k ]; $j++ )
		{
			// Obtain the edge between these two vertices.
			//
			string $fromVertex = $object + ".vtx[" + $fromVertexIndex + "]";
			string $toVertex = $object + ".vtx[" + $toVertexIndex + "]";
			string $newEdge[] = `polyListComponentConversion -fv -te -in $fromVertex $toVertex`;
			$allNewEdges += $newEdge[0];
			$allNewEdges += " ";
	
			// Next pair of vertices.
			//
			$fromVertexIndex = $toVertexIndex;
			$toVertexIndex++;
		}
		$crackEdgeList[ $k ] = $allNewEdges;

		// Set first vertex for the next crack.
		// The index first vertex for the next crack equals the number of vertices
		// which existed after the creation of the current one.
		//
		$crackFirstVertex = $vertexCountAfterCrack[ $k ];
	}

	// Make sure all the cracks have all their edges.  They may have
	// been split by another edge and a new edge inserted.
	//
	verifyCrackEdges( $crackEdgeList );

	return $crackEdgeList;
}


global proc string[] createFirstSplit( string $vertex, int $originalEdgeCount )
//
// This procedure create the first split off the origin.  This procedure returns a string
// array containing the following information:
//
//		splitInfo[0] = the split command (i.e. "polySplit -ep 45 0.15 -ep 47 0.65 ")
//		splitInfo[1] = the face which is being split.
//
{
	string $splitInfo[];
	string $splitCmd;
	int    $splitCount = 0;

	// Get the edges and faces associated with the vertex.
	//
	string $edgeList[] = getEdgeList( $vertex );
	int    $edgeCount  = size( $edgeList );
	string $faceList[] = getFaceList( $vertex );
	int    $faceCount  = size( $faceList );
	string $faceEdgeList[];

	float  $vertexPosition[] = `xform -ws -q -t $vertex`;
	vector $vertexVector = << $vertexPosition[0], $vertexPosition[1], $vertexPosition[2] >>;

	
		// Choose a face from the face list.  This detemines the
		// direction which we will begin the crack from.
		//
		string $face = getUniqueFace( $faceList );

		// Get the edges which make up the face.
		//
		$faceEdgeList = getEdgeList( $face );
		int    $faceEdgeCount  = size( $faceEdgeList );
	
		// Pick the start edge for the crack.  The start edge must be
		// an edge which is both in the face list and associated with
		// the start vertex.  For example, one of the edges below:
		//
		//           \ | /
		//            \|/
		//          ---*---
		//            /|\
		//           / | \
		//
		string $startEdge = getMatchingItem(  $faceEdgeList, $edgeList );
	
		// Pick the end edge for the crack.  The end edge must be an edge
		// which is in the face but NOT associated with the origin vertex.
		//
		string $endEdge = getUnexcludedItem( $faceEdgeList, $edgeList );

		// Make sure we got valid edges.
		//
		if( (size($endEdge) == 0) || (size($startEdge) == 0) )
		{
			// Didn't get valid edges, bail.
			//
			return $splitInfo;
		}

		// Get the start and end edge index.
		//
		int $startIndex = getIndex( $startEdge );
		int $endIndex   = getIndex( $endEdge );

		// Determine a random point on the end edge from which we will
		// create the first split.
		//
		float $endParam = rand( 0.1, 0.9 );

		// Determine the vector from the start of the crack (vertexVector) to the
		// end of the crack.
		//
		float $startParam = getEdgeParameterization( $startEdge, $vertexVector );

		// Create the polySplit command for the first split.
		//
		$splitCmd = "polySplit -ch 1 ";
		$splitCmd += "-ep " + $startIndex + " " + $startParam + " ";
		$splitCmd += "-ep " + $endIndex   + " " + $endParam;
	

	clear( $edgeList );
	clear( $faceList );
	clear( $faceEdgeList );

	$splitInfo[0] = $splitCmd;
	$splitInfo[1] = $face;

	return $splitInfo;
}


global proc vector getFaceNormal( string $face )
{
	float  $x = 0, 
		   $y = 0, 
		   $z = 0;
	string $vertexList[] = getVertexList( $face );
	int    $vertexCount  = size( $vertexList );
	int    $index;
	float  $pi = 3.141592653589793;

	// Determine the normal from the normal per vertex command.
	// This do not always give use the corrent normal but it will
	// give us the general direction of the face normal.  We will 
	// use this later to determine of we have the correct normal.
	//
	for( $i = 0; $i < $vertexCount; $i++ )
	{
		float $vertexNormals[] = `polyNormalPerVertex -q -xyz $vertexList[$i]`;
		$x += $vertexNormals[0];
		$y += $vertexNormals[1];
		$z += $vertexNormals[2];
	}

	// Determine the normal per vertex.
	//
	vector $normalPerVertex = <<$x, $y, $z>>/$vertexCount;

	// Now get another face normal.  This face normal is the "correct" normal
	// but may be flip by 180 degrees.  We check this normal againts the 
	// normal per vertex to determine its direction.  If we need to, we flip the
	// normal by 180 degrees.
	//
	vector $normal = getFaceNormal0( $face );

	// Check the angle between the two normals.  If it is greater then
	// 90 degrees then we flip the normal.
	//
	float $radianAngle = angle( $normal, $normalPerVertex );

	if ( $radianAngle > $pi/2 )
	{
		// Determine an axis for the normal to rotate about.
		//
		string $vertexList[] = getVertexList( $face );
		float  $v0[] = `xform -ws -q -t $vertexList[0]`;
		float  $v1[] = `xform -ws -q -t $vertexList[1]`;
		vector $axis = << $v0[0] - $v1[0], $v0[1] - $v1[1], $v0[2] - $v1[2]>>;

		$normal = rot( $normal, $axis, $pi ); 
	}

	return $normal;
}


global proc vector getFaceNormal0( string $face )
{
	vector $normal = <<0, 0, 0>>;

	// Get the faces edge list and edge count.
	//
	string $edgeList[] = getEdgeList( $face );
	int    $edgeCount  = size( $edgeList );

	// Choose the first edge.
	//
	string $edge1 = $edgeList[0];
	string $edge2;

	// Get the first edges vertex list.
	//
	string $edge1VertexList[] = getVertexList( $edge1 );
	string $edge2VertexList[];

	int    $found = false;

	// Find an edge with a common vertex.  Looking backwards
	// tends to find the edge more quickly.
	//
	for ( $i = $edgeCount - 1; $i >= 0; $i-- )
	{
		if ( ! $found )
		{
			$edge2 = $edgeList[$i];
			$edge2VertexList = getVertexList( $edge2 );

			for ( $j = 0; $j < 2; $j++ )
			{
				// Check for a common vertex.
				//
				if ( ($edge1VertexList[0] == $edge2VertexList[$j]) ||
				     ($edge1VertexList[1] == $edge2VertexList[$j]) )
				{
					$found = true;
					break;
				}
			}
		}
	}

	// If a common vertex was found the determine the normal of
	// the facet.
	//
	if ( $found )
	{
		// Determine the axis we want to rotate the split vector about.  This
		// is the start edge.
		//
		float  $v0[] = `xform -ws -q -t $edge1VertexList[0]`;
		float  $v1[] = `xform -ws -q -t $edge1VertexList[1]`;
		vector $edgeVector1 = << $v1[0] - $v0[0], $v1[1] - $v0[1], $v1[2] - $v0[2]>>;

		$v0 = `xform -ws -q -t $edge2VertexList[0]`;
		$v1 = `xform -ws -q -t $edge2VertexList[1]`;
		vector $edgeVector2 = << $v1[0] - $v0[0], $v1[1] - $v0[1], $v1[2] - $v0[2]>>;

		$normal = cross( $edgeVector1, $edgeVector2 );
	}

	return $normal;
}



global proc float getLineIntersection(vector $split0, vector $split1, vector $edge0, vector $edge1)
{
	float $param = -1.0;

	vector $line1   = $split1 - $split0;
	vector $line2   = $edge1  - $edge0;
	vector $vector0 = $split0 - $edge0;
	vector $vector1 = $edge0  - $split0;


	if ( equiv( $line1.x, 0.0, 0.000001 ) != 1 )
	{
		float $value = ($line2.y - ($line1.y*$line2.x)/$line1.x);

		if ( equiv( $value, 0.0, 0.000001 ) != 1 )
		{
			$param = ($vector0.y + ($line1.y/$line1.x)*$vector1.x)/$value;

			return $param;
		}
	}

	if ( equiv( $line1.y, 0.0, 0.000001 ) != 1 )
	{
		float $value = ($line2.z - ($line1.z*$line2.y)/$line1.y);

		if ( equiv( $value, 0.0, 0.000001 ) != 1 )
		{
			$param = ($vector0.z + ($line1.z/$line1.y)*$vector1.y)/$value;

			return $param;
		}
	}

	if ( equiv( $line1.z, 0.0, 0.000001 ) != 1 )
	{
		float $value = ($line2.x - ($line1.x*$line2.z)/$line1.z);

		if ( equiv( $value, 0.0, 0.000001 ) != 1 )
		{
			$param = ($vector0.x + ($line1.x/$line1.z)*$vector1.z)/$value;

			return $param;
		}
	}

	return $param;
}


global proc int findClosestVertex( string $object, vector $position )
//
// This procedure finds the closest vertex on the surface to the 
// given point and returns its index.
//
{
	int    $vertexCount[] = `polyEvaluate -vertex $object`;
	float  $vp[];
	float  $distance;
	float  $maxDistance = 1000000.0;
	string $vertex;
	int    $vertexIndex = -1;

	for ( $i = 1; $i < $vertexCount[0]; $i++ )
	{
		$vertex = $object + ".vtx[" + $i + "]";
		$vp     = `xform -q -t $vertex`;

		vector $v = <<$vp[0], $vp[1], $vp[2]>>;
		$distance = mag( $position - <<$vp[0], $vp[1], $vp[2]>> );

		if ( $distance < $maxDistance )
		{
			$vertexIndex = $i;
			$maxDistance = $distance;

			if ( $distance == 0.0 )
			{
				break;
			}
		}
	}

	return $vertexIndex;
}


global proc string getUniqueFace( string $faceList[] )
{
	global string $gUsedFaceList[];
	global int    $gUsedFaceCount;
	int    $faceCount = size( $faceList );
	int    $faceIndex = rand( 0, $faceCount );
	string $face      = $faceList[ $faceIndex ];

	int   $found = false;

	if ( $gUsedFaceCount >= $faceCount )
	{
		clear( $gUsedFaceList );
		$gUsedFaceCount = 0;
	}

	for ($i = 0; $i < $gUsedFaceCount; $i++ )
	{
		if ( $face == $gUsedFaceList[$i] )
		{
			$found = true;
		}
	}

	if ( $found == true )
	{
		for ( $i = 0; $i < $faceCount; $i++ )
		{
			$found = false;

			for ( $j = 0; $j < $gUsedFaceCount; $j++ )
			{
				if ( $faceList[$i] == $gUsedFaceList[$j] )
				{
					$found = true;
				}
			}

			if ( $found == false )
			{
				$face = $faceList[$i];
				break;
			}
		}
	}

	$gUsedFaceList[ $gUsedFaceCount ] = $face;
	$gUsedFaceCount++;

	return $face;
}


proc string[] _crackShatter( string $name, int $crackCount, int $crackLength, 
							 int $triangulate, float $perturb, float $extrude, int $original,
							 string $postOp, int $makeRigid, int $verbose)
//
// This procedure looks through the selection list and calls
// surfaceShatterObject() on only the nurbsSurface or
// polygonal mesh shapes.  It then calls addEffectAttributeToNewNodes()
// to "mark" each newly created node with an attribute meaning that
// that node was created during the execution of this script.
//
{
    // The return value.
    //
    string $result[];
    clear( $result );

    // Before proceeding further, make sure that the selection list
    // consists of either a vertex or a cv. Only one object at a time
	// can be shattered and the vertex/cv where the crack is supposed
	// to originate is supposed to be selected.
    //
	if (!selectionValidForCrackShatter())
	{
        error( (uiRes("m_crackShatter.kInvalidSelection")) );
		return $result;
	}

    // This array is used to avoid shattering the same object twice
    // during the running of this script.  This might happen if both
    // the transform and the shape of an object are selected.
    //
    string $objectsDone[];
    clear( $objectsDone );

    // Store a list of all of the nodes in the scene before any
    // work is done.
    //
    string $allNodesBefore[] = `ls`;
    string $selectedShapes[] = getSelectedList( "allGeometry" );

    for( $i = 0; $i < size( $selectedShapes ); $i ++ )
    {
        // If this shape has already been shattered, then skip over
        // it.
        //
        if( findInStringArray( $selectedShapes[$i], $objectsDone ) == -1 )
        {
            // If this shape is not nurbsSurface or polygonal mesh shape,
            // then display a warning and continue.
            //
            string $type = `nodeType $selectedShapes[$i]`;
            if( ( $type == "nurbsSurface" ) || ( $type == "mesh" ) )
            {
                // If for some reason the surfaceShatterObject() procedure
                // returns a blank string, then display a warning and
                // continue.  This could have returned an error, but I
                // decided that I do not want to exit the script for this
                // reason.
                //
                string $newObject = crackShatterObject( $selectedShapes[$i], $name, $crackCount,
														$crackLength, $triangulate, $perturb, 
														$extrude, $original, $postOp, $makeRigid, 
														$verbose );

                if ( size( $newObject ) > 0 )
                {
                    $result = appendSingleToStringArray( $result, $newObject );
                }
                else
                {
                    string $fmt = (uiRes("m_crackShatter.kCouldNotShatter"));
                    warning( `format -s $selectedShapes[$i] $fmt` );
                }
            }
            else
            {
                string $fmt = (uiRes("m_crackShatter.kCannotBeShattered"));
                warning( `format -s $selectedShapes[$i] $fmt` );
            }

            // Note that this shape has been shattered so that we do not do it again
            // during this execution of the script.
            //
            $objectsDone = appendSingleToStringArray( $objectsDone, $selectedShapes[$i] );
        }
    }

    if ( $original == 4 )
    {
        string $parent[] = `listRelatives -parent $selectedShapes`;
        select $parent;
    }
    else
    {
        select $result;
    }

    return $result;
}

global proc string[] crackShatter( string $name, int $crackCount, int $crackLength, 
								   int $triangulate, float $perturb, float $extrude,
								   int $seedValue, int $original, string $postOp, 
								   int $makeRigid, int $verbose)
//
// This is the global procedure that the user actually calls.  It manages the
// wiat cursor and traps any errors or failures that might happen during the
// execution of this script.
//
{
	global string $gLastSelectionList[];

    string $result[];
    clear( $result );

	if ( $seedValue > 0 )
	{
		seed( $seedValue );
	}

    // Store the currently slected objects so that we can
    // restore them if we detect some error.
    //
    $gLastSelectionList = `ls -sl`;

	float $time = `timerX`;

    waitCursor -state on;

    if (catch( $result = _crackShatter( $name, $crackCount, $crackLength, $triangulate, 
										$perturb, $extrude, $original, $postOp, $makeRigid,
										$verbose)) )
    {
		// If an error is detected, call our error-handling
        // procedure, restore the selection list, and clear
        // whatever might be in the result array.  We do not
        // exit the script here, because we want the waitCursor
        // command to turn off the wait cursor.
        //
        shatterErrorHandler( "Crack Shatter" );
        select $gLastSelectionList;
        clear( $result );
    }

    waitCursor -state off;

	if ( $verbose )
	{
		$time = `timerX -st $time`;
		string $fmt = (uiRes("m_crackShatter.kElapsedTime"));
		print( `format -s $time $fmt` );
	}

    return $result;
}


global proc string[] expandUniqueList( string $faceList[], int $shardIndex, int $shardIndexList[] )
{

	string $buffer[];
	string $newFaceList[];

	clear( $newFaceList );

	int $faceCount = size( $faceList );
	int $index     = 0;

	for ( $i = 0; $i < $faceCount; $i++ )
	{
		string $face = $faceList[ $i ];

//		tokenize( $face, "/[/]", $buffer );
		tokenize( $face, "[]", $buffer );
		string $baseName = $buffer[0];
//		tokenize( $buffer[1], "/:", $buffer );
		tokenize( $buffer[1], ":", $buffer );

		int $bufferSize = size( $buffer );

		int $start = (int) $buffer[0];
		int $end   = $start;

		if ( $bufferSize == 2 )
		{
			$end = (int) $buffer[1];
		}

		for ( $j = $start; $j <= $end; $j++ )
		{
			if ( $shardIndexList[ $j ] == 0 )
			{
				$newFaceList[ $index ] = $baseName + "[" + $j + "]";
				$shardIndexList[$j] = $shardIndex;
				$index++;
			}
		}
	}

	return $newFaceList;

}