cm.java

JAKE2用ＪＡＶＡ写的queck2的３Ｄ游戏开发引擎

            p = box_planes[i * 2 + 1];
            p.type = (byte) (3 + (i >> 1));
            p.signbits = 0;
            Math3D.VectorClear(p.normal);
            p.normal[i >> 1] = -1;
        }
    }

    /** To keep everything totally uniform, bounding boxes are turned into small
     * BSP trees instead of being compared directly. */
    public static int HeadnodeForBox(float[] mins, float[] maxs) {
        box_planes[0].dist = maxs[0];
        box_planes[1].dist = -maxs[0];
        box_planes[2].dist = mins[0];
        box_planes[3].dist = -mins[0];
        box_planes[4].dist = maxs[1];
        box_planes[5].dist = -maxs[1];
        box_planes[6].dist = mins[1];
        box_planes[7].dist = -mins[1];
        box_planes[8].dist = maxs[2];
        box_planes[9].dist = -maxs[2];
        box_planes[10].dist = mins[2];
        box_planes[11].dist = -mins[2];

        return box_headnode;
    }

    /** Recursively searches the leaf number that contains the 3d point. */
    private static int CM_PointLeafnum_r(float[] p, int num) {
        float d;
        cnode_t node;
        cplane_t plane;

        while (num >= 0) {
            node = map_nodes[num];
            plane = node.plane;

            if (plane.type < 3)
                d = p[plane.type] - plane.dist;
            else
                d = Math3D.DotProduct(plane.normal, p) - plane.dist;
            if (d < 0)
                num = node.children[1];
            else
                num = node.children[0];
        }

        Globals.c_pointcontents++; // optimize counter

        return -1 - num;
    }

    /** Searches the leaf number that contains the 3d point. */
    public static int CM_PointLeafnum(float[] p) {
    	// sound may call this without map loaded
        if (numplanes == 0)
            return 0; 
        return CM_PointLeafnum_r(p, 0);
    }


    private static int leaf_count, leaf_maxcount;

    private static int leaf_list[];

    private static float leaf_mins[], leaf_maxs[];

    private static int leaf_topnode;

    /** Recursively fills in a list of all the leafs touched. */    
    private static void CM_BoxLeafnums_r(int nodenum) {
        cplane_t plane;
        cnode_t node;
        int s;

        while (true) {
            if (nodenum < 0) {
                if (leaf_count >= leaf_maxcount) {
                    Com.DPrintf("CM_BoxLeafnums_r: overflow\n");
                    return;
                }
                leaf_list[leaf_count++] = -1 - nodenum;
                return;
            }

            node = map_nodes[nodenum];
            plane = node.plane;

            s = Math3D.BoxOnPlaneSide(leaf_mins, leaf_maxs, plane);

            if (s == 1)
                nodenum = node.children[0];
            else if (s == 2)
                nodenum = node.children[1];
            else {
                // go down both
                if (leaf_topnode == -1)
                    leaf_topnode = nodenum;
                CM_BoxLeafnums_r(node.children[0]);
                nodenum = node.children[1];
            }
        }
    }

    /** Fills in a list of all the leafs touched and starts with the head node. */
    private static int CM_BoxLeafnums_headnode(float[] mins, float[] maxs,
            int list[], int listsize, int headnode, int topnode[]) {
        leaf_list = list;
        leaf_count = 0;
        leaf_maxcount = listsize;
        leaf_mins = mins;
        leaf_maxs = maxs;

        leaf_topnode = -1;

        CM_BoxLeafnums_r(headnode);

        if (topnode != null)
            topnode[0] = leaf_topnode;

        return leaf_count;
    }

    /** Fills in a list of all the leafs touched. */
    public static int CM_BoxLeafnums(float[] mins, float[] maxs, int list[],
            int listsize, int topnode[]) {
        return CM_BoxLeafnums_headnode(mins, maxs, list, listsize,
                map_cmodels[0].headnode, topnode);
    }

    /** Returns a tag that describes the content of the point. */
    public static int PointContents(float[] p, int headnode) {
        int l;

        if (numnodes == 0) // map not loaded
            return 0;

        l = CM_PointLeafnum_r(p, headnode);

        return map_leafs[l].contents;
    }

    /*
     * ================== CM_TransformedPointContents
     * 
     * Handles offseting and rotation of the end points for moving and rotating
     * entities ==================
     */
    public static int TransformedPointContents(float[] p, int headnode,
            float[] origin, float[] angles) {
        float[] p_l = { 0, 0, 0 };
        float[] temp = { 0, 0, 0 };
        float[] forward = { 0, 0, 0 }, right = { 0, 0, 0 }, up = { 0, 0, 0 };
        int l;

        // subtract origin offset
        Math3D.VectorSubtract(p, origin, p_l);

        // rotate start and end into the models frame of reference
        if (headnode != box_headnode
                && (angles[0] != 0 || angles[1] != 0 || angles[2] != 0)) {
            Math3D.AngleVectors(angles, forward, right, up);

            Math3D.VectorCopy(p_l, temp);
            p_l[0] = Math3D.DotProduct(temp, forward);
            p_l[1] = -Math3D.DotProduct(temp, right);
            p_l[2] = Math3D.DotProduct(temp, up);
        }

        l = CM_PointLeafnum_r(p_l, headnode);

        return map_leafs[l].contents;
    }

    /*
     * ===============================================================================
     * 
     * BOX TRACING
     * 
     * ===============================================================================
     */

    // 1/32 epsilon to keep floating point happy
    private static final float DIST_EPSILON = 0.03125f;

    private static float[] trace_start = { 0, 0, 0 }, trace_end = { 0, 0, 0 };

    private static float[] trace_mins = { 0, 0, 0 }, trace_maxs = { 0, 0, 0 };

    private static float[] trace_extents = { 0, 0, 0 };

    private static trace_t trace_trace = new trace_t();

    private static int trace_contents;

    private static boolean trace_ispoint; // optimized case

    /*
     * ================ CM_ClipBoxToBrush ================
     */
    public static void CM_ClipBoxToBrush(float[] mins, float[] maxs,
            float[] p1, float[] p2, trace_t trace, cbrush_t brush) {
        int i, j;
        cplane_t plane, clipplane;
        float dist;
        float enterfrac, leavefrac;
        float[] ofs = { 0, 0, 0 };
        float d1, d2;
        boolean getout, startout;
        float f;
        cbrushside_t side, leadside;

        enterfrac = -1;
        leavefrac = 1;
        clipplane = null;

        if (brush.numsides == 0)
            return;

        Globals.c_brush_traces++;

        getout = false;
        startout = false;
        leadside = null;

        for (i = 0; i < brush.numsides; i++) {
            side = map_brushsides[brush.firstbrushside + i];
            plane = side.plane;

            // FIXME: special case for axial

            if (!trace_ispoint) { // general box case

                // push the plane out apropriately for mins/maxs

                // FIXME: use signbits into 8 way lookup for each mins/maxs
                for (j = 0; j < 3; j++) {
                    if (plane.normal[j] < 0)
                        ofs[j] = maxs[j];
                    else
                        ofs[j] = mins[j];
                }
                dist = Math3D.DotProduct(ofs, plane.normal);
                dist = plane.dist - dist;
            } else { // special point case
                dist = plane.dist;
            }

            d1 = Math3D.DotProduct(p1, plane.normal) - dist;
            d2 = Math3D.DotProduct(p2, plane.normal) - dist;

            if (d2 > 0)
                getout = true; // endpoint is not in solid
            if (d1 > 0)
                startout = true;

            // if completely in front of face, no intersection
            if (d1 > 0 && d2 >= d1)
                return;

            if (d1 <= 0 && d2 <= 0)
                continue;

            // crosses face
            if (d1 > d2) { // enter
                f = (d1 - DIST_EPSILON) / (d1 - d2);
                if (f > enterfrac) {
                    enterfrac = f;
                    clipplane = plane;
                    leadside = side;
                }
            } else { // leave
                f = (d1 + DIST_EPSILON) / (d1 - d2);
                if (f < leavefrac)
                    leavefrac = f;
            }
        }

        if (!startout) { // original point was inside brush
            trace.startsolid = true;
            if (!getout)
                trace.allsolid = true;
            return;
        }
        if (enterfrac < leavefrac) {
            if (enterfrac > -1 && enterfrac < trace.fraction) {
                if (enterfrac < 0)
                    enterfrac = 0;
                trace.fraction = enterfrac;
                // copy
                trace.plane.set(clipplane);
                trace.surface = leadside.surface.c;
                trace.contents = brush.contents;
            }
        }
    }

    /*
     * ================ CM_TestBoxInBrush ================
     */
    public static void CM_TestBoxInBrush(float[] mins, float[] maxs,
            float[] p1, trace_t trace, cbrush_t brush) {
        int i, j;
        cplane_t plane;
        float dist;
        float[] ofs = { 0, 0, 0 };
        float d1;
        cbrushside_t side;

        if (brush.numsides == 0)
            return;

        for (i = 0; i < brush.numsides; i++) {
            side = map_brushsides[brush.firstbrushside + i];
            plane = side.plane;

            // FIXME: special case for axial
            // general box case
            // push the plane out apropriately for mins/maxs
            // FIXME: use signbits into 8 way lookup for each mins/maxs

            for (j = 0; j < 3; j++) {
                if (plane.normal[j] < 0)
                    ofs[j] = maxs[j];
                else
                    ofs[j] = mins[j];
            }
            dist = Math3D.DotProduct(ofs, plane.normal);
            dist = plane.dist - dist;

            d1 = Math3D.DotProduct(p1, plane.normal) - dist;

            // if completely in front of face, no intersection
            if (d1 > 0)
                return;

        }

        // inside this brush
        trace.startsolid = trace.allsolid = true;
        trace.fraction = 0;
        trace.contents = brush.contents;
    }

    /*
     * ================ CM_TraceToLeaf ================
     */
    public static void CM_TraceToLeaf(int leafnum) {
        int k;
        int brushnum;
        cleaf_t leaf;
        cbrush_t b;

        leaf = map_leafs[leafnum];
        if (0 == (leaf.contents & trace_contents))
            return;

        // trace line against all brushes in the leaf
        for (k = 0; k < leaf.numleafbrushes; k++) {

            brushnum = map_leafbrushes[leaf.firstleafbrush + k];
            b = map_brushes[brushnum];
            if (b.checkcount == checkcount)
                continue; // already checked this brush in another leaf
            b.checkcount = checkcount;

            if (0 == (b.contents & trace_contents))
                continue;
            CM_ClipBoxToBrush(trace_mins, trace_maxs, trace_start, trace_end,
                    trace_trace, b);
            if (0 == trace_trace.fraction)
                return;
        }

    }

    /*
     * ================ CM_TestInLeaf ================
     */
    public static void CM_TestInLeaf(int leafnum) {
        int k;
        int brushnum;
        cleaf_t leaf;
        cbrush_t b;

        leaf = map_leafs[leafnum];
        if (0 == (leaf.contents & trace_contents))
            return;
        // trace line against all brushes in the leaf
        for (k = 0; k < leaf.numleafbrushes; k++) {
            brushnum = map_leafbrushes[leaf.firstleafbrush + k];
            b = map_brushes[brushnum];
            if (b.checkcount == checkcount)
                continue; // already checked this brush in another leaf
            b.checkcount = checkcount;

            if (0 == (b.contents & trace_contents))
                continue;
            CM_TestBoxInBrush(trace_mins, trace_maxs, trace_start, trace_trace,
                    b);
            if (0 == trace_trace.fraction)
                return;
        }

    }

    /*
     * ================== CM_RecursiveHullCheck ==================
     */
    public static void CM_RecursiveHullCheck(int num, float p1f, float p2f,
            float[] p1, float[] p2) {
        cnode_t node;
        cplane_t plane;
        float t1, t2, offset;
        float frac, frac2;
        float idist;
        int i;
        int side;
        float midf;

        if (trace_trace.fraction <= p1f)
            return; // already hit something nearer

        // if < 0, we are in a leaf node
        if (num < 0) {
            CM_TraceToLeaf(-1 - num);
            return;
        }

        //
        // find the point distances to the seperating plane
        // and the offset for the size of the box
        //
        node = map_nodes[num];
        plane = node.plane;

        if (plane.type < 3) {
            t1 = p1[plane.type] - plane.dist;
            t2 = p2[plane.type] - plane.dist;
            offset = trace_extents[plane.type];
        } else {
            t1 = Math3D.DotProduct(plane.normal, p1) - plane.dist;
            t2 = Math3D.DotProduct(plane.normal, p2) - plane.dist;
            if (trace_ispoint)
                offset = 0;
            else
                offset = Math.abs(trace_extents[0] * plane.normal[0])
                        + Math.abs(trace_extents[1] * plane.normal[1])
                        + Math.abs(trace_extents[2] * plane.normal[2]);
        }

        // see which sides we need to consider
        if (t1 >= offset && t2 >= offset) {
            CM_RecursiveHullCheck(node.children[0], p1f, p2f, p1, p2);
            return;
        }