# A larger level, moving sectors and failed optimisation attempts

I've made a few attempts to boost the performance of the 3D engine for the TI-83+ I'm working on with little success. I had previously failed to get any improvement by adding bounding boxes around each BSP node (the idea being that if a node falls outside the view you can discard it and, by extension, all of its children) but the act of transforming the bounding box to determine whether it was inside or outside the view was more CPU intensive than blindly handling the nodes whether they were inside the view or not.

A simpler test, I reckoned, would be to use bounding circles. These only have one point to transform, and determining whether they are in the view is one comparison to ensure that they're in front of the camera followed by one multiplication (by the constant √2) and two more comparisons to determine whether they are to the left or right of the camera's view; far simpler than a bounding box!

The bounding circles did cut down the number of BSP nodes that were handled each frame but the additional checks made the engine slightly slower in general than it had been before. In some circumstances it was slightly faster, but not enough to make a noticeable difference. The additional data per BSP node added over 900 bytes to the level data, too, so the attempted optimisation had to go.

The newly added rooms to the demo level

One tweak that did boost performance noticeably was to cache the projected X coordinate of each vertex. All vertices in the map have at least two walls connected to them and so are projected to the screen at least twice if within the view. I already had a table that was used to indicate whether a vertex had been transformed around the camera or not that frame so it was easy enough to add the X coordinate of the projected vertex to that table, adding around a 15% boost to the framerate.

Points are projected to the screen by dividing their X (left/right) or Z (up/down) component by their Y (depth) component. Division is slower than multiplication so I tried to calculate the reciprocal of the depth for the vertex then perform all subsequent projection operations by multiplying the X or Z component by this reciprocal. Unfortunately, this resulted in a lack of precision owing to my use of 16-bit fixed-point numbers (walls "wobbled" as you moved the camera) and performance was about the same as it had been before, so I rolled back the changes.

The block of screenshots in the above text shows a new region that has been added to the demo level, and the image below is a map of that level — fans of DOOM may notice that it's based on a small portion of E2M7 (The Spawning Vats).

Map of the level

This level now uses every one of the 256 walls that are available, so is probably a good indication of the maximum size of a single level (and at 6,626 bytes it's certainly rather taxing on the limited amount of memory in a TI-83+ calculator).

This is, however, the maximum size of a single level. It does not take long to load and unload levels, so it would be quite possible to construct a continuous level that appears larger by unloading the current one and loading a different one when the user moves to a particular region. This could be implemented in an obvious manner (such as the player stepping into a teleporter) or transparently (by moving the player into an identical copy of the room he left to hide the transition). The latter option also introduces the option of level geometry that would otherwise be impossible in a 2D-based engine, such as rooms above rooms. Special effects could also be tried, such as an infinite corridor that warps you back to the beginning when you reach its end.

However this feature is implemented, there would need to be some way to trigger the action. The above animated screenshot demonstrates the current trigger system which is used to set a sector in motion. A sector, in this instance, is a region with a particular floor height and ceiling height. Each wall indicates which sector is in front of it and which sector is behind it. Convex sub-sectors contain sets of walls and also indicate which sector they are part of, and are attached to the leaves of the BSP tree. Given a point, you can quickly find out which convex sub-sector it is in by walking the BSP tree. When you have found the convex sub-sector you can then look up its sector. This is currently used to set the player's height, as the sector tells you the floor height.

If you keep track of the player's sector each frame you can tell when they have moved from one sector to another. This then fires an event, reporting which sector the player used to be in and which they are in now. In the above screenshot, the platform is set to descend whenever the sector surrounding it is entered from any sector other than the platform itself (this is to stop it from automatically descending when the player walks off the top of the raised platform). It is also set to rise whenever the platform's own sector is entered. This produces a simple lift; doors are handled in a similar fashion elsewhere in the level.

If you'd like to try this demo on your calculator, you can download the binaries for the TI-83 and TI-83+ in Nostromo.zip. As ever, please back up any important files on your calculator before running the demo; it may well clear your RAM. For those without calculators, an animated screenshot is available.
Nov 30 2010 10:35 AM
Have you tried using (or do you use) some kind of "potentially visible set" which, for each sector (or group thereof) lists which other sectors might be visible from that sector? You could store a pointer in each sector to a list, and share the list between many sectors to save memory (possible over-estimating visible sectors in order to join similar-but-different lists), and that could significantly reduce the processing required when you have a map with distinct areas - a Z shaped hall could divide the map in two, such that only half the world is rendered depending on where you are in the hall.
Nov 30 2010 01:11 PM
I do not currently use any form of PVS, though have been considering it. If I break the level down into eight regions I could assign each node with one byte that flags which regions are contained within that node and another byte that flags which regions are potentially visible from that node. This data could be used to prune the BSP tree quite heavily, but I'm not sure if it would really help as the renderer stops when every column in the screen has been completed, which is likely to be before any of the definitely invisible (as opposed to the potentially visible) regions is visited.

One thing I didn't try was to only use the bounding circle around the convex sub-sectors only. It may be worth trying again, as this may be a faster way to discard sub-sectors consisting of more than one wall (currently each wall is checked in turn), yet won't slow down walking the BSP tree normally.
Nov 30 2010 05:28 PM
You mention that walls store which sectors are on each side. Do sectors store which walls make it up or which sectors share walls with it? Another approach I thought of is to use a simple breadth-first search to choose which sectors to process, starting with the one the player is in. Something like (semi-python):
```sectorsToRender = [GetSector(player.location)]
while (not bAllColumnsFull) and sectorsToRender:
nextSector = sectorsToRender.pop(0)
if not InView(next):
continue
Render(nextSector)

```
The "InView" check being optional, of course, and you'd need some way to check whether a sector was already processed. For the latter, you could use a bitmask for speed, but for the actual list of sectors to render, a pointer or index list (cyclic to make popping free and to avoid multiple allocations) would be better so you can maintain order.
Dec 01 2010 12:15 AM
Quote:
 Original post by Extrarius You mention that walls store which sectors are on each side. Do sectors store which walls make it up or which sectors share walls with it?

There are two distinct structures with confusingly similar names, sorry. A sub-sector is a small convex part of the map containing the list of walls that make it up, and is stored in a BSP tree leaf. A sector is a large region that can be any shape and is made up of sub-sectors. Sectors only define the floor and ceiling height. Sub-sectors reference the particular sector that they inside with an index, and each wall references which sector is in front of it and which sector is behind it — which I've just realised is redundant, as the sector in front of any wall is the sector the wall's sub-sector is in.

Sectors are not used in the rendering process beyond providing height information for the floor and ceiling when drawing individual walls.

Quote:
 Another approach I thought of is to use a simple breadth-first search to choose which sectors to process, starting with the one the player is in.

I'm afraid I'm not entirely sure how that technique would work, which may be down to my misinterpretation of your code. As far as I can tell it only uses the BSP tree to find the starting sub-sector, and then renders subsequent sub-sectors by using the shared walls between them to step from one sub-sector to ones which are further away. If you consider this map and that you are standing in the top room looking down you only have to jump through two rooms to get to the lower room if you go down the right but four rooms to get to the rectangular room in the middle. This would, at least in a simple implementation, render those two large rooms in the wrong order.