Bsp builder compiling question

Get technical support about the C++ source code and about Lua scripts for maps, entities, GUIs, the console, materials, etc. Also covered are the Cafu libraries and APIs, as well as compiling, linking, and the build system.
Post Reply
kunshou
Posts: 1
Joined: 2011-05-01, 10:57

Bsp builder compiling question

Post by kunshou » 2011-05-01, 11:05

Hi
I was reading the CaBSP code lately. Actually everything works just fine, but I just don't understand:

Code: Select all

void BspTreeBuilderT::Build(bool IsWorldspawn, const ArrayT<Vector3dT>& FloodFillSources_,
    const ArrayT<Vector3dT>& OutsidePointSamples, const std::string& MapFileName)
{
    ArrayT<Vector3dT> FloodFillSources=FloodFillSources_;
    MaterialT LeakDetectMat;    // Just a material instance that is different from all others.

    if (IsWorldspawn)
    {
        // Worldspawen entities are supposed to come with a flood-fill origins list provided by the caller,
        // usually obtained from other entity origins (e.g. info_player_start).
        assert(FloodFillSources.Size()>0);
    }
    else
    {
        assert(FloodFillSources.Size()==0);

        if (FaceChildren.Size()>0)
        {
            // We have faces, but no flood-fill origins.

            // Determine a world bounding box.
            BoundingBox3T<double> WorldBB(FaceChildren[0]->Polygon.Vertices);

            for (unsigned long FaceNr=1; FaceNr<FaceChildren.Size(); FaceNr++)
                WorldBB.Insert(FaceChildren[FaceNr]->Polygon.Vertices);

            const double d=20.0*MapT::MinVertexDist;

            FloodFillSources.PushBack(WorldBB.Max+Vector3dT(d, d, d));
        }
    }


    if (!Option_MostSimpleTree && FaceChildren.Size()>0 /*No need to try to optimize the tree if it's too simple.*/)
    {
        if (!Option_MinimizeFaceSplits)
        {
            // FIRST TREE
            PrepareLeakDetection(FloodFillSources, &LeakDetectMat);
            BuildBSPTree();
            Portalize();
            FloodFillInside(FloodFillSources, OutsidePointSamples);
            if (IsWorldspawn)
            {
                // Only worldspawn entities are seen from the "inside", and thus supposed to be "watertight".
                DetectLeaks(FloodFillSources, MapFileName, &LeakDetectMat);
            }
            RemoveOuterFaces();
            for (unsigned long FaceNr=0; FaceNr<FaceChildren.Size(); FaceNr++)
                if (FaceChildren[FaceNr]->Material==&LeakDetectMat)
                {
                    assert(!IsWorldspawn);
                    delete FaceChildren[FaceNr];

                    FaceChildren[FaceNr]=FaceChildren[FaceChildren.Size()-1]; FaceChildren.DeleteBack();
                    FaceNr--;
                }

            // After 1st tree code.
            ChopUpFaces();
        }

        // SECOND TREE
        PrepareLeakDetection(FloodFillSources, &LeakDetectMat);
        BuildBSPTree();
        Portalize();
        FloodFillInside(FloodFillSources, OutsidePointSamples);
        if (IsWorldspawn)
        {
            // Only worldspawn entities are seen from the "inside", and thus supposed to be "watertight".
            DetectLeaks(FloodFillSources, MapFileName, &LeakDetectMat);
        }
        RemoveOuterFaces();
        for (unsigned long FaceNr=0; FaceNr<FaceChildren.Size(); FaceNr++)
            if (FaceChildren[FaceNr]->Material==&LeakDetectMat)
            {
                assert(!IsWorldspawn);
                delete FaceChildren[FaceNr];

                FaceChildren[FaceNr]=FaceChildren[FaceChildren.Size()-1]; FaceChildren.DeleteBack();
                FaceNr--;
            }

        // After 1st+2nd tree code.
        ;
    }

    MergeFaces();
    ChopUpForMaxLightMapSize();
    ChopUpForMaxSHLMapSize();

    // THIRD TREE
    BuildBSPTree();
    if (IsWorldspawn)
    {
        // Do this only for worldspawn entities (seen from the "inside") for now.
        //
        // For other entities (seen from the "outside"), the outer portals are not built correctly with the current code.
        // This is not so bad, because we don't really need a PVS for those entities anyway, but if we did, we had to make sure first
        // that outer portals work right, which in turn is difficult due to their unlimited size (could limit it to the world BB though).
        Portalize();                                                // Nur f? CaPVS!
        FloodFillInside(FloodFillSources, OutsidePointSamples);     // Nicht mehr wirklich n?zlich, es gibt aber noch Zusammenh?ge mit "InnerLeaf"...
        /*if (IsWorldspawn)*/ RemoveOuterPortals();
    }

    SortFacesIntoTexNameOrder();
    CreateFullBrightLightMaps();
    CreateZeroBandSHLMaps();
    AssignOtherChildrenToLeaves();
    ComputeDrawStructures();
    CreateFullVisPVS();
}
the BSPBuilder builds the tree three times, Why? Isn't once enough?
User avatar
Carsten
Site Admin
Posts: 2160
Joined: 2004-08-19, 13:46
Location: Germany
Contact:

Re: Bsp builder compiling question

Post by Carsten » 2011-05-01, 22:48

Hi kunshou,
welcome to the Cafu forums! :welcome:
kunshou wrote:the BSPBuilder builds the tree three times, Why? Isn't once enough?
Technically, once is enough to create a working tree, as is done when Option_MostSimpleTree is true.

Everything else is done with the goal to create a better, optimized tree:
When the map is read from the map file as defined in the map editor, it contains many surfaces that are redundant, e.g. those that comprise the outer hull and any other (part of a) surface that is not visible from the inside.

We remove these faces before the final tree is built, because it reduces the polygon count, the resulting geometry is cleaner and simpler, and because the split plane choosing heuristic can make better decisions for a more balanced tree.

It turns out that computing the optimal geometry is much helped (computationally and performance-wise) when a tree is already available, thus the code works as follows:
  1. Create a gross, initial tree.
  2. Use that tree to remove outer surfaces quickly.
  3. Among all remaining faces, split those that intersect each other.
  4. The initial tree is now useless, create another one.
  5. Use that second tree to remove outer surfaces again (subfaces of those split in step 3 above).
  6. Merge faces that were previously unnecessarily split, or defined as small fragments by the map artist, limited by max. lightmap / SHL map size.
  7. Build the final tree.
:up:
Best regards,
Carsten
Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest