Kurt Schwehr Laurent Nguyen Viz Technical Notes Design and Implementation of the Viz Architecture Note: This document has not been edited and is a bit rough. SEE ALSO: Schwehr et al, 2003, Designing visualization software for ships and robotic vehicles. Eric Zbinden, Laurent Nguyen, Kurt Schwehr, 2000, Viz: An Automated 3D Mapping System for Planetary Exploration. 13-Sept-1998 Overview The visualization package The previous visualization package from IMG includes more features than just rendering. The design of viz is focussed on providing a solid rendering engine. The goal is to provide a more efficient basic rendering server, to allow the designer to isolate the rendering functions from the rest of the application that (s)he is designing. We focused on modular design and rapid proto-typing. We did not try to replicate the entire functionality of the Inventor API outside of the server. We used messages to try to provide a clear and simple API for several reasons: 1. To make it easy to add support for additional scripting or compiled languages. 2. To make it easier to maintain the server code. 3. Easier to learn than the full OpenInventor API -- rapid prototyping. If you want more elaborate interaction with the 3D environment or fancy stuff (TM), we recommend that you write a custom C++ Inventor application. Viz is not intended to support any arbitrary change to the scene graph or user interaction. This allows us to build a scene graph that we can count on to have a number of necessary properties. *** Why OpenInventor Choosing which graphics rendering package is always a tough decision. We chose OpenInventor for a number of reasons. On the SGI, there is no license required for runtime and IRIX ships with the runtime support libraries installed by default. We like the C++ OOP (Object Oriented Programming) design of the Inventor class hierarchy. There is a default GUI provided by OpenInventor that has a rich set of interactions. Together with the manipulators and draggers, this provides a powerful way to interact with 3D worlds. The Inventor file format (IV) provides a very powerful scene graph structure that is a superset of VRML 1. Complex applications can be written as an IV file and loaded into any Inventor application, including the stripped down program "ivview." Inventor is becoming a cross platform development environment. TGS has ported Inventor to Windows, Linux, and Solaris. TGS has also added almost all of the functionality found in other graphics packages, such as collision detection and reading VRML 2. *** Why XDR? Cause Kurt said so. XDR is designed to be a platform independent serialization protocal for exchanging data. Supported many places. Used in packages like NFS, NDDS, and NetCDF. As such, XDR libraries are available on just about every interesting platform. It provides a nice, concrete definition language that is easy to parse. The structure is similar to C structure definitions. Blah blah. Light weight and small library. *** Overview Viz is a 3D graphics rendering server. It accepts messages from clients. Clients send messages to the Viz server to modify the scene graph. Some examples messages include, add object, change color, move an object, remove an object. Clients can connect to Viz via a socket connection. Clients can be written in any language assuming the language supports socket communications and XDR encoding/decoding. Viz supports multi connections from 1 or more clients. The server provides sub-threads to process incoming messages, thus allowing the user to interact with the scene graph with minimal interruptions from communications. The GUI is provide by the default OpenInventor Examiner Viewer. *** Internal Server Design. Viz is one binary program that you run. It is a multi-threaded application written mostly in C++ with a little bit of C. *** Communications Each client connects to Viz through a TCP/IP socket connection to a designated port number (command line configurable). The client encodes each message to the server into an XDR message defined by that message's XDR definition file. The client then sends the byte count of the message to the server through the socket followed by the message name and the encoded (serialized) message. Both the byte count and message name are XDR encoded to provide a uniform format for the data stream. The server spawns one thread per client socket connection. This thread waits in a loop with a select call on the socket. Once a message arrives, it decodes the byte count and message name. Then it sucks in the entire message. Once the message has been completely received, it calls the xdr deserialize function call for that message type. Depending on the name of the message, it processes the message. The name is used to retrieve the processing function from a lookup table. A preprocessing function is retrieved from the lookup table. This is the main work function for each call. We try to do as much of the processing as possible here, inside of the socket thread. Depending on the message, the preprocessing function will search the scene graph, create new sub-scene graphs, and read data from disk. After the prep function executes, it will enter all of this information into a queue of commands to be executed in the main viz thread to modify the scene graph. The queue. The queue is present because only one thread can access the scene graph at a time. OpenInventor is not designed to be thread safe. We allow only the renderer thread to modify the scene graph. All other threads that want to modify the scene graph must queue their changes for the render thread to process. The queue is a queue of commands. Each command is completely self contained object. It includes a function to modify the scene graph and the necessary data and pointers to accomplish those tasks. We use a superclass as a virtual base class. Each command type is a subclass that defines the data needed and how to actually change the scene graph. An example, the add command. It contains a pointer to the parent node in the scene graph and a pointer to a sub scene graph that was created in the prep command of the new object. The modify scene graph function then does an add child of the new object to the parent. Thus the render loop never has to wait for the creation of the new object. *** Renderer Thread The role of the renderer thread is to provide the user with responsive interaction with the scene graph and to execute queued commands from the communications threads. At a given frequency and during a given period of time, it will check the queue and execute any pending commands. DESCRIBE how the execution timing works. Client Each client is a separate heavy weight process (program!) Clients can be on the same machine or distributed across a network. They can be part of a separate application, a small GUI, or a script. Anything that can send XDR encoded data through a socket can be a client. [Maybe this next stuff does not belong here.] So far, we have implimented client support for two languages: Python and C. Adding languages is fairly easy and could be done by in a couple days at the longest. Each language requires two components to support writing clients. The first is socket support. The second is a code generator to produce code for each message that serializes and deserializes the data into XDR format. We have written a generic XDR parser in Flex and Bison (GNU versions of Lex and YACC). This parser produces a parse tree data structure. It is then a simple process to write a small bit of C code that walks the parse tree to produce the XDR code for whatever language. The Python scripting language has turned out to be very easy to work with generating clients. Each message is implimented as a class. After you open a socket, you can create a message and tell it to send itself to the socket. Where has viz been used? List All the applications. Jimmy Villard's work. Supposed to be a masters theasus on sensor data visualization. He tried to represent multi-dimensional data graphically. So, define a generic model of the scensor data create rules to display this data based on the number of dimensions and application. He used Viz as the visualization tool. He did not have to modify Viz. He wrote a program that gets as input the sensor data and formats the data in such a way, translates it into his model. The program is a C client to Viz that uses Xforms for its 2D GUI. Note that it was tricky for vizualization. There was not any real interaction with the user accept for moving the view point. No data was returned to the client from Viz. The performance of the rendering engine was sufficient. Only small datasets were use. He was able to display realtime data. Integration with Viz took him two weeks while he was writing the basic client. TROV -- Alex -> fill in more It has been use to represent 3D models of TROV in a fake terrain for the Oceans conference. This was again a one way client. A 3 axis compass was connected via serial port to an SGI. A Python interface, derived from the Nomad Virtual Dashboard, displayed a 2D compass. This interface then converted the compass data into commands for the TROV model in Viz. This was the first major usage within Viz of the animation and manipulation powers provided by OpenInventor. An engine was connected to the propellers to turn them at a rate proportional to speed. A dragger was attached to the vehicle allowing the user to move TROV about the 3D world. Manipulators were attached to the forward camera's pan/tilt unit. 3D fly through client. What did Alex do with Viz in the Arctic. You did at least run it up there, right? Otherwise, we come to Cleveland and break some kneecaps. Walker -- Neek the Meek, Nick: write this. The walker was cool. The IMG is currently designing and developing a walking robot, lead by Hans Thomas. Hans is too lazy to build the real hardware, so Nick was tasked to build a computer simulation using Viz. The simulator computes robot-terrain interaction outside of Viz. In order to study the behavior of various walking algorithms before the hardware is built, Nick Vallidis, design a python client. Nick Vallidis has implimented a simulator of the leg planner. Previous Art / Other work / Related programs Arc/Info by ESRI GRASS GRASS is a free Geographic Information System (GIS) package developed by the Army Corps of Engineers. GRASS is the first place that one of the authors saw the rendering system strongly separated from much of the processing of 2D and 3D data. Discuss SGI3D. IMEdit www.innovmetric.com IMEdit is another program that has the ability to measure. We frequently use IMEdit to reduce the models we load into Viz. VTK - Visualization Toolkit -- It's lots of stuff. A graphics library wrapped on OpenGL. VEVI 3 VEVI 3 was developed by the Intelligent Mechanisms Group by a privious set of engineers. VEVI 3 is based on World Toolkit 2.1 for rendering and NDDS 1.9 for communications. The program was succesfully used for several robotics missions including CMU's Dante 1 and 2, TROV, and Marsokhod. VEVI 3 does not use a scene graph, as World Toolkit did not have the concept of a scene graph at the time VEVI 3 was developed. VEVI 3 provided the inspiration for much is what Viz is. We tried to improve on the system performance and scriptability. VEVI 3 introduced two concepts, Vshell and Vscript. For Viz, these became our python shell for Viz. We decided that we did not want to write our own scripting language and were frustrated with programming in Tcl, so we went with Python. Execution of VEVI is controlled by files know as Vevi Configuration Files (VCF). VEVI had 2D image billboards and was integrated with Netscape to provide links to user data. VEVI 5 [What can we say here without revealing 4th Planet technology?] The developers of VEVI 3 decided to spin off a company from NASA Ames that is known as Fourth Planet. Since leaving NASA, Fourth Planet has been continually developing VEVI for use in a number of projects, such as Ford factory automation and ???, for visualizing large computer networks in real time. They have ported VEVI to Solaris, HP-UX, and Windows NT. They have changed the networking from NDDS to FPcom, their own, in house, communications package. The storage of the 3D world has, independently, been changed to a scene graph structure that is similar to that of Viz. [ I don't know if that is proprietary information to 4P]. DVIEW by Patti Konig DView has been under development at NASA's JPL for a number of years. DView is based on OpenGL and Motif. It integrates a number of large packages from JPL to support planetary missions, including SPICE. It provides an external scripting interface with the Tcl language. It is not multithreaded. It runs on IRIX, Solaris, and Windows. It is being ported to Java 3D. MarsMap MarsMap was developed by Ted Blackmon at UC Berkeley. It is a World Toolkit based application developed from Blackmon's previous work on the Mars Virtual Explorer at Berkeley. MarsMap was used by the Intelligent Mechanisms Group (IMG) for the Mars Pathfinder mission. MarsMap provides a good example of the some of the common techniques of measuring distances and angles of a 3D model by picking with the mouse into the scene. This and other techniques can be found in CAD, GIS, and mesh editing tools. MarsMap has since been modified and renamed to the Intelligent Modeling System (IMS). A number of communications schemes have been used to couple IMS to robots such as Pioneer, for Chernobyl. Division -- dVISE Deneb -- Telegrip & RobCAD www.deneb.com igrip, etc. Why did we not use something like Deneb. Expensive. It is more suited to factory/industrial applications, structured environment where prior knowledge of the world objects. igrid does not deal well with very large unstructured terrains. It has a predefined world. libptk -- EPFL -- Laurent, get your act together. WITS -- JPL Muse - 3D collaboration tool. *** Section on Rendering Engines. WTK OpenInventor VTK OpenGL Performer Direct3D ----------------------------------- Describe how the Tcp/IP sockets work. There is one thread that listens to the service port. It does a listen (check this) is a loop. Every time a client connects to Viz, this thread spawns a new thread. The accept function assigns that client a new port number to the socket descriptor. You have 1 socket descriptor for each thread-client combination. Each working thread associated with that client. Each working thread does a select in an infinite loop that can be broken by the quitting or breaking the connect. Once a second, the select times out to let the loop check to see if it should terminate from either the quit flag being set or the socket being closed. Describe the lookup table for incoming command handling. The lookup table is implimented as an STL map. The each map entry has a message name associated to a pointer to a function. Upon initialization, the STL map is created and filled with these entries and remains constant for the rest of run time. The function pointer is a pointer to the process function that knows how to create the class for that type of command and run the prep function. In the map, you have the message name and a pointer to a function. That function is a process function that calls the prep function. So every time a new message arrives, you use the map to get the pointer to get the process function. That process function will create a command object instance and will call the prep method of that command object, passing the XDR string as an argument. The prep command will XDR decode the message and then preform the necessary operations on the scene graph to do as much work as possible with out modifying the scene graph. The process command creates this new object and once prep is done, it adds the command to the queue. *** Descripe the queue and how it works. The queue is known in OOP technologie... Everybody knows about the queue. The working threads and the rendering thread know about the queue. The queue is owned by the render queue -- contained in the render class. The queue impliments a First In/First Out (FIFO). The queue contains a command class known as SceneOps. It is a queue of renderer commands. The renderer command is a wrapper around the SceneOp command. It contains two pointers, previous and next, to impliment a doubly linked list. The queue contains SceneOps objects. The queue's internal data structures are protected by semaphores so that it is thread safe. The trick is The idea is that ivQueue knows about sceneOps. About the queue. You can add an object to the queue. You can execute the queued command. If you execute a command, the queue will execute the SceneOps's mod scenegraph function and then remove the command from the queue. This is done with in the renderer thread context. **** Describe add command. The add command is a 2MB file. The add command does way too much. What Laurent knows about the add command. The Add command is a derived class from sceneOps. The main functions are prep and modScene. prep is the most complex command. The add command allows the user to either load a model into viz from a file or use a modified URL. create the basic geometric primitives. Example walkthrough of an add command of a file. First, the prep command is executed. It xdr decodes the message. Using the parent name in the message, add searchs for the parent node. The search is a bit complicated. (Could write search description elsewhere.) Search first looks through the queue for temporary objects not in the scene graph. These objects are waiting to be inserted into the scene graph. This was one major race condition that we did not think of ahead of time. If it does not find the parent in the queue, it looks in the scene graph using a search starting at the root node. If it does not find the node, it fails. [Back to queue... the queue maintains a map as well as the command queue. In this map, the entry is the object name. A link list of nodes is attached to that name. This way you can quickly find a node that has been added. We need a link list to associate several nodes with each name. For example, if you want to add an object and right after that you want to change the color, the change color node is not put into the scene graph either. You can specify which type of node to search the queue for. Now back to our regulary scheduled programming...] [need to mention that the add action defines the scene graph structure.] Now that we have parent node, we begin creating the sub scene graph. We create a separator node. We then parse the pseudo URL to see what kind of object we are adding. If it is not a special marker, e.g. "shape:" or "http:", we assume that it is a file on disk. Assuming that it is a file on disk, we call the Inventor SoDB::readAll call with the filename. All relative paths end up being relative to where Viz was started. This is often confusing. People often think that a file will be found relative to the client. File lookup happens in the normal manner encounter in the Unix file system with calls such as fopen. The scene graph created by SoDB::readAll is attached to our special sub-scene graph. We store the root pointer for this subscene graph and the parent pointer into the Add class and queue the command. Inside the renderer loop, this add command is eventually pulled off the queue and its modScene method is called. modScene then simply does an addChild to the parent of the root of the sub scene graph. [Talk about how we handle other URL types. 3D text, 2D text, ftp:, http: billboard:] We use a python script known as getURL. Laurent wants to say more about the add command. What a punk. There is an issue about the add command. Adding an object is different from adding a camera. When you add a camera, it follows a different structure. The position and orientation are embedded inside the camera node. Same applies for lights. If not, blame Laurent. *** What happens during a render loop. We can divide what happens into two things. One class/part is the Inventor events, like keyboard, mouse. It is all the call back stuff and user interaction. The other part is the timer which really is just an event allong with the mouse and keyboard, but should be considered as a very different beasty. Basically, the only relevant call that is inside the renderer thread function is Inventor::mainLoop(). Everything else is defined in the callbacks. There are two parameters that control the execution of the the time callback. First, the frequency at which the time goes off. Second the amount of time we allow for executing queued sceneOps. Inside this timer callback, check the queue for new commands. We pull out the next sceneOp, execute its modScene method, and then destroy the sceneOp. This is repeated until we run out of time allowed to execute queued commands or we find the queue empty. If we have a low frequency, we have slow responce from viz. There is a higher latency from when a command is sent to when it actually effects the scene graph. Second is the length of time that is allowed to execute commands. Everytime the timer event goes off, the callback records the current clock time. It then executes a command off of the queue and check to see if it has run out of time. If there is time left it will try to execute another sceneOp. This was to try to make sure we allow the renderer thread a better chance to maintain the update rate. We did not want to have the rendering engine pause for long periods of time if viz gets a burst of commands from clients. One limitation is that if one command takes a long time, the renderer thread is blocked until it executes. Most sceneOps are designed to take the minimum amount of time possible. Some exceptions are the printToFile and saveSceneGraph functions which must white large amounts of data without the scene graph being modified while the run. Another interesting effect of both the frequency and length parameters that frquency gets lower and length increases, is that commands that effect the same object may be overridden by following commands before ever scene by the user. Two examples: First if an object is command to be red and then commanded to be blue and both commands are executed in one timer callback, the user will only see a blue object. Add/remove example. This is both good and bad. It is bad because you may not see the effect of all the commands that are sent to viz. Interesting events may be hidden. The good part is that if you maintain your latency low enough, what is displayed in viz is realtime. What you see is the latest update. If you have all these updates come in, a system that shows you all the changes, it will start showing you later and later times. E.G. A user can only see changes faster than 60 HZ by slowing down the rate of display to something slower. *** Billboard engine The billboard is run by using a sensor. Deanne: write this section. *** Command Line Options --debug-level=num --input-port-number=num --log-file=name --iv-timer=int Timer interval in ms. --iv-execute=int in millisec --follow-cursor=bool --version --help **** Keyboard h - help l - add directional light editor t - terrain following rover -/+ on the keypad -- timing level. Reading mail and news! :) The '+' and '-' keys are mapped to an internal variable known as the debug level. This allows the user to increase with + and decrease with - the amount of debugging information sent to stdout. At higher levels, the amount of information sent to stdout will great effect the behavior of the system, so this information is generally not produced unless needed. The 'p' key. If you drank to much, this is what you must do. The p key prints the entire scene graph to stdout. This is very useful debugging small scenes. It can take a VERY long time is there are many objects, especially polygon meshes. Then it is a bad idea to hit the 'p' key. 't' starts the terrain following rover. This should be explained in its own section. ? ? Are mapped to the time level. This was the beginning of performance monitoring additions to viz. This feature has not been fully implimented. We were planning to use this to provide quantitative data on how long certain sections of the program take to run. 'q' is the end of the world as we know it. q quits out of viz without asking! Is this a feature or a bug? Some say feature! 'm' is the mail key ala www.JWZ.org. It tells netscape to bring up its mail reader. 'n' tells netscape to start reading news. m and n are in Viz to make Kurt happy. They illustrate how to interface with Netscape from separate programs. Mouse Click click click... *** Describe the scene graph layout. So... The scene graph organization is built on an intelligent database that tries to increase the systems information entry in a top-down, bottom-up heirarchical oct tree. As a result, our system is better than yours. The scene graph is organized base on objects, "object centric." The scenegraph is a heirarchical collection of objects. Each object has an associated sub-scene graph. The basic form of the sub scene graph is a separator as a root that contains the name the objects in its name field. Root is the parent of a number of components that viz counts to be present. The mandatory components are, in order, a translation node, a group node contianing x, y, and z, rotation nodes, (euler x, y, z rotations), and then the geometry node(s). There are option nodes that are not required to be present to save on memory. The occure much more rarely, so we decided to only add them when necessary, on the fly. The optional nodes are material node, scale, and drawing style. These nodes are contained between the geometry and rotation group node in the scene graph. All child objects are added at the end of the roots children, after the geometry, on the right side. The camera and light nodes unfortunately do not fit in this scheme. :( We have to note that special nodes have special reserved names starting with "_". There are other nodes like sensors and other customized code that also do not conform that are used in other portions of viz. These generally are not acted appon by the standard viz commands. Viz is using a fixed organized scene graph that cannot be modified from outside. The user does not have artibrary access to the scene graph. We want to mention allowing the python swig stuff will not work. This prevents doing things like running swig on the entire Inventor API and allowing inventor scripting clients to be executed by the renderer thread. If this were to be allowed, total chaos would ensue. The other things is that we can create Inventor files that are Viz compatable -- they contain scene graph sections that follow the Viz specification for objects. This allows objects to be create with hooks for clients to modify their behavior. For example, it is possible to create an entire robot in one Inventor file. Each joint can be named so that clients can move all of the robots degrees of freedom. We need to talk about the sensor problem, aka the sensor question. Kurt was working on the url interface to Netscape, www url inline. What happened with Kurt's timing measurements. Didn't get very far. Coding Style. How did STL work for us? How successful/useful/painful? The build structure. Kurt talk about this. What are the major limitations of the this architecture? Is is possible to make Viz independent of the rendering engine/graphics library? The terrain following problem? Under future work, is the concept of Viz as a library. Was a cool concept. But defeats the purpose of having something that is easy to run and then you just connect to the socket, but gives you more flexibility. You can add callbacks and redefine behavior. Under limitations. The Main arguments, as features are added, we have to impliment a new message to support the new feature. We see that the socket language could easily explode and become a real pain/maintanance hassle. We have not really solved the problem of how to deal with output from the viz engine to the clients. We had a couple of strategies. How do we deal with queries, if at all. How do we deal with only some clients wanting subsets of messages. Do we want to add an object database or some way of using the scene graph to allow clients to know what objects exist in the world. << Big issue! There are still questions about what is really needed for thread stack sizes. The default was definitely too small. *** Did we actually talk about implimentation? We described how it works. The design seems not so bad, but where we hide data frequently leads to too much cross talk between classes. It is very lame. It is not really object orieented. Outside of sceneOps, all classes only have one instance. We are not using inheritance. STL is only used in a couple locations. There are two STL maps. Server class is only instanciated once. Ivqueue, IVthread, etc are only instantiated once. MORE STUFF AS OF 23 SEPT: *** Description of all the Viz commands. *** Still need future directions and ideas. References: Fourth Planet Inc, ??? Main Street, Los Altos, CA., http://www.fourthplanet.com Dante 1 & 2, www.frc.ri.cmu.edu DVIEW, Patty Something, http://dview.jpl.nasa.gov VEVI 3, http://img.arc.nasa.gov/vevi ?? VEVI 5, Fourth Planet, http://www.fourthplanet.com