/*
 * c3ditem.c --
 *
 *     This file contains code common to all item types, and some routines
 *     invoked by item specific code.
 *
 *-------------------------------------------------------------------------
 */

#include "c3d.h"
#include <assert.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>


struct C3dDrawCallback {
    float fOrder;
    int iOrder;
    void (*xFunc)(C3dItem *, ClientData);
    C3dItem *pItem;
    ClientData clientData;
};

/*
 *---------------------------------------------------------------------------
 *
 * assertOverlayList --
 *
 *     This function is a no-op if NDEBUG is defined. Otherwise it executes
 *     a bunch of assert() statements that attempt to find problems within
 *     the overlay list.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
#ifndef NDEBUG
static void
assertOverlayList(C3dWidget *pCanvas)
{
    C3dOverlayLink *p;
    for (p = pCanvas->pOverlay; p; p = p->pNext) {
        assert(!p->pNext || p == p->pNext->pPrev);
        assert((!p->pPrev && p == pCanvas->pOverlay) || p == p->pPrev->pNext);
        assert(p->pItem->pType->xOverlay);
    }
}
#else
#define assertOverlayList(x)
#endif

/*
 *---------------------------------------------------------------------------
 *
 * C3dCheckCoords --
 *
 *     This function checks an argument passed as the COORDS parameter to a
 *     [$win create] command is valid. This function checks that:
 *
 *         * pCoords is a well-formed list.
 *         * The list length is a non-zero multiple of three.
 *         * The list length is greater to or equal to parameter nMin.
 *         * If it is not negative, the list length is less than or equal
 *           to parameter nMax.
 *
 *     If the test passes, TCL_OK is returned. Otherwise an error message
 *     is written to interp and TCL_ERROR is returned.
 *
 *     If pnCoords is not NULL, then *pnCoords is set to the number of
 *     entries in the list divided by three.
 *
 * Results:
 *     Tcl result.
 *
 * Side effects:
 *     Modifies *pnCoords.
 *
 *---------------------------------------------------------------------------
 */
int
C3dCheckCoords(
    Tcl_Interp *interp,
    Tcl_Obj *pCoords,
    int nMin,
    int nMax,
    int *pnCoords
) {
    Tcl_Size n;
    Tcl_Size nCoords;
    if (Tcl_ListObjLength(interp, pCoords, &n)) {
        return TCL_ERROR;
    }
    if (n == 0 || (n % 3) != 0) {
        const char *zCoords = Tcl_GetString(pCoords);
        Tcl_ResetResult(interp);
        Tcl_AppendResult(interp, "Invalid coordinates list: ", zCoords, 0);
        return TCL_ERROR;
    }
    nCoords = n / 3;
    if (nCoords < nMin) {
        const char *zCoords = Tcl_GetString(pCoords);
        Tcl_ResetResult(interp);
        Tcl_AppendResult(interp, "Insufficient coordinates: ", zCoords, 0);
        return TCL_ERROR;
    }
    if (nMax >= 0 && nCoords > nMax) {
        const char *zCoords = Tcl_GetString(pCoords);
        Tcl_ResetResult(interp);
        Tcl_AppendResult(interp, "Too many coordinates: ", zCoords, 0);
        return TCL_ERROR;
    }
    if (pnCoords) {
        *pnCoords = nCoords;
    }
    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dSetCoords --
 *
 *     Copy the values from the Tcl coordinates list pCoords into the array
 *     of C3dVertex structures pointed to by pItem->aVertex. Also set the
 *     value of pItem->nVertex.
 *
 * Results:
 *     Tcl result. This function returns TCL_ERROR if pCoords contains any
 *     elements that cannot be converted to floating point numbers.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
int
C3dSetCoords(
    Tcl_Interp *interp,
    Tcl_Obj *pCoords,
    int offset,
    C3dItem *pItem
) {
    Tcl_Obj **aElem;
    Tcl_Size nElem;
    Tcl_Size i;
    C3dVertex *aVertex = pItem->aVertex;

    if (Tcl_ListObjGetElements(interp, pCoords, &nElem, &aElem)) {
        return TCL_ERROR;;
    }

    for (i = 0; i < (nElem/3); i++) {
        double x, y, z;
        if( Tcl_GetDoubleFromObj(interp, aElem[3*i], &x) ||
            Tcl_GetDoubleFromObj(interp, aElem[3*i+1], &y) ||
            Tcl_GetDoubleFromObj(interp, aElem[3*i+2], &z)
        ){
            return TCL_ERROR;
        }
        aVertex[i+offset].x = x;
        aVertex[i+offset].y = y;
        aVertex[i+offset].z = z;
    }
    pItem->nVertex = MAX(pItem->nVertex, offset + nElem / 3);

    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * objectToItemType --
 *
 *     Treat the object pObj as a canvas3d item type string (i.e.
 *     "polygon"). Return the corresponding C3dItemType structure, if any.
 *     If no such item type exists, leave an error message in interp and
 *     return NULL.
 *
 * Results:
 *     Pointer to C3dItemType structure corresponding to the type name
 *     stored in argument pObj.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static C3dItemType *
objectToItemType(Tcl_Interp *interp, Tcl_Obj *pObj)
{
    static char const *ItemTypeNames[] = {
        "polygon", "light", "2dline", "2dtext", "text", "line", "point",
        "2dpolygon", 0
    };
    enum types {
        POLYGON, LIGHT, LINE2, TEXT, TEXT2, LINE, POINT,
        POLYGON2
    };
    C3dItemType *pItemType = 0;
    int c;

    /* apObj[0] contains the type of the new item. Use this to locate the
     * C3dItemType structure containing callbacks for that type.
     */
    if (Tcl_GetIndexFromObj(interp, pObj, ItemTypeNames, "type", 0, &c)) {
        return 0;
    }
    switch ((enum types)c) {
        case POLYGON:
            pItemType = C3dPolygon();
            break;
        case LIGHT:
            pItemType = C3dLight();
            break;
        case TEXT:
        case TEXT2:
            pItemType = C3dText();
            break;
        case LINE2:
            pItemType = C3d2dLine();
            break;
        case POLYGON2:
            pItemType = C3d2dPolygon();
            break;
        case LINE:
            pItemType = C3dLine();
            break;
        case POINT:
            pItemType = C3dPoint();
            break;
        default:
            assert(0);
    }

    return pItemType;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dGetCoords --
 *
 *     A set of coordinates-lists, for example to create a polygon item
 *     with multiple faces can be passed to a [pathName create],
 *     [pathName coords] or [::canvas3d::transform] command in two ways.
 *     Either each coordList (a list of numbers) is passed as a seperate
 *     argument or a list of them is passed as a single argument. For
 *     example, the following are equivalent:
 *
 *         pathName create polygon $A $B $C
 *         pathName create polygon [list $A $B $C]
 *
 *     (assuming each of $A, $B and $C are a lists of numbers, with lengths
 *     equal to a multiple of three).
 *
 *     The arguments argc and argv specify the list of arguments starting
 *     with the first argument that may be a coordList. In the above
 *     examples, argc would be 3 and 1, respectively. The number of
 *     elements of argv that are part of the coordList set is returned
 *     (again, 3 and 1 respectively for the above examples).
 *
 *     After returning, *pnCoords is set to the number of coordinate-lists
 *     passed to the command (i.e. the number of faces on the created
 *     polygon). *papCoords points to an array of size *pnCoords containing
 *     the coordinate-lists themselves.
 *
 * Results:
 *     Number of elements of argv[] that specify the coordinate-list set.
 *
 * Side effects:
 *     Modifies *pnCoords and *papCoords.
 *
 *---------------------------------------------------------------------------
 */
int
C3dGetCoords(
    int objc,
    Tcl_Obj **objv,
    int *pnCoords,
    Tcl_Obj ***papCoords
) {
    int n = 1;                 /* Value to return */
    Tcl_Size len;
    const char *z;

    while (
        n < objc &&
        (z = Tcl_GetStringFromObj(objv[n], &len)) &&
        len > 1 &&
        !isalpha((int)z[1])
    ) {
        n++;
    }

    if (n == 1) {
        Tcl_Obj **apElem;
        Tcl_Size nElem;
        if (!Tcl_ListObjGetElements(0, objv[0], &nElem, &apElem)) {
            Tcl_Obj **apElem2;
            Tcl_Size nElem2;
            if (nElem == 0) {
		*pnCoords = 0;
		*papCoords = 0;
		return 0;
	    }
            if (
                !Tcl_ListObjGetElements(0, apElem[0], &nElem2, &apElem2) &&
                nElem2 > 1
            ) {
                *pnCoords = nElem;
                *papCoords = apElem;
                return n;
            }
        }
    }
    *pnCoords = n;
    *papCoords = objv;

    return n;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemCreate --
 *
 *     This function is called to create a new canvas3d item. If
 *     successful, the returned structure is entirely populated except for
 *     the C3dItem.id field. The item has not yet been put into the
 *     C3dWidget.aItemsById hash table (although it may already be linked
 *     into the C3dWidget.aItemsByTag table).
 *
 *     The arguments to this function are interpreted slightly differently,
 *     depending on whether or not pTemplate is NULL.
 *
 *     If the pTemplate argument is NULL, then the new items options are
 *     initialised based on arguments passed as part of the apObj[] array.
 *     Parameter apObj points to an array of object pointers containing the
 *     command line arguments to [.win create], starting with the type
 *     name. i.e.  apObj[0] contains a string like "polygon" or "light".
 *     apObj[1] contains a coordList or 2dCoordList parameter. After one or
 *     more coordList (or 2dCoordList) arguments there may be
 *     initialization options (e.g. "-color" followed by "red").
 *
 *     If pTemplate is not NULL, then it points to a template item. The
 *     type and option values of the new item are copied from the template
 *     item. In this case parameter apObj points to an array of object
 *     pointers containing coordinate-list arguments (either coordList or
 *     2dCoordList parameters, depending on the type of the template item).
 *     No item options ("-color" etc.) may follow the coordList (or
 *     2dCoordList) parameters.
 *
 * Results:
 *     Pointer to new canvas3d item, fully initialised except for the
 *     C3dItem.id field.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
C3dItem *
C3dItemCreate(
    C3dWidget *pCanvas,
    int nObj,
    Tcl_Obj **apObj,
    C3dItem *pTemplate
) {
    Tcl_Interp *interp = pCanvas->interp;
    C3dItem *pItem;               /* New item to return */
    C3dItemType *pItemType;       /* Type of new item */
    Tk_OptionTable table;         /* Options table for new item */
    int rc;
    char *pOptions;
    int nCoords = 1;              /* Number of coordList args in apObj */
    int iCoords = 0;              /* Index of first coordList in apObj */

    /* Obtain the item type pointer, either from the template or type name.
     * Also set iCoords, to 0 if the template exists, 1 otherwise.
     */
    assert(nObj >= 1);
    if (pTemplate) {
        pItemType = pTemplate->pType;
        iCoords = 0;
    } else {
        pItemType = objectToItemType(interp, apObj[0]);
 	if (pItemType == 0) {
	    return 0;
	}
        iCoords = 1;
    }
    assert(pItemType->xCreate || pItemType->xMultiCreate);
    assert(!pItemType->xCreate || !pItemType->xMultiCreate);

    if (pItemType->xMultiCreate) {
        int nArg = 0;
        Tcl_Obj **apArg = 0;
        nCoords = C3dGetCoords(nObj - iCoords, &apObj[iCoords], &nArg, &apArg);
 	if (nCoords <= 0) {
	    return 0;
	}
        pItem = pItemType->xMultiCreate(pCanvas, nArg, apArg);
    } else {
        /* If no xMultiCreate() function is available, call xCreate(). In
         * this case only a single object from the apObj array is permitted
         * to be a coordList.
         */
        pItem = pItemType->xCreate(pCanvas, apObj[iCoords]);
    }

    /* If the coordList parameters were no good, no item is created. An
     * error has already been written into pCanvas->interp. So only procede
     * if pItem is not NULL.
     */
    if (pItem) {
        int nArg;
        Tcl_Obj **apArg;

        pItem->pType = pItemType;
        pItem->pCanvas = pCanvas;

        /* Set options to default values. */
        table = pItemType->xTable(interp);
        pOptions = (char *)pItem;
        rc = Tk_InitOptions(interp, pOptions, table, pCanvas->tkwin);
        assert(rc == TCL_OK);

        if (pTemplate) {
            Tcl_Obj *pList;
            Tcl_Obj **apI; 
            Tcl_Size nI, i;
            char *pT = (char *)pTemplate;

            pList = Tk_GetOptionInfo(interp, pT, table, 0, pCanvas->tkwin);
            Tcl_ListObjGetElements(interp, pList, &nI, &apI);
            nArg = 0;
            apArg = (Tcl_Obj **)C3dAlloc(sizeof(Tcl_Obj *) * nI * 2);
            for (i = 0; i < nI; i++) {
                Tcl_Obj **apJ; 
                Tcl_Size nJ;
                Tcl_ListObjGetElements(interp, apI[i], &nJ, &apJ);
                if (nJ == 5) {
                    apArg[nArg++] = apJ[0];
                    apArg[nArg++] = apJ[4];
                }
            }
        } else {
            /* Configure the widget with any options passed to [create] */
            nArg = nObj - nCoords - iCoords;
            apArg = &apObj[nCoords + iCoords];
        }
        if (rc == TCL_OK) {
            rc = C3dItemConfigure(pCanvas, pItem, nArg, apArg);
            C3dItemConfigureCommit(pItem);
        }
        if (rc != TCL_OK) {
            C3dItemDelete(pItem);
            pItem = 0;
        }
        if (pTemplate) {
            C3dFree((char *)apArg);
        }
    }

    /* If the item is an overlay item, link it into the overlay list. */
    if (pItem && pItemType->xOverlay) {
        C3dOverlayLink *pOverlay = pItemType->xOverlay(pItem);
        assert(pOverlay);
        pOverlay->pItem = pItem;
        assertOverlayList(pItem->pCanvas);
        if (!pCanvas->pOverlay || !pTemplate) {
            assert(!(pTemplate && !pCanvas->pOverlay));
            pOverlay->pPrev = 0;
            pOverlay->pNext = pCanvas->pOverlay;
            if (pOverlay->pNext) {
                pOverlay->pNext->pPrev = pOverlay;
            }
            pCanvas->pOverlay = pOverlay;
        } else {
            C3dOverlayLink *pT = pItemType->xOverlay(pTemplate);
            pOverlay->pNext = pT->pNext;
            if (pOverlay->pNext) {
                pOverlay->pNext->pPrev = pOverlay;
            }
            pOverlay->pPrev = pT;
            pT->pNext = pOverlay;
        }
        assertOverlayList(pItem->pCanvas);
    }

    return pItem;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemDraw --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemDraw(C3dWidget *pCanvas, C3dItem *pItem)
{
    void (*xDraw)(C3dWidget *, C3dItem *) = pItem->pType->xDraw;
    if (xDraw && !pItem->pType->xOverlay && !pItem->hidden) {
        glLoadName(pItem->id);
        xDraw(pCanvas, pItem);
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemGetType --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemGetType(C3dItem *pItem, Tcl_Obj *pOut)
{
    Tcl_SetStringObj(pOut, pItem->pType->zType, -1);
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemConfigure --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
int
C3dItemConfigure(
    C3dWidget *pCanvas,
    C3dItem *pItem,
    int objc,
    Tcl_Obj *const objv[]
) {
    Tcl_Interp *interp = pCanvas->interp;
    Tk_Window win = pCanvas->tkwin;
    int rc;

    Tk_SavedOptions *pS = &pItem->savedOptions;
    char *pOptions = (char *)pItem;
    Tk_OptionTable table = pItem->pType->xTable(interp);

    assert(!(pItem->flags & ITEMFLAG_SAVEDOPTIONS_VALID));
    rc = Tk_SetOptions(interp, pOptions, table, objc, objv, win, pS, 0);
    pItem->flags |= ITEMFLAG_SAVEDOPTIONS_VALID;

    return rc;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemCget --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
int
C3dItemCget(
    C3dWidget *pCanvas,
    C3dItem *pItem,
    Tcl_Obj *pObj
) {
    Tcl_Obj *pRet;
    Tcl_Interp *interp = pCanvas->interp;

    char *pOptions = (char *)pItem;
    Tk_OptionTable table = pItem->pType->xTable(interp);

    pRet = Tk_GetOptionValue(interp, pOptions, table, pObj, pCanvas->tkwin);
    if (!pRet) {
        return TCL_ERROR;
    }
    Tcl_SetObjResult(interp, pRet);
    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemConfigureInfo --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
int C3dItemConfigureInfo(
    C3dWidget *pCanvas,
    C3dItem *pItem,
    Tcl_Obj *pObj
) {
    Tcl_Interp *interp = pCanvas->interp;
    Tcl_Obj *pRet;
    char *pOptions = (char *)pItem;
    Tk_OptionTable table = pItem->pType->xTable(interp);

    pRet = Tk_GetOptionInfo(interp, pOptions, table, pObj, pCanvas->tkwin);
    if (!pRet) {
        return TCL_ERROR;
    }
    Tcl_SetObjResult(interp, pRet);
    return TCL_OK;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemConfigureCommit --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemConfigureCommit(C3dItem *pItem)
{
    if (pItem->flags & ITEMFLAG_SAVEDOPTIONS_VALID) {
        Tk_FreeSavedOptions(&pItem->savedOptions);
        pItem->flags &= ~(ITEMFLAG_SAVEDOPTIONS_VALID
                          | ITEMFLAG_NORMALS_VALID
                          | ITEMFLAG_CACHE_VALID);
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemConfigureRollback --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemConfigureRollback(C3dItem *pItem)
{
    if (pItem->flags & ITEMFLAG_SAVEDOPTIONS_VALID) {
        Tk_RestoreSavedOptions(&pItem->savedOptions);
        pItem->flags &= ~ITEMFLAG_SAVEDOPTIONS_VALID;
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemDelete --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemDelete(C3dItem *pItem)
{
    void (*xDelete)(C3dItem *) = pItem->pType->xDelete;

    Tk_OptionTable table;
    char *pOptions;

    if (pItem->flags & ITEMFLAG_SAVEDOPTIONS_VALID) {
        C3dItemConfigureCommit(pItem);
    }

    /* If this is an overlay item, remove it from the linked list. */
    if (pItem->pType->xOverlay) {
        C3dOverlayLink *pOverlay = pItem->pType->xOverlay(pItem);
        assertOverlayList(pItem->pCanvas);
        if (pOverlay->pPrev) {
            pOverlay->pPrev->pNext = pOverlay->pNext;
        }
        if (pOverlay->pNext) {
            pOverlay->pNext->pPrev = pOverlay->pPrev;
        }
        if (pOverlay == pItem->pCanvas->pOverlay) {
            pItem->pCanvas->pOverlay = pOverlay->pNext;
        }
        assertOverlayList(pItem->pCanvas);
    }

    pOptions = (char *)pItem;
    table = pItem->pType->xTable(pItem->pCanvas->interp);
    Tk_FreeConfigOptions(pOptions, table, pItem->pCanvas->tkwin);

    if (xDelete) {
        xDelete(pItem);
    } else {
        C3dFree((char *)pItem);
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemDepth --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
float
C3dItemDepth(C3dTransform *pTransform, C3dItem *pItem)
{
    float z = -2.0;

    if (!pItem->pType->xOverlay && pItem->pType->xDraw) {
        int i;
        for (i = 0; i < pItem->nVertex; i++) {
            C3dVertex vertex;
            memcpy(&vertex, &pItem->aVertex[i], sizeof(C3dVertex));
            C3dTransformApply(pTransform, &vertex);
            z = MAX(vertex.z, z);
        }
    }

    return z;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemStatistics --
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemStatistics(C3dItem *pItem, C3dStatistics *pStatistics)
{
    if (!pItem->pType->xOverlay && pItem->pType->xDraw) {
        void (*xStatistics)(C3dItem *, C3dStatistics *);
        pStatistics->nVertex += pItem->nVertex;
        xStatistics = pItem->pType->xStatistics;
        if (xStatistics) {
            xStatistics(pItem, pStatistics);
        }
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemCoords --
 *
 *     This function helps to implement the following command:
 *
 *         pathName coords SEARCH
 *
 *     The coordinates for item pItem are written to Tcl object pRet.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemCoords(C3dItem *pItem, Tcl_Obj *pRet)
{
    void (*xCoords)(C3dItem *, Tcl_Obj *);
    xCoords = pItem->pType->xCoords;
    if (xCoords) {
        xCoords(pItem, pRet);
    } else {
        int i;
        int nObj = pItem->nVertex * 3;
        Tcl_Obj **apObj = (Tcl_Obj **)C3dAlloc(sizeof(Tcl_Obj *) * nObj);
        for (i = 0; i < pItem->nVertex; i++) {
            apObj[i*3 + 0] = Tcl_NewDoubleObj(pItem->aVertex[i].x);
            apObj[i*3 + 1] = Tcl_NewDoubleObj(pItem->aVertex[i].y);
            apObj[i*3 + 2] = Tcl_NewDoubleObj(pItem->aVertex[i].z);
        }
        Tcl_ListObjReplace(0, pRet, 0, 0, nObj, apObj);
        C3dFree((char *)apObj);
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemDrawCallback --
 *
 *     This function is designed to be called from within an item xDraw
 *     callback to register a function to be called later in the drawing
 *     process. After all the xDraw functions for all items have been
 *     invoked, the function pointer passed as the second parameter to this
 *     function is invoked with parameters pItem and clientData as
 *     arguments.
 *
 *     If more than one callback is registered during a round of xDraw
 *     callbacks (for example by different items), the fOrder parameter to
 *     this function determines the order in which the callbacks are made.
 *     Callbacks are delivered starting from the lowest (most negative)
 *     value of fOrder.
 *
 *     Callbacks are stored in the following three C3dWidget member
 *     variables:
 *
 *         int nDrawCallbackAlloc;
 *         int nDrawCallback;
 *         C3dDrawCallback *aDrawCallback;
 *
 *     To invoke all currently accumulated callbacks, call function
 *     C3dItemDrawDoCallbacks().
 *
 *     fOrder Convention --
 *
 *     At the moment three types of callbacks are registered with this
 *     system:
 *         * Callbacks to draw transparent 3d items and faces. The fOrder
 *           parameter for these callbacks is always less than zero.
 *         * A callback with fOrder==0.0 is registered if -saveunder is
 *           "3d". This is to save a copy of the scene before the overlay
 *           items are drawn.
 *         * Overlay item draw callbacks. The fOrder parameter is always
 *           positive.
 *
 *     TODO: The latter two categories should use a different mechanism.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     Registers a callback that will be invoked later.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemDrawCallback(
    C3dWidget *pCanvas,
    void (*xFunc)(C3dItem *, ClientData),
    C3dItem *pItem,
    ClientData clientData,
    float fOrder
) {
    if (pCanvas->eSelectMode) {
	/* If the canvas is in Select mode, then we are running the xDraw
	 * callbacks of each item not to actually draw into a color-buffer,
	 * but to see which items intersect a small portion of the viewing
	 * area.
         *
         * In this case the order in which items are drawn doesn't matter, so
	 * we invoke the callback passed to this function immediately,
	 * instead of putting it in the C3dWidget.aDrawCallback array.
         */
        xFunc(pItem, clientData);
    } else {
        int nThis = pCanvas->nDrawCallback;
        if (nThis == pCanvas->nDrawCallbackAlloc) {
            char *a = (char *)pCanvas->aDrawCallback;
            int n = pCanvas->nDrawCallbackAlloc + 1000;
            a = C3dRealloc(a, n * sizeof(C3dDrawCallback));
            pCanvas->nDrawCallbackAlloc = n;
            pCanvas->aDrawCallback = (C3dDrawCallback *)a;
        }

        pCanvas->aDrawCallback[nThis].xFunc = xFunc;
        pCanvas->aDrawCallback[nThis].pItem = pItem;
        pCanvas->aDrawCallback[nThis].clientData = clientData;
        pCanvas->aDrawCallback[nThis].fOrder = fOrder;
        pCanvas->aDrawCallback[nThis].iOrder = nThis;
        pCanvas->nDrawCallback++;
    }
}

/*
 *---------------------------------------------------------------------------
 *
 * cmpCallback --
 *
 *     pLeft and pRight are pointers to C3dDrawCallback structures. Compare
 *     the fOrder fields of each and return less than, equal to or greater
 *     than zero if pLeft->fOrder is less than, equal to or greater than
 *     pRight->fOrder. i.e.
 *
 *         (pLeft->fOrder - pRight->fOrder)
 *
 * Results:
 *     See above.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
static int
cmpCallback(const void *pLeft, const void *pRight)
{
    float l = ((C3dDrawCallback *)pLeft)->fOrder;
    float r = ((C3dDrawCallback *)pRight)->fOrder;
    float f = l - r;

    if (f > 0.0) return 1;
    if (f < 0.0) return -1;

    return
        ((C3dDrawCallback *)pRight)->iOrder -
        ((C3dDrawCallback *)pLeft)->iOrder;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemDrawDoCallbacks --
 *
 *     Invoke all callbacks registered with C3dItemDrawCallback().
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemDrawDoCallbacks(C3dWidget *pCanvas)
{
    int i;
    int nCb = pCanvas->nDrawCallback;
    qsort(pCanvas->aDrawCallback, nCb, sizeof(C3dDrawCallback), cmpCallback);
    for (i = 0; i < nCb; i++) {
        C3dDrawCallback *pCb = &pCanvas->aDrawCallback[i];
        glLoadName(pCb->pItem->id);
        pCb->xFunc(pCb->pItem, pCb->clientData);
    }
    pCanvas->nDrawCallback = 0;
}

/*
 *---------------------------------------------------------------------------
 *
 * C3dItemDrawOverlay --
 *
 *     Draw all the overlay items.
 *
 * Results:
 *     None.
 *
 * Side effects:
 *     None.
 *
 *---------------------------------------------------------------------------
 */
void
C3dItemDrawOverlay(C3dWidget *pCanvas)
{
    C3dOverlayLink *pOverlay;
    glDisable(GL_DEPTH_TEST);
    glDepthMask(GL_FALSE);
    for (pOverlay = pCanvas->pOverlay; pOverlay; pOverlay = pOverlay->pNext) {
        C3dItem *pItem = pOverlay->pItem;
        void (*xDraw)(C3dWidget *, C3dItem *) = pItem->pType->xDraw;
        if (xDraw && !pItem->hidden) {
            glLoadName(pItem->id);
            xDraw(pCanvas, pItem);
        }
    }
    C3dItemDrawDoCallbacks(pCanvas);
    glDepthMask(GL_TRUE);
    glEnable(GL_DEPTH_TEST);
}
