1 /*
2
3 Copyright (C) 1991-2001 and beyond by Bungie Studios, Inc.
4 and the "Aleph One" developers.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 This license is contained in the file "COPYING",
17 which is included with this source code; it is available online at
18 http://www.gnu.org/licenses/gpl.html
19
20 Rendering Clipping/Rasterization Class
21 by Loren Petrich,
22 August 7, 2000
23
24 Contains the calculation of clipping and rasterization; from render.c
25
26 Made [view_data *view] a member and removed it as an argument
27 Also removed [bitmap_definition *destination] as superfluous,
28 now that there is a special rasterizer object that can contain it.
29
30 Sep 2, 2000 (Loren Petrich):
31 Added some idiot-proofing, since the shapes accessor now returns NULL for nonexistent bitmaps
32
33 If a polygon has a "full_side" texture, and there is another polgyon on the other side,
34 then suppress the void for the boundary's texture.
35 */
36
37 #include "cseries.h"
38
39 #include "map.h"
40 #include "lightsource.h"
41 #include "media.h"
42 #include "RenderRasterize.h"
43 #include "AnimatedTextures.h"
44 #include "OGL_Setup.h"
45 #include "preferences.h"
46 #include "screen.h"
47 #include "platforms.h"
48
49 #include <string.h>
50
51
52 /* maximum number of vertices a polygon can be world-clipped into (one per clip line) */
53 #define MAXIMUM_VERTICES_PER_WORLD_POLYGON (MAXIMUM_VERTICES_PER_POLYGON+4)
54
55
RenderRasterizerClass()56 RenderRasterizerClass::RenderRasterizerClass():
57 view(NULL), // Idiot-proofing
58 RSPtr(NULL),
59 RasPtr(NULL)
60 {}
61
62
63 /* ---------- rendering the tree */
64
render_tree()65 void RenderRasterizerClass::render_tree()
66 {
67 render_tree(kDiffuse);
68 }
69
render_tree(RenderStep renderStep)70 void RenderRasterizerClass::render_tree(RenderStep renderStep)
71 {
72 assert(view); // Idiot-proofing
73 assert(RSPtr);
74 assert(RasPtr);
75 vector<sorted_node_data>::iterator node;
76 // LP: reference to simplify the code
77 vector<sorted_node_data>& SortedNodes = RSPtr->SortedNodes;
78
79 // LP change: added support for semitransparent liquids
80 bool SeeThruLiquids = get_screen_mode()->acceleration != _no_acceleration ? TEST_FLAG(Get_OGL_ConfigureData().Flags,OGL_Flag_LiqSeeThru) : graphics_preferences->software_alpha_blending != _sw_alpha_off;
81
82 /* walls, ceilings, interior objects, floors, exterior objects for all nodes, back to front */
83 for (node= SortedNodes.begin(); node != SortedNodes.end(); ++node)
84 render_node(&*node, SeeThruLiquids, renderStep);
85 }
86
render_node(sorted_node_data * node,bool SeeThruLiquids,RenderStep renderStep)87 void RenderRasterizerClass::render_node(
88 sorted_node_data *node,
89 bool SeeThruLiquids,
90 RenderStep renderStep)
91 {
92 polygon_data *polygon= get_polygon_data(node->polygon_index);
93 clipping_window_data *window;
94 render_object_data *object;
95
96 // LP change: moved this stuff out here because it only has to be calculated
97 // once per polygon.
98 horizontal_surface_data floor_surface, ceiling_surface;
99 short i;
100
101 ceiling_surface.origin= polygon->ceiling_origin;
102 ceiling_surface.height= polygon->ceiling_height;
103 ceiling_surface.texture= polygon->ceiling_texture;
104 ceiling_surface.lightsource_index= polygon->ceiling_lightsource_index;
105 ceiling_surface.transfer_mode= polygon->ceiling_transfer_mode;
106 ceiling_surface.transfer_mode_data= 0;
107
108 floor_surface.origin= polygon->floor_origin;
109 floor_surface.height= polygon->floor_height;
110 floor_surface.texture= polygon->floor_texture;
111 floor_surface.lightsource_index= polygon->floor_lightsource_index;
112 floor_surface.transfer_mode= polygon->floor_transfer_mode;
113 floor_surface.transfer_mode_data= 0;
114
115 // Disguise flooded platforms
116 if (polygon->type == _polygon_is_platform)
117 {
118 platform_data *platform = get_platform_data(polygon->permutation);
119 if (platform && PLATFORM_IS_FLOODED(platform))
120 {
121 short adj_index = find_flooding_polygon(node->polygon_index);
122 if (adj_index != NONE)
123 {
124 struct polygon_data *adjacent_polygon= get_polygon_data(adj_index);
125 floor_surface.origin= adjacent_polygon->floor_origin;
126 floor_surface.height= adjacent_polygon->floor_height;
127 floor_surface.texture= adjacent_polygon->floor_texture;
128 floor_surface.lightsource_index= adjacent_polygon->floor_lightsource_index;
129 floor_surface.transfer_mode= adjacent_polygon->floor_transfer_mode;
130 floor_surface.transfer_mode_data= 0;
131 }
132 }
133 }
134
135 // The "continue" conditions are OK to move out here, because a non-drawn polygon's
136 // inhabitants will be clipped away.
137
138 // LP: get liquid data here for convenience;
139 // pointer to it being NULL means no liquid in the polygon
140 media_data *media = NULL;
141 if (polygon->media_index!=NONE)
142 media = get_media_data(polygon->media_index);
143
144 /* if necessary, replace the ceiling or floor surfaces with the media surface */
145 // LP change: don't do this step if liquids are semitransparent
146 if (media && !SeeThruLiquids)
147 {
148 // LP change: moved this get upwards
149 // struct media_data *media= get_media_data(polygon->media_index);
150 horizontal_surface_data *media_surface= NULL;
151
152 if (view->under_media_boundary)
153 {
154 // LP change: skip if high and dry
155 if (media->height <= polygon->floor_height)
156 return;
157
158 if (media->height<polygon->ceiling_height) media_surface= &ceiling_surface;
159 }
160 else
161 {
162 // LP change: skip if submerged
163 if (media->height >= polygon->ceiling_height)
164 return;
165
166 if (media->height>polygon->floor_height) media_surface= &floor_surface;
167 }
168
169 if (media_surface)
170 {
171 media_surface->origin= media->origin;
172 media_surface->height= media->height;
173 media_surface->texture= media->texture;
174 media_surface->lightsource_index= polygon->media_lightsource_index;
175 media_surface->transfer_mode= media->transfer_mode;
176 media_surface->transfer_mode_data= 0;
177 }
178 }
179 // LP change: always render liquids that are semitransparent
180 else if (!SeeThruLiquids)
181 {
182 // if we�re trying to draw a polygon without media from under a polygon with media, don�t
183 if (view->under_media_boundary) return;
184 }
185
186 // LP: this loop renders the walls
187 for (window= node->clipping_windows; window; window= window->next_window)
188 {
189 if (ceiling_surface.height>floor_surface.height)
190 {
191 /* render ceiling if above viewer */
192 if (ceiling_surface.height>view->origin.z)
193 {
194 // LP change: indicated that the void is on other side
195 render_node_floor_or_ceiling(window, polygon, &ceiling_surface, true, true, renderStep);
196 }
197
198 /* render visible sides */
199 for (i= 0; i<polygon->vertex_count; ++i)
200 {
201 short side_index= polygon->side_indexes[i];
202
203 if (side_index!=NONE && TEST_RENDER_FLAG(side_index, _side_is_visible))
204 {
205 line_data *line= get_line_data(polygon->line_indexes[i]);
206 side_data *side= get_side_data(side_index);
207 vertical_surface_data surface;
208
209 surface.length= line->length;
210 store_endpoint(get_endpoint_data(polygon->endpoint_indexes[i]), surface.p0);
211 store_endpoint(get_endpoint_data(polygon->endpoint_indexes[WRAP_HIGH(i, polygon->vertex_count-1)]), surface.p1);
212 surface.ambient_delta= side->ambient_delta;
213
214 // LP change: indicate in all cases whether the void is on the other side;
215 // added a workaround for full-side textures with a polygon on the other side
216 bool void_present;
217
218 switch (side->type)
219 {
220 case _full_side:
221 void_present = true;
222 // Suppress the void if there is a polygon on the other side.
223 if (polygon->adjacent_polygon_indexes[i] != NONE) void_present = false;
224
225 surface.lightsource_index= side->primary_lightsource_index;
226 surface.h0= floor_surface.height - view->origin.z;
227 surface.hmax= ceiling_surface.height - view->origin.z;
228 surface.h1= polygon->ceiling_height - view->origin.z;
229 surface.texture_definition= &side->primary_texture;
230 surface.transfer_mode= side->primary_transfer_mode;
231 render_node_side(window, &surface, void_present, renderStep);
232 break;
233 case _split_side: /* render _low_side first */
234 surface.lightsource_index= side->secondary_lightsource_index;
235 surface.h0= floor_surface.height - view->origin.z;
236 surface.h1= MAX(line->highest_adjacent_floor, floor_surface.height) - view->origin.z;
237 surface.hmax= ceiling_surface.height - view->origin.z;
238 surface.texture_definition= &side->secondary_texture;
239 surface.transfer_mode= side->secondary_transfer_mode;
240 render_node_side(window, &surface, true, renderStep);
241 /* fall through and render high side */
242 case _high_side:
243 surface.lightsource_index= side->primary_lightsource_index;
244 surface.h0= MIN(line->lowest_adjacent_ceiling, ceiling_surface.height) - view->origin.z;
245 surface.hmax= ceiling_surface.height - view->origin.z;
246 surface.h1= polygon->ceiling_height - view->origin.z;
247 surface.texture_definition= &side->primary_texture;
248 surface.transfer_mode= side->primary_transfer_mode;
249 render_node_side(window, &surface, true, renderStep);
250 // render_node_side(view, destination, window, &surface);
251 break;
252 case _low_side:
253 surface.lightsource_index= side->primary_lightsource_index;
254 surface.h0= floor_surface.height - view->origin.z;
255 surface.h1= MAX(line->highest_adjacent_floor, floor_surface.height) - view->origin.z;
256 surface.hmax= ceiling_surface.height - view->origin.z;
257 surface.texture_definition= &side->primary_texture;
258 surface.transfer_mode= side->primary_transfer_mode;
259 render_node_side(window, &surface, true, renderStep);
260 // render_node_side(view, destination, window, &surface);
261 break;
262
263 default:
264 assert(false);
265 break;
266 }
267
268 if (side->transparent_texture.texture!=UNONE)
269 {
270 surface.lightsource_index= side->transparent_lightsource_index;
271 surface.h0= MAX(line->highest_adjacent_floor, floor_surface.height) - view->origin.z;
272 surface.h1= line->lowest_adjacent_ceiling - view->origin.z;
273 surface.hmax= ceiling_surface.height - view->origin.z;
274 surface.texture_definition= &side->transparent_texture;
275 surface.transfer_mode= side->transparent_transfer_mode;
276 render_node_side(window, &surface, false, renderStep);
277 }
278 }
279 }
280
281 /* render floor if below viewer */
282 if (floor_surface.height<view->origin.z)
283 {
284 // LP change: indicated that the void is on other side
285 render_node_floor_or_ceiling(window, polygon, &floor_surface, true, false, renderStep);
286 }
287 }
288 }
289
290 // LP: this is for objects on the other side of the liquids;
291 // render them out here if one can see through the liquids
292 if (SeeThruLiquids)
293 {
294 /* render exterior objects (with their own clipping windows) */
295 for (object= node->exterior_objects; object; object= object->next_object)
296 {
297 render_node_object(object, true, renderStep);
298 }
299 }
300
301 // LP: render the liquid surface after the walls and the stuff behind it
302 // and before the stuff before it.
303 if (media && SeeThruLiquids)
304 {
305
306 // Render only if between the floor and the ceiling:
307 if (media->height > polygon->floor_height && media->height < polygon->ceiling_height)
308 {
309
310 // Render the liquids
311 bool ceil = (media->height > view->origin.z);
312 horizontal_surface_data LiquidSurface;
313
314 LiquidSurface.origin= media->origin;
315 LiquidSurface.height= media->height;
316 LiquidSurface.texture= media->texture;
317 LiquidSurface.lightsource_index= polygon->media_lightsource_index;
318 LiquidSurface.transfer_mode= media->transfer_mode;
319 LiquidSurface.transfer_mode_data= 0;
320
321 for (window= node->clipping_windows; window; window= window->next_window)
322 {
323 render_node_floor_or_ceiling(window, polygon, &LiquidSurface, false, ceil, renderStep);
324 }
325 }
326 }
327
328 // LP: this is for objects on the view side of the liquids
329 /* render exterior objects (with their own clipping windows) */
330 for (object= node->exterior_objects; object; object= object->next_object)
331 {
332 render_node_object(object, false, renderStep);
333 }
334 }
335
store_endpoint(endpoint_data * endpoint,long_vector2d & p)336 void RenderRasterizerClass::store_endpoint(
337 endpoint_data *endpoint,
338 long_vector2d& p)
339 {
340 overflow_short_to_long_2d(endpoint->transformed, endpoint->flags, p);
341 }
342
343
344 /* ---------- rendering ceilings and floors */
345
346 // LP change: added "void present on other side" flag
render_node_floor_or_ceiling(clipping_window_data * window,polygon_data * polygon,horizontal_surface_data * surface,bool void_present,bool ceil,RenderStep renderStep)347 void RenderRasterizerClass::render_node_floor_or_ceiling(
348 clipping_window_data *window,
349 polygon_data *polygon,
350 horizontal_surface_data *surface,
351 bool void_present,
352 bool ceil,
353 RenderStep renderStep)
354 {
355 // LP addition: animated-texture support
356 // Extra variable defined so as not to edit the original texture
357 shape_descriptor Texture = AnimTxtr_Translate(surface->texture);
358 if (Texture!=UNONE)
359 {
360 struct polygon_definition textured_polygon;
361 flagged_world_point2d vertices[MAXIMUM_VERTICES_PER_WORLD_POLYGON];
362 world_distance adjusted_height= surface->height-view->origin.z;
363 int32 transformed_height= adjusted_height*view->world_to_screen_y;
364 short vertex_count;
365 short i;
366
367 /* build transformed vertex list */
368 vertex_count= polygon->vertex_count;
369 for (i=0;i<vertex_count;++i)
370 {
371 // LP change: expanded the transformed-endpoint access
372 long_vector2d temp_vertex;
373 endpoint_data *endpoint = get_endpoint_data(polygon->endpoint_indexes[i]);
374 overflow_short_to_long_2d(endpoint->transformed,endpoint->flags,temp_vertex);
375 vertices[i].x = temp_vertex.i;
376 vertices[i].y = temp_vertex.j;
377 vertices[i].flags= 0;
378 }
379
380 /* reversing the order in which these two were clipped caused weird problems */
381
382 /* clip to left and right sides of the window */
383 vertex_count= xy_clip_horizontal_polygon(vertices, vertex_count, &window->left, _clip_left);
384 vertex_count= xy_clip_horizontal_polygon(vertices, vertex_count, &window->right, _clip_right);
385
386 /* clip to top and bottom sides of the window */
387 vertex_count= z_clip_horizontal_polygon(vertices, vertex_count, &window->top, adjusted_height, _clip_up);
388 vertex_count= z_clip_horizontal_polygon(vertices, vertex_count, &window->bottom, adjusted_height, _clip_down);
389
390 if (vertex_count)
391 {
392 /* transform the points we have into screen-space (backwards for ceiling polygons) */
393 for (i=0;i<vertex_count;++i)
394 {
395 flagged_world_point2d *world= vertices + (adjusted_height>0 ? vertex_count-i-1 : i);
396 point2d *screen= textured_polygon.vertices + i;
397
398 switch (world->flags&(_clip_left|_clip_right))
399 {
400 case 0:
401 // LP change: making it long-distance friendly
402 {
403 int32 world_x = world->x ? world->x : 1; // fix for division by zero error
404 int32 screen_x= view->half_screen_width + (world->y*view->world_to_screen_x)/world_x;
405 screen->x= PIN(screen_x, 0, view->screen_width);
406 }
407 break;
408 case _clip_left: screen->x= window->x0; break;
409 case _clip_right: screen->x= window->x1; break;
410 default:
411 screen->x= window->x0;
412 break;
413 }
414
415 switch (world->flags&(_clip_up|_clip_down))
416 {
417 case 0:
418 // LP change: making it long-distance friendly
419 {
420 int32 world_x = world->x ? world->x : 1; // fix for division by zero error
421 int32 screen_y= view->half_screen_height - transformed_height/world_x + view->dtanpitch;
422 screen->y= PIN(screen_y, 0, view->screen_height);
423 }
424 break;
425 case _clip_up: screen->y= window->y0; break;
426 case _clip_down: screen->y= window->y1; break;
427 default:
428 screen->y= window->y0;
429 break;
430 }
431 // vassert(screen->y>=0&&screen->y<=view->screen_height, csprintf(temporary, "horizontal: flags==%x, window @ %p", world->flags, window));
432 }
433
434 /* setup the other parameters of the textured polygon */
435 textured_polygon.flags= 0;
436 textured_polygon.origin.x= view->origin.x + surface->origin.x;
437 textured_polygon.origin.y= view->origin.y + surface->origin.y;
438 textured_polygon.origin.z= adjusted_height;
439 get_shape_bitmap_and_shading_table(Texture, &textured_polygon.texture, &textured_polygon.shading_tables, view->shading_mode);
440 // Bug out if bitmap is nonexistent
441 if (!textured_polygon.texture) return;
442
443 textured_polygon.ShapeDesc = Texture;
444 textured_polygon.ambient_shade= get_light_intensity(surface->lightsource_index);
445 textured_polygon.vertex_count= vertex_count;
446 instantiate_polygon_transfer_mode(view, &textured_polygon, surface->transfer_mode, true);
447 if (view->shading_mode==_shading_infravision) textured_polygon.flags|= _SHADELESS_BIT;
448
449 /* and, finally, map it */
450 // LP: added OpenGL support; also presence of void on other side
451 textured_polygon.VoidPresent = void_present;
452 // LP: using rasterizer object
453 RasPtr->texture_horizontal_polygon(textured_polygon);
454 }
455 }
456 }
457
458 /* ---------- rendering sides (walls) */
459
460 // LP change: added "void present on other side" flag
render_node_side(clipping_window_data * window,vertical_surface_data * surface,bool void_present,RenderStep renderStep)461 void RenderRasterizerClass::render_node_side(
462 clipping_window_data *window,
463 vertical_surface_data *surface,
464 bool void_present,
465 RenderStep renderStep)
466 {
467 world_distance h= MIN(surface->h1, surface->hmax);
468
469 // LP addition: animated-texture support
470 // Extra variable defined so as not to edit the original texture
471 shape_descriptor Texture = AnimTxtr_Translate(surface->texture_definition->texture);
472 if (h>surface->h0 && Texture!=UNONE)
473 {
474 struct polygon_definition textured_polygon;
475 flagged_world_point2d posts[2];
476 flagged_world_point3d vertices[MAXIMUM_VERTICES_PER_WORLD_POLYGON];
477 short vertex_count;
478 short i;
479
480 /* initialize the two posts of our trapezoid */
481 vertex_count= 2;
482 posts[0].x= surface->p0.i; posts[0].y= surface->p0.j; posts[0].flags= 0;
483 posts[1].x= surface->p1.i; posts[1].y= surface->p1.j; posts[1].flags= 0;
484
485 /* clip to left and right sides of the cone (must happen in the same order as horizontal polygons) */
486 vertex_count= xy_clip_line(posts, vertex_count, &window->left, _clip_left);
487 vertex_count= xy_clip_line(posts, vertex_count, &window->right, _clip_right);
488
489 if (vertex_count)
490 {
491 /* build a polygon out of the two posts */
492 vertex_count= 4;
493 vertices[0].z= vertices[1].z= h;
494 vertices[2].z= vertices[3].z= surface->h0;
495 vertices[0].x= vertices[3].x= posts[0].x, vertices[0].y= vertices[3].y= posts[0].y;
496 vertices[1].x= vertices[2].x= posts[1].x, vertices[1].y= vertices[2].y= posts[1].y;
497 vertices[0].flags= vertices[3].flags= posts[0].flags;
498 vertices[1].flags= vertices[2].flags= posts[1].flags;
499
500 /* clip to top and bottom sides of the window; because xz_clip_vertical_polygon accepts
501 vertices in clockwise or counterclockwise order, we can set our vertex list up to be
502 clockwise on the screen and never worry about it after that */
503 vertex_count= xz_clip_vertical_polygon(vertices, vertex_count, &window->top, _clip_up);
504 vertex_count= xz_clip_vertical_polygon(vertices, vertex_count, &window->bottom, _clip_down);
505
506 if (vertex_count)
507 {
508 world_distance dx= surface->p1.i - surface->p0.i;
509 world_distance dy= surface->p1.j - surface->p0.j;
510 world_distance x0= WORLD_FRACTIONAL_PART(surface->texture_definition->x0);
511 world_distance y0= WORLD_FRACTIONAL_PART(surface->texture_definition->y0);
512
513 /* calculate texture origin and direction */
514 world_distance divisor = surface->length;
515 if (divisor == 0)
516 divisor = 1;
517 textured_polygon.vector.i= (WORLD_ONE*dx)/divisor;
518 textured_polygon.vector.j= (WORLD_ONE*dy)/divisor;
519 textured_polygon.vector.k= -WORLD_ONE;
520 textured_polygon.origin.x= surface->p0.i - (x0*dx)/divisor;
521 textured_polygon.origin.y= surface->p0.j - (x0*dy)/divisor;
522 textured_polygon.origin.z= surface->h1 + y0;
523
524 /* transform the points we have into screen-space */
525 for (i=0;i<vertex_count;++i)
526 {
527 flagged_world_point3d *world= vertices + i;
528 point2d *screen= textured_polygon.vertices + i;
529
530 switch (world->flags&(_clip_left|_clip_right))
531 {
532 case 0:
533 // LP change: making it long-distance friendly
534 {
535 int32 screen_x= view->half_screen_width + (world->x ? (world->y*view->world_to_screen_x)/world->x : 0);
536 screen->x= PIN(screen_x, 0, view->screen_width);
537 }
538 break;
539 case _clip_left: screen->x= window->x0; break;
540 case _clip_right: screen->x= window->x1; break;
541 default:
542 screen->x= window->x0;
543 break;
544 }
545
546 switch (world->flags&(_clip_up|_clip_down))
547 {
548 case 0:
549 // LP change: making it long-distance friendly
550 {
551 int32 screen_y= view->half_screen_height - (world->x ? (world->z*view->world_to_screen_y)/world->x : 0) + view->dtanpitch;
552 screen->y= PIN(screen_y, 0, view->screen_height);
553 }
554 break;
555 case _clip_up: screen->y= window->y0; break;
556 case _clip_down: screen->y= window->y1; break;
557 default:
558 screen->y= window->y0;
559 break;
560 }
561 // vassert(screen->y>=0&&screen->y<=view->screen_height, csprintf(temporary, "#%d!in[#0,#%d]: flags==%x, wind@%p #%d w@%p s@%p", screen->y, view->screen_height, world->flags, window, vertex_count, world, screen));
562 }
563
564 /* setup the other parameters of the textured polygon */
565 textured_polygon.flags= 0;
566 get_shape_bitmap_and_shading_table(Texture, &textured_polygon.texture, &textured_polygon.shading_tables, view->shading_mode);
567 // Bug out if bitmap is nonexistent
568 if (!textured_polygon.texture) return;
569
570 textured_polygon.ShapeDesc = Texture;
571 textured_polygon.ambient_shade= get_light_intensity(surface->lightsource_index) + surface->ambient_delta;
572 textured_polygon.ambient_shade= PIN(textured_polygon.ambient_shade, 0, FIXED_ONE);
573 textured_polygon.vertex_count= vertex_count;
574 instantiate_polygon_transfer_mode(view, &textured_polygon, surface->transfer_mode, false);
575 if (view->shading_mode==_shading_infravision) textured_polygon.flags|= _SHADELESS_BIT;
576
577 /* and, finally, map it */
578 // LP: added OpenGL support; also presence of void on other side
579 textured_polygon.VoidPresent = void_present;
580 // LP: using rasterizer object
581 RasPtr->texture_vertical_polygon(textured_polygon);
582 }
583 }
584 }
585 }
586
587 /* ---------- rendering objects */
588
render_node_object(render_object_data * object,bool other_side_of_media,RenderStep renderStep)589 void RenderRasterizerClass::render_node_object(
590 render_object_data *object,
591 bool other_side_of_media,
592 RenderStep renderStep)
593 {
594 struct clipping_window_data *window;
595
596 for (window= object->clipping_windows; window; window= window->next_window)
597 {
598 object->rectangle.clip_left= window->x0;
599 object->rectangle.clip_right= window->x1;
600 object->rectangle.clip_top= window->y0;
601 object->rectangle.clip_bottom= window->y1;
602
603 // Models will have their own liquid-surface clipping,
604 // so don't edit their clip rects
605 // This is bitwise XOR, but is presumably OK here
606 if (view->under_media_boundary ^ other_side_of_media)
607 {
608 // Clipping: below a liquid surface
609 if (object->rectangle.ModelPtr)
610 object->rectangle.BelowLiquid = true;
611 else
612 object->rectangle.clip_top= MAX(object->rectangle.clip_top, object->ymedia);
613 }
614 else
615 {
616 // Clipping: above a liquid surface
617 if (object->rectangle.ModelPtr)
618 object->rectangle.BelowLiquid = false;
619 else
620 object->rectangle.clip_bottom= MIN(object->rectangle.clip_bottom, object->ymedia);
621 }
622
623 // LP: added OpenGL support
624 // LP: using rasterizer object
625 RasPtr->texture_rectangle(object->rectangle);
626 }
627 }
628
629
630 /* ---------- horizontal polygon clipping */
631
632 enum /* xy_clip_horizontal_polygon() states */
633 {
634 _testing_first_vertex, /* are we in or out? */
635 _searching_cw_for_in_out_transition,
636 _searching_ccw_for_out_in_transition,
637 _searching_cw_for_out_in_transition
638 };
639
640 // LP change: make it better able to do long-distance views
xy_clip_horizontal_polygon(flagged_world_point2d * vertices,short vertex_count,long_vector2d * line,uint16 flag)641 short RenderRasterizerClass::xy_clip_horizontal_polygon(
642 flagged_world_point2d *vertices,
643 short vertex_count,
644 long_vector2d *line,
645 uint16 flag)
646 {
647 #ifdef QUICKDRAW_DEBUG
648 debug_flagged_points(vertices, vertex_count);
649 debug_vector(line);
650 #endif
651 // dprintf("clipping %p (#%d vertices) to vector %x,%x (slope==%x)", vertices, vertex_count, line->i, line->j, slope);
652
653 if (vertex_count)
654 {
655 short state= _testing_first_vertex;
656 short vertex_index= 0, vertex_delta= 1, first_vertex= 0;
657 short entrance_vertex= NONE, exit_vertex= NONE; /* exiting the clipped area and entering the clipped area */
658 bool clipped_exit_vertex= true, clipped_entrance_vertex= true; /* will be false if these points lie directly on a vertex */
659
660 do
661 {
662 // LP change:
663 CROSSPROD_TYPE cross_product= CROSSPROD_TYPE(line->i)*vertices[vertex_index].y - CROSSPROD_TYPE(line->j)*vertices[vertex_index].x;
664 // int32 cross_product= line->i*vertices[vertex_index].y - line->j*vertices[vertex_index].x;
665
666 switch (SGN(cross_product))
667 {
668 case -1: /* inside (i.e., will be clipped) */
669 // dprintf("vertex#%d is inside s==#%d", vertex_index, state);
670 switch (state)
671 {
672 case _testing_first_vertex:
673 first_vertex= vertex_index;
674 state= _searching_cw_for_in_out_transition; /* the exit point from the clip area */
675 break;
676
677 case _searching_ccw_for_out_in_transition: /* found exit point from clip area */
678 state= _searching_cw_for_out_in_transition; /* the entrance point to the clipped area */
679 vertex_delta= 1;
680 if (exit_vertex==NONE) exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
681 vertex_index= first_vertex; /* skip vertices we already know are out */
682 break;
683
684 case _searching_cw_for_out_in_transition: /* found entrance point to clipped area */
685 if (entrance_vertex==NONE) entrance_vertex= vertex_index;
686 state= NONE;
687 break;
688 }
689 break;
690
691 case 0: /* clip line passed directly through a vertex */
692 // dprintf("vertex#%d is on the clip line s==#%d", vertex_index, state);
693 switch (state)
694 {
695 /* if we�re testing the first vertex, this tells us nothing */
696
697 case _searching_cw_for_out_in_transition:
698 entrance_vertex= vertex_index;
699 clipped_entrance_vertex= false; /* remember if this passes through vertex */
700 break;
701
702 case _searching_cw_for_in_out_transition:
703 exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
704 clipped_exit_vertex= false;
705 break;
706 case _searching_ccw_for_out_in_transition:
707 exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
708 clipped_exit_vertex= false; /* remember if this passes through vertex */
709 break;
710 }
711 break;
712
713 case 1: /* outside (i.e., will not be clipped) */
714 // dprintf("vertex#%d is outside s==#%d", vertex_index, state);
715 switch (state)
716 {
717 case _testing_first_vertex:
718 first_vertex= vertex_index;
719 state= _searching_ccw_for_out_in_transition; /* the exit point from the clipped area */
720 vertex_delta= -1;
721 break;
722
723 case _searching_cw_for_in_out_transition: /* found exit point from clipped area */
724 state= _searching_cw_for_out_in_transition; /* the entrance point to the clipped area */
725 if (exit_vertex==NONE) exit_vertex= vertex_index;
726 break;
727 }
728 break;
729 }
730
731 /* adjust vertex_index (clockwise or counterclockwise, depending on vertex_delta)
732 if we�ve come back to the first vertex without finding an entrance point we�re
733 either all the way in or all the way out */
734 vertex_index= (vertex_delta<0) ? WRAP_LOW(vertex_index, vertex_count-1) :
735 WRAP_HIGH(vertex_index, vertex_count-1);
736 if (vertex_index==first_vertex) /* we came full-circle without hitting anything */
737 {
738 switch (state)
739 {
740 case _searching_cw_for_in_out_transition: /* never found a way out: clipped into nothing */
741 vertex_count= 0;
742 case _testing_first_vertex: /* is this the right thing to do? */
743 case _searching_ccw_for_out_in_transition: /* never found a way in: no clipping */
744 exit_vertex= NONE;
745 state= NONE;
746 break;
747 }
748 }
749 }
750 while (state!=NONE);
751
752 if (exit_vertex!=NONE) /* we�ve got clipping to do */
753 {
754 flagged_world_point2d new_entrance_point, new_exit_point;
755
756 // dprintf("entrance_vertex==#%d (%s), exit_vertex==#%d (%s)", entrance_vertex, clipped_entrance_vertex ? "clipped" : "unclipped", exit_vertex, clipped_exit_vertex ? "clipped" : "unclipped");
757
758 /* clip the entrance to the clipped area */
759 if (clipped_entrance_vertex)
760 {
761 xy_clip_flagged_world_points(vertices + WRAP_LOW(entrance_vertex, vertex_count-1), vertices + entrance_vertex,
762 &new_entrance_point, line);
763 }
764 else
765 {
766 new_entrance_point= vertices[entrance_vertex];
767 }
768 new_entrance_point.flags|= flag;
769
770 /* clip the exit from the clipped area */
771 if (clipped_exit_vertex)
772 {
773 xy_clip_flagged_world_points(vertices + WRAP_LOW(exit_vertex, vertex_count-1), vertices + exit_vertex,
774 &new_exit_point, line);
775 }
776 else
777 {
778 new_exit_point= vertices[WRAP_LOW(exit_vertex, vertex_count-1)];
779 }
780 new_exit_point.flags|= flag;
781
782 /* adjust for the change in number of vertices */
783 vertex_delta= entrance_vertex - exit_vertex;
784 if (vertex_delta<0)
785 {
786 if (vertex_delta!=-2) memmove(vertices+entrance_vertex+2, vertices+exit_vertex, (vertex_count-exit_vertex)*sizeof(flagged_world_point2d));
787 vertex_delta= vertex_count+vertex_delta;
788 }
789 else
790 {
791 /* move down by exit_vertex, add new vertices to end */
792 assert(vertex_delta);
793 if (exit_vertex)
794 {
795 memmove(vertices, vertices+exit_vertex, vertex_delta*sizeof(flagged_world_point2d));
796 entrance_vertex-= exit_vertex;
797 }
798 }
799
800 vertex_count= vertex_delta+2;
801 vwarn(vertex_count>=3 && vertex_count<=MAXIMUM_VERTICES_PER_WORLD_POLYGON,
802 csprintf(temporary, "vertex overflow or underflow (#%d);g;", vertex_count));
803
804 if (vertex_count<3 || vertex_count>MAXIMUM_VERTICES_PER_WORLD_POLYGON)
805 {
806 vertex_count= 0;
807 }
808 else
809 {
810 /* and, finally, add the new vertices */
811 vertices[entrance_vertex]= new_entrance_point;
812 vertices[entrance_vertex+1]= new_exit_point;
813 }
814 }
815 }
816
817 #ifdef QUICKDRAW_DEBUG
818 debug_flagged_points(vertices, vertex_count);
819 debug_vector(line);
820 #endif
821 // dprintf("result == %p (#%d vertices)", vertices, vertex_count);
822
823 return vertex_count;
824 }
825
826 /* sort points before clipping to assure consistency; there is a way to make this more accurate
827 but it requires the downshifting game, as played in SCOTTISH_TEXTURES.C. it�s tempting to
828 think that having a smaller scale for our world coordinates would help here (i.e., less bits
829 per distance) but then wouldn�t we be screwed when we tried to rotate? */
830 // LP change: make it better able to do long-distance views
xy_clip_flagged_world_points(flagged_world_point2d * p0,flagged_world_point2d * p1,flagged_world_point2d * clipped,long_vector2d * line)831 void RenderRasterizerClass::xy_clip_flagged_world_points(
832 flagged_world_point2d *p0,
833 flagged_world_point2d *p1,
834 flagged_world_point2d *clipped,
835 long_vector2d *line)
836 {
837 bool swap= (p1->y>p0->y) ? false : ((p0->y==p1->y) ? (p1->x<p0->x) : true);
838 flagged_world_point2d *local_p0= swap ? p1 : p0;
839 flagged_world_point2d *local_p1= swap ? p0 : p1;
840 world_distance dx= local_p1->x - local_p0->x;
841 world_distance dy= local_p1->y - local_p0->y;
842 int32 numerator = int32(1LL*line->j*local_p0->x - 1LL*line->i*local_p0->y);
843 int32 denominator = int32(1LL*line->i*dy - 1LL*line->j*dx);
844 short shift_count= FIXED_FRACTIONAL_BITS;
845 _fixed t;
846
847 /* give numerator 16 significant bits over denominator and then calculate t==n/d; MPW�s PPCC
848 didn�t seem to like (INT32_MIN>>1) and i had to substitute 0xc0000000 instead (hmmm) */
849 while (numerator<=(int32)0x3fffffff && numerator>=(int32)0xc0000000 && shift_count--) numerator<<= 1;
850 if (shift_count>0) denominator>>= shift_count;
851 t= numerator;
852 if (denominator)
853 t /= denominator;
854
855 /* calculate the clipped point */
856 clipped->x = local_p0->x + FIXED_INTEGERAL_PART(int32(1LL*t*dx));
857 clipped->y = local_p0->y + FIXED_INTEGERAL_PART(int32(1LL*t*dy));
858 clipped->flags= local_p0->flags&local_p1->flags;
859 }
860
861 /* almost wholly identical to xz_clip_vertical_polygon() except that this works off 2d points
862 in the xy-plane and a height */
863 // LP change: make it better able to do long-distance views
z_clip_horizontal_polygon(flagged_world_point2d * vertices,short vertex_count,long_vector2d * line,world_distance height,uint16 flag)864 short RenderRasterizerClass::z_clip_horizontal_polygon(
865 flagged_world_point2d *vertices,
866 short vertex_count,
867 long_vector2d *line, /* i==x, j==z */
868 world_distance height,
869 uint16 flag)
870 {
871 CROSSPROD_TYPE heighti= CROSSPROD_TYPE(line->i)*height;
872
873 #ifdef QUICKDRAW_DEBUG
874 debug_flagged_points(vertices, vertex_count);
875 debug_x_line(line->j ? (line->i*height)/line->j : (height<0 ? INT32_MIN : INT32_MAX));
876 #endif
877 // dprintf("clipping %p (#%d vertices) to vector %x,%x", vertices, vertex_count, line->i, line->j);
878
879 if (vertex_count)
880 {
881 short state= _testing_first_vertex;
882 short vertex_index= 0, vertex_delta= 1, first_vertex= 0;
883 short entrance_vertex= NONE, exit_vertex= NONE; /* exiting the clipped area and entering the clipped area */
884 bool clipped_exit_vertex= true, clipped_entrance_vertex= true; /* will be false if these points lie directly on a vertex */
885
886 do
887 {
888 CROSSPROD_TYPE cross_product= heighti - CROSSPROD_TYPE(line->j)*vertices[vertex_index].x;
889
890 if (cross_product<0) /* inside (i.e., will be clipped) */
891 {
892 switch (state)
893 {
894 case _testing_first_vertex:
895 first_vertex= vertex_index;
896 state= _searching_cw_for_in_out_transition; /* the exit point from the clip area */
897 break;
898
899 case _searching_ccw_for_out_in_transition: /* found exit point from clip area */
900 state= _searching_cw_for_out_in_transition; /* the entrance point to the clipped area */
901 vertex_delta= 1;
902 if (exit_vertex==NONE) exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
903 vertex_index= first_vertex; /* skip vertices we already know are out */
904 break;
905
906 case _searching_cw_for_out_in_transition: /* found entrance point to clipped area */
907 if (entrance_vertex==NONE) entrance_vertex= vertex_index;
908 state= NONE;
909 break;
910 }
911 }
912 else
913 {
914 if (cross_product>0) /* outside (i.e., will not be clipped) */
915 {
916 switch (state)
917 {
918 case _testing_first_vertex:
919 first_vertex= vertex_index;
920 state= _searching_ccw_for_out_in_transition; /* the exit point from the clipped area */
921 vertex_delta= -1;
922 break;
923
924 case _searching_cw_for_in_out_transition: /* found exit point from clipped area */
925 state= _searching_cw_for_out_in_transition; /* the entrance point to the clipped area */
926 if (exit_vertex==NONE) exit_vertex= vertex_index;
927 break;
928 }
929 }
930 else /* clip line passed directly through a vertex */
931 {
932 switch (state)
933 {
934 /* if we�re testing the first vertex (_testing_first_vertex), this tells us nothing */
935
936 case _searching_cw_for_out_in_transition:
937 entrance_vertex= vertex_index;
938 clipped_entrance_vertex= false; /* remember if this passes through vertex */
939 break;
940
941 case _searching_cw_for_in_out_transition:
942 exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
943 clipped_exit_vertex= false;
944 break;
945 case _searching_ccw_for_out_in_transition:
946 exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
947 clipped_exit_vertex= false; /* remember if this passes through vertex */
948 break;
949 }
950 }
951 }
952
953 /* adjust vertex_index (clockwise or counterclockwise, depending on vertex_delta)
954 if we�ve come back to the first vertex without finding an entrance point we�re
955 either all the way in or all the way out */
956 vertex_index= (vertex_delta<0) ? WRAP_LOW(vertex_index, vertex_count-1) :
957 WRAP_HIGH(vertex_index, vertex_count-1);
958 if (vertex_index==first_vertex) /* we came full-circle without hitting anything */
959 {
960 switch (state)
961 {
962 case _searching_cw_for_in_out_transition: /* never found a way out: clipped into nothing */
963 vertex_count= 0;
964 case _testing_first_vertex: /* is this the right thing to do? */
965 case _searching_ccw_for_out_in_transition: /* never found a way in: no clipping */
966 exit_vertex= NONE;
967 state= NONE;
968 break;
969 }
970 }
971 }
972 while (state!=NONE);
973
974 if (exit_vertex!=NONE) /* we�ve got clipping to do */
975 {
976 flagged_world_point2d new_entrance_point, new_exit_point;
977
978 // dprintf("entrance_vertex==#%d (%s), exit_vertex==#%d (%s)", entrance_vertex, clipped_entrance_vertex ? "clipped" : "unclipped", exit_vertex, clipped_exit_vertex ? "clipped" : "unclipped");
979
980 /* clip the entrance to the clipped area */
981 if (clipped_entrance_vertex)
982 {
983 z_clip_flagged_world_points(vertices + WRAP_LOW(entrance_vertex, vertex_count-1), vertices + entrance_vertex,
984 height, &new_entrance_point, line);
985 }
986 else
987 {
988 new_entrance_point= vertices[entrance_vertex];
989 }
990 new_entrance_point.flags|= flag;
991
992 /* clip the exit from the clipped area */
993 if (clipped_exit_vertex)
994 {
995 z_clip_flagged_world_points(vertices + WRAP_LOW(exit_vertex, vertex_count-1), vertices + exit_vertex,
996 height, &new_exit_point, line);
997 }
998 else
999 {
1000 new_exit_point= vertices[WRAP_LOW(exit_vertex, vertex_count-1)];
1001 }
1002 new_exit_point.flags|= flag;
1003
1004 /* adjust for the change in number of vertices */
1005 vertex_delta= entrance_vertex - exit_vertex;
1006 if (vertex_delta<0)
1007 {
1008 if (vertex_delta!=-2) memmove(vertices+entrance_vertex+2, vertices+exit_vertex, (vertex_count-exit_vertex)*sizeof(flagged_world_point2d));
1009 vertex_delta= vertex_count+vertex_delta;
1010 }
1011 else
1012 {
1013 /* move down by exit_vertex, add new vertices to end */
1014 assert(vertex_delta);
1015 if (exit_vertex)
1016 {
1017 memmove(vertices, vertices+exit_vertex, vertex_delta*sizeof(flagged_world_point2d));
1018 entrance_vertex-= exit_vertex;
1019 }
1020 }
1021 vertex_count= vertex_delta+2;
1022
1023 vwarn(vertex_count>=3 && vertex_count<=MAXIMUM_VERTICES_PER_WORLD_POLYGON,
1024 csprintf(temporary, "vertex overflow or underflow (#%d);g;", vertex_count));
1025
1026 if (vertex_count<3 || vertex_count>MAXIMUM_VERTICES_PER_WORLD_POLYGON)
1027 {
1028 vertex_count= 0;
1029 }
1030 else
1031 {
1032 /* and, finally, add the new vertices */
1033 vertices[entrance_vertex]= new_entrance_point;
1034 vertices[entrance_vertex+1]= new_exit_point;
1035 }
1036 }
1037 }
1038
1039 #ifdef QUICKDRAW_DEBUG
1040 debug_flagged_points(vertices, vertex_count);
1041 debug_x_line(line->j ? (line->i*height)/line->j : (height<0 ? INT32_MIN : INT32_MAX));
1042 #endif
1043 // dprintf("result == %p (#%d vertices)", vertices, vertex_count);
1044
1045 return vertex_count;
1046 }
1047
1048 /* sort points before clipping to assure consistency; this is almost identical to xz_clip�()
1049 except that it clips 2d points in the xy-plane at the given height. */
1050 // LP change: make it better able to do long-distance views
z_clip_flagged_world_points(flagged_world_point2d * p0,flagged_world_point2d * p1,world_distance height,flagged_world_point2d * clipped,long_vector2d * line)1051 void RenderRasterizerClass::z_clip_flagged_world_points(
1052 flagged_world_point2d *p0,
1053 flagged_world_point2d *p1,
1054 world_distance height,
1055 flagged_world_point2d *clipped,
1056 long_vector2d *line)
1057 {
1058 bool swap= (p1->y>p0->y) ? false : ((p0->y==p1->y) ? (p1->x<p0->x) : true);
1059 flagged_world_point2d *local_p0= swap ? p1 : p0;
1060 flagged_world_point2d *local_p1= swap ? p0 : p1;
1061 world_distance dx= local_p1->x - local_p0->x;
1062 world_distance dy= local_p1->y - local_p0->y;
1063 int32 numerator = int32(1LL*line->j*local_p0->x - 1LL*line->i*height);
1064 int32 denominator = int32(-1LL*line->j*dx);
1065 short shift_count= FIXED_FRACTIONAL_BITS;
1066 _fixed t;
1067
1068 /* give numerator 16 significant bits over denominator and then calculate t==n/d; MPW�s PPCC
1069 didn�t seem to like (INT32_MIN>>1) and i had to substitute 0xc0000000 instead (hmmm) */
1070 while (numerator<=(int32)0x3fffffff && numerator>=(int32)0xc0000000 && shift_count--) numerator<<= 1;
1071 if (shift_count>0) denominator>>= shift_count;
1072 t= numerator;
1073 if (denominator)
1074 t /= denominator;
1075
1076 /* calculate the clipped point */
1077 clipped->x = local_p0->x + FIXED_INTEGERAL_PART(int32(1LL*t*dx));
1078 clipped->y = local_p0->y + FIXED_INTEGERAL_PART(int32(1LL*t*dy));
1079 clipped->flags= local_p0->flags&local_p1->flags;
1080 }
1081
1082 /* ---------- vertical polygon clipping */
1083
1084 // LP change: make it better able to do long-distance views
xy_clip_line(flagged_world_point2d * posts,short vertex_count,long_vector2d * line,uint16 flag)1085 short RenderRasterizerClass::xy_clip_line(
1086 flagged_world_point2d *posts,
1087 short vertex_count,
1088 long_vector2d *line,
1089 uint16 flag)
1090 {
1091 #ifdef QUICKDRAW_DEBUG
1092 // debug_flagged_points(posts, vertex_count);
1093 // debug_vector(line);
1094 #endif
1095 // dprintf("clipping %p (#%d) to line (%d,%d)", posts, vertex_count, line->i, line->j);
1096
1097 if (vertex_count)
1098 {
1099 CROSSPROD_TYPE cross_product0= CROSSPROD_TYPE(line->i)*posts[0].y - CROSSPROD_TYPE(line->j)*posts[0].x;
1100 CROSSPROD_TYPE cross_product1= CROSSPROD_TYPE(line->i)*posts[1].y - CROSSPROD_TYPE(line->j)*posts[1].x;
1101
1102 if (cross_product0<0)
1103 {
1104 if (cross_product1<0) /* clipped out of existence */
1105 {
1106 vertex_count= 0;
1107 }
1108 else
1109 {
1110 xy_clip_flagged_world_points(&posts[0], &posts[1], &posts[0], line);
1111 posts[0].flags|= flag;
1112 }
1113 }
1114 else
1115 {
1116 if (cross_product1<0)
1117 {
1118 xy_clip_flagged_world_points(&posts[0], &posts[1], &posts[1], line);
1119 posts[1].flags|= flag;
1120 }
1121 }
1122 }
1123
1124 #ifdef QUICKDRAW_DEBUG
1125 // debug_flagged_points(posts, vertex_count);
1126 // debug_vector(line);
1127 #endif
1128 // dprintf("result #%d vertices", vertex_count);
1129
1130 return vertex_count;
1131 }
1132
1133 // LP change: make it better able to do long-distance views
xz_clip_vertical_polygon(flagged_world_point3d * vertices,short vertex_count,long_vector2d * line,uint16 flag)1134 short RenderRasterizerClass::xz_clip_vertical_polygon(
1135 flagged_world_point3d *vertices,
1136 short vertex_count,
1137 long_vector2d *line, /* i==x, j==z */
1138 uint16 flag)
1139 {
1140 #ifdef QUICKDRAW_DEBUG
1141 // debug_flagged_points3d(vertices, vertex_count);
1142 // debug_vector(line);
1143 #endif
1144 // dprintf("clipping %p (#%d vertices) to vector %x,%x", vertices, vertex_count, line->i, line->j);
1145
1146 if (vertex_count)
1147 {
1148 short state= _testing_first_vertex;
1149 short vertex_index= 0, vertex_delta= 1, first_vertex= 0;
1150 short entrance_vertex= NONE, exit_vertex= NONE; /* exiting the clipped area and entering the clipped area */
1151 bool clipped_exit_vertex= true, clipped_entrance_vertex= true; /* will be false if these points lie directly on a vertex */
1152
1153 do
1154 {
1155 CROSSPROD_TYPE cross_product= CROSSPROD_TYPE(line->i)*vertices[vertex_index].z - CROSSPROD_TYPE(line->j)*vertices[vertex_index].x;
1156
1157 switch (SGN(cross_product))
1158 {
1159 case -1: /* inside (i.e., will be clipped) */
1160 // dprintf("vertex#%d is inside s==#%d", vertex_index, state);
1161 switch (state)
1162 {
1163 case _testing_first_vertex:
1164 first_vertex= vertex_index;
1165 state= _searching_cw_for_in_out_transition; /* the exit point from the clip area */
1166 break;
1167
1168 case _searching_ccw_for_out_in_transition: /* found exit point from clip area */
1169 state= _searching_cw_for_out_in_transition; /* the entrance point to the clipped area */
1170 vertex_delta= 1;
1171 if (exit_vertex==NONE) exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
1172 vertex_index= first_vertex; /* skip vertices we already know are out */
1173 break;
1174
1175 case _searching_cw_for_out_in_transition: /* found entrance point to clipped area */
1176 if (entrance_vertex==NONE) entrance_vertex= vertex_index;
1177 state= NONE;
1178 break;
1179 }
1180 break;
1181
1182 case 0: /* clip line passed directly through a vertex */
1183 // dprintf("vertex#%d is on the clip line s==#%d", vertex_index, state);
1184 switch (state)
1185 {
1186 /* if we�re testing the first vertex, this tells us nothing */
1187
1188 case _searching_cw_for_out_in_transition:
1189 entrance_vertex= vertex_index;
1190 clipped_entrance_vertex= false; /* remember if this passes through vertex */
1191 break;
1192
1193 case _searching_cw_for_in_out_transition:
1194 exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
1195 clipped_exit_vertex= false;
1196 break;
1197 case _searching_ccw_for_out_in_transition:
1198 exit_vertex= WRAP_HIGH(vertex_index, vertex_count-1);
1199 clipped_exit_vertex= false; /* remember if this passes through vertex */
1200 break;
1201 }
1202 break;
1203
1204 case 1: /* outside (i.e., will not be clipped) */
1205 // dprintf("vertex#%d is outside s==#%d", vertex_index, state);
1206 switch (state)
1207 {
1208 case _testing_first_vertex:
1209 first_vertex= vertex_index;
1210 state= _searching_ccw_for_out_in_transition; /* the exit point from the clipped area */
1211 vertex_delta= -1;
1212 break;
1213
1214 case _searching_cw_for_in_out_transition: /* found exit point from clipped area */
1215 state= _searching_cw_for_out_in_transition; /* the entrance point to the clipped area */
1216 if (exit_vertex==NONE) exit_vertex= vertex_index;
1217 break;
1218 }
1219 break;
1220 }
1221
1222 /* adjust vertex_index (clockwise or counterclockwise, depending on vertex_delta)
1223 if we�ve come back to the first vertex without finding an entrance point we�re
1224 either all the way in or all the way out */
1225 vertex_index= (vertex_delta<0) ? WRAP_LOW(vertex_index, vertex_count-1) :
1226 WRAP_HIGH(vertex_index, vertex_count-1);
1227 if (vertex_index==first_vertex) /* we came full-circle without hitting anything */
1228 {
1229 switch (state)
1230 {
1231 case _searching_cw_for_in_out_transition: /* never found a way out: clipped into nothing */
1232 vertex_count= 0;
1233 case _testing_first_vertex: /* is this the right thing to do? */
1234 case _searching_ccw_for_out_in_transition: /* never found a way in: no clipping */
1235 exit_vertex= NONE;
1236 state= NONE;
1237 break;
1238 }
1239 }
1240 }
1241 while (state!=NONE);
1242
1243 if (exit_vertex!=NONE) /* we�ve got clipping to do */
1244 {
1245 flagged_world_point3d new_entrance_point, new_exit_point;
1246
1247 // dprintf("entrance_vertex==#%d (%s), exit_vertex==#%d (%s)", entrance_vertex, clipped_entrance_vertex ? "clipped" : "unclipped", exit_vertex, clipped_exit_vertex ? "clipped" : "unclipped");
1248
1249 /* clip the entrance to the clipped area */
1250 if (clipped_entrance_vertex)
1251 {
1252 xz_clip_flagged_world_points(vertices + WRAP_LOW(entrance_vertex, vertex_count-1), vertices + entrance_vertex,
1253 &new_entrance_point, line);
1254 }
1255 else
1256 {
1257 new_entrance_point= vertices[entrance_vertex];
1258 }
1259 new_entrance_point.flags|= flag;
1260
1261 /* clip the exit from the clipped area */
1262 if (clipped_exit_vertex)
1263 {
1264 xz_clip_flagged_world_points(vertices + WRAP_LOW(exit_vertex, vertex_count-1), vertices + exit_vertex,
1265 &new_exit_point, line);
1266 }
1267 else
1268 {
1269 new_exit_point= vertices[WRAP_LOW(exit_vertex, vertex_count-1)];
1270 }
1271 new_exit_point.flags|= flag;
1272
1273 /* adjust for the change in number of vertices */
1274 vertex_delta= entrance_vertex - exit_vertex;
1275 if (vertex_delta<0)
1276 {
1277 if (vertex_delta!=-2) memmove(vertices+entrance_vertex+2, vertices+exit_vertex, (vertex_count-exit_vertex)*sizeof(flagged_world_point3d));
1278 vertex_delta= vertex_count+vertex_delta;
1279 }
1280 else
1281 {
1282 /* move down by exit_vertex, add new vertices to end */
1283 assert(vertex_delta);
1284 if (exit_vertex)
1285 {
1286 memmove(vertices, vertices+exit_vertex, vertex_delta*sizeof(flagged_world_point3d));
1287 entrance_vertex-= exit_vertex;
1288 }
1289 }
1290 vertex_count= vertex_delta+2;
1291
1292 vwarn(vertex_count>=3 && vertex_count<=MAXIMUM_VERTICES_PER_WORLD_POLYGON,
1293 csprintf(temporary, "vertex overflow or underflow (#%d);g;", vertex_count));
1294
1295 if (vertex_count<3 || vertex_count>MAXIMUM_VERTICES_PER_WORLD_POLYGON)
1296 {
1297 vertex_count= 0;
1298 }
1299 else
1300 {
1301 /* and, finally, add the new vertices */
1302 vertices[entrance_vertex]= new_entrance_point;
1303 vertices[entrance_vertex+1]= new_exit_point;
1304 }
1305 }
1306 }
1307
1308 #ifdef QUICKDRAW_DEBUG
1309 // debug_flagged_points3d(vertices, vertex_count);
1310 // debug_vector(line);
1311 #endif
1312 // dprintf("result == %p (#%d vertices)", vertices, vertex_count);
1313
1314 return vertex_count;
1315 }
1316
1317 /* sort points before clipping to assure consistency */
1318 // LP change: make it better able to do long-distance views
xz_clip_flagged_world_points(flagged_world_point3d * p0,flagged_world_point3d * p1,flagged_world_point3d * clipped,long_vector2d * line)1319 void RenderRasterizerClass::xz_clip_flagged_world_points(
1320 flagged_world_point3d *p0,
1321 flagged_world_point3d *p1,
1322 flagged_world_point3d *clipped,
1323 long_vector2d *line)
1324 {
1325 bool swap= (p1->y>p0->y) ? false : ((p0->y==p1->y) ? (p1->x<p0->x) : true);
1326 flagged_world_point3d *local_p0= swap ? p1 : p0;
1327 flagged_world_point3d *local_p1= swap ? p0 : p1;
1328 world_distance dx= local_p1->x - local_p0->x;
1329 world_distance dy= local_p1->y - local_p0->y;
1330 world_distance dz= local_p1->z - local_p0->z;
1331 int32 numerator = int32(1LL*line->j*local_p0->x - 1LL*line->i*local_p0->z);
1332 int32 denominator = int32(1LL*line->i*dz - 1LL*line->j*dx);
1333 short shift_count= FIXED_FRACTIONAL_BITS;
1334 _fixed t;
1335
1336 /* give numerator 16 significant bits over denominator and then calculate t==n/d; MPW�s PPCC
1337 didn�t seem to like (INT32_MIN>>1) and i had to substitute 0xc0000000 instead (hmmm) */
1338 while (numerator<=(int32)0x3fffffff && numerator>=(int32)0xc0000000 && shift_count--) numerator<<= 1;
1339 if (shift_count>0) denominator>>= shift_count;
1340 t = numerator;
1341 if (denominator)
1342 t /= denominator;
1343
1344 /* calculate the clipped point */
1345 clipped->x = local_p0->x + FIXED_INTEGERAL_PART(int32(1LL*t*dx));
1346 clipped->y = local_p0->y + FIXED_INTEGERAL_PART(int32(1LL*t*dy));
1347 clipped->z = local_p0->z + FIXED_INTEGERAL_PART(int32(1LL*t*dz));
1348 clipped->flags= local_p0->flags&local_p1->flags;
1349 }
1350