// Aqsis
// Copyright (c) 1997 - 2001, Paul C. Gregory
//
// Contact: pgregory@aqsis.com
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

/**
 * Copyright (C) 2006-2007  NTT DATA CORPORATION
 * 
 * Version: 1.0.0 2007/04/01
 *  
 */
package net.cellcomputing.himawari.library;

import static java.lang.Math.sqrt;
import static java.lang.Math.round;
import static java.lang.Math.max;
import static java.lang.Math.min;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

import static net.cellcomputing.himawari.library.RiGlobal.QGetRenderContext;
import static net.cellcomputing.himawari.library.RiGlobal.QGetRenderContextI;
import static net.cellcomputing.himawari.library.RiGlobal.USES;
import static net.cellcomputing.himawari.library.RiGlobal.isDONE;
import static net.cellcomputing.himawari.library.Float_h.FLT_EPSILON;
import static net.cellcomputing.himawari.library.EqVariableType.*;
import static net.cellcomputing.himawari.library.EqVariableClass.*;
import static net.cellcomputing.himawari.library.EqSplitDir.*;
import static net.cellcomputing.himawari.library.EqEnvVars.*;

import net.cellcomputing.himawari.accessory.STLVector;
import net.cellcomputing.himawari.accessory.Vector;
import net.cellcomputing.himawari.accessory.primitive.p_String;
import net.cellcomputing.himawari.accessory.primitive.p_float;
import net.cellcomputing.himawari.accessory.primitive.p_int;
import net.cellcomputing.himawari.library.types.CqColor;
import net.cellcomputing.himawari.library.types.CqMatrix;
import net.cellcomputing.himawari.library.types.CqVector2D;
import net.cellcomputing.himawari.library.types.CqVector3D;
import net.cellcomputing.himawari.library.types.CqVector4D;

/**
 * 
 * 
 * 
 * @author NTT DATA Corporation
 */
public strictfp class CqSurfaceSubdivisionPatch extends CqBasicSurface {

    private CqSubdivision2	m_pTopology;
    private CqLath			m_pFace;
    private int			m_Uses;
    private float			m_Time;
    private int			m_FaceIndex;
	
    
    public CqSurfaceSubdivisionPatch( final CqSubdivision2 pTopology, CqLath pFace, int faceIndex)
    {
        m_pTopology	= pTopology;
        m_pFace		= pFace;
	    m_Uses		= Uses();
		m_Time		= QGetRenderContextI().Time();
		m_FaceIndex	= faceIndex;
    }
    
    
    /** 
     * Get the pointer to the subdivision surface hull that this patch is part of.
     */
    public CqSubdivision2 pTopology()
    {
        return( m_pTopology );
    }

    /** 
     * Get the index of the face on the hull that this patch refers to.
     */
    public CqLath pFace()
    {
        return( m_pFace );
    }

    @Override
    public	IqAttributes pAttributes()
    {
        return ( pTopology().pPoints().pAttributes() );
    }
    
    @Override
    public	IqTransform pTransform()
    {
        return ( pTopology().pPoints().pTransform() );
    }
    
    // Required implementations from IqSurface
    public void Transform( final CqMatrix matTx, final CqMatrix matITTx, final CqMatrix matRTx, int iTime )
    {
        //pTopology().pPoints( iTime ).Transform( matTx, matITTx, matRTx );
    }
    // NOTE: These should never be called.
    public	int	cUniform()
    {
        return ( 0 );
    }
    public	int	cVarying()
    {
        return ( 0 );
    }
    public	int	cVertex()
    {
        return ( 0 );
    }
    public	int	cFaceVarying()
    {
        return ( 0 );
    }

    // Implementations required by CqBasicSurface
    public	CqBound	Bound()
    {
        assert( pTopology()!=null );
        assert( pTopology().pPoints()!=null );
        assert( pFace()!=null );

        CqBound B = new CqBound();

    	// First make sure that the appropriate neighbour facets have been subdivided if this is >0 level face.
        if( pFace().pParentFacet()!=null )
        {
            Vector<CqLath> aQff = new Vector<CqLath>();
            Vector<CqLath> apSubFaces2 = new Vector<CqLath>();
            pFace().pParentFacet().Qff( aQff );
//            Vector<CqLath*>::iterator iF;
            for( CqLath iF : aQff )
    		{
    			CqLath face = iF;
    			if (null == face.pFaceVertex())
    				pTopology().SubdivideFace(face, apSubFaces2);
    		}
        }


        // Get the laths of the surrounding faces.
        Vector<CqLath> aQff = new Vector<CqLath>();
        pFace().Qff(aQff);
//        Vector<CqLath*>::iterator iFF;
        for( CqLath iFF : aQff )
        {
            // Get the laths that reference the vertices of this face
        	Vector<CqLath> aQfv = new Vector<CqLath>();
            (iFF).Qfv(aQfv);

            // Now get the vertices, and form the bound.
//            Vector<CqLath*>::iterator iQfv;
            for( CqLath iQfv : aQfv )
            {
                int iTime;
                for( iTime = 0; iTime < pTopology().iTimes(); iTime++ )
                    B.Encapsulate( new CqVector3D( (CqVector4D)pTopology().pPoints( iTime ).P().pValue_get((iQfv).VertexIndex(),0) ) );
            }
        }

        return( AdjustBoundForTransformationMotion( B ) );
    }
    
    public	CqMicroPolyGridBase Dice()
    {
    	CqSubdivision2 pSurface;
    	STLVector<CqMicroPolyGridBase> apGrids = new STLVector<CqMicroPolyGridBase>(CqMicroPolyGridBase.class);

        int iTime;
        for( iTime = 0; iTime < pTopology().iTimes(); iTime++ )
        {
    		pSurface = Extract(iTime);
    		CqSurfaceSubdivisionPatch pPatch = new CqSurfaceSubdivisionPatch(pSurface, pSurface.pFacet(0), 0);
    		pPatch.m_uDiceSize = m_uDiceSize;
    		pPatch.m_vDiceSize = m_vDiceSize;
    		CqMicroPolyGridBase pGrid = pPatch.DiceExtract();
    		apGrids.add( pGrid );
    	}

        if( apGrids.size() == 1 )
            return( apGrids.get( 0 ) );
        else
        {
            CqMotionMicroPolyGrid pGrid = new CqMotionMicroPolyGrid();
            int i;
            for ( i = 0; i < pTopology().iTimes(); i++ )
                pGrid.AddTimeSlot( pTopology().Time( i ), apGrids.get( i ) );
            return( pGrid );
        }
    }
    
    public	int Split( STLVector<CqBasicSurface> aSplits )
    {
    	assert( pTopology()!=null );
    	assert( pTopology().pPoints()!=null );
    	assert( pFace()!=null );

    	boolean canuse = pTopology().CanUsePatch( pFace() ); 
        if( canuse )
        {
            // Find the point indices for the 16 patch vertices.
            CqLath pPoint = pFace().cv().cv().cf().cf();
            CqLath pRow = pPoint;

            Vector<Integer>	aiVertices	= new Vector<Integer>();
            Vector<Integer>	aiFVertices	= new Vector<Integer>();

            // 0,0
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 0,1
            pPoint = pPoint.ccf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 0,2
            pPoint = pPoint.cv().ccf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 0,3
            pPoint = pPoint.cv().ccf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 1,0
            pRow = pPoint = pRow.cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 1,1
            pPoint = pPoint.cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 1,2
            pPoint = pPoint.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 1,3
            pPoint = pPoint.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 2,0
            pRow = pPoint = pRow.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 2,1
            pPoint = pPoint.cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 2,2
            pPoint = pPoint.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 2,3
            pPoint = pPoint.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 3,0
            pPoint = pRow.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 3,1
            pPoint = pPoint.cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 3,2
            pPoint = pPoint.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );
            // 3,3
            pPoint = pPoint.ccv().cf();
            aiVertices.add( pPoint.VertexIndex() );
            aiFVertices.add( pPoint.FaceVertexIndex() );

            STLVector<CqSurfacePatchBicubic> apSurfaces = new STLVector<CqSurfacePatchBicubic>(CqSurfacePatchBicubic.class);

            int iTime;

            for( iTime = 0; iTime < pTopology().iTimes(); iTime++ )
            {
                // Create a surface patch
            	CqSurfacePatchBicubic pSurface = new CqSurfacePatchBicubic();
                // Fill in default values for all primitive variables not explicitly specified.
                pSurface.SetSurfaceParameters( pTopology().pPoints( iTime ) );

//                Vector<CqParameter*>::iterator iUP;
//                Vector<CqParameter*>::iterator end = pTopology().pPoints( iTime).aUserParams().end();
                for ( CqParameter iUP : pTopology().pPoints( iTime ).aUserParams() )
                {
                    if ( ( iUP ) .Class().getValue() == class_varying )
                    {
                        // Copy any 'varying' class primitive variables.
                        CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                        pNewUP.SetSize( pSurface.cVarying() );
                        pNewUP.SetValue( ( iUP ), 0, aiVertices.get(5) );
                        pNewUP.SetValue( ( iUP ), 1, aiVertices.get(6) );
                        pNewUP.SetValue( ( iUP ), 2, aiVertices.get(9) );
                        pNewUP.SetValue( ( iUP ), 3, aiVertices.get(10) );
                        pSurface.AddPrimitiveVariable( pNewUP );
                    }
                    else if ( ( iUP ) .Class().getValue() == class_vertex )
                    {
                        // Copy any 'vertex' class primitive variables.
                        CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                        pNewUP.SetSize( pSurface.cVertex() );
                        int i;
                        for( i = 0; i < pSurface.cVertex(); i++ )
                            pNewUP.SetValue( ( iUP ), i, aiVertices.get(i) );
                        pSurface.AddPrimitiveVariable( pNewUP );
                    }
                    else if ( ( iUP ) .Class().getValue() == class_facevarying )
                    {
                        // Copy any 'facevarying' class primitive variables.
                        CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                        pNewUP.SetSize( pSurface.cVertex() );
                        int i;
                        for( i = 0; i < pSurface.cVertex(); i++ )
                            pNewUP.SetValue( ( iUP ), i, aiFVertices.get(i) );
                        pSurface.AddPrimitiveVariable( pNewUP );
                    }
                    else if ( ( iUP ) .Class().getValue() == class_uniform )
                    {
                        // Copy any 'uniform' class primitive variables.
                        CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                        pNewUP.SetSize( pSurface.cUniform() );
                        pNewUP.SetValue( ( iUP ), 0, m_FaceIndex );
                        pSurface.AddPrimitiveVariable( pNewUP );
                    }
                    else if ( ( iUP ) .Class().getValue() == class_constant )
                    {
                        // Copy any 'constant' class primitive variables.
                        CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                        pNewUP.SetSize( 1 );
                        pNewUP.SetValue( ( iUP ), 0, 0 );
                        pSurface.AddPrimitiveVariable( pNewUP );
                    }
                }

                // Need to get rid of any 'h' values added to the "P" variables during multiplication.
                int i;
                for( i = 0; i < pSurface.cVertex(); i++ )
                    ((CqVector4D)pSurface.P().pValue_get(i,0)).assignment( new CqVector3D( (CqVector4D)( pSurface.P().pValue_get(i,0) ) ) );

                CqMatrix matuBasis = new CqMatrix( RendermanInterface.RiBSplineBasis );
                CqMatrix matvBasis = new CqMatrix( RendermanInterface.RiBSplineBasis );
                pSurface.ConvertToBezierBasis( matuBasis, matvBasis );

                int iUses = Uses();

                // If the shader needs s/t or u/v, and s/t is not specified, then at this point store the object space x,y coordinates.
                if ( USES( iUses, EnvVars_s ) || USES( iUses, EnvVars_t ) || USES( iUses, EnvVars_u ) || USES( iUses, EnvVars_v ) )
                {
                    if ( USES( iUses, EnvVars_s ) && !pTopology().pPoints().bHasVar(EnvVars_s) )
                    {
                        CqParameterTypedVarying<p_float, p_float> pNewUP = new CqParameterTypedVarying<p_float, p_float>( "s", new EqVariableType(type_float), p_float.class, p_float.class );
                        pNewUP.SetSize( pSurface.cVarying() );

                        ((p_float)pNewUP.pValue_get( 0 , 0 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 1 )).value = 1.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 2 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 3 )).value = 1.0f;

                        pSurface.AddPrimitiveVariable( pNewUP );
                    }

                    if ( USES( iUses, EnvVars_t ) && !pTopology().pPoints().bHasVar(EnvVars_t) )
                    {
                    	CqParameterTypedVarying<p_float, p_float> pNewUP = new CqParameterTypedVarying<p_float, p_float>( "t", new EqVariableType(type_float), p_float.class, p_float.class );
                        pNewUP.SetSize( pSurface.cVarying() );

                        ((p_float)pNewUP.pValue_get( 0 , 0 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 1 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 2 )).value = 1.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 3 )).value = 1.0f;

                        pSurface.AddPrimitiveVariable( pNewUP );
                    }

                    if ( USES( iUses, EnvVars_u ) && !pTopology().pPoints().bHasVar(EnvVars_u) )
                    {
                    	CqParameterTypedVarying<p_float, p_float> pNewUP = new CqParameterTypedVarying<p_float, p_float>( "u", new EqVariableType(type_float), p_float.class, p_float.class );
                        pNewUP.SetSize( pSurface.cVarying() );

                        ((p_float)pNewUP.pValue_get( 0 , 0 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 1 )).value = 1.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 2 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 3 )).value = 1.0f;

                        pSurface.AddPrimitiveVariable( pNewUP );
                    }

                    if ( USES( iUses, EnvVars_v ) && !pTopology().pPoints().bHasVar(EnvVars_v) )
                    {
                    	CqParameterTypedVarying<p_float, p_float> pNewUP = new CqParameterTypedVarying<p_float, p_float>( "v", new EqVariableType(type_float), p_float.class, p_float.class );
                        pNewUP.SetSize( pSurface.cVarying() );

                        ((p_float)pNewUP.pValue_get( 0 , 0 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 1 )).value = 0.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 2 )).value = 1.0f;
                        ((p_float)pNewUP.pValue_get( 0 , 3 )).value = 1.0f;

                        pSurface.AddPrimitiveVariable( pNewUP );
                    }
                }
                apSurfaces.add( pSurface );
            }

            if( apSurfaces.size() == 1 )
                aSplits.add(apSurfaces.get( 0 ));
            else if( apSurfaces.size() > 1 )
            {
            	CqDeformingSurface pMotionSurface = new CqDeformingSurface( (CqBasicSurface)null );
                for( iTime = 0; iTime < pTopology().iTimes(); iTime++ )
                {
                    float time = pTopology().Time( iTime );
                    pMotionSurface.AddTimeSlot( time, apSurfaces.get( iTime ) );
                }
                aSplits.add(pMotionSurface);
            }
        }
        else
        {
            // Subdivide the face, and create new patches for the subfaces.
            Vector<CqLath> apSubFaces = new Vector<CqLath>();
            pTopology().SubdivideFace( pFace(), apSubFaces );

            // Now create new patch objects for each subface.
//            Vector<CqLath*>::iterator iSF;
            for( CqLath iSF : apSubFaces )
            {
    			// Create a new patch object, note the use of the same face index as the current patch, as "uniform" values won't change, 
    			// so can be shared up the subdivision stack.
            	CqSurfaceSubdivisionPatch pNew = new CqSurfaceSubdivisionPatch( pTopology(), (iSF), m_FaceIndex );
                aSplits.add(pNew);
            }
        }

        return(aSplits.size());

    }
    
    public boolean Diceable()
    {
    	assert( pTopology()!=null );
    	assert( pTopology().pPoints()!=null );
    	assert( pFace()!=null );
    	
    	// If the cull check showed that the primitive cannot be diced due to crossing the e and hither planes,
    	// then we can return immediately.
    	if ( !m_fDiceable )
    		return ( false );
    	
    	// If we can use a patch, don't dice, as dicing a patch is much quicker.
    	if( pTopology().CanUsePatch( pFace() ) )
    		return(false);
    	
    	// Get the laths that reference the vertices of this face
    	Vector<CqLath> aQfv = new Vector<CqLath>();
    	pFace().Qfv(aQfv);
    	
    	// Cannot dice if not 4 points
    	if ( aQfv.size() != 4 )
    		return ( false );
    	
    	// Otherwise we should continue to try to find the most advantageous split direction, OR the dice size.
    	final CqMatrix matCtoR = QGetRenderContext() .matSpaceToSpace( "camera", "raster", new CqMatrix(), new CqMatrix(), QGetRenderContext().Time() );
    	
    	// Convert the control hull to raster space.
    	CqVector2D[] avecHull = new CqVector2D[ 4 ];
    	for( int i=0; i<4; i++ )	avecHull[i] = new CqVector2D();
    	int i;
    	
    	float ShadingRate = pAttributes() .GetFloatAttribute( "System", "ShadingRate" ) [ 0 ];
    	
    	for ( i = 0; i < 4; i++ )
    		avecHull[ i ].assignment( matCtoR.multiply( new CqVector3D( (CqVector4D)pTopology().pPoints().P().pValue_get( 0, aQfv.get( i ).VertexIndex() ) ) ) );
    	
    	float uLen = 0;
    	float vLen = 0;
    	
    	CqVector2D	Vec1 = avecHull[ 1 ].sub( avecHull[ 0 ] );
    	CqVector2D	Vec2 = avecHull[ 2 ].sub( avecHull[ 3 ] );
    	uLen = ( Vec1.Magnitude2() > Vec2.Magnitude2() ) ? Vec1.Magnitude2() : Vec2.Magnitude2();
    	
    	Vec1 = avecHull[ 3 ].sub( avecHull[ 0 ] );
    	Vec2 = avecHull[ 2 ].sub( avecHull[ 1 ] );
    	vLen = ( Vec1.Magnitude2() > Vec2.Magnitude2() ) ? Vec1.Magnitude2() : Vec2.Magnitude2();
    	
		if( ShadingRate>0 ){
			uLen = (float) sqrt( uLen  / ShadingRate);
			vLen = (float) sqrt( vLen  / ShadingRate);
		}
		else{
			uLen = 0;
			vLen = 0;
		}
    	
    	m_SplitDir = ( uLen > vLen ) ? new EqSplitDir(SplitDir_U) : new EqSplitDir(SplitDir_V);
    	
    	uLen = max( round( uLen ), 1 );
    	vLen = max( round( vLen ), 1 );
    	
    	m_uDiceSize = (int)uLen;
    	m_vDiceSize = (int)vLen;
    	
    	// Note Subd surfaces always have a power of 2 dice rate because they
    	// are diced by recursive subdivision. Hence no need to set it explicitly.
    	
    	if ( uLen < FLT_EPSILON || vLen < FLT_EPSILON )
    	{
    		m_fDiscard = true;
    		return ( false );
    	}
    	
    	// because splitting to a bicubic patch is so much faster than dicing by
    	// recursive subdivision, the grid size is made smaller than usual to give
    	// us more chance to break regular parts off as a patch.
    	float gs = 8.0f;
    	final float[] poptGridSize = QGetRenderContext() .optCurrent().GetFloatOption( "System", "SqrtGridSize" );
    	if( poptGridSize!=null )
    		gs = poptGridSize[0] / 2.0f;
    	
    	if ( m_uDiceSize > gs) return false;
    	if ( m_vDiceSize > gs) return false;
    	
    	return ( true );
    }

    // Dice rate table		              0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
    private static int aDiceSizes[] = { 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4 };
    
    private static float BilinearEvaluate( final float A, final float B, final float C, final float D, float s, float t )
    {
    	float AB, CD;
        // Work out where the u points are first, then linear interpolate the v value.
        if ( s <= 0.0 )
        {
            AB = A;
            CD = C;
        }
        else
        {
            if ( s >= 1.0 )
            {
                AB = B;
                CD = D;
            }
            else
            {
                AB = ( B - A ) * s + A;
                CD = ( D - C ) * s + C;
            }
        }

        float R;
        if ( t <= 0.0 )
            R = AB;
        else
        {
            if ( t >= 1.0 )
                R = CD;
            else
                R = ( CD - AB ) * t + AB;
        }

        return ( R );
    }

    /** 
     * Dice the patch this primitive represents.
     * Subdivide recursively the appropriate number of times, then extract the information into 
     * a MPG structure.
     */
    public	CqMicroPolyGridBase DiceExtract()
    {
    	assert( pTopology()!=null );
        assert( pTopology().pPoints()!=null );
        assert( pFace()!=null );

        int dicesize = min(max(m_uDiceSize, m_vDiceSize), 16);

    	int sdcount = aDiceSizes[ dicesize ];
        dicesize = 1 << sdcount;
        int lUses = Uses();

        STLVector<CqMicroPolyGrid> apGrids = new STLVector<CqMicroPolyGrid>(CqMicroPolyGrid.class);

        int iTime;
        for( iTime = 0; iTime < pTopology().iTimes(); iTime++ )
        {
            CqMicroPolyGrid pGrid = new CqMicroPolyGrid( dicesize, dicesize, pTopology().pPoints() );

            CqPolygonPoints pMotionPoints = pTopology().pPoints( iTime );

            int isd;
            Vector<CqLath> apSubFace1 = new Vector<CqLath>();
            Vector<CqLath> apSubFace2 = new Vector<CqLath>();
            apSubFace1.add(pFace());

            for( isd = 0; isd < sdcount; isd++ )
            {
                apSubFace2.clear();
//                Vector<CqLath*>::iterator iSF;
                for( CqLath iSF : apSubFace1 )
    			{
                    // Subdivide this face, storing the resulting new face indices.
                    Vector<CqLath> apSubFaceTemp = new Vector<CqLath>();
                    pTopology().SubdivideFace( (iSF), apSubFaceTemp );
                    // Now combine these into the new face indices for this subdivision level.
//                    apSubFace2.insert(apSubFace2.end(), apSubFaceTemp.begin(), apSubFaceTemp.end());
                    apSubFace2.addAll( apSubFaceTemp );
                }
                // Now swap the new level's indices for the old before repeating at the next level, if appropriate.
//                apSubFace1.swap(apSubFace2);
        		Vector<CqLath> tmp = new Vector<CqLath>( apSubFace1 );
        		apSubFace1 = new Vector<CqLath>( apSubFace2 );
        		apSubFace2 = new Vector<CqLath>( tmp );
        		tmp.clear();

            }

            // Now we use the first face index to start our extraction
            int nc, nr, c, r;
            nc = nr = dicesize;
            r = 0;

            CqLath pLath, pTemp;
            pLath = apSubFace1.get(0);
            pTemp = pLath;

            // Get data from pLath
            int ivA = pLath.VertexIndex();
            int iFVA = pLath.FaceVertexIndex();
            int indexA = 0;
            StoreDice( pGrid, pMotionPoints, ivA, iFVA, indexA );

            indexA++;
            pLath = pLath.ccf();
            c = 0;
            while( c < nc )
            {
                ivA = pLath.VertexIndex();
    	        iFVA = pLath.FaceVertexIndex();
                StoreDice( pGrid, pMotionPoints, ivA, iFVA, indexA );

                if( c < ( nc - 1 ) )
                    pLath = pLath.cv().ccf();

                indexA++;
                c++;
            }
            r++;

            while( r <= nr )
            {
                pLath = pTemp.cf();
                if( r < nr )
                    pTemp = pLath.ccv();

                // Get data from pLath
                ivA = pLath.VertexIndex();
    	        iFVA = pLath.FaceVertexIndex();
                indexA = ( r * ( nc + 1 ) );
                StoreDice( pGrid, pMotionPoints, ivA, iFVA, indexA );

                indexA++;
                pLath = pLath.cf();
                c = 0;
                while( c < nc )
                {
                    ivA = pLath.VertexIndex();
    		        iFVA = pLath.FaceVertexIndex();
                    StoreDice( pGrid, pMotionPoints, ivA, iFVA, indexA );

                    if( c < ( nc - 1 ) )
                        pLath = pLath.ccv().cf();

                    indexA++;
                    c++;
                }

                r++;
            }


            // If the color and opacity are not defined, use the system values.
            if ( USES( lUses, EnvVars_Cs ) && !pTopology().pPoints().bHasVar(EnvVars_Cs) )
            {
                if ( pAttributes() .GetColorAttribute( "System", "Color" )!=null )
                    pGrid.pVar(EnvVars_Cs) .SetColor( new CqColor( pAttributes() .GetColorAttribute( "System", "Color" ) [ 0 ] ) );
                else
                    pGrid.pVar(EnvVars_Cs) .SetColor( new CqColor( 1, 1, 1 ) );
            }

            if ( USES( lUses, EnvVars_Os ) && !pTopology().pPoints().bHasVar(EnvVars_Os) )
            {
                if ( pAttributes() .GetColorAttribute( "System", "Opacity" )!=null )
                    pGrid.pVar(EnvVars_Os) .SetColor( new CqColor( pAttributes() .GetColorAttribute( "System", "Opacity" ) [ 0 ] ) );
                else
                    pGrid.pVar(EnvVars_Os) .SetColor( new CqColor( 1, 1, 1 ) );
            }
            apGrids.add( pGrid );

            // Fill in u/v if required.
            if ( USES( lUses, EnvVars_u ) && !pTopology().pPoints().bHasVar(EnvVars_u) )
            {
                int iv, iu;
                for ( iv = 0; iv <= dicesize; iv++ )
                {
                    float v = ( 1.0f / ( dicesize + 1 ) ) * iv;
                    for ( iu = 0; iu <= dicesize; iu++ )
                    {
                        float u = ( 1.0f / ( dicesize + 1 ) ) * iu;
                        int igrid = ( iv * ( dicesize + 1 ) ) + iu;
                        pGrid.pVar(EnvVars_u).SetFloat( BilinearEvaluate( 0.0f, 1.0f, 0.0f, 1.0f, u, v ), igrid );
                    }
                }
            }

            if ( USES( lUses, EnvVars_v ) && !pTopology().pPoints().bHasVar(EnvVars_v) )
            {
                int iv, iu;
                for ( iv = 0; iv <= dicesize; iv++ )
                {
                    float v = ( 1.0f / ( dicesize + 1 ) ) * iv;
                    for ( iu = 0; iu <= dicesize; iu++ )
                    {
                        float u = ( 1.0f / ( dicesize + 1 ) ) * iu;
                        int igrid = ( iv * ( dicesize + 1 ) ) + iu;
                        pGrid.pVar(EnvVars_v).SetFloat( BilinearEvaluate( 0.0f, 0.0f, 1.0f, 1.0f, u, v ), igrid );
                    }
                }
            }

            // Fill in s/t if required.
            if ( USES( lUses, EnvVars_s ) && !pTopology().pPoints().bHasVar(EnvVars_s) )
            {
                pGrid.pVar(EnvVars_s).SetValueFromVariable( pGrid.pVar(EnvVars_u) );
            }

            if ( USES( lUses, EnvVars_t ) && !pTopology().pPoints().bHasVar(EnvVars_t) )
            {
                pGrid.pVar(EnvVars_t).SetValueFromVariable( pGrid.pVar(EnvVars_v) );
            }
        }

        if( apGrids.size() == 1 )
            return( apGrids.get( 0 ) );
        else
        {
            CqMotionMicroPolyGrid pGrid = new CqMotionMicroPolyGrid();
            int i;
            for ( i = 0; i < pTopology().iTimes(); i++ )
                pGrid.AddTimeSlot( pTopology().Time( i ), apGrids.get( i ) );
            return( pGrid );
        }

    }

    /** 
     *  Determine whether the passed surface is valid to be used as a
     *  frame in motion blur for this surface.
     */
    public boolean IsMotionBlurMatch( CqBasicSurface pSurf )
    {
        return( false );
    }

    public void StoreDice( CqMicroPolyGrid pGrid, final CqPolygonPoints pPoints, int iParam, int iFVParam, int iData)
    {
        int lUses = m_Uses;
        int lDone = 0;

        if ( USES( lUses, EnvVars_P ) )
            pGrid.pVar(EnvVars_P) .SetPoint( new CqVector3D( (CqVector4D)pPoints.P().pValue_get( iParam ,0) ), iData );

        // Special cases for s and t if "st" exists, it should override s and t.
        CqParameter pParam;
        if( ( pParam = pPoints.FindUserParam("st") ) != null )
        {
    		int index = iParam;
    		if( pParam.Class().getValue() == class_facevarying )
    			index = iFVParam;
    		CqParameterTyped<p_float, p_float> pSTParam = (CqParameterTyped<p_float, p_float>)(pParam);
            if ( USES( lUses, EnvVars_s ) && ( null != pGrid.pVar(EnvVars_s) ) )
                pGrid.pVar( EnvVars_s ).SetFloat( ((p_float)pSTParam.pValue_get( index ,0)).value, iData);
            if ( USES( lUses, EnvVars_t ) && ( null != pGrid.pVar(EnvVars_t) ) )
                pGrid.pVar( EnvVars_t ).SetFloat( ((p_float)pSTParam.pValue_get( index ,1)).value, iData);
//            DONE( lDone, EnvVars_s );
//            DONE( lDone, EnvVars_t );
            lDone = lDone | ( 0x00000001<<EnvVars_s );
            lDone = lDone | ( 0x00000001<<EnvVars_t );
        }

        if ( USES( lUses, EnvVars_s ) && ( null != pGrid.pVar(EnvVars_s) ) && ( pPoints.bHasVar(EnvVars_s) ) && !isDONE(lDone, EnvVars_s ) )
        {
            if( pPoints.s().Class().getValue() == class_varying || pPoints.s().Class().getValue() == class_vertex )
                pGrid.pVar(EnvVars_s) .SetFloat( ((p_float)pPoints.s().pValue_get( iParam ,0)).value, iData );
            else if( pPoints.s().Class().getValue() == class_facevarying )
                pGrid.pVar(EnvVars_s) .SetFloat( ((p_float)pPoints.s().pValue_get( iFVParam ,0)).value, iData );
            else if( pPoints.s().Class().getValue() == class_uniform )
                pGrid.pVar(EnvVars_s) .SetFloat( ((p_float)pPoints.s().pValue_get( 0 ,0)).value, iData );
        }

        if ( USES( lUses, EnvVars_t ) && ( null != pGrid.pVar(EnvVars_t) ) && ( pPoints.bHasVar(EnvVars_t) ) && !isDONE(lDone, EnvVars_t ) )
        {
            if( pPoints.t().Class().getValue() == class_varying || pPoints.t().Class().getValue() == class_vertex )
                pGrid.pVar(EnvVars_t) .SetFloat( ((p_float)pPoints.t().pValue_get( iParam ,0)).value, iData );
            else if( pPoints.t().Class().getValue() == class_facevarying )
                pGrid.pVar(EnvVars_t) .SetFloat( ((p_float)pPoints.t().pValue_get( iFVParam ,0)).value, iData );
            else if( pPoints.t().Class().getValue() == class_uniform )
                pGrid.pVar(EnvVars_t) .SetFloat( ((p_float)pPoints.t().pValue_get( 0 ,0)).value, iData );
        }

        if ( USES( lUses, EnvVars_Cs ) && ( null != pGrid.pVar(EnvVars_Cs) ) && ( pPoints.bHasVar(EnvVars_Cs) ) )
        {
            if( pPoints.Cs().Class().getValue() == class_varying || pPoints.Cs().Class().getValue() == class_vertex )
                pGrid.pVar(EnvVars_Cs) .SetColor( ((CqColor)pPoints.Cs().pValue_get(iParam,0)), iData );
            else if( pPoints.Cs().Class().getValue() == class_facevarying )
                pGrid.pVar(EnvVars_Cs) .SetColor( ((CqColor)pPoints.Cs().pValue_get(iFVParam,0)), iData );
            else if( pPoints.Cs().Class().getValue() == class_uniform )
                pGrid.pVar(EnvVars_Cs) .SetColor( ((CqColor)pPoints.Cs().pValue_get(0,0)), iData );
        }

        if ( USES( lUses, EnvVars_Os ) && ( null != pGrid.pVar(EnvVars_Os) ) && ( pPoints.bHasVar(EnvVars_Os) ) )
        {
            if( pPoints.Os().Class().getValue() == class_varying || pPoints.Os().Class().getValue() == class_vertex )
                pGrid.pVar(EnvVars_Os) .SetColor( ((CqColor)pPoints.Os().pValue_get(iParam,0)), iData );
            else if( pPoints.Os().Class().getValue() == class_facevarying )
                pGrid.pVar(EnvVars_Os) .SetColor( ((CqColor)pPoints.Os().pValue_get(iFVParam,0)), iData );
            else if( pPoints.Os().Class().getValue() == class_uniform )
                pGrid.pVar(EnvVars_Os) .SetColor( ((CqColor)pPoints.Os().pValue_get(0,0)), iData );
        }

        // Now lets store the diced user specified primitive variables.
//        Vector<CqParameter*>::iterator iUP;
        for ( CqParameter iUP : pPoints.aUserParams() )
        {
            ///TODO: Must transform point/vector/normal/matrix parameter variables from 'object' space to current before setting.
        	IqShader pShader;
        	//【改】aqsis1.01変更********************************************************
    		if ( ( pShader=pGrid.pAttributes() .pshadSurface(m_Time) )!=null )
    			StoreDiceAPVar( pShader, ( iUP ), iParam, iFVParam, iData );
                //StoreDiceAPVar( pShader, ( iUP ), iParam, iData );
    		
            if ( ( pShader=pGrid.pAttributes() .pshadDisplacement(m_Time) )!=null )
            	StoreDiceAPVar( pShader, ( iUP ), iParam, iFVParam, iData );
            	//StoreDiceAPVar( pShader, ( iUP ), iParam, iData );

            if ( ( pShader=pGrid.pAttributes() .pshadAtmosphere(m_Time) )!=null )
            	StoreDiceAPVar( pShader, ( iUP ), iParam, iFVParam, iData );
                //StoreDiceAPVar( pShader, ( iUP ), iParam, iData );
            //******************************************************************************
        }

    }
    
    @SuppressWarnings("unchecked")
//	private static void StoreDiceAPVar( final IqShader pShader, CqParameter pParam, int ivA, int indexA )
    private static void StoreDiceAPVar( final IqShader pShader, CqParameter pParam, int ivA, int ifvA, int indexA )
    {
        // Find the argument
        IqShaderData pArg = pShader.FindArgument( pParam.strName() );
        if ( pArg!=null )
        {
        	//【改】aqsis1.01変更追加*************************
        	int index = ivA;
    		if( pParam.Class().getValue() == class_facevarying )
    			index = ifvA;
    		//************************************************

            switch ( pParam.Type().getValue() )
            {
            case type_float:
                {
                    CqParameterTyped<p_float, p_float> pNParam = (CqParameterTyped<p_float, p_float>)( pParam );
                    //pArg.SetValue( ((p_float)pNParam.pValue_get( ivA ,0)).value, indexA ); 【改】aqsis1.01変更 
                    pArg.SetValue( ((p_float)pNParam.pValue_get( index ,0)).value, indexA );
                }
                break;

            case type_integer:
                {
                    CqParameterTyped<p_int, p_float> pNParam = (CqParameterTyped<p_int, p_float>)( pParam );
                    //pArg.SetValue( ((p_int)pNParam.pValue_get( ivA ,0)).value, indexA );
                    pArg.SetValue( ((p_int)pNParam.pValue_get( index ,0)).value, indexA );
                }
                break;

            case type_point:
            case type_vector:
            case type_normal:
                {
                    CqParameterTyped<CqVector3D, CqVector3D> pNParam = (CqParameterTyped<CqVector3D, CqVector3D>)( pParam );
                    //pArg.SetValue( ((CqVector3D)pNParam.pValue_get( ivA ,0)), indexA );
                    pArg.SetValue( ((CqVector3D)pNParam.pValue_get( index ,0)), indexA );
                }
                break;

            case type_hpoint:
                {
                    CqParameterTyped<CqVector4D, CqVector3D> pNParam = (CqParameterTyped<CqVector4D, CqVector3D>)( pParam );
                    //pArg.SetValue( new CqVector3D( ((CqVector4D)pNParam.pValue_get( ivA ,0)) ), indexA );
                    pArg.SetValue( new CqVector3D((CqVector4D)pNParam.pValue_get( index ,0)), indexA );
                }
                break;

            case type_string:
                {
                    CqParameterTyped<p_String, p_String> pNParam = (CqParameterTyped<p_String, p_String>)( pParam );
                    //pArg.SetValue( ((p_String)pNParam.pValue_get( ivA ,0)).value, indexA );
                    pArg.SetValue( ((p_String)pNParam.pValue_get( index ,0)).value, indexA );
                }
                break;

            case type_color:
                {
                    CqParameterTyped<CqColor, CqColor> pNParam = (CqParameterTyped<CqColor, CqColor>)( pParam );
                    //pArg.SetValue( ((CqColor)pNParam.pValue_get( ivA ,0)), indexA );
                    pArg.SetValue( ((CqColor)pNParam.pValue_get( index ,0)), indexA );
                }
                break;

            case type_matrix:
                {
                    CqParameterTyped<CqMatrix, CqMatrix> pNParam = (CqParameterTyped<CqMatrix, CqMatrix>)( pParam );
                    //pArg.SetValue( ((CqMatrix)pNParam.pValue_get( ivA ,0)), indexA );
                    pArg.SetValue( ((CqMatrix)pNParam.pValue_get( index ,0)), indexA );
                }
                break;

            default:
                {
                    // left blank to avoid compiler warnings about unhandled types
                }
                break;
            }
        }
    }

    
    public CqSubdivision2 Extract( int iTime )
    {
        assert( pTopology()!=null );
        assert( pTopology().pPoints()!=null );
        assert( pFace()!=null );

        // Find the point indices for the polygons surrounding this one.
    	// Use a map to ensure that shared vertices are only counted once.
        HashMap<Integer, Integer> Vertices = new HashMap<Integer, Integer>();
    	int cVerts=0;
        Vector<Integer>	FVertices = new Vector<Integer>();

        Vector<CqLath> aQff	= new Vector<CqLath>();
//        Vector<CqLath> apSubFaces2	= new Vector<CqLath>();
        pFace().Qff( aQff );
//        Vector<CqLath*>::iterator iF;
        for( CqLath iF : aQff )
    	{
    		Vector<CqLath> aQfv = new Vector<CqLath>();
    		(iF).Qfv( aQfv );

//    		Vector<CqLath*>::reverse_iterator iV;
    		CqLath iV;
    		int idx;
//    		for( iV = aQfv.rbegin(); iV != aQfv.rend(); iV++ )
    		for( idx=aQfv.size()-1; idx>=0; idx-- )
    		{
    			iV = aQfv.get(idx);
//    			if( Vertices.find((iV).VertexIndex()) == Vertices.end() )
    			if( !Vertices.containsKey((iV).VertexIndex()) )
    			{
    				Vertices.put( (iV).VertexIndex(), cVerts );
    				cVerts++;
    			}
    			FVertices.add( (iV).FaceVertexIndex() );
    		}
    	}
//    	int cFaceVerts = FVertices.size();
//    	int cFaces = aQff.size();

        // Create a storage class for all the points.
    	CqPolygonPoints pPointsClass = new CqPolygonPoints( cVerts, aQff.size(), FVertices.size() );
        // Fill in default values for all primitive variables not explicitly specified.
        pPointsClass.SetSurfaceParameters( pTopology().pPoints( iTime ) );

        CqSubdivision2 pSurface = new CqSubdivision2( pPointsClass );
        pSurface.Prepare( cVerts );

//        Vector<CqParameter*>::iterator iUP;
//        Vector<CqParameter*>::iterator end = pTopology().pPoints( iTime).aUserParams().end();
        for ( CqParameter iUP : pTopology().pPoints( iTime ).aUserParams() )
        {
            if ( ( iUP ) .Class().getValue() == class_vertex || ( iUP ) .Class().getValue() == class_varying )
            {
                // Copy any 'vertex' or 'varying' class primitive variables.
                CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                pNewUP.SetSize( cVerts );
                //マップからの取り出しは以下のように書き換えた。
//                std::map<int, int>::iterator i;
//                for( i = Vertices.begin(); i != Vertices.end(); i++ )
//                    pNewUP.SetValue( ( iUP ), (*i).second, (*i).first );
                Iterator<Entry<Integer,Integer>> ite = Vertices.entrySet().iterator();
                while( ite.hasNext() ){
                	Entry<Integer,Integer> i = ite.next();
                	pNewUP.SetValue( ( iUP ), (i).getValue(), (i).getKey() );
                }
                pSurface.pPoints().AddPrimitiveVariable( pNewUP );
            }
            else if ( ( iUP ) .Class().getValue() == class_facevarying )
            {
                // Copy any 'facevarying' class primitive variables.
                CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                pNewUP.SetSize( FVertices.size() );
//                Vector<Integre>::iterator i;
    			int iv = 0;
    			for( int i : FVertices ){
    				pNewUP.SetValue( ( iUP ), iv, (i) );
    				iv++;
    			}
                pSurface.pPoints().AddPrimitiveVariable( pNewUP );
            }
            else if ( ( iUP ) .Class().getValue() == class_uniform )
            {
                // Copy any 'uniform' class primitive variables.
                CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                pNewUP.SetSize( pSurface.pPoints().cUniform() );
                pNewUP.SetValue( ( iUP ), 0, m_FaceIndex );
                pSurface.pPoints().AddPrimitiveVariable( pNewUP );
            }
            else if ( ( iUP ) .Class().getValue() == class_constant )
            {
                // Copy any 'constant' class primitive variables.
                CqParameter pNewUP = ( iUP ) .CloneType( ( iUP ) .strName(), ( iUP ) .Count() );
                pNewUP.SetSize( 1 );
                pNewUP.SetValue( ( iUP ), 0, 0 );
                pSurface.pPoints().AddPrimitiveVariable( pNewUP );
            }
        }

        // Need to get rid of any 'h' values added to the "P" variables during multiplication.
        int i;
        for( i = 0; i < cVerts; i++ )
            ((CqVector4D)pSurface.pPoints().P().pValue_get(i,0)).assignment( (CqVector4D)( pSurface.pPoints().P().pValue_get(i,0) ) );

//        int iUses = Uses();

    	int iP = 0;
        for( CqLath iF : aQff )
    	{
    		Vector<Integer> vertices = new Vector<Integer>();
    		Vector<CqLath> aQfv = new Vector<CqLath>();
    		(iF).Qfv( aQfv );
    		
    		CqLath iV;
    		int idx;
//  		Vector<CqLath*>::reverse_iterator iV;
//    		for( iV = aQfv.rbegin(); iV != aQfv.rend(); ++iV )
    		for( idx=aQfv.size()-1; idx>=0; idx-- ) {
    			iV = aQfv.get(idx);
    			vertices.add( Vertices.get( (iV).VertexIndex() ) );
    		}
    		
    		//int[]に変換する
    		int[] verticesAry = new int[ vertices.size() ];
    		for( int ii=0; ii<verticesAry.length; ii++ )		verticesAry[ii] = vertices.get(ii);
    		
    		pSurface.AddFacet( vertices.size(), verticesAry, iP );
    		iP += vertices.size();
        }
        pSurface.Finalise();
        return(pSurface);

    }

    
    
    
    
    
    
    
    
    
    
}
