1/*
2Copyright (C) 1996-1997 Id Software, Inc.
3
4This program is free software; you can redistribute it and/or
5modify it under the terms of the GNU General Public License
6as published by the Free Software Foundation; either version 2
7of the License, or (at your option) any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13See the GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License
16along with this program; if not, write to the Free Software
17Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19*/
20#include "quakedef.h"
21
22static	hull_t		box_hull;
23static	dclipnode_t	box_clipnodes[6];
24static	mplane_t	box_planes[6];
25
26extern	vec3_t player_mins;
27extern	vec3_t player_maxs;
28
29/*
30===================
31PM_InitBoxHull
32
33Set up the planes and clipnodes so that the six floats of a bounding box
34can just be stored out and get a proper hull_t structure.
35===================
36*/
37void PM_InitBoxHull (void)
38{
39	int		i;
40	int		side;
41
42	box_hull.clipnodes = box_clipnodes;
43	box_hull.planes = box_planes;
44	box_hull.firstclipnode = 0;
45	box_hull.lastclipnode = 5;
46
47	for (i=0 ; i<6 ; i++)
48	{
49		box_clipnodes[i].planenum = i;
50
51		side = i&1;
52
53		box_clipnodes[i].children[side] = CONTENTS_EMPTY;
54		if (i != 5)
55			box_clipnodes[i].children[side^1] = i + 1;
56		else
57			box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
58
59		box_planes[i].type = i>>1;
60		box_planes[i].normal[i>>1] = 1;
61	}
62
63}
64
65
66/*
67===================
68PM_HullForBox
69
70To keep everything totally uniform, bounding boxes are turned into small
71BSP trees instead of being compared directly.
72===================
73*/
74hull_t	*PM_HullForBox (vec3_t mins, vec3_t maxs)
75{
76	box_planes[0].dist = maxs[0];
77	box_planes[1].dist = mins[0];
78	box_planes[2].dist = maxs[1];
79	box_planes[3].dist = mins[1];
80	box_planes[4].dist = maxs[2];
81	box_planes[5].dist = mins[2];
82
83	return &box_hull;
84}
85
86
87/*
88==================
89PM_HullPointContents
90
91==================
92*/
93int PM_HullPointContents (hull_t *hull, int num, vec3_t p)
94{
95	float		d;
96	dclipnode_t	*node;
97	mplane_t	*plane;
98
99	while (num >= 0)
100	{
101		if (num < hull->firstclipnode || num > hull->lastclipnode)
102			Sys_Error ("PM_HullPointContents: bad node number");
103
104		node = hull->clipnodes + num;
105		plane = hull->planes + node->planenum;
106
107		if (plane->type < 3)
108			d = p[plane->type] - plane->dist;
109		else
110			d = DotProduct (plane->normal, p) - plane->dist;
111		if (d < 0)
112			num = node->children[1];
113		else
114			num = node->children[0];
115	}
116
117	return num;
118}
119
120/*
121==================
122PM_PointContents
123
124==================
125*/
126int PM_PointContents (vec3_t p)
127{
128	float		d;
129	dclipnode_t	*node;
130	mplane_t	*plane;
131	hull_t		*hull;
132	int			num;
133
134	hull = &pmove.physents[0].model->hulls[0];
135
136	num = hull->firstclipnode;
137
138	while (num >= 0)
139	{
140		if (num < hull->firstclipnode || num > hull->lastclipnode)
141			Sys_Error ("PM_HullPointContents: bad node number");
142
143		node = hull->clipnodes + num;
144		plane = hull->planes + node->planenum;
145
146		if (plane->type < 3)
147			d = p[plane->type] - plane->dist;
148		else
149			d = DotProduct (plane->normal, p) - plane->dist;
150		if (d < 0)
151			num = node->children[1];
152		else
153			num = node->children[0];
154	}
155
156	return num;
157}
158
159/*
160===============================================================================
161
162LINE TESTING IN HULLS
163
164===============================================================================
165*/
166
167// 1/32 epsilon to keep floating point happy
168#define	DIST_EPSILON	(0.03125)
169
170/*
171==================
172PM_RecursiveHullCheck
173
174==================
175*/
176qboolean PM_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, pmtrace_t *trace)
177{
178	dclipnode_t	*node;
179	mplane_t	*plane;
180	float		t1, t2;
181	float		frac;
182	int			i;
183	vec3_t		mid;
184	int			side;
185	float		midf;
186
187// check for empty
188	if (num < 0)
189	{
190		if (num != CONTENTS_SOLID)
191		{
192			trace->allsolid = false;
193			if (num == CONTENTS_EMPTY)
194				trace->inopen = true;
195			else
196				trace->inwater = true;
197		}
198		else
199			trace->startsolid = true;
200		return true;		// empty
201	}
202
203	if (num < hull->firstclipnode || num > hull->lastclipnode)
204		Sys_Error ("PM_RecursiveHullCheck: bad node number");
205
206//
207// find the point distances
208//
209	node = hull->clipnodes + num;
210	plane = hull->planes + node->planenum;
211
212	if (plane->type < 3)
213	{
214		t1 = p1[plane->type] - plane->dist;
215		t2 = p2[plane->type] - plane->dist;
216	}
217	else
218	{
219		t1 = DotProduct (plane->normal, p1) - plane->dist;
220		t2 = DotProduct (plane->normal, p2) - plane->dist;
221	}
222
223#if 1
224	if (t1 >= 0 && t2 >= 0)
225		return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
226	if (t1 < 0 && t2 < 0)
227		return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
228#else
229	if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
230		return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
231	if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
232		return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
233#endif
234
235// put the crosspoint DIST_EPSILON pixels on the near side
236	if (t1 < 0)
237		frac = (t1 + DIST_EPSILON)/(t1-t2);
238	else
239		frac = (t1 - DIST_EPSILON)/(t1-t2);
240	if (frac < 0)
241		frac = 0;
242	if (frac > 1)
243		frac = 1;
244
245	midf = p1f + (p2f - p1f)*frac;
246	for (i=0 ; i<3 ; i++)
247		mid[i] = p1[i] + frac*(p2[i] - p1[i]);
248
249	side = (t1 < 0);
250
251// move up to the node
252	if (!PM_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
253		return false;
254
255#ifdef PARANOID
256	if (PM_HullPointContents (pm_hullmodel, mid, node->children[side])
257	== CONTENTS_SOLID)
258	{
259		Con_Printf ("mid PointInHullSolid\n");
260		return false;
261	}
262#endif
263
264	if (PM_HullPointContents (hull, node->children[side^1], mid)
265	!= CONTENTS_SOLID)
266// go past the node
267		return PM_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
268
269	if (trace->allsolid)
270		return false;		// never got out of the solid area
271
272//==================
273// the other side of the node is solid, this is the impact point
274//==================
275	if (!side)
276	{
277		VectorCopy (plane->normal, trace->plane.normal);
278		trace->plane.dist = plane->dist;
279	}
280	else
281	{
282		VectorSubtract (vec3_origin, plane->normal, trace->plane.normal);
283		trace->plane.dist = -plane->dist;
284	}
285
286	while (PM_HullPointContents (hull, hull->firstclipnode, mid)
287	== CONTENTS_SOLID)
288	{ // shouldn't really happen, but does occasionally
289		frac -= 0.1;
290		if (frac < 0)
291		{
292			trace->fraction = midf;
293			VectorCopy (mid, trace->endpos);
294			Con_DPrintf ("backup past 0\n");
295			return false;
296		}
297		midf = p1f + (p2f - p1f)*frac;
298		for (i=0 ; i<3 ; i++)
299			mid[i] = p1[i] + frac*(p2[i] - p1[i]);
300	}
301
302	trace->fraction = midf;
303	VectorCopy (mid, trace->endpos);
304
305	return false;
306}
307
308
309/*
310================
311PM_TestPlayerPosition
312
313Returns false if the given player position is not valid (in solid)
314================
315*/
316qboolean PM_TestPlayerPosition (vec3_t pos)
317{
318	int			i;
319	physent_t	*pe;
320	vec3_t		mins, maxs, test;
321	hull_t		*hull;
322
323	for (i=0 ; i< pmove.numphysent ; i++)
324	{
325		pe = &pmove.physents[i];
326	// get the clipping hull
327		if (pe->model)
328			hull = &pmove.physents[i].model->hulls[1];
329		else
330		{
331			VectorSubtract (pe->mins, player_maxs, mins);
332			VectorSubtract (pe->maxs, player_mins, maxs);
333			hull = PM_HullForBox (mins, maxs);
334		}
335
336		VectorSubtract (pos, pe->origin, test);
337
338		if (PM_HullPointContents (hull, hull->firstclipnode, test) == CONTENTS_SOLID)
339			return false;
340	}
341
342	return true;
343}
344
345/*
346================
347PM_PlayerMove
348================
349*/
350pmtrace_t PM_PlayerMove (vec3_t start, vec3_t end)
351{
352	pmtrace_t		trace, total;
353	vec3_t		offset;
354	vec3_t		start_l, end_l;
355	hull_t		*hull;
356	int			i;
357	physent_t	*pe;
358	vec3_t		mins, maxs;
359
360// fill in a default trace
361	memset (&total, 0, sizeof(pmtrace_t));
362	total.fraction = 1;
363	total.ent = -1;
364	VectorCopy (end, total.endpos);
365
366	for (i=0 ; i< pmove.numphysent ; i++)
367	{
368		pe = &pmove.physents[i];
369	// get the clipping hull
370		if (pe->model)
371			hull = &pmove.physents[i].model->hulls[1];
372		else
373		{
374			VectorSubtract (pe->mins, player_maxs, mins);
375			VectorSubtract (pe->maxs, player_mins, maxs);
376			hull = PM_HullForBox (mins, maxs);
377		}
378
379	// PM_HullForEntity (ent, mins, maxs, offset);
380	VectorCopy (pe->origin, offset);
381
382		VectorSubtract (start, offset, start_l);
383		VectorSubtract (end, offset, end_l);
384
385	// fill in a default trace
386		memset (&trace, 0, sizeof(pmtrace_t));
387		trace.fraction = 1;
388		trace.allsolid = true;
389//		trace.startsolid = true;
390		VectorCopy (end, trace.endpos);
391
392	// trace a line through the apropriate clipping hull
393		PM_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);
394
395		if (trace.allsolid)
396			trace.startsolid = true;
397		if (trace.startsolid)
398			trace.fraction = 0;
399
400	// did we clip the move?
401		if (trace.fraction < total.fraction)
402		{
403			// fix trace up by the offset
404			VectorAdd (trace.endpos, offset, trace.endpos);
405			total = trace;
406			total.ent = i;
407		}
408
409	}
410
411	return total;
412}
413
414
415