PCDM - Parallel 2D Constrained Delaunay Meshing
Version 1.0

PCDM in parallel generates 2D quality constrained Delaunay meshes conforming 
to the given boundaries.

There is no warranty whatsoever. Use at your own risk.

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

Copyright (C) 2006  Andrey Nikolayevich Chernikov                 
                                                                  
This program is free software; you can redistribute it and/or     
modify it under the terms of the GNU General Public License       
as published by the Free Software Foundation; either version 2    
of the License, or (at your option) any later version.            
                                                                  
This program is distributed in the hope that it will be useful,   
but WITHOUT ANY WARRANTY; without even the implied warranty of    
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     
GNU General Public License for more details.                      
                                                                  
You should have received a copy of the GNU General Public License 
along with this program; if not, write to the Free Software       
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA     
02110-1301, USA.                                                  
                                                                  
Author's contact address:                                         
  Andrey N. Chernikov                                             
  Department of Computer Science                                  
  College of William and Mary                                     
  PO Box 8795,                                                    
  Williamsburg, VA 23187, USA                                     
  phone: 757-221-3436                                             
  email: ancher@cs.wm.edu     
                                      
Supervisor's contact address:                                     
  Nikos P. Chrisochoides                                          
  Department of Computer Science                                  
  College of William and Mary                                     
  PO Box 8795,                                                    
  Williamsburg, VA 23187, USA                                     
  phone: 757-221-3466                                             
  email: nikos@cs.wm.edu                                          

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

If you use the results obtained with PCDM to accomplish real work and/or for
publication, please include an appropriate acknowledgement and let me know. 
This is very important for me to be able to justify further development of the 
program!

As of January 2006, the most appropriate citation is

Andrey N. Chernikov and Nikos P. Chrisochoides. Parallel 2D Constrained 
Delaunay Meshing. Submitted to ACM Transactions on Mathematical Software,
January 2006. 

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

The libraries used by PCDM:

-- Robust Predicates by Jonathan Shewchuk, UC Berkeley;
-- Metis by George Karypis, Kirk Schloegel, and Vipin Kumar, 
   University of Minnesota;
-- Triangle by Jonathan Shewchuk, UC Berkeley.

These libraries should be downloaded and compiled separately (see below).
                            
--------------------------------------------------------------------------------

Command-line switches:

pcdm <input_region_file_name> <input_triangle_file_name>   \
     -a <double> [-q <double>] [-m <int>] [-o <directory>] \
     [-s <directory>] [-c] [-f <int>] [-h]                 \
     [{-c} or {-W <num_procs_1> <memory_1> ... <num_procs_k> <memory_k>}]
    
    input_region_file_name --- *.dat file, contains the boundaries of the 
                               subdomains, required;
    input_triangle_file_name --- *.cdt file, contains the initial constrained 
                                 Delaunay triangulations of the subdomains, 
                                 required;
    
    -a --- the upper bound on the desired triangle area, required;
    -q --- the lower bound on the desired minimal angle in degrees;
           the default is 20.1 degrees; 
    -m --- maximum number of `split' messages that can be accumulated for a
           particular subdomain before sending them; 512 by default;
    -o --- the directory to save the resulting files;
           if this parameter is omitted, the files are not saved;
    -s --- the directory to save the statistics files;
           if this parameter is omitted, the files are not saved;
    -Q --- compute the angle histogram; OFF by default;
    -f --- poll frequency, i.e. number of points inserted between calls 
           to poll(); 512 by default;
    -h --- print help and exit;
    -c --- use consecutive mapping of regions onto processors instead of calling
           MeTiS (e.g. regions 1...i1 -> processor 0, i1+1...i2 ->processor 1,
           and so on); OFF by default;
    -W --- if given, must be the last parameter; assuming the processes are
           taken from k subclusters, with memory_i (i=1,...,k) GB of memory 
           each, the subdomains are distributed proportional to the amount of
           memory available for each process. 
           (num_procs_1 + ... + num_procs_k = total number of processes)

Example:
  mpirun C -wd $PWD $PWD/pcdm $PWD/models/pipe4_madd.dat \
  $PWD/models/pipe4_madd.cdt -a 20 -m 512 -o $PWD/poly    
This will create 12 files in the directory `/poly', which can be visually 
inspected using Shewchuk's `showme' program.

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

Source files:

-- `pcdm.cc'    - the main program file;
-- `pcdm.h'     - the interface for calling PCDM as a library;
-- `defs.h'     - the required `define' commands;
-- `pcdmio.cc' and `pcdmio.h' - the I/O interface class;

Additional code included:

-- `driver.cc' - a sample program on how to use pcdm as a library;
   This code provides an example on using PCDM as a library, e.g. by a solver,
   and does not contribute to the functionality.
   
-- `cdt.cc'    - a utility for constructing initial constrained Delaunay
                 triangulations (CDTs); this is a standalone program which 
                 should be used before running the PCDM to generate the input
                 *.cdt files.
   Usage:
     cdt <input *.dat file name> <output *.cdt file name>
   where the input file structure is described below.
   
--------------------------------------------------------------------------------

Compiling:

1.a download the robust predicates from
    http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c
1.b compile `predicates.o', e.g. `gcc -O3 -c predicates.c'.
1.c set the PREDICATES variable in the PCDM Makefile to be the complete path
    (directory name) to 'predicates.o'.
    
2.a download the Metis library from
    http://www-users.cs.umn.edu/~karypis/metis/metis/download.html;
2.b unpack and compile it: `make';
2.c set the METIS variable in the PCDM Makefile.

3.a download Jonathan Shewchuk's Triangle software from 
    http://www.cs.cmu.edu/~quake/triangle.html; 
3.b unpack it;
3.c IMPORTANT!!! if the OS is not Linux, remove the -DLINUX flag from 
    CSWITCHES variable in Triangle's makefile;
3.d compile the Triangle: `make trilibrary';
3.e set the TRIANGLE variable in the PCDM Makefile to be the directory 
    containing `triangle.o'.
  
4   To compile PCDM, type one of these commands:
-- `make' to compile PCDM as a standalone program (recommended for the
    testing purposes);
-- `make pcdmlibrary' to compile PCDM as a library;
-- `make cdt' to compile the code for producing initial constrained Delaunay
   triangulations;
-- `make driver' to compile the sample driver program.
    
--------------------------------------------------------------------------------

Script files for launching the parallel jobs in batch mode:

Sample files are provided in the directory `/scripts'.
The names of the script files are composed of three parts:
-- a single letter standing for the first letter of the model name 
  (`c' for Chesapeake bay, `f' for the cylinder flow, 
  and `p' for the pipe cross-section);
-- a number indicating the total number of processes;
-- a number standing for the aggregation parameter.

These files are specific for the SciClone cluster at the College of William and
Mary. They will need to be mofified for other clusters.
    
--------------------------------------------------------------------------------

Statistics files:

The statistics are saved in the directory `/statistics'.
This is a tree of directories with the format:
/statistics/aggr_<aggregation>/<model name>/<total number of processes>/
<process number>

When the angle histogram is not computed, the corresponding entries are zeroes.

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

Input files (*.dat):

The input is a set of subregions (subdomains) that can share common boundaries
and are represented as segment bounded Planar Straight Line Graphs (PSLGs).

Four sample data sets are provided in the directory `/models':
-- pipe4000_madd.dat and pipe4000_madd.cdt
-- flow4000_madd.dat and flow4000_madd.cdt
-- chesapeake4000_madd.dat and chesapeake4000_madd.cdt
(These three contain 400 subdomains each and were used for the performance
evaluation presented in the paper)
-- pipe4_madd.dat and pipe4_madd.cdt
(This one is an additional, simpler, test case with only 4 subdomains)


*.dat file structure:

First line: <# of points>
Following lines (for each point): <point_id> <x> <y>
One line: <# of segments>
Following lines (for each segment): <segment_id> <point_id> <point_id>
One line: <# of subdomains>
Following lines (for each subdomain): 
  One line: <subdomain_id> <number_of_segments> 
  One line: <segment_id> ... <segment_id>
Following lines (for each subdomain): 
  One line: <subdomain_id> <number_of_holes>
  Following lines (for each hole): <x> <y>
    
All identificators are positive integers, unique within each type of entities.

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

Output mesh files:

The output mesh files are saved in the Showme format:
http://www.cs.cmu.edu/~quake/showme.html
Note that saving the files to disc is provided primarily for the testing
purposes and is very expensive in terms of time and space.


--
Andrey Chernikov
January 2006
