\section{Introduction}
\label{sec:introduction}

\label{fig:pvs}
\end{figure*}
\begin{figure*}
\centering
\includegraphics[width=0.33\textwidth]{images/pvs}
\caption{The PVS Computation Module integrated in the Ogre3d engine. 
A snapshot of Vienna is shown, with the rendered PVS shown in the lower right corner. Note 
how the PVS closely fits to the geometry actually seen.}

This manual provides a guide to apply preprocessed visibility in a particular target engine. It
will start with instruction for building the preprocessor, describes the integration of the 
preprocessor and the generated visibility solution, and last but not least the usage of 
the view cells within the target engine.

\section{Build Project}
\label{sec:build}

Open the {\em GtpVisibility.sln} with {\em Visual Studio 2003} (2005 might work, but we did not test it recently). 
Set the build target to {\em Release}. Build the project {\em TestPreprocessor}. Now there should be a newly built
executable {\em Preprocessor.exe} in {\em bin{/}release} and a library {\em Preprocessor.lib}
in {\em lib{/}release}.

\section{Generate Visibility Solution}
\label{sec:visibility}

All necessary scripts are located in the {\em Preprocessor/scripts} directory.
The easiest way to use the scripts is with Cygwin.
First some meaningful view cells must be generated for the current scene.
The script {\em generate\_viewcells.sh} is responsible for view cell generation. 
It takes the parameters from the file {\em generate\_viewcells.env}.
To specify the input scene, the parameter

\begin{verbatim}Scene.filename\end{verbatim}

must be set to the file name of the new scene. Our preprocessor supports the formats obj and x3d.
Important options for performance are

%\begin{verbatim}
%VspBspTree.Construction.samples
%VspBspTree.Termination.maxViewCells
%\end{verbatim}

\begin{verbatim}
Hierarchy.Construction.samples
VspTree.Termination.maxLeaves
\end{verbatim}

The first parameter sets the number of samples that is used for view cell construction. Less samples
means faster computation, but maybe slightly less optimized view cells. The second
parameter sets the maximal number of view cells.
%The easiest way to use the file is with Cygwin, but a windows command line will also do the job

Running the script will generate a visibility solution with empty view cells.
Now we must compute visibility for these view cells.
In the preprocessor script {\em generate\_visibility.sh}, set the following parameter to the
newly generated visibility solution.

\begin{verbatim}ViewCells.filename\end{verbatim}

This script starts the preprocessor and generates the full visibility solution. This solution contains
view cells and the corresponding Potentially Visible Set (PVS). Next we explain how this visibility
solution can be used in a target engine. 

 
\section{Integration of Preprocessed Visibility}
\label{sec:integration}

\subsection{Requirements}
\label{sec:requirements}

Add the following libraries to your application. 

\begin{itemize}
\item {\em Preprocessor.lib }
\item {\em zdll.lib }
\item {\em zziplib.lib }
\item {\em xerces\-c\_2.lib }
\item {\em devil.lib }
\item {\em glut32.lib }
\item {\em OpenGL32.Lib }
\item {\em glu32.lib }
\item {\em glew32.lib }
\item {\em glew32s.lib }
\end{itemize}

The libraries can be found in the following directories.

\begin{itemize}
\item {\em trunk/Lib/Vis/Preprocessing/lib/Release }
\item {\em GTP/trunk/Lib/Vis/Preprocessing/src/GL }
\item {\em NonGTP/Xerces/xercesc/lib }
\item {\em NonGTP/Zlib/lib }
\end{itemize}

The following include directory must be added to your Solution.

\begin{itemize}
\item {\em GTP/trunk/Lib/Vis/Preprocessing/src }
\end{itemize}

In order to employ the preprocessor in a target engine we must make
the visibility solution (PVS data) available in the engine.
For this purpose we associate the entities of the engine with the PVS
entries from the visibility solution. 
For this purpose the user must implement a small number of interface classes
of the preprocessor.
We demonstrate this on a small example, which shows how to access preprocessed visibility 
in the popular rendering engine Ogre3D. Of course, the implementation has to be adapted 
to the requirements of a particular target engine.

\begin{verbatim}
// this class associates PVS entries 
// with the entities of the engine.
OctreeBoundingBoxConverter bconverter(this);
	 
// a vector of intersectables
ObjectContainer objects;

// load the view cells and their PVS
GtpVisibilityPreprocessor::ViewCellsManager *viewCellsManager = 
         GtpVisibilityPreprocessor::ViewCellsManager::LoadViewCells
                                   (filename, &objects, &bconverter);
\end{verbatim}

This piece of code is loading the view cells into the engine.
Let's analyze this code. There are three constructs that need explanation, the
BoundingBoxConverter and the ObjectContainer, and the ViewCellsManager.

\paragraph{BoundingBoxConverter}
\label{sec:BoundingBoxConverter}

This is one of the interfaces that must be implemented
In this case, we implemented an OctreeBoundingBoxConverter for the Ogre OctreeSceneManager.
The bounding box converter is used to associate one or more entities (objects)
in the engine with each pvs entry of the visibility solution. This is done by 
geometric comparison of the bounding boxes. 

In the current setting we compare not for equality but for intersection.
All entities of the engine intersecting a bounding box of a PVS entry are 
associated with this PVS entry. This means that often more than one entity in the 
engine will map to a particular pvs entry. This gives a slight overestimation of 
PVS but yields a very robust solution.

\paragraph{ObjectContainer}
\label{sec:ObjectContainer}

An object container is a vector of {\em Intersectable *}. It contains all
static entities of the scene.
A PVS entry must be derived from this class. To get access to the PVS of a view cell,
the user must implement this interface as a wrapper for the entities in the
particular engine.

\paragraph{ViewCellsManager}
\label{sec:Loading}

The loading function returns a view cells manager.

\begin{verbatim}
static ViewCellsManager *LoadViewCells(const string &filename, 
                                       ObjectContainer *objects,
                                       bool finalizeViewCells = false,
                                       BoundingBoxConverter *bconverter = NULL);
\end{verbatim}

The user has to provide the filename of the visibility solution, an ObjectContainer 
containing all the static entities of the scene, and a bounding box converter. 
From now on, the view cells manager is used to access and
manage the view cells. For example, it can be applied to locate the current view cell.
After this step the view cells should be loaded and accessable in the engine.

\section{Example Implementation}
\label{sec:implementation}

In this section we show an example implementation for the interface classes in Ogre3D.
First for the object class of the preprocessor, {\em Intersectable}, then for the converter class 
{\em BoundingBoxConverter }.

\subsection{Class Intersectable}
\label{sec:intersectable}

In our current setting we said that we test for intersection other than equality when
assigning the pvs entries to engine entites. Hence there can be more than one matching object 
per PVS entry, and there is a 1:n relationship. The typical wrapper for 
an {\em Intersectable} will therefore contain an array of entities corresponding to this PVS entry.
In order to use the entities of the target engine instead of Ogre3D entities,
replace {\em Entity} with the entity representation of the target engine. 

\begin{verbatim}
// a vector of engine entities
typedef vector<Entity *> EntityContainer;

class EngineIntersectable: public GtpVisibilityPreprocessor::
                                IntersectableWrapper<EntityContainer *>
{
public:
   EngineIntersectable(EntityContainer *item): GtpVisibilityPreprocessor::
      IntersectableWrapper<EntityContainer *>(item) 
   {}

   EngineIntersectable::~EngineIntersectable() 
   {
       delete mItem;
   }

   int Type() const
   {
       return Intersectable::ENGINE_INTERSECTABLE;
   }
};

\end{verbatim}


\subsection{Class BoundingBoxConverter}
\label{sec:Converter}

This is the most involved part of the integration, but it shouldn't be too difficult, either. 
A bounding box converter is necessary because we have to associate the objects of the 
visibility solution with the objects from the engine without having unique ids. This is the 
interface of the class {\em BoundingBoxConverter }.

\begin{verbatim}
/** This class assigns unique indices to objects by
    comparing bounding boxes.
*/
class BoundingBoxConverter
{
public:
	/** Takes a vector of indexed bounding boxes and 
	    identify objects with a similar bounding box
      It will then assign the bounding box id to the objects.
      The objects are returned in the object container.
		
      @returns true if conversion was successful
  */
  virtual bool IdentifyObjects(
                 const IndexedBoundingBoxContainer &iboxes,
                 ObjectContainer &objects) const
  {
    // default: do nothing as we assume that a unique id is 
    // already assigned to the objects.
    return true;
  }
};
\end{verbatim}

We give an example of implementation of a {\em BoundingBoxConverter } 
for the Ogre3D rendering engine. It is templated in order to works with any {\em SceneManager } in Ogre3D
(If you are not familiar with the {\em SceneManager} concept in Ogre3D, it does not matter).
Again, the implementation of this interface must be adapted for the requirements 
of the particular engine. 

\begin{verbatim}
/**	This class converts preprocessor entites to Ogre3D entities
*/
template<typename T> PlatFormBoundingBoxConverter: 
    public GtpVisibilityPreprocessor::BoundingBoxConverter
{
public:
  /** This constructor takes a scene manager template as parameter.
  */
  PlatFormBoundingBoxConverter(T *sm);
	
  bool IdentifyObjects(const GtpVisibilityPreprocessor::
         IndexedBoundingBoxContainer &iboxes,
         GtpVisibilityPreprocessor::ObjectContainer &objects) const;

protected:

  /** find objects which are intersected by this box
  */
  void FindIntersectingObjects(const AxisAlignedBox &box,
                               vector<Entity *> &objects) const;

  T *mSceneMgr;
};

typedef PlatFormBoundingBoxConverter<OctreeSceneManager> 
          OctreeBoundingBoxConverter;
\end{verbatim}

This class is inherited from {\em BoundingBoxConverter}.
This class has only one virtual function {\em IdentifyObjects} that must
be implemented. Additionally we use a helper function {\em FindIntersectingObjects} that 
is responsible for locating the corresponding objects in the scene. Let's now have a look 
at the implementation of {\em IdentifyObjects} for Ogre3D.

\begin{verbatim}
template<typename T>
bool PlatFormBoundingBoxConverter<T>::IdentifyObjects(
       const GtpVisibilityPreprocessor::IndexedBoundingBoxContainer &iboxes,
       GtpVisibilityPreprocessor::ObjectContainer &objects) const
{
  GtpVisibilityPreprocessor::IndexedBoundingBoxContainer::
	  const_iterator iit, iit_end = iboxes.end();
  
  for (iit = iboxes.begin(); iit != iit_end; ++ iit)
  {
    const AxisAlignedBox box = 
      OgreTypeConverter::ConvertToOgre((*iit).second);
		
    EntityContainer *entryObjects = new EntityContainer();

    // find all objects that intersect the bounding box
    FindIntersectingObjects(box, *entryObjects);

    EngineIntersectable *entry = new EngineIntersectable(entryObjects);
    entry->SetId((*iit).first);

    objects.push_back(entry);
  }
  return true;
}
\end{verbatim}

The function just loops over the bounding boxes of the PVS entries and finds the entities that
are intersected by the bounding boxes. Additionally we introduce a new class, the { \em OgreTypeConverter }.
This class is just responsible for converting basic classes like {\em Vector3 } or { \em AxisAlignedBox }
betwen Ogre3D types and Preprocessor types. Now we revisit the function 
{\em FindIntersectingObjects}, which searches the intersections for each individual box.

\begin{verbatim}
template<typename T>
void PlatFormBoundingBoxConverter<T>::FindIntersectingObjects(
       const AxisAlignedBox &box,
       EntityContainer &objects) const
{
  list<SceneNode *> sceneNodeList;
			
  // find intersecting scene nodes to get candidates for intersection
  // note: this function has to be provided by scene manager
  mSceneMgr->findNodesIn(box, sceneNodeList, NULL);

  // convert the bounding box to preprocessor format
  GtpVisibilityPreprocessor::AxisAlignedBox3 nodeBox = 
    OgreTypeConverter::ConvertFromOgre(box);
	
  // loop through the intersecting scene nodes
  for (sit = sceneNodeList.begin(); sit != sceneNodeList.end(); ++ sit)
  {
    SceneNode *sn = *sit;
    SceneNode::ObjectIterator oit = sn->getAttachedObjectIterator();

    // find the objects that intersect the box
    while (oit.hasMoreElements())
    {
      MovableObject *mo = oit.getNext();

      // we are only interested in scene entities
      if (mo->getMovableType() != "Entity")
        continue;
			
      // get the bounding box of the objects
      AxisAlignedBox bbox = mo->getWorldBoundingBox();
			
      // test for intersection (note: function provided of preprocessor)
      if (Overlap(nodeBox, OgreTypeConverter::ConvertFromOgre(bbox)))
      {
        objects.push_back(static_cast<Entity *>(mo));
      }
    }
  }
}
\end{verbatim}

Note that the implementation of this function is maybe the one that differs the most
for other engines, as it is highly depending on the particular engine design. 
For the Ogre3D implementation, we use a two stage approach. First we find the 
intersecting scene nodes. We apply a search function that is optimized for this engine. 
In case of Ogre3D, this is the function {\em findNodesIn}.
The engine is responsible to provide a function for fast geometric search in the scene,
in order to quickly find the objects intersecting the bounding box of a PVS entry. 
A spatial data structure like octree or kd-tree is very useful in this regard.
Second we traverse through the list of entities attached to the scene node. The intersection
test is then applied for each indiviual bounding box. 

\section{View Cells Usage}
\label{sec:usage}

At this point the view cells should be accessible within the target engine. The 
view cells manager provides the necessary functionality to handle the view cells. 
In order to query the current view cell, use the following function of the 
view cells manager.

\begin{verbatim}
ViewCell *GetViewCell(const Vector3 &point, const bool active = false) const;
\end{verbatim}

In the target engine, the function is envoked like this.

\begin{verbatim}
ViewCell *currentViewCell = viewCellsManager->GetViewCell(viewPoint);
\end{verbatim}

{\em viewPoint} contains the current location of the player. It must be of type
{\em GtpVisibilityPreprocessor::Vector3}. In order to traverse the PVS of this view cell, we 
apply a PVS iterator, like in the following example.
For the implementation in another engine, { \em Entity} from Ogre3D must be replaced by the
target engine entities.

\begin{verbatim}
GtpVisibilityPreprocessor::ObjectPvsIterator pit = 
  currentViewCell->GetPvs().GetIterator();
			
while (pit.HasMoreEntries())
{		
  GtpVisibilityPreprocessor::ObjectPvsEntry entry = pit.Next();
  GtpVisibilityPreprocessor::Intersectable *obj = entry.mObject;

  EngineIntersectable *oi = static_cast<EngineIntersectable *>(obj);
  EntityContainer *entries = oi->GetItem();
  
  EntityContainer::const_iterator eit, eit_end = entries->end();

  for (eit = entries->begin(); eit != eit_end; ++ eit)
  {
    Entity *ent = *eit;
		    
    // do something, e.g., set objects visible
  }	
}
\end{verbatim}