Skip to main content
This is a pre-production deployment of Warehouse. Changes made here affect the production instance of PyPI (
Help us improve Python packaging - Donate today!

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](
Release History

Release History

This version
History Node


History Node


History Node


History Node


History Node


Download Files

Download Files

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

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
chenhancc-0.0.5.tar.gz (173.1 kB) Copy SHA256 Checksum SHA256 Source Oct 6, 2017

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting