[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15417] branches/harmonic-skeleton/source/ blender: Reeb Graph Copy procedures, for multi resolution filtering
Martin Poirier
theeth at yahoo.com
Thu Jul 3 19:52:32 CEST 2008
Revision: 15417
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15417
Author: theeth
Date: 2008-07-03 19:51:19 +0200 (Thu, 03 Jul 2008)
Log Message:
-----------
Reeb Graph Copy procedures, for multi resolution filtering
Modified Paths:
--------------
branches/harmonic-skeleton/source/blender/include/reeb.h
branches/harmonic-skeleton/source/blender/src/reeb.c
Modified: branches/harmonic-skeleton/source/blender/include/reeb.h
===================================================================
--- branches/harmonic-skeleton/source/blender/include/reeb.h 2008-07-03 16:32:19 UTC (rev 15416)
+++ branches/harmonic-skeleton/source/blender/include/reeb.h 2008-07-03 17:51:19 UTC (rev 15417)
@@ -101,6 +101,7 @@
struct GHash *faces;
float angle;
+ struct ReebArc *link; /* for multi resolution filtering, points to higher levels */
} ReebArc;
typedef struct ReebArcIterator {
Modified: branches/harmonic-skeleton/source/blender/src/reeb.c
===================================================================
--- branches/harmonic-skeleton/source/blender/src/reeb.c 2008-07-03 16:32:19 UTC (rev 15416)
+++ branches/harmonic-skeleton/source/blender/src/reeb.c 2008-07-03 17:51:19 UTC (rev 15417)
@@ -103,179 +103,177 @@
void REEB_AxialSymmetry(BNode* root_node, BNode* node1, BNode* node2, struct BArc* barc1, BArc* barc2);
-/***************************************** BUCKET UTILS **********************************************/
+/***************************************** UTILS **********************************************/
-void addVertToBucket(EmbedBucket *b, float co[3])
+void REEB_freeArc(BArc *barc)
{
- b->nv++;
- VecLerpf(b->p, b->p, co, 1.0f / b->nv);
+ ReebArc *arc = (ReebArc*)barc;
+ BLI_freelistN(&arc->edges);
+
+ if (arc->buckets)
+ MEM_freeN(arc->buckets);
+
+ if (arc->faces)
+ BLI_ghash_free(arc->faces, NULL, NULL);
+
+ MEM_freeN(arc);
}
-void removeVertFromBucket(EmbedBucket *b, float co[3])
+void REEB_freeGraph(ReebGraph *rg)
{
- VecMulf(b->p, (float)b->nv);
- VecSubf(b->p, b->p, co);
- b->nv--;
- VecMulf(b->p, 1.0f / (float)b->nv);
-}
-
-void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
-{
- if (bDst->nv > 0 && bSrc->nv > 0)
+ ReebArc *arc;
+ ReebNode *node;
+
+ // free nodes
+ for( node = rg->nodes.first; node; node = node->next )
{
- bDst->nv += bSrc->nv;
- VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
+ // Free adjacency lists
+ if (node->arcs != NULL)
+ {
+ MEM_freeN(node->arcs);
+ }
}
- else if (bSrc->nv > 0)
+ BLI_freelistN(&rg->nodes);
+
+ // free arcs
+ arc = rg->arcs.first;
+ while( arc )
{
- bDst->nv = bSrc->nv;
- VECCOPY(bDst->p, bSrc->p);
+ ReebArc *next = arc->next;
+ REEB_freeArc((BArc*)arc);
+ arc = next;
}
+
+ // free edge map
+ BLI_edgehash_free(rg->emap, NULL);
+
+ MEM_freeN(rg);
}
-void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end)
+ReebGraph * newReebGraph()
{
- if (aDst->bcount > 0 && aSrc->bcount > 0)
- {
- int indexDst = 0, indexSrc = 0;
-
- start = MAX3(start, aDst->buckets[0].val, aSrc->buckets[0].val);
-
- while(indexDst < aDst->bcount && aDst->buckets[indexDst].val < start)
- {
- indexDst++;
- }
-
- while(indexSrc < aSrc->bcount && aSrc->buckets[indexSrc].val < start)
- {
- indexSrc++;
- }
-
- for( ; indexDst < aDst->bcount &&
- indexSrc < aSrc->bcount &&
- aDst->buckets[indexDst].val <= end &&
- aSrc->buckets[indexSrc].val <= end
-
- ; indexDst++, indexSrc++)
- {
- mergeBuckets(aDst->buckets + indexDst, aSrc->buckets + indexSrc);
- }
- }
+ ReebGraph *rg;
+ rg = MEM_callocN(sizeof(ReebGraph), "reeb graph");
+
+ rg->totnodes = 0;
+ rg->emap = BLI_edgehash_new();
+
+
+ rg->free_arc = REEB_freeArc;
+ rg->free_node = NULL;
+ rg->radial_symmetry = REEB_RadialSymmetry;
+ rg->axial_symmetry = REEB_AxialSymmetry;
+
+ return rg;
}
-void flipArcBuckets(ReebArc *arc)
+ReebNode * addNode(ReebGraph *rg, EditVert *eve, float weight)
{
- int i, j;
+ ReebNode *node = NULL;
- for (i = 0, j = arc->bcount - 1; i < j; i++, j--)
- {
- EmbedBucket tmp;
-
- tmp = arc->buckets[i];
- arc->buckets[i] = arc->buckets[j];
- arc->buckets[j] = tmp;
- }
+ node = MEM_callocN(sizeof(ReebNode), "reeb node");
+
+ node->flag = 0; // clear flag on init
+ node->symmetry_level = 0;
+ node->arcs = NULL;
+ node->degree = 0;
+ node->weight = weight;
+ node->index = rg->totnodes;
+ VECCOPY(node->p, eve->co);
+
+ BLI_addtail(&rg->nodes, node);
+ rg->totnodes++;
+
+ return node;
}
-void allocArcBuckets(ReebArc *arc)
+ReebNode * copyNode(ReebGraph *rg, ReebNode *node)
{
- int i;
- float start = ceil(((ReebNode*)arc->head)->weight);
- arc->bcount = (int)(floor(((ReebNode*)arc->tail)->weight) - start) + 1;
+ ReebNode *cp_node = NULL;
- if (arc->bcount > 0)
- {
- arc->buckets = MEM_callocN(sizeof(EmbedBucket) * arc->bcount, "embed bucket");
-
- for(i = 0; i < arc->bcount; i++)
- {
- arc->buckets[i].val = start + i;
- }
- }
- else
- {
- arc->buckets = NULL;
- }
+ cp_node = MEM_callocN(sizeof(ReebNode), "reeb node copy");
+ memcpy(cp_node, node, sizeof(ReebNode));
+
+ cp_node->prev = NULL;
+ cp_node->next = NULL;
+ cp_node->arcs = NULL;
+
+ BLI_addtail(&rg->nodes, cp_node);
+ rg->totnodes++;
+
+ return cp_node;
}
-void resizeArcBuckets(ReebArc *arc)
+ReebArc * copyArc(ReebGraph *rg, ReebArc *arc)
{
- EmbedBucket *oldBuckets = arc->buckets;
- int oldBCount = arc->bcount;
+ ReebArc *cp_arc;
+ ReebNode *node;
- allocArcBuckets(arc);
+ cp_arc = MEM_callocN(sizeof(ReebArc), "reeb arc copy");
+
+ memcpy(cp_arc, arc, sizeof(ReebArc));
- if (oldBCount != 0 && arc->bcount != 0)
+ cp_arc->link = arc;
+
+ cp_arc->head = NULL;
+ cp_arc->tail = NULL;
+
+ cp_arc->prev = NULL;
+ cp_arc->next = NULL;
+
+ cp_arc->edges.first = NULL;
+ cp_arc->edges.last = NULL;
+
+ /* copy buckets */
+ cp_arc->buckets = MEM_callocN(sizeof(EmbedBucket) * cp_arc->bcount, "embed bucket");
+ memcpy(cp_arc->buckets, arc->buckets, sizeof(EmbedBucket) * cp_arc->bcount);
+
+ /* copy faces map */
+ cp_arc->faces = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
+ mergeArcFaces(rg, cp_arc, arc);
+
+ /* find corresponding head and tail */
+ for (node = rg->nodes.first; node && (cp_arc->head == NULL || cp_arc->tail == NULL); node = node->next)
{
- int oldStart = (int)oldBuckets[0].val;
- int oldEnd = (int)oldBuckets[oldBCount - 1].val;
- int newStart = (int)arc->buckets[0].val;
- int newEnd = (int)arc->buckets[arc->bcount - 1].val;
- int oldOffset = 0;
- int newOffset = 0;
- int len;
-
- if (oldStart < newStart)
+ if (node->index == arc->head->index)
{
- oldOffset = newStart - oldStart;
+ cp_arc->head = node;
}
- else
+ else if (node->index == arc->tail->index)
{
- newOffset = oldStart - newStart;
+ cp_arc->tail = node;
}
-
- len = MIN2(oldEnd - (oldStart + oldOffset) + 1, newEnd - (newStart - newOffset) + 1);
-
- memcpy(arc->buckets + newOffset, oldBuckets + oldOffset, len * sizeof(EmbedBucket));
}
-
- if (oldBuckets != NULL)
- {
- MEM_freeN(oldBuckets);
- }
+
+ BLI_addtail(&rg->arcs, cp_arc);
+
+ return cp_arc;
}
-void calculateArcLength(ReebArc *arc)
+ReebGraph * copyReebGraph(ReebGraph *rg)
{
- ReebArcIterator iter;
- EmbedBucket *bucket = NULL;
- float *vec0, *vec1;
+ ReebNode *node;
+ ReebArc *arc;
+ ReebGraph *cp_rg = newReebGraph();
- arc->length = 0;
-
- initArcIterator(&iter, arc, arc->head);
-
- bucket = nextBucket(&iter);
-
- vec0 = arc->head->p;
- vec1 = arc->head->p; /* in case there's no embedding */
-
- while (bucket != NULL)
+ /* Copy nodes */
+ for (node = rg->nodes.first; node; node = node->next)
{
- vec1 = bucket->p;
-
- arc->length += VecLenf(vec0, vec1);
-
- vec0 = vec1;
- bucket = nextBucket(&iter);
+ copyNode(cp_rg, node);
}
- arc->length += VecLenf(arc->tail->p, vec1);
-}
-
-void calculateGraphLength(ReebGraph *rg)
-{
- ReebArc *arc;
-
+ /* Copy arcs */
for (arc = rg->arcs.first; arc; arc = arc->next)
{
- calculateArcLength(arc);
+ copyArc(cp_rg, arc);
}
+
+ BLI_rebuildAdjacencyList((BGraph*)cp_rg);
+
+ return cp_rg;
}
-/***************************************** UTILS **********************************************/
-
ReebEdge * copyEdge(ReebEdge *edge)
{
ReebEdge *newEdge = NULL;
@@ -301,51 +299,6 @@
}
}
-void REEB_freeArc(BArc *barc)
-{
- ReebArc *arc = (ReebArc*)barc;
- BLI_freelistN(&arc->edges);
-
- if (arc->buckets)
- MEM_freeN(arc->buckets);
-
- if (arc->faces)
- BLI_ghash_free(arc->faces, NULL, NULL);
-
- MEM_freeN(arc);
-}
-
-void REEB_freeGraph(ReebGraph *rg)
-{
- ReebArc *arc;
- ReebNode *node;
-
- // free nodes
- for( node = rg->nodes.first; node; node = node->next )
- {
- // Free adjacency lists
- if (node->arcs != NULL)
- {
- MEM_freeN(node->arcs);
- }
- }
- BLI_freelistN(&rg->nodes);
-
- // free arcs
- arc = rg->arcs.first;
- while( arc )
- {
- ReebArc *next = arc->next;
- REEB_freeArc((BArc*)arc);
- arc = next;
- }
-
- // free edge map
- BLI_edgehash_free(rg->emap, NULL);
-
- MEM_freeN(rg);
-}
-
void NodeDegreeDecrement(ReebGraph *rg, ReebNode *node)
{
node->degree--;
@@ -471,6 +424,177 @@
#endif
}
+/***************************************** BUCKET UTILS **********************************************/
+
+void addVertToBucket(EmbedBucket *b, float co[3])
+{
+ b->nv++;
+ VecLerpf(b->p, b->p, co, 1.0f / b->nv);
+}
+
+void removeVertFromBucket(EmbedBucket *b, float co[3])
+{
+ VecMulf(b->p, (float)b->nv);
+ VecSubf(b->p, b->p, co);
+ b->nv--;
+ VecMulf(b->p, 1.0f / (float)b->nv);
+}
+
+void mergeBuckets(EmbedBucket *bDst, EmbedBucket *bSrc)
+{
+ if (bDst->nv > 0 && bSrc->nv > 0)
+ {
+ bDst->nv += bSrc->nv;
+ VecLerpf(bDst->p, bDst->p, bSrc->p, (float)bSrc->nv / (float)(bDst->nv));
+ }
+ else if (bSrc->nv > 0)
+ {
+ bDst->nv = bSrc->nv;
+ VECCOPY(bDst->p, bSrc->p);
+ }
+}
+
+void mergeArcBuckets(ReebArc *aDst, ReebArc *aSrc, float start, float end)
+{
+ if (aDst->bcount > 0 && aSrc->bcount > 0)
+ {
+ int indexDst = 0, indexSrc = 0;
+
+ start = MAX3(start, aDst->buckets[0].val, aSrc->buckets[0].val);
+
+ while(indexDst < aDst->bcount && aDst->buckets[indexDst].val < start)
+ {
+ indexDst++;
+ }
+
+ while(indexSrc < aSrc->bcount && aSrc->buckets[indexSrc].val < start)
+ {
+ indexSrc++;
+ }
+
+ for( ; indexDst < aDst->bcount &&
+ indexSrc < aSrc->bcount &&
+ aDst->buckets[indexDst].val <= end &&
+ aSrc->buckets[indexSrc].val <= end
+
+ ; indexDst++, indexSrc++)
+ {
+ mergeBuckets(aDst->buckets + indexDst, aSrc->buckets + indexSrc);
+ }
+ }
+}
+
+void flipArcBuckets(ReebArc *arc)
+{
+ int i, j;
+
+ for (i = 0, j = arc->bcount - 1; i < j; i++, j--)
+ {
+ EmbedBucket tmp;
+
+ tmp = arc->buckets[i];
+ arc->buckets[i] = arc->buckets[j];
+ arc->buckets[j] = tmp;
+ }
+}
+
+void allocArcBuckets(ReebArc *arc)
+{
+ int i;
+ float start = ceil(((ReebNode*)arc->head)->weight);
+ arc->bcount = (int)(floor(((ReebNode*)arc->tail)->weight) - start) + 1;
+
+ if (arc->bcount > 0)
+ {
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list