Merge from Harmonic Skeleton branch

This code adds a basic and simple skeleton generator.

Examples and links are in the wiki, docs will come eventually: http://wiki.blender.org/index.php/User:Theeth/skeletor

In a nutshell, select a vertex at the top of the head and press "Generate Skeleton". UI Panel is in the Editing buttons in Edit Mode, tooltips and semi-useful.

3 files changed, 133 insertions, 2 deletions

diff --git a/source/blender/include/BIF_editarmature.h b/source/blender/include/BIF_editarmature.h
index 903c663e5f3..31a5cc2ec4c 100644
--- a/source/blender/include/BIF_editarmature.h
+++ b/source/blender/include/BIF_editarmature.h
@@ -101,6 +101,8 @@ void	make_trans_bones (char mode);
 
 int		do_pose_selectbuffer(struct Base *base, unsigned int *buffer, short hits);
 
+void generateSkeleton(void);
+
 void	mouse_armature(void);
 void	remake_editArmature(void);
 void	selectconnected_armature(void);
@@ -117,8 +119,8 @@ void	hide_selected_pose_bones(void);
 void	hide_unselected_pose_bones(void);
 void	show_all_pose_bones(void);
 
-int		bone_looper(Object *ob, struct Bone *bone, void *data,
-				int (*bone_func)(Object *, struct Bone *, void *));
+int		bone_looper(struct Object *ob, struct Bone *bone, void *data,
+				int (*bone_func)(struct Object *, struct Bone *, void *));
 
 void	undo_push_armature(char *name);
 void	armature_bone_rename(struct bArmature *arm, char *oldname, char *newname);
diff --git a/source/blender/include/butspace.h b/source/blender/include/butspace.h
index debac14f63e..5029c88fba7 100644
--- a/source/blender/include/butspace.h
+++ b/source/blender/include/butspace.h
@@ -420,6 +420,8 @@ void curvemap_buttons(struct uiBlock *block, struct CurveMapping *cumap, char la
 #define B_SETTFACE_RND		2082
 #define B_SETMCOL_RND		2083
 
+#define B_GEN_SKELETON		2090
+
 /* *********************** */
 #define B_VGROUPBUTS		2100
 
diff --git a/source/blender/include/reeb.h b/source/blender/include/reeb.h
new file mode 100644
index 00000000000..c8352aedec5
--- /dev/null
+++ b/source/blender/include/reeb.h
@@ -0,0 +1,127 @@
+/**
+ * $Id: 
+ *
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * Contributor(s): Martin Poirier
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+ 
+#ifndef REEB_H_
+#define REEB_H_
+
+#include "DNA_listBase.h"
+
+struct EdgeHash;
+struct ReebArc;
+struct ReebEdge;
+struct ReebNode;
+
+typedef struct ReebGraph {
+	ListBase arcs;
+	ListBase nodes;
+	int totnodes;
+	struct EdgeHash *emap;
+} ReebGraph;
+
+typedef struct EmbedBucket {
+	float val;
+	int	  nv;
+	float p[3];
+} EmbedBucket;
+
+typedef struct ReebNode {
+	struct ReebNode *next, *prev;
+	struct ReebArc **arcs;
+	int index;
+	int degree;
+	float weight;
+	float p[3];
+	int flags;
+} ReebNode;
+
+typedef struct ReebEdge {
+	struct ReebEdge *next, *prev;
+	struct ReebArc  *arc;
+	struct ReebNode *v1, *v2;
+	struct ReebEdge *nextEdge;
+} ReebEdge;
+
+typedef struct ReebArc {
+	struct ReebArc *next, *prev;
+	ListBase edges;
+	struct ReebNode *v1, *v2;
+	struct EmbedBucket *buckets;
+	int	bcount;
+	int flags;
+} ReebArc;
+
+typedef struct ReebArcIterator {
+	struct ReebArc	*arc;
+	int index;
+	int start;
+	int end;
+	int stride;
+} ReebArcIterator;
+
+struct EditMesh;
+
+int weightToHarmonic(struct EditMesh *em);
+int weightFromDistance(struct EditMesh *em);
+int weightFromLoc(struct EditMesh *me, int axis);
+void weightToVCol(struct EditMesh *em);
+void renormalizeWeight(struct EditMesh *em, float newmax);
+
+ReebGraph * generateReebGraph(struct EditMesh *me, int subdivisions);
+void freeGraph(ReebGraph *rg);
+void exportGraph(ReebGraph *rg, int count);
+
+#define OTHER_NODE(arc, node) ((arc->v1 == node) ? arc->v2 : arc->v1)
+
+void initArcIterator(struct ReebArcIterator *iter, struct ReebArc *arc, struct ReebNode *head);
+void initArcIterator2(struct ReebArcIterator *iter, struct ReebArc *arc, int start, int end);
+struct EmbedBucket * nextBucket(struct ReebArcIterator *iter);
+
+/* Filtering */
+void filterNullReebGraph(ReebGraph *rg);
+int filterExternalReebGraph(ReebGraph *rg, float threshold);
+int filterInternalReebGraph(ReebGraph *rg, float threshold);
+
+/* Post-Build processing */
+void repositionNodes(ReebGraph *rg);
+void postprocessGraph(ReebGraph *rg, char mode);
+void removeNormalNodes(ReebGraph *rg);
+
+/* Graph processing */
+void buildAdjacencyList(ReebGraph *rg);
+
+void sortNodes(ReebGraph *rg);
+void sortArcs(ReebGraph *rg);
+
+int subtreeDepth(ReebNode *node, ReebArc *rootArc);
+int countConnectedArcs(ReebGraph *rg, ReebNode *node);
+int hasAdjacencyList(ReebGraph *rg); 
+int	isGraphCyclic(ReebGraph *rg);
+
+/* Sanity check */
+void verifyBuckets(ReebGraph *rg);
+
+#endif /*REEB_H_*/