1 /*

     2 * Copyright (c) 2003 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of the License "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: RenderQueue implementation

    15 *

    16 */

    17 

    18 

    19 /*!

    20  * \internal

    21  * \file

    22  * \brief RenderQueue implementation.

    23  *

    24  * Render queue holds

    25  * meshes and sprites that are added to queue in rendering

    26  * setup. After setup, queue is committed and contents are

    27  * rendered. Queue grows dynamically, its initial size is

    28  * defined in m3g_defs.h.

    29  */

    30 

    31 #ifndef M3G_CORE_INCLUDE

    32 #   error included by m3g_core.c; do not compile separately.

    33 #endif

    34 

    35 #include "m3g_array.h"

    36 

    37 /*----------------------------------------------------------------------

    38  * Private data structures

    39  *--------------------------------------------------------------------*/

    40 

    41 /*!

    42  * \internal

    43  * \brief RenderQueue entry object

    44  */

    45 struct RenderItemImpl

    46 {

    47 	Node *node;

    48 	Matrix toCamera;

    49     

    50     M3Gint subMeshIndex;

    51 	M3Guint sortKey;

    52 };

    53 

    54 /*!

    55  * \internal

    56  * \brief Drawable queue

    57  */

    58 struct RenderBucketImpl

    59 {

    60     PointerArray items;

    61 };

    62 

    63 

    64 /* Sanity checking... */

    65 M3G_CT_ASSERT(M3G_RENDERQUEUE_BUCKET_BITS >= M3G_APPEARANCE_HARD_SORT_BITS);

    66 

    67 

    68 /*----------------------------------------------------------------------

    69  * Private functions

    70  *--------------------------------------------------------------------*/

    71 

    72 static M3G_INLINE RenderBucket *m3gGetRenderBucket(RenderQueue *rq,

    73                                                    M3Guint sortKey,

    74                                                    Interface *m3g)

    75 {

    76     int i = (int)(sortKey >> (32 - M3G_RENDERQUEUE_BUCKET_BITS));

    77     RenderBucket *bucket = rq->buckets[i];

    78     

    79     if (!bucket) {

    80         bucket = m3gAllocZ(m3g, sizeof(RenderBucket));

    81         /* array already initialized by zero-allocation; see m3g_array.h */

    82         rq->buckets[i] = bucket;

    83     }

    84 

    85     if (i < rq->minBucket) {

    86         rq->minBucket = i;

    87     }

    88     if (i > rq->maxBucket) {

    89         rq->maxBucket = i;

    90     }

    91     

    92     return bucket;

    93 }

    94 

    95 static void m3gDestroyRenderBucket(RenderBucket *bucket, Interface *m3g)

    96 {

    97     if (bucket) {

    98         int i;

    99         PointerArray *items = &bucket->items;

   100         for (i = 0; i < m3gArraySize(items); ++i) {

   101             m3gFree(m3g, m3gGetArrayElement(items, i));

   102         }

   103         m3gDestroyArray(items, m3g);

   104     }

   105     m3gFree(m3g, bucket);

   106 }

   107 

   108 static RenderItem *m3gGetRenderItem(RenderQueue *rq, Interface *m3g)

   109 {

   110     RenderItem *item = rq->freeItems;

   111     if (!item) {

   112         m3gIncStat(m3g, M3G_STAT_RENDERQUEUE_SIZE, 1);

   113         item = m3gAlloc(m3g, sizeof(RenderItem));

   114     }

   115     else {

   116         M3G_VALIDATE_MEMBLOCK(item);

   117         rq->freeItems = *(RenderItem**)item; /* move to next */

   118     }

   119     return item;

   120 }

   121 

   122 static void m3gRecycleRenderItem(RenderQueue *rq, RenderItem *item)

   123 {

   124     if (item) {

   125         *(RenderItem**)item = rq->freeItems; /* store "next" pointer */

   126         rq->freeItems = item;

   127     }

   128 }

   129 

   130 static M3Gbool m3gInsertRenderItem(RenderBucket *bucket,

   131                                    RenderItem *item,

   132                                    Interface *m3g)

   133 {

   134     PointerArray *items = &bucket->items;

   135     int idx = m3gArraySize(items);

   136     

   137     /* Do a binary search for the sorting key of the item */

   138     {

   139         M3Guint key = item->sortKey;

   140         int low = 0;

   141         int high = idx;

   142         const RenderItem *cmp;

   143 

   144         idx >>= 1;

   145         

   146         while (low < high) {

   147             cmp = (const RenderItem*) m3gGetArrayElement(items, idx);

   148             

   149             if (cmp->sortKey < key) {

   150                 low = idx + 1;

   151             }

   152             else if (cmp->sortKey > key) {

   153                 high = idx;

   154             }

   155             else {

   156                 break;

   157             }            

   158             idx = (low + high) >> 1;

   159         }

   160     }

   161 

   162     /* Now that we know where to insert, insert; out of memory here

   163      * returns < 0 */

   164 

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

   166 }

   167 

   168 

   169 /*----------------------------------------------------------------------

   170  * Internal functions

   171  *--------------------------------------------------------------------*/

   172 

   173 /*!

   174  * \internal

   175  * \brief Creates a new render queue.

   176  *

   177  * \param m3g   M3G interface object

   178  * \return      RenderQueue object

   179  */

   180 static RenderQueue *m3gCreateRenderQueue(Interface *m3g)

   181 {

   182     RenderQueue *rq;

   183     

   184     rq = m3gAllocZ(m3g, (M3Gsizei) sizeof(RenderQueue));

   185     return rq;

   186 }

   187 

   188 /*!

   189  * \internal

   190  * \brief Destroys a render queue and frees

   191  * all allocated memory.

   192  *

   193  * \param m3g   M3G interface object

   194  * \param rq    RenderQueue

   195  */

   196 static void m3gDestroyRenderQueue(Interface *m3g, RenderQueue *rq)

   197 {

   198     if (rq) {

   199         int i;

   200         for (i = 0; i < (1 << M3G_RENDERQUEUE_BUCKET_BITS); ++i) {

   201             RenderBucket *bucket = rq->buckets[i];

   202             m3gDestroyRenderBucket(bucket, m3g);

   203         }

   204         while (rq->freeItems) {

   205             RenderItem *item = rq->freeItems;

   206             rq->freeItems = *(RenderItem**)item;

   207             m3gFree(m3g, item);

   208         }

   209     }

   210     m3gFree(m3g, rq);

   211 }

   212 

   213 /*!

   214  * \internal

   215  * \brief Inserts a mesh to the queue. May allocate

   216  * memory if queue size is exceeded.

   217  *

   218  * \param m3g           M3G interface object

   219  * \param rq            RenderQueue

   220  * \param mesh          Mesh object

   221  * \param subMeshIndex  submesh index inside mesh

   222  * \param sortKey       sorting key

   223  */

   224 static M3Gbool m3gInsertDrawable(Interface *m3g,

   225                                  RenderQueue *rq,

   226                                  Node *node,

   227                                  const Matrix *toCamera,

   228                                  M3Gint subMeshIndex,

   229                                  M3Guint sortKey)

   230 {

   231     RenderItem *item;

   232     RenderBucket *bucket;

   233     

   234     item = m3gGetRenderItem(rq, m3g);

   235     if (!item) {

   236         goto OutOfMemory;

   237     }

   238 

   239     bucket = m3gGetRenderBucket(rq, sortKey, m3g);

   240     if (!bucket) {

   241         goto OutOfMemory;

   242     }

   243 

   244     item->node         = node;

   245     item->toCamera     = *toCamera;

   246     item->subMeshIndex = subMeshIndex;

   247     item->sortKey      = (sortKey << M3G_RENDERQUEUE_BUCKET_BITS);

   248 

   249     M3G_BEGIN_PROFILE(m3g, M3G_PROFILE_SETUP_SORT);

   250     if (!m3gInsertRenderItem(bucket, item, m3g)) {

   251         goto OutOfMemory;

   252     }

   253     M3G_END_PROFILE(m3g, M3G_PROFILE_SETUP_SORT);

   254     return M3G_TRUE;

   255 

   256 OutOfMemory:        

   257     m3gRecycleRenderItem(rq, item);

   258     return M3G_FALSE;

   259 }

   260 

   261 /*!

   262  * \internal

   263  * \brief Clears the queue.

   264  *

   265  * \param rq            RenderQueue

   266  */

   267 static void m3gClearRenderQueue(RenderQueue *rq)

   268 {

   269     rq->root = NULL;

   270     rq->lightManager = NULL;

   271     rq->minBucket = (1 << M3G_RENDERQUEUE_BUCKET_BITS);

   272     rq->maxBucket = 0;

   273 }

   274 

   275 /*!

   276  * \internal

   277  * \brief Commits the queue by rendering its contents.

   278  *

   279  * \param rq            RenderQueue

   280  * \param ctx           RenderContext object

   281  */

   282 static void m3gCommit(RenderQueue *rq, RenderContext *ctx)

   283 {

   284     M3Gint b;

   285 

   286     for (b = rq->minBucket; b <= rq->maxBucket; ++b) {

   287         if (rq->buckets[b]) {

   288             PointerArray *items = &rq->buckets[b]->items;

   289             int n = m3gArraySize(items);

   290             int i;

   291             for (i = 0; i < n; ++i) {

   292                 RenderItem *item = (RenderItem*) m3gGetArrayElement(items, i);

   293                 M3G_VFUNC(Node, item->node, doRender)(

   294                     item->node, ctx, &item->toCamera, item->subMeshIndex);

   295                 m3gRecycleRenderItem(rq, item);

   296             }

   297             m3gClearArray(items);

   298             m3gIncStat(M3G_INTERFACE(ctx), M3G_STAT_RENDER_NODES_DRAWN, n);

   299         }

   300     }

   301 }

   302