

  
                             3D Foundation Classes



                            *** TECHNICAL NOTES ***



     -------------------
      Table of Contents
     -------------------



           About This File

           Portal Engine

           Data Structures

           Portal Clip

           Collision Detection

           Portal Crossing

           Engine Pipelines



     -----------------
      About This File
     -----------------



           Here can be found a collection of technical notes.
           
           The purpose is help the reader to get an overview
           
           about some algorithms used in engine implementation.

           The information is about 3DFC v0.0.1.


           May changes are not described here.



     ---------------
      Portal Engine
     ---------------



           One of the biggest problems in 3D viewing is

           define what scene elements hide each others.

           To better understand the problem think in a scene
           
           composed by polygons disposed in random positions.
           
           You cant draw all of them in any order because a closer
           
           polygon can be covered by a polygon that are behind it.

           The magic of make only what is in front of the viewer
           
           visible is known as hiden surface removal.

           To make it exist many technics: Z-buffer, deph-sort,
           
           BSP-Tree sort and others.
           
           The algorithm used in this case is called portal clip.

           To understand this algorithm imagine the viewer
           
           inside a convex scene. A scene is convex when their
           
           polygons do not overlap each others in any point of
           
           view where viewer can be.
           
           The polygons, in this case, can be drawn

           in any order because they never overlap each others.

           Portal engines use this principle to render the scene.

           The scenery unit is known as "sector": a convex set of polygons
           
           where they never overlap (if the viewer is inside them).

           There is a problem because the sectors must be convex, this

           limit them too simple models. To create more complex scenes

           is used portal clip: some of the sector polygons are passages
           
           to other sectors. This polygons is known as "portals": polygons
           
           (normaly invisible) that work as clip areas to adjacent sectors.


           The basic view algorithm is: draw the sector where the viewer
           
           is, if a portal is visible from viewer point of view, call
           
           recursively the sector draw algorithm - drawing the

           sector linked by the portal. The sector visible througth a
           
           portal polygon is a "destin sector" and their polygons must
           
           be clipped acording the portal.

           If more portals are visible from the destin sector,

           call again the sector draw algorithm making the

           apropriate clip. The scene is complete when all visible
           
           portal polygons have their destin sectors drawn.


           Portal clip can be thinked as an evolution of BSP-tree

           sort, as BSP-tree sort and deph-sort are an evolution
           
           compared with Z-buffer.
           
           In Z-buffer to make hiden surface removal is
           
           needed test each pixel - the scenery unit is a pixel.
           
           In BSP-tree sort hiden surface removal is performed
           
           drawing polygons in the right other, acording the tree,
           
           the scenery unit is a polygon. In portal engines the

           hiden surface removal is made by portal clip througth a
           
           convex set of polygons - the scenery unit is a sector.

           Sure, think if a view method is better than other because
           
           the scenery units are biggest between each other is
           
           dangerous. Big scenery units mean scene design limitations,
           
           but normaly performace increase, too.

           
           Some problems of portal approach are: a very complex scene
           
           with many objects would be hard to be modeled, the scene

           must be indoor and the objects modeled with portals and
           
           sectors must be static. All this limitations can be
           
           atenuated with some additions. Usually portal engines are

           used to visualize the static scene objects like rooms, walls,
           
           pillars. More complex or, moveble, objects like stairs,
           
           chairs and animals would be visualized using an other

           method: Z-buffer, BSP-tree sort, and so on.
           
           
           Advantajes of portal redering: the implementation is relatively

           easy, big scene clusters are complete clipped very fast;

           transform universe reference system to camera reference

           system must be made only in visible sectors and their inside
           
           objects - with some precautions the scenery model can be
           
           hude without performace loose. Many tests like viewer collision
           
           detection can be optimized - made only between viewer and
           
           polygons sector where it be (see Collision Detection section).



     -----------------
      Data Structures
     -----------------



           The main scenery data structure, for a portal engine, looks
           
           like a connected graph. Each node has data for one sector,
           
           the links between nodes are made by sector portals.

           
           One suggestion, to implement this structure, is create a linked
           
           list with all scenery sectors and define in sectors structures
           
           pointers to adjacent sectors. Each pointer is related with
           
           one portal. If the portal is visible, the engine call
           
           recursively the visualization algorithm, passing the sector
           
           pointed as an parameter.


           The graph nodes have all information needed to render a

           sector and their objects. For example, can have a
           
           polygon mesh and a list to objects that are inside it.

           The polygon mesh have information about the sector
           
           walls. Thinking in implementation, can have a list of vertexes
           
           and a list of polygons composed by this vertexes. In adition,
           
           each portal polygon have a pointer to a destin sector.

           The polygons can have too, an texture ID, a transparency
           
           level, its normal vector, ...


           3DFC structure is very close as the above. The difference
           
           is each polygon don't have a pointer to the possible destin

           sectors, but a flag. If the flag is TRUE, the polygon is a

           portal. In this case the destin sector is found in a

           specific list. For performace reasons, in nexts versions, I

           will change this to the structure described above.

           Other diferences are related with future features to be
           
           added, and don't are relevant now.



     -------------
      Portal Clip
     -------------



           Portal engines make invisible surface removal based

           on portal clip. The portal is a simple scene polygon,

           the clipping can be performed with any known method.

           I implement one method based on "clip edge buffer",
           
           probably exists better methods, but it's easy implement.


           Consider a viewport where X increase from left to right and

           the portal must be a convex polygon.
           
           
           For each scanline exist two 
           
           informations associated: one start X value
           
           and one end X value. This array of X start-end values is
           
           known as edge buffer. During polygon edges scanning, the 
           
           the minimum and the maximum edge values, for each scanline,
           
           are defined. If there isn't portal visible in a scanline,
           
           the values stored for this scanline are the maximum
           
           viewport X in start X and minimum viewport X in end X.


           When the destin sector is in rendering their polygons are

           tested and clipped by the edge buffer limits. The same
           
           procedure must be done to set a new clip edge buffer,
           
           if another portal is visible througth destin sector.


           The clip edge buffer, in the sector where viewer is inside,
           
           can be initialized with the viewport limits.


           This method have two problems if the vertical resolution
           
           is high: need allocation of to much memory for each rendering
           
           recursion level, and to much tests for each scanline.


           A suggestion (more resolution independent) can be,
           
           create a new polygon acording the visible area
           
           between the portal and the destin sector polygon.

           The visible area is the intersection between both polygons.



     ---------------------
      Collision Detection
     ---------------------



           The collision detection method described is between a
           
           sphere and a polygon mesh. The coodernate system used

           is the universe. The mesh has only convex polygons.
           
           
           The viewer is the sphere. The center is viewer
           
           position, and, is recomendable, as minimum radius, the
           
           half viewport diagonal measure, in universe reference system
           
           coordenate units.


           The collision detection is made in two steps. First, verify
           
           if the distance between the sphere and the polygon plan is
           
           equal or less than the radius. Second step, case the first

           is true, verify if the intersection point between sphere
           
           and the plan is inside the polygon area.
           
           
           For each polygon in the mesh is needed make collision

           detection tests. This can be optimized, as suggested bellow.


           To implement the first step is needed define the distance,
           
           between a point (viewer position) and a plan, using
           
           the expression:
           
              distance = ax + by + cz - d

              where,

              (a, b, c) are the polygon normal vector normalized,

              (x, y, z) are viewer position,

              d = - ax' - by' - cz',
              
              (x', y', z') are any point inside plan (can be a vertex).

           Both, "d" and (a, b, c), can be pre-calculated.

           If the distance is equal or less than sphere radius is needed

           run the second step.


           In my implementations, the second step, doesn't work

           for all cases. I don't know exactly why.

           
           For the second step is needed one new information:
           
           the intersection point.
           
           
           The intersection point between the
           
           sphere and the plan can be computed by projecting the
           
           sphere center to the plan, using the expression:

              px = x - a * distance
              
              py = y - b * distance
              
              pz = z - c * distance

              where,

              (px, py, pz) is the projected point,

              (x, y, z) is sphere center position is space,

              (a, b, c) are the polygon normal vector normalized,

              "distance" is the value computed on first step.

            
           To verify if a point is inside a convex polygon is used

           dot-product between two vectors. The algorithm is:
           
              - select one polygon vertex;
             
              - make a vector from selected vertex to its next vertex;
             
              - make other vector from the selected vertex and the point
             
                to be tested;

              - compute dot-product;

              - select the next vertex and make all again.

           If the dot-product sign change during the interaction, this
          
           mean the point is outside the polygon. If there is no sign
          
           change, the point is inside the polygon.

           
           Example of how to get the vectors:


                    1--------2
                   /          \
                  /            \
                 /              \
                /                \
               /   polygon        3
              /                  /        
             /                  /
            /                  /
           5------------------4           * point

           Interaction 0:

                    1--------2
                   /          \
                  /            \
                 /              \
                /                \
               /   polygon      _ 3
              /                  /|      
             /                  /  
            /                  /
           5------------------4------->* point

           Interaction 1:

                    1--------2_
                   /         |\
                  /            \
                 /              \
                /                \
               /   polygon        3  
              /                  / \     
             /                  /   \
            /                  /    _\/
           5------------------4       * point

           ....

          
           The first step can be optimized if the mesh has explicit

           information about its plans. Share a plan with many polygons
           
           have other advantajes like: memory save, more efficient
           
           back-face culling, ...


           Other optimization can be made, if collision detection is
           
           to avoid polygon crossing. For example, between the
          
           viewer and a wall, in some cases, is only need the first step.

           If the polygon is not in same plan as a portal (portals must

           be crossable polygons) maybe this is possible.


           If the collision detection is made only between the sector

           where viewer is, there is a problem. No adjacent sectors

           can be smaller than the viewer radius. Or while the viewer is

           going to the adjacent sector it can cross some destin sector
          
           polygons.

          
           In second step, 3DFC v0.0.1 use other way to make sign test.

           Is used, cross-product between two vectors to define a

           normal vector. The sign test is made over each normal vector

           component. This solution is more slow and don't work for

           all cases.



     -----------------
      Portal Crossing
     -----------------



           In portal engines, detect when the viewer change the current
           
           sector, is a problem. If the sectors are simple
           
           boxes, aligned with universe plans, it is easy. But the

           scenery design would be very limited.
           
           
           The implementation use the distance between viewer
           
           and the portal plan. If the viewer is collidin and
           
           the distance is negative, the portal is crossed.
           

           3DFC v0.0.1 just test if viewer distance is negative between

           portal plan. Because this, is impossible design scenerys with
           
           portals sharing the same plan.


           Other two problems remain with no solution on 3DFC v0.0.1.

           What to make when a visible object is between two sectors.
           
           When the viewer is clossing a portal and the portal is clipped
           
           by the near Z plan (can be partialy solved reseting the
           
           clip edge buffer to frame buffer limits).



     ------------------
      Engine Pipelines
     ------------------



           Main engine loop is:

           
           1 - keyboard input - detect if program must terminate,
           
               set a viewer move direction vector and viewer
               
               rotation angles;

           2 - detect collision - can change the move directon vector or

               make portal crossing detection;

           3 - update viewer reference system

           4 - make sockets communication - send viewer position and
           
               receive objects position;

           5 - render frame
           
           6 - goto step 1.


           Rendering pipeline overview:


           Before rendering, must be already defined, the start
           
           sector - sector where viewer is and, the clip edge buffer,
           
           must be initialized with viewport limits.
           
           The main rendering steps are:
           
           1 - transform sector mesh to camera reference system;

           2 - project and ajust mesh to viewport;

           3 - for each polygon:

           3.1 - copy projected polygon vertexes to an array and
           
                 count how much of them are behing near Z clip plan or

                 outside viewport (only horizontal or vertical) limits.

           3.2 - if the polygon is completety outside the viewer area
           
                 skip polygon, goto step 3;

           3.3 - make backface culling (usefull to avoid engine deathlock

                 and remove some invisible polygons).
               
                 The engine deathlock happens when a previous rendered
               
                 sector is rendered again. Recursively, is
               
                 called the render algorithm from a destin sector to a
               
                 previous sector.

                 If polygon not visible, goto step 3;

           3.4 - create a new clipped polygon, if polygon intersect
           
                 near Z clip plan;

           3.5 - verify if the polygon is a portal

           3.6 - if is a portal:
           
                    set a new clip edge buffer for the destin sector,
                    
                    verify if some portal part is visible. If yes, call
                    
                    recursively the rendering (goto step 1). Before
                    
                    end rendering the destin sector, is needed make
                    
                    steps 1 and 2 again for the current sector.

                    3DFC v0.0.1 use the same structure, for all

                    redendered meshes, to store camera and

                    projected data. On next versions this would change.

                 if the polygon is not a portal:

                    render a textured polygon making portal clip.
