I spent most of last week continuing my reading about
the technical aspects of meshes, then spent the latter
part of the week delving into the OpenJUMP/JTS code
base to figure out how to best integrate TIN
functionality.
I have things pretty much squared away in my mind
about where I'm going with the TIN module and how I'm
going to get there, but now that I'm beginning to
start the coding, I have begun to bang my head against
the eclipse IDE. I've never used eclipse before, and
I'm finding it impossible to do things that should be
simple like unite the jts cvs tree and the jump-pilot
svn tree into a project that I can build, run, and
modify without breaking dependencies left and right. I
have everything checked out and in the workspace, but
can't put it all into one project. And the eclipse
tutorials aren't helping one bit. I'm close to just
using a text editor, but in the long run, it would
make things much easier to use a good IDE and if I can
get the dependency hell figured out, eclipse would
make a good IDE. I have a message into
SunburnedSurveyer to see if we can meet this week and
do a quick in person eclipse orientation.
So, instead of java interfaces and class stubs, I'll
lay out in longhand the specifics I have planned.
tin Package:
TriangulatedIrregularNetwork extends MultiPolygon (I'm
debating whether or not to directly inherit from
MultiPolygon or to add more interfaces to create a
MultiPolygon->Surface->PolygonalSurface->TIN hierarchy
that is closer to the Simple Features spec)
In order for the TIN code to integrate seamlessly with
OpenJUMP, the interface to the in-memory
representation of the TIN should be as compatible as
possible with the JTS. By making the TIN a
MultiPolygon with the added restrictions that all
Polygons are non-overlapping, connected triangles, all
the code that works with GeometryCollections can be
made to easily work with TINs. Internally, the TIN
surface will be represented by a triangle-table which
is a simplified version of a quad-edge data structure.
Each record in the table represents a triangle and
contains the three vertex points and three table keys
that point to the bordering triangles within the
triangle table. The vertexes will be stored as raw
doubles and the lines inferred. When the class is
queried for a triangle or point, the returned geometry
object will be created on the fly from the internal
data structure. If this proves too slow, then it might
be worth the space tradeoff to store the vertexes as
Point Objects. This data structure is compact, fast
and can accomplish anything we would want to do with a
TIN.
In addition to the inherited GeometryCollection
methods and the methods specified in the Simple
Features spec for Surfaces and PolyhedralSurfaces, the
TIN class should also have TIN specific methods like:
* extractContourBands: given a height increment and
baseline (default = 0), return a MultiLineString
containing the contour bands separated by the given
height increment.
* subset: given an envelope or even a linear ring,
return a TIN that contains all the triangles of the
current TIN that lie within the given boundary.
I'm still not 100% clear on OpenJUMP's rendering
pipeline, but it looks like I will implement a new
instance of
com.vividsolutions.jump.workbench.ui.renderer.Renderer
that will work with TINs such that elevation color
bands and hillshades can be implemented by
coloring/shading each triangle on the fly. If this
winds up being too slow, I might have to add
pre-computed normals to the TIN's triangle-table.
TinFactory
For efficiency sake, the TIN should be immutable, thus
a Factory will be needed to create a TIN fully formed.
This Factory would be analogous to the GeometryFactory
class. Various methods would take input lines and
points and output a fully constructed instance of a
TriangulatedIrregularNetwork. The first factory I'll
work on will take a MultiPoint set and use Chew's
algorithm found in
org.openjump.core.graph.delauneySimplexInsert. This
algorithm isn't the fastest, and doesn't deal with
breaklines, but it is already in the OpenJUMP code
base and will help to get the TIN pipeline working
faster. The next factory to be coded will take a
MultiPoint collection and a MultiLineString collection
and will use a constrained delaunay triangulation to
create the TIN. We may want to do a conforming
delaunay triangulation instead and add steiner points
on the breaklines in order to not have huge triangles
next to the breaklines. Steiner points are also the
reason why the TIN class should contain the copy of
it's breaklines, because the breaklines in the TIN
might be different than the breaklines that were
initially given to the factory (the TIN's breaklines
would have more points). Later on down the road, I
would also like to make a TinFactory that takes in a
MultiLineString of breaklines and a stream of Points,
then builds up the TIN until the stream closes. This
will be useful when we move beyond OpenJUMP's in
memory representation and embrace larger TINs.
tin.io Package
This package will contain classes that can turn
various types of input files into MultiPoint / point
streams and MultiLineString geometry to be input into
a TinFactory. There will also be classes that can
export a TIN to a file and then be read it back into a
TIN class. At first only Well Known Text input and
output will be implemented. Eventually various DEM
files will be supported for input and various 3D
formats supported for input and output (i.e. W3's
X3D).
tin.viewshed Package
All the papers I've read about viewsheds use a
separate data structure for the viewshed that is built
from the TIN. This data structure is then queried. The
query could be a point or line with the return value
being a MultiPolygon containing regions that can be
seen from the input feature. The query could also be
two features with the return value being a boolean
indicating whether or not the features are visible
from each other. The downside to viewsheds is that
they have a big memory footprint: the most versatile
data structure has a table for each point that
contains a boolean value for every other point in the
TIN indicating if it is visible or not. Because of
this, viewsheds shouldn't be integrated into the TIN
class and should only be used when requested.
tin.watershed Package
Much like the viewshed package, separate data
structures that are built using the TIN will be
needed.
tin.multitriangulation Package
The classes in this package will implement a
multi-resolution triangulation model. The MT data
structure can return a TIN class with a specified
level of detail. The LOD can be constant over the
whole surface, or can be higher at specified locations
and coarser at others. This won't be of much use if
the TIN can fit in memory, but once the TIN gets
bigger, a multi-resolution data structure can use a
file or database backing and return a TIN in a
resolution that will fit in memory and cover the
points of interest at the required detail. This might
wind up being implemented solely within PostGIS/WMS,
so that OpenJUMP can simply issue a WMS query and
receive a TIN object as a reply.
Again, sorry for not coming bearing code today. I
haven't been slacking though; in addition to reading
more about about meshes and TINs than I ever imagined
existed and trying to wrap my head around the entire
OpenJUMP/JTS code base, the code structure laid out
above is the third or fourth revision I've come up
with. I think this layout will be the best balance
between OpenJUMP integration and ability to be used by
third parties. Previous designs had put more emphasis
on the TIN library being independent from OpenJUMP,
but those eventually broke down into a collection of
bad hacks when I tried to figure out how to integrate
it into OpenJUMP. I have since decided that OpenJUMP
will the the primary target and third party use will
be kept in the back of my mind. I'll try not to make
life harder than it needs to be for third party
developers, but when needs conflict, I'm siding with
the OpenJUMP way.
Comments and suggestions appreciated,
--Christopher
PS I'm posting the meat of this message on the wiki.
____________________________________________________________________________________
Be a better friend, newshound, and
know-it-all with Yahoo! Mobile. Try it now.
http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
Jump-pilot-devel mailing list
Jump-pilot-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jump-pilot-devel
