3D Coding TAT - Unfolding Polyhedra & Mapping Adjacent Faces
In a couple of previous sections I have described methods which follow neighbouring polygon faces to exploit the locality of surfaces, shared edges and vertices etc. but there some problems which need to be tackled in order to make these methods feasible. The main problems are:
1. Following these neighbouring faces. There are as many neighbours for each face as there are edges.
2. It is possible to visit the same face twice. Because every polygon is connected to AT LEAST 3 others (3 sides = 3 neighbours) it is possible to find your way back to the starting polygon in many, many ways.
3. Neighbouring faces can be at any angle to the current one. So there is no easy way to find the polygon face above (or in any direction to) the current one.
Point 1: There are two likely strategies for tracing the neighbouring (Mapping Adjacent Faces). One way it to create two elements for every polygon edge where these two elements point to the two neighbouring polygons which share the edge. Another way which I have used throughout this document is to create N links for the N sides of each polygon. So for a 5 sided polygon there would be 5 links. Each link is just a pointer to the neighbouring polygon. Creating these links is a very simple matter of searching for two polygons which share the same 2 vertices but in reverse order. So one polygon would use 2 vertices A..B and the other would use B..A to describe ONE edge.
Point 2: As there are many links (because the polyhreda is a closed surface of joined faces) there is no start or end and no single direction to trace out these neighbouring faces. You can think of this as a multi-directional circular tree.
Point 3: It would be incredibly useful if there was a way to move around the object quickly in a certain direction. If there was we could possibly reject large numbers of polygons when we encounter a clipping edge. E.g. if the current polygon is clipped against the right screen edge then we can reject ALL those polygons to the right of it, and likewise with the other screen/clipping edges.
1: Unfolding
If it wasn't for the 3rd dimension of the 3d models which connects one side along the back to the other, then the links would not need be circular. If the model was 2d then we would have leaves to the tree structure where the outer polygons have no neighbours. Because at the end of the day the 3d model will be projected onto a 2d bitmap screen you could think of the entire 3d model being squashed flat onto a plane. This is what the projection actually does, it removes one dimension to create a flat group of co-planar polygons. We only see (and draw) the polygons on one side of this plane because the others are rejected by the back-face culling. If all these polygons remained rectangular with no overlapping then finding the polygons in a particular direction would be very easy, just step across this 2d array map. But this is never the case.
I believe that only convex polyhreda can be folded flat this way with no overlapping of polygon faces. Concave objects cannot be made from a single piece of paper or card, where convex can (I think).
By thinking of a 3d model as being a 2d one with 2 sides (of which 1 is rejected) then it should be possible to trace around the edge of the polyhedral object to discover those polygon faces which are on the visible side. That way any faces inside this front/back boundary can be accepted and those outside it will can be rejected without the need to apply back-face culling to every face.
NOTE: This scanning of the front/back boundary polygons is no doubt only valid for true convex polyhedral object models (those without lumps or dips in their surface skins).
2: Neighbours and Trees
Programs and CPUs are efficient at handling sequential data (one after the other), but they are lousy with multi-direction data structures. We can define fancy binary or multi-way trees and jump tables which branch off into many directions from one single point although there is no easy way to simutaneously follow more than one branch. To visit all the nodes/junctions on just a binary tree requires a temporary linear buffer (i.e. a stack) so we can back track and follow the second route after following the first to its conclusion (a leaf).
What's this got to do with 3d models? Well, a circular tree (or "ring" tree) can be used to model a 3d object by taking the tree nodes as being the polygon edges we could define our old friend the cube using the following tree for its six faces:
1 ------
/ | \ \
/ | \ \
6 ----- 2 ---- 5 \
\ \ | / / |
\ \ | / / /
\ 3 / /
\ | / /
\ | / /
4 ------
The above (lousy) ASCII diagram shows how each of the six faces are connected to its four neighbouring faces. Please note that the connecting lines are BI-DIRECTIONAL so face 1 is joined to 4 and face 4 is joined back to 1. The biggest problem with the above structure is knowing which links you have already visited and when you have reached the end.
Another way to represent the cube is choose one starting face and then squash it flat. If we repeat this for all the faces then we have the following holy shapes.
The top-most square is the starting face.
Ú-¿ Ú-¿ Ú-¿ Ú-¿ Ú-¿ Ú-¿
³A³ ³B³ ³C³ ³D³ ³E³ ³F³
Ú-Å-Å-¿ Ú-Å-Å-¿ Ú-Å-Å-¿ Ú-Å-Å-¿ Ú-Å-Å-¿ Ú-Å-Å-¿
³F³B³E³ ³F³C³E³ ³F³D³E³ ³F³A³E³ ³A³B³C³ ³C³B³A³
À-Å-Å-- À-Å-Å-- À-Å-Å-- À-Å-Å-- À-Å-Å-- À-Å-Å--
³B³ ³D³ ³A³ ³B³ ³F³ ³E³
Ã-´ Ã-´ Ã-´ Ã-´ Ã-´ Ã-´
³B³ ³A³ ³B³ ³C³ ³D³ ³D³
À-- À-- À-- À-- À-- À--
We could use a 2d table to represent the cube like this:
Face Up Right Down Left
---- -- ----- ---- ----
A D E B F
B A E C F
C B E D F
D C E A F
E D C B A
F D A B C
For the moment I can't think of any really practical way to define general polyhedral based objects using either binary or multi-way trees. And it might be a lost cause to believe a solution exsists because tree based structures are best utilised for navigating a SINGLE path through pre-sorted data. They tend to be really awful for visiting every location as recursion (real or fake) is needed to follow every possible path. And visiting every path (in some order) is what we need for 3d model rendering. Finding one, single face isn't enough and if we repeat the navigation for every face then the tree structure is actually creating more work instead of saving it. Tasks such as string-searching, locating a particular item in a sorted list both benefit from using a tree, but sadly I think face rendering doesn't (apart from BSP trees).
3: 3d models, 2d belts
As I have previously mentioned linear (sequential) data structures are best suited for programming purposes because they usually have a beginning and an end. All of the 3d models that we wish to render will tend to be closed ones with no beginning or end. Even 'open' objects like a cup can be represented by a continuous surface made up from connected polygons or 'mesh' as I believe most people like to call it. Think of a lump of clay, the exterior surface of the clay is our polygon mesh. Now deform it into the shape of a cup. I think if you take any convex polyhedron and reverse deform it back into a clay lump then you always end up with a spherical shaped mesh lump. This general, globe-like lump could be the basis for all 3d models (maybe).
Now we need to find a suitable way to describe this ball shaped lump and if possible do it in a mostly linear way so a straight forward list could be used. At this point I will break with tradition and use a regular dodecahedron instead of our overly employed cube. It has 12 faces, 20 vertices and 30 edges (each face has 5 edges). If you looked square on at this dodecahedron then you would see 5 faces with 3 at the top and 2 at the bottom.
J
e.g. _____________
/ | | \ <--- Cool back-face culled
/ A | B | C \ object (who needs SVGA)
/ /\ /\ |
| / \ / \ |
| / \ / \|
\ E | F /
\ | /
\_____|_____/
K
The above diagram (okay, stop larfing) shows 5 of its 12 faces with the other 7 faces hidden from view. Unlike a cube we can not use left/right/up/down direction to navigate a path across it's surface polygons. For example starting at face B what is the next face on the right, is it C or F? One idea which I had today is to cross-section an object into a number of 'belts' using a series of parallel cuts through it. A 'belt' is a sequence of polygon faces which follow an imaginary plane as closely as possible. In the above diagram the A,B,C (and the hidden) D,E faces would be classified as a single belt. It's data structure is nothing more complicated than a circular list which is a wrap-around linear list.
e.g.
Ú-------------------------¿
³ <--- A 'belt'
A -- B -- C -- D -- E ---
This parallel dismembering of the 3d object model continues with the next belt of faces. We must also repeat this for the top and bottom layers. At the end we have the following belts listed in vertical order.
Belt Faces
---- -----
1 J
2 A B C D E
3 E F G H I
4 K
NOTE: The faces in the object only appear ONCE in this list of belts. This means we never need to worry about revisiting the same polygon face.
SO WHAT? At the moment I am not really sure how useful this is. It could possibly be good for back-face culling or trival polygon rejection. One strategy for using these belts might be to test the visibility of the first face in the list and if that is visible then continue with through the list until we find a back-face culled one. At this point start again at the beginning of the list and step backwards through it until we encounter another invisible face. Now hopefully between these two completion points we have correctly rejected many faces without the need for visibility testing. I.e. we have followed and drawn each face from the front of the belt in both directions stopping at each side and NOT bothering to process the back faces. This method is perhaps only useful for 3d object models which have a high number of polygons. Primative things like a cube, pyramid and the like are probably not worth doing.