cdt

KO | EN

gitlite — search

#hacktoberfest #react #ai #llm #go #machine-learning #docker #windows #cli #kubernetes #awesome-list #pytorch #ios #openai

(★ 105)

Single Header 2D Constrained Delaunay Triangulation

File Explorer

Download Latest Version (.zip)

- glad.obj
- glew32.dll
- glew32.lib
- glew32s.lib
- glfw3.dll
- glfw3.lib
- glfw3_mt.lib
- glfw3dll.lib
- - main.c
- - ex_gl.c
  - ex_gl.h
  - ex_log.c
  - ex_log.h
  - ex_math.c
  - ex_math.h
  - ex_shape.h
  - main.c
- - ex_ds.cpp
  - ex_ds.h
  - ex_engine.cpp
  - ex_engine.h
  - ex_gl.cpp
  - ex_gl.h
  - ex_math.cpp
  - ex_math.h
  - main.cpp
  - pathfind.cpp
- dt.png
- non_dt.png
- operator_basic.png
- operator_intermediate.png
- operators.png
- org.png
- triangle.png
- vertex.png
.gitignore
build.bat
cdt.h
README.md

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# CDT

**CDT** is a single-header, stb-style C library for **incremental 2D Constrained Delaunay Triangulation**, designed with game development in mind.

## What is CDT?

CDT stands for **Constrained Delaunay Triangulation**.  
It produces high-quality, "fat" triangles instead of long, thin "sliver" triangles, which results in significantly better navigation meshes and more stable geometry processing.

### Visual comparison

**Without Delaunay refinement (many thin triangles):**

**With Constrained Delaunay Triangulation (CDT):**

## Why should I consider this library?
- It is fully dynamic: you can add or remove obstacles (constraints) at runtime, during gameplay.
- It is a single-header C library (stb-style): just include one file, no dependencies, easy to use and easy to port.

## What are the downsides?
- The library is not fully optimized yet, but it is still usable.
- Since the core is currently based on quad-edges and does not retain triangles, iterating over all triangles is somewhat cumbersome and inefficient at the moment.
- Familiarity with basic quad-edge operators is recommended to fully utilize this library.

## Data Structure Explanation
First, note that a triangle consists of three directed edges ordered counter-clockwise; thus, each directed edge is associated with exactly one triangle. 
In this library, a directed edge is aliased as a quad-edge.

A quad-edge structure stores the vertex from which it originates.

A vertex stores its coordinates and an array of quad-edges that originate from it.

## Quad-Edge Operators
Those are the most basic operators you'll most likely care about.

Then, you can do something like this:

The library provides the full set of operators; however, as aforementioned above, you'll 
most likely care about sym, lnext and org.

## How to build examples
#### Windows (MSVC cl x64)
Simply run build.bat within the root directory.
``` console
> build
```

cdt

File Explorer

Today's picks

Was this content helpful?

Recent Feedback

cdt

File Explorer

Today's picks

Was this content helpful?

Recent Feedback

Download README