/*
* The port of 'lines_intersect' (from Graphics Gems II) is failing on the
* Vectrex. Unfortunately this is a critical component of the Planarity game.
*
* By using the same random number generator and the same size of data objects,
* the vectrex and linux compilations of this program generate identical pairs
* of lines. By selecting a pair where the result (intersection detection) is
* visibly incorrect, we can compare the steps in the calculation and determine
* where the error is.
*/
#ifdef LINUX
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdint.h>
#else
#define uint8_t unsigned int
#define int8_t int
#define int16_t long
#define int32_t long long
#include <vectrex.h>
#define NULL 0
#endif
#ifndef TRUE
#define TRUE (0==0)
#define FALSE (0!=0)
#endif
#ifdef LINUX
static void drawline(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, int dashed) {
if (dashed) fprintf(stderr, "Intersecting ");
fprintf(stderr, "line from (%d,%d) to (%d,%d)\n", x1,y1, x2,y2);
}
#else
static unsigned int dotmask = 0xC3;
#define DRAWING_SCALE 0x80
#define CROSSHAIR_SCALE 0x40
#define set_scale(s) do { VIA_t1_cnt_lo = s; } while (0)
static unsigned char patList[2];
static void drawline_patterned(int y, int x, unsigned char pat)
{
patList[0]=(unsigned char)y;
patList[1]=(unsigned char)x;
*(volatile unsigned char *)0xC829 = pat;
*(volatile unsigned char *)0xC823 =0;
Draw_Pat_VL(patList);
}
static void drawline(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, int dashed) {
long ax1, ay1, dx, dy;
ax1 = ((long)x1-128L); ay1 = ((long)y1-128L);
dx = ((long)x2-(long)x1); dy = ((long)y2-(long)y1);
Reset0Ref(); set_scale(DRAWING_SCALE); Intensity_5F();
Moveto_d((int)ay1,(int)ax1);
// id dx is 255, it splits into 127 and 128 - which causes a problem because +128 is not possible
if (dy == 255 || dx == 255) {
// 255-unit long lines are split in three, all others are split in two.
drawline_patterned((int)(dy/3L), (int)(dx/3L), (dashed ? dotmask : 0xFF));
dy -= dy/3L; dx -= dx/3L;
}
if (dy < -128L || dy > 127L || dx < -128L || dx > 127L) {
drawline_patterned((int)(dy>>1L), (int)(dx>>1L), (dashed ? dotmask : 0xFF));
// don't care which way it rounds (>>1 or /2) because this picks up the odd bit:
dy -= dy>>1L; dx -= dx>>1L;
}
drawline_patterned((int)dy, (int)dx, (dashed ? dotmask : 0xFF));
}
#endif
static char debug_buffer[64];
void debug_int32(int y, int x, char *var, int32_t i) {
#ifdef LINUX
fprintf(stderr, "%s: %d\n", var, i);
#else
char *s = debug_buffer, *startpos, *endpos;
(void)y; (void)x;
while (*var != '\0') {
char c;
c = *var++;
*s++ = c;
}
*s++ = ':'; *s++ = ' ';
if (i < 0) *s++ = '-'; else i = -i;
startpos = s;
for (;;) {
int32_t j = i / ((typeof(i))(10));
char digit = (char)(i - j*((typeof(i))(10)));
*s++ = '0'-digit;
i = j;
if (i == 0) break;
}
endpos = s-1;
//reverse(startpos, s);
while (startpos < endpos) {
char t = *startpos;
*startpos = *endpos;
*endpos = t;
startpos += 1; endpos -= 1;
}
*s++ = 0x80;
*s = '\0';
Reset0Ref(); set_scale(DRAWING_SCALE); Intensity_5F();
Print_Str_d(y, x, debug_buffer);
#endif
}
void debug_uint8(int y, int x, char *var, uint8_t i) {
#ifdef LINUX
fprintf(stderr, "%s: %d\n", var, i);
#else
debug_int32(y, x, var, (int32_t)i);
#endif
}
void debug_int8(int y, int x, char *var, int8_t i) {
#ifdef LINUX
fprintf(stderr, "%s: %d\n", var, i);
#else
debug_int32(y, x, var, (int32_t)i);
#endif
}
void debug_int16(int y, int x, char *var, int16_t i) {
#ifdef LINUX
fprintf(stderr, "%s: %d\n", var, i);
#else
debug_int32(y, x, var, (int32_t)i);
#endif
}
static uint8_t _x, _a, _b, _c;
static void initRandom8(unsigned int s1,unsigned int s2,unsigned int s3, unsigned int x0) {
_x = x0; _a = s1; _b = s2; _c = s3; _x++; _a = (_a^_c^_x); _b = (_b+_a); _c = ((_c+(_b>>1))^_a);
}
static uint8_t random8(void) { // assert returns unsigned value that fits in an int.
_x++; _a = (_a^_c^_x); _b = (_b+_a); _c = ((_c+(_b>>1))^_a);
return _c;
}
/* lines_intersect: AUTHOR: Mukesh Prasad, from Graphics Gems II
*
* This function computes whether two line segments,
* respectively joining the input points (x1,y1) -- (x2,y2)
* and the input points (x3,y3) -- (x4,y4) intersect.
* If the lines intersect, the output variables x, y are
* set to coordinates of the point of intersection.
*
* All values are in integers. The returned value is rounded
* to the nearest integer point.
*
* If non-integral grid points are relevant, the function
* can easily be transformed by substituting floating point
* calculations instead of integer calculations.
*
* Entry
* x1, y1, x2, y2 Coordinates of endpoints of one segment.
* x3, y3, x4, y4 Coordinates of endpoints of other segment.
*
* Exit
* x, y Coordinates of intersection point.
*
* The value returned by the function is one of:
*
* DONT_INTERSECT 0
* DO_INTERSECT 1
* COLLINEAR 2
*
* Error conditions:
*
* Depending upon the possible ranges, and particularly on 16-bit
* computers, care should be taken to protect from overflow.
*
* In the following code, 'long' values have been used for this
* purpose, instead of 'int'.
*
*/
// I (gt) believe I have modified this correctly for gcc6809's "-mint8" environment,
// but the end of the game is not being detected which would imply that this call
// is failing. Looks like a job for the debugger...
#define DONT_INTERSECT 0
#define DO_INTERSECT 1
#define COLLINEAR 2
/**************************************************************
* *
* NOTE: The following macro to determine if two numbers *
* have the same sign, is for 2's complement number *
* representation. It will need to be modified for other *
* number systems. *
* *
**************************************************************/
static int lines_intersect(int16_t x1, int16_t y1, /* First line segment */
int16_t x2, int16_t y2,
int16_t x3, int16_t y3, /* Second line segment */
int16_t x4, int16_t y4) {
int16_t b1, b2;
int32_t a1, a2, c1, c2; /* Coefficients of line eqns. */
int32_t r1, r2, r3, r4; /* 'Sign' values */
int32_t denom; /* Intermediate values */
// no apparent change in cycles regardless of which macro is used:
//#define SAME_SIGNS( a, b ) (((a)^(b)) >= 0)
#define SAME_SIGNS( a, b ) ((((a)<0) && ((b)<0)) || (((a)>=0) && ((b)>=0)))
/* Compute a1, b1, c1, where line joining points 1 and 2
* is "a1 x + b1 y + c1 = 0".
*/
a1 = y2 - y1; //debug_int32(120, -120, "A1", a1);
b1 = x1 - x2; //debug_int16(108, -120, "B1", b1);
c1 = (int32_t)x2 * (int32_t)y1 - (int32_t)x1 * (int32_t)y2; //debug_int32( 96, -120, "C1", c1);
/* Compute r3 and r4. */
r3 = ((int32_t)a1 * (int32_t)x3) + ((int32_t)b1 * (int32_t)y3) + (int32_t)c1; //debug_int32( 84, -120, "R3", r3);
r4 = ((int32_t)a1 * (int32_t)x4) + ((int32_t)b1 * (int32_t)y4) + (int32_t)c1; //debug_int32( 72, -120, "R4", r4);
/* Check signs of r3 and r4. If both point 3 and point 4 lie on
* same side of line 1, the line segments do not intersect.
*/
if ( r3 != 0 &&
r4 != 0 &&
SAME_SIGNS( r3, r4 ))
return ( DONT_INTERSECT );
/* Compute a2, b2, c2 */
a2 = y4 - y3; debug_int32( 64, -120, "A2", a2);
b2 = x3 - x4; debug_int16( 52, -120, "B2", b2);
c2 = (int32_t)x4 * (int32_t)y3 - (int32_t)x3 * (int32_t)y4; debug_int32( 40, -120, "C2", c2);
/* Compute r1 and r2 */
r1 = (a2 * (int32_t)x1) + ((int32_t)b2 * (int32_t)y1) + (int32_t)c2; debug_int32( 28, -120, "R1", r1);
r2 = (a2 * (int32_t)x2) + ((int32_t)b2 * (int32_t)y2) + (int32_t)c2; debug_int32( 16, -120, "R2", r2);
/* Check signs of r1 and r2. If both point 1 and point 2 lie
* on same side of second line segment, the line segments do
* not intersect.
*/
if ( r1 != 0 &&
r2 != 0 &&
SAME_SIGNS( r1, r2 ))
return ( DONT_INTERSECT );
/* Line segments intersect: compute intersection point. */
denom = a1 * b2 - a2 * b1;
if ( denom == 0 )
return ( COLLINEAR );
return ( DO_INTERSECT ); /* lines_intersect */
#undef SAME_SIGNS
}
int main(void) {
uint8_t x1,y1,x2,y2,x3,y3,x4,y4;
int new_data_wanted = TRUE;
uint8_t LineNo = 0;
uint8_t PrevBtnState = 0;
#ifdef LINUX
debug_int32(0,0,"Test", 0);
debug_int32(0,0,"Test", 2);
debug_int32(0,0,"Test", 23);
debug_int32(0,0,"Test", 32767);
debug_int32(0,0,"Test", 32768);
debug_int32(0,0,"Test", 0x7FFFFFFF);
debug_int32(0,0,"Test", -2);
debug_int32(0,0,"Test", -23);
debug_int32(0,0,"Test", -32767);
debug_int32(0,0,"Test", -32768);
debug_int32(0,0,"Test", ((int32_t)0x80000000));
#endif
initRandom8(1,2,3,123);
#ifndef LINUX
Wait_Recal();
Read_Btns();
#endif
debug_buffer[0] = 0x80; debug_buffer[1] = '\0';
for (;;) {
int Crosses;
if (new_data_wanted) {
LineNo += 1;
x1 = random8(); y1 = random8();
x2 = random8(); y2 = random8();
x3 = random8(); y3 = random8();
x4 = random8(); y4 = random8();
new_data_wanted = FALSE;
}
debug_uint8(-120, -40, "LINE", LineNo);
Crosses = lines_intersect(x1,y1,x2,y2,x3,y3,x4,y4) == DO_INTERSECT;
drawline(x1, y1, x2, y2, Crosses);
drawline(x3, y3, x4, y4, Crosses);
#ifdef LINUX
{
int c;
char *s = debug_buffer;
while ((*s&0x7f) != '\0') {fputc(*s, stderr); s += 1; }
fprintf(stderr, "\nNext>");
for (;;) {
c = fgetc(stdin);
if (c == EOF) exit(0);
if ((c == 'y')||(c == 'j')) new_data_wanted = TRUE; /*i18n ;-) */
if (c == '\n' && new_data_wanted) break;
if (c == '\n') fprintf(stderr, "Next>");
}
new_data_wanted = TRUE;
}
#else
if ((Vec_Btn_State&~PrevBtnState)&1) { // edge only
new_data_wanted = TRUE;
}
PrevBtnState = Vec_Btn_State;
Wait_Recal();
Read_Btns();
#endif
}
return 0;
}