3D Coding TAT - The Missing Link? "Inlet" Rendering
Another idea which has held my short attention span for some time is convex, linked rooms or "inlet rendering" as I like to call it. This looks the most promising form of rendering at the moment (mostly because I am unable to come up with a better method) and elegantly it squats many-a-fly with the same rolled up newspaper. The method behind it is very easy, linked-lists! But the power and promise of very fast rendering with extra features thrown in with minimum effort makes it worth investigating. It can easily be used for lifts in buildings, water effects, force fields, coloured lighting and a heap of other stuff that I haven't got round to hype up yet.
This originally came out of extending the "Noah" rendering (flood-fill) method, but this will (hopefully) allow true 3d environments with smoked/coloured glass and water effects without too much work. The main problem with flood-filling is that of tracing the map boundary, the objects within each cell must be decoded and the appropriate action taken. With true 3d levels (rooms above and below) storage can sometimes be a real problem. The obvious way is to extend the 2d map array into 3 dimensions, so instead of a 2d array we have a 3d array. If levels are designed to fill entirely within a cube shaped map array then this isn't too bad, but most levels have large areas of empty space beyond the real environment (such as behind the walls in a corridor) this can lead to alot of wasted memory space. One solution is to use this space in the 3d level array for sub-levels or secret transporter destination rooms.
Now I will describe how linked-lists levels might work. Think of the easiest 3d environment, yeah, our old friend, "the cube". But this time we are inside the cube and imagine that there is NO outside to it, the interior of the cube is the entire game universe. This only needs 6 surfaces. Usually the cube's interior is never seen and so never defined only the 6 exterior surfaces/polygons are defined and rendered. But in INLET RENDERING the opposite is true. We only ever see the inside, never the outside. Imagine being trapped inside a bubble, there is only 1 surface and no matter in which direction you look you will always see a wall and the wall always disappears beyond your peripheral view (around your head, where your eye can't see). Bubbles are hard to draw so lets return to the simpler cube. An important thing to note about the cube is that it is CONVEX in every direction.
1: CAVE'd or VEX'd ?
In my understanding CONVEX is something which is like a bubble or cube - the angles between two interior surfaces are always less or equal to 180°. Or if you stood and looked directly along each interior surface then they would slope upwards and over your head. If we walked along each one of the below surface lines then we would always meet an adjoining surface which slopes upwards like the inside of a bubble or cube.
This means that NO surface is hidden by any other surface - this means NO depth-sorting yipee!
CONVEX.
---------
side cross-section view
________________
Ú-------<------¿ \ \
³ ³ \ \
³ ^ \ \
³ ³ \ /
³ view -> ³ \ view -> /
À--------------- \__________/
CONCAVE
---------
And CONCAVE volumes have interior surfaces which have one or more angles which are more than 180°.
side cross-section view
Ú--<-¿
³ ³ _____________________
Ú----<-----x ³ \ \
³ ³ \ \
³ ^ \ x____\
³ ³ \ /
³ view -> ³ \ view -> /
À--------------- \__________/
In both the above diagrams 'x' marks an angle of more than 180°. If we walked along each surface then we would meet a part of the volume where it dips away underneath our feet like a hole in the ground. This means that a surface can be hidden from certain view points in the volume, and this means depth sorting.
2: CONVEX Rulez
I haven't seen any mathematical proof for the following statement, it is just common sense which I believe to be true (until proven otherwise) - don't sue me.
To my knowledge, a CONVEX volume NEVER needs depth-sorting because no surfaces are ever hidden by other surfaces. For every position within the convex volume and for every direction this is true. So no matter what position within the convex volume and no matter which direction you are facing you will never see a partially hidden or completely hidden surface (except those behind you, of course).
The above is NOT true for CONCAVE volumes because for certain positions and directions we can see a surface which ends at the top of a hill where the connected surface can not be seen (it is hidden behind the hill). Of course if we move further around the volume then that surface will appear.
3: CONVEX - SO WHAT ?
Most other 3d engines need some form of depth sorting or BSP structure which can handle polygons/surfaces which are partially or entirely obscured by others. This happens when a CONCAVE environment needs to be modelled like a door-frame which connects one room to another.
e.g.
plan view
Ú-------------------¿ Ú-------------¿
³ ³ a³ ³
³ À----- ³ back
c³ V ---> room 1 door room2 ³
³ Ú----¿ ³ wall
³ ³ b³ ³
À-------------------- À--------------
In the above H shaped diagram both room1 and room2 are convex and so is the door-frame which connects both. If we are at the viewpoint V then some kind of depth-sorting is required so that the back wall of room2 is drawn before any others. This way the closest walls are drawn last. In this tiny example a total of 12 walls need to be sorted, of which 3 would be considered as hidden (a, b and c).
It's the door-frame which makes the above diagram CONCAVE.
4: Is that a lightbulb ?
We could just define our levels as 1 convex room, but that would be very crap. Suppose we kept the above H shaped level with two rooms connected by a doorway and we already know it's a concave shape, but let's close the door to seal off the other room. Now we have a CONVEX room! That is good news from a rendering point. But if we added an alcove to our sealled off room or a recessed area in one of the walls then we would be back with a CONCAVE volume again.
5: Where's these LINKED-LISTS ?
The "Noah" method flooded each area and followed those which a connection into another area could be made. But what happens if we have very large rooms or open areas? This flood-fill would be very costly. We would be filling a large area even though we didn't need to, all we want to the find where the wall boundaries are. One way could be to modify the flood-fill to only follow edges this is very simple to do. It is often called an "Edge-follow" or "Boundary Trace" algorithm. But it does cause a problem which anyone who has ever written a version of the classic Pac-man will know too well. The problem of islands within a map, where two or more walls are not connected together. Imagine that you are inside a room with a central pillar and you walked around the room keeping a wall by your left side. After a while you are back to the starting point, but you still haven't found the central post. This would occur in the circular list method, we would never get to the central-post and so we wouldn't draw it.
Ignoring the 'island' problem for a moment I will comment on a method which is similar to the edge-follow method but uses linked-lists for speed. What we need to do is follow the walls which mark the environment's boundary. This is a case of tracing the path of connected polygon surfaces.
In the case of a cube we could trace like this :
b
Ú--------¿
³ ³
³ ^ ³
a³ ³ ³c plan view
³ view ³
À---------
d
First we could draw polygon wall a and then wall b and finally wall c. We don't bother with wall d because it is behind our viewpoint and so ignored.
As we don't want to have to search lots of polygons to find which one connects to polygon a along it's edge then we can used a LINKED-LIST. For each edge of a polygon we store a pointer link which is the address of the connected polygon which shares the same edge.
clockwise right
Polygon 'Link'
--------- --------
a b
b c
c d
d a
So each 'Link' points to the neighbouring right wall.
NOTE: We have created a circular list of the entire volume simply be pointing the last edge of polygon wall d back to polygon wall a.
Now all we need is the address of a starting wall and then render each one and use this link to immediately find its neighbouring wall. As a bonus we can even use the same edge slope to draw the next wall without having to recalculate it. This should help remove pixel gaps between connected walls.
6: Two way system
There is a problem with the above 'circular' link method. What happens if we need to find the neighbouring wall to the left of the current one? We could search the entire list until we found one whose link is that of our current one but this can be slow if there are many walls in the chain.
It is much better to use another link which points to the left neighbour. So now we can follow the links clockwize to find the next right wall OR anti-clockwize to find the next neighbouring left wall. Now our 3d engine can be given a starting wall address and it can trace walls left or right until either the screen clipping limit has been crossed or the Z view plane had been encountered, at this stage we can stop rendering.
b
plan view Ú--------¿
³ ³
³ ^ ³
a³ ³ ³c
----------------³ view ³-------------- view/projection Z plane
Ú---- À--------¿ (the 2d screen !)
³ ³
³ ³
³ ³
Ú----- ³
³ Ú---------
³ ³
³ ³
À------------------
In the above diagram we are facing north and if we only have the address of wall b to render the environment our engine could do something like this:
Start_Wall = b
If we handle walls in a left to right order this will mean our left & right links will be the StartVertex and EndVertex respectively.
StartVertex EndVertex
o------>------o
^
³
view
In this pseudo-code I will deal with DOOM like walls where they are always vertical as this makes explaining things easier because we can think of the 3d environment as being viewed from above as the plan-view of a series of connected lines.
First make sure our starting wall is visible (i.e. facing in our direction) and if not then follow the chain of links until we find one that is. This deals with a change of direction (when we turn our heads) and so makes sure our 'Start_Wall' is always pointing to a visible wall facing us. Of course this could be handled in your movement code and only ever checked when our direction/position is changed.
WHILE Start_Wall is not Visible
Start_Wall = Start_Wall[ left_link ]
WEND
Now that we have corrected any invisible starting wall (caused by a change of direction) we can begin to render. We can begin in either a left or right order, I will do clockwise first but the order is not important. We could have searched for a starting wall which was outside our left view edge and drawn each wall until we ended up outside the right view edge, but it is often very useful to know what wall you are facing (activating buttons, shooting etc.).
Current_Wall = Start_Wall
WHILE Current_Wall is visible...
AND is not right clipped...
AND does not cut Z viewing plane
Draw_and_Clip_Polygon( Current_Wall )
Current_Wall = Current_wall[ right_link ]
WEND
And a similar thing can be done for an anti-clockwise order (draw until we reach the left view edge of the screen).
Current_Wall = Start_Wall
WHILE Current_Wall is visible...
AND is not left clipped...
AND does not cut Z viewing plane
Draw_and_Clip_Polygon( Current_Wall )
Current_Wall = Current_Wall[ left_link]
WEND
That's basically it! We just follow each link until we encounter a clipped wall (either viewing-window clipped or Z view-plane clipped). The linked-list approach makes this possible with the minimum of fuss and CPU time. We could even totally remove walls by taking them out of the chain or possibly insert new ones for dented walls or a nice time-n-space portal effect.
7: Bonus
There are a few more goodies which are made available by using the linked-list method.
1. Memory consumption isn't too bad, just an extra link-list address for each polygon edge, this is far better than the map/array method as no memory is wasted. It allows much bigger levels simply by placing vertices further apart and to any value not just to the map-cell boundary.
2. Vertices CAN be moved to allow for morphing of levels As long as rooms are still CONVEX after the vertices have been moved. This can be overcome by building large rooms out of triangle shaped parts - this makes it impossible to create CONCAVE rooms, so they are still CONVEX, which is good news.
8: Yeah, but wot about CONCAVE ?
Remember the "light bulb" question? The problem of a CONCAVE level was side-stepped by closing the door and hiding from the problem (hee hee). But in fact this is an elegant solution and even allows other groovy effects for free. Remember that the door-way was the cause of the problem, so shutting it allowed us to pretend that it was just another polygon wall like all the others. So the room is made convex. We can describe the door as a transparent wall made of glass like a window, or "INLET".
The room is rendered as normal, polygon by polygon until an "INLET" is found. It is stored in a list, if the polygon is transparent it isn't drawn, it's neighbouring link is used and rendering continues until the entire room has been done. Now the list of INLETs is examined and possibly rendered depending on whether it is open or closed as in the case of a door. The INLET is a link to a connected room which shares the same door or window. We can then draw each inlet'd room until we have no more inlets left.
Another way to describe this method is to imagine an artist painting a picture of a room. He draw and paints all the three visible walls leaving a small unpainted rectangle for a window, then he paints the floor and ceiling. Now he returned back to the window and draw the scene outside (sky, trees etc.) but he only paints the parts of the scenary which can be seen through the window. By painting the entire room before the outside the artist has entirely removed any overdraw and greatly reduced the region through which distant objects can be seen. Also after completing the room he knows where and how much further rendering needs to be done (or not in the case of low-detail for slow PCs). You can then think of the window as a tiny self contained picture in its own right.
The basic rules for following an INLET polygon are:
1. It must be visible (facing us).
2. Some part of it must be visible on the screen (not totally clipped/hidden by a closer surface).
3. The INLET must be open (we can't see through an closed door).
And possibly for speed reasons:
4. Within our horizon clipping limit. (We could use a solid-fill to black out the any inlet beyond a certain Z cut-off distance or better still draw a solid "horizon" texture.)
9: Remember that central pillar ?
So the INLET rendering method breaks down a level into small CONVEX volumes. This means that (hopefully) no depth-sorting is needed as NO surface in a volume can be hidden by any other surface.
We have also seen that using two circular linked-lists we can quickly trace along the walls or boundaries of an area by using a pointer to each one's neighbour.
But there is a problem, how can we handle rooms with pillars or islands in their middles where none of the boundary walls connect to them? In fact a room with a pillar or island is NOT a convex room, is it CONCAVE! Just like being inside a doughnut shaped room. Part of the outer wall is obscured by the central part at almost every angle.
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
°Ú--------------------------¿° ° = null-space
°³ ³°
°³ doughnut shaped room ³° where it is impossible
°³-------Ú--------¿---------³° to go, so no surfaces
°³ ³°°°°°°°°³ ³° are needed to be
°³ ³°central³ ³° defined.
°³ ³°°post°°³ ³°
°³ ³°°°°°°°°³ ³°
°³-------À------------------³°
°³ ³°
°³ X ³<-------- walls
°À---------------------------°
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
In the above diagram we have a total of 8 walls, 4 interior walls and the 4 exterior walls of the central-post. If we stood at point X and looked north then it obviously means that we couldn't see the far north wall of the room so it can not be convex. Let's add some walls parallel to the centre post corners (marked by ------). This divides the room into 4 parts and each of which is now CONVEX (yipee). But having 4 walls means we can't see much of the room, so let's make them transparent like they're made from perfect glass and turn them into INLETs.
So what we have really done is to turn a concave room into 4 convex sub-rooms. We can think of each of the "INLETS" as being a window into other rooms (just like a door or window). If an inlet is invisible (facing away from us) then we don't bother rendering the adjoining room to which it points (we see through a hidden window can we?).
10: What about depth sorting & Overdraw ?
Now that we have rendered the starting convex room that we are standing in and found all the INLETs (if any), we still need to draw them. There are some important things to notice about each INLET.
1. The same room can be reached by more than one INLET link (e.g. a window & door in the same wall).
2. The INLET might be further away then the current room in which it was found (coz we are rendering out from the view-point).
3. The view of a room through an INLET will be confinded to the area of the INLET polygon (the window/door edges mark the clipping edges).
4. When a connected room is found by the INLET then it might require a lot of searching to find a visible wall. (We would have to follow each wall starting at the back side of the INLET polygon and working either clockwise or anti-clockwise until we found a visible wall.)
In the first case it can be useful if an entire room's vertices are rotated and projected all in one go (instead of calculating each wall as we trace it). Then we could just re-use the same 2d coordinates for a shared room. Possibly removing the need to repeat the hidden surface checking and facing wall check (see case 4).
In the second case this may not always be true. It is possible to be in a small room underneath a much larger one. But case 3 should still remove any need to perform depth-sorting. It 'should' never suffer from the flood-fill problem due to the convex construction of the level. I'm unsure whether any sorting of the listed inlets will ever be needed, I still need to try a proto-type 3d engine!
In the third case this is not a problem, but a *BONUS*. Where a simple depth-sorted (The Painter's algorithm?) method would draw the most distant objects first and possibly overdraw them with closer ones, we don't. The inlets take care of depth-sorting and has hierarchical properties (we only trace rooms which are connected to our view point). The portion of the room beyond the inlet will be restricted to the the inlet's polygon edges as anything beyond them as obscured by the closer walls (the wall which surround the inlet). So the inlet polygon can be used as a clipping window. The only complication is that the clipping region is NOT a rectangle, but possibly a concave polygon? So pixel clipping is required on each horizontal line span. The clipping is just a Xmin to Xmax left/right clip. This can be done in the scan-converting part of the engine. It might be worthwhile first checking the rectangular clipping screen boundary for accepted/clipped edges and then perform the pixel span checking.
This can be improved by keeping the xmin, ymin, xmax and xmax limits for the inlet polygon and using them as a rectangular clipping region. As inlets are likely to be a fraction of the entire screen/window area this should reject far more lines before needing to check pixel spans.
In the fourth case an improvement could be made using a dynamic line-of-sight link which the engine could modify as it renders. This may not help newly inlet'd rooms as the the dynamic link might be pointing to the opposite side of the room to what we want. A possibly solution would be to have central navigation nodes in the centre of each room. The node would need to be multiway to be able to direct the rendering ray to the correct wall for the desired viewing direction. It would not only need north, south, east, west directions but also up and down ones.
Another solution could be to create "spoke-tables" for each room, one for the X-Z plane (horizontal) and one for the Y-Z plane (vertical). As we know that each room is a closed convex volume we also know it extends for 360° in all directions, so given a viewing direction, the spoke-table's length we can soon locate a wall for any particular direction (or alteast find a neighbouring one).
90ø table
Ú--------¿ ------------
³ b ³ 0 a
"INLET"³ ³ 1 b
view ----> 180ø ³c a³ 0ø 2 c
³ d ³ 3 d
À---------
270ø
If we were viewing through the inlet c and wanted to find the wall at an angle of 50°. We divide by this angle down into an index and look-up the wall in the spoke-table. But how?
In the above diagram we have 4 sides, which means that if we take 360° and divide it by 4 then each wall would have an equal share of 360° / 4 = 90°. If we just divided our viewing angle by 90° then there is a problem. Take a look this:
90ø
--------¿
xx/³
xx / ³
50ø xx / ³ 0ø
/ ³
/ ³
45ø ³
So using the formula:
number of walls
index = viewing angle * -----------------
360ø
would give:
0 = 50ø * 4 / 360
but as 50° is more than 45° (half the angle between two walls) what we really want is 1 as our index. So let's add a rounding up part to the formula:
Ú ¿
³ 180ø ³ number of walls
index = ³viewing angle + ----------------- ³ * -----------------
³ number of walls ³ 360ø
À -
So in the 50° example this would give:
1 = ( 50 + 180 / 4 ) * ( 4 / 360)
Now we can just index into the curcuit-table and discover that at 50° that wall b is the closest. For very small rooms with only a few walls this method might prove to be slower than following the wall links around the chain. But it does remove the need to check each wall in the chain for visibility (if it is facing us) and for large convex areas with many walls this might prove to be faster than the dynamic line-of-sight link method for newly encountered rooms.
There may be problems with this as a room's walls might not have a equal share of the 360° arc unlike the above example of a cube (where each wall has a 90° share of 360°). This method might be good for very large rooms with many walls. As the spoke-table is a complete 360° structure and we can reuse the same table for all the inlets which lie on the same plane (in the same room).
This spoke-table might be useful for pathfinding a route through a map for A.I. routines and so on....
11: Pixel clipping distant objects
This is probably the easiest part of the technique and most CPU intensive task of the rendering. You must compare the start and end X coordinates of each polygon scan line against the clipping left and right X coordinates on the same screen scan line and possibly clip the polygon texture and/or shading coordinates.
e.g. In the below diagram the polygon line with pixels "abcdefghijklmn" needs to be clipped inside the left limit.
Scan line
------------ left right
140 ³ ³ <---- each scan line it's own limits
141 abcdefghijklmn ³
142 ³ ³
143 ³ ³ <---- NOTE: not vertical !!
NOTE: Although the left & right clipping limits here begin as straight lines (equal to the screen limits) and form a rectangular clipping region, it can NOT be assumed that they stay this way. And it can NOT be assumed that they form a straight line, as parts of polygons might encrouch inside one side anywhere. So each horizontal scan line must be tested on an individual, pixel coordinate basis.
ALL the pixels between these X-min and X-max values are YET to be drawn. They are simply the clipping span through which all further INLETs or polygons must be checked and clipped. As each polygon has it's edges clipped against these left/right limits it modifies the limits itself, further reducing the span length and decreasing the size of the render inlet.
Some things need to be considered when drawing polygons:
1. whether it is visible
2. if any part of it is clipped inside the INLET edges (this modifies the Xmin and Xmax limits and decreases the difference between them)
3. whether it breaks the inlet into two parts (This happens when a polygon is drawn which lies in the middle of an inlet span with further inlets to either side. I haven't got round to this yet as it is a bitch of a problem. One solution is to create another INLET.)
4. if the polygon is an inlet itself, pointing to another room.
12: Texture clipping speed up
In the pixel clipping section of each polygon its texture must sometimes be clipped inside the left/right inlet limts. For each polygon line there are 6 possible situations for clipping. The clipping of coordinates in texture-space can be slow often requiring a multiply and possibly a divide (yuck!).
x min x max
case 1: abcdefg ³ ³
case 2: abcdefg ³
case 3: ³ abcdefg ³
case 4: ³ abcdefg
case 5: ³ ³ abcdefg
case 6: abcdefghijklmnopqrstuvwxyz
³ ³
Actions:
----------
case 1: completely left of limits, so reject entire line
** case 2: clip left
case 3: accept entire line without clipping
*** case 4: clip right
case 5: completely right of limits, reject entire line
**** case 6: clip both ends
** The clip can be avoided by indicating that the span should be drawn
from right-to-left. This avoids having to clip the texture coordinates
against the left edge. Only the screen left X coordinate needs to be
clipped which is just a MOV instruction.
*** The same applies to this, only the screen right X coordinates needs to
be clipped, not the texture and the drawing can occur normally from
left-to-right.
**** Er... Damn, damn, damn! The left texture coordinates need to be
clipped and both the left & right screen coordinates too. This works
out to 1 texture clip & 2 MOVs in the best case. We can just clip the
texture coords of the left edge and draw from left-to-right WITHOUT
needing to clip the right texture coords.
Possibly more work is required for shaded textured polygons when clipping (to work out the shading points for the clipped horizontal line span). Problems... problems...
13: Problems, Problems
The inlet region might not remain a convex shape. Certain forms of concave shapes are okay unless they divide a scan-line into two individual horizontal parts. The only solution I can see at present is to build up another inlet for the newly created spans.
e.g.
_________ ___________ _____
\ / \ / \ \
\ / \ / \ \
\ B \ \ B / / \
/ \ \ / A / B /
/ / \ / \ / /
/_____/_A_\ /______\_/_____/
concave, but ok. concave, but divided
polygon A merely by polygon A into 2
shrinks the right edge parts.
In the worst solution a total of 4 inlets could be created by a single polygon lying entirely within an inlet.
e.g. _____________________
/ ______ \ Polygon B is the INLET
/ / \ / region and polygon A is
/ INLET \ A / B / the polygon to be drawn.
\ \____/ /
\ B /
\_________________/
But in fact only 2 inlets need to be created. We can extend the top and bottom of polygon A to meet the left or right edge of polygon B. This would create a 'C-shaped' inlet and a small window as well, something like this:
_____________________
/ _______________\
/ / \ /
/ INLET \ A / C /
\ \____/_______/
\ B /
\_________________/
NOTE: There are a few problems with this.
a. If we divide up the inlet then we possibly need to divide any neighbouring polygons/inlets as well.
b. We may end up creating inlets which we don't really need to as all the neighbouring polygons might be solid colour/texture. In this case the entire inlet has been filled so this inlet is deleted and no more are created.
There are about 4 situations which may occur.
1. The neighbouring polygon connected to A might fill up ALL the horizontal lines spans and so close the inlet B. (It can then be removed from our inlet list.)
2. Some neighbouring polygons might only fill one or more sides around polygon A. This would shrink the inlet on one or mores sides and we would be left with 1 inlet (which is what we want).
3. The neighbouring polygons to A might also be inlets themselves, so two or more new inlets will need to be created and the current one discarded.
4. Polygon A might be an inlet itself. This has two possible sub-cases.
4a. All the surrounding polygons fill the inlet B (this reduces the inlet to the area of polygon A).
4b. Some/all the surrounding polygons are also inlets. (At the worst possible case ALL the surrounding polygons are also inlets, so ALL require new inlets to be created.)
I have not explored the possibilies of combining two neighbouring inlets which share an indentical end point along the same scan-line. This can happen when a concave room is sub-divided into convex ones where many invisible inlets are used to connected these sub-volumes and when two inlets break up the same solid wall. An "S-Buffer" technique might be useful in this case to try and reduce the number of inlets and broken texture spans. (See the "Span-Buffer" section for more info.)
Also I have not mentioned movable objects such as monsters or vechiles which themselves might conceal a background wall texture or even part of an inlet. In the very worst case the inlets will degenerate down into single, horizontal line spans. And these themselves might be sub-divided into two parts.
14: Convex Bonuses
There are a number of advantages created when breaking up a concave volume (a room or open space etc.).
1. Depth-sorting 'should' be removed (speeding up the engine).
2. Collision detection should be easier (knowing what convex sub-room a player or monster is standing in reduces the number of polygons to check).
3. Movement will be easier to test for (A.I. code can use the inlets of each room to know where the exits & entrances are. Also you only need to check the polygons which make up your current room).
4. Linked-list allow for easy re-direction (lifts can be done simply by changing the inlets links to its door).
5. Very complex, interconnected environments can be made by glueing together a number of of convex rooms.
15: Convex Downers
But of course there are always some disadvantages:
1. More polygons are created for the inlet sides (these are the perfect glass walls which join two connecting convex volumes).
2. Certain restrictions on map design are imposed (well actually the level editor remove these restrictions turning concave areas into convex).
In case 1 it may first seem like an increase in workload but remember the savings from not doing depth-sorting and all the smart hierarchical clipping which the inlet method performs. Even if a BSP of some kind was used instead there would still be an increase in workload because polygons are often split by BSP trees to resolve partition crossing.
16: Summary
The use of linked-list is the key component to this type of 3d rendering. I've used them in a way to describe the connected relationship between joined walls/polygons. This removes all need to search or depth-sort many polygons.
This method of edge-connection could possibly be extended to solve some of the speed problems for complex 3d objects (like monsters or vechiles in this 3d world). A number of visible (facing us) polygons for every convex part could be used and updated after each render cycle. For example in the case of a monster it would need to be broken down into a number of convex components (the head, the torso, each arm, each leg, each hand, etc.) and for each convex part we store a visible polygon address. This will be our starting point for drawing each component. We pre-build the edge-links for each polygon/surface and use them during rendering just like the linked-list room approach, but instead of describing interior surfaces we describe the exterior ones (the skin). In the example of a head we could start with drawing the nose then follow the edge links for the cheeks, the eyes, the mouth, etc. We continue this until we discover a hidden surface or a clipped polygon, at this point we stop and resume at some other edge until we have followed them all. In the case of the head this would be after following past the forehead, under the chin and around past each ear. We do NOT follow the links around the back of the head because those polygons are hidden from our view.
e.g.
_______x________
x/ \ x
x/ \_x
| |
ears | | ears
|_ top of head _|
| |
\ /
\_____ _____/
\ /
cheek \_/ cheek
nose
In the above work of art, the ears would be the last things drawn and all other connected polygons would be ignored.
NOTE: I am not sure whether there would be any saving in workload using this method for convex objects as they normally only have 6 sides or a few more. The actual saving might not be worth pursuing, although I haven't tested this yet.