Nick's Design Study

From CSSEMediaWiki
(Difference between revisions)
Jump to: navigation, search
(Conclusion)
 
(62 intermediate revisions by one user not shown)
Line 1: Line 1:
 
== What is A Ray Tracer ==
 
== What is A Ray Tracer ==
A ray tracer is a program the produces pre-rendered CGI. This type of program is used by movie studios to create the effects in a large number of movies. Some examples are Autodesk's [http://usa.autodesk.com/adsk/servlet/pc/index?siteID=123112&id=13577897 Maya] and [http://usa.autodesk.com/adsk/servlet/pc/index?siteID=123112&id=13567410 3ds Max]. These suits are available for free; [http://www.blender.org/ Blender] and [http://www.caligari.com/ TrueSpace].  
+
A ray tracer is a program that produces CGI(computer generated imagery). This type of program is used by movie studios to create effects seen in a large number of movies.  
In a rendering system the virtual representation of objects in a scene are stored in memory. A ray tracer can generate an image creating a 'ray' for each pixel (for anti-aliasing more than one ray is sent per pixel). The ray is tested to see if it intersects with any scene object, if it does then the color of the pixel becomes the color of the objects surface. The color is modified by lighting and other scene effects.  
+
 
 +
Some examples of ray tracing programs are Autodesk's [http://usa.autodesk.com/adsk/servlet/pc/index?siteID=123112&id=13577897 Maya] and [http://usa.autodesk.com/adsk/servlet/pc/index?siteID=123112&id=13567410 3D Studio Max]. These ray tracing suites are freely available, [http://www.blender.org/ Blender] and [http://www.caligari.com/ TrueSpace].  
 +
 
 +
In a rendering system the virtual representations of objects in a scene are stored in memory. A ray tracer can generate an image by creating a 'ray' for each pixel (for anti-aliasing more than one ray is sent per pixel). The ray is tested to see if it intersects with any scene object, if it does then the color of the pixel becomes the color of the objects surface. The color is modified by lighting and other scene effects. If the ray doesn't collide with any object, it is set as the background colour.
  
 
== Ray Tracer Project ==
 
== Ray Tracer Project ==
Last year in Cosc 363 the first assignment was a ray tracer. I fairly enjoyed this project, despite some of the hair-ripping hurdles involved. It was also a very good introduction into the use of vector maths for me. Although I had some problems that I couldn't fix, I did get some very neat features to work. Such as reflection and refraction. It was a good feeling to build something, basically from the ground, that had been a marvel and a mystery to me for so long. I got it to work but it wasn't pretty. The OO's structures are not very nice, and there is a high chance that I committed a litany of bad design offences. Also Python is not the most efficient of platforms for something this computationally dependent.
+
Last year in Cosc 363 (computer graphics) the first assignment was to program a ray tracer in python. I fairly enjoyed this project, despite some of the hair-ripping hurdles involved. It was also a very good introduction into the use of vector maths for me. Although I had some problems that I couldn't fix, I did get some very neat features to work. Such as reflection and refraction. It was a good feeling to build something, basically from the ground, that had been a marvel and a mystery to me for so long.  
 +
Allthough I got it to work, it wasn't pretty. The OO's structures were not very nice and I committed a litany of bad design offences. Also Python is not the most efficient of platforms for something this computationally dependent.
  
 
== Original Python Design ==
 
== Original Python Design ==
Comming soon.
+
In this diagram the links between the low-level classes (Vector, Point, Ray and Color) and the higher level ones have been omitted in the interest of highlighting the key relationships..
 +
 
 +
[[Image:Original Python Design.jpg]]
 +
 
 +
There are a number of aspects of this that seems to just plain smell bad. Also the use of Interfaces is not coherent. Here Material class is not an Interface, but a concrete class that is extended. RayCaster doesn't use the Light interface, instead linking to the concrete classes that implement light.
 +
 
 +
Here are some specific maxims that are violated:
 +
 
 +
=== Maxims ===
 +
==== Behavioral completeness ====
 +
The primary violation that jumps at me is that a large portion of behavior that should be done by the Material interface (as it is directly related to the properties of the specific material).
 +
This is a violation of the maxium [http://wiki3.cosc.canterbury.ac.nz/index.php/Behavioral_completeness Behavioral completeness] since the classes do not contain their complete behaviour.
 +
An example in the code can be seen in the "RayCaster" class in the method "getColourForRay()":
 +
 
 +
'surface' is an instance of Material
 +
 
 +
:surface = getSurface(obj.material,hitPoint)
 +
:if surface.transperency < 1:
 +
::pointLights = lightsAt(ray,hitPoint)
 +
::if surface.reflection > 0 and surface.reflection is not None:
 +
:::reflexPix = getReflectionColour(obj, ray, hitPoint,depth)
 +
::else: reflexPix = Colour(0,0,0)
 +
::if surface.refraction > 0 and surface.refraction is not None:
 +
:::refractPix = getRefractionColour(obj, ray, hitPoint,depth)
 +
::else: refractPix = Colour(0,0,0)
 +
:...
 +
:res = surface.litColour(obj.normal(hitPoint), AMBIENT, ray.dir,
 +
::pointLights, reflectionPixel =reflexPix,refractionPixel = refractPix)
 +
 
 +
(the different RGB values are finally combined in the materials litColour method)
 +
 
 +
This is essentially a switch statement that largely varies the behavior based on the materials properties (such as transparency reflection and refraction), this behavior belongs in different concrete implementations of material. The methods called are all part of the same class, RayCaster. They should be part of the material class.
 +
There is an issue that arises from putting this functionality in the material class, for recursive ray events such as reflection the material must be combined with that of new rays cast back into the scene. In this way if the majoryity of operations ascosated with material was within the class it would still have to know about the scene, and be able to cast new rays into it. Since lighting is also used in material colouring materials in this model must also know about lights. This would probably be incorpirated into the interface of the scene class, since lights are part of the scene.
 +
 
 +
I feel this is somehow malodorous, but it dose seem that to some degree in the real world surfaces can 'see' the scene and the lights around them. So there is a trade-off here, between not having cyclic dependency and supporting operations involved in ray casting events like reflection and refraction. Since these two are available in even the most basic ray tracer, and produce some of the ray tracers best effects , they can't be left out.
 +
 
 +
==== Keep related data and behavior in one place ====
 +
This design doesnt subscribe to Riel's Heuristic
 +
[http://wiki3.cosc.canterbury.ac.nz/index.php/Keep_related_data_and_behavior_in_one_place Keep related data and behavior in one place], since behaviour that should be in the meterial class is in the rayCaster class.
 +
 
 +
==== Feature Envy smell ====
 +
The rayCaster is doing work that should be in other classes. For example the method getReflectionColour(object, ray, point, depth), should be in material since the Reflection is a property of the meterial. This is an example of [http://wiki3.cosc.canterbury.ac.nz/index.php/Feature_envy_smell feature envy].
 +
 
 +
==== Tell Don't Ask ====
 +
A related issue the RayCaster is asking details of the meterial and then preforming work and passing using the result in another call to material ( res = surface.litColour(..., reflexPix, refractPix ) ). RayCaster should  tell the material to render a surface point, then retreive the result. Operations like reflection and refraction should be done inside the material classes methods. this is an example of violating the maxum [http://wiki3.cosc.canterbury.ac.nz/index.php/Tell_dont_ask tell, don't ask].
 +
 
 +
==== Open closed principle ====
 +
This design is very difficult to extend, since the structure of the ray casting method is intrinsically linked to the behavior of each supported material. Surfaces in this design suffer from this less, but since all surfaces have materials, in fact need them to become visible, thus these two structures are both equally required. RayCaster (and also scene) should not need to be modified to add new types of material, lights and surfaces. This conflicts with the [http://wiki3.cosc.canterbury.ac.nz/index.php/Open_closed_principle open/closed principle].
 +
 
 +
This is also a violation of [http://wiki3.cosc.canterbury.ac.nz/index.php/Open_closed_principle 'Program to the interface not the implementation'] principle since RayCaster is not aptly set up to deal only with the material and surface interfaces.
 +
 
 +
==== Switch Statement Smell ====
 +
Because the most of the functionality of materials lights and ray functions were all dealt with inside the class RayCaster, the code inside contained several switches biased on type alone. I.e if a materiel was a reflective one, a different part of the code is executed in RayCaster.
 +
This is knowen as [http://wiki3.cosc.canterbury.ac.nz/index.php/Switch_statement_smell switch statement smell].
 +
 
 +
==== Law of Demeter ====
 +
The law of demeter says that you shouldn't be getting objects from other objects and calling their methods. From within method M object O you should only be calling the methods of O, methods of objects created within M, and all the objects that are components of O directly.
 +
In the getColourFor Ray() method for example the RayCaster object is getting the surface (surface = getSurface(obj.material,hitPoint)) and then calling methods on this. This is an example of a violation of the [http://wiki3.cosc.canterbury.ac.nz/index.php/Law_of_Demeter law of demeter] in the code.
 +
 
 +
==== God Object ====
 +
There is a [[God_object|God class ]](RayCaster). This class organizes all the scene elements, and controls the ray casting and writing to screen/ files.  The class has far to much functionality for a single class, some of this should be delegated to other classes.
 +
 
 +
==== Program to the interface not the implementation ====
 +
Perhaps the bigest problem this design has is that it breaks the [http://wiki3.cosc.canterbury.ac.nz/index.php/Program_to_the_interface_not_the_implementation program to the interface not the implementation] prinicple. The RayCaster has be dasigned to cope with specific concrete class implementations and not stable abstractions.
 +
 
 +
=== Issue summary ===
 +
It suffices to say that this design has a certain inelegance that is reflected by the above problems. There is a wide area for improvement. I'm going to attempt to design a system that is easy to use and extend by programmers. To do this I need to make a system that is programmed to a set of Stable Abstractions, ones that represent the various different components of the ray casting model. I'm going to keep this ideal at the forefront as I develop my system.
 +
 
 +
== System Proposal 1 ==
 +
=== Overall System outline ===
 +
In this diagram the links between the low-level classes (Vector, Point, Ray, ... ect) and the higher level ones have been omitted in the interest of clarity.
 +
 
 +
[[Image:System Overview.jpeg]]
 +
 
 +
 
 +
This shows the relationship between the scene object and the various different interfaces, implementations, and primitive types.
 +
For each of the abstractions intended for extension there is also a factory interface. This is to  unify the way in which the scene class creates and maintains collections of scene objects. The scene object will have collections both of each type of object and of each factory type. In this way the library can be extended to include new objects. Also developers can write their own implementation of the factory and their own custom objects, and pass an instance of the factory to the scene. Then objects of any type can be created using a control string such as:
 +
 
 +
"Material Phong phongmat1 (255,0,0) (25,0,0) (255,255,255)"
 +
 
 +
or:
 +
 
 +
"Surface Plane plane1 (0,0,0) (0,1,0)"
 +
 
 +
This can also be used to deliver instuctions to the scene such as;
 +
 
 +
"Transform Rotate plane1 (35, 1,0,0)"
 +
 
 +
or:
 +
 
 +
"Disable light1"
 +
 
 +
 
 +
 
 +
=== Information Flow of System ===
 +
[[Image:enity data flow.jpeg]]
 +
 
 +
This describes the information exchange required for a single ray tracing event within the system. The thing that jumps out is the fact that material is telling scene to provide information. This illistrates that for this to work there must be some fairly strong coupling between Scene and Material.
 +
 
 +
=== Issues ===
 +
 
 +
In this design several of the interfaces are redundant, namely Surface and Light. There is no need for both the Light and the Illuinator classes only one high level abstraction should be provided. Similarly there is no need for both the Surface and the Rendering classes.
 +
This is a violation of riel's huristic [http://wiki3.cosc.canterbury.ac.nz/index.php/Minimal_public_interface Minimal Public Interface].
 +
In the system there is no specific depiction of the ray tracing program, I.e Raycaster disappeared. There should be some example of the central application, even if it is intended to be overwritten.
 +
 
 +
== System Proposal 2 ==
 +
In this digram the links to simple classes(Point, Vector, Ray, RGB and HTransformationMatrix) have been omitted in the interest of clarity.
 +
 
 +
[[Image:System UML.jpeg]]
 +
 
 +
 
 +
Some of the issues have been addressed are:
 +
 
 +
* The unessicary interfaces (Light and Surface) were removed.
 +
* A class was added that actually created a scene and rendered it.
 +
* The interface for transformations was beter defined.
 +
* The interactions and relationships of the low-level classes (Point, Vector and, Ray) are more well defined.
 +
* Scene is still abstraced from any concrete implementations.
 +
 
 +
Once a scene has been created new objects can be added in two ways:
 +
:a) The objects can be directly added to a Scene instance
 +
:b) A constructor string for the object can be used by calling the processCommandString() method of Scene
 +
 
 +
:For example a pointer to a material object can be added directly to scene using the addMaterial() method
 +
 
 +
::or
 +
 
 +
:a command string like :"Material Phong phongmat1 (255,0,0) (25,0,0) (255,255,255)" can be passed to a scenes processCommandString() method.
 +
 
 +
In this string "Material" represents the type of object, "Phong" represents the specific implementation of the type and "phongmat1" in the unique identifier for the new material.
 +
The other 3 items are color values of the type (red,green,blue). In this case they represent the various properties of the material, such as its lit color, ambient color and the color of its highlight.
 +
If a scene is given a faulty command string it quietly ignores it and continues (that is no error is displayed and nothing is added to the collections of scene).
 +
 
 +
==== Have I fixed all of the problems that I identified in the orginal design? ====
 +
 
 +
It could be argued that the scene object has replaced rayCaster as the new God object, But I do not agree. Although scene has more methods than most of the other classes, most of these are getters and setters, a large part of the workload has been delegated to other classes. There are now a set of [http://wiki3.cosc.canterbury.ac.nz/index.php/Stable_abstractions_principle stable abstractions] that makes the system [http://wiki3.cosc.canterbury.ac.nz/index.php/Open_closed_principle open for extension but closed for modification].
 +
This adresses the majority of issues described above.
 +
 
 +
==== Have other issues been introduced? ====
 +
 
 +
There is some concern over the [http://wiki3.cosc.canterbury.ac.nz/index.php/Coupling coupling] between Material and Scene, but this is a nessicary trade-off to achive refective and other effects.
 +
 
 +
== Conclusion ==
 +
Using principles and examples from the Cosc427 I refined my ray tracer design through several iterations. I started by identifying some of the major problems with the initial design, the python source from my computer graphics assignment. I then created new designs basied on the issues identified.
 +
Although many of the initial problems were dealt with by this new design, coupling between the material and scene classes remains an unresolved issue. I think that overall the final result is close to as elegant a solution as possible, in the problem domain.
 +
Although I was not able to implement the code for the updated system I am confidant it will work.
 +
 
  
 
-[[User:Nick Molhoek|Nick Molhoek]]
 
-[[User:Nick Molhoek|Nick Molhoek]]

Latest revision as of 03:29, 1 October 2010

Contents

What is A Ray Tracer

A ray tracer is a program that produces CGI(computer generated imagery). This type of program is used by movie studios to create effects seen in a large number of movies.

Some examples of ray tracing programs are Autodesk's Maya and 3D Studio Max. These ray tracing suites are freely available, Blender and TrueSpace.

In a rendering system the virtual representations of objects in a scene are stored in memory. A ray tracer can generate an image by creating a 'ray' for each pixel (for anti-aliasing more than one ray is sent per pixel). The ray is tested to see if it intersects with any scene object, if it does then the color of the pixel becomes the color of the objects surface. The color is modified by lighting and other scene effects. If the ray doesn't collide with any object, it is set as the background colour.

Ray Tracer Project

Last year in Cosc 363 (computer graphics) the first assignment was to program a ray tracer in python. I fairly enjoyed this project, despite some of the hair-ripping hurdles involved. It was also a very good introduction into the use of vector maths for me. Although I had some problems that I couldn't fix, I did get some very neat features to work. Such as reflection and refraction. It was a good feeling to build something, basically from the ground, that had been a marvel and a mystery to me for so long. Allthough I got it to work, it wasn't pretty. The OO's structures were not very nice and I committed a litany of bad design offences. Also Python is not the most efficient of platforms for something this computationally dependent.

Original Python Design

In this diagram the links between the low-level classes (Vector, Point, Ray and Color) and the higher level ones have been omitted in the interest of highlighting the key relationships..

Original Python Design.jpg

There are a number of aspects of this that seems to just plain smell bad. Also the use of Interfaces is not coherent. Here Material class is not an Interface, but a concrete class that is extended. RayCaster doesn't use the Light interface, instead linking to the concrete classes that implement light.

Here are some specific maxims that are violated:

Maxims

Behavioral completeness

The primary violation that jumps at me is that a large portion of behavior that should be done by the Material interface (as it is directly related to the properties of the specific material). This is a violation of the maxium Behavioral completeness since the classes do not contain their complete behaviour. An example in the code can be seen in the "RayCaster" class in the method "getColourForRay()":

'surface' is an instance of Material

surface = getSurface(obj.material,hitPoint)
if surface.transperency < 1:
pointLights = lightsAt(ray,hitPoint)
if surface.reflection > 0 and surface.reflection is not None:
reflexPix = getReflectionColour(obj, ray, hitPoint,depth)
else: reflexPix = Colour(0,0,0)
if surface.refraction > 0 and surface.refraction is not None:
refractPix = getRefractionColour(obj, ray, hitPoint,depth)
else: refractPix = Colour(0,0,0)
...
res = surface.litColour(obj.normal(hitPoint), AMBIENT, ray.dir,
pointLights, reflectionPixel =reflexPix,refractionPixel = refractPix)

(the different RGB values are finally combined in the materials litColour method)

This is essentially a switch statement that largely varies the behavior based on the materials properties (such as transparency reflection and refraction), this behavior belongs in different concrete implementations of material. The methods called are all part of the same class, RayCaster. They should be part of the material class. There is an issue that arises from putting this functionality in the material class, for recursive ray events such as reflection the material must be combined with that of new rays cast back into the scene. In this way if the majoryity of operations ascosated with material was within the class it would still have to know about the scene, and be able to cast new rays into it. Since lighting is also used in material colouring materials in this model must also know about lights. This would probably be incorpirated into the interface of the scene class, since lights are part of the scene.

I feel this is somehow malodorous, but it dose seem that to some degree in the real world surfaces can 'see' the scene and the lights around them. So there is a trade-off here, between not having cyclic dependency and supporting operations involved in ray casting events like reflection and refraction. Since these two are available in even the most basic ray tracer, and produce some of the ray tracers best effects , they can't be left out.

Keep related data and behavior in one place

This design doesnt subscribe to Riel's Heuristic Keep related data and behavior in one place, since behaviour that should be in the meterial class is in the rayCaster class.

Feature Envy smell

The rayCaster is doing work that should be in other classes. For example the method getReflectionColour(object, ray, point, depth), should be in material since the Reflection is a property of the meterial. This is an example of feature envy.

Tell Don't Ask

A related issue the RayCaster is asking details of the meterial and then preforming work and passing using the result in another call to material ( res = surface.litColour(..., reflexPix, refractPix ) ). RayCaster should tell the material to render a surface point, then retreive the result. Operations like reflection and refraction should be done inside the material classes methods. this is an example of violating the maxum tell, don't ask.

Open closed principle

This design is very difficult to extend, since the structure of the ray casting method is intrinsically linked to the behavior of each supported material. Surfaces in this design suffer from this less, but since all surfaces have materials, in fact need them to become visible, thus these two structures are both equally required. RayCaster (and also scene) should not need to be modified to add new types of material, lights and surfaces. This conflicts with the open/closed principle.

This is also a violation of 'Program to the interface not the implementation' principle since RayCaster is not aptly set up to deal only with the material and surface interfaces.

Switch Statement Smell

Because the most of the functionality of materials lights and ray functions were all dealt with inside the class RayCaster, the code inside contained several switches biased on type alone. I.e if a materiel was a reflective one, a different part of the code is executed in RayCaster. This is knowen as switch statement smell.

Law of Demeter

The law of demeter says that you shouldn't be getting objects from other objects and calling their methods. From within method M object O you should only be calling the methods of O, methods of objects created within M, and all the objects that are components of O directly. In the getColourFor Ray() method for example the RayCaster object is getting the surface (surface = getSurface(obj.material,hitPoint)) and then calling methods on this. This is an example of a violation of the law of demeter in the code.

God Object

There is a God class (RayCaster). This class organizes all the scene elements, and controls the ray casting and writing to screen/ files. The class has far to much functionality for a single class, some of this should be delegated to other classes.

Program to the interface not the implementation

Perhaps the bigest problem this design has is that it breaks the program to the interface not the implementation prinicple. The RayCaster has be dasigned to cope with specific concrete class implementations and not stable abstractions.

Issue summary

It suffices to say that this design has a certain inelegance that is reflected by the above problems. There is a wide area for improvement. I'm going to attempt to design a system that is easy to use and extend by programmers. To do this I need to make a system that is programmed to a set of Stable Abstractions, ones that represent the various different components of the ray casting model. I'm going to keep this ideal at the forefront as I develop my system.

System Proposal 1

Overall System outline

In this diagram the links between the low-level classes (Vector, Point, Ray, ... ect) and the higher level ones have been omitted in the interest of clarity.

System Overview.jpeg


This shows the relationship between the scene object and the various different interfaces, implementations, and primitive types. For each of the abstractions intended for extension there is also a factory interface. This is to unify the way in which the scene class creates and maintains collections of scene objects. The scene object will have collections both of each type of object and of each factory type. In this way the library can be extended to include new objects. Also developers can write their own implementation of the factory and their own custom objects, and pass an instance of the factory to the scene. Then objects of any type can be created using a control string such as:

"Material Phong phongmat1 (255,0,0) (25,0,0) (255,255,255)"

or:

"Surface Plane plane1 (0,0,0) (0,1,0)"

This can also be used to deliver instuctions to the scene such as;

"Transform Rotate plane1 (35, 1,0,0)"

or:

"Disable light1"


Information Flow of System

Enity data flow.jpeg

This describes the information exchange required for a single ray tracing event within the system. The thing that jumps out is the fact that material is telling scene to provide information. This illistrates that for this to work there must be some fairly strong coupling between Scene and Material.

Issues

In this design several of the interfaces are redundant, namely Surface and Light. There is no need for both the Light and the Illuinator classes only one high level abstraction should be provided. Similarly there is no need for both the Surface and the Rendering classes. This is a violation of riel's huristic Minimal Public Interface. In the system there is no specific depiction of the ray tracing program, I.e Raycaster disappeared. There should be some example of the central application, even if it is intended to be overwritten.

System Proposal 2

In this digram the links to simple classes(Point, Vector, Ray, RGB and HTransformationMatrix) have been omitted in the interest of clarity.

System UML.jpeg


Some of the issues have been addressed are:

* The unessicary interfaces (Light and Surface) were removed.
* A class was added that actually created a scene and rendered it.
* The interface for transformations was beter defined.
* The interactions and relationships of the low-level classes (Point, Vector and, Ray) are more well defined.
* Scene is still abstraced from any concrete implementations.

Once a scene has been created new objects can be added in two ways:

a) The objects can be directly added to a Scene instance
b) A constructor string for the object can be used by calling the processCommandString() method of Scene
For example a pointer to a material object can be added directly to scene using the addMaterial() method
or
a command string like :"Material Phong phongmat1 (255,0,0) (25,0,0) (255,255,255)" can be passed to a scenes processCommandString() method.

In this string "Material" represents the type of object, "Phong" represents the specific implementation of the type and "phongmat1" in the unique identifier for the new material. The other 3 items are color values of the type (red,green,blue). In this case they represent the various properties of the material, such as its lit color, ambient color and the color of its highlight. If a scene is given a faulty command string it quietly ignores it and continues (that is no error is displayed and nothing is added to the collections of scene).

Have I fixed all of the problems that I identified in the orginal design?

It could be argued that the scene object has replaced rayCaster as the new God object, But I do not agree. Although scene has more methods than most of the other classes, most of these are getters and setters, a large part of the workload has been delegated to other classes. There are now a set of stable abstractions that makes the system open for extension but closed for modification. This adresses the majority of issues described above.

Have other issues been introduced?

There is some concern over the coupling between Material and Scene, but this is a nessicary trade-off to achive refective and other effects.

Conclusion

Using principles and examples from the Cosc427 I refined my ray tracer design through several iterations. I started by identifying some of the major problems with the initial design, the python source from my computer graphics assignment. I then created new designs basied on the issues identified. Although many of the initial problems were dealt with by this new design, coupling between the material and scene classes remains an unresolved issue. I think that overall the final result is close to as elegant a solution as possible, in the problem domain. Although I was not able to implement the code for the updated system I am confidant it will work.


-Nick Molhoek

Personal tools