Quiz 1 Flashcards
What are the three most basic types of objects made from straight lines?
1) Single straight line
2) Polyline
3) Closed Poly Line
What are the three limitations of storing vertices and line connectivity in the same data structure?
1) Higher computer memory usage, floats and duplicates
2) What happens to coordinates with close vertices? e.g. x = 3.0 and x = 3.0001
3) When a vertex has changed all points in the data set have to be changed separately
How do you find an inverse of a vertex index?
Reverse the data storage and convert [x,y,z] to a geometry key. Geometry keys must have consistent decimal points.
What is the geometry index of:
{0: [0,0],
1: [1.5,1],
2: [2.0,0.5]}
{‘0.0,0.0’: 0,
‘1.5,1.0’: 1,
‘2.0,0.5’: 2}
In a connectivity matrix (m x n) what do the rows (m) and columns (n) represent and how does it show connectivity?
m represents the lines
n represents the nodes
Along the row, the start node is -1 and the end node is 1 with the rest of the row being 0s.
What is the coordinate difference (u, v and w) and what are the sizes of the vectors?
How can these be calculated using the connectivity matrix (C)?
Coordinate differences are the distances in the x, y and z directions between the start and end points of each line.
(m x 1)
u = Cx
v = Cy
w = C*z
What does the transpose of the connectivity matrix tell us?
What lines are connected to a given node as well as the direction of that incoming or outgoing edge.
How does an adjacency matrix (A) work?
It is a symmetric matrix of size n x n where n is the node number. Each row I of the matrix has a 1 in column j if the vertex is connected to vertex j. This connection could be a line joining them or an edge.
What is a degree matrix (D) and how does it work?
The degree matrix is a matrix that stores how many connections each vertex has. Each row of the adjacency matrix is summed and placed into a diagonal matrix showing how many connection each vertex has.
How is the Laplacian matrix found?
Taking away the Adjacency matrix from the degree matrix.
L = D - A
What is the difference between a direct, undirected and mixed graph?
A directed graph is when all the information flow is prescribed (has arrows)
An Undirected graph is when there are no restrictions of directions of flow
A mixed graph is a combination of directed and undirected lines.
What is meant by a weighted graph?
It means that there is a weight or cost to pass through a link or line. For example traffic or forces in a truss.
Why is finding the shortest path through a weighted graph important in real life?
What are the two most popular algorithms used?
Can be used to find the fast route on google maps
Discovering the path of least resistance for forces or flows
Determining the fasting communication route
Dijkstra’s and Bellman-Ford algorithm
What are the three types of meshes?
1) Tri-mesh - triangular faces with three vertices
2) Quad-mesh - only faces with 4 vertices
3) NGon-mesh or Poly-mesh - a mixture of faces with three or more vertices per face.
What is the data structure for meshes made up of?
1) Vertices - an index of all the nodes and their coordinates
2) Faces - an index of how the nodes are connected around a face
3) Edges - Can be derived from the face index but are very useful for modelling and analysis so can be stored separately
What is meant by a half-edge data structure?
What is its biggest disadvantage?
Similar to the edge index however edges that overlap between faces are split into two in an equal and opposite direction.
Half edges can only have a maximum of two edges per line which means the mesh cannot have more than two faces per edge.
How do you check what faces are around a vertex?
Set up a face matrix and simply read off what faces are around the vertex in question
What are the two different mesh structures and describe each one?
Structured Mesh - The vertices/faces are laid on a mathematical or parametric grid usually cartesian/spherical coordinate and as quads
Unstructured Mesh - Usually irregular and triangulated and they usually have mesh refinement at areas of curvature or modelling interest.
How does Delaunay triangulation set up a mesh?
How does Ruppert’s algorithm refine this?
It takes starting vertices already set and forms circles around these points ensuring that no vertices are within the circles. This results in a mesh with maximum internal angles within the triangular faces.
Ruppert’s algorithm produces more equilateral/well-proportioned triangles. it only uses the boundary vertices
What does a simple subdivision do and what are the other popular methods?
It creates a finer mesh by adding vertices at the midpoint of edges or centroids of faces.
Loop, Catmull-Clark and Doo-Sabin subdivision.
What are the three boolean operations?
1) Intersection (overlap)
2) Union (adding)
3) Difference (subtracting)
What is an interpolated spline?
They always pass through the defined points and interpolate between these points with varying degrees. (usually 1 (linear) or 3 (cubic)). They can either be open or closed.
What are Bezier curves?
They are curves between defined anchor points. the shape of the curves can be altered by changing the tangents are each control point. This allows kinks and compound smooth-straight curves can be made.
What are Non-Uniform Rational Basis Spline (NURBS) curves?
In grasshopper, these curves go through control points but in some modelling packages it doesn’t. This makes it harder to use for known points.
