magiccube4d/magiccube4d-src-2_2/Polymgr.cpp

/* -*- c++ -*-
FILE: Polymgr.cpp
RCS REVISION: $Revision: 1.23 $

COPYRIGHT: (c) 1999 -- 2003 Melinda Green, Don Hatch, and Jay Berkenbilt - Superliminal Software

LICENSE: Free to use and modify for non-commercial purposes as long as the
    following conditions are adhered to:
    1) Obvious credit for the source of this code and the designs it embodies
       are clearly made, and
    2) Ports and derived versions of 4D Magic Cube programs are not distributed
       without the express written permission of the authors.

DESCRIPTION:
    Implementation of the PolygonManager4D class
*/

#include "MagicCube.h"
#include "Polymgr.h"
#include "Math4d.h"
#include "Preferences.h"
#include <stdio.h>

static int  length = LENGTH;
// FIX THIS-- need consistent initializion method
static real tilt = DTOR(TILT), twirl = DTOR(TWIRL);


static real bbox[2][2] = { {0} };

static      real
sine_interp(real x)
{
    return (sin((x - .5) * PI) + 1) / 2;
}

#define are_CCW(v0,v1,v2) (twice_triangle_area(v0,v1,v2) > 0)
#define are_CW(v0,v1,v2) (twice_triangle_area(v0,v1,v2) < 0)
/* HA! the following are reversed from the above, since we inverted Y */
#define ushort_are_CCW(v0,v1,v2) (ushort_twice_triangle_area(v0,v1,v2) < 0)
#define ushort_are_CW(v0,v1,v2) (ushort_twice_triangle_area(v0,v1,v2) > 0)
static      real
twice_triangle_area(real v0[2], real v1[2], real v2[2])
{
    real        edge1[2], edge2[2];
    VMV2(edge1, v1, v0);
    VMV2(edge2, v2, v0);
    return VXV2(edge1, edge2);
}
static long
ushort_twice_triangle_area(unsigned short v0[2],
                           unsigned short v1[2], unsigned short v2[2])
{
    int         edge1[2], edge2[2];
    VMV2(edge1, v1, v0);
    VMV2(edge2, v2, v0);
    return VXV2(edge1, edge2);
}


static void
get_triangle_normal(real v0[2], real v1[2], real v2[2], real nrml[3])
{
    real        edge1[3], edge2[3], tomultiplyby;
    VMV3(edge1, v1, v0);
    VMV3(edge2, v2, v0);
    VXV3(nrml, edge1, edge2);
    /* normalize */
    tomultiplyby = 1 / sqrt(NORMSQRD3(nrml));
    VXS3(nrml, nrml, tomultiplyby);
}


static void
getrotmat(int ax, real angle, real mat3[3][3])
{
    real        c = cos(angle), s = sin(angle);
    int         fromax = (ax + 1) % 3, toax = (ax + 2) % 3;

    ZEROMAT3(mat3);
    mat3[ax][ax] = 1;
    mat3[fromax][fromax] = c;
    mat3[fromax][toax] = s;
    mat3[toax][fromax] = -s;
    mat3[toax][(ax + 2) % 3] = c;
}
/*
 * Comparison function for qsort
 */
static int
zcmp(const void *a, const void *b)
{
    const real **A = (const real **)a;
    const real **B = (const real **)b;
    return **A < **B ? -1 : **A > **B ? 1 : 0;
}


PolygonManager4D::PolygonManager4D(Preferences& prefs) :
    preferences(prefs)
{
    tilt = DTOR(prefs.getRealProperty(M4D_TILT, TILT));
    twirl = DTOR(prefs.getRealProperty(M4D_TWIRL, TWIRL));
    faceshrink = prefs.getRealProperty(M4D_FACESHRINK, FACESHRINK);
    stickershrink = prefs.getRealProperty(M4D_STICKERSHRINK, STICKERSHRINK);
    nframes_90 = prefs.getIntProperty(M4D_NFRAMES_90, NFRAMES_90);
    nframes_120 = prefs.getIntProperty(M4D_NFRAMES_120, NFRAMES_120);
    nframes_180 = prefs.getIntProperty(M4D_NFRAMES_180, NFRAMES_180);

    reset(prefs.getLength());
}

void PolygonManager4D::reset(int new_length)
{
    if (new_length != -1)
    {
        length = new_length;

        bbox[0][0] = 0;
        n_untwisted_verts4 = getUntwistedVerts4(untwisted_verts4, faceshrink, stickershrink);

        calc3DFrameInfo(
            (struct stickerspec *)NULL,
            CCW,
            0, /* slicesmask-- so everything else is ignored */
            0.,
            sine_interp,
            n_untwisted_verts4,
            untwisted_verts4,
            preferences.getRealProperty(M4D_EYEW, EYEW),
            !preferences.getBoolProperty(M4D_NOCULLCELLS), /* cullcells */
            &n_untwisted_verts3,
            untwisted_verts3,
            &n_untwisted_quads3,
            untwisted_quads3,
            untwisted_stickerids3,
            NULL);
    }
}

void PolygonManager4D::setShrinkers(real face_val, real sticker_val)
{
    faceshrink = face_val;
    stickershrink = sticker_val;
    n_untwisted_verts4 =
        getUntwistedVerts4(untwisted_verts4,
                                     faceshrink, stickershrink);
}

void PolygonManager4D::calc3DTo2DFrameInfo(
    /* INPUTS */
    int nverts3, real verts3[][3], int nquads3,
    int quads3[][4], int stickerids3[], real tilt,
    real twirl, real eyez, real sunvec[3],
    int sunvec_is_in_objspace, int cullverts,
    int cullbackfaces, int zsort,
    /* OUTPUTS */
    int *Nverts2, real verts2[][2], int *Nquads2,
    int quads2[][4], int quadids2[],
    real brightnesses[])
{
    int         i;
    real        twirlmat[3][3], tiltmat[3][3], viewingmat[3][3];
    real        objspace_sunvec[3], triangle_normal[3];
    real        tomultiplyby, norm;
    int         nverts2, nquads2;   /* set *Nverts2 and *Nquads2 to these at
                                       end */
    real        transformed_verts3[MAXVERTS][3];


    /*
     * make a viewing matrix that tilts and twirls
     */
    getrotmat(Y, twirl, twirlmat);
    getrotmat(X, tilt, tiltmat);
    MXM3(viewingmat, twirlmat, tiltmat);

    /*
     * get normalized sunvec in object space
     * (it's more efficient to transform the light vector to object space
     * than to transform all the face normals to world space)
     */
    if (sunvec && brightnesses)
    {
        if (sunvec_is_in_objspace)
            SET3(objspace_sunvec, sunvec);
        else                    /* apply inverse of viewingmat to sunvec to
                                   get objspace_sunvec */
            MXV3(objspace_sunvec, viewingmat, sunvec);
        norm = sqrt(NORMSQRD3(objspace_sunvec));
        VDS3(objspace_sunvec, objspace_sunvec, norm);
    }

    /*
     * transform verts
     */
    for (i = 0; i < nverts3; ++i)
    {
        VXM3(transformed_verts3[i], verts3[i], viewingmat);
        tomultiplyby = 1. / (eyez - transformed_verts3[i][Z]);
        VXS2(verts2[i], transformed_verts3[i], tomultiplyby);
    }

    /*
     * Copy quads3 to quads2
     * and stickerids3 to quadids2,
     * discarding back faces
     */
    nquads2 = 0;
    for (i = 0; i < nquads3; ++i)
    {
        if (cullbackfaces && !are_CCW(verts2[quads3[i][0]],
                                      verts2[quads3[i][1]],
                                      verts2[quads3[i][2]]))
        {
            continue;
        }
        SET4(quads2[nquads2], quads3[i]);
        quadids2[nquads2] = (stickerids3[quads3[i][0] / 8]) * 6 + (i % 6);
        if (sunvec && brightnesses)
        {
            get_triangle_normal(verts3[quads3[i][0]],
                                verts3[quads3[i][1]],
                                verts3[quads3[i][2]], triangle_normal);
            brightnesses[nquads2] = DOT3(triangle_normal, objspace_sunvec);
            if (brightnesses[nquads2] < 0)
                brightnesses[nquads2] = 0;
        }
        nquads2++;
    }

    nverts2 = nverts3;

    /*
     * Zsort the quads, quadids and brighnesses, from least to greatest z
     */
    if (zsort)
    {
        real        quadzs[MAXQUADS];
        real       *qsortbuf[MAXQUADS];
        int         tempquads[MAXQUADS][4];
        int         tempquadids[MAXQUADS];
        real        tempbrightnesses[MAXQUADS];
        for (i = 0; i < nquads2; ++i)
        {
            quadzs[i] = transformed_verts3[quads2[i][0]][Z]
                + transformed_verts3[quads2[i][2]][Z];
            qsortbuf[i] = &quadzs[i];
        }
        qsort((char *)qsortbuf, nquads2, sizeof(*qsortbuf), zcmp);
        for (i = 0; i < nquads2; ++i)
        {
            SET4(tempquads[i], quads2[qsortbuf[i] - quadzs]);
            tempquadids[i] = quadids2[qsortbuf[i] - quadzs];
            tempbrightnesses[i] = brightnesses[qsortbuf[i] - quadzs];
        }
        for (i = 0; i < nquads2; ++i)
        {
            SET4(quads2[i], tempquads[i]);
            quadids2[i] = tempquadids[i];
            brightnesses[i] = tempbrightnesses[i];
        }
    }

    if (cullverts)
    {
        /*
         * FIX THIS-- should discard unused vertices here if we are
         * planning to store the frame in a file or something.
         */
    }


    *Nverts2 = nverts2;
    *Nquads2 = nquads2;
}


real PolygonManager4D::getTwistTotalAngle(int dim, int dir)
{
    switch (dim)
    {
    case 0:                 /* vertex; 120 degrees */
        return 2 * PI / 3 * dir;
        break;
    case 1:                 /* edge; 180 degrees */
        return 2 * PI / 2 * dir;
        break;
    case 2:                 /* face; 90 degrees */
        return 2 * PI / 4 * dir;
        break;
    default:
        assert(INRANGE(0 <=, dim, <2));
        break;
    }
    return 2 * PI;              /* this never happens */
}

int PolygonManager4D::getTwistNFrames(struct stickerspec *grip)
{
    switch (grip->dim)
    {
    case 0:                 /* vertex; 120 degrees */
        return nframes_120;
        break;
    case 1:                 /* edge; 180 degrees */
        return nframes_180;
        break;
    case 2:                 /* face; 90 degrees */
        return nframes_90;
        break;
    default:
        assert(INRANGE(0 <=, grip->dim, <2));
        break;
    }
    return nframes_90;          /* this never happens */
}


/*
 * This procedure is hopelessly confusing, but it works.
 * Note there are two functions here that are almost identical.
 */
int PolygonManager4D::makeRangesReal(int slicesmask, int,    // whichaxis,
                int sgn, real ranges[MAXLENGTH][2])
{
    int         i, nranges;
    real        temp;

    nranges = 0;
    for (i = 0; i < length; ++i)
    {
        if (BIT(&slicesmask, i))
        {
            if (i == 0 || !BIT(&slicesmask, i - 1))
                ranges[nranges++][0] = (length - 2 * i) * faceshrink;
            ranges[nranges - 1][1] = (length - 2 * (i + 1)) * faceshrink;
        }
    }
    if (BIT(&slicesmask, 0))
        ranges[0][0] += 2 * length; /* bigger than any vertex */
    if (BIT(&slicesmask, length - 1))
        ranges[nranges - 1][1] -= 2 * length;   /* smaller than any vertex */

    if (sgn > 0)                /* then the ranges are right but in the wrong
                                   order */
        for (i = 0; i < nranges; ++i)
        {
            SWAP(ranges[i][0], ranges[nranges - 1 - i][1], temp);
        }
    else                        /* the signs of the ranges are wrong */
        for (i = 0; i < nranges; ++i)
            VXS2(ranges[i], ranges[i], -1);

    return nranges;
}

int PolygonManager4D::makeRangesInt(int slicesmask, int, // whichaxis,
               int sgn, int ranges[MAXLENGTH][2])
{
    int         i, nranges;
    int         temp;

    nranges = 0;
    for (i = 0; i < length; ++i)
    {
        if (BIT(&slicesmask, i))
        {
#if sgi
            /* work around N32 compiler optimizer problem */
            if (length < 0)
                printf("foo\n");
#endif
            if (i == 0 || !BIT(&slicesmask, i - 1))
                ranges[nranges++][0] = (length - 2 * i);
            ranges[nranges - 1][1] = (length - 2 * (i + 1));
        }
    }
    if (BIT(&slicesmask, 0))
        ranges[0][0] += 2 * length; /* bigger than any vertex */
    if (BIT(&slicesmask, length - 1))
        ranges[nranges - 1][1] -= 2 * length;   /* smaller than any vertex */

    if (sgn > 0)                /* then the ranges are right but in the wrong
                                   order */
        for (i = 0; i < nranges; ++i)
        {
            SWAP(ranges[i][0], ranges[nranges - 1 - i][1], temp);
        }
    else                        /* the signs of the ranges are wrong */
        for (i = 0; i < nranges; ++i)
            VXS2(ranges[i], ranges[i], -1);

    return nranges;
}

/*
 * The following is pretty arbitrary... there might be a more natural way.
 */
/* the iris doesn't seem to like the following being chars */
int         facetoaxis[8] = { W, Z, Y, X, X, Y, Z, W };
int         facetosign[8] = { -1, -1, -1, -1, 1, 1, 1, 1 };
int         axis_and_sign_to_face[4][2] = { {3, 4}, {2, 5}, {1, 6}, {0, 7} };

#define FACETOAXIS(f)   facetoaxis[f]
#define FACETOSIGN(f)   facetosign[f]
#define AXIS_AND_SIGN_TO_FACE(a,s) axis_and_sign_to_face[a][((s)+1)/2]

int PolygonManager4D::oppositeFace(int f)
{
    return NFACES - 1 - f;
}

int PolygonManager4D::faceOfGrip(int id)
{
    struct stickerspec grip;
    grip.id_within_cube = id;
    PolygonManager4D::fillStickerspecFromIdAndLength(&grip, 3);
    return grip.face;
}

void PolygonManager4D::fillStickerspecFromIdAndLength(struct stickerspec *sticker,
                                            int length)
{
    int         i, ax, sgn, id, face0coords[4], mat[4][4];
    sticker->id_within_face =
        sticker->id_within_cube % intpow(length, NDIMS - 1);
    sticker->face = sticker->id_within_cube / intpow(length, NDIMS - 1);
    ax = FACETOAXIS(sticker->face);
    sgn = FACETOSIGN(sticker->face);
    Math4d::getCanonicalMatThatTakesAxisToMinusW(ax, sgn, mat);
    TRANSPOSE4i(mat, mat);      /* want to go in the opposite direction */
    id = sticker->id_within_face;
    face0coords[X] = -(length - 1) + 2 * (id % length);
    face0coords[Y] = -(length - 1) + 2 * ((id / length) % length);

    face0coords[Z] = -(length - 1) + 2 * ((id / length / length) % length);
    face0coords[W] = -length;
    VXM4(sticker->coords, face0coords, mat);
    assert(sticker->coords[ax] == sgn * length);

    /* sticker->depth = 0; */
    sticker->dim = NDIMS - 1;
    for (i = 0; i < NDIMS; ++i)
    {
        if (ABS(sticker->coords[i]) == length - 1)
            sticker->dim--;
        /* sticker->depth = MAX(sticker->depth,
           length-1-ABS(sticker->coords[i])); */
    }
}

void PolygonManager4D::fillStickerspecFromId(struct stickerspec *sticker)
{
    fillStickerspecFromIdAndLength(sticker, length);
}

void PolygonManager4D::fillStickerspecFromFaceAndIdAndLength(struct stickerspec
                                                     *sticker, int length)
{
    int         face = sticker->face;
    int         id_within_face = sticker->id_within_face;
    sticker->id_within_cube =
        face * length * length * length + id_within_face;
    fillStickerspecFromIdAndLength(sticker, length);
    assert(sticker->face == face);
    assert(sticker->id_within_face == id_within_face);
}

void PolygonManager4D::fillStickerspecFromFaceAndId(struct stickerspec *sticker)
{
    fillStickerspecFromFaceAndIdAndLength(sticker, length);
}

void PolygonManager4D::fillStickerspecFromCoordsAndLength(struct stickerspec *sticker,
                                                int length)
{
    int         i, ax = 0, sgn, mat[4][4], newcoords[4];

    sticker->dim = NDIMS - 1;
    /* sticker->depth = 0; */
    for (i = 0; i < NDIMS; ++i)
    {
        if (ABS(sticker->coords[i]) == length)
            ax = i;
        else if (ABS(sticker->coords[i]) == length - 1)
            sticker->dim--;
        /* sticker->depth = MAX(sticker->depth,
           length-1-ABS(sticker->coords[i])); */
    }
    assert(INRANGE(X <=, ax, <=W));
    sgn = SGN(sticker->coords[ax]);
    sticker->face = AXIS_AND_SIGN_TO_FACE(ax, sgn);
    Math4d::getCanonicalMatThatTakesAxisToMinusW(ax, sgn, mat);
    VXM4(newcoords, sticker->coords, mat);
    assert(newcoords[W] == -length);

    sticker->id_within_face = 0;
    for (i = NDIMS - 2; i >= 0; --i)
    {
        sticker->id_within_face *= length;
        sticker->id_within_face += (newcoords[i] + length - 1) / 2;
    }
    assert(INRANGE
           (0 <=, sticker->id_within_face, <intpow(length, NDIMS - 1)));
    sticker->id_within_cube =
        sticker->face * intpow(length, NDIMS - 1) + sticker->id_within_face;
}

void PolygonManager4D::fillStickerspecFromCoords(struct stickerspec *sticker)
{
    fillStickerspecFromCoordsAndLength(sticker, length);
}


/*
 * Get a sticker for which a CCW twist is the same transformation
 * as the given face-to-center rotation.
 * returns 1 if legal rot, 0 otherwise.
 */
int PolygonManager4D::facetocenterToGrip(int facetocenter, struct stickerspec *sticker)
{
    int         ax = FACETOAXIS(facetocenter);
    int         sgn = FACETOSIGN(facetocenter);
    if (!INRANGE(X <=, ax, <=Z))
        return 0;

    sticker->coords[ax] = 0;
    sticker->coords[(ax + 1) % 3] = 3;  /* axis of face on which sticker lies
                                         */
    sticker->coords[(ax + 2) % 3] = sgn * -(3 - 1); /* it's magic */
    sticker->coords[W] = 0;

    fillStickerspecFromCoordsAndLength(sticker, 3);

    return 1;
}

void PolygonManager4D::calc2DFrameInfo(
    /* INPUTS */
    struct stickerspec *sticker, int dir,
    int slicesmask, real frac, real(*interp) (real),
    int nverts4, real untwisted_verts4[][4],
    real eyew, int cullcells, real tilt, real twirl,
    real eyez, real sunvec[3],
    int sunvec_is_in_objspace, int cullverts,
    int cullbackfaces, int zsort,
    /* OUTPUTS */
    int *Nverts2, real verts2[][2], int *Nquads2,
    int quads2[][4], int quadids[],
    real brightnesses[])  /* brightnesses not
                             calculated if NULL */
{
    int         nverts3, nquads3;
    real        verts3[MAXVERTS][3];
    int         quads3[MAXQUADS][4];
    int         stickerids3[MAXSTICKERS];

    if (slicesmask)
        calc3DFrameInfo(sticker, dir, slicesmask, frac, interp,
            nverts4, untwisted_verts4, eyew, cullcells,
            &nverts3, verts3, &nquads3, quads3,
            stickerids3, NULL);
    else
    {
        int         i;
        /* FIX THIS-- this copying shouldn't be necessary */
        nverts3 = n_untwisted_verts3;
        for (i = 0; i < nverts3; ++i)
            SET3(verts3[i], untwisted_verts3[i]);
        for (i = 0; i < nverts3 / 8; ++i)
            stickerids3[i] = untwisted_stickerids3[i];
        nquads3 = n_untwisted_quads3;
        for (i = 0; i < nquads3; ++i)
            SET4(quads3[i], untwisted_quads3[i]);
    }

    calc3DTo2DFrameInfo(nverts3, verts3, nquads3, quads3, stickerids3,
        tilt, twirl, eyez,
        sunvec, sunvec_is_in_objspace,
        cullverts, cullbackfaces, zsort,
        Nverts2, verts2, Nquads2, quads2, quadids,
        brightnesses);
}

/*
 * "grip" is equal to the sticker id
 * if length=3; otherwise
 * it's equal to the stickerid on the 3x3x3x3 puzzle
 * that corresponds to the twist.
 * returns 1 if landed on a sticker, 0 otherwise.
 * NOTE: this is mostly the same as pick().
 */
int PolygonManager4D::pickGrip(int x, int y,
        struct frame *frame, struct stickerspec *sticker)
{
    int checking_bbox = !preferences.getBoolProperty(M4D_DONT_CHECK_BBOX);
    unsigned short (*verts)[2] = frame->verts;
    unsigned short (*quads)[4] = frame->quads;
    int         i, j;
    unsigned short thispoint[2];
    thispoint[0] = x;
    thispoint[1] = y;

    for (i = frame->nquads - 1; i >= 0; --i)
    {

        if (checking_bbox)
        {
            for (j = 0; j < 4; ++j)
                if (x <= verts[quads[i][j]][0])
                    break;
            if (j == 4)
                continue;

            for (j = 0; j < 4; ++j)
                if (x >= verts[quads[i][j]][0])
                    break;
            if (j == 4)
                continue;

            for (j = 0; j < 4; ++j)
                if (y <= verts[quads[i][j]][1])
                    break;
            if (j == 4)
                continue;

            for (j = 0; j < 4; ++j)
                if (y >= verts[quads[i][j]][1])
                    break;
            if (j == 4)
                continue;
        }


        for (j = 0; j < 4; ++j)
            if (!ushort_are_CCW(verts[quads[i][j]],
                                verts[quads[i][(j + 1) % 4]], thispoint))
                break;
        if (j == 4)
        {                       /* they were all CCW, so we hit a quad */

            sticker->id_within_cube = frame->quadids[i] / 6;
            fillStickerspecFromId(sticker);

            if (length == 2)
            {
                int ax, sgn, face0coords[4], M[4][4];
                ax = frame->quadids[i] % 3;
                sgn = (frame->quadids[i] % 6) < 3 ? -1 : 1;

                /* invent a nonexistent sticker at the appropriate axis */
                face0coords[ax] = sgn * (length - 1);
                face0coords[(ax + 1) % 3] = 0;
                face0coords[(ax + 2) % 3] = 0;
                face0coords[3] = -length;
                Math4d::getCanonicalMatThatTakesAxisToMinusW(
                    FACETOAXIS(sticker->face), FACETOSIGN(sticker->face), M);
                /* apply inv of that matrix to face0coords */
                MXV4(sticker->coords, M, face0coords);
                sticker->dim = 2;
            }

            /*
             * Now we know the coordinates of the sticker.
             * "Straighten it out" to the coords of the appropriate grip.
             * I.e. change everything < length-1 to 0,
             * change length-1 to 2 and change length to 3.
             */
            for(j=0; j<4; ++j)
            {
                if (ABS(sticker->coords[j]) < length - 1)
                    sticker->coords[j] = 0;
                else
                    sticker->coords[j] = SGN(sticker->coords[j]) *
                        (ABS(sticker->coords[j]) - length + 3);
            }
            fillStickerspecFromCoordsAndLength(sticker, 3);

            return 1;
        }
    }
    return 0;
}

int PolygonManager4D::pick(int x, int y, struct frame *frame, struct stickerspec *sticker)
{
    int checking_bbox = !preferences.getBoolProperty(M4D_DONT_CHECK_BBOX);
    unsigned short (*verts)[2] = frame->verts;
    unsigned short (*quads)[4] = frame->quads;
    int i, j;
    unsigned short thispoint[2];
    thispoint[0] = x;
    thispoint[1] = y;

    for (i = frame->nquads - 1; i >= 0; --i)
    {

        if (checking_bbox)
        {
            for (j = 0; j < 4; ++j)
                if (x <= verts[quads[i][j]][0])
                    break;
            if (j == 4)
                continue;

            for (j = 0; j < 4; ++j)
                if (x >= verts[quads[i][j]][0])
                    break;
            if (j == 4)
                continue;

            for (j = 0; j < 4; ++j)
                if (y <= verts[quads[i][j]][1])
                    break;
            if (j == 4)
                continue;

            for (j = 0; j < 4; ++j)
                if (y >= verts[quads[i][j]][1])
                    break;
            if (j == 4)
                continue;
        }


        for (j = 0; j < 4; ++j)
            if (!ushort_are_CCW(verts[quads[i][j]],
                                verts[quads[i][(j + 1) % 4]], thispoint))
                break;
        if (j == 4)
        {                       /* they were all CCW, so we hit a quad */

            sticker->id_within_cube = frame->quadids[i] / 6;
            fillStickerspecFromId(sticker);

            return 1;
        }
    }
    return 0;
}

void PolygonManager4D::getUntwistedFrame(struct frame *frame)
{
    struct stickerspec sticker;
    sticker.id_within_cube = 0;
    fillStickerspecFromId(&sticker);
    getFrame(&sticker, CCW, 0, 0, 1, frame);
}

void  PolygonManager4D::getFrame(struct stickerspec *sticker,
                  int dir, int slicesmask, int seqno, int outof,
                  struct frame *frame)
{
    /*
     * The frame calculation routines use different types from the
     * struct frame, so we must translate
     */
    int         nverts, nquads;
    real        verts[MAXVERTS][2];
    int         quads[MAXQUADS][4];
    int         quadids[MAXQUADS];
    real        brightnesses[MAXQUADS];
    int         i;
    static real sunvec[3] = { .82, 1.55, 3.3 }; /* FIX THIS--- figure out where
                                               to put it */

    calc2DFrameInfo(sticker, dir, slicesmask, (real) seqno / outof,
                    sine_interp,
                    n_untwisted_verts4, untwisted_verts4,
                    preferences.getRealProperty(M4D_EYEW, EYEW),
                    !preferences.getBoolProperty(M4D_NOCULLCELLS), /* cullcells */
                    tilt,
                    twirl,
                    preferences.getRealProperty(M4D_EYEZ, EYEZ),
                    sunvec, 0, /* sunvec_is_in_objspace */
                    preferences.getBoolProperty(M4D_CULLVERTS), /* cullverts */
                    !preferences.getBoolProperty(M4D_NOCULLFACES), /* cullbackfaces */
                    !preferences.getBoolProperty(M4D_NOZSORT), /* zsort */
                    &nverts, verts, &nquads, quads,
                    quadids, brightnesses);

    frame->nverts = nverts;
    if (!bbox[0][0])
    {
        /*
         * It is assumed that the first time this function is called,
         * it is with the untwisted frame.  The bounding box
         * of this frame is the one that will always be used.
         */
        real        ctr[2], rad;
        ZEROMAT2(bbox);
        for (i = 0; i < nverts; ++i)
        {
            bbox[0][0] = MIN(bbox[0][0], verts[i][0]);
            bbox[0][1] = MIN(bbox[0][1], verts[i][1]);
            bbox[1][0] = MAX(bbox[1][0], verts[i][0]);
            bbox[1][1] = MAX(bbox[1][1], verts[i][1]);
        }
        LERP2(ctr, bbox[0], bbox[1], .5);
        rad = MAX(bbox[1][0] - ctr[0], bbox[1][1] - ctr[1]);
        /* make bbox a square twice or so as big as it was */
        bbox[0][0] = ctr[0] - 1.2 * rad;
        bbox[0][1] = ctr[1] - 1.2 * rad;
        bbox[1][0] = ctr[0] + 1.2 * rad;
        bbox[1][1] = ctr[1] + 1.2 * rad;
    }
    for (i = 0; i < nverts; ++i)
    {
        frame->verts[i][0] =
            (unsigned short)((verts[i][0] - bbox[0][0]) /
                             (bbox[1][0] - bbox[0][0]) * ((1 << 16) - 1));
        frame->verts[i][1] =
            (unsigned short)((bbox[1][1] - verts[i][1]) /
                             (bbox[1][1] - bbox[0][1]) * ((1 << 16) - 1));
    }
    frame->nquads = nquads;
    for (i = 0; i < nquads; ++i)
    {
        SET4(frame->quads[i], quads[i]);
        frame->quadids[i] = quadids[i];
        frame->brightnesses[i] = brightnesses[i];
    }
}


void PolygonManager4D::calc3DFrameInfo(
    /* INPUTS */
    struct stickerspec *grip, int dir,
    int slicesmask, real frac, real(*interp) (real),
    int nverts4, real uv4[][4], real eyew,
    int cullcells,
    /* OUTPUTS */
    int *Nverts3, real verts3[][3],
    int *Nquads3, int quads3[][4],
    int stickerids3[], int stickers_inverted[])
{
    int         i, j, k;
    int         whichax = 0, sgn;
    real        total_angle;
    real        center[4], real_stickercoords[4], mat[4][4];
    int         nranges = 0;
    real        ranges[MAXLENGTH][2];
    real        toverts4[MAXVERTS][4];
    int         nverts3, nquads3;
    real        tomultiplyby, orientationmat[3][3];
    /*
     * NOTE: Don't change the order here.
     * the miserable little hack in polymgr_pick_grip
     * depends on the assumption that cubequads[i] is on axis i%3
     * in direction (i<3 ? -1 : 1).
     */
    static int  cubequads[6][4] = {
        {0, 4, 6, 2},
        {0, 1, 5, 4},
        {0, 2, 3, 1},
        {7, 5, 1, 3},
        {7, 3, 2, 6},
        {7, 6, 4, 5},
    };

    if (0 == nverts4 || NULL == uv4)
    {
        nverts4 = n_untwisted_verts4;
        uv4 = untwisted_verts4;
    }


    if (slicesmask)
    {
        /*
         * Calculate rotation center; it's the center of the face containing
         * the grip
         */
        whichax = -1;
        for (i = 0; i < NDIMS; ++i)
        {
            if (ABS(grip->coords[i]) == 3)
            {
                center[i] = grip->coords[i];
                whichax = i;
            }
            else
                center[i] = 0;
        }
        assert(INRANGE(0 <=, whichax, <NDIMS));

        total_angle = getTwistTotalAngle(grip->dim, dir);
        SET4(real_stickercoords, grip->coords);

        Math4d::get4dRotMatrix(center, real_stickercoords,
                               interp(frac) * total_angle, mat);
        sgn = SGN(center[whichax]);
        nranges = makeRangesReal(slicesmask, whichax, sgn, ranges);
    }

    /*
     * Transform the vertices
     */
    nverts3 = 0;
    for (i = 0; i < nverts4; ++i)
    {
        if (i % 8 == 0)
            stickerids3[nverts3 / 8] = i / 8;
        if (slicesmask)
        {
            /*
             * Transform the vertex in 4-space
             */
            for (j = 0; j < nranges; ++j)
            {
                if (INRANGE(ranges[j][0] <=, untwisted_verts4[i][whichax],
                            <=ranges[j][1]))
                {
                    VXM4(toverts4[i], untwisted_verts4[i], mat);
                    break;
                }
            }
            if (j == nranges)
                SET4(toverts4[i], untwisted_verts4[i]);
        }
        else
        {
            SET4(toverts4[i], untwisted_verts4[i]);
        }

        /*
         * W-divide to get 3d coords
         */
        tomultiplyby = 1 / (eyew - toverts4[i][3]);
        VXS3(verts3[nverts3], toverts4[i], tomultiplyby);
        nverts3++;
        if ((cullcells || stickers_inverted) && i % 8 == 4)
        {
            int         is_inverted;
            /* got enough verts to determine whether to cull */
            j = (nverts3 / 8) * 8;  /* round down to start of sticker */
            VMV3(orientationmat[0], verts3[j + 1], verts3[j]);
            VMV3(orientationmat[1], verts3[j + 2], verts3[j]);
            VMV3(orientationmat[2], verts3[j + 4], verts3[j]);
            is_inverted = DET3(orientationmat) <= 0;
            if (stickers_inverted)
                stickers_inverted[i / 8] = is_inverted;
            if (cullcells && is_inverted)
            {
                i = ROUNDUP(i, 8) - 1;  /* skip rest of this sticker's verts */
                nverts3 = j;
            }
        }
    }

    /*
     * Now we have nverts3 and verts3;
     * set quads.
     */
    nquads3 = 0;
    for (i = 0; i < nverts3 / 8; ++i)   // for each sticker
        for (j = 0; j < 6; ++j)
        {                       // for each sticker face
            for (k = 0; k < 4; ++k) // for each face vertex
                quads3[nquads3][k] = 8 * i + cubequads[j][k];
            nquads3++;
        }

    *Nverts3 = nverts3;
    *Nquads3 = nquads3;
}

int PolygonManager4D::getUntwistedVerts4(real verts4[][4],
                             real faceshrink, real stickershrink)
{
    real        sticker_centers_3d[MAXLENGTH][MAXLENGTH][MAXLENGTH][NDIMS - 1];
    real        face0verts[MAXLENGTH][MAXLENGTH][MAXLENGTH][2][2][2][NDIMS];
    int         i, j, k, ii, jj, kk, f;
    int         mat[4][4];
    int         nverts4;

    for (k = 0; k < length; ++k)
        for (j = 0; j < length; ++j)
            for (i = 0; i < length; ++i)
            {
                sticker_centers_3d[i][j][k][X] = -length + 2 * i + 1;
                sticker_centers_3d[i][j][k][Y] = -length + 2 * j + 1;
                sticker_centers_3d[i][j][k][Z] = -length + 2 * k + 1;
                for (kk = 0; kk < 2; ++kk)
                    for (jj = 0; jj < 2; ++jj)
                        for (ii = 0; ii < 2; ++ii)
                        {
                            face0verts[i][j][k][ii][jj][kk][X] =
                                -length + 2 * (i + ii);
                            face0verts[i][j][k][ii][jj][kk][Y] =
                                -length + 2 * (j + jj);
                            face0verts[i][j][k][ii][jj][kk][Z] =
                                -length + 2 * (k + kk);
                            face0verts[i][j][k][ii][jj][kk][W] = -length;

                            LERP3(face0verts[i][j][k][ii][jj][kk],
                                  sticker_centers_3d[i][j][k],
                                  face0verts[i][j][k][ii][jj][kk],
                                  stickershrink);
                            VXS3(face0verts[i][j][k][ii][jj][kk],
                                 face0verts[i][j][k][ii][jj][kk], faceshrink);
                        }
            }

    nverts4 = 0;
    for (f = 0; f < NFACES; ++f)
    {
        Math4d::getCanonicalMatThatTakesAxisToMinusW(
            FACETOAXIS(f), FACETOSIGN(f), mat);
        for (k = 0; k < length; ++k)
            for (j = 0; j < length; ++j)
                for (i = 0; i < length; ++i)
                    for (kk = 0; kk < 2; ++kk)
                        for (jj = 0; jj < 2; ++jj)
                            for (ii = 0; ii < 2; ++ii)
                            {
                                assert(nverts4 < MAXVERTS);
                                /*
                                 * want to take -W to the axis, so we apply the inverse,
                                 * i.e. apply the transpose, i.e. multiply by the matrix on
                                 * the left
                                 */
                                MXV4(verts4[nverts4], mat,
                                     face0verts[i][j][k][ii][jj][kk]);
                                nverts4++;
                            }
    }
    return nverts4;
}


void PolygonManager4D::incTilt(real inc)
{
    tilt += inc;
    /* restrict to range [-pi/2, pi/2] */
    if (tilt > PI / 2)
        tilt = PI / 2;
    if (tilt < -PI / 2)
        tilt = -PI / 2;
    // printf("Tilt = %g degrees\n", RTOD(tilt));
}

void PolygonManager4D::incTwirl(real inc)
{
    twirl += inc;
    // printf("Twirl = %g degrees\n", RTOD(twirl));
}

// Local Variables:
// c-basic-offset: 4
// c-comment-only-line-offset: 0
// c-file-offsets: ((defun-block-intro . +) (block-open . 0) (substatement-open . 0) (statement-cont . +) (statement-case-open . +4) (arglist-intro . +) (arglist-close . +) (inline-open . 0))
// indent-tabs-mode: nil
// End: