3D Coding TAT - Volume Meshes (Distorted Cube Arrays)

1: Terminology:

VOLUME - a 3d area with a width, a height and a depth, the space inside an object's skin.

LAYER - something of a single thickness (like a page from a book, or floor from a building or in this section a floor or ceiling array)

MESH - a single 2d layer of connected cells which can be moved and bent into different shapes just like a wire fence meshing.

2: A Similiar Method

Another way to render a scene which shares some of the inlet methods and its convex volume ideas is this:

1. Begin with an equally spaced array of cube cells (like the NOAH flood-fill or Wolfenstein map).

```                e.g.            plan view

+---+---+---+---+---+...
|   |   |   |   |   |
|   |   |   |   |   |
+---+---+---+---+---+...
|   |   |   |   |   |
|   |   |   |   |   |
+---+---+---+---+---+...
|   |   |   |   |   |
|   |   |   |   |   |
+---+---+---+---+---+...
.   .   .   .   .   .```

NOTE: Each vertex is shared by FOUR map cells.

2. Now distort the corner vertex points into something like a "volume mesh" of neighbouring cells (i.e. grab a vertex and move it north, south, west, east, up or down).

e.g. plan view

```                        +---+---+---+---+---+...
|   |   |   |   |   |
|   |   |   |   |   |
+---+---+---+---+---+...
|   |   |   |   |   |
|   |   |    |  |   |
+---+---+--   |/+---+...
|   |   |  ---+ |   |
|   |   |    /  |   |
+---+---+---+---+---+...
.   .   .   .   .   .```

Of course you can also drag the vertex point of the the other layers to create sloping floors and ceilings, small tunnels or a high cathedral roof. This would need 2 mesh layers (one for the floor and one for the ceiling). You don't have to keep the vertices vertical, you can move one in or out to create sloped walls.

This has some attractive features and is probably quite a bit easier to implement than proper inlet rendering. For a start we know how many sides each cell has and how many cells can be connected this it 4 (6 if multi-storey). Also as the vertices are shared by 4 neighbouring cells this can greatly cut down on the number of rotation and perspective transformations.

Yet again we find ourselves back in the domain of the all-mighty CUBE. Each cell is (if you haven't guessed) a cube with 8 vertices and 6 faces. If we apply the inlet idea of perfect glass windows to connect neighbouring cells then we have the basics of a complex scene renderer. We can knock down cell walls to create long corridors or vast areas. If we use a 3d array (more than 2 mesh layers) then we can also create vertical lift shafts, holes in the ground and rooms above rooms.

3: DOOM 3 ?

With a single layer mesh it 'might' be possible to write a simple DOOM render engine where walls are ALWAYS vertical only their X and Z coordinates change. All that is needed is to specify the floor and ceiling height of each cell, then stairs, cliffs and ledges can be done. You may also want to store a lighting level for each cell for dark rooms and blinking lights. And a floor type could be described as well (lava, water, gravel etc.). Crushing ceiling and lifts might also be desired.

But this list of parameters for every map cell is starting to get very big especially if you have a large map. Also it takes time to process each of these parameters (blink the lights, move the lift...). If you create very large lifts for example with many small volumes joined together then you are doing all the lift code for each volume individually. Also what happens if you wish to turn a vast area into a pool of lava or create multiple crushing ceiling with a single switch? One way would be to create a list of each cell to be changed this way we could just process the list and modify the attribute of each cell (turn it to lava etc.). A much better solution is to define a small number of region descriptions which define the floor type, lift position, lighting level and so on and then store a byte index within the map mesh. This way we can process ALL the regions once (possibly every game loop) and then for each cell in our mesh we just look-up the region's status.

e.g.

```   the map-mesh                   region descriptions
----------------------
+---+---+---+---+---+...
| A | A | A | - | - |            A - lift, height etc..
|   |   |   |   |   |            B - lava, health -10, light 150%
+---+---+---+---+---+...         C - water
| B | A | D | C | - |            D - normal floor
|   |   |   |   |   |            E - crushing ceiling, blinks
+---+---+---+---+---+...
| B | A | E | - | - |
|   |   |   |   |   |
+---+---+---+---+---+...
.   .   .   .   .   .```

So in the above diagram we define "region" tokens within each cell on map-mesh (our array). Each token is used to index into the region descriptions to discover what type of flooring, lighting, injury and possibly animation should be done. In this way many unconnected cells can be sync'd together or given indentical attributes. In the above diagram the A token is used to describe a T-shaped lift which can be updated once by processing description A. If we changed it's description to say lava, then the entire lift has become a red-hot platform of heat. Nice eh?

4: Now the catch

Like all semi-good ideas, there is a catch or two.

Some depth-sorting might be required because the vertices can be at different angles to one another and their position within the mesh won't guarantee correct depth-sorting.

Designing a level will be harder because we must start off with an equally spaced grid of 3d cells and them deform it to make a more interesting environment. But what happens when the designer wants to create a structure of some kind and needs a vertex in the middle of a volume cells? They can't.

One solution would be to insert vertices along both (or all 3) axises and split any sides which cross it. But this would create a vast amount of work, not only for the level-editor but would probably slow down the engine as there would be more vertices to handle and more polygons.

Another solution is to go back to the inlet method of describing connected cells using links from each window/door side which points to its neighbour. But this would remove some of the advantages of using an array. And at the same time it would remove some of its resstrictions too.

Or you could describe object tokens within the mesh and draw 3d objects whenever for each occupied mesh cell.

Oh well, life eh?