/******************************************************************************* * apps/graphics/traveler/src/trv_rayprune.c * * Copyright (C) 2014 Gregory Nutt. All rights reserved. * Author: Gregory Nutt * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * 3. Neither the name NuttX nor the names of its contributors may be * used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. * ****************************************************************************/ /**************************************************************************** * Included files ****************************************************************************/ #include "trv_types.h" #include "trv_world.h" #include "trv_plane.h" #include "trv_trigtbl.h" #include "trv_raycast.h" #include "trv_rayprune.h" /**************************************************************************** * Pre-processor Definitions ****************************************************************************/ /* These definitions are used to decompose a range of angles into quadrants */ #define START0 0x0001 #define STARTQ1 0x0002 #define START90 0x0004 #define STARTQ2 0x0008 #define START180 0x0010 #define STARTQ3 0x0020 #define START270 0x0040 #define STARTQ4 0x0080 #define END0 0x0100 #define ENDQ1 0x0200 #define END90 0x0400 #define ENDQ2 0x0800 #define END180 0x1000 #define ENDQ3 0x2000 #define END270 0x4000 #define ENDQ4 0x8000 #define S0EQ1 (START0|ENDQ1) #define SQ1EQ1 (STARTQ1|ENDQ1) #define SQ1E90 (STARTQ1|END90) #define SQ1EQ2 (STARTQ1|ENDQ2) #define S90EQ2 (START90|ENDQ2) #define SQ2EQ2 (STARTQ2|ENDQ2) #define SQ2E180 (STARTQ2|END180) #define SQ2EQ3 (STARTQ2|ENDQ3) #define S180EQ3 (START180|ENDQ3) #define SQ3EQ3 (STARTQ3|ENDQ3) #define SQ3E270 (STARTQ3|END270) #define SQ3EQ4 (STARTQ3|ENDQ4) #define S270EQ4 (START270|ENDQ4) #define SQ4EQ4 (STARTQ4|ENDQ4) #define SQ4E0 (STARTQ4|END0) #define SQ4EQ1 (STARTQ4|ENDQ1) /**************************************************************************** * Private Type Declarations ***************************************************************************/ enum working_plane_state_e { WEMPTY = 0, WTOP, WBOTTOM }; /**************************************************************************** * Private Function Prototypes ****************************************************************************/ static void trv_ray_yawxprune_14cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawxprune_14ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawxprune_23cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawxprune_23ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawyprune_12cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawyprune_12ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawyprune_34cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_yawyprune_34ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_mkplanelist(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw); static void trv_ray_selectupper(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist); static void trv_ray_selectlower(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist); /**************************************************************************** * Public Data ****************************************************************************/ struct trv_rect_head_s g_ray_xplane; /* List of X=plane rectangles */ struct trv_rect_head_s g_ray_yplane; /* List of Y=plane rectangles */ struct trv_rect_head_s g_ray_zplane; /* List of Z=plane rectangles */ /**************************************************************************** * Private Data ****************************************************************************/ static enum working_plane_state_e g_working_planestate; static struct trv_rect_head_s g_working_xplane; /* List of X=plane rectangles */ static struct trv_rect_head_s g_working_yplane; /* List of Y=plane rectangles */ static struct trv_rect_head_s g_candidate_xplane; /* List of X=plane rectangles */ static struct trv_rect_head_s g_candidate_yplane; /* List of Y=plane rectangles */ static struct trv_rect_head_s g_candidate_zplane; /* List of Z=plane rectangles */ static struct trv_rect_head_s g_discard_xplane; /* List of discarded X=plane * rectangles */ static struct trv_rect_head_s g_discard_yplane; /* List of discarded Y=plane * rectangles */ static struct trv_rect_head_s g_discard_zplane; /* List of discarded Z=plane * rectangles */ /**************************************************************************** * Private Functions ****************************************************************************/ /**************************************************************************** * Name: trv_ray_yawxprune_14cw * * Description: * This function casts a ray along the Y-Axis looking at points of * intersection on the X-Axis. We are pointed toward in the "right" half * of the view. The X ray cast will proceed positively along the X axis. * Every plane in the input plane list that lies to the "right" of the * camera position and "clockwise" of the current yaw is moved into * the output X plane list. * ***************************************************************************/ static void trv_ray_yawxprune_14cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current X plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next X plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t relx; /* Relative position of the X plane */ trv_coord_t absy; /* Absolute Y position at relx given yaw */ trv_coord_t lastrelx = -1; /* Last relative X position processed */ int32_t dydx; /* Rate of change of Y wrt X (double) */ /* Pre-calculate the rate of change of Y with respect to X */ /* The tangent is equal to the rate of change of Y with respect to the * X-axis. The tangent is stored at double the "normal" scaling. */ dydx = TAN(yaw); /* Look at every rectangle lying in the X plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->head; (entry); entry = next) { next = entry->flink; rect = &entry->d; /* Search for a rectangle which lies "beyond" the current camera * position */ if (rect->plane > g_camera.x) { /* Get the X distance to the plane */ relx = rect->plane - g_camera.x; /* Calculate the Y position at this relative X position. We can * skip this step if we are processing another rectangle at the * same relx distance. */ if (relx != lastrelx) { int32_t deltay; /* Scale == "triple" */ /* The dydx is stored at double the"normal" scaling -- so deltay * is "triple" precision */ deltay = dydx * ((int32_t) relx); absy = tTOs(deltay) + g_camera.y; /* back to "single" */ lastrelx = relx; } /* Check if any part of this plane lies clockwise from this Y * position. In quadrants 1 & 4, clockwise corresponds to smaller Y * values */ if (absy >= rect->hstart) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: trv_ray_yawxprune_14ccw * * Description: * This function casts a ray along the Y-Axis looking at points of * intersection on the X-Axis. We are pointed toward in the "right" half * of the view. The X ray cast will proceed positively along the X axis. * Every plane in the input plane list that lies to the "right" of the * camera position and "counterclockwise" of the current yaw is moved into * the output X plane list. * ***************************************************************************/ static void trv_ray_yawxprune_14ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current X plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next X plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t relx; /* Relative position of the X plane */ trv_coord_t absy; /* Absolute Y position at relx given yaw */ trv_coord_t lastrelx = -1; /* Last relative X position processed */ int32_t dydx; /* Rate of change of Y wrt X (double) */ /* Pre-calculate the rate of change of Y with respect to X */ /* The tangent is equal to the rate of change of Y with respect to the * X-axis. The tangent is stored at double the "normal" scaling. */ dydx = TAN(yaw); /* Look at every rectangle lying in the X plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->head; (entry); entry = next) { next = entry->flink; rect = &entry->d; /* Search for a rectangle which lies "beyond" the current camera * position */ if (rect->plane > g_camera.x) { /* Get the X distance to the plane */ relx = rect->plane - g_camera.x; /* Calculate the Y position at this relative X position. We can * skip this step if we are processing another rectangle at the * same relx distance. */ if (relx != lastrelx) { int32_t deltay; /* Scale == "triple" */ /* The dydx is stored at double the"normal" scaling -- so deltay * is "triple" precision */ deltay = dydx * ((int32_t) relx); absy = tTOs(deltay) + g_camera.y; /* back to "single" */ lastrelx = relx; } /* Check if any part of this plane lies counterclockwise from this Y * position. In quadrants 1 & 4, counterclockwise corresponds to * larger Y values */ if (absy <= rect->hend) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: rayYawYPrune23CW * * Description: * This function casts a ray along the Y-Axis looking at points of * intersection on the X-Axis. We are pointed toward in the "left" half * of the view. The X ray cast will proceed negatively along the X axis. * Every plane in the input X plane list that lies to the "left" of the * camera position and "clockwise" of the current yaw is moved into * the output X plane list. * ***************************************************************************/ static void trv_ray_yawxprune_23cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current X plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next X plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t relx; /* Relative position of the X plane */ trv_coord_t absy; /* Absolute Y position at relx given yaw */ trv_coord_t lastrelx = -1; /* Last relative X position processed */ int32_t dydx; /* Rate of change of Y wrt X (double) */ /* Pre-calculate the rate of change of Y with respect to X */ /* The negative tangent is equal to the rate of change of Y with respect * to the X-axis. The tangent is stored at double the "normal" scaling. */ dydx = -TAN(yaw); /* Look at every rectangle lying in the X plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->tail; (entry); entry = next) { next = entry->blink; rect = &entry->d; /* Search for a rectangle which lies "before" the current camera * position */ if (rect->plane < g_camera.x) { /* Get the X distance to the plane */ relx = g_camera.x - rect->plane; /* Calculate the Y position at this relative X position. We can * skip this step if we are processing another rectangle at the * same relx distance. */ if (relx != lastrelx) { int32_t deltay; /* Scale == "triple" */ /* The dydx is stored at double the"normal" scaling -- so deltay * is "triple" precision */ deltay = dydx * ((int32_t) relx); absy = tTOs(deltay) + g_camera.y; /* back to "single" */ lastrelx = relx; } /* Check if any part of this plane lies clockwise from this Y * position. In quadrants 2 & 3, clockwise corresponds to larger Y * values */ if (absy <= rect->hend) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: rayYawYPrune23CCW * * Description: * This function casts a ray along the Y-Axis looking at points of * intersection on the X-Axis. We are pointed toward in the "left" half * of the view. The X ray cast will proceed negatively along the X axis. * Every plane in the input X plane list that lies to the "left" of the * camera position and "counterclockwise" of the current yaw is moved * into the output X plane list. * ***************************************************************************/ static void trv_ray_yawxprune_23ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current X plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next X plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t relx; /* Relative position of the X plane */ trv_coord_t absy; /* Absolute Y position at relx given yaw */ trv_coord_t lastrelx = -1; /* Last relative X position processed */ int32_t dydx; /* Rate of change of Y wrt X (double) */ /* Pre-calculate the rate of change of Y with respect to X */ /* The negative tangent is equal to the rate of change of Y with respect * to the X-axis. The tangent is stored at double the "normal" scaling. */ dydx = -TAN(yaw); /* Look at every rectangle lying in the X plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->tail; (entry); entry = next) { next = entry->blink; rect = &entry->d; /* Search for a rectangle which lies "before" the current camera * position */ if (rect->plane < g_camera.x) { /* Get the X distance to the plane */ relx = g_camera.x - rect->plane; /* Calculate the Y position at this relative X position. We can * skip this step if we are processing another rectangle at the * same relx distance. */ if (relx != lastrelx) { int32_t deltay; /* Scale == "triple" */ /* The dydx is stored at double the"normal" scaling -- so deltay * is "triple" precision */ deltay = dydx * ((int32_t) relx); absy = tTOs(deltay) + g_camera.y; /* back to "single" */ lastrelx = relx; } /* Check if any part of this plane lies counterclockwise from this Y * position. In quadrants 2 & 3, counterclockwise corresponds to * smaller Y values */ if (absy >= rect->hstart) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: trv_ray_yawyprune_12cw * * Description: * This function casts a ray along the X-Axis looking at points of * intersection on the Y-Axis. We are pointed toward in the "forward" half * of the view. The Y ray cast will proceed positively along the Y axis. * Every plane in the input plane list that lies to the "forward" of the * camera position and "clockwise" of the current yaw is moved into * the output Y plane list. * ***************************************************************************/ static void trv_ray_yawyprune_12cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current Y plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next Y plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t rely; /* Relative position of the Y plane */ trv_coord_t absx; /* Absolute X position at rely given yaw */ trv_coord_t lastrely = -1; /* Last relative Y position processed */ int32_t dxdy; /* Rate of change of X wrt Y (double) */ /* Pre-calculate the rate of change of X with respect to Y */ /* The inverted tangent is equal to the rate of change of X with respect * to the Y-axis. The cotangent is stored at double the the "normal" * scaling. */ dxdy = g_cot_table(yaw); /* Look at every rectangle lying in the Y plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->head; (entry); entry = next) { next = entry->flink; rect = &entry->d; /* Search for a rectangle which lies "beyond" the current camera * position */ if (rect->plane > g_camera.y) { /* Get the Y distance to the plane */ rely = rect->plane - g_camera.y; /* Calculate the X position at this relative Y position. We can * skip this step if we are processing another rectangle at the * same rely distance. */ if (rely != lastrely) { int32_t deltax; /* Scale == "triple" */ /* The dxdy is stored at double the"normal" scaling -- so deltax * is "triple" precision */ deltax = dxdy * ((int32_t) rely); absx = tTOs(deltax) + g_camera.x; /* back to "single" */ lastrely = rely; } /* Check if any part of this plane lies clockwise from this X * position. In quadrants 1 & 2, clockwise corresponds to larger * X values */ if (absx <= rect->hend) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: trv_ray_yawyprune_12ccw * * Description: * This function casts a ray along the X-Axis looking at points of * intersection on the Y-Axis. We are pointed toward in the "forward" half * of the view. The Y ray cast will proceed positively along the Y axis. * Every plane in the input plane list that lies to the "forward" of the * camera position and "counterclockwise" of the current yaw is moved into * the output Y plane list. * ***************************************************************************/ static void trv_ray_yawyprune_12ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current Y plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next Y plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t rely; /* Relative position of the Y plane */ trv_coord_t absx; /* Absolute X position at rely given yaw */ trv_coord_t lastrely = -1; /* Last relative Y position processed */ int32_t dxdy; /* Rate of change of X wrt Y (double) */ /* Pre-calculate the rate of change of X with respect to Y */ /* The inverted tangent is equal to the rate of change of X with respect * to the Y-axis. The cotangent is stored at double the the "normal" * scaling. */ dxdy = g_cot_table(yaw); /* Look at every rectangle lying in the Y plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->head; (entry); entry = next) { next = entry->flink; rect = &entry->d; /* Search for a rectangle which lies "beyond" the current camera * position */ if (rect->plane > g_camera.y) { /* Get the Y distance to the plane */ rely = rect->plane - g_camera.y; /* Calculate the X position at this relative Y position. We can * skip this step if we are processing another rectangle at the * same rely distance. */ if (rely != lastrely) { int32_t deltax; /* Scale == "triple" */ /* The dxdy is stored at double the"normal" scaling -- so * deltax is "triple" precision */ deltax = dxdy * ((int32_t) rely); absx = tTOs(deltax) + g_camera.x; /* back to "single" */ lastrely = rely; } /* Check if any part of this plane lies counterclockwise from this * X position. In quadrants 1 & 2, counterclockwise corresponds * to smaller X values */ if (absx >= rect->hstart) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: trv_ray_yawyprune_34cw * * Description: * This function casts a ray along the X-Axis looking at points of * intersection on the Y-Axis. We are pointed toward in the "back" half * of the view. The Y ray cast will proceed negatively along the Y axis. * Every plane in the input plane list that lies to the "back" of the * camera position and "clockwise" of the current yaw is moved into * the output Y plane list. * ***************************************************************************/ static void trv_ray_yawyprune_34cw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current Y plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next Y plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t rely; /* Relative position of the Y plane */ trv_coord_t absx; /* Absolute X position at rely given yaw */ trv_coord_t lastrely = -1; /* Last relative Y position processed */ int32_t dxdy; /* Rate of change of X wrt Y (double) */ /* Pre-calculate the rate of change of X with respect to Y */ /* The negative inverted tangent is equal to the rate of change of X with * respect to the Y-axis. The cotangent is stored at double the the * "normal" scaling. */ dxdy = -g_cot_table(yaw - ANGLE_180); /* Look at every rectangle lying in the Y plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->tail; (entry); entry = next) { next = entry->blink; rect = &entry->d; /* Search for a rectangle which lies "before" the current camera * position */ if (rect->plane < g_camera.y) { /* Get the Y distance to the plane */ rely = g_camera.y - rect->plane; /* Calculate the X position at this relative Y position. We can skip * this step if we are processing another rectangle at the same rely * distance. */ if (rely != lastrely) { int32_t deltax; /* Scale == "triple" */ /* The dxdy is stored at double the"normal" scaling -- so * deltax is "triple" precision */ deltax = dxdy * ((int32_t) rely); absx = tTOs(deltax) + g_camera.x; /* back to "single" */ lastrely = rely; } /* Check if any part of this plane lies clockwise from this X * position. In quadrants 3 & 4, clockwise corresponds to * smaller X values */ if (absx >= rect->hstart) { /* Remove the plane from the input plane list and add it to * the output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: trv_ray_yawyprune_34ccw * * Description: * This function casts a ray along the X-Axis looking at points of * intersection on the Y-Axis. We are pointed toward in the "back" half * of the view. The Y ray cast will proceed negatively along the Y axis. * Every plane in the input plane list that lies to the "back" of the * camera position and "counterclockwise" of the current yaw is moved * into the output Y plane list. * ***************************************************************************/ static void trv_ray_yawyprune_34ccw(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t yaw) { FAR struct trv_rect_list_s *entry; /* Points to the current Y plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next Y plane * rectangle */ FAR struct trv_rect_data_s *rect; /* Points to the rectangle data */ trv_coord_t rely; /* Relative position of the Y plane */ trv_coord_t absx; /* Absolute X position at rely given yaw */ trv_coord_t lastrely = -1; /* Last relative Y position processed */ int32_t dxdy; /* Rate of change of X wrt Y (double) */ /* Pre-calculate the rate of change of X with respect to Y */ /* The negative inverted tangent is equal to the rate of change of X with * respect to the Y-axis. The cotangent is stored at double the the * "normal" scaling. */ dxdy = -g_cot_table(yaw - ANGLE_180); /* Look at every rectangle lying in the Y plane */ /* This logic should be improved at some point so that non-visible planes * are "pruned" from the list prior to ray casting! */ for (entry = inlist->tail; (entry); entry = next) { next = entry->blink; rect = &entry->d; /* Search for a rectangle which lies "before" the current camera * position */ if (rect->plane < g_camera.y) { /* Get the Y distance to the plane */ rely = g_camera.y - rect->plane; /* Calculate the X position at this relative Y position. We can * skip this step if we are processing another rectangle at the * same rely distance. */ if (rely != lastrely) { int32_t deltax; /* Scale == "triple" */ /* The dxdy is stored at double the"normal" scaling -- so * deltax is "triple" precision */ deltax = dxdy * ((int32_t) rely); absx = tTOs(deltax) + g_camera.x; /* back to "single" */ lastrely = rely; } /* Check if any part of this plane lies counterclockwise from this X * position. In quadrants 3 & 4, counterclockwise corresponds to * larger X values */ if (absx <= rect->hend) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } } /**************************************************************************** * Name: trv_ray_mkplanelist * * Description: * This function creates a "fake" plane list based on the current working * plane list. The "head" of the "fake" plane list points to the first * entry "beyond" the current camera position; the "tail" point to the * first plane "before" the current position. * ****************************************************************************/ static void trv_ray_mkplanelist(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist, int16_t pos) { FAR struct trv_rect_list_s *list; /* Points to the current plane rectangle */ /* Look at every rectangle lying in the specified "in" plane starting at * the beginning of the list. */ outlist->head = NULL; for (list = inlist->head; list; list = list->flink) { /* Search for the first rectangle which lies "beyond" the current * camera position */ if (list->d.plane > pos) { outlist->head = list; break; } } /* Look at every rectangle lying in the specified "in" plane starting at * the end of the list */ outlist->tail = NULL; for (list = inlist->tail; list; list = list->blink) { /* Search for the first rectangle which lies "before" the current * camera position */ if (list->d.plane < pos) { outlist->tail = list; break; } } } /**************************************************************************** * Name: trv_ray_selectupper * * Description: * Transfer each plane that lies (at least in part) above the level viewing * angle from the inlist to the outlist). * ****************************************************************************/ static void trv_ray_selectupper(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist) { FAR struct trv_rect_list_s *entry; /* Points to the current Y plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next Y plane * rectangle */ /* Look at every rectangle lying in the inlist */ for (entry = inlist->head; (entry); entry = next) { next = entry->flink; /* If the "top" of the rectangle lies above the camera Z level, then * some (or all) of the rectangle is above the level viewing angle. */ if (entry->d.vend >= g_camera.z) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } /**************************************************************************** * Name: trv_ray_selectlower * * Description: * Transfer each plane that lies (at least in part) above the level viewing * angle from the inlist to the outlist). * ****************************************************************************/ static void trv_ray_selectlower(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist) { FAR struct trv_rect_list_s *entry; /* Points to the current Y plane * rectangle */ FAR struct trv_rect_list_s *next; /* Points to the next Y plane * rectangle */ /* Look at every rectangle lying in the inlist */ for (entry = inlist->head; (entry); entry = next) { next = entry->flink; /* If the "bottom" of the rectangle lies below the camera Z level, then * some (or all) of the rectangle is above the level viewing angle. */ if (entry->d.vstart < g_camera.z) { /* Remove the plane from the input plane list and add it to the * output plane list */ trv_move_plane(entry, outlist, inlist); } } } /**************************************************************************** * Public Functions ****************************************************************************/ /**************************************************************************** * Name: trv_ray_yawprune * * Description: * This function may be called at the beginning of each rending cycle to * prepare ray casting data. This function "prunes" out all planes that * may be visible in the specified yaw range. * ****************************************************************************/ void trv_ray_yawprune(int16_t yawstart, int16_t yawend) { uint16_t quadrants; /* Nullify the working plane lists */ g_working_xplane.head = g_working_xplane.tail = NULL; g_working_xplane.head = g_working_xplane.tail = NULL; g_working_planestate = WEMPTY; /* Nullify the candidate plane lists */ g_candidate_xplane.head = g_candidate_xplane.tail = NULL; g_candidate_yplane.head = g_candidate_yplane.tail = NULL; g_candidate_zplane.head = g_candidate_zplane.tail = NULL; /* Nullify the discard plane lists */ g_discard_xplane.head = g_discard_xplane.tail = NULL; g_discard_yplane.head = g_discard_yplane.tail = NULL; g_discard_zplane.head = g_discard_zplane.tail = NULL; /* Determine the quadrant(s) spanned by yawstart and yawend */ if (yawstart == ANGLE_0) { quadrants = START0; } else if (yawstart < ANGLE_90) { quadrants = STARTQ1; } else if (yawstart == ANGLE_90) { quadrants = START90; } else if (yawstart < ANGLE_180) { quadrants = STARTQ2; } else if (yawstart == ANGLE_180) { quadrants = START180; } else if (yawstart < ANGLE_270) { quadrants = STARTQ3; } else if (yawstart == ANGLE_270) { quadrants = START270; } else { quadrants = STARTQ4; } if (yawend == ANGLE_0) { quadrants |= END0; } else if (yawend < ANGLE_90) { quadrants |= ENDQ1; } else if (yawend == ANGLE_90) { quadrants |= END90; } else if (yawend < ANGLE_180) { quadrants |= ENDQ2; } else if (yawend == ANGLE_180) { quadrants |= END180; } else if (yawend < ANGLE_270) { quadrants |= ENDQ3; } else if (yawend == ANGLE_270) { quadrants |= END270; } else { quadrants |= ENDQ4; } /* Now, perform the pruning based upon the quadrant(s) spanned by yawstart * and yawend */ switch (quadrants) { case S0EQ1: trv_ray_yawxprune_14ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_yplane, yawend); break; case SQ1EQ1: trv_ray_yawxprune_14ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_12ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ1E90: trv_ray_yawxprune_14ccw(&g_candidate_xplane, &g_xplane, yawstart); trv_ray_yawyprune_12ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ1EQ2: trv_ray_yawxprune_14ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_xplane, yawend); trv_merge_planelists(&g_candidate_xplane, &g_discard_xplane); trv_ray_yawyprune_12ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case S90EQ2: trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_xplane, yawend); trv_ray_yawyprune_12ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ2EQ2: trv_ray_yawxprune_23ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_12ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ2E180: trv_ray_yawxprune_23ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_12ccw(&g_candidate_yplane, &g_yplane, yawstart); break; case SQ2EQ3: trv_ray_yawxprune_23ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_12ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_yplane, yawend); trv_merge_planelists(&g_candidate_yplane, &g_discard_yplane); break; case S180EQ3: trv_ray_yawxprune_23ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_yplane, yawend); break; case SQ3EQ3: trv_ray_yawxprune_23ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_23cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_34ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ3E270: trv_ray_yawxprune_23ccw(&g_candidate_xplane, &g_xplane, yawend); trv_ray_yawyprune_34ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ3EQ4: trv_ray_yawxprune_23ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_xplane, yawend); trv_merge_planelists(&g_candidate_xplane, &g_discard_xplane); trv_ray_yawyprune_34ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case S270EQ4: trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_xplane, yawend); trv_ray_yawyprune_34ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ4EQ4: trv_ray_yawxprune_14ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_34ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_34cw(&g_candidate_yplane, &g_discard_yplane, yawend); break; case SQ4E0: trv_ray_yawxprune_14ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_34ccw(&g_candidate_yplane, &g_yplane, yawstart); break; case SQ4EQ1: trv_ray_yawxprune_14ccw(&g_discard_xplane, &g_xplane, yawstart); trv_ray_yawxprune_14cw(&g_candidate_xplane, &g_discard_xplane, yawend); trv_ray_yawyprune_34ccw(&g_discard_yplane, &g_yplane, yawstart); trv_ray_yawyprune_12cw(&g_candidate_yplane, &g_yplane, yawend); trv_merge_planelists(&g_candidate_yplane, &g_discard_yplane); break; default: /* No other combination should occur if the range is < 90 deg */ break; } /* Create the special plane lists for the raycaster */ trv_ray_mkplanelist(&g_ray_xplane, &g_candidate_xplane, g_camera.x); trv_ray_mkplanelist(&g_ray_yplane, &g_candidate_yplane, g_camera.y); trv_ray_mkplanelist(&g_ray_zplane, &g_zplane, g_camera.z); } /**************************************************************************** * Name: trv_ray_pitchprune * * Description: * This function may be called at each "horizontal" pitch swathe to * prepare ray casting data. This function "prunes" out all planes that * may be visible in the specified pitch range. * ****************************************************************************/ void trv_ray_pitchprune(int16_t pitchstart, int16_t pitchend) { /* Check the current pitch range */ if (pitchend <= ANGLE_180) { /* The entire view is in the upper hemisphere */ if (g_working_planestate != WTOP) { if (g_working_planestate == WBOTTOM) { /* Merge the workingPlane lists with the candidate plane lists */ trv_merge_planelists(&g_candidate_xplane, &g_working_xplane); trv_merge_planelists(&g_candidate_yplane, &g_working_yplane); } /* Select the rectangles which lie above the level line of sight */ trv_ray_selectupper(&g_working_xplane, &g_candidate_xplane); trv_ray_selectupper(&g_working_yplane, &g_candidate_yplane); /* Create the special plane lists for the raycaster */ trv_ray_mkplanelist(&g_ray_xplane, &g_working_xplane, g_camera.x); trv_ray_mkplanelist(&g_ray_yplane, &g_working_yplane, g_camera.y); g_working_planestate = WTOP; } } else if (pitchstart <= ANGLE_180) { /* The view is split between the upper and lower hemispheres */ if (g_working_planestate != WEMPTY) { /* Merge the workingPlane lists with the candidate plane lists */ trv_merge_planelists(&g_candidate_xplane, &g_working_xplane); trv_merge_planelists(&g_candidate_yplane, &g_working_yplane); /* Create the special plane lists for the raycaster */ trv_ray_mkplanelist(&g_ray_xplane, &g_candidate_xplane, g_camera.x); trv_ray_mkplanelist(&g_ray_yplane, &g_candidate_yplane, g_camera.y); g_working_planestate = WEMPTY; } } else { /* The entire view is in the lower hemisphere */ if (g_working_planestate != WBOTTOM) { if (g_working_planestate == WTOP) { /* Merge the workingPlane lists with the candidate plane lists */ trv_merge_planelists(&g_candidate_xplane, &g_working_xplane); trv_merge_planelists(&g_candidate_yplane, &g_working_yplane); } /* Select the rectangles which lie below the level line of sight */ trv_ray_selectlower(&g_working_xplane, &g_candidate_xplane); trv_ray_selectlower(&g_working_yplane, &g_candidate_yplane); /* Create the special plane lists for the raycaster */ trv_ray_mkplanelist(&g_ray_xplane, &g_working_xplane, g_camera.x); trv_ray_mkplanelist(&g_ray_yplane, &g_working_yplane, g_camera.y); g_working_planestate = WBOTTOM; } } } /**************************************************************************** * Name: trv_ray_pitchunprune * * Description: * This function may be called at the end of each rending cycle to * restore the environment which was perturbed by trv_ray_pitchprune. * ****************************************************************************/ void trv_ray_pitchunprune(void) { } /**************************************************************************** * Name: trv_ray_yawunprune * * Description: * This function may be called at the end of each rending cycle to * restore the environment which was perturbed by trv_ray_yawprune. * ****************************************************************************/ void trv_ray_yawunprune(void) { /* Merge the working X plane list with the discarded X plane list */ trv_merge_planelists(&g_discard_xplane, &g_working_xplane); /* Merge the candidate X plane list with the discarded X plane list */ trv_merge_planelists(&g_discard_xplane, &g_candidate_xplane); /* Merge the discarded X plane list with the original "raw" X plane list */ trv_merge_planelists(&g_xplane, &g_discard_xplane); /* Merge the working Y plane list with the discarded Y plane list */ trv_merge_planelists(&g_discard_yplane, &g_working_yplane); /* Merge the candidate X plane list with the discarded X plane list */ trv_merge_planelists(&g_discard_yplane, &g_candidate_yplane); /* Merge the discarded Y plane list with the original "raw" Y plane list */ trv_merge_planelists(&g_yplane, &g_discard_yplane); }