/*
* Copyright (c) 2003 Nokia Corporation and/or its subsidiary(-ies).
* All rights reserved.
* This component and the accompanying materials are made available
* under the terms of the License "Eclipse Public License v1.0"
* which accompanies this distribution, and is available
* at the URL "http://www.eclipse.org/legal/epl-v10.html".
*
* Initial Contributors:
* Nokia Corporation - initial contribution.
*
* Contributors:
*
* Description: RenderQueue implementation
*
*/


/*!
 * \internal
 * \file
 * \brief RenderQueue implementation.
 *
 * Render queue holds
 * meshes and sprites that are added to queue in rendering
 * setup. After setup, queue is committed and contents are
 * rendered. Queue grows dynamically, its initial size is
 * defined in m3g_defs.h.
 */

#ifndef M3G_CORE_INCLUDE
#   error included by m3g_core.c; do not compile separately.
#endif

#include "m3g_array.h"

/*----------------------------------------------------------------------
 * Private data structures
 *--------------------------------------------------------------------*/

/*!
 * \internal
 * \brief RenderQueue entry object
 */
struct RenderItemImpl
{
	Node *node;
	Matrix toCamera;
    
    M3Gint subMeshIndex;
	M3Guint sortKey;
};

/*!
 * \internal
 * \brief Drawable queue
 */
struct RenderBucketImpl
{
    PointerArray items;
};


/* Sanity checking... */
M3G_CT_ASSERT(M3G_RENDERQUEUE_BUCKET_BITS >= M3G_APPEARANCE_HARD_SORT_BITS);


/*----------------------------------------------------------------------
 * Private functions
 *--------------------------------------------------------------------*/

static M3G_INLINE RenderBucket *m3gGetRenderBucket(RenderQueue *rq,
                                                   M3Guint sortKey,
                                                   Interface *m3g)
{
    int i = (int)(sortKey >> (32 - M3G_RENDERQUEUE_BUCKET_BITS));
    RenderBucket *bucket = rq->buckets[i];
    
    if (!bucket) {
        bucket = m3gAllocZ(m3g, sizeof(RenderBucket));
        /* array already initialized by zero-allocation; see m3g_array.h */
        rq->buckets[i] = bucket;
    }

    if (i < rq->minBucket) {
        rq->minBucket = i;
    }
    if (i > rq->maxBucket) {
        rq->maxBucket = i;
    }
    
    return bucket;
}

static void m3gDestroyRenderBucket(RenderBucket *bucket, Interface *m3g)
{
    if (bucket) {
        int i;
        PointerArray *items = &bucket->items;
        for (i = 0; i < m3gArraySize(items); ++i) {
            m3gFree(m3g, m3gGetArrayElement(items, i));
        }
        m3gDestroyArray(items, m3g);
    }
    m3gFree(m3g, bucket);
}

static RenderItem *m3gGetRenderItem(RenderQueue *rq, Interface *m3g)
{
    RenderItem *item = rq->freeItems;
    if (!item) {
        m3gIncStat(m3g, M3G_STAT_RENDERQUEUE_SIZE, 1);
        item = m3gAlloc(m3g, sizeof(RenderItem));
    }
    else {
        M3G_VALIDATE_MEMBLOCK(item);
        rq->freeItems = *(RenderItem**)item; /* move to next */
    }
    return item;
}

static void m3gRecycleRenderItem(RenderQueue *rq, RenderItem *item)
{
    if (item) {
        *(RenderItem**)item = rq->freeItems; /* store "next" pointer */
        rq->freeItems = item;
    }
}

static M3Gbool m3gInsertRenderItem(RenderBucket *bucket,
                                   RenderItem *item,
                                   Interface *m3g)
{
    PointerArray *items = &bucket->items;
    int idx = m3gArraySize(items);
    
    /* Do a binary search for the sorting key of the item */
    {
        M3Guint key = item->sortKey;
        int low = 0;
        int high = idx;
        const RenderItem *cmp;

        idx >>= 1;
        
        while (low < high) {
            cmp = (const RenderItem*) m3gGetArrayElement(items, idx);
            
            if (cmp->sortKey < key) {
                low = idx + 1;
            }
            else if (cmp->sortKey > key) {
                high = idx;
            }
            else {
                break;
            }            
            idx = (low + high) >> 1;
        }
    }

    /* Now that we know where to insert, insert; out of memory here
     * returns < 0 */

    return (m3gArrayInsert(items, idx, item, m3g) >= 0);
}


/*----------------------------------------------------------------------
 * Internal functions
 *--------------------------------------------------------------------*/

/*!
 * \internal
 * \brief Creates a new render queue.
 *
 * \param m3g   M3G interface object
 * \return      RenderQueue object
 */
static RenderQueue *m3gCreateRenderQueue(Interface *m3g)
{
    RenderQueue *rq;
    
    rq = m3gAllocZ(m3g, (M3Gsizei) sizeof(RenderQueue));
    return rq;
}

/*!
 * \internal
 * \brief Destroys a render queue and frees
 * all allocated memory.
 *
 * \param m3g   M3G interface object
 * \param rq    RenderQueue
 */
static void m3gDestroyRenderQueue(Interface *m3g, RenderQueue *rq)
{
    if (rq) {
        int i;
        for (i = 0; i < (1 << M3G_RENDERQUEUE_BUCKET_BITS); ++i) {
            RenderBucket *bucket = rq->buckets[i];
            m3gDestroyRenderBucket(bucket, m3g);
        }
        while (rq->freeItems) {
            RenderItem *item = rq->freeItems;
            rq->freeItems = *(RenderItem**)item;
            m3gFree(m3g, item);
        }
    }
    m3gFree(m3g, rq);
}

/*!
 * \internal
 * \brief Inserts a mesh to the queue. May allocate
 * memory if queue size is exceeded.
 *
 * \param m3g           M3G interface object
 * \param rq            RenderQueue
 * \param mesh          Mesh object
 * \param subMeshIndex  submesh index inside mesh
 * \param sortKey       sorting key
 */
static M3Gbool m3gInsertDrawable(Interface *m3g,
                                 RenderQueue *rq,
                                 Node *node,
                                 const Matrix *toCamera,
                                 M3Gint subMeshIndex,
                                 M3Guint sortKey)
{
    RenderItem *item;
    RenderBucket *bucket;
    
    item = m3gGetRenderItem(rq, m3g);
    if (!item) {
        goto OutOfMemory;
    }

    bucket = m3gGetRenderBucket(rq, sortKey, m3g);
    if (!bucket) {
        goto OutOfMemory;
    }

    item->node         = node;
    item->toCamera     = *toCamera;
    item->subMeshIndex = subMeshIndex;
    item->sortKey      = (sortKey << M3G_RENDERQUEUE_BUCKET_BITS);

    M3G_BEGIN_PROFILE(m3g, M3G_PROFILE_SETUP_SORT);
    if (!m3gInsertRenderItem(bucket, item, m3g)) {
        goto OutOfMemory;
    }
    M3G_END_PROFILE(m3g, M3G_PROFILE_SETUP_SORT);
    return M3G_TRUE;

OutOfMemory:        
    m3gRecycleRenderItem(rq, item);
    return M3G_FALSE;
}

/*!
 * \internal
 * \brief Clears the queue.
 *
 * \param rq            RenderQueue
 */
static void m3gClearRenderQueue(RenderQueue *rq)
{
    rq->root = NULL;
    rq->lightManager = NULL;
    rq->minBucket = (1 << M3G_RENDERQUEUE_BUCKET_BITS);
    rq->maxBucket = 0;
}

/*!
 * \internal
 * \brief Commits the queue by rendering its contents.
 *
 * \param rq            RenderQueue
 * \param ctx           RenderContext object
 */
static void m3gCommit(RenderQueue *rq, RenderContext *ctx)
{
    M3Gint b;

    for (b = rq->minBucket; b <= rq->maxBucket; ++b) {
        if (rq->buckets[b]) {
            PointerArray *items = &rq->buckets[b]->items;
            int n = m3gArraySize(items);
            int i;
            for (i = 0; i < n; ++i) {
                RenderItem *item = (RenderItem*) m3gGetArrayElement(items, i);
                M3G_VFUNC(Node, item->node, doRender)(
                    item->node, ctx, &item->toCamera, item->subMeshIndex);
                m3gRecycleRenderItem(rq, item);
            }
            m3gClearArray(items);
            m3gIncStat(M3G_INTERFACE(ctx), M3G_STAT_RENDER_NODES_DRAWN, n);
        }
    }
}