3D Dubins Path Solver

Find the shortest curvature-constrained path between two oriented points in 3D space. Also known as CLC (Curve-Line-Curve) or CSC (Curve-Straight-Curve) paths. Applications include directional drilling, UAV/drone flight planning, autonomous vehicles, underwater vehicle routing, pipeline routing, and robotics.

What is a CLC path?

A CLC (Curve-Line-Curve) path is the 3D equivalent of a Dubins path (detailed overview) — the shortest route between two oriented points when constrained to a minimum turning radius. In 2D, Dubins (1957) proved that optimal paths consist of circular arcs and straight lines. The CLC type connects two configurations using an arc, a straight tangent line, then a second arc.

Extending this to 3D is significantly harder. In 2D there are only 6 possible path types; in 3D the turning circle at each point becomes a full family of circles — every possible turning direction perpendicular to the heading. Finding which pair of circles (one at the start, one at the target) can be connected by a straight tangent line is a challenging geometric search problem.

Each configuration is a point in space with a direction (position + unit vector). The solver finds all valid CLC paths connecting them, ranked by total arc angle or path length.

Points and conventions

The path passes through four points, each with a position and direction:

Path segments

1. C1 — circular arc from P0 to P1, with turning radius r. The arc departs P0 in direction vec0 and arrives at P1 in direction vec1.
2. L — straight line from P1 to P2. Direction is vec1 = vec2 (tangent continuity).
3. C2 — circular arc from P2 to P3, with turning radius r3. The arc departs P2 in direction vec2 and arrives at P3 in direction vec3.

The key constraint: vec1 = vec2 — the direction at P1 must equal the direction at P2, since the straight line segment connects them.

3D example — two solutions for the same start and target

Blue: gentle path (133° total arc). Red: wrap-around path (356° total arc). Both are valid CLC solutions connecting the same P0 and P3.

Input

Output (per solution)

Multiple solutions

Many geometries have more than one valid CLC path. For example, a path can wrap the "short way" or the "long way" around a turning circle. The solver finds multiple solutions where they exist, ranked by your chosen criterion (minimize: "arc" for gentlest path, or "md" for shortest total path length).

Accuracy tiers

* GPU timings on NVIDIA RTX 3080 Ti at batch sizes of 1,000+ pairs. Small batches (< 10 pairs) run on CPU where GPU launch overhead exceeds compute time — expect ~20-40ms/pair. The compute field in the response indicates which was used.

Radius sweep

r_scale_min and r_scale_max are ratio multipliers applied to the turning radius r. For example, with DLS = 3°/30m the design radius is r ≈ 573m:

Set r_scale_min=0.9 and r_scale_max=1.1 with n_r_steps=5 to solve at exactly 5 radii across that range (0.9, 0.95, 1.0, 1.05, 1.1). If the design radius (1.0) falls within the range, the nearest grid point is snapped to it — so you always get the design radius without using an extra solve. All radii are batched in a single GPU call, so the incremental cost of additional radii is low.

Useful for finding the optimal turning radius or checking feasibility at different curvatures. A minor increase in DLS (smaller radius) can result in a significantly shorter total path length. In drilling: optimising dogleg severity.

Drilling context

DLS to radius: The turning radius r is derived from dogleg severity (DLS) and course length:

r = (180 / π) × (course_length / DLS)

where DLS is in degrees per course_length (e.g. °/30m or °/100ft). For example, DLS = 3°/30m gives r ≈ 573m.

Terminology mapping:

Try the solver

The WellEng CLC Solver is available as a REST API — send a JSON request with your start and target configurations, get ranked CLC solutions back in milliseconds. No installation required.

• Interactive API docs — try it in your browser with the built-in examples (click Authorize, enter your API key, then Try it out)
• Health check — verify the solver is running (no auth required)
• Request an API key — free tier available for evaluation (up to 10 pairs per request)

The solver runs on GPU (NVIDIA RTX 3080 Ti) and handles batch workloads of up to 100,000 pairs per request at ~0.1ms/pair. Small batches run on CPU. The compute field in the response tells you which was used.

Quick start — curl example

curl -s --compressed -X POST https://api.welleng.org/api/v1/solve \
  -H "Content-Type: application/json" \
  -H "X-API-Key: YOUR_KEY" \
  -d '{
    "pairs": [{
      "pos0": [0, 0, 0], "vec0": [0, 0, 1],
      "pos3": [100, 50, 600], "vec3": [0.2, 0.1, 0.97],
      "r": 573
    }],
    "solver": "analytical",
    "shortest_only": true
  }'

Radius sweep

To test multiple turning radii, add r_scale_min, r_scale_max, and optionally n_r_steps:

{
  "pairs": [{"pos0": ..., "vec0": ..., "pos3": ..., "vec3": ..., "r": 573}],
  "solver": "analytical",
  "shortest_only": true,
  "r_scale_min": 0.8,
  "r_scale_max": 1.2,
  "n_r_steps": 5
}

This tests 5 r1-scales × 5 r2-scales = 25 permutations per pair, returning the shortest solution from each. If n_r_steps is omitted, it defaults to 3 when a sweep is requested.

Background: the 3D Dubins problem

From 2D to 3D

In 1957, Lester Dubins proved that the shortest path between two oriented points in a plane, subject to a minimum turning radius, is composed of at most three segments — each either a circular arc (C) at the minimum radius or a straight line (S). This gives six possible Dubins path types: CSC (three variants) and CCC (three variants). The problem has elegant closed-form solutions in 2D and is widely used in robot motion planning, UAV path planning, and vehicle routing.

Extending Dubins paths to 3D is an open problem in computational geometry. The key difficulty: in 2D, each point has exactly two turning circles (left and right). In 3D, the set of all possible turning circles from a point forms a continuous family — every direction perpendicular to the heading defines a valid turning circle. Finding a valid CLC path requires identifying one circle at the start and one at the target that can be connected by a mutual tangent line — a search over a much larger space than the 2D case.

Classical approaches and their limitations

Several approaches have been proposed for 3D Dubins-like path planning:

Analytical extensions of 2D Dubins. Some work extends Dubins' 2D results to restricted 3D cases — for example, Chitsaz and LaValle (2007) characterised time-optimal paths for a Dubins airplane, and Owen, Beard and McLain (2014) provided implementations for fixed-wing UAVs. These are effective for their specific domains but don't generalise to arbitrary 3D orientations.

Iterative numerical methods. In directional drilling, the standard approach is a fixed-point iteration that adjusts toolface and dogleg angles until the endpoint converges. The welleng library's Connector class uses this approach and is reliable for realistic well geometries. However, iterative methods can converge to local minima — particularly at extreme curvatures — and are inherently sequential (one pair at a time), limiting throughput.

The scaling problem. All of these approaches process one pair at a time. In applications like multi-target well planning, anti-collision checking, or real-time UAV re-routing, you may need to solve thousands to hundreds of thousands of pairs simultaneously. Sequential methods that take 5-15ms per pair become impractical at this scale. This solver was designed specifically for batch throughput — solving 100,000 pairs in ~12 seconds on a single GPU.

Our approach

This solver uses a novel geometric formulation that is natively GPU-parallel, enabling batch throughput orders of magnitude faster than sequential methods. Key properties:

• Exhaustive search — the entire solution space is explored, not just a few candidate directions
• GPU-parallel — the core computation is embarrassingly parallel, mapping naturally to GPU hardware
• Multiple solutions — valid CLC paths are found and ranked, not just the first local minimum

Applications

3D CLC paths appear in any domain where a vehicle or tool must travel between two oriented points with constrained curvature:

• Directional drilling — planning well trajectories subject to dogleg severity limits (Wikipedia)
• Aviation — aircraft approach paths, UAV mission planning with altitude changes
• Autonomous vehicles — 3D path planning on undulating terrain
• Marine navigation — submarine and AUV routing with depth constraints
• Pipeline and cable routing — minimum bend radius constraints in 3D layouts
• Robotics — manipulator path planning with joint curvature limits

References

• Dubins, L.E. (1957). "On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents". American Journal of Mathematics. Wikipedia · Grokipedia
• Sawaryn, S.J. and Thorogood, J.L. (2005). "A Compendium of Directional Calculations Based on the Minimum Curvature Method". SPE 84246-PA. SPE Drilling & Completion. OnePetro
• Scholes, H. (1992). "Constant Curvature Method for Planning a 3-D Directional Well". SPE 24381. OnePetro
• Chitsaz, H. and LaValle, S.M. (2007). "Time-optimal paths for a Dubins airplane". IEEE CDC. PDF
• Owen, M., Beard, R. and McLain, T. (2014). "Implementing Dubins Airplane Paths on Fixed-Wing UAVs". Handbook of Unmanned Aerial Vehicles, Springer. Link
• Sun, Y. et al. (2021). "Subsea field layout optimization (Part I) — directional well trajectory planning based on 3D Dubins Curve". Journal of Petroleum Science and Engineering. ScienceDirect
• Hota, S. and Ghose, D. (2010). "Optimal Geometrical Path in 3D with Curvature Constraint". IEEE/RSJ IROS. Analytical CSC construction for "sufficiently far" configurations. IEEE Xplore
• Baez, V.M., Navkar, N. and Becker, A.T. (2024). "An Analytic Solution to the 3D CSC Dubins Path Problem". arXiv:2405.08710. Shows up to 7 valid CSC solutions exist via inverse kinematics formulation. arXiv
• Wikipedia: Motion planning — broader context for path planning under curvature constraints
• Wikipedia: Directional drilling — the primary application domain
• welleng — open-source well engineering library by the same author, which motivated this work

Interactive API docs · [email protected] · Author · Guide v3.5