Part-of relationships, scene graphs, PostScript implementation P.J. Drongowski 28 September 2004 (revised 7 October 2004) Relationships between classes and objects * Need to have a way to document relationships between classes and objects + Help document the system + Need diagrams to understand complex systems (100,000+ lines of code) + A way to guide the implementation to a clean solution * part-of relationship + Examples of part-of relationships - Organizations: corporation-division-department-group-employee - Governmental territories: nation-state-county-municipality - Musical notation: score-system-staff-measures-notes&rests - Chemistry: molecule-atom-electron&nuclei-proton&neutron - Electronic circuits - Geometric modelling * is-a relationship + Models generalization / specialization + Direction of arrow is from specialized class to generalized class e.g., pet -> animal + Specialized classes inherit common properties from the generalized class (attributes and behavior) + Be careful when drawing diagrams - We can talk about part-of and is-a relationships between classes (OOA/OOD) and specific objects - Dilip's rule * Define what the symbols in a diagram mean * Be consistent in their use - We need to be consistent when drawing relationship diagrams - Meaning of boxes (class or object) and arcs must be consistent - Remember, an object is an instance of a class, so the relationship between class and object is an instance-of relationship * Class diagram + Boxes are classes, arcs are relationships (part -> parent) + This kind of diagram is drawn using a notation like UML (Unified Modelling Language) + Any object in the aggregate class is composed of other objects from the subpart classes + Constraints (notated as a number on an arc) specify how many subpart objects may be related to a (parent) object from the aggregate class + Are class diagrams always trees? No, two aggregate classes may use subparts selected from the same child class (i.e., a child class may have two parents) * Draw the part-of hierarchy (class diagram) for a robot -----> Head Scene -----> Robot -----> Body -----> Leg * Scene graph + A common concept in use in OpenGL, VRML, Java 3D API, game engines + This notion of scene graph is taken from the Java 3D API Specification + A scene graph is a "directed acyclic graph" -- no cycles allowed -- in the shape of a tree - What is a directed acyclic graph? (nodes and directed edges) - Examples: tree, hierarchy + There are two types of nodes (boxes) - Group nodes -- the interior nodes of the tree - Leaf nodes -- the leaves of the tree + Notation: - A circle is a "group node" - A box is a "leaf node" - Directed arcs denote parent-child relationships (from parent to child) + Topology - A group node may have only one parent, but may have multiple children - Group nodes organize leaf nodes and other group nodes - A group node specifies spatial transformations to place, orient and scale its children - A leaf node has no children and only one parent + A group node has one of two roles - Group (organize) children together - A group transformation node changes the position, orientation and scale of all objects below it + Leaf nodes - Leaf nodes typically consist of geometric primitives (e.g., shapes) - The state of a leaf node is defined by the nodes in the direct path from the root to the leaf - If the graphics context depends solely on the direct path, then the renderer can traverse the graph in any order [Draw example scene graph here] + Scene graph controls rendering of its constituent objects - An object can be drawn independently of all other objects - Objects on different branches of tree cannot share state information -- this destroys independence - Indepedence let's objects be rendered concurrently through parallel processing + Spatial separation and grouping - Scene graph hierarchy encourages spatial grouping of geomtric elements at the leaves of the graph - Group node defines a spatial boundary that contains geometry of all descendents - Allows efficient implrmentation of proximity detection, collision detection, etc. * Draw the scene graph for a robot scene ... / / \ \ | | | | V V V V translate translate translate translate gsave/grestore | | | | operations are implicit V V V V at each level jimmy dad mom becky Robot Robot Robot Robot | | | | V V | V ... ... | ... | ... / / \ \ translate translate translate translate | | | | head body leftLeg rightLeg Head Body Leg Leg | | | | circle rect line line * Explain the spatial relationships between the parts + Each part has its own origin + Subparts are placed and oriented with respect to that origin + Child is unaware of the context in which is will be created and used + PostScript transformations are used to place and orient subparts * Show how to break down a multi-part picture + Draw each subcomponent on its own grid with own origin + Show how to use PostScript transformations to place/orient subparts PostScript picture (second PostScript assignment) * Use the PostScript file class to draw a multi-part picture * Example: Robot + Robot parts: head, body, legs + Are all scene graphs trees? + Draw hierarchy diagram that shows part-of relationships - What is a hierarchy? - How does it differ from a tree? + Could have other part-of relationships by adding hands and feet * Each part type is defined by a separate class + Robot can have two legs where each leg is an instance of the Leg class + From one class, many objects + A class is an "object factory" * The part-of hierarchy also shows the relative geometric placement of parts with respect to their parent part + Coordinate space transformations (translate, scale, rotate) + Geometric transformations can be concatenated (matrix multiply) * PostScript primitives for part placement + Coordinate space transformation matrix is kept in graphics state + gsave / grestore: Save and restore the current graphics state + translate, scale, rotate: Concatenate transformations + PostScript transformations "stack up" * Consider these questions + Hmmm, can you write a program to walk a part-of hierarchy and display it? + What is the shape of the hierarchy? * Show robot example in detail including final result * Approach + Must start the assignment with a plan! + Draw the part-of hierarchy (also called the "scene graph") + Draw primitive parts (the "leaves" of the part-of hierarchy) on a grid - Define origin as middle of object in order to rotate later - Draw object on a unit square in order to set scale later + Use PostScript transformations to position parts