Transcript Implementing Scene Graphs, CSG Trees

Implementing Scene Graphs,
CSG Trees
Glenn G. Chappell
[email protected]
U. of Alaska Fairbanks
CS 481/681 Lecture Notes
Monday, January 26, 2004
Review:
Data Structures for Scenes

We will discuss four types of trees for holding scenes:

Scene Graphs
• Organized by how the scene is constructed.
• Nodes hold objects.

CSG Trees
• Organized by how the scene is constructed.
• Leaves hold 3-D primitives. Internal nodes hold set operations.

BSP Trees
• Organized by spatial relationships in the scene.
• Nodes hold facets (in 3-D, polygons).

Quadtrees & Octrees
• Organized spatially.
• Nodes represent regions in space. Leaves hold objects.
26 Jan 2004
CS 481/681
2
Review:
The Basics of Scene Graphs [1/2]

Structure of a (simple) scene graph:



Each node corresponds to a drawable object.
The children of a given node correspond to “parts” of
the object; these may be movable.
Thus, each node has a transformation. It, and all of its
descendants, are drawn with this transformation.
• The descendants have, in addition, their own
transformations.

Data needed in each node:
• Drawable object (pointer to this?).
• Transformation (a matrix? a pointer to a matrix? a pointer
to a function that returns a matrix?).
• Pointers to child nodes.
26 Jan 2004
CS 481/681
3
Review:
The Basics of Scene Graphs [2/2]

In face.cpp, if we stored the face in a scene graph, it
might look like this:
Head
Hair

Eye
Eye
Iris
Iris
Pupil
Pupil
Ear
Ear
Nose
L.
Mouth
R.
We can add functionality to scene graphs by putting other
things in them. In particular:


Light sources.
Other things like light sources (e.g., environment maps).
26 Jan 2004
CS 481/681
4
Implementing Scene Graphs:
Overview

Now we look at how to implement a
scene graph.





What type of tree to use.
The node data structure.
Drawing via a simple recursive traversal.
Deallocation issues.
Lastly, we look briefly at a “DAG” variation, in
which we do not use a tree.
26 Jan 2004
CS 481/681
5
Implementing Scene Graphs:
Using B-Trees

We often implement an arbitrary tree as a binary tree.


We distinguish between the logical tree and the physical tree. The
latter is the internal representation, which may be entirely hidden.
Each node has a “down” pointer to its first (logical) child and a
“right” pointer to the next (logical) child of its (logical) parent.
• Either or both of these may be null.

A pre-order traversal of the physical tree gives a reasonable (preorder, roughly speaking) traversal of the logical tree.
Logical Tree
26 Jan 2004
Physical Tree
CS 481/681
6
Implementing Scene Graphs:
Node Implementation

Say a node is an object of class SGNode. Each node needs:


An object:(Drawable *).
A transformation.
• I will use an array of 16 GLdouble’s. You may want to do this differently.

Down pointer & right pointer: (SGNode *).
class SGNode {
public:
// Lots of stuff here: constructor(s), etc.
void drawtree() const; // Draw objects in my subtree.
private:
Drawable * object;
// Must be valid.
GLdouble transform[16]; // Handle differently??
SGNode * downp;
// Each of downp, rightp is
SGNode * rightp;
// either valid or null.
};
26 Jan 2004
CS 481/681
7
Implementing Scene Graphs:
Drawing Via Tree Traversal

Now writing drawtree is easy: recursively traverse the tree.

Stuff hanging off of downp uses this node’s transformation, but stuff
hanging off of rightp does not.
void SGNode::drawtree() const
{
glPushMatrix();
glMultMatrixd(transform); // Handle differently??
object->draw();
// virtual function call
if (downp) downp->drawtree();
glPopMatrix();
if (rightp) rightp->drawtree();
}

Draw the scene by calling drawtree for the root node.
26 Jan 2004
CS 481/681
8
Implementing Scene Graphs:
The Node Destructor

Everything needs to be deallocated. Generally, in a tree, each
node is responsible for freeing its children.
SGNode::~SGNode()
{
// Is the node responsible for delete'ing its object?
// If not, then you don't want the line below.
delete object;
// transform is just an array member; we can ignore
// it here. But if your transformation uses dynamic
// allocation, you should probably deallocate it now.
if (downp) delete downp;
if (rightp) delete rightp;
}
26 Jan 2004
CS 481/681
9
Implementing Scene Graphs:
DAG Variation

A Directed Acyclic Graph (DAG) is a generalization of a tree.





Different nodes can share children.
Thus, a node may not have a unique parent.
We do not allow “cycles”: a node cannot be its own descendant.
The 2-child-pointer idea does not work for a DAG. (Why not?)
DAG’s are particularly appropriate for scene graphs, since
identical objects can appear more than once in a scene.


This means that an object cannot store its own transformation.
Instead, it stores the transformations of its children.
Deallocation gets interesting; a parent no longer “owns” its children.
• Solution 1: Each node keeps a reference count. When it hits 0, deallocate.
• Solution 2: Nodes do not manage each other at all. Keep all nodes in a list.
26 Jan 2004
CS 481/681
10
CSG Trees:
Introduction to CSG


We have constructed scenes with polygons (and points & lines).
Another method is Constructive Solid Geometry (CSG).

In CSG, primitives are solid 3-D objects. For example,
•
•
•
•
•

Sphere
Cube
Cylinder
Cone
Etc. …
We create new objects from existing ones using three set operations:
• Union
• Intersection
• Set difference

CSG does not work well with pipeline-based rendering, so we will
say little about it right now.



CSG scenes are typically rendered using some type of ray tracing.
The movie Tron (Disney, 1982) used CSG-style techniques.
CSG is less mainstream than it used to be.

I am told it is still used in CAD.
26 Jan 2004
CS 481/681
11
CSG Trees:
Scene Representation

In CSG, we represent a scene as a binary tree.



Leaves hold primitives.
Internal nodes, which always have two children, hold set operations.
The order in which children are given matters (for the set-difference
operation).
U
U
U
–
∩
cube

sphere
sphere
cube
CSG trees are useful for things other than rendering.


cone
sphere
Intersection tests (collision detection, etc.) are not too hard. (Thus:
ray tracing.)
A DAG may be appropriate here as well.
26 Jan 2004
CS 481/681
12
A Brief Introduction to BSP Trees

A very different way of storing a scene is
a Binary Space Partition tree (BSP tree).


BSP trees are useful for visibility-related
issues, HSR, etc.
Nodes hold polygons.
• In 3-D nodes hold polygons. In 2-D they would hold
line segments.
• Thus, a BSP tree provides a relatively low-level
description of a scene.


Data about the arrangement of the scene is
encoded in the structure of the tree.
Details on the board …
26 Jan 2004
CS 481/681
13