/*

* 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);

        }

    }

}