Search / View

[ReD NeCKersoN]

I decided to paste this here since it is no longer at it's old website. -ReD-

(c) William 'SmallPileofGibs' Joseph
Thanks to MrElusive and Maj

1. Geometry Definitions

A Point A in a map is stored as a single set of coordinates (X,Y,Z) using Integer (whole number) arbitrary units.
A Line AB is represented by two Points A and B with a straight line of infinite extent passing through both points.
A Plane ABC is represented by three Points, A B and C with a 2-Dimensional (flat) surface of infinite extent passing through all three points. A plane has a front and a back.
An Area is a finite part of a Plane bounded by Lines. A Polygon is an Area bounded by 3 or more Lines
A Volume is a finite part of a 3-Dimensional space. It is bounded by four or more Planes.

An Axial Plane is a Plane perpendicular to one of the grid axes, X Y or Z. A Plane is perpendicular to the X axis when all points on the Plane have the same X coordinate, eg. X=0.

A Vertex is a Point (plural Vertices). A Vertex in a BSP is stored as a single set of coordinates (X,Y,Z) using Floating Point (decimal fractions) arbitrary units.
A Triangle is a Polygon with three Vertices (plural Triangles or "Tris")
A Strip is an arrangement of multiple Triangles in a strip shape, each new Triangle sharing Vertices with an adjacent Triangle.
A Fan is an arrangement of multiple Triangles in a fan shape, each new Triangle sharing Vertices with an adjacent Triangle.

2. Dimensions: Areas

Starting with a Plane seen in 2D we can draw a single Line of infinite length dividing the Plane in two. Adding more non-parallel Lines allows us to define an Area on the Plane. An Area bounded by three or more Lines in this way is always a convex Polygon. It is impossible to bound a non-convex Polygon with straight lines of infinite length.

3. Dimensions: Volumes

Starting with an infinite Volume of space, imagine a Plane dividing it into two child Volumes, front and back. Four or more non-parallel Planes are required to define a finite Volume in an infinite space. A finite Volume defined by four or more Planes is always a convex Volume.

Map Definitions

Brushes

A brush is a convex Volume. This Volume is always bounded by four or more Planes, each Plane forming one Face of the Brush . Each Brush Face has a set of Texture, Surface and Content properties. Texture properties are a small number of values defining: ONE Shader Name, XYZ Scale/Stretch values, rotation. These values are stored along with each face in the mapname.map file. One Brush Face can only have one set of Texture properties. Surface and Content properties are stored in an external Shader script. However, some Content properties may still be stored along with the Texture properties in the mapname.map file, one example being detail.

Bezier Patch Surfaces

Bezier Patches or "curves" are one type of Parametric Surface. A parametric surface is a surface with a shape defined by a set of parameters, so the shape of the surface can change depending on the values of the parameters. For Bezier Patches in Quake 3, the parameter is the LOD, or Level Of Detail. Patches in Quake 3 are rendered with triangles, so the curves must be 'tessellated' (subdivided) into a number of triangles. The higher the LOD value, the more the curve is subdivided, and the more triangles are created in tessellation. The LOD can be set to change with the viewer's distance from the Patch, decreasing as they get further away. In Q3 "r_lodCurveError" controls how much the LOD changes with distance, and "r_subdivisions" fixes the maximum LOD for all curves. A Patch is stored as a 2-dimensional matrix of points. A 2-dimensional matrix is a table containing sets of values arranged in rows and columns. Each point is stored as two sets of values. One set contains the XYZ coordinates defining the location of the point in the 3-dimensional volume of the map. The other set contains the UV coordinates defining the location of that point on the 2-dimensional area of the Shader. One Patch can only have one Shader, for the same reason one brush face can only have one Shader.

Shaders

A Shader is a collection of properties that controls how a surface is treated by the compilers, and how the surface is rendered by the Quake 3 engine. Every Surface has a default set of Shader properties, unless an external shader script is specified.

Combinations of a number of pre-defined properties control the way the compiler treats the surface. See the Shader Manual for more information. "SurfaceParm" is the shader keyword for universal shader properties. SurfaceParms are either Brush "Content" Properties or Brush "Surface" Properties. A Content Property applies to the contents of an entire Brush if the first face of the brush (face 0) has that property. Because of this, identical Content Properties should be applied to all faces of a brush to avoid unpredictable results. A Surface Property applies only to the surface with that property.

Relevant SurfaceParms (for full list see the shader manual)

Content:
solid(default contents unless alternative specified. Brush is solid, casts shadows, clips players and all entities)
nonsolid (Brush is not solid)
structural (default contents unless alternative specified. Brushes split BSP, but only block visibility if not trans)
detail (Brush faces do not split BSP or block visibility)
playerclip (Brush clips players only, faces do not split BSP)
trans (Brush does not cast shadows)

Surface:
nodraw (Face removed at compile)
nolightmap (Lightmap not created for face)

SurfaceParm combinations in common shaders:

DEFAULT - Content: solid, structural - Surface: Visible, has lightmap.

common/caulk - Content: solid, structural - Surface: nodraw, nolightmap
common/hint - Content: nonsolid, structural, trans - Surface: nodraw, nolightmap
common/nodrawnonsolid - Content: nonsolid, structural - Surface: nodraw, nolightmap
common/clip - Content: playerclip, trans - Surface: nodraw, nolightmap
common/weapclip - Content: solid, trans - Surface: nodraw, nolightmap

Entities

A Quake3 map is a collection of Entities, numbered from 0 upwards. Some Entities can have Brushes and Bezier Patch Surfaces belonging to them. All Brushes and Bezier Patch Surfaces belong to the Worldspawn Entity (entity 0) by default. The Worldspawn is the solid hull around the map (the game "World"), containing all other entities within the space inside. All entities in a map have an Origin Point and an Axis-Aligned bounding Volume (or bounding-box). The Worldspawn's Origin is the point (0,0,0).
Each entity has a set of Properties. These properties are predefined "Keys", each Key having a variable value, which can be numerical values or a string of text.

Mapobjects

Each Mapobject is a collection of triangle surfaces arranged in Strips. The Strips are stored as one frame in a single objectname.md3 file. A Mapobject strip is similar to a Bezier Patch surface in that it cannot be structural and can only have a single shader. Each Mapobject strip has a shader name and and a set of texture coordinates assigned to it, which are stored in the objectname.md3. The md3 format is the same as the format used for item and player models in Quake3, so Mapobjects require no pre-processing other than being added to the BSP at the first compile stage.
Mapobject strips cannot have content properties, and do not have a lightmap, but they can emit light or cast shadows, depending on the strip's shader properties.




The Q3 compile process has four stages: BSP, VIS, LIGHT, BSPC.

Stage 1. "BSP" (q3map mapname.map)
mapname.bsp is the format that compiled Q3 levels are stored as. The important part of this process is the actual creation of the BSP Tree from the brushes of a map.


What does the BSP stage do?

The player-navigable space inside the World is split into convex volumes bounded by planes. These convex volumes are called Leaf Nodes. The Leaf Nodes are stored in a binary tree called a BSP Tree.

Note: The "player-navigable space" inside the World means: everywhere in the game World that isn't a brush which is both solid and structural. The area the player can navigate around in the World using noclip, without passing through a Solid structural Brush. All World Brushes are Solid and structural unless they have a different content property set. Non-structural content properties are detail, playerclip, trans. Non-Solid properties are WATER, LAVA, nonsolid
detail brushes are set by surfaceparm detail, or by making the brush detail in Radiant (viewing detail is toggled by ctrl+d). Some of the common/ shaders are structural, but not visible, including: CAULK, HINT, nodrawnonsolid, AREAPORTAL. The rest are either non-structural, are only used on Entities, or are not commonly used in maps.

How and why is the BSP created?

A map is a 3-dimensional volume of space extending +/- 4096 units from the origin in X Y and Z, containing smaller solid convex volumes bounded by planes (structural brushes).
The goal is to use the fewest splits possible to split the space of the map into convex volumes, each of which do not contain any structural brushes.
A simple cube room is a convex volume bounded by six planes. Convex volumes are important for visibility, because it is simple and fast to determine whether two convex volumes can see one another.
These convex volumes are stored as Leaf Nodes in a binary tree, making it easy to determine which Leaf Node the viewpoint or objects (entities, tris, patches) are in.
This is called a Binary Space Partitioning Tree, or BSP Tree.

A BSP tree is produced using a recursive operation. A recursive operation is one that causes itself to repeat within itself.
The operation is performed on a Volume, starting with the entire map as a single Volume:
If the Volume contains structural Brushes...
Then split the volume along the Plane of the Face of one structural Brush. Continue to the first child Volume produced and repeat the operation.
Else, if the Volume does not contain structural Brushes, it contains no Planes for splitting, and a Leaf Node is created for the volume.
Then return to the next child Volume up the tree and repeat the operation. If there is no child Volume, end the operation.

Note: Each split-plane does not always divide the volume exactly in half. Axial split-planes are chosen before non-axial split-planes. The split-plane which cuts through the maximum number of brushes is chosen.
It is important to split the tree roughly in half each time in order that each Leaf Node is roughly the same distance from the tree's root, balancing the branches of the tree.

How can I control the BSP splits? (a way to use detail and Hint brushes)

ALL structural brush face-planes, Including completely hidden or nodraw faces, are possible candidates to split the BSP and create extra Leaf Nodes. Leaf Nodes are currently NEVER merged, even if the result of the merge would be a new convex leaf. The ideal situation is to have all structural brush faces axial and perpendicular to the grid lines every 128 units. Any more complex brushes can be made detail, and all hidden structural or detail Brush faces can be made nodraw as well, by applying the common/caulk shader. The effect is similar to using Bezier Patch surfaces, which also do not block vis or have any other visible faces than the front surface.

Hint Brushes are structural, trans, and nonsolid. This means they are totally invisible in a compiled Quake3 level, but their Face-Planes are used to split the BSP like other structural Brush Face. A large Axial Hint brush face will be an ideal candidate to be used for a BSP Split. Adding Hints with Axial faces (perpendicular to the 128-unit grid lines) aligned with other Axial Planes from structural Brush faces, minimises the number of extra split-Planes and Leaf Nodes.

Basing a map on the 128-unit grid allows you to hugely simplify the visibility process. If the leaf nodes are all 128-unit cubes, its very easy for the designer to predict whether one area can see into another, and place simple axial hint brushes to reduce visibility with minimal increase in vis pre-processing time. As detail brushes and bezier patch surfaces do not affect the shape of nodes they can be used to build up complex architecture in front of simple axial structural nodraw brushes

What is a leak?

A quake3 map is a hollow space made up from a number of convex volumes (Leaf Nodes) contained within a solid outer hull. The Leaf Nodes "outside" the map are discarded (pruned =) after the BSP Tree is created.
There is a "leak" if you cannot separate the Entities on the inside from the "void" outside the radiant grid. If there is a leak q3map generates a detailed error message (seen if you use q3map -v) and records the path of the leak to the Pointfile "mapname.lin". Usually a leak will be displayed in Radiant as a path from the origin of an entity to a Leaf Node touching the area outside the radiant grid without passing through a solid brush.

What is the .prt file?

The Leaf Nodes remaining in the BSP Tree after the outside Leaf Nodes are removed are bounded either by other nodes or by structural brush faces. A Portal is created for every face of a Leaf Node that is bounded by another Leaf Node. Each Portal is like a window from one node looking outwards into another. The Portal information is not needed in the BSP, but it is essential to VIS, so it is stored in the portal file "mapname.prt".

How are the brushes/patches turned into triangles?

For brushes, a convex polygon is defined for the area of each visible brush-face that touches one or more Convex Leaf Nodes. Brush-faces with surfaceParm nodraw are ignored. Extra vertices on are created on the edges of each polygon where other polygon vertices meet the edge and create a T-junction. The extra vertices 'fix' the T-junction by turning it into a point where three polygon edges meet. If a vertex lies on an edge that cannot be split, there will be a tiny crack in the hull of the map (along the edge that cannot be split). These tiny cracks are known as "sparklies", because of the way they look when a bright surface is drawn behind the crack and 'sparkles' through it. Finally, each polygon is divided into triangles and stored as an OpenGL primitive called a Triangle-Strip, or as a Triangle-Fan in some cases.

Patch Surfaces are treated as a collection of points during the BSP compile, and are turned into Triangle-Strips when the map is loaded. For this reason, T-junctions involving Patch-surfaces cannot be fixed automatically.

Texture coordinates are generated for each vertex. Texture coordinates are two values U and V (UV Coordinates or 'UVs') which specify the position of the vertex on the texture image as a percentage. These coordinates are normalized decimal (Floating Point) values between 0 and 1: If the texture dimension are 256*128, and a vertex has the UV coords (0.5,0.75), the texel (texture pixel) at 50% of 256 horizontally and 75% of 128 vertically will be drawn on the vertex.
Note: each brush-face or patch-surface is a separate primitive, enabling it to have its own set of Texture Coordinates and Shader properties.



Stage 2. "VIS" (q3map -vis mapname.bsp) bsp_fullvis
VIS is short for Visibility. The relevant part of this process is the creation of the PVS Table for the Portals in the map.
As the player's viewpoint moves around a FULLY vis'ed bsp different areas become visible or hidden, depending on which area the viewpoint is in.

How is the PVS created?

Every Portal in the portal file is checked against every other Portal for visibility. Portal 1 is visible to Portal 2 if a straight line of sight can be drawn between any part of Portal 1 and Portal 2 without passing through a solid structural brush. Every Portal then gets a list of the other Portals that can be seen from it. This information is the Potentially Visible Set and is stored in the PVS Table.

What does -vis -fast do?

Otherwise know as "bsp_fastvis", using the -vis -fast option does not create a PVS, leaving every Portal visible to every other Portal.

How do Portals affect visibility?

Every Leaf Node has one or more Portals (unless there is only one node in the BSP tree). If a Portal belonging to Node 1 can see a Portal belonging to Node 2, Node 1 is visible to Node 2. When the player Viewpoint is anywhere in Node 1, every object in Node 2 is drawn. When the player Viewpoint is in Leaf Node x, every object in every other Leaf Node visible from x will be drawn.
Objects include Brush Faces, Bezier Patches, Entities. One object can be in more than one Leaf Node at the same time.
A Brush Face is drawn when any part of the face is touching a visible Leaf Node.
A Bezier patch is drawn when any of its control points are touching a visible Leaf Node.
An entity is drawn when any part of its bounding box is touching a visible Leaf Node.

To summarise: Effectively, solid structural brushes block visibility between the contents of Leaf Nodes. Curves, detail brushes and Entities do not block visibility. Visibility between two areas will only be blocked when both areas are completely hidden from each other. Generally, the more Leaf Nodes visible from the Leaf containing the Viewpoint, the more objects will be drawn. The aim when optimising for visibility, is to have the smallest number of other Leaf Nodes visible from any one Leaf Node.
More of the map will be drawn if the BSP has a small number of large leaf Nodes, or an innefficient arrangement of Leaf Nodes.
You can reduce the number of Leaf Nodes created by reducing the number of unique structural Planes in the map, by making all unnecessary structural Face-Planes into detail Brushes.
You can control visibility by placing Hints to create the Leaf Nodes and their Portals exactly where you want them to be, splitting the space into more Leaf Nodes only in areas where they are needed.

How can I make VIS more efficient? (and reduce -vis processing time)

The time -vis takes is roughly proportional to the number of Portals in the map. The number of portals is displayed when you start VIS, as "numportals xxxx". The visdatasize is the size the PVS table takes up in the mapname.bsp file - this is limited to around 2MB.
A lot of Leaf Nodes means a lot of Portals. A lot of Portals means a long vis time.
The number of Leaf Nodes depends entirely on the complexity of the BSP.
Solution: detail brushes - Making a brush detail will stop it from affecting the BSP Tree, reducing the number of Leaf Nodes formed.
To make any brush a detail brush, select it and press ctrl+m or Selection > Make detail. Toggle viewing of detail brushes with ctrl+D or use the View > Show menu.

The drawback of wide use of detail is that over-simplifying the Leaf Nodes can hurt your visibility efficiency (see visibility summary).
Solution: HINT brushes - A Hint brush (common/hint) will be invisible in Q3, but is structural, so it will affect the BSP Tree and create more Leaf Nodes. This gives you a lot of control over WHERE the Leaf Nodes are created. Placing a hint brush in an area of open space will force creation of a Leaf Node within the area of that hint brush. Hints can also intersect with other structural solid brushes or Hints, creating multiple Leaf Nodes or isolating groups of Leaf Nodes.
Hint brushes use a shader which makes the brushes nonsolid and nodraw, called common/hint.

Hints are best used to make large axial cuts along planes shared by other structural brushes, to maximise the amount of area hidden by each vis-blocking structural brush, by minimising the number and size of the Leaf Nodes visible.

Intelligent use of detail and Hint brushes in combination can reduce vis time and r_speeds in almost any map. However the map must be designed from the start with this in mind. Redoing an inneffiently made map is a lot of work.
Note: Making a brush detail will stop it from blocking visibility, so don't make your vis-blocking walls into detail brushes.



Stage 3. "LIGHT" (q3map -light mapname.bsp)
This is the lighting stage, where lightmaps are generated for every world surface in the map. It has no effect on bsp, hints, vis or r_speeds.

How do lightmaps work?

The Q3map -light algorithm creates a lightmap pixel for every 16 game world units on a brush, and every 20 units on a patch, stored in 128*128 pages. The lightmaps are 24bit RGB, and are blended with the textures by multiplying the lightmap RGB values with the RGB values of the texture (see the Shader Manual: blendfunc filter).

How are lightmaps generated?

All lightmap pixels start pure black (RGB 0 0 0). A straight line is traced from the centre of each lightmap pixel towards the origin of each point light source. The distance between the pixel and the light source decides the brightness the light adds to the RGB values of that pixel. If the line is blocked by any visible non-transparent brush, the light source does not have any effect on the lightmap pixel. The time taken by the LIGHT stage is proportional the number of lightmap pixels multiplied by the number of point light sources.

What about surface lights?

Surface lights are subdivided using the q3map_lightsubdivide value (default 64), creating a point light source on the surface every 64 units. These are used in the light calculations in the same way as other point light sources.

What does -light -extra do?

Using the -extra option a straight line is traced from four extra points on each lightmap pixel in addition to the original one. The average of the result is taken, which helps to smooth out jagged shadows. Unfortunately it also makes -light take five times as long.



Stage 4. "BSPC" (bspc -bsp2aas mapname.bsp)
This stage uses the bspc tool, and generates an Area file mapname.aas. The Area file is used by bots to navigate the map.
BSPC is a separate process from the other compile stages, and and it has no effect on and ignores any information created in those stages. BSPC requires only a mapname.bsp which does not leak.

How does BSPC interpret the map?

BSPC uses the Brush Face information in the mapname.bsp to make a list of Faces which clip the bots. Bezier Patches are tessellated into into planar Faces called "curve brushes" and are then treated the same as other Brush Faces. Face content properties which clip bots include: structural (all brushes or curves are structural by default), detail, Trans, playerclip. All Faces which clip the player are considered solid to bots, so they are all treated identically as "solid" and any other content property is forgotten.

What is the "Brush CSG" stage of BSPC?

During this stage unnecessary Brushes are discarded. If any Brush is completely contained within another Brush it will be discarded, by CSG-Subtracting the container brush from the contained brush. The more brushes BSPC ignores the better - use large simple clip brushes to completely contain any complex architecture made from multiple brushes.

How is the area file created?

BSPC splits the bot-navigable space in the map up into convex volumes called Areas, in a process similar to q3map BSP. Each Area must be convex, like the Leaf Nodes in a BSP Tree. BSPC also tries to minimise the number of Areas by merging any two Areas where the result is another convex Area. BSPC stores the Areas in groups called Clusters, in the Area file "mapname.aas". A Cluster is a group of connected Areas, separated from other Clusters by Solid walls or Clusterportals. Without Clusterportals, most maps will have a single large Cluster of Areas.
You can see the Cluster/area info in bspc.log after creating the area file.

Note: Bot-navigable space in a map is anywhere on the inside that isn't a solid player-clipping brush. Solid player-clipping brush content properties include: solid(default for all brushes unless nonsolid), playerclip.

How do Bots use the area file

Bots use the Areas in the Area file to navigate between Entities in the map. At any point in time they have to be thinking about all the areas in whichever Cluster they are in. If there are a large number of areas in that Cluster, the bots' cpu usage will be noticeably larger while they are in it. More than 1000 areas in the Cluster gives a very noticable performance hit - below 500 is much better, and the smaller the number of areas in the largest Cluster the better.

How do I make Clusterportals?

Clusterportal Brushes are used to control the way BSPC creates Clusters, by adding potential Clusterportals for BSPC to consider.
Clusterportal Brushes should not be confused with Areaportal Brushes as there are a few important differences in their use. Clusterportal Brushes should be thin axial brushes, up to 32 units thick. For a Clusterportal brush to be accepted by BSPC as a ClusterPortal it must have two opposite faces touching two separate Clusters. It must be placed in a doorway or a horizontal passage where bots can freely walk through it rather than falling through vertically. The two opposite faces should be identical in shape and size, and the other four faces should be against solid brushes or clip brushes.

Note: In the same way as Areaportals, Clusterportals must be used to entirely separate parts of the map from each other. If a bot can reach area 2 from area 1 (via any other areas) without passing through a Clusterportal, both areas are connected and will be part of the same Cluster.