The triangle module is part of a suite of modules for advanced Triangle generation and manipulation. This includes various methods of triangulation such as Vornoi, Delaunay, Area, Convex Hull, Concave region and triangulation of a regular grid with an arbitrary fault line. Methods for testing whether a point is inside a triangle and computing the area of a triangle are also provided.
module triangle <src_file="tri.cxx",
c_src_files="triangle.c barycent.c">
{
string+IPort2 params;
struct_triangulateio+IPort2 in;
cxxmethod+req update (
params+read+req+notify,
in+read+req+notify,
out+write,
vorout+write
);
struct_triangulateio+OPort2 out;
struct_triangulateio vorout;
};
The modules in the Triangle IAC project expose methods from a triangle manipulation
library so that they can be used within AVS/Express to perform a variety of tasks.
The underlying algorithms come from the "Triangle" library written by Jonathan Richard
Shewchuk. This library is intended to be a two-dimensional quality mesh generator and
delaunay triangulator. More information about this library, its purpose and how it can
be used can be found at http://www.cs.cmu.edu/~quake/triangle.html.
Details of the license that this library is distributed under can be found in the
LICENSE file. This suite of modules has been used
in a large AVS/Express project for geologic modeling.
The triangle library was originally intended to be used as a command line program.
It was only later that it was adapted to be used as an internal library. Due to this
control over the triangle library is achieved by passing a string containing a list
of parameters to the triangle library. The triangle module presented here exposes this
functionality in its most basic form. Any parameters specified in the params
string are passed directly to the triangle library. Details of the parameters can be
found on the triangle library home page
or in the triangle.c source code file. This method provides for the maximum
possible control over the library. However it does also allow the user to specify incorrect
parameters. Specifying incorrect parameters may cause the triangle library, and hence
AVS/Express, to crash.
A number of higher-level macros are provided that perform specific tasks. These have the necessary parameters already specified and hence should be more reliable. Where possible these macros should be used instead of accessing the triangle library directly.
in
The input triangle data for the triangle module. This data should be contained a
struct_triangulateio group and contain all the data necessary to perform the task
specified in the params string. The data structure is essentially passed
to the triangle library without modification. If the input triangle data is not
specified correctly the results are not defined.
params
The input parameter string for the triangle module. This string is passed directly
to the triangle library and indicates which functions should be performed on the input
data. Details of the parameters can be found on the triangle library
home page
or in the triangle.c source code file. Examples of typical parameter
strings can be seen in the supplied high-level macros.
out
The output triangle data generated by the triangle module. The triangle library takes the input data and parameter string, performs the specified functions and outputs the generated triangle data using this output. This output is a struct_triangulateio group. Links can be made directly to the arrays contained in this group. Alternatively the struct_to_field macro can be used to convert the data into an AVS/Express field.
vorout
The output voronoi triangle data generated by the triangle module. The triangle library takes the input data and parameter string, performs the specified functions and outputs the generated voronoi triangle data using this output. This output is a struct_triangulateio group. Links can be made directly to the arrays contained in this group.
A number of utility modules are also provided along with the triangle library. These perform a number of simpler tasks that are not done directly by the triangle library.
fix_voronoi_edges
Edges generated by the voronoi triangulation algorithm can extend away to infinity. This module looks for those edges and changes them so that they can be displayed by the standard AVS/Express viewer.
compute_triangle_areas
This module takes a list of triangles and calculates the area of each triangle. The triangles are input as arrays of coordinates and connectivity data. The calculated areas are output as an array of floating point numbers.
point_in_triangle
This module takes a list of points and triangles and determines which triangle, if any, each point intersects with. It also determines how many points intersect with each triangle. The triangles are input as arrays of coordinates and connectivity data. The points are input as a simple array of coordinates. The triangle that each point intersects with and the number of points for each triangle are output as two arrays of integer numbers.
fault_region
This module takes a structured mesh and a fault line and determines which cells of the structured mesh the fault line crosses. The fault line is input as a single array of coordinates that represents a single polyline. The structured mesh is input as arrays of coordinates and connectivity. The module outputs a mesh that represents the cells that the fault line crossed and a set of cell data that contains a 1 for each affected cell. This cell data can be combined with the original input mesh.
The Triangle project contains 8 example applications that provide a good illustration of what the triangle library is capable of. Most of these example use either the ClickSketch or ContinuousSketch modules to create input data. Those that use the ClickSketch module start out with a blank window and expect the user to create a polyline. This is done by clicking the right mouse button in the viewer window. You should see you polyline appear in red. Once you have completed this you should click the Done button. This begins the triangulation process. Once this has finished the results are shown in the viewer window. The ContinuousSketch module is similar except that the user should hold and drag with the right mouse button to create a trail of points.
The examples supplied are as follows, beginning with the ClickSketch examples.
TriConcavePolygonExampleTriConvexHullExampleTriDelauneyTriangulationExampleTriPointInPolygonExampleCTRL-click the triangle containing the
picked point is determined and displayed.
TriVoronoiExampleTriFaultExampleTriMovingRegionExampleTriAnimatedRegionExampleiac_proj/triangle/trimods.v contains the V definitions of the low-level modules triangle, fix_voronoi_edges, compute_triangle_areas, point_in_triangle and fault_region and the group struct_triangulateio.
The low-level TriangleMods library containing the low-level modules does not specify a process. By default the express process will be used.
Dr. David Knight, Advanced Visual Systems, Inc.
Ma YingLiang, Manchester Visualization Centre Andrew Dodd, International AVS Centre
International AVS Centre Manchester Visualization Centre Manchester Computing University of Manchester Oxford Road Manchester United Kingdom M13 9PL