Delaunay cleanup: Added bucket allocator, more robust trigonometry, coding style
diff --git a/Source/geom.c b/Source/geom.c
index 4c49d58..84d9ca8 100755
--- a/Source/geom.c
+++ b/Source/geom.c
@@ -264,11 +264,16 @@
/*
Calculate the angle between v1-v2 and v1-v0
*/
-TESSreal calcAngle(TESSvertex *v0, TESSvertex *v1, TESSvertex *v2) {
+TESSreal calcAngle( TESSvertex *v0, TESSvertex *v1, TESSvertex *v2 )
+{
TESSreal a[2] = { v2->s - v1->s, v2->t - v1->t };
TESSreal b[2] = { v0->s - v1->s, v0->t - v1->t };
- return acosf((a[0] * b[0] + a[1] * b[1]) /
- (sqrt(a[0] * a[0] + a[1] * a[1]) * sqrt(b[0] * b[0] + b[1] * b[1])));
+ TESSreal num = a[0] * b[0] + a[1] * b[1];
+ TESSreal den = sqrt( a[0] * a[0] + a[1] * a[1] ) * sqrt( b[0] * b[0] + b[1] * b[1] );
+ if ( den > 0.0 ) num /= den;
+ if ( num < -1.0 ) num = -1.0;
+ if ( num > 1.0 ) num = 1.0;
+ return acos( num );
}
/*
diff --git a/Source/mesh.c b/Source/mesh.c
index 1b0ff9e..20c52ff 100755
--- a/Source/mesh.c
+++ b/Source/mesh.c
@@ -750,8 +750,6 @@
return 1;
}
-#include <stdio.h>
-
void tessMeshFlipEdge( TESSmesh *mesh, TESShalfEdge *edge )
{
assert(EdgeIsInternal(edge));
@@ -779,8 +777,8 @@
b0->Onext = a1->Sym;
a2->Onext = b0;
b2->Onext = a0;
- b1->Onext = a2->Sym;
- a1->Onext = b2->Sym;
+ b1->Onext = a2->Sym;
+ a1->Onext = b2->Sym;
a0->Lnext = a2;
a2->Lnext = b1;
diff --git a/Source/tess.c b/Source/tess.c
index e1d3b63..fa1639c 100755
--- a/Source/tess.c
+++ b/Source/tess.c
@@ -385,41 +385,53 @@
}
+typedef struct EdgeStackNode EdgeStackNode;
+typedef struct EdgeStack EdgeStack;
+
struct EdgeStackNode {
TESShalfEdge *edge;
- struct EdgeStackNode *next;
+ EdgeStackNode *next;
};
struct EdgeStack {
- struct EdgeStackNode *top;
+ EdgeStackNode *top;
+ struct BucketAlloc *nodeBucket;
};
-void stackInit(struct EdgeStack *stack)
+int stackInit( EdgeStack *stack, TESSalloc *alloc )
{
- stack->top = NULL;
+ stack->top = NULL;
+ stack->nodeBucket = createBucketAlloc( alloc, "CDT nodes", sizeof(EdgeStackNode), 512 );
+ return stack->nodeBucket != NULL;
}
-int stackEmpty(struct EdgeStack *stack)
+void stackDelete( EdgeStack *stack )
+{
+ deleteBucketAlloc( stack->nodeBucket );
+}
+
+int stackEmpty( EdgeStack *stack )
{
return stack->top == NULL;
}
-void stackPush(struct EdgeStack *stack, TESShalfEdge *e)
+void stackPush( EdgeStack *stack, TESShalfEdge *e )
{
- struct EdgeStackNode *node = malloc(sizeof(struct EdgeStackNode));
+ EdgeStackNode *node = (EdgeStackNode *)bucketAlloc( stack->nodeBucket );
+ if ( ! node ) return;
node->edge = e;
node->next = stack->top;
stack->top = node;
}
-TESShalfEdge *stackPop(struct EdgeStack *stack)
+TESShalfEdge *stackPop( EdgeStack *stack )
{
- TESShalfEdge *e = NULL;
- struct EdgeStackNode *node = stack->top;
+ TESShalfEdge *e = NULL;
+ EdgeStackNode *node = stack->top;
if (node) {
stack->top = node->next;
e = node->edge;
- free(node);
+ bucketFree( stack->nodeBucket, node );
}
return e;
}
@@ -428,7 +440,7 @@
Starting with a valid triangulation, uses the Edge Flip algorithm to
refine the triangulation into a Constrained Delaunay Triangulation.
*/
-int tessMeshRefineDelaunay( TESSmesh *mesh )
+int tessMeshRefineDelaunay( TESSmesh *mesh, TESSalloc *alloc )
{
/* At this point, we have a valid, but not optimal, triangulation.
We refine the triangulation using the Edge Flip algorithm */
@@ -439,8 +451,8 @@
3) insert all dual edges into a queue
*/
TESSface *f;
- struct EdgeStack stack;
- stackInit(&stack);
+ EdgeStack stack;
+ stackInit(&stack, alloc);
TESShalfEdge *e;
TESShalfEdge *edges[4];
for( f = mesh->fHead.next; f != &mesh->fHead; f = f->next ) {
@@ -453,7 +465,7 @@
} while (e != f->anEdge);
}
}
-
+
// Pop stack until we find a reversed edge
// Flip the reversed edge, and insert any of the four opposite edges
// which are internal and not already in the stack (!marked)
@@ -475,6 +487,8 @@
}
}
}
+
+ stackDelete(&stack);
return 1;
}
@@ -1020,7 +1034,7 @@
} else {
rc = tessMeshTessellateInterior( mesh );
if (elementType == TESS_CONSTRAINED_DELAUNAY_TRIANGLES) {
- rc = tessMeshRefineDelaunay( mesh );
+ rc = tessMeshRefineDelaunay( mesh, &tess->alloc );
elementType = TESS_POLYGONS;
polySize = 3;
}
