This directory contains two netlib versions.  The routines have been
grabbed from netlib and other places.  In general the C files are
direct translations of the FORTRAN, so the `*.f` should be edited if
improvements are required or mods are to be made.

The old netlib library has been almost completely removed.  All code
but `triangle.c` and related code belong to the newer `v3p_netlib
library`.

The `v3p_netlib` library contains updated netlib code converted with `f2c`
in a thread-safe manner.  Sources have been modified to use the
`v3p_*.h` headers in this directory.  Types and function names have been
mangled to start with a `v3p_netlib_` prefix.  This distinguishes them
from other netlib libraries and keeps the code grouped and isolated.

------------------------------------------------------------------------------
The `libf2c` directory was created as follows:

1. Downloaded and extracted http://www.netlib.org/f2c/libf2c.zip

2. Converted sources to include our mangled `f2c` header.

    ```bash
    for f in libf2c/*.c; do
        cat $f | sed 's/f2c.h/v3p_f2c.h/' > $f.tmp && mv $f.tmp $f
    done
    ```
3. Added a missing leading segment to some sources.

    ```bash
    for f in libf2c/sig_die.c libf2c/cabs.c; do
        (echo "#include \"v3p_f2c.h\"
    #undef abs
    #undef min
    #undef max
    " && cat $f) > $f.tmp &&
        mv $f.tmp $f
    done
    ```
4. Remove calls to `f_exit` from `libf2c/sig_die.c`

5. Put `v3p_netlib_`-mangling definitions in `v3p_f2c_mangle.h` and
`undef` directives in `v3p_f2c_unmangle.h`.  These change the symbol
and type names using the preprocessor to avoid sweeping changes
of the code.

Updates to the `libf2c` directory for newer upstream versions should be
made by first committing them to a new branch and then merging the
changes to the main tree.

------------------------------------------------------------------------------

The other directories were created as follows:

1. Find needed FORTRAN routines from http://www.netlib.org/liblist.html

2. Use the web interface to download the routines and dependencies.
For example at

    http://www.netlib.org/cgi-bin/netlibfiles.pl?filename=/linpack/dsvdc.f

    choose "yes" for including BLAS routines and package as zip or tgz.

3. Extract the sources into the `vxl/v3p/netlib` directory.  They should
automatically create subdirectories like `blas/` and `linpack/` with the
respecitve sources.

4. Commit the original FORTRAN sources.
    ```bash
    $ git commit -m "Adding original FORTRAN code for this function."
    ```

5. Convert the sources to C using `f2c` and replace the `f2c.h` header
inclusion with `v3p_netlib.h`:
    ```bash
    for d in blas linpack temperton eispack laso arpack lapack/complex16 lapack/double lapack/single lapack/util napack minpack opt linalg toms datapac mathews; do
      for f in ${d}/*.f; do
        b=`echo "$f" | sed 's/.f$//'`
        if [ ! -f "${b}.c" ]; then
          echo "Converting ${b}.f to ${b}.c"
          f2c -A -a -C++ -c -ec -E -P -d${d} ${b}.f &&
          cat ${b}.c | sed 's/f2c.h/v3p_netlib.h/' > ${b}.c.tmp &&
          mv ${b}.c.tmp ${b}.c
        fi
      done
    done
    ```
    ```bash
    $ git commit -m "Converted function from FORTRAN to C."
    ```

  Note the use of options to `f2c`:

    -A    = Produce ANSI C.
    -a    = Make local variables automatic instead of static (for threads).
    -C++  = Make code C++ compatible.
    -c    = Include original FORTRAN code in comments.
    -ec   = Place uninitialized COMMON blocks in separate files
    -E    = Declare uninitialized common blocks to be extern.
    -P    = Write ANSI C prototypes to .P files.
    -ddir = Write output files to given directory.

6. Put `v3p_netlib_`-mangling definitions in `v3p_netlib_mangle.h` and
`undef` directives in `v3p_netlib_unmangle.h`.  These change the symbol
and type names using the preprocessor to avoid sweeping changes of the
code.  Use
    ```bash
    $ nm libv3p_netlib.a | grep " [TRD] "
    ```
to identify symbols in the library that have not been
properly mangled.  Note if using shared libraries the command
is
    ```bash
    $ nm libv3p_netlib.so | grep " [TRD] "
    ```
and the shared-library implementation functions `_fini` and `_init` should
be left alone.

7. Convert prototypes in the `*.P` files generated by `f2c` to `*.h` files
with the mangled interface.  Include them all in `v3p_netlib_prototypes.h`.
    ```bash
    echo "/* Include prototype headers. */" > v3p_netlib_prototypes.h
    for f in blas/*.P linpack/*.P temperton/*.P eispack/*.P laso/*.P arpack/*.P lapack/*/*.P napack/*.P minpack/*.P opt/*.P linalg/*.P toms/*.P datapac/*.P mathews/*.P; do
      b=`echo "$f" | sed 's/.P//'`
      if [ ! -f "${b}.h" ] ; then
        echo "Converting prototype $b"
        cat ${b}.P |
        grep -v "^/\\*" |
        sed 's/\([A-Za-z0-9]*\)_(/v3p_netlib_\1_(/' |
        sed 's/(/(\n  /g' |
        sed 's/, /,\n  /g' |
        sed 's/)/\n  )/g' |
        sed 's/const/v3p_netlib_const/g' |
        sed '/ logical1/ {s/logical1/v3p_netlib_logical1/g}' |
        sed '/ real/ {s/real/v3p_netlib_real/g}' |
        sed '/ integer1/ {s/integer1/v3p_netlib_integer1/g}' |
        sed '/ uinteger/ {s/uinteger/v3p_netlib_uinteger/g}' |
        sed '/ integer/ {s/integer/v3p_netlib_integer/g}' |
        sed '/ address/ {s/address/v3p_netlib_address/g}' |
        sed '/ shortint/ {s/shortint/v3p_netlib_shortint/g}' |
        sed '/ doublereal/ {s/doublereal/v3p_netlib_doublereal/g}' |
        sed '/ doublecomplex/ {s/doublecomplex/v3p_netlib_doublecomplex/g}' |
        sed '/ complex/ {s/complex/v3p_netlib_complex/g}' |
        sed '/ shortlogical/ {s/shortlogical/v3p_netlib_shortlogical/g}' |
        sed '/ logical/ {s/logical/v3p_netlib_logical/g}' |
        sed '/ longint/ {s/longint/v3p_netlib_longint/g}' |
        sed '/ ulongint/ {s/ulongint/v3p_netlib_ulongint/g}' |
        sed '/ ftnlen/ {s/ftnlen/v3p_netlib_ftnlen/g}' |
        sed '/ C_f/ {s/C_f/v3p_netlib_C_f/g}' |
        sed '/ E_f/ {s/E_f/v3p_netlib_E_f/g}' |
        sed '/ H_f/ {s/H_f/v3p_netlib_H_f/g}' |
        sed '/ Z_f/ {s/Z_f/v3p_netlib_Z_f/g}' |
        cat > ${b}.h
      fi
      echo "#include \"${b}.h\"" >> v3p_netlib_prototypes.h
    done
    ```
    ```bash
    $ git commit -m "Converted .P file prototypes generated by f2c to v3p_netlib_-mangled protytypes in header files."
    ```
Some of these prototype header files have been manually edited to add
`v3p_netlib_const` to some of the arguments.  This is a hack to allow
const-correct code to call the functions.  The `v3p_netlib_const` macro
is defined to empty when building sources in side the library which
allows the f2c-converted code to compile without manual conversion to
const-correctness.  The macro is defined to "const" when compiling
other sources which enforces const-correctness for code calling the
routines.  Since the interface is `extern "C"` code, the symbol names
are not changed by the presence or absence of `const`.
    ```bash
    $ git commit -m "Manually documented prototype and added v3p_netlib_const to appropriate arguments."
    ```
------------------------------------------------------------------------------

Thread safety can be partially checked in this directory by running
    ```bash
    $ grep "  static" **/*.c |grep -v constant
    ```
Global data declared static seem to be constant, so only local
variables are of concern, which is why the grep expression contains
spaces.  Local statics that have been manually deemed safe (constant)
should be marked with a
    ```cpp
       /* constant */
    ```
comment to avoid being listed in the grep output.  Local statics that
require one-time initialization at run-time should be marked with a
    ```cpp
       /* runtime-initialized constant */
    ```

comment to avoid being listed in the grep output.  The routines
holding them should be given a `v3p_netlib_*_init()` function that is
called from `v3p_netlib_init.c` in the `v3p_netlib_initialize` function.

Functions that call back to user functions have been manually given a
userdata callback argument.  This allows them to be reentrant.

Triangle
A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
Version 1.6

Show Me
A Display Program for Meshes and More.
Version 1.6

Copyright 1993, 1995, 1997, 1998, 2002, 2005 Jonathan Richard Shewchuk
2360 Woolsey #H
Berkeley, California  94705-1927
Please send bugs and comments to jrs@cs.berkeley.edu

Created as part of the Quake project (tools for earthquake simulation).
Supported in part by NSF Grant CMS-9318163 and an NSERC 1967 Scholarship.
There is no warranty whatsoever.  Use at your own risk.


Triangle generates exact Delaunay triangulations, constrained Delaunay
triangulations, conforming Delaunay triangulations, Voronoi diagrams, and
high-quality triangular meshes.  The latter can be generated with no small
or large angles, and are thus suitable for finite element analysis.
Show Me graphically displays the contents of the geometric files used by
Triangle.  Show Me can also write images in PostScript form.

Information on the algorithms used by Triangle, including complete
references, can be found in the comments at the beginning of the triangle.c
source file.  Another listing of these references, with PostScript copies
of some of the papers, is available from the Web page

    http://www.cs.cmu.edu/~quake/triangle.research.html

------------------------------------------------------------------------------

These programs may be freely redistributed under the condition that the
copyright notices (including the copy of this notice in the code comments
and the copyright notice printed when the `-h' switch is selected) are
not removed, and no compensation is received.  Private, research, and
institutional use is free.  You may distribute modified versions of this
code UNDER THE CONDITION THAT THIS CODE AND ANY MODIFICATIONS MADE TO IT
IN THE SAME FILE REMAIN UNDER COPYRIGHT OF THE ORIGINAL AUTHOR, BOTH
SOURCE AND OBJECT CODE ARE MADE FREELY AVAILABLE WITHOUT CHARGE, AND
CLEAR NOTICE IS GIVEN OF THE MODIFICATIONS.  Distribution of this code as
part of a commercial system is permissible ONLY BY DIRECT ARRANGEMENT
WITH THE AUTHOR.  (If you are not directly supplying this code to a
customer, and you are instead telling them how they can obtain it for
free, then you are not required to make any arrangement with me.)

------------------------------------------------------------------------------

The files included in this distribution are:

  README           The file you're reading now.
  triangle.c       Complete C source code for Triangle.
  showme.c         Complete C source code for Show Me.
  triangle.h       Include file for calling Triangle from another program.
  tricall.c        Sample program that calls Triangle.
  makefile         Makefile for compiling Triangle and Show Me.
  A.poly           A sample input file.

Each of Triangle and Show Me is a single portable C file.  The easiest way
to compile them is to edit and use the included makefile.  Before
compiling, read the makefile, which describes your options, and edit it
accordingly.  You should specify:

  The source and binary directories.

  The C compiler and level of optimization.

  The "correct" directories for include files (especially X include files),
  if necessary.

  Do you want single precision or double?  (The default is double.)  Do you
  want to leave out some of Triangle's features to reduce the size of the
  executable file?  Investigate the SINGLE, REDUCED, and CDT_ONLY symbols.

  If yours is not a Unix system, define the NO_TIMER symbol to remove the
  Unix-specific timing code.  Also, don't try to compile Show Me; it only
  works with X Windows.

  If you are compiling on an Intel x86 CPU and using gcc w/Linux or
  Microsoft C, be sure to define the LINUX or CPU86 (for Microsoft) symbol
  during compilation so that the exact arithmetic works right.

Once you've done this, type "make" to compile the programs.  Alternatively,
the files are usually easy to compile without a makefile:

  cc -O -o triangle triangle.c -lm
  cc -O -o showme showme.c -lX11

On some systems, the C compiler won't be able to find the X include files
or libraries, and you'll need to specify an include path or library path:

  cc -O -I/usr/local/include -o showme showme.c -L/usr/local/lib -lX11

Some processors, including Intel x86 family and possibly Motorola 68xxx
family chips, are IEEE conformant but have extended length internal
floating-point registers that may defeat Triangle's exact arithmetic
routines by failing to cause enough roundoff error!  Typically, there is a
way to set these internal registers so that they are rounded off to IEEE
single or double precision format.  I believe (but I'm not certain) that
Triangle has the right incantations for x86 chips, if you have gcc running
under Linux (define the LINUX compiler symbol) or Microsoft C (define the
CPU86 compiler symbol).

If you have a different processor or operating system, or if I got the
incantations wrong, you should check your C compiler or system manuals to
find out how to configure these internal registers to the precision you are
using.  Otherwise, the exact arithmetic routines won't be exact at all.
See http://www.cs.cmu.edu/~quake/robust.pc.html for details.  Triangle's
exact arithmetic hasn't a hope of working on machines like the Cray C90 or
Y-MP, which are not IEEE conformant and have inaccurate rounding.

Triangle and Show Me have both text and HTML documentation.  The latter is
illustrated.  Find it on the Web at

  http://www.cs.cmu.edu/~quake/triangle.html
  http://www.cs.cmu.edu/~quake/showme.html

Complete text instructions are printed by invoking each program with the
`-h' switch:

  triangle -h
  showme -h

The instructions are long; you'll probably want to pipe the output to
`more' or `lpr' or redirect it to a file.

Both programs give a short list of command line options if they are invoked
without arguments (that is, just type `triangle' or `showme').

Try out Triangle on the enclosed sample file, A.poly:

  triangle -p A
  showme A.poly &

Triangle will read the Planar Straight Line Graph defined by A.poly, and
write its constrained Delaunay triangulation to A.1.node and A.1.ele.
Show Me will display the figure defined by A.poly.  There are two buttons
marked "ele" in the Show Me window; click on the top one.  This will cause
Show Me to load and display the triangulation.

For contrast, try running

  triangle -pq A

Now, click on the same "ele" button.  A new triangulation will be loaded;
this one having no angles smaller than 20 degrees.

To see a Voronoi diagram, try this:

  cp A.poly A.node
  triangle -v A

Click the "ele" button again.  You will see the Delaunay triangulation of
the points in A.poly, without the segments.  Now click the top "voro" button.
You will see the Voronoi diagram corresponding to that Delaunay triangulation.
Click the "Reset" button to see the full extent of the diagram.

------------------------------------------------------------------------------

If you wish to call Triangle from another program, instructions for doing
so are contained in the file `triangle.h' (but read Triangle's regular
instructions first!).  Also look at `tricall.c', which provides an example
of how to call Triangle.

Type "make trilibrary" to create triangle.o, a callable object file.
Alternatively, the object file is usually easy to compile without a
makefile:

  cc -DTRILIBRARY -O -c triangle.c

Type "make distclean" to remove all the object and executable files created
by make.

------------------------------------------------------------------------------

If you use Triangle, and especially if you use it to accomplish real work,
I would like very much to hear from you.  A short letter or email (to
jrs@cs.berkeley.edu) describing how you use Triangle will mean a lot to me.
The more people I know are using this program, the more easily I can
justify spending time on improvements and on the three-dimensional
successor to Triangle, which in turn will benefit you.  Also, I can put you
on a list to receive email whenever a new version of Triangle is available.

If you use a mesh generated by Triangle or plotted by Show Me in a
publication, please include an acknowledgment as well.  And please spell
Triangle with a capital `T'!  If you want to include a citation, use
`Jonathan Richard Shewchuk, ``Triangle:  Engineering a 2D Quality Mesh
Generator and Delaunay Triangulator,'' in Applied Computational Geometry:
Towards Geometric Engineering (Ming C. Lin and Dinesh Manocha, editors),
volume 1148 of Lecture Notes in Computer Science, pages 203-222,
Springer-Verlag, Berlin, May 1996.  (From the First ACM Workshop on Applied
Computational Geometry.)'


Jonathan Richard Shewchuk
July 27, 2005