// 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.StrictMath.*;
import net.cellcomputing.himawari.library.types.CqVector3D;
import static net.cellcomputing.himawari.library.Float_h.*;

/**
 * 
 *	レンダリングのためにオブジェクトの階層モデルを作成する 
 * 
 * @author NTT DATA Corporation
 */
strictfp class CqOcclusionBox {
	
	/**
	 * レンダリング中に使用されるstaticな階層構造を作成。<br>
	 * レンダリング処理の前に、一度だけ呼ばれる。
	 * 
	 * @param bucketXSize	バケツの数　(X値)
	 * @param bucketYSize	バケツの数　(Y値)
	 * @param XFWidth	フィルター幅　(X値)
	 * @param YFWidth	フィルター幅　(Y値)
	 */
	public static void CreateHierarchy( int bucketXSize, int bucketYSize, int XFWidth, int YFWidth )
	{
		//Make sure this hasn't been called more than once;
	    assert( m_Hierarchy == null );
	    assert( m_LevelStartId == null );
	    
	    int xdivisions = ( int ) ( log10( (float)(bucketXSize + XFWidth) ) / log10( 2.0 ) );
	    int ydivisions = ( int ) ( log10( (float)(bucketYSize + YFWidth) ) / log10( 2.0 ) );

	    m_HierarchyLevels = min( xdivisions, ydivisions );

	    m_LevelStartId = new int[ m_HierarchyLevels + 1 ];
	    m_LevelStartId[ 0 ] = 0;
	    int numBoxes = 1;
	    int i;
	    for ( i = 1; i < m_HierarchyLevels; i++ )
	    {
	        m_LevelStartId[ i ] = numBoxes;
	        numBoxes = numBoxes * 4 + 1;
	    }
	    m_LevelStartId[ m_HierarchyLevels ] = numBoxes;
	    m_TotalBoxes = numBoxes;

	    m_Hierarchy = new CqOcclusionBox[ numBoxes ];

	    for ( i = 0; i < numBoxes; i++ )
	    {
	    	m_Hierarchy[ i ] = new CqOcclusionBox(); 
	        m_Hierarchy[ i ].m_Id = i;
	    }
	}
	
	/**
	 * 
	 *	CreateHierachy()で作成された階層構造をdeleteする
	 * 
	 */
	public static void DeleteHierarchy()
	{
		// make sure this isn't being called out of turn.
		assert( m_Hierarchy != null );
		assert( m_LevelStartId != null );
		
		m_Hierarchy = null;
		m_LevelStartId = null;
	
	}
	
	/**
	 * バケツ一つに対し、階層構造をセットアップする。
	 * 各バケツをレンダリングする度に呼ばれる。
	 * 
	 * @param bucket	レンダリングするバケツ
	 * @param xMin	バケツの左端 (taking into account crop windows etc)
	 * @param yMin	バケツの上端
	 * @param xMax	バケツの右端
	 * @param yMax	バケツの下端
	 */
	public static void SetupHierarchy( CqBucket bucket, int xMin, int yMin, int xMax, int yMax )
	{
	    assert( bucket != null);
	    m_Bucket = bucket;

	    m_Hierarchy[ 0 ].SetBounds( xMin, yMin, xMax, yMax );
	    m_Hierarchy[ 0 ].SetupChildren();
	    m_Hierarchy[ 0 ].Clear();
	
	}
	
	/**
	 * 
	 * UpdateLevel()のセッター
	 * 最大・最小Z値を更新する。
	 * 
	 */
	public static void Update()
	{
		UpdateLevel( m_HierarchyLevels - 1 );
	}
	
	/**
	 * 
	 * IsCullable()のゲッター
	 * バウンディングされたオブジェクトを選別できるか否かを返す。
	 * 
	 * @param bound	バウンディングボックス
	 * @return	true / false
	 */
	public static boolean CanCull( CqBound bound )
	{
		return m_Hierarchy[ 0 ].IsCullable( bound );
	}
	
	/**
	 * 
	 * MarkForUpdate()のセッター
	 * 
	 * @param id
	 */
	public static void MarkForUpdate( int id )
	{
		assert( id >= 0 && id < m_TotalBoxes );
		m_Hierarchy[ id ].MarkForUpdate();
	}
	
	/**
	 * コンストラクタ　初期値を設定
	 */
	protected CqOcclusionBox()
	{
		m_MinX = 0;
		m_MinY = 0;
		m_MaxX = 0;
		m_MaxY = 0;
		
		m_MinZ = FLT_MAX;
		m_MaxZ = FLT_MAX;
		
		m_Id = -1; // Start off uninitialised
		
		m_NeedsUpdating = false;
	}
	
	/**
	 * 
	 * バウンディングボックスの子に再帰的にバウンディングを行う。
	 * 
	 */
	protected void SetupChildren()
	{
		int firstChildId = m_Id * 4 + 1;
	    if ( firstChildId >= m_TotalBoxes )
	    {
	        // bottom of tree. setup the pixels we cover
	        for ( int j = m_MinY; j < m_MaxY; j++ )
	        {
	            for ( int i = m_MinX; i < m_MaxX; i++ )
	            {
	            	int pie;
	            	pie = CqBucket.ImageElement( i, j );
	                CqBucket.aieImage(pie).SetOcclusionBoxId( m_Id );
	            }
	        }
	    }
	    else
	    {
	        int midX = ( m_MaxX - m_MinX ) / 2 + m_MinX;
	        int midY = ( m_MaxY - m_MinY ) / 2 + m_MinY;

	        m_Hierarchy[ firstChildId ].SetBounds( m_MinX, m_MinY, midX, midY );
	        m_Hierarchy[ firstChildId + 1 ].SetBounds( midX, m_MinY, m_MaxX, midY );
	        m_Hierarchy[ firstChildId + 2 ].SetBounds( m_MinX, midY, midX, m_MaxY );
	        m_Hierarchy[ firstChildId + 3 ].SetBounds( midX, midY, m_MaxX, m_MaxY );

	        m_Hierarchy[ firstChildId ].SetupChildren();
	        m_Hierarchy[ firstChildId + 1 ].SetupChildren();
	        m_Hierarchy[ firstChildId + 2 ].SetupChildren();
	        m_Hierarchy[ firstChildId + 3 ].SetupChildren();
	    }

	}
	
	/**
	 * 
	 * 与えられたレベルで変化の起きたボックスに対し、格納された最大・最小Z値を更新する。
	 * また変更をする場合、階層構造の中の親ボックスの階層レベルを上げて繰り返す。
	 * 
	 * @param level	階層レベル
	 */
	protected static void UpdateLevel( int level )
	{
		assert( level < m_HierarchyLevels && level >= 0 );

	    int firstBox = m_LevelStartId[ level ];
	    int lastBox = m_LevelStartId[ level + 1 ] - 1;

	    boolean updateNextLevel = false;
	    for ( int i = firstBox; i <= lastBox; i++ )
	    {
	        // only update if it's been marked as needing it
	        if ( m_Hierarchy[ i ].NeedsUpdating() )
	        {
	            // only mark parent for update if we actually change
	            if ( m_Hierarchy[ i ].UpdateZValues() )
	            {
	                m_Hierarchy[ i / 4 ].MarkForUpdate();
	                updateNextLevel = true;
	            }
	        }
	    }

	    // move up a level
	    if ( updateNextLevel && level > 0 )
	        UpdateLevel( level - 1 );
	}
	
	/**
	 * 
	 *	ボックスに格納されている最大・最小Z値を更新する。<br>
	 * 	その子であるボックスは全て最新のものと仮定する。
	 *  
	 * @return	madeUpdate	変化があればtrueを返す。
	 */
	protected boolean UpdateZValues()
	{
		boolean madeUpdate = false;
	    float currentMaxZ = -FLT_MAX;
	    float currentMinZ = m_MinZ;

	    int firstChildId = m_Id * 4 + 1;
	    if ( firstChildId >= m_TotalBoxes )
	    {
	        // we don't have any children so check pixel depths directly
	        for ( int j = m_MinY; j < m_MaxY; j++ )
	        {
	            for ( int i = m_MinX; i < m_MaxX; i++ )
	            {
	                int pie;
	                pie = CqBucket.ImageElement( i, j );
	                CqImagePixel img = CqBucket.aieImage( pie );
	                // only update if it's been marked as needing it
	                if ( img.NeedsZUpdating() )
	                {
	                    img.UpdateZValues();
	                }
	                if ( img.MaxDepth() > currentMaxZ )
	                {
	                    currentMaxZ = img.MaxDepth();
	                }
	                if ( img.MinDepth() < currentMinZ )
	                {
	                    currentMinZ = img.MinDepth();
	                }
	            }
	        }
	    }
	    else
	    {
	        for ( int i = 0; i < 4; i++ )
	        {
	            if ( m_Hierarchy[ firstChildId + i ].m_MaxZ > currentMaxZ )
	            {
	                currentMaxZ = m_Hierarchy[ firstChildId + i ].m_MaxZ;
	            }
	            if ( m_Hierarchy[ firstChildId + i ].m_MinZ < currentMinZ )
	            {
	                currentMinZ = m_Hierarchy[ firstChildId + i ].m_MinZ;
	            }
	        }
	    }

	    if ( currentMaxZ < m_MaxZ )
	    {
	        m_MaxZ = currentMaxZ;
	        madeUpdate = true;
	    }
	    if ( currentMinZ < m_MinZ )
	    {
	        m_MinZ = currentMinZ;
	        madeUpdate = true;
	    }

	    m_NeedsUpdating = false;
	    return madeUpdate;
	}
	
	/**
	 * 
	 * ボックスとその子がもつ最大・最小Z値をリセットする。
	 * 
	 */
	protected void Clear()
	{
		m_MinZ = FLT_MAX;
		m_MaxZ = FLT_MAX;
		m_NeedsUpdating = false;
		
		int firstChildId = m_Id * 4 + 1;
		if ( firstChildId >= m_TotalBoxes )
			return ; // bottom of tree. we have no children
		
		for ( int i = 0; i < 4; i++ )
			m_Hierarchy[ firstChildId + i ].Clear();
	}
	
	/**
	 * 
	 * ボックスのスクリーン画素領域を設定する。
	 * 
	 * @param x0	領域開始X座標
	 * @param y0	領域開始Y座標
	 * @param x1	領域終了X座標
	 * @param y1	領域終了Y座標
	 */
	protected void SetBounds( int x0, int y0, int x1, int y1 )
	{
		m_MinX = x0;
		m_MinY = y0;
		m_MaxX = x1;
		m_MaxY = y1;
	}
	
	/**
	 * 
	 * 与えられたバウンディングボックスが自分自身と重なる場合、テストを行う。
	 * 
	 * @param bound	 テストするバウンディングボックス
	 * @return	retval	バウンドが重なる場合はtrueを返す
	 */
	protected boolean Overlaps( CqBound bound )
	{
		boolean retval = true;

	    if (!( bound.vecMin().x <= m_MaxX && 
	    		bound.vecMin().y <= m_MaxY &&
	            bound.vecMax().x >= m_MinX && 
	            bound.vecMax().y >= m_MinY ))
	    {
	        retval = false;
	    }

	    return retval;
	}
	
	/**
	 * 
	 *  バウンディングされたオブジェクトを選別できる場合にテストをする。
	 *  
	 * @param bound		テストをするバウンディングオブジェクト
	 * @return	true / false	バウンディングボックスの中にバウンディングボックスが隠れている場合、trueを返す
	 */
	protected boolean IsCullable( CqBound bound )
	{
		CqVector3D vecMin = bound.vecMin();
		CqVector3D vecMax = bound.vecMax();
		float zVal = vecMin.z;
		
		if ( zVal > m_MaxZ )
		{
			// 隠れている場合	bound totally hidden by box
			return true;
		}
		else if ( zVal < m_MinZ )
		{
			// 見えている場合	bound totally visible
			return false;
		}
		
		int firstChildId = m_Id * 4 + 1;
		if ( firstChildId >= m_TotalBoxes )
		{
			// 子をもたない場合,葉の場合(テストモデル)： check pixels directly
			int x0 = max( m_MinX, (int)( vecMin.x ) );
			int y0 = max( m_MinY, (int)( vecMin.y ) );
			int x1 = min( m_MaxX, (int)( vecMax.x ) );
			int y1 = min( m_MaxY, (int)( vecMax.y ) );
			
			for ( int j = y0; j < y1; j++ )
			{
				for ( int i = x0; i < x1; i++ )
				{
					if ( zVal < m_Bucket.MaxDepth( i, j ) )
						return false;
				}
			}
		}
		else
		{
			// 子のテストを再帰的に行う。バウンディングボックスが全ての子に隠されているなら、trueを返す。
			for ( int i = 0; i < 4; i++ )
			{
				if ( m_Hierarchy[ firstChildId + i ].Overlaps( bound ) )
				{
					if ( !m_Hierarchy[ firstChildId + i ].IsCullable( bound ) )
						return false;
				}
			}
		}
		return true;
	}
	
	/**
	 * 
	 * アップデートが必要かどうかの情報を示す。
	 * 
	 * @return	m_NeedsUpdating
	 */
	protected boolean NeedsUpdating()
	{
		return m_NeedsUpdating;
	}

	/**
	 * 
	 * アップデート処理を判断するマークをつける。
	 * 
	 */
	protected void MarkForUpdate()
	{
		m_NeedsUpdating = true;
	}
	
	protected int m_MinX; 	//バウンディングボックスの位置　(ピクセル位置)
	protected int m_MinY;
	protected int m_MaxX;
	protected int m_MaxY;
	
	protected float m_MinZ;
	protected float m_MaxZ;
	
	protected int m_Id;
	
	/*
	 m_Hierarchyは木構造だが、高速化を図るため、配列として実行
	 また、各ボックスは葉(明らかなもの)は別として、4人の子をもっている。

	 For reference:
	 this = m_Hierarchy[m_Id];
	 parent = m_Hierarchy[m_Id/4]; (integer divide, rounds down)
	 first child = m_Hierarchy[m_Id*4 + 1]; (if we are a leaf this will be >= m_TotalBoxes)
	 next sibling = m_Hierarchy[m_Id + 1];
	 */
	
	protected static CqBucket m_Bucket;
	protected static CqOcclusionBox[] m_Hierarchy; // tree of OcclusionBoxes
	protected static int m_HierarchyLevels; // the depth of the tree
	protected static int m_TotalBoxes;
	protected static int[] m_LevelStartId; // the id for the start of each level, ie 0,1,5,21... etc
	protected boolean m_NeedsUpdating;
	
}
