2 * Copyright (C) Volition, Inc. 1999. All rights reserved.
4 * All source code herein is the property of Volition, Inc. You may not sell
5 * or otherwise commercially exploit the source or things you created based on
10 * $Logfile: /Freespace2/code/Math/Fvi.h $
15 * Prototypes for fvi stuff
18 * Revision 1.2 2002/06/09 04:41:13 relnev
19 * added copyright header
21 * Revision 1.1.1.1 2002/05/03 03:28:12 root
25 * 5 8/16/99 8:19a Andsager
26 * Add project_point_onto_bbox() to fvi and include in aicode
28 * 4 3/08/99 7:03p Dave
29 * First run of new object update system. Looks very promising.
31 * 3 11/13/98 11:10a Andsager
32 * Add fvi_two_lines_in_3space() - returns closest point of intersection
34 * 2 10/07/98 10:53a Dave
37 * 1 10/07/98 10:49a Dave
39 * 16 1/12/98 9:20p Andsager
40 * Modify calling procedure to fvi_sphere_plane.
42 * 15 10/19/97 9:42p Andsager
43 * add fvi_sphere_plane to header
45 * 14 10/19/97 9:28p Andsager
46 * removed local function from header
48 * 13 10/17/97 1:21a Andsager
49 * add new function to check sphere-polgon edge collision
51 * 12 10/03/97 5:06p Andsager
52 * added sphere polygon intersection code
54 * 11 9/28/97 2:16p Andsager
55 * added fvi_moving_sphere_intersect_plane
57 * 10 4/01/97 1:03p John
58 * Changed fvi_ray_plane to take a dir, not two points.
60 * 9 3/26/97 10:48a Hoffoss
61 * JAS: Added fvi_ray_sphere
63 * 8 3/24/97 3:55p John
64 * renamed fvi functions so rays and segments aren't confusing.
66 * 7 3/24/97 3:26p John
67 * Cleaned up and restructured model_collide code and fvi code. In fvi
68 * made code that finds uvs work.. Added bm_get_pixel to BmpMan.
70 * 6 2/17/97 5:18p John
71 * Added a bunch of RCS headers to a bunch of old files that don't have
83 // fvi functions - fvi stands for Find Vector Intersection
84 // fvi_a_b - means find the intersection of something of type a with something of type b
86 // ray: a line from p0 through p1 extending to inifinity
87 // segment: a line from p0 stopping at p1
88 // sphere, point, face
90 //--------------------------------------------------------------------
91 // fvi_ray_plane - Finds the point on the specified plane where the
92 // infinite ray intersects.
94 // Returns scaled-distance plane is from the ray_origin (t), so
95 // P = O + t*D, where P is the point of intersection, O is the ray origin,
96 // and D is the ray's direction. So 0.0 would mean the intersection is
97 // exactly on the ray origin, 1.0 would be on the ray origin plus the ray
98 // direction vector, anything negative would be behind the ray's origin.
99 // If you pass a pointer to the new_pnt, this routine will perform the P=
100 // calculation to calculate the point of intersection and put the result
103 // If radius is anything other than 0.0, it assumes you want the intersection
104 // point to be that radius from the plane.
106 // Note that ray_direction doesn't have to be normalized unless you want
107 // the return value to be in units from the ray origin.
109 // Also note that new_pnt will always be filled in to some valid value,
110 // even if it is a point at infinity.
112 // If the plane and line are parallel, this will return the largest
113 // negative float number possible.
115 // So if you want to check a line segment from p0 to p1, you would pass
116 // p0 as ray_origin, p1-p0 as the ray_direction, and there would be an
117 // intersection if the return value is between 0 and 1.
119 float fvi_ray_plane(vector *new_pnt,
120 vector *plane_pnt,vector *plane_norm, // Plane description, a point and a normal
121 vector *ray_origin,vector *ray_direction, // Ray description, a point and a direction
125 //find the point on the specified plane where the line segment intersects
126 //returns true if point found, false if line parallel to plane
127 //new_pnt is the found point on the plane
128 //plane_pnt & plane_norm describe the plane
129 //p0 & p1 are the ends of the line
130 int fvi_segment_plane(vector *new_pnt, vector *plane_pnt, vector *plane_norm, vector *p0, vector *p1, float rad);
134 // see if a point in inside a face by projecting into 2d. Also
135 // Finds uv's if uvls is not NULL. Returns 0 if point isn't on
136 // face, non-zero otherwise.
137 // From Graphics Gems I, "An efficient Ray-Polygon intersection", p390
138 // checkp - The point to check
139 // nv - how many verts in the poly
140 // verts - the vertives for the polygon
141 // norm1 - the polygon's normal
142 // u_out,vout - if not null and v_out not null and uvls not_null and point is on face, the uv's of where it hit
143 // uvls - a list of uv pairs for each vertex
144 // This replaces the old check_point_to_face & find_hitpoint_uv
145 int fvi_point_face(vector *checkp, int nv, vector **verts, vector * norm1, float *u_out, float *v_out, uv_pair * uvls );
148 //maybe this routine should just return the distance and let the caller
149 //decide it it's close enough to hit
150 //determine if and where a vector intersects with a sphere
151 //vector defined by p0,p1
152 //returns 1 if intersects, and fills in intp
154 int fvi_segment_sphere(vector *intp, vector *p0, vector *p1, vector *sphere_pos, float sphere_rad);
156 //determine if and where a ray intersects with a sphere
157 //vector defined by p0,p1
158 //returns 1 if intersects, and fills in intp
160 int fvi_ray_sphere(vector *intp, vector *p0, vector *p1, vector *sphere_pos, float sphere_rad);
163 //==============================================================
164 // Finds intersection of a ray and an axis-aligned bounding box
165 // Given a ray with origin at p0, and direction pdir, this function
166 // returns non-zero if that ray intersects an axis-aligned bounding box
167 // from min to max. If there was an intersection, then hitpt will contain
168 // the point where the ray begins inside the box.
169 // Fast ray-box intersection taken from Graphics Gems I, pages 395,736.
170 int fvi_ray_boundingbox( vector *min, vector *max, vector * p0, vector *pdir, vector *hitpt );
172 // sphere polygon collision prototypes
174 // Given a polygon vertex list and a moving sphere, find the first contact the sphere makes with the edge, if any
175 int fvi_polyedge_sphereline(vector *hit_point, vector *xs0, vector *vs, float Rs, int nv, vector **verts, float *hit_time);
177 int fvi_sphere_plane(vector *intersect_point, vector *sphere_center_start, vector *sphere_velocity, float sphere_radius,
178 vector *plane_normal, vector *plane_point, float *hit_time, float *delta_time);
180 // finds the point of intersection between two lines or the closest points if lines do not intersect
181 // closest points - line 1: p1 + v1 * s, line 2: p2 + v2 * t
182 // p1 - point on line 1
183 // v1 - vector direction of line 1
184 // p2 - point on line 2
185 // v2 - vector direction of line 2
186 // s - parameter of intersection of line 1
187 // t - parameter of intersection of line 2
188 void fvi_two_lines_in_3space(vector *p1, vector *v1, vector *p2, vector *v2, float *s, float *t);
190 // vector mins - minimum extents of bbox
191 // vector maxs - maximum extents of bbox
192 // vector start - point in bbox reference frame
193 // vector box_pt - point in bbox reference frame.
194 // NOTE: if a coordinate of start is *inside* the bbox, it is *not* moved to surface of bbox
195 // return: 1 if inside, 0 otherwise.
196 int project_point_onto_bbox(vector *mins, vector *maxs, vector *start, vector *box_pt);