A Primer On Computational Geometry – Part Two

Just because they are acute, that doesn’t mean triangles get asked on many dates.

Previously on Oscar Tortures You All, we talked about how to define a point, a line, and a plane inside a computer.  We also talked about working with a triangle with regard to defining a plane (and all the fun math you can use to do so without ever drawing said triangle).  Today we are going to talk about triangles some more, and how they relate to more complex geometry.

But first, in the last paragraph of the previous post, I kind of sped through the whole process of turning three points into a triangle, so I’m going to briefly work that out.

So, three points: a(0,0,0), b(4,1,2), c(1,4,3)

Three vectors and their magnitudes:

• [ab] (which is b – a, or [4,1,2]), magnitude 4.583
• [ac] (which is c – a, or [1,4,3]), magnitude 5.1
• [bc] (which is c – b, or [-3,3,1), magnitude 4.359

[ab] & [ac] point away from the origin (point a), and [bc] points from b toward c.  Remember that the direction is determined by which point is being subtracted from which.  If I want to flip [ab], I subtract b from a, instead of a from b, and I write the vector as [ba].

Three Dot Products:

• [ab].[ac] = (4*1)+(1*4)+(2*3)  = 14
• [ab].[bc] = (4*-3)+(1*3)+(2*1) = -7
• [ac].[bc] = (1*-3)+(4*3)+(3*1) = 12

Three angles from the dot products (you use the Arc-cosine to get the angle):

• 4.583 * 5.1 * Cos(bac) = 14 -> Cos(bac) = (14/23.3733) -> Cos(bac) = 0.598974 -> Angle(bac) = 53.2 deg
• 5.1 * 4.359 * Cos(acb) = 12 -> Cos(acb) = (12/22.2309) -> Cos(acb) = 0.539789 -> Angle(acb) = 57.33 deg
• 4.583 * 4.359 * Cos(abc) = -7 -> Cos(abc) = (-7/19.9773) -> Cos(abc) = -0.350398 -> Angle(abc) = 69.49 deg

Sanity Check!  The sum of the angles of a planar triangle have to equal 180 degrees, so 53.2+57.33+59.49=180.02 -> close enough! (the 0.02 extra is rounding error).

Now for the normal of the triangle and the plane it rests on.  Take the Cross Product of [ab] X [ac]:

• [ab] X [ac] = [4,1,2] X [1,4,3] = (3-8)x + (2-12)y + (16-1)z = -5x-10y+15z = 0
• Magnitude of the normal is the square root of (5*5 + 10*10 + 15*15) = 18.71, so the area of the triangle is (18.71/2) = 9.35

And that is everything a computer needs to know about that triangle.

It’s hard to stress enough just how important the triangle is.  Triangles are the simplest polygon, 3 points, 3 lines.  Triangles as defined can only exist on a plane. ¹ Triangles have exactly one way to connect all the points to each other. ²  In short if you want to model geometry in a computer, you want to start with triangles.

The best part about triangles is that I can build all the other polygons out of triangles.  What is a polygon, you ask?  A polygon is any 2D shape that has at least 3 straight sides and angles.  The key bits in that definition is that the sides (lines, or edges) are straight, NOT curved, and that each side is at an angle relative to the sides it shares a point with (so two sides with a common point can not be parallel).  Triangles, squares, pentagons, etc are all polygons.  Regular polygons are those that have all the sides of equal length and all the angles of equal measure.  What is a square except two right triangles with a common hypotenuse?  Or four equilateral isosceles triangles with points and edges in common?  I can take any polygon and carve it up into triangles.  Keep this in mind, it’ll come in handy later.

So we have points, line, triangles, and an idea how to make them into something greater (polygons), but how do we get this into a computer?

Point Clouds – not an airy place where everyone has valid observations regarding politics or society.

Back in the bad old days, a common way to get geometry information, especially complex geometry information, into a computer was via a point cloud.  If we are talking REALLY bad old days, geometry would be reduced to an array of 3D points that would then be punched onto computer cards and hand fed, one by one, into a computer ³.  Even today, with CAD and solid modeling everywhere, point clouds are still put together in spreadsheets or other columnar or tabulated data formats and fed into modeling software ⁴ that reads the XYZ data and at the very least it stores the points.  Turning those points into geometry can be very simple, or it can require a great deal of human effort, or metadata.

Let’s take a wing, like the NACA6412 seen below.  This was produced using a simple column of 2D points, and the modeling software was instructed that the points were to be joined by a line going from one to the next, and that the curve should close (connect the last point to the first).

See the XY axes, that’s the origin (0,0)

A point cloud is similar, but in three dimensions, and with more metadata than the above.  What I mean by metadata is information that indicates grouping (which points in a point cloud belong together) and possible connectivity (which points are connected to each other).  The grouping is very important, but the connectivity isn’t always, because triangles.  Take a look at this bit of geometry.

Just a quick spiral shape.

If I was to hide the rendered surfaces and edges (lines), so all I was left with were the points, I could still recreate the edges and surfaces by running an algorithm that would start drawing triangles between all the points, and it would error check itself by not allowing an edges to cross each other and to not permit any point to be contained within a triangle.  Of course, the most obvious problem is that it would start creating triangles between the surfaces you see, so points on the upper side of the spiral would form triangles with points on the blunt edge and the underside of the spiral, which would mess up the surfaces.  Hence, we’d have to group them, so triangles are only formed between points contained within a group, and we error check in a similar fashion as before, making sure no triangle edges cross any other group, etc.  Any points that are common between two groups become edges of the whole model ⁵ .

That’s a lot of information to process, and lots of math to do, but hey, that is what computers are really good at – processing data and performing complex repetitive operations upon it.  And although the rendering engine makes the surfaces of the spiral look smooth, there are no actual curves, just slight changes in the relative angle between adjacent triangles.

Polyhedra – it’s an alternative marriage arrangement, just not with people

Alternatively, instead of making triangles and using them to form surfaces, we could use polyhedra.  Polyhedra are 3D polygons, also called 3D solids.  Polyhedra take many forms, such as prismatic solids, platonic solids, regular (or uniform) polyhedra, and even stellated polyhedra (stars).

Prismatic Solids – a polygon that is simple extended along the perpendicular axis

The basic polyhedra is the tetrahedron, which is, you guessed it, 4 triangles that share common edges.

The tetrahedron – the simplest of polyhedra

And just like simple triangles, tetrahedron can be used to build all higher order polyhedra.  Remember this, it too, will come back later.

Back to the computing side, if we wanted to model this in the computer, we’d do it in a manner very similar to modeling a triangle.  All we need is one more point that is not on the same plane (co-planar) as the other three.  Much like a triangle has at least one point that is not co-linear with the other two.  So once you’ve verified… wait, how do you verify that the polyhedron is convex, instead of collapsed?  Very simple, let’s say you have four points, {a, b, c, d}.  Take three points, {a, b, c} and build a triangle like we did before (build two vectors, take the cross product, find the unit normal), than replace one of the points with point d (any point, it truly does not matter which one), and build a second triangle.  If the unit normals match, your triangle is collapsed.

But what if they don’t match, but the difference is very small (i.e. they almost, but not quite, match)?  Welcome to polyhedra quality, which is something we’ll table for now.

When using tetrahedron to build higher order solids, you need to keep an eye on shared sides, just like you do when using triangles to build surfaces, and as a triangle with two points in common with another triangle shares an edge, a tetrahedron with three points in common with another shares a side.  Obviously, then, you check for shared sides by checking for 3 points in common, right?  Sure, if you want to do a lot of work, but there is a more efficient way – you find the centroid of each side of the tetrahedron.

A centroid is the geometric center of any shape.  And I mean any shape.  If it helps, you can think about the centroid as being the center of gravity of the shape ⁶.  Finding the centroid can be a challenge for irregular shapes, but for triangles, luckily, it’s dead on simple.

Ready?

It’s the average of the three points.  Seriously, it’s that simple.  Same for the tetrahedron (average of the four points).

So now that I have face centroids, I just compare centroids to find shared sides.  If I want a verification that a side is shared, and not just very, very close, I can always compare unit normals and see if they are co-linear (remember the dot product?  If it equals 1, they are co-linear),

So we’ve gone from points to lines to triangles to polygons to complex surfaces to polyhedra and we haven’t drawn a single thing, this is all pure math.  If the spiral up above had tetrahedrons through the body, instead of just triangles on the surface, we’d have a solid body instead of just connected surfaces.  But there is one more way to mathematically represent geometry, which we’ll talk about next time.

Image by fdecomite

1. You can stretch a triangle over a curved surface, such a sphere, but then it no longer fits the definition of a simple triangle, since the lines are now curves
2. If you have four points, you could make a quadrilateral, but you have to make sure your lines don’t cross; triangles don’t have this concern
3. I had a professor who spent an internship at NASA doing just this
4. and modeling software still has to be able to read and process said data, because lots of old geometry is still in that format, and because it’s pretty universal
5. ideally, edges are manifold and only belong to two surfaces; edges that belong to one, or three or more surfaces, are non-manifold and while geometrically valid, can be problematic for engineering simulations, so they are avoided
6. provided the shape is made up of a homogeneous material, squishy things with lots of parts with different densities, like people, have a center of gravity in a location that is very distinct from their centroid