[Bf-committers] Re: [Bf-blender-cvs] CVS commit: blender/source/blender/include BIF_editmesh.h blender/source/blender/src editmesh_tools.c editobject.c

[Brecht Van Lommel]

Hey Geoffrey,

Geoffrey Bantle wrote:
>   Log:
>   -> Path Select Tool

Nice tool.

>   The tool uses a straightforward implementation of Dijsktra's algorithm
>   and may be a bit slow on extremely large meshes. As a speedup you can
>   hide the parts of the mesh that you are not working on and they will
>   not be searched.

It seems to get fairly slow on even reasonably large meshes (5k vertices).
This is time complexity working against you. There's two problems in the
code:

The first is when creating the PathEdges. You loop over all nodes edges
and then all vertices / nodes. It's probably better to store a PathNode
pointer in that eve->tmp, and store whatever is in there in the PathNode.

Extract_Min also loops over all nodes. It's best to use a priority queue /
heap for this lookup. I added BLI_heap for shortest path seam cutting
about a month ago. Allows insert/remove/extract_min all in log(n) time.

Brecht.