home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Deathday Collection
/
dday.bin
/
edit
/
bspwin
/
picknode.c
< prev
next >
Wrap
C/C++ Source or Header
|
1994-05-24
|
7KB
|
213 lines
/*- PICKNODE.C --------------------------------------------------------------*
To be able to divide the nodes down, this routine must decide which is the
best Seg to use as a nodeline. It does this by selecting the line with least
splits and has least difference of Segs on either side of it.
Credit to Raphael Quinet and DEU, this routine is a copy of the nodeline
picker used in DEU5beta. I am using this method because the method I
originally used was not so good.
(Some stuff was optimized, check out 'picknode.old' for original code - Alex.)
*---------------------------------------------------------------------------*/
#include "prottype.h"
struct Seg *PickNode(struct Seg *ts)
{
int num_splits,num_left,num_right;
int min_splits,min_diff,val;
struct Seg *part,*check,*best;
int max,new,grade = 0,bestgrade = 32767,seg_count;
// min_splits = 32767;
// min_diff = 32767;
best = ts; /* Set best to first (failsafe measure)*/
for(part=ts;part;part = part->next) /* Use each Seg as partition*/
{
progress(); /* Something for the user to look at.*/
psx = vertices[part->start].x; /* Calculate this here, cos it doesn't*/
psy = vertices[part->start].y; /* change for all the interations of*/
pex = vertices[part->end].x; /* the inner loop!*/
pey = vertices[part->end].y;
pdx = psx - pex; /* Partition line DX,DY*/
pdy = psy - pey;
num_splits = 0;
num_left = 0;
num_right = 0;
seg_count = 0;
for(check=ts;check;check=check->next) /* Check partition against all Segs*/
{
seg_count++;
if(check == part) num_right++; /* If same as partition, inc right count*/
else
{
lsx = vertices[check->start].x; /* Calculate this here, cos it doesn't*/
lsy = vertices[check->start].y; /* change for all the interations of*/
lex = vertices[check->end].x; /* the inner loop!*/
ley = vertices[check->end].y;
val = DoLinesIntersect(); /* get state of lines relation to each other*/
if((val&2 && val&64) || (val&4 && val&32))
{
num_splits++; /* If line is split, inc splits*/
num_left++; /* and add one line into both*/
num_right++; /* sides*/
}
else
{
if(val&1 && val&16) /* If line is totally in same*/
{ /* direction*/
if(check->flip == part->flip) num_right++;
else num_left++; /* add to side according to flip*/
}
else /* So, now decide which side*/
{ /* the line is on*/
if(val&34) num_left++; /* and inc the appropriate*/
if(val&68) num_right++; /* count*/
}
}
}
// if(num_splits > min_splits) break; /* If more splits than last, reject*/
}
if(num_right > 0 && num_left > 0) /* Make sure at least one Seg is*/
{ /* on either side of the partition*/
max = max(num_right,num_left);
new = (num_right + num_left) - seg_count;
grade = max+new*8;
if(grade < bestgrade)
{
bestgrade = grade;
best = part; /* and remember which Seg*/
}
}
}
return best; /* all finished, return best Seg*/
}
/*---------------------------------------------------------------------------*
Because this is used a horrendous amount of times in the inner loops, the
coordinate of the lines are setup outside of the routine in global variables
psx,psy,pex,pey = partition line coordinates
lsx,lsy,lex,ley = checking line coordinates
The routine returns 'val' which has 3 bits assigned to the the start and 3
to the end. These allow a decent evaluation of the lines state.
bit 0,1,2 = checking lines starting point and bits 4,5,6 = end point
these bits mean 0,4 = point is on the same line
1,5 = point is to the left of the line
2,6 = point is to the right of the line
There are some failsafes in here, these mainly check for small errors in the
side checker.
( I made some changes here to eliminate sqrt() functions - Alex)
*---------------------------------------------------------------------------*/
int DoLinesIntersect()
{
short int x,y,val = 0;
long dx2,dy2,dx3,dy3,a,b;
dx2 = psx - lsx; /* Checking line -> partition*/
dy2 = psy - lsy;
dx3 = psx - lex;
dy3 = psy - ley;
a = pdy*dx2 - pdx*dy2;
b = pdy*dx3 - pdx*dy3;
if((a<0 && b>0) || (a>0 && b<0)) /* Line is split, just check that*/
{
ComputeIntersection(&x,&y);
dx2 = lsx - x; /* Find distance from line start*/
dy2 = lsy - y; /* to split point*/
if(dx2 == 0 && dy2 == 0) a = 0;
else
if( dx2*dx2 + dy2*dy2 < 4) a = 0;
/* If either ends of the split */
/* are smaller than 2 pixs then */
/* assume this starts on part line*/
dx3 = lex - x; /* Find distance from line end*/
dy3 = ley - y; /* to split point*/
if(dx3 == 0 && dy3 == 0) b = 0;
else
if ( dx3*dx3 + dy3*dy3 < 4) b = 0;
}
if(a == 0) val = val | 16; /* start is on middle*/
if(a < 0) val = val | 32; /* start is on left side*/
if(a > 0) val = val | 64; /* start is on right side*/
if(b == 0) val = val | 1; /* end is on middle*/
if(b < 0) val = val | 2; /* end is on left side*/
if(b > 0) val = val | 4; /* end is on right side*/
return val;
}
/*---------------------------------------------------------------------------*
Calculate the point of intersection of two lines. ps?->pe? & ls?->le?
returns int xcoord, int ycoord
( Profiling revealed that this was most time-consuming routine here
so I rewrote it completly and new one is more than 2 times faster
than previous (w/o coprocessor) - Alex)
*---------------------------------------------------------------------------*/
void _fastcall ComputeIntersection(short int *outx,short int *outy)
{
/* Now, algorithm is based on solving the system of 2 linear equaltions of
given lines - Alex*/
double X,Y, a1,b1,a2;
long dx1,dy1,dx2,dy2;
dx1 = (long)pex - psx;
dy1 = (long)pey - psy;
dx2 = (long)lex - lsx;
dy2 = (long)ley - lsy;
if( (!dx1 && !dy1) || (!dx2 && !dy2) )
ProgError("Invalid line encountered");
if( !dx1 && !dy2) { *outx = psx; *outy = lsy; return; }
if( !dy1 && !dx2) { *outx = lsx; *outy = psy; return; }
if( !dx1 || !dx2)
{
a1 = (double)((long)pex-psx)/((long)pey-psy);
a2 = (double)((long)lex-lsx)/((long)ley-lsy);
if( a1 == a2 ) { *outx = lsx; *outy = lsy; return; }
b1 = psx - a1*psy;
X = (lsx - a2*lsy - b1)/(a1-a2);
Y = a1*X + b1;
*outx = (int)(Y + ((Y<0)?-0.5:0.5));
*outy = (int)(X + ((X<0)?-0.5:0.5));
}
else
{
a1 = (double)((long)pey-psy)/((long)pex-psx);
a2 = (double)((long)ley-lsy)/((long)lex-lsx);
if( a1 == a2 ) { *outx = lsx; *outy = lsy; return; }
b1 = psy - a1*psx;
X = (lsy - a2*lsx - b1)/(a1-a2);
Y = a1*X + b1;
*outx = (short int)(X + ((X<0)?-0.5:0.5));
*outy = (short int)(Y + ((Y<0)?-0.5:0.5));
}
}
/*--------------------------------------------------------------------------*/