CSCE 441 Lecture 27

« previous | Wednesday, March 26, 2014 | next »

Constructive Solid Geometry

Usually represented as binary tree

• interior nodes are operations: unions, intersections, subtraction, translations, etc.
• leaves are solids (sphere, cylinder, plane)

Rendering CSG tree

Assume we have a ray $R$ and a CSG tree $T$

1. If $T$ is a solid,
   • compute all intersections of $R$ with $T$
   • return parameter values and normals
2. If $T$ is a transformation
   • apply inverse transformation to $R$ and recur
   • apply inverse transpose of transformation to normals
   • return parameter values
3. Otherwise $T$ is a boolean operation
   • recur on two children to obtain two sets of intervals
   • apply operation $T$ to intervals
   • return parameter values
4. display closest intersection point.

Returned parameter values are grouped in pairs: enter solid, exit solid, enter solid, exit solid

Inside/Outside Test

Given a point $p$ and a tree $T$, determine if $p$ is inside or outside the solid defined by $T$.

Easy to tell inside/outside given implicit shape equations

1. If $T$ is a solid
   • determine if $p$ is inside $T$ and return (trivial)
2. If $T$ is a transformation
   • apply inverse transformation to $p$ and recur
3. Otherwise $T$ is a boolean operation
   • Recur to determine inside/outside of left and right children
   • If $T$ is a union, inside of either left or right is inside the union
   • If $T$ is an intersection, inside of both is inside the intersection
   • If $T$ is a subtraction, $p$ is inside iff $p$ is inside the left child and outside the right child.

Computing Volume: Monte Carlo method

1. Put bounding box around object
2. Pick $n$ random points inside the box
   • Determine if each point is inside or outside
3. $V\approx V_{\mbox{box}}\cdot {\frac {\mbox{num. inside}}{n}}$

Octrees

Models space as a tree with 8 children

Take cube and slice halfway down each axis

Nodes can be interior, solid, or empty.

Building

1. If cube is completely inside, return solid node
2. If cube is completely outside, return emtpy node
3. Otherwise recur until maximum depth is reached

Advantages:

• Storage space is proportional to surface area
• Inside/outside is trivial
• Computing volume: only count volumes of solid nodes (trivial)
• Relatively simple structure
• can approximate any shape.

Disadvantages:

• Blocky appearance

Boundary Representations

Stores boundary of solid

• Geometry: vertex locations
• Topology: connectivity information (vertices, edges, faces)

Constant time adjacency information:

• For each vertex
  • find edges and faces touching the vertex
• for each edge
  • find vertices and faces touching edge
• for each face
  • find vertices and edges touching face

Half Edge Data Structure

Edges are very important: they are like roads over the surface.

Half-edges are oriented edges, and each edge has two half-edges, one facing in each direction.

class HalfEdge
{
    HalfEdge *next, *prev, *flip;
    Face *face;
    Vertex *origin;
    Edge *edge;
};

class Face
{
    HalfEdge *edge; // can be any half-edge that is part of this face
};

class Vertex
{
    HalfEdge *edge; // can be any half-edge that points away
};

class Edge
{
    HalfEdge *he; // can be any
};

Given a face, find all vertices touching that face:

HalfEdge *he = face.edge;
HalfEdge *current = he;

vector<Vertex*> vertices;

while (current != he) {
    vertices.push_back(current.origin;
    current = current.next;
}

Given a vertex, find all edge-adjacent vertices

HalfEdge *he = vertex->edge;
HalfEdge *current = he;

vector<Vertex*> adjacent;

while (current != he) {
    adjacent.push_back(current->flip->origin);
    current = current->flip->next;
}

Given a face, find all adjacent faces

HalfEdge *he = face.edge;
HalfEdge *current = he;

vector<Face*> faces;

while (current != he) {
    faces.push_back(current.face)
    current = he.next;
}

Could also use a hash table indexed by two vertices

Boundary Representations Summary

Advantages:

• Explicitly stores neighbor information
• Easy to render
• Easy to calculate volume
• Nice-looking surface

Disadvantages:

• CSG is very difficult
• Inside/Outside test is hard

Implicit Representations

Shaped described by solutions to function $f(x)=c$

$f(x,y)=x^{2}+y^{2}-9$

• points evaluated inside are negative
• points evaluated outside are positive
• points evaluated on boundary are 0

Advantages:

• No topology to maintain
• Always defines a closed surface
• Inside/outside test is trivial (as described above)
• CSG operations (next time)