Triangle Mesh Primitive

Triangles are used in real-time computer graphics because they are planar and can be rasterized very quickly in hardware. Several triangles form a mesh. Meshes are used to represent just about anything in a 3D scene. For example, the globe is represented using meshes.


The Globe	Triangle meshes that represent the globe

The triangle mesh primitive is used to render arbitrary triangle meshes. This includes polygons on the globe (e.g. states or countries), terrain and imagery extents, ellipses, and walls. The triangle mesh is a generic rendering object that takes input from other objects that compute triangles. For example, the surface polygon triangulator takes boundary positions on the globe as input and outputs triangles that represent the filled interior region. These triangles are then used as input to the triangle mesh.

STK Engine provides the following triangulators:

Topic	Description
Surface Extent	Computes triangles for a rectangular extent on the surface or at a constant altitude.
Surface Polygon	Computes triangles for a polygon, with an optional holes, on the surface or at a constant altitude.
Extruded Polyline Triangulator	Computes triangles for an extruded polyline.

Extent Triangulator

The extent triangulator, SurfaceExtentTriangulator, computes triangles for a rectangular extent on the surface or at a constant altitude. The example code below uses the extent triangulator and the triangle mesh primitive to render the extent around Louisiana.

[C#] Copy Code

IAgStkGraphicsSceneManager
 manager = ((IAgScenario)root.CurrentScenario).SceneManager;
                Array extent = new object[]
                {
                     -94, // West
                     29, // South
                     -89, // East
                     33 // North
                };

                IAgStkGraphicsSurfaceTriangulatorResult triangles =
 manager.Initializers.SurfaceExtentTriangulator.ComputeSimple(
                "Earth", ref extent);

                IAgStkGraphicsTriangleMeshPrimitive mesh =
 manager.Initializers.TriangleMeshPrimitive.InitializeWithSetHint(
                AgEStkGraphicsSetHint.eStkGraphicsSetHintInfrequent);
                mesh.SetTriangulator((IAgStkGraphicsTriangulatorResult)triangles);
                ((IAgStkGraphicsPrimitive)mesh).Color =
 Color.White;

                manager.Primitives.Add((IAgStkGraphicsPrimitive)mesh);
                manager.Render();

The image on the left shows the output of the extent triangulator, and the image on the right shows the actual results of executing the example.


Triangles from Extent Triangulator	Rendered using Triangle Mesh

To see the triangles that make up a mesh, set the triangle mesh's Wireframe property to true.

To create the extent at altitude, use the extent triangulator's Compute method with altitude parameter:

[C#] Copy Code

IAgStkGraphicsSurfaceTriangulatorResult triangles =
 manager.Initializers.SurfaceExtentTriangulator.Compute(
                "Earth", ref extent, 75000, 1);

This results in the following image:

In addition to an altitude, this method also takes a granularity that defines how many triangles should be used when computing the mesh. A mesh with more triangles will conform to the surface better but consume more memory and render slower. The default granularity is 1 degree. The following images demonstrate the effects of changing the granularity.


Granularity: 0.25 degrees Triangles: 1,334	Granularity: 1 degrees Triangles: 96	Granularity: 2 degrees Triangles: 24

Surface Polygon Triangulator

The polygon triangulator, SurfacePolygonTriangulator, computes triangles for a polygon on the surface or at a constant altitude. This is commonly used for country and state borders, sensor footprints, and ground ellipses. The polygon triangulator works similarly to the extent triangulator except its input is a set of points on the surface that define a boundary to compute a mesh for, as opposed to just a rectangular extent.

The following example passes the boundary positions for Washington D.C. to the polygon triangulator, which is then used as input to the triangle mesh.

[C#] Copy Code

IAgStkGraphicsSceneManager
 manager = ((IAgScenario)root.CurrentScenario).SceneManager;
                Array positions = new object[]
                {
                     38.9665570, -77.008232, 0,
                     38.8899880, -76.911209, 0,
                     38.7881200, -77.045448, 0,
                     38.8139150, -77.035248, 0,
                     38.8293650, -77.045189, 0,
                     38.838413, -77.040405, 0,
                     38.862431, -77.039078, 0,
                     38.886101, -77.067886, 0,
                     38.915600, -77.078949, 0,
                     38.932060, -77.122627, 0,
                     38.993431, -77.042389, 0,
                     38.966557, -77.008232, 0
                };

                IAgStkGraphicsSurfaceTriangulatorResult triangles =
                manager.Initializers.SurfacePolygonTriangulator.ComputeCartographic("Earth",
 ref positions);

                IAgStkGraphicsTriangleMeshPrimitive mesh =
 manager.Initializers.TriangleMeshPrimitive.InitializeWithSetHint(
                AgEStkGraphicsSetHint.eStkGraphicsSetHintInfrequent);
                mesh.SetTriangulator((IAgStkGraphicsTriangulatorResult)triangles);
                ((IAgStkGraphicsPrimitive)mesh).Color =
 Color.Red;
                manager.Primitives.Add((IAgStkGraphicsPrimitive)mesh);

The polygon triangulator is efficient and supports dynamic polygons, which is commonly used for sensor footprints. At each time step, the triangulation can be recomputed with new boundary positions then used as input to the triangle mesh's SetTriangulator method.

Technical Details: The polygon triangulator uses an ear clipping algorithm with optimizations.

Similar to the extent triangulator, the polygon triangulator provides methods to create the mesh at an altitude or with a user-defined granularity.

Triangulating Polygons with a Hole

The polygon triangulator can triangulate polygons with an interior hole, like the one shown below, when a list of points defining the hole is used as input.

The winding order of a hole does not have to be the same as the winding order of the boundary. The following example triangulates a polygon with a hole, and creates a triangle mesh primitive for the interior fill and two polyline primitives that outline the mesh.

[C#] Copy Code

IAgStkGraphicsSceneManager
 manager = ((IAgScenario)root.CurrentScenario).SceneManager;

                IAgStkGraphicsSurfaceTriangulatorResult triangles =
 manager.Initializers.SurfacePolygonTriangulator.ComputeWithHole(
                "Earth", ref positions, ref holePositions);

                IAgStkGraphicsTriangleMeshPrimitive mesh =
 manager.Initializers.TriangleMeshPrimitive.Initialize();
                mesh.SetTriangulator((IAgStkGraphicsTriangulatorResult)triangles);
                ((IAgStkGraphicsPrimitive)mesh).Color =
 Color.Gray;
                ((IAgStkGraphicsPrimitive)mesh).Translucency = 0.5f;
                manager.Primitives.Add((IAgStkGraphicsPrimitive)mesh);

                IAgStkGraphicsPolylinePrimitive boundaryLine =
 manager.Initializers.PolylinePrimitive.Initialize();
                Array boundaryPositionsArray = triangles.BoundaryPositions;
                boundaryLine.Set(ref boundaryPositionsArray);
                ((IAgStkGraphicsPrimitive)boundaryLine).Color =
 Color.Red;
                boundaryLine.Width = 2;
                manager.Primitives.Add((IAgStkGraphicsPrimitive)boundaryLine);

                IAgStkGraphicsPolylinePrimitive holeLine =
 manager.Initializers.PolylinePrimitive.Initialize();
                holeLine.Set(ref holePositions);
                ((IAgStkGraphicsPrimitive)holeLine).Color =
 Color.Red;
                holeLine.Width = 2;
                manager.Primitives.Add((IAgStkGraphicsPrimitive)holeLine);

Extruded Polyline Triangulator

The extruded polyline triangulator computes triangles for extrusions perpendicular to the surface. The extrusion is defined by boundary positions, similar to the input to the surface polygon triangulator. In addition, the altitude for both the bottom and top of the extrusion are specified. The bottom of the extrusion is not required to be on the ground as the following example demonstrates:

[C#] Copy Code

IAgStkGraphicsExtrudedPolylineTriangulatorResult triangles =
                manager.Initializers.ExtrudedPolylineTriangulator.ComputeWithAltitudesAndWindingOrder(
                "Earth", ref positions, 10000, 25000,
 AgEStkGraphicsWindingOrder.eStkGraphicsWindingOrderCounterClockwise);
                IAgStkGraphicsTriangleMeshPrimitive mesh =
 manager.Initializers.TriangleMeshPrimitive.Initialize();
                mesh.SetTriangulator((IAgStkGraphicsTriangulatorResult)triangles);
                ((IAgStkGraphicsPrimitive)mesh).Color =
 Color.Blue;
                ((IAgStkGraphicsPrimitive)mesh).Translucency = 0.4f;

Surface Shapes

The surface and wall triangulators can take their input from boundaries computed from surface shapes. Surface shapes compute boundaries for areas on the surface such as ellipses and rectangles. They enable the triangle mesh to render these areas filled and the polyline to render the area's boundary. The pipeline of surface shapes, triangulators and primitives is shown below.

When fill is not required, positions from surface shape computations can be input to the polyline primitive to render just the boundary. When fill is used, the boundary from the triangulator should be input to the polyline. In many cases, the boundary computed by the triangulator will be different than the boundary input to the triangulator. By allowing the triangulator to add detail to the boundary, the triangulator can guarantee that the boundary it outputs precisely lines up with the triangle mesh it computed. This results in a watertight connection between the boundary and the mesh.

The following code example uses surface shapes to compute the boundary for a circle. The object is then input to the surface triangulator, which outputs triangles for the triangle mesh and a boundary for the polyline.

[C#] Copy Code

IAgStkGraphicsSceneManager
 manager = ((IAgScenario)root.CurrentScenario).SceneManager;
                Array center = new object[] { 39.88, -75.25, 0.0 };

                IAgStkGraphicsSurfaceShapesResult shape =
 manager.Initializers.SurfaceShapes.ComputeCircleCartographic("Earth",
 ref center, 10000);
                Array positions = shape.Positions;
                IAgStkGraphicsSurfaceTriangulatorResult triangles =
 manager.Initializers.SurfacePolygonTriangulator.Compute("Earth", ref
 positions);

                IAgStkGraphicsTriangleMeshPrimitive mesh =
 manager.Initializers.TriangleMeshPrimitive.InitializeWithSetHint(
                AgEStkGraphicsSetHint.eStkGraphicsSetHintInfrequent);
                mesh.SetTriangulator((IAgStkGraphicsTriangulatorResult)triangles);
                ((IAgStkGraphicsPrimitive)mesh).Color =
 Color.White;
                ((IAgStkGraphicsPrimitive)mesh).Translucency = 0.5f;

                IAgStkGraphicsPolylinePrimitive line =
 manager.Initializers.PolylinePrimitive.InitializeWithHint(
                AgEStkGraphicsSetHint.eStkGraphicsSetHintInfrequent);
                Array boundaryPositions = triangles.BoundaryPositions;
                line.Set(ref boundaryPositions);
                line.Width = 2;

                manager.Primitives.Add((IAgStkGraphicsPrimitive)mesh);
                manager.Primitives.Add((IAgStkGraphicsPrimitive)line);

Indexed Triangle Lists (Advanced)

In addition to triangulator objects, the triangle mesh can be initialized using an indexed triangle list representation of a triangle mesh.

A naive way to represent a mesh in memory is a collection of vertices (x, y, z triplets), where every three vertices represents one triangle. This is referred to as triangle soup and is grossly inefficient in terms of memory usages and GPU vertex cache awareness.

Since most triangles in a mesh are connected to other triangles in a mesh, the preferred representation is the indexed triangle list. All of the unique vertices in the mesh are stored in a collection. A second collection contains indices of vertices in the first collection. Every 3 indices represents 1 triangle. Since the size of an index (typically 2 or 4 bytes) is much less than the size of a vertex (typically 12 or 24 bytes), less memory is used compared to triangle soup representations. Furthermore, STK Engine is capable of organizing the indices and vertices to get the best performance out of GPU vertex caches, which improves rendering performance.

Technical Details: STK Engine's vertex cache optimization is based on the 2007 SIGGRAPH paper Fast Triangle Reordering for Vertex Locality and Reduced Overdraw.

An indexed triangle list for a mesh with two triangles is shown below.

Normals (Advanced)

For proper lighting, meshes must have surface normals defined for each vertex. A surface normal is a vector of unit length that is perpendicular to the surface at that point as shown below.

Normals are computed in a variety of ways. A straightforward algorithm to compute a normal for a position is to normalize the average of the cross products of all adjacent incident edges to that position. Once computed, normals should be stored in a separate collection that has a one-to-one mapping with the position collection. The normal at index i in the normal collection is the normal for the position at index i in the position collection as shown below.