CSCE 441 Lecture 27

From Notes
Jump to navigation Jump to search

« 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} and a CSG tree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T}

  1. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a solid,
    • compute all intersections of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T}
    • return parameter values and normals
  2. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a transformation
    • apply inverse transformation to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} and recur
    • apply inverse transpose of transformation to normals
    • return parameter values
  3. Otherwise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a boolean operation
    • recur on two children to obtain two sets of intervals
    • apply operation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and a tree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} , determine if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is inside or outside the solid defined by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} .

Easy to tell inside/outside given implicit shape equations

  1. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a solid
    • determine if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is inside Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} and return (trivial)
  2. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a transformation
    • apply inverse transformation to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and recur
  3. Otherwise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a boolean operation
    • Recur to determine inside/outside of left and right children
    • If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a union, inside of either left or right is inside the union
    • If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is an intersection, inside of both is inside the intersection
    • If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} is a subtraction, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is inside iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is inside the left child and outside the right child.

Computing Volume: Monte Carlo method

  1. Put bounding box around object
  2. Pick Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} random points inside the box
    • Determine if each point is inside or outside
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = c}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)
Retrieved from "https://notes.komputerwiz.net/w/index.php?title=CSCE_441_Lecture_27&oldid=7520"