ps1bsptools/bsp.h

#pragma once

#define CONTENTS_EMPTY      -1
#define CONTENTS_SOLID      -2
#define CONTENTS_WATER      -3
#define CONTENTS_SLIME      -4
#define CONTENTS_LAVA       -5
#define CONTENTS_SKY        -6

typedef struct                 // A Directory entry
{
	long  offset;                // Offset to entry, in bytes, from start of file
	long  size;                  // Size of entry in file, in bytes
} dentry_t;

typedef struct                 // The BSP file header
{
    long  version;               // Model version, must be 0x17 (23).
    dentry_t entities;           // List of Entities.
    dentry_t planes;             // Map Planes.
                                 // numplanes = size/sizeof(plane_t)
    dentry_t miptex;             // Wall Textures.
    dentry_t vertices;           // Map Vertices.
                                 // numvertices = size/sizeof(vertex_t)
    dentry_t visilist;           // Leaves Visibility lists.
    dentry_t nodes;              // BSP Nodes.
                                 // numnodes = size/sizeof(node_t)
    dentry_t texinfo;            // Texture Info for faces.
                                 // numtexinfo = size/sizeof(texinfo_t)
    dentry_t faces;              // Faces of each surface.
                                 // numfaces = size/sizeof(face_t)
    dentry_t lightmaps;          // Wall Light Maps.
    dentry_t clipnodes;          // clip nodes, for Models.
                                 // numclips = size/sizeof(clipnode_t)
    dentry_t leaves;             // BSP Leaves.
                                 // numlaves = size/sizeof(leaf_t)
    dentry_t lface;              // List of Faces.
    dentry_t edges;              // Edges of faces.
                                 // numedges = Size/sizeof(edge_t)
    dentry_t ledges;             // List of Edges.
    dentry_t models;             // List of Models.
                                 // nummodels = Size/sizeof(model_t)
} dheader_t;

typedef struct Plane
{
    vec3_t normal;               // Vector orthogonal to plane (Nx,Ny,Nz)
                                // with Nx2+Ny2+Nz2 = 1
    scalar_t dist;               // Offset to plane, along the normal vector.
                                 // Distance from (0,0,0) to the plane
    long    type;                // Type of plane, depending on normal vector.

    double pointDistance(const Vec3& point) const
    {
        return normal.dotProduct(point) - dist;
    }

    void getTangents(Vec3& tangent, Vec3& bitangent) const
    {
        Vec3 dir;
        switch (type)
        {
        case 0:
        case 3:
            dir = Vec3(0.f, 1.f, 0.f);
            break;
        case 1:
        case 4:
        default:
            dir = Vec3(0.f, 0.f, 1.f);
            break;
        case 2:
        case 5:
            dir = Vec3(1.f, 0.f, 0.f);
            break;
        }

        tangent = normal.crossProduct(dir).normalized();
        bitangent = tangent.crossProduct(normal);
    }

    Vec3 projectPoint(const Vec3& point) const
    {
        double pointDist = normal.dotProduct(point) - dist;
        return point - normal * pointDist;
    }
} plane_t;

typedef struct BoundBox                 // Bounding Box, Float values
{
    vec3_t   min;                // minimum values of X,Y,Z
    vec3_t   max;                // maximum values of X,Y,Z

    BoundBox(): min(FLT_MAX, FLT_MAX, FLT_MAX), max(FLT_MIN, FLT_MIN, FLT_MIN) { }

    void init(vec3_t point)
    {
        min = point;
        max = point;
    }

    void includePoint(vec3_t point)
    {
        if (point.x < min.x)
            min.x = point.x;
        if (point.y < min.y)
            min.y = point.y;
        if (point.z < min.z)
            min.z = point.z;

        if (point.x > max.x)
            max.x = point.x;
        if (point.y > max.y)
            max.y = point.y;
        if (point.z > max.z)
            max.z = point.z;
    }

    vec3_t getCenter() const
    {
        return vec3_t(
            (max.x + min.x) * 0.5f,
            (max.y + min.y) * 0.5f,
            (max.z + min.z) * 0.5f
        );
    }

    SVECTOR toBoundingSphere() const
    {
        Vec3 center = getCenter();
        Vec3 extents = max - center;

        SVECTOR sphere = center.convertWorldPosition();
        sphere.pad = (short)(extents.magnitude() * WORLDSCALE);
        return sphere;
    }
} boundbox_t;

typedef struct BBoxShort            // Bounding Box, Short values
{
    short   min[3];                 // minimum values of X,Y,Z
    short   max[3];                 // maximum values of X,Y,Z

    vec3_t getMins() const
    {
        return Vec3(min[0], min[1], min[2]);
    }

    vec3_t getMaxs() const
    {
        return Vec3(max[0], max[1], max[2]);
    }

    vec3_t getCenter() const
    {
        return vec3_t(
            ((float)max[0] + (float)min[0]) / 2,
            ((float)max[1] + (float)min[1]) / 2,
            ((float)max[2] + (float)min[2]) / 2
        );
    }

    SVECTOR toBoundingSphere() const
    {
        Vec3 center = getCenter();
        Vec3 extents = getMaxs() - center;

        SVECTOR sphere = center.convertWorldPosition();
        sphere.pad = (short)(extents.magnitude() * WORLDSCALE);
        return sphere;
    }
} bboxshort_t;

typedef struct                 // Mip texture list header
{
    long numtex;                 // Number of textures in Mip Texture list
    long *offset;               // Offset to each of the individual texture
} mipheader_t;                 //  from the beginning of mipheader_t

typedef struct                 // Mip Texture
{
    char   name[16];             // Name of the texture.
    unsigned long width;                // width of picture, must be a multiple of 8
    unsigned long height;               // height of picture, must be a multiple of 8
    unsigned long offset1;              // offset to u_char Pix[width   * height]
    unsigned long offset2;              // offset to u_char Pix[width/2 * height/2]
    unsigned long offset4;              // offset to u_char Pix[width/4 * height/4]
    unsigned long offset8;              // offset to u_char Pix[width/8 * height/8]
} miptex_t;

typedef struct Vertex
{
    float X;                    // X,Y,Z coordinates of the vertex
    float Y;                    // usually some integer value
    float Z;                    // but coded in floating point

    vec3_t toVec() const
    {
        return vec3_t(X, Y, Z);
    }
} vertex_t;

typedef struct
{
    unsigned short vertex0;             // index of the start vertex
                                //  must be in [0,numvertices[
    unsigned short vertex1;             // index of the end vertex
                                 //  must be in [0,numvertices[
} edge_t;

typedef struct
{
    vec3_t   vectorS;            // S vector, horizontal in texture space)
    scalar_t distS;              // horizontal offset in texture space
    vec3_t   vectorT;            // T vector, vertical in texture space
    scalar_t distT;              // vertical offset in texture space
    unsigned long   texture_id;         // Index of Mip Texture
                                 //           must be in [0,numtex[
    unsigned long   animated;           // 0 for ordinary textures, 1 for water 
} texinfo_t;

typedef struct
{
    unsigned short plane_id;            // The plane in which the face lies
                                //           must be in [0,numplanes[ 
    unsigned short side;                // 0 if in front of the plane, 1 if behind the plane
    long ledge_id;               // first edge in the List of edges
                                 //           must be in [0,numledges[
    unsigned short ledge_num;           // number of edges in the List of edges
    unsigned short texinfo_id;          // index of the Texture info the face is part of
                                 //           must be in [0,numtexinfos[ 
    unsigned char typelight;            // type of lighting, for the face
    unsigned char baselight;            // from 0xFF (dark) to 0 (bright)
    unsigned char light[2];             // two additional light models  
    long lightmap;               // Pointer inside the general light map, or -1
                                 // this define the start of the face light map
} face_t;

typedef struct
{
    long    plane_id;            // The plane that splits the node
                                //           must be in [0,numplanes[
    short   front;               // If bit15==0, index of Front child node
                                 // If bit15==1, ~front = index of child leaf
    short   back;                // If bit15==0, id of Back child node
                                 // If bit15==1, ~back =  id of child leaf
    bboxshort_t box;             // Bounding box of node and all childs
    unsigned short face_id;             // Index of first Polygons in the node
    unsigned short face_num;            // Number of faces in the node
} node_t;

typedef struct
{
    long type;                   // Special type of leaf
    long vislist;                // Beginning of visibility lists
                                 //     must be -1 or in [0,numvislist[
    bboxshort_t bound;           // Bounding box of the leaf
    unsigned short lface_id;            // First item of the list of faces
                                 //     must be in [0,numlfaces[
    unsigned short lface_num;           // Number of faces in the leaf  
    unsigned char sndwater;             // level of the four ambient sounds:
    unsigned char sndsky;               //   0    is no sound
    unsigned char sndslime;             //   0xFF is maximum volume
    unsigned char sndlava;              //
} dleaf_t;

typedef struct
{
    boundbox_t bound;            // The bounding box of the Model
    vec3_t origin;               // origin of model, usually (0,0,0)
    long node_id0;               // index of first BSP node
    long node_id1;               // index of the first Clip node
    long node_id2;               // index of the second Clip node
    long node_id3;               // usually zero
    long numleafs;               // number of BSP leaves
    long face_id;                // index of Faces
    long face_num;               // number of Faces
} model_t;

typedef struct World
{
    const char* name;
    dheader_t header;

    mipheader_t mipheader;
    miptex_t* miptexes;
    unsigned char** textures;

    int numPlanes;
    plane_t* planes;

    int numVertices;
    vertex_t* vertices;

    int numEdges;
    edge_t* edges;

    int edgeListLength;
    int* edgeList;

    int numTexInfos;
    texinfo_t* texInfos;

    int numFaces;
    face_t* faces;

    int faceListLength;
    unsigned short* faceList;

    int visListLength;
    unsigned char *visList;

    int numNodes;
    node_t* nodes;

    int numLeaves;
    dleaf_t* leaves;

    int numModels;
    model_t* models;

    int entitiesLength;
    char* entities;

    int lightmapLength;
    unsigned char* lightmap;

    // Find the list of all faces that contain the given point, i.e. the point lies on the face's plane and is contained within its polygon bounds
    std::vector<const face_t*> facesWithPoint(const Vec3& point) const
    {
        std::vector<const face_t*> outFaces;
        for (int faceIdx = 0; faceIdx < numFaces; ++faceIdx)
        {
            const face_t* face = &faces[faceIdx];
            const plane_t* plane = &planes[face->plane_id];

            // Check if the point lies on the face's plane (it's not strictly necessary to do this, but this check makes the whole function a lot faster)
            if (fabs(plane->pointDistance(point)) > 0.01)
                continue;

            // Check if the point is contained within the face's polygon
            double angleSum = 0;
            for (int edgeListIdx = 0; edgeListIdx < face->ledge_num; ++edgeListIdx)
            {
                int edgeIdx = edgeList[face->ledge_id + edgeListIdx];

                Vec3 v0, v1;
                if (edgeIdx > 0)
                {
                    const edge_t* edge = &edges[edgeIdx];
                    v0 = vertices[edge->vertex0].toVec();
                    v1 = vertices[edge->vertex1].toVec();
                }
                else
                {
                    const edge_t* edge = &edges[-edgeIdx];
                    v0 = vertices[edge->vertex1].toVec();
                    v1 = vertices[edge->vertex0].toVec();
                }

                Vec3 p0 = v0 - point;
                Vec3 p1 = v1 - point;
                double m0 = p0.magnitude();
                double m1 = p1.magnitude();

                if ((m0 * m1) <= 0.1)
                {
                    // Point is on one of the vertices
                    outFaces.push_back(face);
                    break;
                }

                double dot = p0.dotProduct(p1) / (m0 * m1);
                if (dot < -1) dot = -1; if (dot > 1) dot = 1;   // Floating point rounding errors, YAY!
                angleSum += acos(dot);
            }

            // If the point is inside the polygon, then the sum of all the above angles will be exactly 360 degrees
            if (fabs(2 * M_PI - angleSum) <= 0.01)
                outFaces.push_back(face);
        }

        return outFaces;
    }

    std::vector<Vec3> findTjunctions(const Vec3& point) const
    {
        std::vector<Vec3> outTangents;
        for (int faceIdx = 0; faceIdx < numFaces; ++faceIdx)
        {
            const face_t* face = &faces[faceIdx];
            const plane_t* plane = &planes[face->plane_id];

            // Check if the point lies on the face's plane (it's not strictly necessary to do this, but this check makes the whole function a lot faster)
            if (fabs(plane->pointDistance(point)) > 0.01)
                continue;

            Vec3 faceNormal = face->side ? -plane->normal : plane->normal;

            // Check if the point is located on one of the face's edges
            for (int edgeListIdx = 0; edgeListIdx < face->ledge_num; ++edgeListIdx)
            {
                int edgeIdx = edgeList[face->ledge_id + edgeListIdx];

                Vec3 v0, v1;
                if (edgeIdx > 0)
                {
                    const edge_t* edge = &edges[edgeIdx];
                    v0 = vertices[edge->vertex0].toVec();
                    v1 = vertices[edge->vertex1].toVec();
                }
                else
                {
                    const edge_t* edge = &edges[-edgeIdx];
                    v0 = vertices[edge->vertex1].toVec();
                    v1 = vertices[edge->vertex0].toVec();
                }

                Vec3 p0 = v0 - point;
                Vec3 p1 = v1 - point;
                double m0 = p0.magnitude();
                double m1 = p1.magnitude();

                if ((m0 * m1) <= 0.01)
                {
                    // Point is on one of the face's vertices, this is not a T-junction
                    break;
                }

                double dot = p0.dotProduct(p1) / (m0 * m1);
                if (dot <= -0.99)
                {
                    // Point is on one of the face's edges, in-between its two vertices. This is a T-junction.
                    Vec3 edgeDir = (v1 - v0).normalized();
                    Vec3 tangent = faceNormal.crossProduct(edgeDir);
                    outTangents.push_back(tangent);
                }
            }
        }

        return outTangents;
    }

} world_t;