[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Stratagus-CVS] stratagus/src/video sweepline.c sweepline.h
From: |
Jimmy Salmon |
Subject: |
[Stratagus-CVS] stratagus/src/video sweepline.c sweepline.h |
Date: |
Mon, 20 Oct 2003 18:44:50 -0400 |
CVSROOT: /cvsroot/stratagus
Module name: stratagus
Branch:
Changes by: Jimmy Salmon <address@hidden> 03/10/20 18:44:50
Modified files:
src/video : sweepline.c sweepline.h
Log message:
Cleanup
Patches:
Index: stratagus/src/video/sweepline.c
diff -u stratagus/src/video/sweepline.c:1.9 stratagus/src/video/sweepline.c:1.10
--- stratagus/src/video/sweepline.c:1.9 Fri Jul 11 10:35:34 2003
+++ stratagus/src/video/sweepline.c Mon Oct 20 18:44:50 2003
@@ -9,7 +9,7 @@
// Stratagus - A free fantasy real time strategy game engine
//
/address@hidden sweepline.c - Invalidate rectangles from given marked
areas *///
-// (c) Copyright 2002 by Lutz Sammer and Stephan Rasenberg
+// (c) Copyright 2002-2003 by Lutz Sammer and Stephan Rasenberg
//
// 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
@@ -25,7 +25,7 @@
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.
//
-// $Id: sweepline.c,v 1.9 2003/07/11 14:35:34 n0body Exp $
+// $Id: sweepline.c,v 1.10 2003/10/20 22:44:50 jsalmon3 Exp $
//@{
@@ -59,7 +59,7 @@
** SWEEPLINE_MERGE pixels of another segment and than will combine them.
** @note: SWEEPLINE_MERGE>0, as SWEEPLINE_MERGE==1 will merge only
** touching segments, wich is the atleast you can do.
-**/
+*/
#define SWEEPLINE_MERGE 10
/**
@@ -96,12 +96,19 @@
** next in line to be invalidated. When the
** current sweepline y-pos >= bottomyshadow we
** have a candidate to invalidate.
-**/
+*/
typedef struct SRectangle {
- struct SRectangle *nextleft, *nextright;
- struct SRectangle *midleft, *midright, **pnode;
- struct SRectangle *bottomprv, *bottomnxt;
- int leftx, rightx, topy, bottomyshadow;
+ struct SRectangle* nextleft;
+ struct SRectangle* nextright;
+ struct SRectangle* midleft;
+ struct SRectangle* midright;
+ struct SRectangle** pnode;
+ struct SRectangle* bottomprv;
+ struct SRectangle* bottomnxt;
+ int leftx;
+ int rightx;
+ int topy;
+ int bottomyshadow;
} SRectangle;
@@ -121,8 +128,8 @@
** FIXME: this will result into a memory-leak when this mechanism is no
** longer used. But I expect this to be needed througout the program and
** so no memory is given back.
-**/
-static SRectangle *sweepline_garbage=NULL;
+*/
+local SRectangle* sweepline_garbage;
/**
** The double link-list that contains all segments ordered in which they
@@ -130,9 +137,9 @@
** firt to be invalidated and should then have current sweepline y-pos
** bigger/equal to head's bottomyshadow. The tail is used to add new
** segments to the back, so we get a FIFO-like of getting rectangles.
-**/
-static SRectangle *sweepline_bottom_head=NULL;
-static SRectangle *sweepline_bottom_tail=NULL;
+*/
+local SRectangle* sweepline_bottom_head;
+local SRectangle* sweepline_bottom_tail;
/*----------------------------------------------------------------------------
@@ -142,40 +149,47 @@
/**
** Delete a segment from all lists.. making it re-useable as garbage
** Pre: given segment should have been added with SweeplineAdd
-**/
-static void DeleteSRectangle( SRectangle *node )
+*/
+local void DeleteSRectangle(SRectangle* node)
{
-// remove from double link-list nextleft,nextright
- if ( node->nextleft )
- node->nextleft->nextright = node->nextright;
- if ( node->nextright )
- node->nextright->nextleft = node->nextleft;
-
-// remove from double link-list bottomprv,bottomnxt
- if ( node->bottomprv )
- node->bottomprv->bottomnxt = node->bottomnxt;
- else sweepline_bottom_head = node->bottomnxt;
- if ( node->bottomnxt )
- node->bottomnxt->bottomprv = node->bottomprv;
- else sweepline_bottom_tail = node->bottomprv;
-
-// remove from binary tree midleft,midright,pnode
- if ( node->midright )
- {
- *node->pnode = node->midright;
- if ( node->midleft )
- {
- SRectangle *q = node->midright;
- while ( q->midleft )
- q = q->midleft;
- q->midleft = node->midleft;
- }
- }
- else *node->pnode = node->midleft;
-
-// Add to single link-list by nextright (for memory re-use)
- node->nextright = sweepline_garbage;
- sweepline_garbage = node;
+ // remove from double link-list nextleft,nextright
+ if (node->nextleft) {
+ node->nextleft->nextright = node->nextright;
+ }
+ if (node->nextright) {
+ node->nextright->nextleft = node->nextleft;
+ }
+
+ // remove from double link-list bottomprv,bottomnxt
+ if (node->bottomprv) {
+ node->bottomprv->bottomnxt = node->bottomnxt;
+ } else {
+ sweepline_bottom_head = node->bottomnxt;
+ }
+ if (node->bottomnxt) {
+ node->bottomnxt->bottomprv = node->bottomprv;
+ } else {
+ sweepline_bottom_tail = node->bottomprv;
+ }
+
+ // remove from binary tree midleft,midright,pnode
+ if (node->midright) {
+ *node->pnode = node->midright;
+ if (node->midleft) {
+ SRectangle* q;
+ q = node->midright;
+ while (q->midleft) {
+ q = q->midleft;
+ }
+ q->midleft = node->midleft;
+ }
+ } else {
+ *node->pnode = node->midleft;
+ }
+
+ // Add to single link-list by nextright (for memory re-use)
+ node->nextright = sweepline_garbage;
+ sweepline_garbage = node;
}
/**
@@ -184,22 +198,23 @@
** (y+SWEEPLINE_MERGE) >= bottomyshadow. It will do so placing the node
** at the back again with bottomyshadow (y+SWEEPLINE_MERGE)
** Pre: given segment should have been added with SweeplineAdd
-**/
-static void UpdateRectangleBottom( SRectangle *node, int y )
+*/
+local void UpdateRectangleBottom(SRectangle* node, int y)
{
- node->bottomyshadow = y + SWEEPLINE_MERGE;
- if ( node->bottomnxt )
- {
- // remove from double link-list bottomprv,bottomnxt
- if ( node->bottomprv )
- node->bottomprv->bottomnxt = node->bottomnxt;
- else sweepline_bottom_head = node->bottomnxt;
- node->bottomnxt->bottomprv = node->bottomprv;
- // add node to the tail (to make FIFO on bottomyshadow possible)
- sweepline_bottom_tail->bottomnxt = node;
- node->bottomprv = sweepline_bottom_tail;
- node->bottomnxt = NULL;
- }
+ node->bottomyshadow = y + SWEEPLINE_MERGE;
+ if (node->bottomnxt) {
+ // remove from double link-list bottomprv,bottomnxt
+ if (node->bottomprv) {
+ node->bottomprv->bottomnxt = node->bottomnxt;
+ } else {
+ sweepline_bottom_head = node->bottomnxt;
+ }
+ node->bottomnxt->bottomprv = node->bottomprv;
+ // add node to the tail (to make FIFO on bottomyshadow possible)
+ sweepline_bottom_tail->bottomnxt = node;
+ node->bottomprv = sweepline_bottom_tail;
+ node->bottomnxt = NULL;
+ }
}
/**
@@ -219,125 +234,124 @@
**
** FIXME: prevent merging, when concerning a line consistent of a numer
** of blocks. Which would now deliver one big rectangle for a line
-**/
-void SweeplineAdd( int leftx, int rightx, int y )
+*/
+void SweeplineAdd(int leftx, int rightx, int y)
{
- static SRectangle *sweepline_root=NULL;
+ static SRectangle* sweepline_root = NULL;
+ SRectangle** pnode;
+ SRectangle* nextleft;
+ SRectangle* nextright;
+ SRectangle* node;
+ int shadowleftx;
+ int shadowrightx;
+
+#ifdef DEBUG
+ nextleft = nextright = NULL;
+#endif
+
+ DebugCheck(leftx > rightx);
+
+ shadowleftx = leftx - SWEEPLINE_MERGE;
+ shadowrightx = rightx + SWEEPLINE_MERGE;
+
+ pnode = &sweepline_root;
+ while ((node = *pnode)) {
+ if (shadowrightx < node->leftx) {
+ // given segment left of found segment --> try next left segment
+ pnode = &node->midleft;
+ nextright = node;
+ } else if (shadowleftx > node->rightx) {
+ // given segment right of found segment --> try next right segment
+ pnode = &node->midright;
+ nextleft = node;
+ } else {
+ // Handle overlap: merge and delete ununique segments
+ if (leftx < node->leftx) {
+ SRectangle* l;
+ l = node->nextleft;
+ if (l && l->rightx >= shadowleftx) {
+ // merge found segment(s) on leftside
+ SRectangle *last = l;
+ while ((l = last->nextleft) && l->rightx >= shadowleftx) {
+ DeleteSRectangle(last);
+ last = l;
+ }
+ if (last->leftx < leftx) {
+ leftx = last->leftx;
+ }
+ DeleteSRectangle(last);
+ }
+ node->leftx = leftx;
+ }
+ if (rightx > node->rightx) {
+ SRectangle* r;
+ r = node->nextright;
+ if (r && r->leftx <= shadowrightx) {
+ // merge found segment(s) on rightside
+ SRectangle* last;
+ last = r;
+ while ((r = last->nextright) && r->leftx <= shadowrightx) {
+ DeleteSRectangle(last);
+ last = r;
+ }
+ if (last->rightx > rightx) {
+ rightx = last->rightx;
+ }
+ DeleteSRectangle(last);
+ }
+ node->rightx = rightx;
+ }
+ UpdateRectangleBottom(node, y);
+ return;
+ }
+ }
- SRectangle **pnode, *nextleft, *nextright, *node;
- int shadowleftx, shadowrightx;
+ // no overlapping segment found --> create new one as leaf node
- IfDebug( nextleft=nextright=NULL);
+ // Allocate memory for garbage link-list
+ if (!sweepline_garbage) {
+ int size;
+ size = 256; // begin support for 256 rectangles at one line
+ sweepline_garbage = node = malloc(size * sizeof(SRectangle));
+ if (!node) {
+ printf("Out of memory (SweeplineAdd,video/sweepline.c)\n");
+ exit(1);
+ }
+ while (--size > 0) {
+ node->nextright = node + 1;
+ ++node;
+ }
+ node->nextright = NULL;
+ }
- DebugCheck( leftx > rightx );
+ // Take new segment from garbage link-list
+ node = *pnode = sweepline_garbage;
+ sweepline_garbage = sweepline_garbage->nextright;
+
+ // Fill in segment struct
+ node->leftx = leftx;
+ node->rightx = rightx;
+ node->topy = y;
+ UpdateRectangleBottom(node, y);
+ node->pnode = pnode;
+ node->midleft = node->midright = NULL;
+ if (nextleft) {
+ node->nextleft = nextleft;
+ nextleft->nextright = node;
+ } else {
+ node->nextleft = NULL;
+ }
+ if (nextright) {
+ node->nextright = nextright;
+ nextright->nextleft = node;
+ }
+ else {
+ node->nextright = NULL;
+ }
- shadowleftx = leftx - SWEEPLINE_MERGE;
- shadowrightx = rightx + SWEEPLINE_MERGE;
-
- pnode = &sweepline_root;
- while ( (node=*pnode) )
- {
- if ( shadowrightx < node->leftx )
- // given segment left of found segment --> try next left segment
- {
- pnode = &node->midleft;
- nextright = node;
- }
- else if ( shadowleftx > node->rightx )
- // given segment right of found segment --> try next right segment
- {
- pnode = &node->midright;
- nextleft = node;
- }
- else
- {
- // Handle overlap: merge and delete ununique segments
- if ( leftx < node->leftx )
- {
- SRectangle *l = node->nextleft;
- if ( l && l->rightx >= shadowleftx )
- { // merge found segment(s) on leftside
- SRectangle *last = l;
- while ( (l=last->nextleft) && l->rightx >= shadowleftx )
- {
- DeleteSRectangle( last );
- last = l;
- }
- if ( last->leftx < leftx )
- leftx = last->leftx;
- DeleteSRectangle( last );
- }
- node->leftx = leftx;
- }
- if ( rightx > node->rightx )
- {
- SRectangle *r = r->nextright;
- if ( r && r->leftx <= shadowrightx )
- { // merge found segment(s) on rightside
- SRectangle *last = r;
- while ( (r=last->nextright) && r->leftx <= shadowrightx )
- {
- DeleteSRectangle( last );
- last = r;
- }
- if ( last->rightx > rightx )
- rightx = last->rightx;
- DeleteSRectangle( last );
- }
- node->rightx = rightx;
- }
- UpdateRectangleBottom( node, y );
- return;
- }
- }
-
-// no overlapping segment found --> create new one as leaf node
-
- // Allocate memory for garbage link-list
- if ( !sweepline_garbage )
- {
- int size=256; // begin support for 256 rectangles at one line
- sweepline_garbage = node = malloc(size*sizeof(SRectangle));
- if ( !node )
- {
- printf( "Out of memory (SweeplineAdd,video/sweepline.c)\n" );
- exit( 1 );
- }
- while ( --size > 0 )
- {
- node->nextright = node + 1;
- node++;
- }
- node->nextright=NULL;
- }
-
- // Take new segment from garbage link-list
- node = *pnode = sweepline_garbage;
- sweepline_garbage = sweepline_garbage->nextright;
-
- // Fill in segment struct
- node->leftx = leftx;
- node->rightx = rightx;
- node->topy = y;
- UpdateRectangleBottom( node, y );
- node->pnode = pnode;
- node->midleft = node->midright = NULL;
- if ( nextleft )
- {
- node->nextleft = nextleft;
- nextleft->nextright = node;
- }
- else node->nextleft = NULL;
- if ( nextright )
- {
- node->nextright = nextright;
- nextright->nextleft = node;
- }
- else node->nextright = NULL;
-
-// FIXME: It might be good to balance the binary searchtree at this point
-// (reduces searchpath length for next insertions), but this has some cost.
-// Investigate first wether it's worth it to do on a such small tree.
+ // FIXME: It might be good to balance the binary searchtree at this point
+ // (reduces searchpath length for next insertions), but this has some cost.
+ // Investigate first wether it's worth it to do on a such small tree.
}
/**
@@ -347,33 +361,31 @@
** @note: This leaves segments which might still be 'merged' with new ones
** or are the last and need to be invalidated separetely with
** SweeplineInvalidateAll
-**/
-void SweeplineInvalidate( int y )
+*/
+void SweeplineInvalidate(int y)
{
- while ( sweepline_bottom_head &&
- sweepline_bottom_head->bottomyshadow <= y )
- {
- InvalidateArea( sweepline_bottom_head->leftx,
- sweepline_bottom_head->topy,
- sweepline_bottom_head->rightx,
- sweepline_bottom_head->bottomyshadow-SWEEPLINE_MERGE );
- DeleteSRectangle( sweepline_bottom_head );
- }
+ while (sweepline_bottom_head &&
+ sweepline_bottom_head->bottomyshadow <= y) {
+ InvalidateArea(sweepline_bottom_head->leftx,
+ sweepline_bottom_head->topy,
+ sweepline_bottom_head->rightx,
+ sweepline_bottom_head->bottomyshadow - SWEEPLINE_MERGE);
+ DeleteSRectangle(sweepline_bottom_head);
+ }
}
/**
** Invalidate all segments still available in this structure.
-**/
-void SweeplineInvalidateAll( void )
+*/
+void SweeplineInvalidateAll(void)
{
- while ( sweepline_bottom_head )
- {
- InvalidateArea( sweepline_bottom_head->leftx,
- sweepline_bottom_head->topy,
- sweepline_bottom_head->rightx,
- sweepline_bottom_head->bottomyshadow-SWEEPLINE_MERGE );
- DeleteSRectangle( sweepline_bottom_head );
- }
+ while (sweepline_bottom_head) {
+ InvalidateArea(sweepline_bottom_head->leftx,
+ sweepline_bottom_head->topy,
+ sweepline_bottom_head->rightx,
+ sweepline_bottom_head->bottomyshadow - SWEEPLINE_MERGE);
+ DeleteSRectangle(sweepline_bottom_head);
+ }
}
#endif
Index: stratagus/src/video/sweepline.h
diff -u stratagus/src/video/sweepline.h:1.6 stratagus/src/video/sweepline.h:1.7
--- stratagus/src/video/sweepline.h:1.6 Thu Jul 3 12:59:56 2003
+++ stratagus/src/video/sweepline.h Mon Oct 20 18:44:50 2003
@@ -10,7 +10,7 @@
//
/address@hidden sweepline.h - Invalidate rectangles from given marked
areas */
//
-// (c) Copyright 2002 by Lutz Sammer and Stephan Rasenberg
+// (c) Copyright 2002-2003 by Lutz Sammer and Stephan Rasenberg
//
// 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
@@ -26,7 +26,7 @@
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.
//
-// $Id: sweepline.h,v 1.6 2003/07/03 16:59:56 ingo Exp $
+// $Id: sweepline.h,v 1.7 2003/10/20 22:44:50 jsalmon3 Exp $
#ifndef __SWEEPLINE_H__
#define __SWEEPLINE_H__
@@ -40,7 +40,7 @@
/**
**
**
-**/
+*/
/*----------------------------------------------------------------------------
-- Functions
@@ -60,8 +60,8 @@
** @note: For this to work all segments should be added with an increasing
** or equal y-coordinate, to make the merge possible and ensure the
** invalidate order.
-**/
-extern void SweeplineAdd( int leftx, int rightx, int y );
+*/
+extern void SweeplineAdd(int leftx, int rightx, int y);
/**
** Invalidate all segments which exist too long (have bottomyshadow
@@ -70,13 +70,13 @@
** @note: This leaves segments which might still be 'merged' with new ones
** or are the last and need to be invalidated separetely with
** SweeplineInvalidateAll
-**/
-extern void SweeplineInvalidate( int y );
+*/
+extern void SweeplineInvalidate(int y);
/**
** Invalidate all segments still available in this structure.
-**/
-extern void SweeplineInvalidateAll( void );
+*/
+extern void SweeplineInvalidateAll(void);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Stratagus-CVS] stratagus/src/video sweepline.c sweepline.h,
Jimmy Salmon <=