bool VoxelTree::nudgeCheck(OctreeElement* element, void* extraData) {
    VoxelTreeElement* voxel = (VoxelTreeElement*)element;
    if (voxel->isLeaf()) {
        // we have reached the deepest level of elements/voxels
        // now there are two scenarios
        // 1) this element's size is <= the minNudgeAmount
        //      in which case we will simply call nudgeLeaf on this leaf
        // 2) this element's size is still not <= the minNudgeAmount
        //      in which case we need to break this leaf down until the leaf sizes are <= minNudgeAmount

        NodeChunkArgs* args = (NodeChunkArgs*)extraData;

        // get octal code of this element
        const unsigned char* octalCode = element->getOctalCode();

        // get voxel position/size
        VoxelPositionSize unNudgedDetails;
        voxelDetailsForCode(octalCode, unNudgedDetails);

        // find necessary leaf size
        float newLeafSize = findNewLeafSize(args->nudgeVec, unNudgedDetails.s);

        // check to see if this unNudged element can be nudged
        if (unNudgedDetails.s <= newLeafSize) {
            args->thisVoxelTree->nudgeLeaf(voxel, extraData);
            return false;
        } else {
            // break the current leaf into smaller chunks
            args->thisVoxelTree->chunkifyLeaf(voxel);
        }
    }
    return true;
}

void VoxelsScriptingInterface::eraseVoxel(float x, float y, float z, float scale) {
    // setup a VoxelDetail struct with data
    VoxelDetail deleteVoxelDetail = {x / (float)TREE_SCALE, y / (float)TREE_SCALE, z / (float)TREE_SCALE,
                                        scale / (float)TREE_SCALE};


    // handle the local tree also...
    if (_tree) {
        VoxelTreeElement* deleteVoxelElement = _tree->getVoxelAt(deleteVoxelDetail.x, deleteVoxelDetail.y, deleteVoxelDetail.z, deleteVoxelDetail.s);
        if (deleteVoxelElement) {
            deleteVoxelDetail.red = deleteVoxelElement->getColor()[0];
            deleteVoxelDetail.green = deleteVoxelElement->getColor()[1];
            deleteVoxelDetail.blue = deleteVoxelElement->getColor()[2];
        }
        
        if (_undoStack) {
            DeleteVoxelCommand* command = new DeleteVoxelCommand(_tree,
                                                                 deleteVoxelDetail,
                                                                 getVoxelPacketSender());
            // As QUndoStack automatically executes redo() on push, we don't need to execute the command ourselves.
            _undoStack->push(command);
        } else {
            getVoxelPacketSender()->queueVoxelEditMessages(PacketTypeVoxelErase, 1, &deleteVoxelDetail);
            _tree->deleteVoxelAt(deleteVoxelDetail.x, deleteVoxelDetail.y, deleteVoxelDetail.z, deleteVoxelDetail.s);
        }
    }
}

void voxelTutorial(VoxelTree * tree) {
    printf("adding scene...\n");

    // We want our corner voxels to be about 1/2 meter high, and our TREE_SCALE is in meters, so...    
    float voxelSize = 0.5f / TREE_SCALE;

    // Here's an example of how to create a voxel.
    printf("creating corner points...\n");
    tree->createVoxel(0, 0, 0, voxelSize, 255, 255 ,255);

    // Here's an example of how to test if a voxel exists
    VoxelTreeElement* node = tree->getVoxelAt(0, 0, 0, voxelSize);
    if (node) {
        // and how to access it's color
        printf("corner point 0,0,0 exists... color is (%d,%d,%d) \n", 
            node->getColor()[0], node->getColor()[1], node->getColor()[2]);
    }

    // here's an example of how to delete a voxel
    printf("attempting to delete corner point 0,0,0\n");
    tree->deleteVoxelAt(0, 0, 0, voxelSize);

    // Test to see that the delete worked... it should be FALSE...
    if (tree->getVoxelAt(0, 0, 0, voxelSize)) {
        printf("corner point 0,0,0 exists...\n");
    } else {
        printf("corner point 0,0,0 does not exists...\n");
    }
}

VoxelTreeElement* VoxelTree::createNewElement(unsigned char * octalCode) const {
    VoxelSystem* voxelSystem = NULL;
    if (_rootNode) {
        voxelSystem = ((VoxelTreeElement*)_rootNode)->getVoxelSystem();
    }
    VoxelTreeElement* newElement = new VoxelTreeElement(octalCode); 
    newElement->setVoxelSystem(voxelSystem);
    return newElement;
}

void VoxelsScriptingInterface::setVoxel(float x, float y, float z, float scale,
                                        uchar red, uchar green, uchar blue) {
    // setup a VoxelDetail struct with the data
    VoxelDetail addVoxelDetail = {x / (float)TREE_SCALE, y / (float)TREE_SCALE, z / (float)TREE_SCALE,
                                  scale / (float)TREE_SCALE, red, green, blue
                                 };


    // handle the local tree also...
    if (_tree) {
        if (_undoStack) {
            AddVoxelCommand* addCommand = new AddVoxelCommand(_tree,
                    addVoxelDetail,
                    getVoxelPacketSender());

            VoxelTreeElement* deleteVoxelElement = _tree->getVoxelAt(addVoxelDetail.x, addVoxelDetail.y, addVoxelDetail.z, addVoxelDetail.s);
            if (deleteVoxelElement) {
                nodeColor color;
                memcpy(&color, &deleteVoxelElement->getColor(), sizeof(nodeColor));
                VoxelDetail deleteVoxelDetail = {addVoxelDetail.x,
                                                 addVoxelDetail.y,
                                                 addVoxelDetail.z,
                                                 addVoxelDetail.s,
                                                 color[0],
                                                 color[1],
                                                 color[2]
                                                };
                DeleteVoxelCommand* delCommand = new DeleteVoxelCommand(_tree,
                        deleteVoxelDetail,
                        getVoxelPacketSender());
                _undoStack->beginMacro(addCommand->text());
                // As QUndoStack automatically executes redo() on push, we don't need to execute the command ourselves.
                _undoStack->push(delCommand);
                _undoStack->push(addCommand);
                _undoStack->endMacro();
            } else {
                // As QUndoStack automatically executes redo() on push, we don't need to execute the command ourselves.
                _undoStack->push(addCommand);
            }
        } else {
            // queue the destructive add
            queueVoxelAdd(PacketTypeVoxelSetDestructive, addVoxelDetail);
            _tree->createVoxel(addVoxelDetail.x, addVoxelDetail.y, addVoxelDetail.z, addVoxelDetail.s, red, green, blue, true);
        }
    }
}

// will average the child colors...
void VoxelTreeElement::calculateAverageFromChildren() {
    int colorArray[4] = {0,0,0,0};
    float density = 0.0f;
    for (int i = 0; i < NUMBER_OF_CHILDREN; i++) {
        VoxelTreeElement* childAt = getChildAtIndex(i);
        if (childAt && childAt->isColored()) {
            for (int j = 0; j < 3; j++) {
                colorArray[j] += childAt->getTrueColor()[j]; // color averaging should always be based on true colors
            }
            colorArray[3]++;
        }
        if (childAt) {
            density += childAt->getDensity();
        }
    }
    density /= (float) NUMBER_OF_CHILDREN;
    //
    //  The VISIBLE_ABOVE_DENSITY sets the density of matter above which an averaged color voxel will
    //  be set.  It is an important physical constant in our universe.  A number below 0.5 will cause
    //  things to get 'fatter' at a distance, because upward averaging will make larger voxels out of
    //  less data, which is (probably) going to be preferable because it gives a sense that there is
    //  something out there to go investigate.   A number above 0.5 would cause the world to become
    //  more 'empty' at a distance.  Exactly 0.5 would match the physical world, at least for materials
    //  that are not shiny and have equivalent ambient reflectance.
    //
    const float VISIBLE_ABOVE_DENSITY = 0.10f;
    nodeColor newColor = { 0, 0, 0, 0};
    if (density > VISIBLE_ABOVE_DENSITY) {
        // The density of material in the space of the voxel sets whether it is actually colored
        for (int c = 0; c < 3; c++) {
            // set the average color value
            newColor[c] = colorArray[c] / colorArray[3];
        }
        // set the alpha to 1 to indicate that this isn't transparent
        newColor[3] = 1;
    }
    //  Set the color from the average of the child colors, and update the density
    setColor(newColor);
    setDensity(density);
}

bool sendVoxelsOperation(OctreeElement* element, void* extraData) {
    VoxelTreeElement* voxel = static_cast<VoxelTreeElement*>(element);
    SendVoxelsOperationArgs* args = static_cast<SendVoxelsOperationArgs*>(extraData);
    if (voxel->isColored()) {
        const unsigned char* nodeOctalCode = voxel->getOctalCode();
        unsigned char* codeColorBuffer = NULL;
        int codeLength  = 0;
        int bytesInCode = 0;
        int codeAndColorLength;
        
        // If the newBase is NULL, then don't rebase
        if (args->newBaseOctCode) {
            codeColorBuffer = rebaseOctalCode(nodeOctalCode, args->newBaseOctCode, true);
            codeLength  = numberOfThreeBitSectionsInCode(codeColorBuffer);
            bytesInCode = bytesRequiredForCodeLength(codeLength);
            codeAndColorLength = bytesInCode + SIZE_OF_COLOR_DATA;
        } else {
            codeLength  = numberOfThreeBitSectionsInCode(nodeOctalCode);
            bytesInCode = bytesRequiredForCodeLength(codeLength);
            codeAndColorLength = bytesInCode + SIZE_OF_COLOR_DATA;
            codeColorBuffer = new unsigned char[codeAndColorLength];
            memcpy(codeColorBuffer, nodeOctalCode, bytesInCode);
        }
        
        // copy the colors over
        codeColorBuffer[bytesInCode + RED_INDEX] = voxel->getColor()[RED_INDEX];
        codeColorBuffer[bytesInCode + GREEN_INDEX] = voxel->getColor()[GREEN_INDEX];
        codeColorBuffer[bytesInCode + BLUE_INDEX] = voxel->getColor()[BLUE_INDEX];
        args->packetSender->queueVoxelEditMessage(PacketTypeVoxelSetDestructive,
                                                  codeColorBuffer, codeAndColorLength);
        
        delete[] codeColorBuffer;
    }
    return true; // keep going
}

bool copyAndFillOperation(OctreeElement* element, void* extraData) {
    VoxelTreeElement* voxel = (VoxelTreeElement*)element;
    copyAndFillArgs* args = (copyAndFillArgs*)extraData;
    char outputMessage[128];

    args->inCount++;
    int percentDone = (100*args->inCount/args->originalCount);

    // For each leaf node...
    if (voxel->isLeaf()) {
        // create a copy of the leaf in the copy destination
        float x = voxel->getCorner().x;
        float y = voxel->getCorner().y;
        float z = voxel->getCorner().z;
        float s = voxel->getScale();
        unsigned char red = voxel->getTrueColor()[RED_INDEX];
        unsigned char green = voxel->getTrueColor()[GREEN_INDEX];
        unsigned char blue = voxel->getTrueColor()[BLUE_INDEX];
        bool destructive = true;

        args->destinationTree->createVoxel(x, y, z, s, red, green, blue, destructive);
        args->outCount++;
        
        sprintf(outputMessage,"Completed: %d%% (%lu of %lu) - Creating voxel %lu at [%f,%f,%f,%f]",
            percentDone,args->inCount,args->originalCount,args->outCount,x,y,z,s);
        printf("%s",outputMessage);
        for (int b = 0; b < strlen(outputMessage); b++) {
            printf("\b");
        }
        
        // and create same sized leafs from this leaf voxel down to zero in the destination tree
        for (float yFill = y-s; yFill >= 0.0f; yFill -= s) {
            args->destinationTree->createVoxel(x, yFill, z, s, red, green, blue, destructive);

            args->outCount++;
        
        sprintf(outputMessage,"Completed: %d%% (%lu of %lu) - Creating fill voxel %lu at [%f,%f,%f,%f]",
            percentDone,args->inCount,args->originalCount,args->outCount,x,y,z,s);
            printf("%s",outputMessage);
            for (int b = 0; b < strlen(outputMessage); b++) {
                printf("\b");
            }
        }
    }
    return true;
}

VoxelDetail VoxelsScriptingInterface::getVoxelEnclosingPoint(const glm::vec3& point) {
    VoxelDetail result = { 0.0f, 0.0f, 0.0f, 0.0f, 0, 0, 0 };
    if (_tree) {
        OctreeElement* element = _tree->getElementEnclosingPoint(point / (float)TREE_SCALE);
        if (element) {
            VoxelTreeElement* voxel = static_cast<VoxelTreeElement*>(element);
            result.x = voxel->getCorner().x;
            result.y = voxel->getCorner().y;
            result.z = voxel->getCorner().z;
            result.s = voxel->getScale();
            result.red = voxel->getColor()[0];
            result.green = voxel->getColor()[1];
            result.blue = voxel->getColor()[2];
        }
    }
    return result;
}

// will detect if children are leaves AND the same color
// and in that case will delete the children and make this node
// a leaf, returns TRUE if all the leaves are collapsed into a
// single node
bool VoxelTreeElement::collapseChildren() {
    // scan children, verify that they are ALL present and accounted for
    bool allChildrenMatch = true; // assume the best (ottimista)
    int red,green,blue;
    for (int i = 0; i < NUMBER_OF_CHILDREN; i++) {
        VoxelTreeElement* childAt = getChildAtIndex(i);
        // if no child, child isn't a leaf, or child doesn't have a color
        if (!childAt || !childAt->isLeaf() || !childAt->isColored()) {
            allChildrenMatch=false;
            //qDebug("SADNESS child missing or not colored! i=%d\n",i);
            break;
        } else {
            if (i==0) {
                red   = childAt->getColor()[0];
                green = childAt->getColor()[1];
                blue  = childAt->getColor()[2];
            } else if (red != childAt->getColor()[0] ||
                    green != childAt->getColor()[1] || blue != childAt->getColor()[2]) {
                allChildrenMatch=false;
                break;
            }
        }
    }


    if (allChildrenMatch) {
        //qDebug("allChildrenMatch: pruning tree\n");
        for (int i = 0; i < NUMBER_OF_CHILDREN; i++) {
            OctreeElement* childAt = getChildAtIndex(i);
            delete childAt; // delete all the child nodes
            setChildAtIndex(i, NULL); // set it to NULL
        }
        nodeColor collapsedColor;
        collapsedColor[0]=red;
        collapsedColor[1]=green;
        collapsedColor[2]=blue;
        collapsedColor[3]=1;    // color is set
        setColor(collapsedColor);
    }
    return allChildrenMatch;
}

RayToVoxelIntersectionResult VoxelsScriptingInterface::findRayIntersection(const PickRay& ray) {
    RayToVoxelIntersectionResult result;
    if (_tree) {
        OctreeElement* element;
        result.intersects = _tree->findRayIntersection(ray.origin, ray.direction, element, result.distance, result.face);
        if (result.intersects) {
            VoxelTreeElement* voxel = (VoxelTreeElement*)element;
            result.voxel.x = voxel->getCorner().x;
            result.voxel.y = voxel->getCorner().y;
            result.voxel.z = voxel->getCorner().z;
            result.voxel.s = voxel->getScale();
            result.voxel.red = voxel->getColor()[0];
            result.voxel.green = voxel->getColor()[1];
            result.voxel.blue = voxel->getColor()[2];
            result.intersection = ray.origin + (ray.direction * result.distance);
        }
    }
    return result;
}

VoxelDetail VoxelsScriptingInterface::getVoxelAt(float x, float y, float z, float scale) {
    // setup a VoxelDetail struct with the data
    VoxelDetail result = {0,0,0,0,0,0,0};

    if (_tree) {
        _tree->lockForRead();

        VoxelTreeElement* voxel = static_cast<VoxelTreeElement*>(_tree->getOctreeElementAt(x / (float)TREE_SCALE, y / (float)TREE_SCALE, 
                                                    z / (float)TREE_SCALE, scale / (float)TREE_SCALE));
        _tree->unlock();
        if (voxel) {
             // Note: these need to be in voxel space because the VoxelDetail -> js converter will upscale
            result.x = voxel->getCorner().x;
            result.y = voxel->getCorner().y;
            result.z = voxel->getCorner().z;
            result.s = voxel->getScale();
            result.red = voxel->getColor()[RED_INDEX];
            result.green = voxel->getColor()[GREEN_INDEX];
            result.blue = voxel->getColor()[BLUE_INDEX];
        }
    }
    return result;
}

void unitTest(VoxelTree * tree) {
    VoxelTreeElement* node = NULL;
    printf("unit tests...\n");
    unsigned long nodeCount;

    // We want our corner voxels to be about 1/2 meter high, and our TREE_SCALE is in meters, so...    
    float voxelSize = 0.5f / TREE_SCALE;

    // Here's an example of how to create a voxel.
    printf("creating corner points...\n");
    tree->createVoxel(0, 0, 0, voxelSize, 255, 255 ,255);
    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    
    // Here's an example of how to test if a voxel exists
    node = tree->getVoxelAt(0, 0, 0, voxelSize);
    if (node) {
        // and how to access it's color
        printf("CORRECT - corner point 0,0,0 exists... color is (%d,%d,%d) \n", 
            node->getColor()[0], node->getColor()[1], node->getColor()[2]);
    }

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    // here's an example of how to delete a voxel
    printf("attempting to delete corner point 0,0,0\n");
    tree->deleteVoxelAt(0, 0, 0, voxelSize);

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    // Test to see that the delete worked... it should be FALSE...
    if ((node = tree->getVoxelAt(0, 0, 0, voxelSize))) {
        printf("FAIL corner point 0,0,0 exists...\n");
    } else {
        printf("CORRECT corner point 0,0,0 does not exists...\n");
    }

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    tree->createVoxel(0, 0, 0, voxelSize, 255, 255 ,255);
    if ((node = tree->getVoxelAt(0, 0, 0, voxelSize))) {
        printf("CORRECT - corner point 0,0,0 exists... color is (%d,%d,%d) \n", 
            node->getColor()[0], node->getColor()[1], node->getColor()[2]);
    } else {
        printf("FAIL corner point 0,0,0 does not exists...\n");
    }

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    tree->createVoxel(voxelSize, 0, 0, voxelSize, 255, 255 ,0);
    if ((node = tree->getVoxelAt(voxelSize, 0, 0, voxelSize))) {
        printf("CORRECT - corner point voxelSize,0,0 exists... color is (%d,%d,%d) \n", 
            node->getColor()[0], node->getColor()[1], node->getColor()[2]);
    } else {
        printf("FAIL corner point voxelSize,0,0 does not exists...\n");
    }

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    tree->createVoxel(0, 0, voxelSize, voxelSize, 255, 0 ,0);
    if ((node = tree->getVoxelAt(0, 0, voxelSize, voxelSize))) {
        printf("CORRECT - corner point 0, 0, voxelSize exists... color is (%d,%d,%d) \n", 
            node->getColor()[0], node->getColor()[1], node->getColor()[2]);
    } else {
        printf("FAILED corner point 0, 0, voxelSize does not exists...\n");
    }

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    tree->createVoxel(voxelSize, 0, voxelSize, voxelSize, 0, 0 ,255);
    if ((node = tree->getVoxelAt(voxelSize, 0, voxelSize, voxelSize))) {
        printf("CORRECT - corner point voxelSize, 0, voxelSize exists... color is (%d,%d,%d) \n", 
            node->getColor()[0], node->getColor()[1], node->getColor()[2]);
    } else {
        printf("corner point voxelSize, 0, voxelSize does not exists...\n");
    }

    printf("Nodes at line %d... %ld nodes\n", __LINE__, tree->getOctreeElementsCount());

    printf("check root voxel exists...\n");
    if (tree->getVoxelAt(0,0,0,1.0)) {
        printf("of course it does\n");
    } else {
        printf("WTH!?!\n");
    }

    nodeCount = tree->getOctreeElementsCount();
    printf("Nodes before writing file: %ld nodes\n", nodeCount);
    
    tree->writeToSVOFile("voxels.svo");

    printf("erasing the tree...\n");
    tree->eraseAllOctreeElements();

    printf("check root voxel exists...\n");
    if (tree->getVoxelAt(0,0,0,1.0)) {
        printf("of course it does\n");
    } else {
        printf("WTH!?!\n");
    }
//.........这里部分代码省略.........

// This will be called primarily on addChildAt(), which means we're adding a child of our
// own type to our own tree. This means we should initialize that child with any tree and type
// specific settings that our children must have. One example is out VoxelSystem, which
// we know must match ours.
OctreeElement* VoxelTreeElement::createNewElement(unsigned char* octalCode) {
    VoxelTreeElement* newChild = new VoxelTreeElement(octalCode);
    newChild->setVoxelSystem(getVoxelSystem()); // our child is always part of our voxel system NULL ok
    return newChild;
}

DeleteVoxelCommand::DeleteVoxelCommand(VoxelTree* tree, VoxelDetail& voxel, VoxelEditPacketSender* packetSender, QUndoCommand* parent) :
    QUndoCommand("Delete Voxel", parent),
    _tree(tree),
    _packetSender(packetSender),
    _voxel(voxel),
    _oldTree(NULL)
{
    _tree->lockForRead();
    VoxelTreeElement* element = _tree->getEnclosingVoxelAt(_voxel.x, _voxel.y, _voxel.z, _voxel.s);
    if (element->getScale() == _voxel.s) {
        if (!element->hasContent() && !element->isLeaf()) {
            _oldTree = new VoxelTree();
            _tree->copySubTreeIntoNewTree(element, _oldTree, false);
        } else {
            _voxel.red = element->getColor()[0];
            _voxel.green = element->getColor()[1];
            _voxel.blue = element->getColor()[2];
        }
    } else if (element->hasContent() && element->isLeaf()) {
        _voxel.red = element->getColor()[0];
        _voxel.green = element->getColor()[1];
        _voxel.blue = element->getColor()[2];
    } else {
        _voxel.s = 0.0f;
    }
    _tree->unlock();
}