JTin Google Summer of Code 2008

I created this page on the wiki for discussion of the JTin library. This will be a low-level library that allows for the creation and manipulation of TINs. This may be something that we can work on with GeoTools/UDig. In this scenario OpenJUMP and UDig would create their own plug-ins to access the low-level JTin library.

Before serious work begins on the library I think we should make some decisions on the following items:

1. How is TIN defined, and how will we represent it in memory? (Note: We aren't talking about the display of a TIN, but rather the model from which a display or view of the TIN might be created.)
2. What data input formats will we support? Will we wrap access to these formats in a common interface?
3. What data output formats will we support?
4. How will we integrate TIN support into OpenJUMP?
5. How will we display TINs? Do we want this display to be in the normal Layer View of OpenJUMP? Will this be a 2D display? Will it be a 3D display? Can we support 3D display of a TIN in a separate component to avoid tweaking the existing 2D rendering code?

I will add my comments below. Other interested programmers can add their content also. Then we can make a decision on the best way to proceed.

• TIN Definition*

%{color:blue}The Sunburned Surveyor:% From a land surveying perspective a TIN is defined by three (3) components.

The first component is a collection of points representing the samples of the surface being modeled by the TIN. Each sample site has a horizontal position and a measure of the value being modeled with the surface. (This could be the ground elevation surface or the surface of something completely different, like population)

The second component is a line, either 2D or 3D, that represents the boundaries of the surface being modeled. There must be at least one exterior boundary and there may be one or more interior boundaries. (An interior boundary might be used to exclude a building envelope from an elevation TIN.)

The third component is a set of 3D lines that represent the breaklines of the TIN. TIN lines, or the edges of the triangular faces in the TIN, are not allowed to cross breaklines. Breaklines are a critical component of accurate TIN definition and creation.

I believe that our library should incorporate creation of TINs using all three (3) components, not just the first component, as is typically done in GIS.

%{color:green}Christopher DeMars:% Do we need to include support for both hard and soft breaklines (hard breaklines indicating a change in height along the line like in a road grade)?

%{color:blue}The Sunburned Surveyor:% I'm not really sure what a "soft" breakline would be. What I am talking about would be a hard breakline. It is basically a set of connected TIN lines that can't be crossed by other TIN lines. You would typically create these breaklines along topographic features like ridge tops or valleys.

• TIN Representation*

%{color:blue}The Sunburned Surveyor:% I believe that our TIN representation should be made as simple as possible. In my perspective this simplest representation is a set of TIN faces. Each TIN face is defined by three (3) three-dimensional points. I believe we can represent each TIN face by using a JTS Polygon whose nodes have a valid elevation value. Other alternatives are representing each face by a set of raw coordinate values, perhaps as JTS Coordinate objects, or by a set of three (3) LineStrings, with one LineString used to represent each edge of the face. Paul Austin mentioned that representing a face with raw coordinates might be the most efficient method. Whatever method is finally selected, it I think it would be practical to provide methods that allow access to either a JTS Polygon, JTS Point, or JTS LineString representation of the face.

Perhaps the best way to approach this is by encapsulating the common behavior of a TIN face in an interface, and then allowing multiple implementations of this interface using one of the JTS Geometries.

%{color:blue}Paul Austin:% Each face is a Triangle which could be modelled as a Triangle object with 3 coordinates. This would be a very efficient data structure and the Triangle object can have methods to return properties of the Triangle such as the circumcentre. There can be methods on the Tin to wrap this Triangle as a Polygon for use in renderring. See CoordinateSequence as the interface that would allow this wrapping.

%{color:green}Christopher DeMars:% Most of the following commentary was inspired by this paper: http://www.cs.unc.edu/%7Eisenburg/papers/ilss-scdt-06.pdf

The paper mentions that another fundamental value to be stored in a TIN for each triangle facet is three links to adjacent facets.

Other aspects that could/should be associated with each TIN face might be precomputed normals and water flow data (like WaterBug, determine where water flowing in the uphill edges exits).

Another big question that needs to be answered is shall we stick with JTS and use a 2.5D model or go full 3D (2.5D surfaces can be projected onto the xy plane without having overlap)? The advantages of 2.5D is that the algorithms are out there and it would mesh well with OpenJUMP. The disadvantage is that we couldn’t model such things as cave structures or mines and the TIN library couldn’t be used for non-GIS 3D applications like medical imaging. The biggest downside to going full 3D is that Delaunay triangulation of 3D surfaces is an open research topic with regards to creating a decently fast implementation. As of this moment, my thoughts are that we should stick with 2.5D, but try to craft the interface such that full 3D code could be plugged in at some future time.

%{color:blue}The Sunburned Surveyor:% I agree with Paul. Each TIN face could be stored as three Coordinates. We could then provide methods that return things like a 2D Polygon representation of the triangle, the slope, the aspect, or the normal as suggested by Chris.

However, I don't think we should store topology data in the object representing the actual TIN face. I think this should be stored in a separate data structure or data structures.

Chris wrote: "The disadvantage is that we couldn’t model such things as cave structures or mines and the TIN library couldn’t be used for non-GIS 3D applications like medical imaging."

I didn't even think about that Chris. Those are interesting applications of a TIN library.

Chris wrote: "The biggest downside to going full 3D is that Delaunay triangulation of 3D surfaces is an open research topic with regards to creating a decently fast implementation. As of this moment, my thoughts are that we should stick with 2.5D, but try to craft the interface such that full 3D code could be plugged in at some future time."

Excellent points. I agree with your suggestion. Let's go with 2.5D know, but design the library so that we can plug-in true 3D functionality in the future.

• TIN Input Formats*

%{color:green}Christopher DeMars:% At the very least, we should import DEMs and CSV points are converted into a TIN.

%{color:blue}The Sunburned Surveyor:% O.K. - Let's support DEM and CSV in our "alpha" release of the library. Still, we should design an interface that allows access to the three (3) main elements above. That would be (1) 3D points defining the surface, (2) 3D points defining breaklines, and (3) 3d points that define interior and exterior boundaries. We would only require access to a set of 3D points defining the surface. The breaklines and boundaries would be supplemental information that could be using to construct the TIN if available, but which would not be required.

If we take this route I can work on a format for define TINs based on a simple text format. I'd prefer something in YAML, but woudln't be against using XML if there was a lot of support for that.

• TIN Output Formats*

%{color:green}Christopher DeMars:% I see two possibilities. The preferred option IMHO would be to have a streaming architecture where the last stage in the pipeline wrote out the data (triangles, breaklines, borders, waterflow etc) to a PostGIS database. Then the TIN class (or TINDB class) could have a method that returns a subset of the TIN as a new TIN. The new TIN could either be DB backed, or reside only in memory. This would allow us to process, store, and use TINs that are larger than main memory.

Another possible output format would be a raw list of points segregated into a breakline section, border section, and triangle section. This could be either in WKT, WKB, or our own format. In order to save space, markup languages should be avoided. The downside to this is it would be much harder to deal with data sets that dwarf main memory.

%{color:blue}The Sunburned Surveyor:% I agree with Chris on some of the main "outputs" our TIN library should support. I think that these should be a representation of the constructed TIN, including TIN faces, breaklines and boundaries. At some point in the future I would hope to see support for contours (as JTS LineStrings so they could be displayed in OpenJUMP) hillshades, and water flow analysis.

Chris mentioned a "streaming" API that allows access to a TIN in a manner that is independent of memory. I believe this is very important. However, I do not believe we should tie the API to any relational database, at least not directly. We should present a streaming API and then allow individual programmers the liberty to choose their implementation. For example, I would personally avoid a relational database and would focus on streaming access to a TIN based on a binary file or series of text files.

• GeoTools/OpenJUMP Collaboration*

• TIN Display Options*

I don't think, at least initially, that we should be concerned with making major modifications to OpenJUMP so that TIN's can be displayed. I think the more simple, and easily obtained solution, would be to focus on exporting data products from a TIN that could be displayed in OpenJUMP. This could be TIN faces represented as JTS Polygons, countour lines represented as JTS LineStrings, and Hillshades represented as JTS Polygons or raster images.

I believe 3D display of TIN files should take place in either [1] a stand alone tool, or [2] in a plug-in specifically designed for display of 3D data. The second option would allow us to write 3D display code that could be used for future extensions in OpenJUMP's functionality. However, I do not think it would be wise to attempt a mash-up of OpenJUMP's current 2D dispaly and a new 3D display. OpenJUMP's current 2D rendering system is quick and capable of producing high-quality map images. Let's not mess with that. Separating display of 3D data into another component will allow us to experiment with and use tools specifically build for 3D data, liek Java OpenGL bindings, without polluting the current (and effective) 2D rendering system.

• Integration of TIN Support In OpenJUMP*

I don't think, at least initially, that we should worry about integrating TINs into OpenJUMP as a special type of feature. Let's concentrate on building TINs and on creating simple output from TINs in the formats OpenJUMP already permits. When we are successful with this goal we can consider adding more built in support for TIN manipulation directly into OpenJUMP via plug-ins.

• Integration of TIN Support In UDig*

h2. Reference

• 2008 Google Summerof Code http://code.google.com/soc/2008/

• TIN (Triangulated irregular network) http://en.wikipedia.org/wiki/Triangulated_irregular_network

• Delaunay triangulation http://en.wikipedia.org/wiki/Delaunay_triangulation

• more