Triangle Mesh Primitive

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:

SurfaceTriangulatorResult triangles =
    SurfaceExtentTriangulator.compute(CentralBodiesFacet.getFromContext().getEarth(), 
                                      new CartographicExtent(Trig.degreesToRadians(-94.0), // West 
                                                             Trig.degreesToRadians(29.0), // South
                                                             Trig.degreesToRadians(-89.0), // East
                                                             Trig.degreesToRadians(33.0))); // North

TriangleMeshPrimitive mesh = new TriangleMeshPrimitive(SetHint.INFREQUENT);
mesh.set(triangles);
mesh.setColor(Color.WHITE);

SceneManager.getPrimitives().add(mesh);
SceneManager.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

Tip
To see the triangles that make up a mesh, set the triangle mesh's Wireframe (get / set) property to true.

To create an extent at altitude, use the compute method which takes an altitude parameter:

SurfaceTriangulatorResult triangles = 
    SurfaceExtentTriangulator.compute(CentralBodiesFacet.getFromContext().getEarth(),
                                      new CartographicExtent(Trig.degreesToRadians(-94.0), // West
                                                             Trig.degreesToRadians(29.0), // South
                                                             Trig.degreesToRadians(-89.0), // East 
                                                             Trig.degreesToRadians(33.0)), // North
                                      75000.0, // Altitude in meters 
                                      Trig.degreesToRadians(1.0));

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 degree. Triangles: 96.

Granularity: 2 degrees. Triangles: 24.

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, rather than 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:

ArrayList<Cartographic> positions = new ArrayList<Cartographic>();
positions.add(new Cartographic(Trig.degreesToRadians(-77.008232), Trig.degreesToRadians(38.9665570), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-76.911209), Trig.degreesToRadians(38.8899880), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.045448), Trig.degreesToRadians(38.7881200), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.035248), Trig.degreesToRadians(38.8139150), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.045189), Trig.degreesToRadians(38.8293650), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.040405), Trig.degreesToRadians(38.838413), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.039078), Trig.degreesToRadians(38.862431), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.067886), Trig.degreesToRadians(38.886101), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.078949), Trig.degreesToRadians(38.915600), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.122627), Trig.degreesToRadians(38.932060), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.042389), Trig.degreesToRadians(38.993431), 0.0));
positions.add(new Cartographic(Trig.degreesToRadians(-77.008232), Trig.degreesToRadians(38.966557), 0.0));

EarthCentralBody earth = CentralBodiesFacet.getFromContext().getEarth();
SurfaceTriangulatorResult triangles = SurfacePolygonTriangulator.computeCartographic(earth, positions);

TriangleMeshPrimitive mesh = new TriangleMeshPrimitive(SetHint.INFREQUENT);
mesh.set(triangles);
mesh.setColor(Color.RED);
SceneManager.getPrimitives().add(mesh);

The polygon triangulator is efficient and supports dynamic polygons, which are 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 set method.

Note
Technical Details: The polygon triangulator uses an ear clipping algorithm, with optimizations described in our blog post: Triangulation Rhymes With Strangulation.

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

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.

SurfaceTriangulatorResult triangles = SurfacePolygonTriangulator.compute(earth, positions, holePositions);

TriangleMeshPrimitive mesh = new TriangleMeshPrimitive();
mesh.set(triangles);
mesh.setColor(Color.GRAY);
mesh.setTranslucency(0.5f);
SceneManager.getPrimitives().add(mesh);

PolylinePrimitive boundaryLine = new PolylinePrimitive();
boundaryLine.set(triangles.getBoundaryPositions());
boundaryLine.setColor(Color.RED);
boundaryLine.setWidth(2.0f);
SceneManager.getPrimitives().add(boundaryLine);

PolylinePrimitive holeLine = new PolylinePrimitive();
holeLine.set(holePositions);
holeLine.setColor(Color.RED);
holeLine.setWidth(2.0f);
SceneManager.getPrimitives().add(holeLine);

ExtrudedPolylineTriangulator 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:

ExtrudedPolylineTriangulatorResult triangles = 
    ExtrudedPolylineTriangulator.computeCartographic(earth, positions, 10000.0, 25000.0, WindingOrder.COUNTER_CLOCKWISE);

TriangleMeshPrimitive mesh = new TriangleMeshPrimitive(SetHint.INFREQUENT);
mesh.set(triangles);
mesh.setColor(Color.BLUE);
mesh.setTranslucency(0.4f);

SceneManager.getPrimitives().add(mesh);

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.

Cartographic center = new Cartographic(Trig.degreesToRadians(39.88), Trig.degreesToRadians(-75.25), 0.0);
SurfaceShapesResult shape = SurfaceShapes.computeCircleCartographic(earth, center, 10000.0);

SurfaceTriangulatorResult triangles = SurfacePolygonTriangulator.compute(earth, shape.getPositions());

TriangleMeshPrimitive mesh = new TriangleMeshPrimitive(SetHint.INFREQUENT);
mesh.set(triangles);
mesh.setColor(Color.WHITE);
mesh.setTranslucency(0.5f);

PolylinePrimitive line = new PolylinePrimitive(SetHint.INFREQUENT);
line.set(triangles.getBoundaryPositions());
line.setWidth(2.0f);

SceneManager.getPrimitives().add(mesh);
SceneManager.getPrimitives().add(line);

In addition to triangulator objects, the triangle mesh can be initialized using an indexed triangle list representation of a triangle mesh. First, we describe the motivation and data structures for indexed triangle lists. Then, code examples are provided.

A naive way to represent a mesh in memory is an 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 usage 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 an 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, Insight3D is capable of organizing the indices and vertices to get the best performance out of GPU vertex caches, which improves rendering performance.

Note
Technical Details: Insight3D'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:

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 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.

The following code example creates a triangle mesh with two triangles. The normals are the surface normals of the ellipsoid when the vertex is projected onto the surface.

Cartographic p0 = new Cartographic(Trig.degreesToRadians(-5.0), Trig.degreesToRadians(-5.0), 75000.0);
Cartographic p1 = new Cartographic(Trig.degreesToRadians(5.0), Trig.degreesToRadians(-5.0), 75000.0);
Cartographic p2 = new Cartographic(Trig.degreesToRadians(-5.0), Trig.degreesToRadians(5.0), 75000.0);
Cartographic p3 = new Cartographic(Trig.degreesToRadians(5.0), Trig.degreesToRadians(5.0), 75000.0);

Ellipsoid shape = CentralBodiesFacet.getFromContext().getEarth().getShape();
ArrayList<Cartesian> positions = new ArrayList<Cartesian>();
positions.add(shape.cartographicToCartesian(p0));
positions.add(shape.cartographicToCartesian(p1));
positions.add(shape.cartographicToCartesian(p2));
positions.add(shape.cartographicToCartesian(p3));

ArrayList<Cartesian> normals = new ArrayList<Cartesian>();
normals.add(Cartesian.toCartesian(Ellipsoid.surfaceNormal(p0)));
normals.add(Cartesian.toCartesian(Ellipsoid.surfaceNormal(p1)));
normals.add(Cartesian.toCartesian(Ellipsoid.surfaceNormal(p2)));
normals.add(Cartesian.toCartesian(Ellipsoid.surfaceNormal(p3)));

ArrayList<Integer> indices = new ArrayList<Integer>();
indices.add(0);
indices.add(1);
indices.add(2);
indices.add(1);
indices.add(3);
indices.add(2);

TriangleMeshPrimitive mesh = new TriangleMeshPrimitive(SetHint.INFREQUENT);
mesh.set(positions, normals, indices);
mesh.setWireframe(true);

SceneManager.getPrimitives().add(mesh);