July 15, 1993		1

What is Group 3?
Prepared by Jerry Isdale [72330,770], Project Leader
(In Progress: 
  * Animation Language ideas
  * Driving problems: escher, disabled, physics lab, etc.
  * Sub projects (HMD, Object Maker, Gloves, etc)

July 1993 - with the demise of Group3 and itsreplacement by the 
Cyberforum Workgroups. I am not going to work on this paper further. 
(it's been a long time since i even had time to look at it!) It is provided as 
a historical reference.  Interested readers should also see files named 
WE*.* as these were earlier uploads by various people on the World 
Editor.
------------------------- Table of Contents --------------------
1.	Introduction
2.	What is Group 3?
2.1.	What's in a Name? (Origins of "Group 3")
2.2.	Group 3 File Repository
2.3.	Stone Soup Software Development Method
2.4.	Making a Living
3.	Our Approach: World Editor/World Player
3.1.	World Player
3.2.	World Editor
4.	Coding Standards
5.	World Space
6.	Objects
6.1. Position/Orientable
6.2. Hierarchy
6.3. Motion Scripts
6.4. Trigger Scripts
6.5. Named Attributes
6.6. Object Geometry
6.6.1. Vertex Join Set Polygon Format
6.6.2. Bounding Volume
6.6.3. Sample Format:
6.6.4. Geometry Conversion
7.	GUI - 2D graphical controls
7.1. Buttons
7.2. Scroll Bars/Sliders
7.3. Gauges
7.4. Text Display & Inputs
8.	Image Rendering
8.1.	Rend386
8.1.1.	Problems with Rend386
8.1.1.1.	Documenation
8.1.1.2.	Coding Style
8.1.1.3.	Error Messages (or lack thereof)
8.1.1.4.	WorldDescriptions
8.1.1.5.	Object Descriptions/creation
8.1.1.6.	Fixed Resolution
8.1.1.7.	Visibility Errors
8.1.1.8.	Splits & interactive support
8.1.1.9.	Color Scheme
8.2.	Suggested Renderer Development Path
8.3.	Renderer Developement
9.	World Description File
9.1.	Player Configuration Section
9.2.	Scene Description Section
9.3.	Object & Geometry Description Files/Section
9.4.	Object Actions & Triggers
10.	WDF Interpreter

------------------------- --------------------

1.	Introduction

This paper (Group3.txt) is an introduction to the Group 3  homebrew 
Virtual Reality development project . It was prepared by Jerry Isdale, 
leader of the Group 3 project at the time (March 1993). It is the second in 
a series of papers. The first was an introduction to Virtual Reality from 
the homebrew perspective. The third paper is a more detailed discussion 
of the Group3 project direction and my personal ideas for the 
development of a homebrew Virtual Reality system.
2.	What is Group 3?

Group 3 is an ad hoc group of developers on Compuserve, operating out 
of  the GRAPHDEV (Graphics Developers) Forum, Virtual Reality 
Sections.

The intention of the group is to develop public domain software for use 
on  low  cost (stock and augmented) personal computers that allows the 
user to create  and experience virtual worlds.
 
The preliminary goal is to create a World Editor/World Player (WE/WP)  
system built on a World Description File (WDF). It is our hope to make 
the system portable to different personal computer systems. However, 
initial development will be done on MSDOS (ibm compatible) systems, 
primarily due to the availability of the fast image rendering software, 
REND386.
2.1.	What's in a Name? (Origins of "Group 3")

There are two meanings behind the name "Group3". The first is that our 
development group was the third group of software developers to be 
supported by the GraphDev forum (actually, the ComArt forum, our 
previous home). The earlier two groups being the Stone Soup Group 
(Fractals) and Persistence of Vision (Raytracing).

  The second meaning derives from a division of people into three groups 
based on their response to technology. The first group are those opposed 
to the use of Technology (Ludites, etc). The second group are those who 
are quite willing to use established technology, as long as it doesnt 
require too much effort/risk. The third group are the pioneers, willing to 
go out into uncharted techonological frontiers and experiment upon that 
shaky ground. VR is definately an uncharted emerging technology.

2.2.	Group 3 File Repository

[NOTE: the files from Group 3 have been moved to CyberForum. Lib 2,3, 
and/or 4]

The GraphDev VR Tech library (Lib 11) is the repository for all code and 
documentation for the project. To help organize the library, 
documentation files directly relating to the WE/WP project are named 
starting with 'WE', followed by two initials of the author and two digits 
indicating order in sequence of author's uploads. For example prior 
works by Jerry Isdale are called WEJI01.TXT, WEJI02.TXT, etc.

2.3.	Stone Soup Software Development Method

Group 3 is part of the Stone Soup development groups on CompuServe, 
all operating out of the GraphDev forum. There are five development 
groups in the forum, one each for fractals, raytracing, virtual reality, 
morphing and animation. Each of these groups follows what is called the 
'Stone Soup' method of software development. This name derives from 
the following story:

Once upon a time, there was a shortage of food upon the land. People 
horded their foodstuffs and became unsociable. In this time, a peddler 
came to a small village. As evening fell, he had no food and none was to 
found for purchase. The enterprising peddler set up a large pot over a 
large fire and filled it with water. All the while he talked loudly about the 
wonderful "stone soup" he was going to make. He took from his peddler's 
cart a velvet bag and withdrew from it a medium sized stone. He put the 
stone into the water. As he stirred the water, he sniffed it and said 
"Mmmm, Stone Soup! What a delight! How wonderful!" The townsfolk 
peered cautiously out their windows at this strange fellow. "There is 
almost nothing in the world I like more than Stone Soup" he continued. 
"That is, unless it is Stone Soup with Cabbage! Now there is a really 
wonderful meal!"  Well, from out of one of the houses, a townsperson 
crept and said "I have a small cabbage. If I add it to the soup, will you 
share with me?" "Certainly!" said the peddler, and dropped the cabbage 
in! The two of them stood in the townsquare smelling the soup as it 
began to boil. "Youknow," said the peddler, "Stone soup with cabbage is a 
delight, but Stone Soup with cabbage and Carrots! now there is a 
REALLY wonderful meal" Out came another townsman with some carrots 
that were added to the pot. This continued with the peddler and his new 
friends sniffing the pot and thinking of other things to add. More 
townsfolk came out with their horded ingredients and dumped them into 
the steaming pot. Soon there was a wonderful stew cooking and there 
was enough food for everyone. Musicians appeared and soon there was 
dancing. The townsfolk and the peddler had a grand time cooking and 
eating the soup, dancing and celebrating.

Thats how our Stone Soup groups are developing their software. First 
someone comes round with a simple package that kinda does the job. 
Then someone else adds a bit to that code, and this entices more people 
to get involved. Soon there is a very complete and useful package 
available, all done with public domain source code. The FractInt program 
is one of the best success stories of this method. From its humble 
beginnings, it has grown to have hundreds of contributing authors.

2.4.	Making a Living

How can we give away such complex, programs? 1) it is not our primary 
employment (some of us are in school) 2) we are helping to create a 
public standard, this gives us a) an inside track on that standard for 
commercial contracting and b) advertising our selves. 3) writing books, 
articles, etc from the knowledge learned. Helping to distribute the 
knowledge to the rest of the world.

3.	Our Approach: World Editor/World Player

3.1.	World Player

The World Player reads the World Description Files (includes object 
geometry, actions, etc), gets inputs from user controls, handles 
interaction, object actions, etc and generates the outputs (images, 
sounds, etc.) It might let you save the current World State to re-enter 
later (save game feature).

The basic world player program (aka Reality Engine) function is:

	Load World Definition (and associated files)
	Initialize inputs, objects and displays
	LOOP (till exit or enter editing, each iteration = 1 TICK) 
Get Inputs (update controlled values)
Process Actions ( interpret motion scripts, controlled objects, 
triggers)
2D GUI update
3D Render (invoke renderer with objects at current TICK)

The player maintains a number of lists: Controlled Objects (objects that 
receive data from inputs), Objects in Motion, Objects with Triggers, 
Objects  visible to Renderer

3.2.	World Editor

The World Editor can do all the World Player functions, PLUS it can 
create and modify objects and their actions (reactions, personality, etc). It 
can also create and modify world parameters (eg this 'room' is dark, or 
has background color N). 

The WE provides simple object geometry manipulations. It is not a full 
fledged CAD system, but it does support importing of geometries created 
with CAD systems.

The WE provides text editing cababilities for the scripts that define object 
actions. It should also provide support for a library of predefined objects, 
rooms, etc. The world designer could copy these into the current world 
definition and modify them.
4.	Coding Standards

The issue of code standards and language can be very important and 
also a  very personal (almost religious) issue. To facilitate the goal of 
portability, the C programming language will be the primary development 
vechicle. There are those who would wish to use C++, and they are 
welcome to do so, however, that language is not standardized and thus is 
not portable. Furthermore, object oriented programming has many 
pitfalls that require careful and experienced design to avoid.

  We need to have some basic code libraries to facilitate development. For 
instance, a list manager,  a good set of matrix routines (3x3 & 4x4, do 
not need NxM flexibility, need SPEED), and routines for reading and 
manipulation of geometry files (similar to those in iegeom.zip)

5.	World Space

Previous discussions have covered the need to have a limited 'stage' on 
which the visible actions occur. This allows fewer objects to be computed 
both for scripts and for rendering. There should be multiple stages (aka 
rooms, areas, zones, worlds, multiverses, etc) and a way to move between 
them. The dimensions of these stages will be limited by the precision 
used for coordinate representation. Floating point representation allows 
for a very large range of coordinate values, but has significant processing 
costs. Also, the distribution of floating point numbers is not uniform 
across the entire range values. Very large values lose precision that is 
present in smaller values. (eg. may not distinguish between 1.3x10**20  
and 1.3x10**20 +1).  Fixed point representation can allow for large stages 
without the FP costs and it provides uniform distribution of coordinates.

6.	Objects

Objects in the virtual world can have geometry, hierarchy, motion, 
triggers, and other attributes. The capabilities of objects has a 
tremendous impact on the structure and design of the system. In order 
to retain flexibility, it is suggested that objects support a list of named 
attributes with value pointers. Thus attributes can be added to the 
system without requiring changes to the object data structures.

Objects in the virtual world can have a number of attributes. 

6.1. Position/Orientable
First, an object is positionable and orientable. (i.e. you can apply matrix, 
translation and rotation operations to it). 

6.2. Hierarchy

An object may be part of an object part HIERARCHY with a parent, sibling, 
and child objects. Such an object would inherit the transformations applied to it's 
parent object and pass these on to it's siblings and children.

6.3. Motion Scripts

An object may have one or more MOTION SCRIPTS defined. Only one 
motion script should be active for an object at any one instant.  Motion scripts 
modify the object's position, orientation or other attributes based on the current 
system Tick. This is a potentially powerful feature, depending on how complex 
we allow these scripts to become.  Care must be exercised since the interpretation 
of these scripts will require time, which impacts the frame and delay rates.

6.4. Trigger Scripts

An object may have one or more TRIGGERS. Example triggers are collision 
and proximity detectors.  The WP system needs to evaluate the trigger 
parameters at each TICK. For proximity detectors, this may be a simple distance 
check from the object to the 3D eye or effector object (aka virtual human) 
Collision detection is a more involved process. It is desirable but may not be 
practical without offloading the rendering and some UI tasks from the main 
processor.

6.5. Named Attributes

To allow for future expansion, objects should support NAMED ATTRIBUTES. 
These are attributes that are addressable by name (i.e. cube.mass => mass of the 
cube object). They may be a scalar, vector, or expression value. They may be 
addressable from within the motion or trigger scripts of their object. They might 
be accessible from scripts in other objects.

6.6. Object Geometry

It would be wonderful if the WP could support a variety of different 
geometry forms, (e.g. polygons, spline surfaces, CSG models, procedural 
geometry, etc). However, such flexibility comes at a tradeoff in rendering speed. 
Thus the WP will initially support only a Vertex Join Set Polygon format 
geometry. When augmented homebrew VR systems become available, more 
forms can be supported.

The geometry and possibly object formats should be available in both ascii 
text  and a binary format. Binary is much more desireable for rapid file loading.

6.6.1. Vertex Join Set Polygon Format

Vertex Join Set Polygon Format means that for each object there is a common 
pool of Points that are referenced by the polygons for that object. Transforming 
these shared points reduces the calculations needed to render the object. (A point 
at the edge of a cube is only processed once, rather once for each of the three 
edge/polygons that reference it.) The geometry format should support 
precomputed polygon and vertex normals. Both Polygons and vertices should be 
allowed a color attribute. Different renderers may use or  ignore these and 
possibly more advance surface characteristics. Precomputed polygon normals are 
very helpful for backface polygon removal. (the PLG format used by D. Stampe 
is an example

6.6.2. Bounding Volume

Additionally, the object geometry should include a BOUNDING VOLUME. 
The simplest bounding volume is the Bounding Sphere, specified by a center and 
radius. This data can be used for rapid object culling during renderering and 
trigger analysis. Objects whose bounding sphere is not within the viewing area 
need not be transformed of considered further during rendering. Collision 
detection with bounding spheres is very rapid. It could be used alone, or as a 
method for culling objects before more rigorous algorithms are applied.

6.6.3. Sample Format:

OBJECT cube1
BOUND x y z radius
PARENT cube0
SIBLING cube2
CHILD cube4
SIZE npoints npolygons nvertices
POINTS
x y z Color=c Norm=(x y z)
....
POLYS
nvtx v1 v2 v3 ... Color=c Norm=(x y z)
.....
END OBJECT cube1 

Alternatively, there may be a distinction between the object attributes and the 
points/polygons of the geometry. The object portion may contain only the  
(Bound, Hierarchy, Attributes) and reference a named GEOMETRY. This method 
would allow for instancing of the geometry data file (several objects could share 
a common 'cube' base geometry.)

6.6.4. Geometry Conversion

There will need to be a set of geometry file converters to import objects 
created with various 3D modeling and CAD programs. The PLG, Movie.BYU,  
OFF and DXF are example formats for which some code

7.	GUI - 2D graphical controls

The user interface to the VW might be restricted to direct interaction in 
the  3D world. However, this is extremely limiting and requires lots of 3D 
calculations. Thus it is desirable to have some form of 2D Graphical user 
interface to assist in controlling the virtual world. These 'control panels' 
of the would appear to occlude portions of the 3D world, or perhaps the 
3D world would appear as a window or viewport set in a 2D screen 
interface. The 2D interactions could also be represented as a flat panel 
floating in 3D space, with a 3D effector controlling them.

 Furthermore, the WE will need a GUI to perform its activities.

There are four primary types of 2D controls and displays. (controls cause 
changes in the virtual world, displays show some measurement on the VW.) 
Buttons, Sliders, Gauges and Text. 

There will need to be a definition for how the 2D cursor effects these areas. It 
may be desirable to have a notion of a 'current control' that is the focus of the 
activity (button pressed, etc) for the 2D effector. Perhaps the arrow keys on the 
keyboard could be used to change the current control, instead of using the mouse 
(which might be part of the 3D effector at present). 

7.1. Buttons

Buttons have an area, a hilite methods, and an action. A button can be 
selected and activated. These may be two separate operations. Selection means 
that the button is current focus of the 2D Effector device. (i.e. a button may 
change color/hilite when the mouse cursor passes over it.) Activation causes a 
hilite change on the button and invokes the button action.

Button Action may be used to control head position/orientation, or a wide 
range of other world player control variables.

7.2. Scroll Bars/Sliders

Scroll Bars and Sliders may have several Active (selectable) areas, a 
Proportional Slider, and its parameter links. The selectable areas might be the 
grab & drag slider, scroll buttons at ends of slider, the background area around 
the slider. Different GUIs (Mac, Windows, Motif, etc) have different types of 
scroll bar/slider selectable control areas. Some scroll bars allow the size of 
floating slider to give an indication of proportionate size.

Sliders will generally be attached to some linear control value, with minimum 
and maximum values. Perhaps the scale will wrap around (i.e. controlling 
roll/pitch/yaw of eye or object) and function more like a dial.

7.3. Gauges

Gauges are used to give feedback on some parameter of the virtual world. 
They have an Area, a float/fill style, and a parameter link. The area defines the 
screen area and image for the gauge. The floater or fill style defines how the 
gauge shows the relative value of its parameter.

7.4. Text Display & Inputs

Text displays and text input boxes are very useful interaction items. One 
advanced text input might be an interactive  World Description File editor. Text 
displays might be considered a form of Gauge, while input areas might be 
considered a type of slider control. 

Indeed a UI might allow the user to specify the eye position with sliders for 
approximation, text boxes for exact specification, and buttons to reset to 
predefined, or saved (undo?) values.

8.	Image Rendering

Rendering images of the virtual world is a critical component of any VR 
system. The rendering subsystem will be used by both the WE and WP 
systems. It would be useful to have a variety of rendering methods and 
resolutions to choose from, such as wireframe, solid color, shaded image, 
etc.  Higher resolution images may be desired when examining detail (ie 
creating geometry) and fast screen response is not as critical. These 
requirements indicate a need for a rendering program interface (api). 

The WE/WP does not define the exact rendering algorithm, or method. 
Instead an interface to the rendering engine is defined. The actual engine used 
might be a wireframe, flat or shaded polygon, or hardware rendering accelerator. 
The WP will initialize the renderer and feed it new scene descriptions for each 
image to be generated. This instantaneous frame description is a set of data 
structures and function calls, rather than an interpreted language. The rendering 
process must be very fast.

Possible contents of frame description: 
viewport controls (portion of display memory in which to render)
eye controls (position, orientation, field of view, viewing etc)
object list (object geometry, shading, &transforms for world coordinates, 
bounding volume, precomputed normals, prior rendering 
calculations if object/view has not changed, etc.)
lighting controls

8.1.	Rend386

The initial WE/WP system will be built using the REND386 rendering 
software developed by Dave Stampe and Bernie Roehl of the University of  
Waterloo (Canada). This renderer requires an Intel 386 processor and a 
VGA display screen. Initial screen resolution is 320 x 200 256 color. 
Source code for REND386 is available and can be modified to support 
other VGA resolutions. The system also supports time-multiplexed 
stereographics (Sega/Toshiba LCD glasses).

Future WE/WP systems will use other rendering software and hardware 
as it becomes available. The rendering engine is a key component of the 
WE/WP system. When fast engines become available for other platforms 
(or alternate rendering engines for the pc), the system should be 
adaptable to support them.

8.1.1.	Problems with Rend386

Rend386 suffers from a number of severe problems.  Rend386 was not 
designed to be a VR program but rather has grown into that role from a 
simple fast polygon drawing library. This development path is the root of 
many of its problems. Some of the problems with Rend386 can be fixed 
by reworking the source code. Other problems require tossing out large 
parts of the system and starting over.

  * notes on Rend386: v4 exists & is ok, but not great
  * code/documentation cleanup
  * code modifications/enhancements
  * notes on new rendering (486, flat mem, zbuffer, tex map)

8.1.1.1.	Documenation
minimal!
8.1.1.2.	Coding Style
not modular, function naming inconsistent too much global memory use

8.1.1.3.	Error Messages (or lack thereof)
The source code for Rend386 lacks good organization, modulatity and 
other aspects of professional, maintainable code.

8.1.1.4.	WorldDescriptions
WLD, FIG, PLG files - different styles, confusing, poor parsing.

8.1.1.5.	Object Descriptions/creation
Multi-PLG not supported equally (both #multi & multiple/file), PLG 
colors, different point ordering in world and plg files. 

8.1.1.6.	Fixed Resolution

The released code for Rend386 (Devel4.zip) is hard coded for 
320x200x256 resolution. There are hooks for video drivers at different 
resolutions, but the core code still only accesses the image space as 
320x200. If a larger screen is used, Rend will draw only in the upper left 
corner. This error has been worked on by several Group 3 developers for 
personal versions. Their changes could and should be rolled back into 
the G3 baseline version.

8.1.1.7.	Visibility Errors

Rend386 uses a "Painter's Algorithm" to draw the polygons. That is, it 
sorts the polygons by their depth and draw them from most distant to 
nearest. This method is prone to seever visiblity problems. The value 
used as the polygon's depth needs to be a single value, however, a large 
polygon at an angle to the eye will cover a large depth range.  
There are also visiblity problems related to the use of fixed point 
calculations.

8.1.1.8.	Splits & interactive support

Splits are a scheme devised by Dave Stampe to help reduce the visibilty 
errors inherent in a painter's algorithm based renderer. They are 
basically a set of planes that sub-divide the world space. Objects on the 
far side of split planes from the eye are drawn first, then objects on the 
plane, then objects in front of the plane. The split planes form a modified 
Binary Space Division tree. Conventional BSD trees split the world for 
each and every polygon. This makes for a large and very cumbersome 
structure, particularly when objects move within the world. Dave's use of 
seperate, user defined split planes can be a great savings, however, the 
burden now rests on the world designer. The proper placement of splits 
is a trial and error art form. Actually specifing the splits is not simple, 
requiring a fair understanding of plane geometry and derivation of plane 
equations (or locating 3 points on the plane).

8.1.1.9.	Color Scheme
The current color scheme in Rend386 is diffucult to understand and 
manipulate. Colors are specified in a very non-intuitive manner. It isnt 
even RGB.

8.2.	Suggested Renderer Development Path

There are two paths we could take to building a better renderer. We 
could start from scratch and write our own renderer from the ground up. 
This would give us maximum control over the design of the renderer. We 
might use some code and ideas from Rend386 (like the fast  polygon 
drawing functions) and other programs. A complete OO renderer would 
need to be done this way. The drawback to this path is the time and 
effort required to design, implement and debug the program. This is time 
that would not get spent on the higher level functions of the WE/WP.

The alternative is to take Rend386 as the basic system for now. We 
would fix up the most glaring problems with the core and substitute our 
own world description and other high level functions. A new API would be 
defined for accessing the rendering core. There is a fair bit of code 
cleanup needed, but the hardest parts of the renderer are done.

8.3.	Renderer Developement

While presently we are using the Rend386 system as our core rendering 
engine, there are a number of problems with it. Aside from these failings, 
noted elsewhere, it is entirely possible that the code will become a 
shareware program in the future. It is highly desirable that we have our 
own rendering code to avoid any problems with code distribution.  There 
are a number of features we should consider when desiging our own 
image generator. 

One consideration is the level of system supported and type of memory 
access. A 386 with 387FPU is still fairly slow at floating point 
calculations. However, a 486 system is faster at floating point than it is 
at the integer calculations used in Rend386. For such systems, there are 
NO benifits to using integer math. Also, both 386 and 486 systems are 
capable of addressing large amounts of flat memory. This could quite 
easily be used for a z-buffer type renderer, which would eliminate the 
visibility problems of Rend386's painter's algorthm (and most of the need 
for the confusing and difficult 'splits'). The true viability of this 
mechanism remains to be proven. The VGA access is still a very limiting 
constraint on the ability to draw graphics. Perhaps a z-buffer + dirty 
rectangle algorithm could be used.

9.	World Description File

  The World Description File describes the entire virtual environment. 
That is,  the player configuration, user interface (objects and actions), 
scene descriptions, object descriptions, actions and triggers.  I do not 
attempt to  specify any syntax or even semantics at this point. I have 
conceptually divided  the WDF to better determine the various necessary 
part.

9.1.	Player Configuration Section

 Hardware Controls,  User Input Control Mappings (mouse, glove, etc. 2D 
&  3D interaction methods) Effectors 2D, Effectors 3D,  Viewports

9.2.	Scene Description Section

 There would be multiple scene descriptions each giving the names of 
objects in scene, stage description (size, backgrounds, lighting, etc.).

9.3.	Object & Geometry Description Files/Section

 Object description includes hierarchy information (sibling, parent, child),  
geometry file/data, 3D space attributes (position, orientation,, mass, 
velocity,  etc)

9.4.	Object Actions & Triggers

  Object motion scripts and proximity or collision detectors

Scene Control Interface 
    Head (eye) position/orientation controls, 2D & 3D GUI controls 
available

10.	WDF Interpreter

The interpretation of WDF files is a key component of the WE/WP 
system. This process also has a great impact on the design of the WDF 
language. The interpreter needs to be very quick as well as very flexible. 
One suggestion has been to use a threaded interpretive language (TIL). 
However, there are many other alternative methods for implementing the 
WDF interpreter. The engine a TIL can be coded in C, C++, or assmebler 
and made very efficent. TIL's are by their nature highly extendable 
languages. TRIX is a TIL that was developed at Autodesk for use in 
virtual reality application. It combines many of the features of C++, LISP, 
and Forth.
 Other languages that have been suggested for basis of the WDF 
interpreter are BOB and SCHEME.

ÿ