chenhancc

A Fast geodesic algorithm in python that spans across the surface through the polygons

Many Thanks

The original c++ source code was provided to me by Dr. Xin Shiqing (https://sites.google.com/site/xinshiqing/). My sincere thanks to him for his help

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. </>

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.

chenhan_cython

Using cython instead of PyBind11 generated by Binder. Rather straightforward. I am giving up on Binder to generate the pybind11 binding code for Windows. This attempt is to create PXD files and use autowrap to generate the PYX files. Looks promising so far.

Installation

Python Package Manager (PIP)

• pip install py_chenhancc --user or
• sudo pip install py_chenhancc (You need administration privileges)

Easy Install

easy_install --prefix $HOME/.local This is for ubuntu

Prerequesties

• This code is compiled using cython and autowrap module to generate PYX files. There is no need to generate the PYX files yourself. It has been generated already for Windows and GCC systems

  *Github link for autowrap.

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

• You can install using PIP
• Do pip install py_chenhancc

ISSUES

• Unix systems - Using pip install pip install py_chenhancc it would fail saying the command gcc failed with the compilation because of blah blah reason. I got it to work by exporting export CC=x86_64-linux-gnu-g++
• Next if you notice it still fails after setting the above step ensure you have gcc version 4.9 atleast. Looks like gcc 4.8 is annoyed with std=c++14 flag in the compiler options. These two steps should figure you out.
• Windows and Macintosh systems - I am finding it difficult to get my hands on a macintosh machine. Will soon test it and update all of you with what is necessary. If someone is kind enough to lend me a hand then please.

License

I haven't thought about it yet. The world is so strange that even free stuffs come at a cost. Did you notice that even for free licenses there are many variants to it? Anyways feel free to do things you want to after cloning the repository.

Demos

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 blender folder inside the demo 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.

#Replace the below Blender api imports with the framework of your choice. 
#The idea is to supply points, and face information for mesh representation
#inside the geodesics algorithm

#----------Blender based api modules import----------------
import bpy, bmesh;
from mathutils import Vector;
#----------End of Blender based api modules import----------------

from py_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 = bpy.data.meshes.new(obName);
    ob = bpy.data.objects.new(obName, me);

    # Get a BMesh representation
    bm = bmesh.new();   # 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 = bm.verts.new(co);
        v.index = index;
        
    bm.verts.ensure_lookup_table();
    
    for index, co in enumerate(points[1:]):
        v1 = bm.verts[index-1];
        v2 = bm.verts[index];
        e = bm.edges.new((v1, v2));
        
    
    # also add bm.edges and bm.faces

    # Finish up, write the bmesh back to the mesh
    bm.to_mesh(me);
    bm.free();  # free and prevent further access
    
    scn = bpy.context.scene;
    scn.objects.link(ob);
    scn.objects.active = ob;
    ob.select = True;


if(m):
    verts = [];
    faces = [];
    loops = m.data.loops;
    
    bmodel = RichModel();
    
    m.data.vertices[svid].select = True;
    m.data.vertices[evid].select = True;
    
    for v in m.data.vertices:
        p3d = Point3D(v.co.x, v.co.y, v.co.z);
        verts.append(p3d);
   
    for f in m.data.polygons:
        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);
    bmodel.Preprocess();
    
    emethod = ICHWithFurtherPriorityQueue(bmodel, set([svid]));
    emethod.Execute();
    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)));
    createPathMesh(path_verts);
    print('DONE FOUND THE PATHS::: ');