/*
Copyright (C) 2015-2018 Night Dive Studios, LLC.
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
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
/*
* $Source: r:/prj/cit/src/RCS/cone.c $
* $Revision: 1.48 $
* $Author: tjs $
* $Date: 1994/08/29 00:18:59 $
*/
#include
#include
#include "cone.h"
#include "map.h"
#include "fr3d.h"
#include "frparams.h"
#include "frspans.h"
#include "frflags.h"
#include "tools.h"
extern uint _fr_curflags;
#define PRINT_PYRAMID
// temp macros
#define GAME_HEIGHT (fix_make(-(1 << SLOPE_SHIFT_D), 0))
#define MAP_X (fix_make(MAP_XSIZE, 0) - fix_make(0, 1))
#define MAP_Y (fix_make(MAP_YSIZE, 0) - fix_make(0, 1))
#define FIX_ZERO (fix_make(0, 0))
#define MAX_PTS 8
#define FIX_EPSILON (0x00000010)
#define FIX_SQRT_MAX 0x005a8279
#define THREE_QUARTERS_PI ((FIXANG_PI * 3) / 4)
#define print_point(pt) (print_fix_point(pt.x, pt.y))
// Returns the z component of a cross product
#define FIX_CROSS_DIRECTION(line, point) \
(fix_mul((line.end.x - line.start.x), (point.y - line.start.y)) - \
fix_mul((point.x - line.start.x), (line.end.y - line.start.y)))
// Does a (x <= y <= z) check
//#define IN_BETWEEN(x,y,z) (((x) <= (y)) && ((y) <= (z)))
#define IN_BETWEEN(x, y, z) ((((x) <= (y)) && ((y) <= (z))) || (((x) >= (y)) && ((y) >= (z))))
typedef struct {
fix x;
fix y;
} fix_point;
typedef struct {
fix_point start;
fix_point end;
} fix_line;
// Allocation for the view cone list
fix view_cone_list[MAX_PTS * 2];
int view_count = 0;
g3s_vector main_view_vectors[4];
// wow is this ugly
extern g3s_vector viewer_position;
extern g3s_angvec viewer_orientation;
// prototypes
void reverse_poly_list(int index, fix *new_pts);
uchar clockwise_poly(int index, fix *poly_pts);
int insert_viewer_position(int index, fix *new_pts, fix_point viewer_point);
int radius_fix(int index, fix *new_pts, fix_point viewer);
void intersect_cone_sides(fix *vlist, int n, fix y_min, fix y_max, int v_left, int v_right, int v_max);
// -----------------------------------------------------
// reverse_poly_list()
//
// reverses the poly list
void reverse_poly_list(int index, fix *new_pts) {
fix temp_pts[MAX_PTS * 2];
int i;
int n;
// Copy over the raw data to the temp list
LG_memcpy(temp_pts, new_pts, sizeof(fix) * 2 * index);
// copy the data back, but in reverse order
// (fastest way????)
for (i = 0, n = (index - 1); i < index; i++, n--) {
new_pts[i * 2] = temp_pts[n * 2];
new_pts[i * 2 + 1] = temp_pts[n * 2 + 1];
}
}
// -------------------------------------------
// clockwise_poly()
//
// Returns TRUE if polygon's verticies are in clockwise order.
// Special cases: If there are less than 3 verticies, will return TRUE.
// If there are three colinear points, returns TRUE.
//
// Note: Does not handle points that are really really close together.
uchar clockwise_poly(int index, fix *poly_pts) {
fix temp_pts[MAX_PTS * 2];
fix_line poly_line;
fix_point point;
fix cross_prd;
uchar clockwise;
uchar extra_div = TRUE;
if (index < 3)
return (TRUE); // Is a point or line clockwise??? - hmmmmmm, why not?
LG_memcpy(temp_pts, poly_pts, sizeof(fix) * 2 * index);
while (extra_div) {
int i;
extra_div = FALSE;
for (i = 0; i < (index * 2); i++)
if (temp_pts[i] > FIX_SQRT_MAX) {
extra_div = TRUE;
break;
}
if (extra_div)
for (i = 0; i < (index * 2); i++)
temp_pts[i] = (temp_pts[i] > FIX_ZERO) ? temp_pts[i] >> 4 : -((fix_abs(temp_pts[i])) >> 4);
}
poly_line.start.x = temp_pts[0];
poly_line.start.y = temp_pts[1]; // fix_div(poly_pts[1], FIX_SQRT_MAX);
poly_line.end.x = temp_pts[2]; // fix_div(poly_pts[2], FIX_SQRT_MAX);
poly_line.end.y = temp_pts[3]; // fix_div(poly_pts[3], FIX_SQRT_MAX);
point.x = temp_pts[4]; // fix_div(poly_pts[4], FIX_SQRT_MAX);
point.y = temp_pts[5]; // fix_div(poly_pts[5], FIX_SQRT_MAX);
cross_prd = FIX_CROSS_DIRECTION(poly_line, point);
if (cross_prd == FIX_ZERO) {
if (index == 3) // Another Straight line - this is different though
clockwise = TRUE;
else {
point.x = temp_pts[6]; // fix_div(poly_pts[6], FIX_SQRT_MAX);
point.y = temp_pts[7]; // fix_div(poly_pts[7], FIX_SQRT_MAX);
cross_prd = FIX_CROSS_DIRECTION(poly_line, point);
if (cross_prd == FIX_ZERO) {
// Warning(("We've got a problem: Four colinear points.\n"));
clockwise = TRUE;
} else
clockwise = (cross_prd < FIX_ZERO);
}
} else
clockwise = (cross_prd < FIX_ZERO);
return (clockwise);
}
// --------------------------------------------------------------------
// insert_viewer_position()
//
// Inserts the viewer_point into the polygon, if the viewer_point does
// not lie within the polygon.
//
// Requires: verticies of polygon to be in clockwise order
int insert_viewer_position(int index, fix *new_pts, fix_point viewer_point) {
fix_line poly_line;
fix_point vpoint;
fix temp_pts[MAX_PTS * 2];
fix *current_pt;
fix cross_prd;
int i;
int insert;
uchar extra_div = TRUE;
uchar inside = FALSE;
// Reduce values to a reasonable number, so cross product is happy
// Copy over the raw data to the temp list
LG_memcpy(temp_pts, new_pts, sizeof(fix) * 2 * index);
vpoint.x = viewer_point.x;
vpoint.y = viewer_point.y;
while (extra_div) {
extra_div = FALSE;
for (i = 0; i < (index * 2); i++)
if (temp_pts[i] > FIX_SQRT_MAX) {
extra_div = TRUE;
break;
}
if ((!extra_div) && ((viewer_point.x > FIX_SQRT_MAX) || (viewer_point.y > FIX_SQRT_MAX)))
extra_div = TRUE;
if (extra_div) {
// Reduce values to a reasonable number, so cross product is happy
for (i = 0; i < (index * 2); i++)
temp_pts[i] = (temp_pts[i] > FIX_ZERO) ? temp_pts[i] >> 4 : -((fix_abs(temp_pts[i])) >> 4);
vpoint.x = (vpoint.x > FIX_ZERO) ? vpoint.x >> 4 : -((fix_abs(vpoint.x)) >> 4);
vpoint.y = (vpoint.y > FIX_ZERO) ? vpoint.y >> 4 : -((fix_abs(vpoint.y)) >> 4);
}
}
poly_line.end.x = temp_pts[(index - 1) * 2];
poly_line.end.y = temp_pts[(index - 1) * 2 + 1];
insert = index; // Represents the point being in the polygon.
for (i = 0, current_pt = temp_pts; i < index; i++) {
poly_line.start = poly_line.end;
poly_line.end.x = *(current_pt++);
poly_line.end.y = *(current_pt++);
cross_prd = FIX_CROSS_DIRECTION(poly_line, vpoint);
if (cross_prd == FIX_ZERO) {
// Do something smart about colinear stuff.
if ((IN_BETWEEN(poly_line.start.x, vpoint.x, poly_line.end.x)) &&
(IN_BETWEEN(poly_line.start.y, vpoint.y, poly_line.end.y))) {
return (index);
} else if ((IN_BETWEEN(vpoint.x, poly_line.start.x, poly_line.end.x)) &&
(IN_BETWEEN(vpoint.y, poly_line.start.y, poly_line.end.y))) {
current_pt -= 4;
*(current_pt++) = vpoint.x;
*(current_pt++) = vpoint.y;
return (index);
} else {
current_pt -= 2;
*(current_pt++) = vpoint.x;
*(current_pt++) = vpoint.y;
return (index);
}
} else if (cross_prd > FIX_ZERO) {
fix slope, inv_slope;
fix inter, inv_inter;
fix interx, intery;
uchar local_inside;
// check if we don't have to compute the intersection point
if (poly_line.end.x == poly_line.start.x) {
interx = poly_line.start.x;
intery = vpoint.y;
} else if (poly_line.end.y == poly_line.start.y) {
interx = vpoint.x;
intery = poly_line.start.y;
} else {
slope = fix_div((poly_line.end.y - poly_line.start.y), (poly_line.end.x - poly_line.start.x));
inv_slope = -fix_div(fix_make(1, 0), slope);
inter = poly_line.end.y - fix_mul(poly_line.end.x, slope);
inv_inter = vpoint.y - fix_mul(vpoint.x, inv_slope);
interx = fix_div((inter - inv_inter), (inv_slope - slope));
intery = fix_mul(slope, interx) + inter;
}
local_inside = (IN_BETWEEN(poly_line.start.x, interx, poly_line.end.x) &&
IN_BETWEEN(poly_line.start.y, intery, poly_line.end.y));
if (inside) {
if (local_inside) {
// Warning(("Outside two vectors of polygon: Insert - %d. Index - %d.\n", insert,
// i));
// Warning(("vpoint:\n"));
// warning_fix_point(vpoint.x, vpoint.y);
// Warning(("Modified Poly List:\n"));
// warning_poly_list(index, temp_pts);
// Warning(("Viewer Point:\n"));
// warning_fix_point(viewer_point.x, viewer_point.gY);
// Warning(("Original Poly List:\n"));
// warning_poly_list(index, new_pts);
// Warning(("Finding Art would probably be a very good thing!!!!\n"));
// mprintf(("View vectors:\n"));
// print_view_vectors(0, 0, 0L);
}
} else {
insert = i;
inside = local_inside;
}
}
}
if (insert != index) {
// shift data over, so we can insert the viewer point
current_pt = new_pts + (insert * 2);
LG_memmove(current_pt + 2, current_pt, sizeof(fix) * 2 * (index - insert));
*(current_pt) = viewer_point.x;
*(current_pt + 1) = viewer_point.y;
insert = index + 1;
}
return (insert);
}
// --------------------------------------------------------
// radius_fix()
//
// Takes the points and a center view point and rearranges the
// points so they are in order in a circle (counter-clockwise)
int radius_fix(int index, fix *new_pts, fix_point viewer) {
fix_line poly_line;
fix_point test_pt;
int i, j, k;
int new_index;
int counter;
uchar middle;
uchar second, third;
fix x, y, x2, y2;
fix *current_pt;
fix *insert_pt;
fix tempx, tempy;
fix temp_pts[MAX_PTS * 2];
fixang pt_ang[MAX_PTS];
fixang tempang;
fix cross_prd;
if (index > 4)
; // Warning(("Too many verticies\n"));
if (index < 3)
return (index);
// Find the ArcTans for each vertex, but also divide it by the
// larger of the two values to get values under 1. Don't normalize
// cause it's not necessary and it's expensive.
for (i = 0; i < index; i++) {
x = (new_pts[i * 2] - viewer.x);
y = (new_pts[(i * 2) + 1] - viewer.y);
if (fix_abs(y) > fix_abs(x)) {
x = fix_div(x, fix_abs(y));
y = (y < FIX_ZERO) ? fix_make(-1, 0) : fix_make(1, 0);
} else {
y = fix_div(y, fix_abs(x));
x = (x < FIX_ZERO) ? fix_make(-1, 0) : fix_make(1, 0);
}
pt_ang[i] = fix_atan2(y, x);
}
// Sort the list of angles
for (i = 1; i < index; i++) {
for (j = (index - 1); j >= i; j--) {
if (pt_ang[j - 1] > pt_ang[j]) {
k = j * 2;
tempx = new_pts[k - 2];
tempy = new_pts[k - 1];
tempang = pt_ang[j - 1];
new_pts[k - 2] = new_pts[k];
new_pts[k - 1] = new_pts[k + 1];
pt_ang[j - 1] = pt_ang[j];
new_pts[k] = tempx;
new_pts[k + 1] = tempy;
pt_ang[j] = tempang;
}
}
}
// Check for overlap
LG_memcpy(temp_pts, new_pts, sizeof(fix) * 2 * index);
for (i = 1, j = 0; i < index; i++) {
if (pt_ang[i - 1] >= FIXANG_PI)
break;
if ((pt_ang[i - 1] + THREE_QUARTERS_PI) < pt_ang[i]) {
for (j = 0; j < (index - i); j++) {
new_pts[j * 2] = temp_pts[(i + j) * 2];
new_pts[j * 2 + 1] = temp_pts[(i + j) * 2 + 1];
}
for (k = 0; k < (index - j); k++) {
new_pts[(j + k) * 2] = temp_pts[k * 2];
new_pts[(j + k) * 2 + 1] = temp_pts[k * 2 + 1];
}
break;
}
}
// Check the first pair of verticies for colinearity. (is that a word??)
current_pt = new_pts;
x = *(current_pt);
y = *(current_pt + 1);
x2 = *(current_pt + 2);
y2 = *(current_pt + 3);
new_index = 1;
insert_pt = current_pt + 2;
middle = FALSE;
if (!((x == x2) || (y == y2))) {
if (index == 3) {
// If there are 3 verticies, then we save the middle to be
// checked with the last vertex.
middle = TRUE;
current_pt += 2;
} else {
new_index++;
current_pt += 4;
insert_pt += 2;
}
} else {
// Remove colinear vertex
current_pt += 4;
}
// Check the last pair of verticies.
// If we only have three verticies, and we have already removed
// one vertex, we do not need to do the following since the last
// vertex does not belong to a pair.
// Unless of course, we did not remove a vertex, and therefore
// the middle vertex joins the last vertex as the pair.
if ((index != 3) || middle) {
x = *(current_pt);
y = *(current_pt + 1);
x2 = *(current_pt + 2);
y2 = *(current_pt + 3);
// Again, check if we have a vertex on the same axis, and punt if the
// "first" is inward of the second one(outer most).
if ((x == x2) || (y == y2)) {
// Punt the inner vertex
current_pt += 2;
*(insert_pt++) = *(current_pt++);
*(insert_pt++) = *(current_pt++);
new_index++;
} else {
for (i = 0; i < 4; i++)
*(insert_pt++) = *(current_pt++);
new_index += 2;
}
} else // We have three verticies and we removed one vertex.
{
*(insert_pt++) = *(current_pt++);
*(insert_pt++) = *(current_pt++);
new_index++;
}
if (new_index > 2) {
uchar extra_div = TRUE;
// This will remove convexness from the polygon
// We are assuming counter-clockwise, due to sorting by angles.
second = third = TRUE;
LG_memcpy(temp_pts, new_pts, sizeof(fix) * 2 * index);
// shrink down values to compensate for fix-point limitations
while (extra_div) {
extra_div = FALSE;
for (i = 0; i < (index * 2); i++)
if (temp_pts[i] > FIX_SQRT_MAX) {
extra_div = TRUE;
break;
}
if (extra_div)
for (i = 0; i < (index * 2); i++)
temp_pts[i] /= 10;
}
poly_line.start.x = temp_pts[0];
poly_line.start.y = temp_pts[1];
poly_line.end.x = temp_pts[4];
poly_line.end.y = temp_pts[5];
test_pt.x = temp_pts[2];
test_pt.y = temp_pts[3];
cross_prd = FIX_CROSS_DIRECTION(poly_line, test_pt);
if (cross_prd >= FIX_ZERO)
second = FALSE;
if (new_index == 4) {
poly_line.end.x = temp_pts[6];
poly_line.end.y = temp_pts[7];
cross_prd = FIX_CROSS_DIRECTION(poly_line, test_pt);
if (cross_prd >= FIX_ZERO)
second = FALSE;
test_pt.x = temp_pts[4];
test_pt.y = temp_pts[5];
cross_prd = FIX_CROSS_DIRECTION(poly_line, test_pt);
if (cross_prd >= FIX_ZERO)
third = FALSE;
else {
poly_line.start.x = temp_pts[2];
poly_line.start.y = temp_pts[3];
cross_prd = FIX_CROSS_DIRECTION(poly_line, test_pt);
if (cross_prd >= FIX_ZERO)
third = FALSE;
}
}
counter = (second) ? 2 : 1;
insert_pt = new_pts + (2 * counter);
if (third) {
*(insert_pt++) = new_pts[4];
*(insert_pt++) = new_pts[5];
counter++;
}
if (new_index == 4) {
*(insert_pt++) = new_pts[6];
*(insert_pt++) = new_pts[7];
counter++;
}
} else
counter = new_index;
return (counter);
}
// ----------------------------------------------------------------
// find_view_area()
//
// modifies an array of points to represents the view area in clockwise order
// *count will have the number of points in the array.
uchar find_view_area(fix *cone_list, fix floor_val, fix roof_val, int *count, fix radius) {
int i;
fix tx, tz;
fix *new_pts;
int index = 0;
fix ratiox, ratioy, ratioz;
g3s_vector my_view[4];
fix radius_square;
fix x_val;
fix z_val;
fix len;
fix *current_pt;
fix_point viewer_point;
grs_clip old_clip;
fix height = 0;
// char fix_buffer[80];
if (radius <= fix_make(0, 0)) {
*count = 0;
return (FALSE);
}
radius_square = (radius >= FIX_SQRT_MAX) ? FIX_MAX : fix_mul(radius, radius);
new_pts = cone_list;
viewer_point.x = viewer_position.gX;
viewer_point.y = viewer_position.gZ;
g3_get_view_pyramid(my_view);
if (((_fr_curflags & FR_CURVIEW_MASK) == FR_CURVIEW_STRT) && !(_fr_curflags & FR_HACKCAM_FLAG))
LG_memcpy(main_view_vectors, my_view, sizeof(g3s_vector) * 4);
// check if we're looking completely up, or completely down
// if so, we can do something fast
if ((my_view[0].gY > FIX_ZERO) && (my_view[1].gY > FIX_ZERO) && (my_view[2].gY > FIX_ZERO) &&
(my_view[3].gY > FIX_ZERO)) {
height = floor_val;
for (i = 0; i < 4; i++) {
if (my_view[i].gY < fix_make(0, 0x0080))
my_view[i].gY = fix_make(0, 0x0080);
}
} else if ((my_view[0].gY < FIX_ZERO) && (my_view[1].gY < FIX_ZERO) && (my_view[2].gY < FIX_ZERO) &&
(my_view[3].gY < FIX_ZERO)) {
height = roof_val;
for (i = 0; i < 4; i++) {
if (my_view[i].gY > -fix_make(0, 0x0080))
my_view[i].gY = -fix_make(0, 0x0080);
}
}
if (height != 0) {
index = 4;
// Find all the "raw" values without clipping
for (i = 0; i < 4; i++) {
ratioy = fix_div((height - viewer_position.gY), my_view[i].gY);
x_val = fix_mul(ratioy, my_view[i].gX);
z_val = fix_mul(ratioy, my_view[i].gZ);
if (radius_square == FIX_MAX) {
new_pts[i * 2] = viewer_position.gX + x_val;
new_pts[i * 2 + 1] = viewer_position.gZ + z_val;
} else {
// deals with fix_point limitations - must shift down so we don't square over 65536
if ((fix_abs(x_val) > FIX_SQRT_MAX) || (fix_abs(z_val) > FIX_SQRT_MAX)) {
len = fix_mul((fix_abs(x_val) >> 9), (fix_abs(x_val) >> 9)) +
fix_mul((fix_abs(z_val) >> 9), (fix_abs(z_val) >> 9));
if (len <= (radius_square >> 18)) {
new_pts[i * 2] = viewer_position.gX + x_val;
new_pts[i * 2 + 1] = viewer_position.gZ + z_val;
} else {
len = fix_sqrt(len) << 9;
new_pts[i * 2] = viewer_position.gX + fix_mul(fix_div(radius, len), x_val);
new_pts[i * 2 + 1] = viewer_position.gZ + fix_mul(fix_div(radius, len), z_val);
}
} else {
len = fix_mul(x_val, x_val) + fix_mul(z_val, z_val);
if (len <= radius_square) {
new_pts[i * 2] = viewer_position.gX + x_val;
new_pts[i * 2 + 1] = viewer_position.gZ + z_val;
} else {
len = fix_sqrt(len);
new_pts[i * 2] = viewer_position.gX +
fix_mul(fix_div(radius, len), x_val); //(fix_div(fix_mul(x_val, radius), len);
new_pts[i * 2 + 1] =
viewer_position.gZ +
fix_mul(fix_div(radius, len), z_val); // fix_div(fix_mul(z_val, radius), len);
}
}
}
}
// Make the polygon clockwise, if it isn't already
if (!clockwise_poly(index, new_pts)) {
reverse_poly_list(index, new_pts);
}
} else {
index = 4;
current_pt = new_pts;
for (i = 0; i < 4; i++) {
// Check for duplicate verticies
if ((my_view[i].gX == my_view[(i + 1) % 4].gX) && (my_view[i].gZ == my_view[(i + 1) % 4].gZ)) {
index--;
continue;
}
if (radius_square == FIX_MAX) {
// Find direction of this vector
if (my_view[i].gX < FIX_ZERO) {
tx = FIX_ZERO;
ratiox = fix_div(FIX_ZERO - viewer_position.gX, my_view[i].gX);
} else if (my_view[i].gX > FIX_ZERO) {
tx = MAP_X;
ratiox = fix_div(MAP_X - viewer_position.gX, my_view[i].gX);
} else {
tx = 0;
ratiox = FIX_MIN;
}
if (my_view[i].gZ < FIX_ZERO) {
tz = FIX_ZERO;
ratioz = fix_div(FIX_ZERO - viewer_position.gZ, my_view[i].gZ);
} else if (my_view[i].gZ > FIX_ZERO) {
tz = MAP_Y;
ratioz = fix_div(MAP_Y - viewer_position.gZ, my_view[i].gZ);
} else {
tz = 0;
ratioz = FIX_MIN;
}
if ((ratiox == FIX_MIN) && (ratioz == FIX_MIN)) {
index--;
continue;
}
if ((ratiox < FIX_ZERO) && (ratioz < FIX_ZERO)) {
if ((viewer_position.gX < MAP_X) && (viewer_position.gX > FIX_ZERO) &&
(viewer_position.gZ < MAP_Y) && (viewer_position.gZ > FIX_ZERO)) {
// Warning(("Negative Ratios for cone clip - inside the map!!!!\n"));
// print_view_vectors(0, 0L, 0);
// Warning(("Go Find Art!\n"));
}
index--;
continue;
}
if (ratiox < ratioz)
tx = viewer_position.gX + fix_mul(ratioz, my_view[i].gX);
else if (ratiox > ratioz)
tz = viewer_position.gZ + fix_mul(ratiox, my_view[i].gZ);
} else {
if (fix_abs(my_view[i].gX) > fix_abs(my_view[i].gZ)) {
tx = (my_view[i].gX < 0) ? -radius : radius;
tz = fix_mul(fix_div(tx, my_view[i].gX), my_view[i].gZ);
} else {
tz = (my_view[i].gZ < 0) ? -radius : radius;
tx = fix_mul(fix_div(tz, my_view[i].gZ), my_view[i].gX);
}
len = fix_sqrt(fix_mul(tx, tx) + fix_mul(tz, tz));
tx = viewer_position.gX + fix_mul(fix_div(radius, len), tx); // fix_div(fix_mul(tx, radius), len);
tz = viewer_position.gZ + fix_mul(fix_div(radius, len), tz); // fix_mul(tz, radius), len);
}
*(current_pt++) = tx;
*(current_pt++) = tz;
}
if (index < 2) {
WARN("%s: HEY - Only one point for cone - this is bad...", __FUNCTION__);
}
index = radius_fix(index, new_pts, viewer_point);
reverse_poly_list(index, new_pts);
}
index = insert_viewer_position(index, new_pts, viewer_point);
// Clip the polygon
old_clip.f = grd_fix_clip;
gr_set_fix_cliprect(FIX_ZERO, FIX_ZERO, MAP_X, MAP_Y);
index = gr_clip_fix_poly(index, new_pts, new_pts);
grd_fix_clip = old_clip.f;
// I don't think we need this stuff, and when it gets called - it
// causes bad things to happen!!!
// if (!clockwise_poly(index, new_pts))
// {
// reverse_poly_list(index, new_pts);
// mprintf("I guess we need this darn thing, or is it a bug????\n\n");
// }
*count = index;
if (index > 2)
return (TRUE);
else
return (FALSE);
}
// ---------------------------------------------
// intersect_cone_sides
//
fix span_lines[8];
byte span_index[2];
fix span_intersect[4];
void intersect_cone_sides(fix *vlist, int n, fix y_min, fix y_max, int v_left, int v_right, int v_max) {
fix deltax, deltay;
int s_left, s_right;
fix y;
// get the viewer's position - and take the bottom
// y = fix_trunc(viewer_position.gZ);
y = viewer_position.gZ;
if ((y_min == y) || (y_max == y)) {
if (y_max == y) {
v_left = v_right = v_max;
while (vlist[2 * ((v_left + n - 1) % n) + 1] == y_max)
v_left = (v_left + n - 1) % n;
while (vlist[2 * ((v_right + 1) % n) + 1] == y_max)
v_right = (v_right + 1) % n;
}
// do the left side
span_lines[0] = vlist[2 * ((v_left + n - 1) % n)] - vlist[2 * v_left];
span_lines[1] = vlist[2 * ((v_left + n - 1) % n) + 1] - vlist[2 * v_left + 1];
span_lines[2] = vlist[2 * ((v_left + 1) % n)] - vlist[2 * v_left];
span_lines[3] = vlist[2 * ((v_left + 1) % n) + 1] - vlist[2 * v_left + 1];
span_index[0] = -(v_left + 1);
span_intersect[0] = vlist[2 * v_left];
span_intersect[1] = vlist[2 * v_left + 1];
// do the right side
span_lines[4] = vlist[2 * ((v_right + n - 1) % n)] - vlist[2 * v_right];
span_lines[5] = vlist[2 * ((v_right + n - 1) % n) + 1] - vlist[2 * v_right + 1];
span_lines[6] = vlist[2 * ((v_right + 1) % n)] - vlist[2 * v_right];
span_lines[7] = vlist[2 * ((v_right + 1) % n) + 1] - vlist[2 * v_right + 1];
span_index[1] = -(v_right + 1);
span_intersect[2] = vlist[2 * v_right];
span_intersect[3] = vlist[2 * v_right + 1];
} else {
s_left = v_left;
s_right = v_right;
while (vlist[2 * ((s_left + 1) % n) + 1] < (y - FIX_EPSILON))
s_left = (s_left + 1) % n;
while (vlist[2 * ((s_right + n - 1) % n) + 1] < (y - FIX_EPSILON))
s_right = (s_right + n - 1) % n;
// first check if crossing is at upper point of vector
if (y == vlist[2 * ((s_left + 1) % n) + 1]) {
span_lines[0] = vlist[2 * s_left] - vlist[2 * ((s_left + 1) % n)];
span_lines[1] = vlist[2 * s_left + 1] - vlist[2 * ((s_left + 1) % n) + 1];
span_lines[2] = vlist[2 * ((s_left + 2) % n)] - vlist[2 * ((s_left + 1) % n)];
span_lines[3] = vlist[2 * ((s_left + 2) % n) + 1] - vlist[2 * ((s_left + 1) % n) + 1];
span_index[0] = -((s_left + 1) % n) - 1;
span_intersect[0] = vlist[2 * ((s_left + 1) % n)];
span_intersect[1] = vlist[2 * ((s_left + 1) % n) + 1];
} else {
// do the left side first
deltax = vlist[2 * ((s_left + 1) % n)] - vlist[2 * s_left];
deltay = vlist[2 * ((s_left + 1) % n) + 1] - vlist[2 * s_left + 1];
span_lines[0] = -deltax;
span_lines[1] = -deltay;
span_lines[2] = deltax;
span_lines[3] = deltay;
span_index[0] = s_left;
span_intersect[0] = vlist[2 * s_left] + fix_mul(fix_div((y - vlist[2 * s_left + 1]), deltay), deltax);
// fix_div(fix_mul((y-vlist[2*s_left+1]), deltax), deltay);
span_intersect[1] = y;
}
// first check if crossing is at upper point of vector
if (y == vlist[2 * ((s_right + n - 1) % n) + 1]) {
span_lines[4] = vlist[2 * ((s_right + n - 2) % n)] - vlist[2 * ((s_right + n - 1) % n)];
span_lines[5] = vlist[2 * ((s_right + n - 2) % n) + 1] - vlist[2 * ((s_right + n - 1) % n) + 1];
span_lines[6] = vlist[2 * s_right] - vlist[2 * ((s_right + n - 1) % n)];
span_lines[7] = vlist[2 * s_right + 1] - vlist[2 * ((s_right + n - 1) % n) + 1];
span_index[1] = -((s_right + n - 1) % n) - 1;
span_intersect[2] = vlist[2 * ((s_right + n - 1) % n)];
span_intersect[3] = vlist[2 * ((s_right + n - 1) % n) + 1];
} else {
// do the right side next
deltax = vlist[2 * ((s_right + n - 1) % n)] - vlist[2 * s_right];
deltay = vlist[2 * ((s_right + n - 1) % n) + 1] - vlist[2 * s_right + 1];
span_lines[4] = deltax;
span_lines[5] = deltay;
span_lines[6] = -deltax;
span_lines[7] = -deltay;
span_index[1] = (s_right + n - 1) % n;
span_intersect[2] = vlist[2 * s_right] + fix_mul(fix_div((y - vlist[2 * s_right + 1]), deltay), deltax);
// fix_div(fix_mul((y - vlist[2*s_right+1]), deltax), deltay);
span_intersect[3] = y;
}
}
}
// --------------------------------------------
// simple_cone_clip_pass()
//
// Cone clips the area, and calls store_x_span on the
// contents of the cone.
//
void simple_cone_clip_pass(void) {
int n;
int i;
byte v_min; // vertex with smallest y coord
byte v_max; // vertex with largest y coord
byte v_left, v_right; // current left & right vertices
// byte v_prev; // previous vertex
int y; // current scanline
int y_top;
fix left, right; // the left and right values on scan line, making sure scan line does not go past end points
fix y_min, y_max; // min & max vertex y coords
fix y_left, y_right; // ending y for left & right edges
fix x_min, x_max; // min & max x coords
fix x_left, x_right; // scanline x intersections
fix m_prev; // previous slopes
fix m_left = fix_make(-1, 0);
fix m_right = fix_make(1, 0); // look - slopes for right/left edges
fix d; // difference for slope computations
fix x_abs_left, x_abs_right; // min or max value of endpoint for that line of the polygon
fix x_outer_left, x_outer_right; // used to determine if that line is horizontal
fix x_shift;
uchar right_line, left_line; // looking for line
uchar right_repeat, left_repeat; // looking for repeat on the line
// get the view polygon - if there's not a valid cone, then just return.
if (!find_view_area(view_cone_list, fix_make(0, 0), GAME_HEIGHT, &n, fix_make(_frp.view.radius, 0))) {
// so if we don't have a valid cone, let's check if we're in the map first before
// spewing a warning message
if ((viewer_position.gX < MAP_X) && (viewer_position.gX > FIX_ZERO) && (viewer_position.gZ < MAP_Y) &&
(viewer_position.gZ > FIX_ZERO)) {
WARN("%s: Not a valid cone found and we're inside the map!", __FUNCTION__);
}
return;
}
view_count = n;
// initialize these to weenie values.
x_min = y_min = FIX_MAX;
x_max = y_max = 0;
// find the y coordinate of the highest and lowest vertices; save the
// vertex number of the highest.
for (i = 0; i < n; i++) {
if (view_cone_list[2 * i] < x_min)
x_min = view_cone_list[2 * i];
if (view_cone_list[2 * i] > x_max)
x_max = view_cone_list[2 * i];
if (view_cone_list[2 * i + 1] < y_min) {
y_min = view_cone_list[2 * i + 1];
v_min = i;
}
if (view_cone_list[2 * i + 1] > y_max) {
y_max = view_cone_list[2 * i + 1];
v_max = i;
}
}
// printf("y_min: %f, y_max: %f\n", fix_float(y_min), fix_float(y_max));
/* check if this is a horizontal line. */
if (fix_int(y_min) == fix_int(y_max)) {
cone_span_set(fix_int(y_min), fix_int(x_min), fix_int(x_max));
return;
}
/* we want to set v_left and v_right to be leftmost and rightmost vertices
with y = y_min. usually, both are v_min, but if there is a horizontal
edge at y = y_min, they will be different. */
v_left = v_right = v_min;
while (view_cone_list[2 * ((v_left + 1) % n) + 1] == y_min)
v_left = (v_left + 1) % n;
while (view_cone_list[2 * ((v_right + n - 1) % n) + 1] == y_min)
v_right = (v_right + n - 1) % n;
// printf("v_left: %i, v_right: %i\n", fix_float(v_left), fix_float(v_right));
intersect_cone_sides(view_cone_list, n, y_min, y_max, v_left, v_right, v_max);
// Check if top line is the max line - if so then decrement;
y_top = fix_int(y_max);
if (y_top == MAP_YSIZE)
y_top = MAP_YSIZE - 1;
/* draw each span, starting at y_min. */
for (y = fix_int(y_min); y < y_top; y++) {
/* process completed left edge(s). */
left_line = left_repeat = FALSE;
x_outer_left = fix_make(-1, 0);
while (fix_int(view_cone_list[2 * v_left + 1]) == y) {
m_prev = m_left;
x_left = view_cone_list[2 * v_left];
y_left = view_cone_list[2 * v_left + 1];
v_left = (v_left + 1) % n;
if (left_repeat) {
x_outer_left = lg_min(x_outer_left, x_left);
left_line = TRUE;
} else {
x_outer_left = x_left;
if (m_prev > fix_make(0, 0)) {
left_line = TRUE;
x_outer_left -= fix_mul(fix_frac(y_left), m_prev); // save the left point's X coordinate
}
left_repeat = TRUE; // signal that if we do this again - we've repeated
}
x_abs_left = lg_min(view_cone_list[2 * v_left], x_left);
d = view_cone_list[2 * v_left + 1] - y_left;
// if the next point is above the current - calculate the slope
if (fix_int(view_cone_list[2 * v_left + 1]) > fix_int(y_left)) {
m_left = fix_div(view_cone_list[2 * v_left] - x_left, d);
x_shift = 0;
// this gets to the leftmost point of the line - either on top or bottom of the pixel
d = (m_left < 0) ? (fix_make(1, 0) - fix_frac(y_left)) : fix_frac(y_left);
x_shift = fix_abs(fix_mul(d, m_left));
// shift over - if the line before does for any left over
if (m_prev > fix_make(0, 0)) {
d = fix_abs(fix_mul(fix_frac(y_left), m_prev));
x_shift = lg_max(d, x_shift);
}
x_left -= x_shift;
}
}
right_line = right_repeat = FALSE;
x_outer_right = fix_make(-1, 0);
/* process completed right edge(s). */
while (fix_int(view_cone_list[2 * v_right + 1]) == y) {
m_prev = m_right;
x_right = view_cone_list[2 * v_right];
y_right = view_cone_list[2 * v_right + 1];
v_right = (v_right + n - 1) % n;
if (right_repeat) {
x_outer_right = lg_max(x_outer_right, x_right);
right_line = TRUE;
} else {
x_outer_right = x_right;
if (m_prev < fix_make(0, 0)) {
x_outer_right += fix_abs(fix_mul(fix_frac(y_right), m_prev));
right_line = TRUE;
}
right_repeat = TRUE;
}
x_abs_right = lg_max(view_cone_list[2 * v_right], x_right);
d = view_cone_list[2 * v_right + 1] - y_right;
// if the next point is above the current - calculate the slope
if (fix_int(view_cone_list[2 * v_right + 1]) > fix_int(y_right)) {
m_right = fix_div(view_cone_list[2 * v_right] - x_right, d);
d = (m_right > 0) ? (fix_make(1, 0) - fix_frac(y_right)) : fix_frac(y_right);
x_shift = fix_abs(fix_mul(d, m_right));
if (m_prev < fix_make(0, 0)) {
d = fix_abs(fix_mul(fix_frac(y_right), m_prev));
x_shift = lg_max(d, x_shift);
}
x_right += x_shift;
}
}
/* draw this scanline and calculate x intersections with next. */
if (fix_int(x_left) <= fix_int(x_right)) {
left = x_left;
right = x_right;
// checking that we don't go pass the endpoints - x_abs_left
left = lg_max(x_left, x_abs_left);
right = lg_min(x_right, x_abs_right);
// checking for horizontal lines (using x_outer_left)
// if so, take the leftmost or rightmost point.
if (left_line)
left = lg_min(left, x_outer_left);
if (right_line)
right = lg_max(right, x_outer_right);
cone_span_set(y, fix_int(left), fix_int(right));
}
x_left += m_left;
x_right += m_right;
}
// This is for the top scan line - which shouldn't be done with the
// above, because we'd get just the vertex point, if we've got
// a broad angle. (kindof difficult to explain)
if (fix_int(x_left) <= fix_int(x_right)) {
// checking that we don't go pass the endpoints - x_abs_left
left = lg_max(x_left, x_abs_left);
right = lg_min(x_right, x_abs_right);
cone_span_set(y, fix_int(left), fix_int(right));
}
}