Skip to main content

A geodesic path solution using chenhan

Project description


A Fast geodesic algorithm in python that spans across the surface through the polygons. You will find it useful if you are working with 3D graphics and triangular meshes. Given a pt <a> as seed then this algorithm finds a smooth point to any point <p> on the mesh.
The algorithm is purely based on the paper of Shiqing who provided me with this wonderful c++ code as well. All I had to do was make some changes so it can be compiled as a python library. The timing or efficiency difference between the pure python implementation and c++ -> python conversion is atleast 210x times.

Many Thanks

The original c++ source code was provided to me by Dr. Xin Shiqing ( My sincere thanks to him for his help

Xin SQ, Wang GJ. Improving Chen and Han's algorithm on the discrete geodesic problem. ACM Transactions on Graphics (TOG). 2009 Aug 1;28(4):104.

Running the tests

Below snippets are some examples to test the chenhancc library::

A simple test using Python3

#!/usr/bin/env python3

from chenhancc import CPoint3D, CFace, CRichModel, CBaseModel, CExactMethodForDGP;
from random import random, randint;

verts = [CPoint3D(random() * 3,random() * 3,random() * 3) for i in range(20)];
faces = [CFace(randint(0,3),randint(0,3),randint(0,3)) for i in range(20)];

bmodel = CBaseModel();
bmodel.LoadModel(verts, faces);


rmodel = CRichModel();
rmodel.LoadModel(verts, faces);

print('END OF TESTS')


If you want to perform demos as shown in the screenshots above. Then after installing the sharedobject for chenhancc you should be also install another Blender plugin to see live paths on meshes. The link to the repository is [here]( Once you have installed the plugin then start clicking on the meshes and see paths between consecutive clicks.

Demos - Blender

You will find <b>blender</b> folder inside the <b>demo</b> folder. There is a blend file that can test a mesh loaded in the scene. Just ensure to load a mesh, select it with mouse and run the script `(Alt-p)`. You should see a path between the selected vertices as supplied in the code in the text editor of Blender. In the below code change the `svid` and `evid` to change the vertex selection. `svid` is the seed vertex index, and `evid` is the target vertex index to which a path should be found.

A simple test using Blender
.. code:: python
#----------Blender based api modules import----------------
import bpy, bmesh;
from mathutils import Vector;
#----------End of Blender based api modules import----------------

from chenhancc import CBaseModel as BaseModel, CRichModel as RichModel, CPoint3D as Point3D, CFace as Face, CICHWithFurtherPriorityQueue as ICHWithFurtherPriorityQueue;

c = bpy.context;
m = c.active_object;
svid = 0;
evid = 20000;

def rotate(l, n):
return l[n:] + l[:n];

def createPathMesh(points):
myvertexlist = [[2,2,2],[4,4,4],[6,6,6],[8,8,8]]

obName = "path_"+str(len(points));
me =;
ob =, me);

# Get a BMesh representation
bm =; # create an empty BMesh
bm.from_mesh(me); # fill it in from a Mesh

# Modify the BMesh, can do anything here...
for index, co in enumerate(points):
v =;
v.index = index;


for index, co in enumerate(points[1:]):
v1 = bm.verts[index-1];
v2 = bm.verts[index];
e =, v2));

# also add bm.edges and bm.faces

# Finish up, write the bmesh back to the mesh
bm.to_mesh(me);; # free and prevent further access

scn = bpy.context.scene;; = ob; = True;

verts = [];
faces = [];
loops =;

bmodel = RichModel();[svid].select = True;[evid].select = True;

for v in
p3d = Point3D(,,;

for f in
f_vids = [loops[lid].vertex_index for lid in f.loop_indices];
faces.append(Face(f_vids[0], f_vids[1], f_vids[2]));

bmodel.LoadModel(verts, faces);

emethod = ICHWithFurtherPriorityQueue(bmodel, set([svid]));
paths = emethod.FindSourceVertex(evid,[]);
paths = rotate(paths, 1);

path_verts = [];

for epoint in paths:
pt = epoint.Get3DPoint(bmodel);
path_verts.append(Vector((pt.x, pt.y, pt.z)));
print('DONE FOUND THE PATHS::: ');

**On any OS (Linux, OS X, MAC, Windows)**

- Clone this repository
- Navigate inside distribution_files
- run `python3 build` - To create the build
- run `python3 install --user` - for copying in your local library
- Or this can be pip-able soon or already available as ```pip3 install chenhancc ```

**Prerequesties for compiling everything yourself**
- This code is compiled using the magic binders for pybind11 created by binder.

*[Github link for binder](

*[Github link for pybind11](

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
chenhancc-0.0.5.tar.gz (173.1 kB) Copy SHA256 hash SHA256 Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page