kdtree.java

Sunflow是一个照片级的渲染系统

                            int obj = unpackObject(ptr);
                            lrtable[obj >>> 2] |= 1 << ((obj & 3) << 1);
                            lk++;
                        }
                    }
                }
                for (int i = bestOffsetStart; i < bestOffsetEnd; i++) {
                    long ptr = splits[i];
                    assert unpackAxis(ptr) == bestAxis;
                    if (unpackSplitType(ptr) == PLANAR) {
                        if (bestPlanarLeft) {
                            int obj = unpackObject(ptr);
                            lrtable[obj >>> 2] |= 1 << ((obj & 3) << 1);
                            lk++;
                        } else {
                            int obj = unpackObject(ptr);
                            lrtable[obj >>> 2] |= 2 << ((obj & 3) << 1);
                            rk++;
                        }
                    }
                }
                for (int i = bestOffsetEnd; i < nSplits; i++) {
                    long ptr = splits[i];
                    if (unpackAxis(ptr) == bestAxis) {
                        if (unpackSplitType(ptr) != OPENED) {
                            int obj = unpackObject(ptr);
                            lrtable[obj >>> 2] |= 2 << ((obj & 3) << 1);
                            rk++;
                        }
                    }
                }
                // output new splits while maintaining order
                long[] splitsL = taskL.splits;
                long[] splitsR = taskR.splits;
                int nsl = 0, nsr = 0;
                for (int i = 0; i < nSplits; i++) {
                    long ptr = splits[i];
                    int obj = unpackObject(ptr);
                    int idx = obj >>> 2;
                    int mask = 1 << ((obj & 3) << 1);
                    if ((lrtable[idx] & mask) != 0) {
                        splitsL[nsl] = ptr;
                        nsl++;
                    }
                    if ((lrtable[idx] & (mask << 1)) != 0) {
                        splitsR[nsr] = ptr;
                        nsr++;
                    }
                }
                taskL.n = nsl;
                taskR.n = nsr;
                // free more memory
                task.splits = splits = splitsL = splitsR = null;
                task = null;
                // allocate child nodes
                int nextOffset = tempTree.getSize();
                tempTree.add(0);
                tempTree.add(0);
                tempTree.add(0);
                tempTree.add(0);
                // create current node
                tempTree.set(offset + 0, (bestAxis << 30) | nextOffset);
                tempTree.set(offset + 1, Float.floatToRawIntBits(bestSplit));
                // recurse for child nodes - free object arrays after each step
                stats.updateInner();
                switch (bestAxis) {
                    case 0:
                        buildTree(minx, bestSplit, miny, maxy, minz, maxz, taskL, depth + 1, tempTree, nextOffset, tempList, stats);
                        taskL = null;
                        buildTree(bestSplit, maxx, miny, maxy, minz, maxz, taskR, depth + 1, tempTree, nextOffset + 2, tempList, stats);
                        taskR = null;
                        return;
                    case 1:
                        buildTree(minx, maxx, miny, bestSplit, minz, maxz, taskL, depth + 1, tempTree, nextOffset, tempList, stats);
                        taskL = null;
                        buildTree(minx, maxx, bestSplit, maxy, minz, maxz, taskR, depth + 1, tempTree, nextOffset + 2, tempList, stats);
                        taskR = null;
                        return;
                    case 2:
                        buildTree(minx, maxx, miny, maxy, minz, bestSplit, taskL, depth + 1, tempTree, nextOffset, tempList, stats);
                        taskL = null;
                        buildTree(minx, maxx, miny, maxy, bestSplit, maxz, taskR, depth + 1, tempTree, nextOffset + 2, tempList, stats);
                        taskR = null;
                        return;
                    default:
                        assert false;
                }
            }
        }
        // create leaf node
        int listOffset = tempList.getSize();
        int n = 0;
        for (int i = 0; i < task.n; i++) {
            long ptr = task.splits[i];
            if (unpackAxis(ptr) == 0 && unpackSplitType(ptr) != CLOSED) {
                tempList.add(unpackObject(ptr));
                n++;
            }
        }
        stats.updateLeaf(depth, n);
        if (n != task.numObjects)
            UI.printError(Module.ACCEL, "Error creating leaf node - expecting %d found %d", task.numObjects, n);
        tempTree.set(offset + 0, (3 << 30) | listOffset);
        tempTree.set(offset + 1, task.numObjects);
        // free some memory
        task.splits = null;
    }

    public void intersect(Ray r, IntersectionState state) {
        float intervalMin = r.getMin();
        float intervalMax = r.getMax();
        float orgX = r.ox;
        float dirX = r.dx, invDirX = 1 / dirX;
        float t1, t2;
        t1 = (bounds.getMinimum().x - orgX) * invDirX;
        t2 = (bounds.getMaximum().x - orgX) * invDirX;
        if (invDirX > 0) {
            if (t1 > intervalMin)
                intervalMin = t1;
            if (t2 < intervalMax)
                intervalMax = t2;
        } else {
            if (t2 > intervalMin)
                intervalMin = t2;
            if (t1 < intervalMax)
                intervalMax = t1;
        }
        if (intervalMin > intervalMax)
            return;
        float orgY = r.oy;
        float dirY = r.dy, invDirY = 1 / dirY;
        t1 = (bounds.getMinimum().y - orgY) * invDirY;
        t2 = (bounds.getMaximum().y - orgY) * invDirY;
        if (invDirY > 0) {
            if (t1 > intervalMin)
                intervalMin = t1;
            if (t2 < intervalMax)
                intervalMax = t2;
        } else {
            if (t2 > intervalMin)
                intervalMin = t2;
            if (t1 < intervalMax)
                intervalMax = t1;
        }
        if (intervalMin > intervalMax)
            return;
        float orgZ = r.oz;
        float dirZ = r.dz, invDirZ = 1 / dirZ;
        t1 = (bounds.getMinimum().z - orgZ) * invDirZ;
        t2 = (bounds.getMaximum().z - orgZ) * invDirZ;
        if (invDirZ > 0) {
            if (t1 > intervalMin)
                intervalMin = t1;
            if (t2 < intervalMax)
                intervalMax = t2;
        } else {
            if (t2 > intervalMin)
                intervalMin = t2;
            if (t1 < intervalMax)
                intervalMax = t1;
        }
        if (intervalMin > intervalMax)
            return;

        // compute custom offsets from direction sign bit
        int offsetXFront = (Float.floatToRawIntBits(dirX) & (1 << 31)) >>> 30;
        int offsetYFront = (Float.floatToRawIntBits(dirY) & (1 << 31)) >>> 30;
        int offsetZFront = (Float.floatToRawIntBits(dirZ) & (1 << 31)) >>> 30;

        int offsetXBack = offsetXFront ^ 2;
        int offsetYBack = offsetYFront ^ 2;
        int offsetZBack = offsetZFront ^ 2;

        IntersectionState.StackNode[] stack = state.getStack();
        int stackTop = state.getStackTop();
        int stackPos = stackTop;
        int node = 0;

        while (true) {
            int tn = tree[node];
            int axis = tn & (3 << 30);
            int offset = tn & ~(3 << 30);
            switch (axis) {
                case 0: {
                    float d = (Float.intBitsToFloat(tree[node + 1]) - orgX) * invDirX;
                    int back = offset + offsetXBack;
                    node = back;
                    if (d < intervalMin)
                        continue;
                    node = offset + offsetXFront; // front
                    if (d > intervalMax)
                        continue;
                    // push back node
                    stack[stackPos].node = back;
                    stack[stackPos].near = (d >= intervalMin) ? d : intervalMin;
                    stack[stackPos].far = intervalMax;
                    stackPos++;
                    // update ray interval for front node
                    intervalMax = (d <= intervalMax) ? d : intervalMax;
                    continue;
                }
                case 1 << 30: {
                    // y axis
                    float d = (Float.intBitsToFloat(tree[node + 1]) - orgY) * invDirY;
                    int back = offset + offsetYBack;
                    node = back;
                    if (d < intervalMin)
                        continue;
                    node = offset + offsetYFront; // front
                    if (d > intervalMax)
                        continue;
                    // push back node
                    stack[stackPos].node = back;
                    stack[stackPos].near = (d >= intervalMin) ? d : intervalMin;
                    stack[stackPos].far = intervalMax;
                    stackPos++;
                    // update ray interval for front node
                    intervalMax = (d <= intervalMax) ? d : intervalMax;
                    continue;
                }
                case 2 << 30: {
                    // z axis
                    float d = (Float.intBitsToFloat(tree[node + 1]) - orgZ) * invDirZ;
                    int back = offset + offsetZBack;
                    node = back;
                    if (d < intervalMin)
                        continue;
                    node = offset + offsetZFront; // front
                    if (d > intervalMax)
                        continue;
                    // push back node
                    stack[stackPos].node = back;
                    stack[stackPos].near = (d >= intervalMin) ? d : intervalMin;
                    stack[stackPos].far = intervalMax;
                    stackPos++;
                    // update ray interval for front node
                    intervalMax = (d <= intervalMax) ? d : intervalMax;
                    continue;
                }
                default: {
                    // leaf - test some objects
                    int n = tree[node + 1];
                    while (n > 0) {
                        primitiveList.intersectPrimitive(r, primitives[offset], state);
                        n--;
                        offset++;
                    }
                    if (r.getMax() < intervalMax)
                        return;
                    do {
                        // stack is empty?
                        if (stackPos == stackTop)
                            return;
                        // move back up the stack
                        stackPos--;
                        intervalMin = stack[stackPos].near;
                        if (r.getMax() < intervalMin)
                            continue;
                        node = stack[stackPos].node;
                        intervalMax = stack[stackPos].far;
                        break;
                    } while (true);
                }
            } // switch
        } // traversal loop
    }
}