Specification

Renderer

Model Parser Proposal

Motivation

1. A parser provides a clean separation of the radiosity solver and the actual data. By starting off with a simple parser we are leading the way for more complex parsing of DXF and 3DS files.
2. Minor changes to hard coded scenes require recompiling of the project and wastes time.
3. Hard coding data structures especially in C++ can be difficult which may give way to an easier data structure for hard coded scene but may not be well suited for parser driven model generation.
4. Major enhancements can be made to the parser to preprocess and augment the input as to make the input file easier to generate and still provide more complex models.
5. Hard coded scenes limit the amount of testing to that one scene. By allowing quick modification to an input file a wide variety of testing can be done.

Description

1. Determining if the given normal for a patch is in the same direction as the normal calculated using the patch vertices.
2. Checking to make sure that all the normals of an object point in the same direction.
3. Determining whether an object is convex, concave or other properties that maybe yield inappropriate results from the radiosity solver.
4. The vertex list given corresponds to valid vertices in the vertex list.

1. subdiv – The amount the patch should be subdivided by when parsing. This allows for very easy subdivision of patches before the radiosity solver begins. This is an integer value
2. reflectivity – The fraction of radiosity that this patch absorbs from other patches. Used in the radiosity calculations. This is a 3-tuple of floats where each value is between 0 and 1.
3. emission – The initial emission values for this patch. These value will be zero except for the light source. This is a 3-tuple of float values.
4. normal – This is the normal vector to the patch. This is an optional value since the normal can be determined from the vertices given. But since the direction of the normal is extremely important explicitly specifying it is sometimes easier. The value does not need to be a unit vector that will be done by the parser.

An implementation of this spec can be done relatively easily using flex and bison. Flex being a lexical analyzer and bison being a parser generator. Unfortunately the interface to these tools is somewhat clumsy and strictly C orientated. Given below is a possible C++ interface that can wrap the C interface.

Parser Improvements

1. Addition of more complex object types. By specifying a center and radius a sphere could be generated use a variety of mesh generation techniques. An example may be:

   object "globe" { sphere { center (1, 1, 1) radius 5 } }

   This could be done for a variety of non-rectangular shapes (i.e. cone, torus, cylinder, etc.)

2. Keeping the same interface we could write parsers for other predetermined format and use the correct parser by looking at file extensions (i.e. DXF files and 3DS files).
3. Large number of improvements could be made to the pre and post processing of input files.

C++ Interface

class parser_t
   {
   public:
      parser_t(void);
      model_t* parse(char* filename);
   };

Grammar

model ->
   MODEL {
      POINTS { <point> {, <point> } }
      { <object> }
      RENDER { <string> {, <string> }
   }

object ->
   OBJECT <string> {
      <patch> { <patch> }
   }

patch ->
   PATCH {
      SUBDIV <integer>
      REFLECTIVITY <point>
      EMISSION  <point>
      VERTICES { <integer>, <integer>, <integer>, <integer> }
      [ NORMAL <point> ]
   }

point ->
      ( <float>, <float>, <float> )

integer ->
   INT

float ->
   INT | FLOAT

string ->
   STRING

Radiosity Solver & Geometry Library

Winged Edge Data Structure

The winged edge data structure allows easy iteration over faces, edges, and vertices. In practice, half-edge is usually used because of its simpler implementation.

Note: Vertex and edge ordering is always counter-clockwise.

Mesh

• iteration over all faces
• Iterator firstFace()
• void nextFace(Iterator& it)
• Face& getFace(Iterator it)

• iteration over all vertices
• Iterator firstVertex()
• void nextVertex(Iterator& it)
• Vertex& getVertex(Iterator it)

Face

• iteration over adjacent faces
• Iterator firstFace()
• void nextFace(Iterator& it)
• Face& getFace(Iterator it)

• iteration over edges
• Iterator firstEdge()
• void nextEdge(Iterator& it)
• Edge& getEdge(Iterator it)

• iteration over vertices
• Iterator firstVertex()
• void nextVertex(Iterator& it)
• Vertex& getVertex(Iterator it)

• TQTree& tqTree()
• return tri-quad tree associated with this face
• (see tqtree.txt)

• Vector3D& normal()
• return the surface normal of this face

Edge

• Face& face()
• returns the face belonging to this edge

• Vertex& vertex()
• returns the vertex this edge points to

• bool siblingEdge(Edge& edge)
• returns this edge's sibling edge (if it exists)

Vertex

• iteration over edges pointing to this vertex
• Iterator firstEdge()
• void nextEdge(Iterator& it)
• Vertex& getVertex()

• Vertex& nextVertex()
• returns the next counter-clockwise vertex

• iteration over adjacent faces
• Iterator firstFace()
• void nextFace(Iterator& it)
• Face& getFace(Iterator it)

• Point3D& point()
• returns the 3-D point of this vertex

Renderer

The renderer can operate in two modes: flat shaded mode or Gouraud shaded mode. Gouraud shading interpolates vertex colours, and thus requires these colours to be pre-calculated.

The scene is manouvered through via a camera object. The camera is manipulated through its own interface.

Renderer

• Camera& getCamera()
• return the camera object

• void render()
• display the scene from the viewpoint of the camera

Geometry Library

3-D

Point3D

• Point3D(double x, double y, double z)
• Point3D()
• constructors

• Point3D& operator +=(const Vector3D& v)
• Point3D& operator -=(const Vector3D& v)

• double operator[](int e)
• p[0] returns x
• p[1] returns y
• p[2] returns z

Vector3D

• Vector3D(double x, double y, double z)
• Vector3D()
• constructors

• Vector3D& operator+=(const Vector3D& v)
• Vector3D& operator-=(const Vector3D& v)
• Vector3D& operator*=(double s)
• math

• double normalize()
• double magnitude()

• double operator[](int e)
• p[0] returns x
• p[1] returns y
• p[2] returns z

Matrix & Vector operations

• Point3D operator+(const Point3D& P, const Vector3D& v)
• Point3D operator+(const Vector3D& v, const Point3D& P)
• Point3D operator-(const Point3D& P, const Vector3D& v)
• Vector3D operator+(const Vector3D& v1, const Vector3D& v2)
• Vector3D operator-(const Vector3D& v1, const Vector3D& v2)
• Vector3D operator-(const Point3D& P1, const Point3D& P2)
• Vector3D operator*(const Vector3D& v, const double s)
• Vector3D operator*(double s, const Vector3D& v)
• double dot(const Vector3D& v1, const Vector3D& v2)
• Vector3D cross(const Vector3D& v1, const Vector3D& v2)
• more math

Ray3D

• Ray3D(const Point3D& P, const Vector3D& v)
• Ray3D()
• constructors

• P()
• returns point
• v()
• returns vector

• Point3D operator()(double t)
• evaluate ray at t

2-D

• same as 3-D Point and Vector

---

Tri-quad tree

Each tri-quad tree is rooted in a face.

Note: Vertex and edge ordering is always counter-clockwise.

Vertex

• Point3D& getPoint()
• return the 3-D point this vertex is located at

• Radiosity& getRadiosity()
• return the radiosity at this vertex
• this value is normally determined from adjacent faces
• this value should be calculated after the radiosity solution for elements has been completed

Element

• iteration over vertices
• Iterator firstVertex()
• void nextVertex(Iterator& it)
• Vertex& getVertex()

• Radiosity& radiosity()
• radiosity of this element

• Vector3D normal()
• return the surface normal of this element

• bool intersect(const Ray3D& ray)
• intersect a ray with this element and return true if it hits, false otherwise

TQTree

• iteration over children
• Iterator firstChild()
• void nextChild(Iterator& it)
• TQTree& getChild(Iterator it)

• Patch& element()
• returns the element at this level of the tri-quad tree

• bool split(int nChildren)
• split the element at this level of the tri-quad tree into nChildren elements
• return true if the operation is successful, false otherwise

---

Radiosity Solver

The input is the scene containing all polygonal surfaces. The output is the same scene, possibly subdivided, with radiosity values calculated for each face.

Radiosity

• void solve(GrScene& scene)
• solve radiosity

Camera

Note that the camera should ALWAYS stay level with respect to the z axis, unless you want your audience nauseous.

Also note that you shouldn't change the field of view to zoom. Dolly in and out instead.

Camera

• Camera(const Point3D& eye, const Vector3D& view, const Vector3D& up, double fov)
• eyepoint, view direction, up direction and field of view settings for camera construction

• void jumpTo(const Point3D& eye, const Vector3D& view, const Vector3D& up)
• move camera immediately to location

• void dolly(double dist)
• move the camera forward or back (negative dist)
• void track(double dist)
• move the camera horizontally, perpendicular to the line of sight
• void crane(double dist)
• raise or lower the camera vertically
• void tilt(double angle)
• rotate about the horizontal axis perpendicular to the line of sight
• void pan(double angle)
• rotate about the vertical axis of the camera (after tilt)

---

Scene

Definitions:

Mesh

a solid object described by a collection of maximally connected faces

Face

a single facet of a polygonal solid (mesh)

faces are restricted to be quadrilaterals

Element

produced by subdivision of faces

each face is an element, but each element is not a face

elements are restricted to be quadrilaterals or triangles

Vertex

a corner of a face

Light

a face that emits radiosity

lights are not subdivided and thus consist of a single face

Receiver element

an element that is not part of a light

Scene

• iteration over all meshes
• Iterator firstMesh()
• void nextMesh(Iterator& it)
• Mesh& getMesh(Iterator it)

• iteration over all faces
• Iterator firstFace()
• void nextFace(Iterator& it)
• Face& getFace(Iterator it)

• iteration over all lights
• Iterator firstLight()
• void nextLight(Iterator& it)
• Face& getLight(Iterator it)

• iteration over all vertices
• Iterator firstVertex()
• void nextVertex(Iterator& it)
• Vertex& getVertex(Iterator it)

• iteration over all receiver elements
• Iterator firstElement()
• void nextElement(Iterator& it)
• Element& getElement(Iterator it)

• void addMesh(Mesh* pMesh)
• bool intersect(const Ray& ray, Face& face)
• intersect a ray with the scene, returning true if the ray
• intersects a face, as well as returning the face itself

• void calculateVertexRadiosity()
• calculate radiosities for each vertex in the scene

---

Iterators

for(int i = 1; i <= N; i++) {
     //
     // do stuff
     //
}

It makes sense to iterate over things other than numbers. It also makes sense to have a standard interface to iteration. The following is commonly used (see GNU C++ library, Microsoft Foundation Classes):

for(Iterator it = object.first(); it != NULL; object.next(it)) {
     doSomethingWith(object.get(it));
}

Iterator functions an object supporting iteration must implement are:

• Iterator first();
• void next(Iterator& it);
• ChildObject& get(Iterator it);

Optional iterator functionality is:

• Iterator last();
• void previous(Iterator& it);

Using iterators neatly encapsulates iteration behaviour and avoids the need to access pointers directly. The Iterator type is usually a void pointer, but the user doesn't need to know that.

[Home]