GCTIN - Greedy Cuts Triangular Irregular Networks

Implementation of the algorithm from "Automatic Generation of Triangular Irregular Networks Using Greedy Cuts" by Cláudio T. Silva, Joseph S. B. Mitchell, and Arie E. Kaufman, IEEE Visualization 1995: 201-208.

This tool generates simplified triangular meshes from terrain height field data using error-bounded approximation.

Features

• Error-bounded triangulation: Guarantees all points are within epsilon distance of the generated mesh
• Greedy optimization: Minimizes triangle count while maintaining error bounds
• Multiple output formats: Native triangle format and Geomview OFF format
• Sample datasets: Includes 120x120 height field data from various terrains

Quick Start

Build

Using CMake (recommended):

mkdir build
cd build
cmake ..
make

Or using the original Makefile:

cd src
make

This creates two executables:

• gctin - Main triangulation program
• tri2off - Converts triangles to OFF format for visualization

Basic Usage

# If using CMake build
cd build
./gctin 0.5 ../data120/jackson-w.pts
./tri2off < ../data120/jackson-w.pts-0.5.triangles > output.off

# If using Makefile build
cd src
./gctin 0.5 ../data120/jackson-w.pts
./tri2off < ../data120/jackson-w.pts-0.5.triangles > output.off

Input Format

Height field files use ZMESH format:

ZMESH
  120   120
1.7
1.5
1.5
...

First line: ZMESH header
Second line: width and height dimensions
Following lines: height values in row-major order

Sample Datasets

The data120/ directory contains 120x120 height fields:

• buffalo-w.pts - Buffalo terrain (west)
• denver-e.pts - Denver terrain (east)
• eagle_pass-e.pts - Eagle Pass terrain (east)
• jackson-w.pts - Jackson terrain (west)
• seattle-e.pts - Seattle terrain (east)

Algorithm Overview

The algorithm uses a three-phase iterative approach:

1. Initial approximation: Creates boundary polygon from height field
2. Iterative refinement: Progressively subdivides polygons using three phases:
   • Phase 1: Standard vertex insertion
   • Phase 2: Alternative insertion strategies
   • Phase 3: Edge-based operations
3. Error validation: Ensures triangles meet epsilon error bound
4. Output: Writes final triangulation or marks infeasible regions

Output

The program outputs:

• Triangle count and number of infeasible triangles
• Execution time
• Triangle file with format: x1 y1 z1 x2 y2 z2 x3 y3 z3 per line

Example output:

error bound: 0.500000
1127 triangles generated, 59 not feasible
execution time: 1.5069

Visualization

Use Geomview (available from http://www.geom.umn.edu) to visualize OFF files:

./tri2off < data120/jackson-w.pts-0.5.triangles > terrain.off
geomview terrain.off

Build Requirements

• CMake 3.10 or higher (for CMake build)
• ANSI C compiler (tested on SGI, Sparc, PC)
• Math library (-lm)

License

Copyright (c) 1994-1997 by C. T. Silva and the Research Foundation of the State University of New York at Stony Brook.

Permission to use, copy, modify and distribute this software for any purpose is hereby granted without fee, provided that the copyright notice appears in all copies and that you do not sell the software.

THE SOFTWARE IS PROVIDED "AS IS" AND WITHOUT WARRANTY OF ANY KIND.

Citation

If you use this software in your research, please cite:

Cláudio T. Silva, Joseph S. B. Mitchell, Arie E. Kaufman:
Automatic Generation of Triangular Irregular Networks Using Greedy Cuts. 
IEEE Visualization 1995: 201-208

Author

Claudio T. Silva
Computational Geometry Group
Department of Applied Mathematics and Statistics
State University of New York at Stony Brook