Quiz 1

Question 1

What are the three most basic types of objects made from straight lines?

Answer 1

1) Single straight line
2) Polyline
3) Closed Poly Line

Question 2

What are the three limitations of storing vertices and line connectivity in the same data structure?

Answer 2

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

Question 3

How do you find an inverse of a vertex index?

Answer 3

Reverse the data storage and convert [x,y,z] to a geometry key. Geometry keys must have consistent decimal points.

Question 4

What is the geometry index of:
{0: [0,0],
1: [1.5,1],
2: [2.0,0.5]}

Answer 4

{‘0.0,0.0’: 0,
‘1.5,1.0’: 1,
‘2.0,0.5’: 2}

Question 5

In a connectivity matrix (m x n) what do the rows (m) and columns (n) represent and how does it show connectivity?

Answer 5

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.

Question 6

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)?

Answer 6

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

Question 7

What does the transpose of the connectivity matrix tell us?

Answer 7

What lines are connected to a given node as well as the direction of that incoming or outgoing edge.

Question 8

How does an adjacency matrix (A) work?

Answer 8

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.

Question 9

What is a degree matrix (D) and how does it work?

Answer 9

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.

Question 10

How is the Laplacian matrix found?

Answer 10

Taking away the Adjacency matrix from the degree matrix.

L = D - A

Question 11

What is the difference between a direct, undirected and mixed graph?

Answer 11

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.

Question 12

What is meant by a weighted graph?

Answer 12

It means that there is a weight or cost to pass through a link or line. For example traffic or forces in a truss.

Question 13

Why is finding the shortest path through a weighted graph important in real life?

What are the two most popular algorithms used?

Answer 13

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

Question 14

What are the three types of meshes?

Answer 14

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.

Question 15

What is the data structure for meshes made up of?

Answer 15

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

Question 16

What is meant by a half-edge data structure?

What is its biggest disadvantage?

Answer 16

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.

Question 17

How do you check what faces are around a vertex?

Answer 17

Set up a face matrix and simply read off what faces are around the vertex in question

Question 18

What are the two different mesh structures and describe each one?

Answer 18

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.

Question 19

How does Delaunay triangulation set up a mesh?

How does Ruppert’s algorithm refine this?

Answer 19

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

Question 20

What does a simple subdivision do and what are the other popular methods?

Answer 20

It creates a finer mesh by adding vertices at the midpoint of edges or centroids of faces.

Loop, Catmull-Clark and Doo-Sabin subdivision.

Question 21

What are the three boolean operations?

Answer 21

1) Intersection (overlap)
2) Union (adding)
3) Difference (subtracting)

Question 22

What is an interpolated spline?

Answer 22

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.

Question 23

What are Bezier curves?

Answer 23

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.

Question 24

What are Non-Uniform Rational Basis Spline (NURBS) curves?

Answer 24

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.

Question 25

What is the 1D u parameter domain on a spline curve and how is it normalised?

Answer 25

Define the start of a curve as u = 0 and the end as u = L. To normalise this you divide the endpoint by itself. This makes the start u = 0 and the end u = 1. Therefore we can evaluate curves by fishing relative points along the curve. e.g halfway is u = 0.5

Question 26

How does the u parameter differ in surfaces?

Answer 26

in 2D surfaces, the u parameter becomes the u-v parameter. u,v = 0,0 at the bottom left, u,v = 1,0 bottom right, u,v = 0,1 top left and u,v = 1,1 at the top right. At any point on the surface, you can find in terms of u and v.

Question 27

What is the difference between dividing and shattering a curve?

Answer 27

When you divide a curve it divides it with points either by length or count. this then populates the curve with points which can be used to shatter the curve which means split up.

Question 28

What is a fillet curve?

Answer 28

Fillet curves round off sharp corners made by two curves coming to a point.

Question 29

Explain what tween and blend operations do.

Answer 29

A tween is when you set two curves as the limits for a new curve in between them.

A blend creates a new curve that transitions to the end points of two curves

Question 30

Explain what sweep, extrude and loft operations do.

Answer 30

Curve sections are swepped along another curve acting as a guide rail.

Extrude: set a base curve and define a straight or curved path for it to follow.

Loft: set 2 + cross-section curves and the loft surface will join the curves together.

Question 31

Using a half-edge data structure, How could we start to identify the edges along the inner hole and outer boundary of the mesh

Answer 31

Edges where there are only one half edge indicates that there is no adjacent face to that edge. This process of finding single half edges will thus pick up the edges of the hole and perimeter.

Question 32

How do you create rectangular array/matrix sized in computer memory that could store the face index to vertex index connectivity when the mesh faces have different number of edges?

Answer 32

Create a face mesh using node connectivity as usual but the add -1 after the face is complete for as many times as there are extra edges in the largest face.

Question 33

How could we find the vertices that are connected to a particular vertex using a half-edge data structure?

Answer 33

1. Pick a vertex i
2. Find the faces next to vertex i
3. Find all half-edges within these faces that have vertex i as either the start or end point
4. For all those half edges with I as its end, trace the half edge back to find the connected vertex.
5. For all those half edges with I as its start, trace the half edge forward to find the connected vertex.

Question 34

Why do we subdivide meshes in practice?

Answer 34

• might need finer discretisation for accurate models
• More detail for Fabrication
• Smoothen a sharp coarse mesh into something smooth.