global proc float getParticleZ(string $particleShapeName, int $id){
	
	float $z[] = `eval("getParticleAttr -at z "+$particleShapeName+".pt["+$id+"]")`;
	return $z[0];

}

global proc int compareZ(int $left, int $right, string $particleShapeName){
	
	float $leftZ = getParticleZ($particleShapeName, $left);
	float $rightZ = getParticleZ($particleShapeName, $right);

	int $isRightBig = 0;
	if($leftZ < $rightZ){
		$isRightBig = 1;
	}

	return $isRightBig;
}

global proc float getDistance(float $p1[], float $p2[]){

	float $tmpX = pow($p1[0] - $p2[0],2);
	float $tmpY = pow($p1[1] - $p2[1],2);
	float $tmpZ = pow($p1[2] - $p2[2],2);

	return sqrt($tmpX +$tmpY +$tmpZ);
}

global proc float[] getCameraSpacePosition(float $currentPosition[],float $cameraInverseMatrix[]){
	
	//float $cameraInverseMatrix[] = invertMat($cameraMatrix);
	float $currentMatrix[] = {
		1,	0,	0,	0,
		0,	1,	0,	0,
		0,	0,	1,	0,
		0,	0,	0,	1
	};
	$currentMatrix[12] = $currentPosition[0];
	$currentMatrix[13] = $currentPosition[1];
	$currentMatrix[14] = $currentPosition[2];
	
	float $cameraSpaceMatrix[] = multMatrix($currentMatrix,$cameraInverseMatrix);
	
	return {$cameraSpaceMatrix[12],$cameraSpaceMatrix[13],$cameraSpaceMatrix[14]};
}

global proc int[]  mergeArray_3(int $array1[], int $pivot, int $array2[]){

	int $array3[];
	
	//put fisrt array
	for ($item1 in $array1)
	{
	$array3[size($array3)] = $item1;
	}

	//put pivot
	$array3[size($array3)] = $pivot;

	//put second array
	for ($item2 in $array2)
	{
	$array3[size($array3)] = $item2;
	}

	return $array3;
}

global proc float[] invertMat(float $m[]) {
	
	float $outMatrix[16];

	$outMatrix[0] = $m[6]*$m[11]*$m[13] - $m[7]*$m[10]*$m[13] + $m[7]*$m[9]*$m[14] - $m[5]*$m[11]*$m[14] - $m[6]*$m[9]*$m[15] + $m[5]*$m[10]*$m[15];
	$outMatrix[1] = $m[3]*$m[10]*$m[13] - $m[2]*$m[11]*$m[13] - $m[3]*$m[9]*$m[14] + $m[1]*$m[11]*$m[14] + $m[2]*$m[9]*$m[15] - $m[1]*$m[10]*$m[15];
	$outMatrix[2] = $m[2]*$m[7]*$m[13] - $m[3]*$m[6]*$m[13] + $m[3]*$m[5]*$m[14] - $m[1]*$m[7]*$m[14] - $m[2]*$m[5]*$m[15] + $m[1]*$m[6]*$m[15];
	$outMatrix[3] = $m[3]*$m[6]*$m[9] - $m[2]*$m[7]*$m[9] - $m[3]*$m[5]*$m[10] + $m[1]*$m[7]*$m[10] + $m[2]*$m[5]*$m[11] - $m[1]*$m[6]*$m[11];
	$outMatrix[4] = $m[7]*$m[10]*$m[12] - $m[6]*$m[11]*$m[12] - $m[7]*$m[8]*$m[14] + $m[4]*$m[11]*$m[14] + $m[6]*$m[8]*$m[15] - $m[4]*$m[10]*$m[15];
	$outMatrix[5] = $m[2]*$m[11]*$m[12] - $m[3]*$m[10]*$m[12] + $m[3]*$m[8]*$m[14] - $m[0]*$m[11]*$m[14] - $m[2]*$m[8]*$m[15] + $m[0]*$m[10]*$m[15];
	$outMatrix[6] = $m[3]*$m[6]*$m[12] - $m[2]*$m[7]*$m[12] - $m[3]*$m[4]*$m[14] + $m[0]*$m[7]*$m[14] + $m[2]*$m[4]*$m[15] - $m[0]*$m[6]*$m[15];
	$outMatrix[7] = $m[2]*$m[7]*$m[8] - $m[3]*$m[6]*$m[8] + $m[3]*$m[4]*$m[10] - $m[0]*$m[7]*$m[10] - $m[2]*$m[4]*$m[11] + $m[0]*$m[6]*$m[11];
	$outMatrix[8] = $m[5]*$m[11]*$m[12] - $m[7]*$m[9]*$m[12] + $m[7]*$m[8]*$m[13] - $m[4]*$m[11]*$m[13] - $m[5]*$m[8]*$m[15] + $m[4]*$m[9]*$m[15];
	$outMatrix[9] = $m[3]*$m[9]*$m[12] - $m[1]*$m[11]*$m[12] - $m[3]*$m[8]*$m[13] + $m[0]*$m[11]*$m[13] + $m[1]*$m[8]*$m[15] - $m[0]*$m[9]*$m[15];
	$outMatrix[10] = $m[1]*$m[7]*$m[12] - $m[3]*$m[5]*$m[12] + $m[3]*$m[4]*$m[13] - $m[0]*$m[7]*$m[13] - $m[1]*$m[4]*$m[15] + $m[0]*$m[5]*$m[15];
	$outMatrix[11] = $m[3]*$m[5]*$m[8] - $m[1]*$m[7]*$m[8] - $m[3]*$m[4]*$m[9] + $m[0]*$m[7]*$m[9] + $m[1]*$m[4]*$m[11] - $m[0]*$m[5]*$m[11];
	$outMatrix[12] = $m[6]*$m[9]*$m[12] - $m[5]*$m[10]*$m[12] - $m[6]*$m[8]*$m[13] + $m[4]*$m[10]*$m[13] + $m[5]*$m[8]*$m[14] - $m[4]*$m[9]*$m[14];
	$outMatrix[13] = $m[1]*$m[10]*$m[12] - $m[2]*$m[9]*$m[12] + $m[2]*$m[8]*$m[13] - $m[0]*$m[10]*$m[13] - $m[1]*$m[8]*$m[14] + $m[0]*$m[9]*$m[14];
	$outMatrix[14] = $m[2]*$m[5]*$m[12] - $m[1]*$m[6]*$m[12] - $m[2]*$m[4]*$m[13] + $m[0]*$m[6]*$m[13] + $m[1]*$m[4]*$m[14] - $m[0]*$m[5]*$m[14];
	$outMatrix[15] = $m[1]*$m[6]*$m[8] - $m[2]*$m[5]*$m[8] + $m[2]*$m[4]*$m[9] - $m[0]*$m[6]*$m[9] - $m[1]*$m[4]*$m[10] + $m[0]*$m[5]*$m[10];
	
	return $outMatrix;
}

global proc float[] multMatrix(float $mat1[], float $mat2[]){
	
	float $outMat[16];

	$outMat[0] = $mat1[0]*$mat2[0] + $mat1[1]*$mat2[4] + $mat1[2]*$mat2[8] + $mat1[3]*$mat2[12];
	$outMat[1] = $mat1[0]*$mat2[1] + $mat1[1]*$mat2[5] + $mat1[2]*$mat2[9] + $mat1[3]*$mat2[13];
	$outMat[2] = $mat1[0]*$mat2[2] + $mat1[1]*$mat2[6] + $mat1[2]*$mat2[10] + $mat1[3]*$mat2[14];
	$outMat[3] = $mat1[0]*$mat2[3] + $mat1[1]*$mat2[7] + $mat1[2]*$mat2[11] + $mat1[3]*$mat2[15];

	$outMat[4] = $mat1[4]*$mat2[0] + $mat1[5]*$mat2[4] + $mat1[6]*$mat2[8] + $mat1[7]*$mat2[12];
	$outMat[5] = $mat1[4]*$mat2[1] + $mat1[5]*$mat2[5] + $mat1[6]*$mat2[9] + $mat1[7]*$mat2[13];
	$outMat[6] = $mat1[4]*$mat2[2] + $mat1[5]*$mat2[6] + $mat1[6]*$mat2[10] + $mat1[7]*$mat2[14];
	$outMat[7] = $mat1[4]*$mat2[3] + $mat1[5]*$mat2[7] + $mat1[6]*$mat2[11] + $mat1[7]*$mat2[15];

	$outMat[8] = $mat1[8]*$mat2[0] + $mat1[9]*$mat2[4] + $mat1[10]*$mat2[8] + $mat1[11]*$mat2[12];
	$outMat[9] = $mat1[8]*$mat2[1] + $mat1[9]*$mat2[5] + $mat1[10]*$mat2[9] + $mat1[11]*$mat2[13];
	$outMat[10] = $mat1[8]*$mat2[2] + $mat1[9]*$mat2[6] + $mat1[10]*$mat2[10] + $mat1[11]*$mat2[14];
	$outMat[11] = $mat1[8]*$mat2[3] + $mat1[9]*$mat2[7] + $mat1[10]*$mat2[11] + $mat1[11]*$mat2[15];

	$outMat[12] = $mat1[12]*$mat2[0] + $mat1[13]*$mat2[4] + $mat1[14]*$mat2[8] + $mat1[15]*$mat2[12];
	$outMat[13] = $mat1[12]*$mat2[1] + $mat1[13]*$mat2[5] + $mat1[14]*$mat2[9] + $mat1[15]*$mat2[13];
	$outMat[14] = $mat1[12]*$mat2[2] + $mat1[13]*$mat2[6] + $mat1[14]*$mat2[10] + $mat1[15]*$mat2[14];
	$outMat[15] = $mat1[12]*$mat2[3] + $mat1[13]*$mat2[7] + $mat1[14]*$mat2[11] + $mat1[15]*$mat2[15];

	return $outMat;
}


global proc int isInView(

	float $positionInCameraSpace[],
	float $camApertureWidth, float $camApertureHeight,
	float $nearClipPlane, float $farClipPlane, float $filmAspectRatio,
	float $angleOfView
	){

	int $isIn = 1;

	// cull behind camera
	if($positionInCameraSpace[2]>0){
		$isIn = 0;
	}

	//get distance from camera plane
	float $distFromCamPlane = -$positionInCameraSpace[2];

	//cull through X
	float $xDist = $distFromCamPlane * tan(deg_to_rad($angleOfView)/2);
	if($positionInCameraSpace[0] > $xDist || $positionInCameraSpace[0] < -$xDist){
		$isIn = 0;
	}

	//cull through Y
	float $xDist = $distFromCamPlane * tan(deg_to_rad($angleOfView)/2)*(1/$filmAspectRatio);
	if($positionInCameraSpace[1] > $xDist || $positionInCameraSpace[1] < -$xDist){
		$isIn = 0;
	}

	//cull through clipping plane
	if($distFromCamPlane < $nearClipPlane || $distFromCamPlane > $farClipPlane){
		$isIn = 0;
	}


	return $isIn;
	//return 1;
}

global proc string getCamera(){
	return "persp1";
}

global proc string getParticleShape(){
	return "particleShape1";
}

global proc int getNumOfElementsInEachSlice(){
	return 200;
}

global proc arrayElementSwap(int $data[], int $index1, int $index2){
	int $temp = $data[$index1];
	$data[$index1] = $data[$index2];
	$data[$index2] = $temp;
}

//quick sort
global proc quickSortByZ(int $id[], int $start, int $end){

	int $i = $start;
	int $k = $end;

	if($end - $start >= 1){
	
		int $pivotId = $id[$start];
		float $pivot_z = getParticleZ(getParticleShape(),$pivotId);

		while($k > $i){
			
			float $i_z = getParticleZ(getParticleShape(),$id[$i]);
			float $k_z = getParticleZ(getParticleShape(),$id[$k]);

			while($i_z <= $pivot_z && $i <= $end && $k > $i ){
				$i+=1;
				$i_z = getParticleZ(getParticleShape(),$id[$i]);
			}
			while($k_z > $pivot_z && $k >= $start && $k >= $i ){
				$k-=1;
				$k_z = getParticleZ(getParticleShape(),$id[$k]);
			}
			if($k > $i){
				arrayElementSwap($id,$i,$k);
			}
		}
		arrayElementSwap($id,$start,$k);

		quickSortByZ($id,$start,$k-1);
		quickSortByZ($id,$k+1,$end);
	}
}

global proc setParticleZOrder(int $renderParticleID[]){
	
	quickSortByZ($renderParticleID,0,size($renderParticleID)-1);

	for($n = 0 ; $n < size($renderParticleID) ; $n ++){

		eval("select -r "+getParticleShape()+".pt["+$renderParticleID[$n]+"]\;");
		setParticleAttr -fv $n -at zOrder;
	}
}

global proc int getNumOfSlice(int $total,int $numOfElementsInEachSlice){
	
	int $numOfSlice = 0;
	if($numOfElementsInEachSlice != 0){
		int $tmp = $numOfElementsInEachSlice;
		while($tmp < $total){
			$numOfSlice += 1;
			$tmp = $numOfElementsInEachSlice * $numOfSlice;
		}
	}
	return $numOfSlice;
}

global proc previewGroupColor(int $renderParticleID[],int $numOfElementsInEachSlice){

	//get the number of group
	int $total = size($renderParticleID);
	int $numOfSlice = getNumOfSlice($total,$numOfElementsInEachSlice);
	
	//set group color
	float $r[];float $g[];float $b[];
	for($n = 0 ; $n < $numOfSlice ; $n++){
		seed((float)$n+3);
		$r[$n] = rand(1);
		$g[$n] = rand(1);
		$b[$n] = rand(1);

		//print ("r"+$n+" : "+$r[$n]+"\n");
	}
	//print ("numOfSlice : "+$numOfSlice+"\n");

	int $test = 0;
	//set rgbPP attribute
	for($n = 0 ; $n < $numOfSlice ; $n ++){
		for($m = $n*($numOfElementsInEachSlice) ; $m < ($n * ($numOfElementsInEachSlice) + $numOfElementsInEachSlice) ; $m++){
			//print ("m : "+$m+"\n");
			if($m < size($renderParticleID)){
				eval("select -r "+getParticleShape()+".pt["+$renderParticleID[$m]+"]\;");
				setParticleAttr -vv $r[$n] $g[$n] $b[$n] -at rgbPP;
				setParticleAttr -vv 1 1 1 -at opacityPP;
				//setParticleAttr -vv 1 1 1 -at rgbPP;
				$test ++;
			}
		}
	}
	//print ("c : "+$test+"\n");
}

global proc _toolChange(){
	SelectMaskToolMarkingMenu;
	buildSelectMaskMM;
	changeToolIcon;
	SelectMaskToolMarkingMenuPopDown;
	MarkingMenuPopDown;
	if (`popupMenu -exists tempMM`) { deleteUI tempMM; }if (`popupMenu -exists tempMM2`) { deleteUI tempMM2; };
}

global proc ho_slicePoints(){

	//selection tool - not to get warnning in script editer
	_toolChange();

	string $cameraName = getCamera();
	string $particleShapeName = getParticleShape();

	//get camera info
	float $cameraPosition[] = `xform -q -ws -t $cameraName`;

	string $tmp[] = `listRelatives -s $cameraName`;
	string $cameraShape = $tmp[0];
	float $camApertureWidth = `camera -q -horizontalFilmAperture $cameraShape`;
	float $camApertureHeight = `camera -q -verticalFilmAperture $cameraShape`;
	float $nearClipPlane = `camera -q -nearClipPlane $cameraShape`;
	float $farClipPlane = `camera -q -farClipPlane $cameraShape`;
	float $angleOfView = `camera -q -horizontalFieldOfView $cameraShape`;
	float $filmAspectRatio = `camera -q -aspectRatio $cameraShape`;

	//get camera matrix
	float $cameraMatrix[] = `xform -q -ws -m $cameraName`;
	float $cameraInverseMatrix[] = invertMat($cameraMatrix);

	//num of particles
	int $numOfParticle = `eval ("getAttr "+$particleShapeName+".count")`;

	//rendering particle id array
	int $renderParticleID[] = {};

	for($n = 0 ; $n < $numOfParticle ; $n++){

		//get each particle position - world space
		float $pPos[3] = `eval("getParticleAttr -at position -array true "+$particleShapeName+".pt["+$n+"]")`;

		//get each particle position - camera space
		float $positionInCamSpace[] = getCameraSpacePosition($pPos,$cameraInverseMatrix);
		
		//check if the particle is inside view - culling
		if(isInView($positionInCamSpace, $camApertureWidth, $camApertureHeight, $nearClipPlane,
			$farClipPlane, $filmAspectRatio,$angleOfView)){

			//get z depth - camera space -tz
			//float $z = -$positionInCamSpace[2];
			float $z = getDistance($pPos,{$cameraMatrix[12],$cameraMatrix[13],$cameraMatrix[14]});
			
			//set particle Attr z 
			eval("select -r "+$particleShapeName+".pt["+$n+"]\;");
			setParticleAttr -fv $z -at z;

			//append rendering particle array
			$renderParticleID[size($renderParticleID)] = $n;

			//print ($z+"\n");
			//
			
		}
		
	}
	setParticleZOrder($renderParticleID);
	//error($renderParticleID[0]);

	//color privew - black
	setParticleAttr -vv 0 0 0 -at rgbPP -o $particleShapeName;
	setParticleAttr -vv 0.02 0.02 0.02 -at opacityPP -o $particleShapeName;
	previewGroupColor($renderParticleID,getNumOfElementsInEachSlice());


	select -cl;
	print ("\n"+size($renderParticleID)+"\ndone\n");
}