From 0aae446c231bb6382ecbac30505a0166a95a098c Mon Sep 17 00:00:00 2001 From: Gregory Nutt Date: Sat, 6 Dec 2014 12:00:25 -0600 Subject: Add more plan management logic --- apps/graphics/traveler/Makefile | 4 +- apps/graphics/traveler/include/trv_plane.h | 10 +- apps/graphics/traveler/src/trv_loadplanes.c | 147 ------------ apps/graphics/traveler/src/trv_plane.c | 300 ------------------------- apps/graphics/traveler/src/trv_planefiles.c | 183 +++++++++++++++ apps/graphics/traveler/src/trv_planelists.c | 331 ++++++++++++++++++++++++++++ 6 files changed, 524 insertions(+), 451 deletions(-) delete mode 100644 apps/graphics/traveler/src/trv_loadplanes.c delete mode 100644 apps/graphics/traveler/src/trv_plane.c create mode 100644 apps/graphics/traveler/src/trv_planefiles.c create mode 100644 apps/graphics/traveler/src/trv_planelists.c (limited to 'apps/graphics') diff --git a/apps/graphics/traveler/Makefile b/apps/graphics/traveler/Makefile index 91840fed2..5f66d75f4 100644 --- a/apps/graphics/traveler/Makefile +++ b/apps/graphics/traveler/Makefile @@ -47,8 +47,8 @@ STACKSIZE = 2048 ASRCS = CSRCS = trv_bitmaps.c trv_color.c trv_createworld.c trv_doors.c -CSRCS += trv_graphics.c trv_input.c trv_loadplanes.c trv_mem.c -CSRCS += trv_plane.c trv_pov.c trv_rayavoid.c trv_raycast.c +CSRCS += trv_graphics.c trv_input.c trv_mem.c trv_planefiles.c +CSRCS += trv_planelists.c trv_pov.c trv_rayavoid.c trv_raycast.c CSRCS += trv_raycntl.c trv_rayprune.c trv_rayrend.c trv_trigtbl.c MAINSRC = trv_main.c diff --git a/apps/graphics/traveler/include/trv_plane.h b/apps/graphics/traveler/include/trv_plane.h index 57a1adf1d..936fc4e9e 100644 --- a/apps/graphics/traveler/include/trv_plane.h +++ b/apps/graphics/traveler/include/trv_plane.h @@ -139,6 +139,8 @@ extern struct trv_rect_list_s *g_rect_freelist; * Public Function Prototypes ****************************************************************************/ +/* Plane list management */ + int trv_initialize_planes(void); void trv_add_plane(FAR struct trv_rect_list_s *rect, FAR struct trv_rect_head_s *list); @@ -149,9 +151,13 @@ void trv_merge_planelists(FAR struct trv_rect_head_s *outlist, FAR struct trv_rect_head_s *inlist); void trv_release_planes(void); +/* Plane memory management */ + +FAR struct trv_rect_list_s *trv_new_plane(void); + +/* Plane file management */ + int trv_load_planefile(FAR const char *wldfile); -int trv_load_planes(FAR FILE *fp); int trv_save_planes(const char *wldfile); -FAR struct trv_rect_list_s *trv_new_plane(void); #endif /* __APPS_GRAPHICS_TRAVELER_INCLUDE_TRV_PLANE_H */ diff --git a/apps/graphics/traveler/src/trv_loadplanes.c b/apps/graphics/traveler/src/trv_loadplanes.c deleted file mode 100644 index a57fb5105..000000000 --- a/apps/graphics/traveler/src/trv_loadplanes.c +++ /dev/null @@ -1,147 +0,0 @@ -/******************************************************************************* - * apps/graphics/traveler/src/trv_loadplanes.c - * This file contains the logic to load the world data from the opened file - * - * 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_plane.h" - -#include -#include - -/**************************************************************************** - * Definitions - ****************************************************************************/ - -/**************************************************************************** - * Private Type Declarations - ***************************************************************************/ - -/**************************************************************************** - * Private Functions - ****************************************************************************/ - -/**************************************************************************** - * Name: trv_load_worldplane - * - * Description: - * - * This function loads the world data for one plane - * - ***************************************************************************/ - -static int trv_load_worldplane(FAR FILE *fp, FAR struct trv_rect_head_s *head, - uint8_t nrects) -{ - FAR struct trv_rect_list_s *rect; - int ret; - int i; - - for (i = 0; i < nrects; i++) - { - /* Allocate space for the next rectangle */ - - rect = trv_new_plane(); - if (!rect) - { - return -ENOMEM; - } - - /* Read the next rectangle from the input file */ - - ret = fread((char*)&rect->d, RESIZEOF_TRVRECTDATA_T, 1, fp); - if (ret != 1) - { - int errcode = errno; - fprintf(stderr, "Error: read of rectangle %d (of %d) failed\n", - i, nrects); - fprintf(stderr, "feof=%d ferror=%d errno=%d\n", - feof(fp), ferror(fp), errcode); - return -errcode; - } - - /* Put the new rectangle into the plane list */ - - trv_add_plane(rect, head); - } - - return OK; -} - -/**************************************************************************** - * Public Functions - ****************************************************************************/ - -/**************************************************************************** - * Function: trv_load_planes - * Description: - * This function loads the world data from the opened file - ***************************************************************************/ - -int trv_load_planes(FAR FILE *fp) -{ - struct trv_planefile_header_s header; - int ret; - - /* Read the plane file header */ - - ret = fread((char*)&header, SIZEOF_TRVPLANEFILEHEADER_T, 1, fp); - if (ret != 1) - { - int errcode = errno; - fprintf(stderr, "Error: Failed to read of file header\n"); - fprintf(stderr, "feof=%d ferror=%d errno=%d\n", - feof(fp), ferror(fp), errcode); - return -errcode; - } - - /* Then load each grid, performing run length (rle) decoding */ - - ret = trv_load_worldplane(fp, &g_xplane, header.nxrects); - if (ret == OK) - { - ret = trv_load_worldplane(fp, &g_yplane, header.nyrects); - } - - if (ret == OK) - { - ret = trv_load_worldplane(fp, &g_zplane, header.nzrects); - } - - return ret; -} diff --git a/apps/graphics/traveler/src/trv_plane.c b/apps/graphics/traveler/src/trv_plane.c deleted file mode 100644 index 7337c482d..000000000 --- a/apps/graphics/traveler/src/trv_plane.c +++ /dev/null @@ -1,300 +0,0 @@ -/******************************************************************************* - * apps/graphics/traveler/src/trv_plane.c - * This file contains the global variable declarations needed by the world - * plane management logic. - * - * 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_plane.h" - -/**************************************************************************** - * Public Data - ****************************************************************************/ - -/* The is the world!!! The world is described by lists of rectangles, one - * for each of the X, Y, and Z planes. - */ - -struct trv_rect_head_s g_xplane; /* list of X=plane rectangles */ -struct trv_rect_head_s g_yplane; /* list of Y=plane rectangles */ -struct trv_rect_head_s g_zplane; /* list of Z=plane rectangles */ - -/* "Deallocated" planes are retained in a free list */ - -struct trv_rect_list_s *g_rect_freelist; - -/**************************************************************************** - * Public Functions - ****************************************************************************/ - -/**************************************************************************** - * Name: trv_initialize_planes - * - * Description: - * - ***************************************************************************/ - -int trv_initialize_planes(void) -{ - g_xplane.head = NULL; - g_xplane.tail = NULL; - g_yplane.head = NULL; - g_yplane.tail = NULL; - g_zplane.head = NULL; - g_zplane.tail = NULL; - g_rect_freelist = NULL; - - return OK; -} - -/**************************************************************************** - * Name: trv_add_plane - * - * Description: - * This function adds a plane to a world plane list - * - ***************************************************************************/ - -void trv_add_plane(FAR struct trv_rect_list_s *rect, - FAR struct trv_rect_head_s *list) -{ - struct trv_rect_list_s *next; - struct trv_rect_list_s *prev; - - /* Search the list to find the location to insert the new rectangle. Each - * is list is maintained in ascending plane order. - */ - - for (next = list->head; - ((next) && (next->d.plane < rect->d.plane)); - next = next->flink); - - /* Add the 'rect' to the spot found in the list. Check if the 'rect' lies - * at the end of the list. - */ - - if (!next) - { - /* No rectangle with plane larger than the one to be added was found - * in the list. The 'rect' goes at the end of the list. - */ - - prev = list->tail; - if (!prev) - { - /* Special case: The list is empty */ - - rect->flink = NULL; - rect->blink = NULL; - list->head = rect; - list->tail = rect; - } - else - { - rect->flink = NULL; - rect->blink = prev; - prev->flink = rect; - list->tail = rect; - } - } - else - { - /* The 'rect' goes just before 'next' */ - - prev = next->blink; - if (!prev) - { - /* Special case: Insert at the head of the list */ - - rect->flink = next; - rect->blink = NULL; - next->blink = rect; - list->head = rect; - } - else - { - /* Insert in the middle of the list */ - - rect->flink = next; - rect->blink = prev; - prev->flink = rect; - next->blink = rect; - } - } -} - -/**************************************************************************** - * Name: trv_move_plane - * - * Description: - * - * This function removes the specified plane from the world plane srclist - * then adds it to the world plane destlist - * - ***************************************************************************/ - -void trv_move_plane(FAR struct trv_rect_list_s *rect, - FAR struct trv_rect_head_s *destlist, - FAR struct trv_rect_head_s *srclist) -{ - /* Un-hook the backward link to the rect */ - - if (rect->flink) - { - rect->flink->blink = rect->blink; - } - else - { - srclist->tail = rect->blink; - } - - /* Un-hook the forward link to the rect */ - - if (rect->blink) - { - rect->blink->flink = rect->flink; - } - else - { - srclist->head = rect->flink; - } - - /* Then add the rect to the specified list */ - - trv_add_plane(rect, destlist); -} - -/**************************************************************************** - * Name: trv_merge_planelists - * - * Description: - * This function concatenates two world plane lists - * - ***************************************************************************/ - -void trv_merge_planelists(FAR struct trv_rect_head_s *outlist, - FAR struct trv_rect_head_s *inlist) -{ - struct trv_rect_list_s *inrect; - struct trv_rect_list_s *nextin; - struct trv_rect_list_s *outrect; - struct trv_rect_list_s *prevout; - - /* Initialize the inner plane search loop */ - - outrect = outlist->head; - - /* Process every plane in the input plane list */ - - for (inrect = inlist->head; (inrect); inrect = nextin) - { - nextin = inrect->flink; - - /* Search the output plane list to find the location to insert the - * input rectangle. Each is list is maintained in ascending plane - * order. - */ - - for (; - outrect && outrect->d.plane < inrect->d.plane; - outrect = outrect->flink); - - /* Add the 'inrect' to the spot found in the list. Check if the - * 'inrect' goes at the one of the ends of the list. - */ - - if (!outrect) - { - /* No rectangle with plane larger than the one to be added - * was found in the list. The 'inrect' goes at the end of - * the list. - */ - - prevout = outlist->tail; - if (!prevout) - { - /* Special case: The list is empty */ - - inrect->flink = NULL; - inrect->blink = NULL; - outlist->head = inrect; - outlist->tail = inrect; - } - else - { - inrect->flink = NULL; - inrect->blink = prevout; - prevout->flink = inrect; - outlist->tail = inrect; - } - } - else - { - /* The 'inrect' goes just before 'outrect' */ - - prevout = outrect->blink; - if (!prevout) - { - /* Special case: Insert at the head of the list */ - - inrect->flink = outrect; - inrect->blink = NULL; - outrect->blink = inrect; - outlist->head = inrect; - } - else - { - /* Insert in the middle of the list */ - - inrect->flink = outrect; - inrect->blink = prevout; - prevout->flink = inrect; - outrect->blink = inrect; - } - } - - /* Set up for the next time through */ - - outrect = inrect; - } - - /* Mark the input list empty */ - - inlist->head = NULL; - inlist->tail = NULL; -} diff --git a/apps/graphics/traveler/src/trv_planefiles.c b/apps/graphics/traveler/src/trv_planefiles.c new file mode 100644 index 000000000..828d6c06d --- /dev/null +++ b/apps/graphics/traveler/src/trv_planefiles.c @@ -0,0 +1,183 @@ +/******************************************************************************* + * apps/graphics/traveler/src/trv_planefiles.c + * This file contains the logic to manage the world data files + * + * 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_plane.h" + +#include +#include + +/**************************************************************************** + * Pre-processor Definitions + ****************************************************************************/ + +/**************************************************************************** + * Private Type Declarations + ***************************************************************************/ + +/**************************************************************************** + * Private Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: trv_load_worldplane + * + * Description: + * + * This function loads the world data for one plane + * + ***************************************************************************/ + +static int trv_load_worldplane(FAR FILE *fp, FAR struct trv_rect_head_s *head, + uint8_t nrects) +{ + FAR struct trv_rect_list_s *rect; + int ret; + int i; + + for (i = 0; i < nrects; i++) + { + /* Allocate space for the next rectangle */ + + rect = trv_new_plane(); + if (!rect) + { + return -ENOMEM; + } + + /* Read the next rectangle from the input file */ + + ret = fread((char*)&rect->d, RESIZEOF_TRVRECTDATA_T, 1, fp); + if (ret != 1) + { + int errcode = errno; + fprintf(stderr, "Error: read of rectangle %d (of %d) failed\n", + i, nrects); + fprintf(stderr, "feof=%d ferror=%d errno=%d\n", + feof(fp), ferror(fp), errcode); + return -errcode; + } + + /* Put the new rectangle into the plane list */ + + trv_add_plane(rect, head); + } + + return OK; +} + +/**************************************************************************** + * Function: trv_load_planes + * Description: + * This function loads the world data from the opened file + ***************************************************************************/ + +static int trv_load_planes(FAR FILE *fp) +{ + struct trv_planefile_header_s header; + int ret; + + /* Read the plane file header */ + + ret = fread((char*)&header, SIZEOF_TRVPLANEFILEHEADER_T, 1, fp); + if (ret != 1) + { + int errcode = errno; + fprintf(stderr, "Error: Failed to read of file header\n"); + fprintf(stderr, "feof=%d ferror=%d errno=%d\n", + feof(fp), ferror(fp), errcode); + return -errcode; + } + + /* Then load each grid, performing run length (rle) decoding */ + + ret = trv_load_worldplane(fp, &g_xplane, header.nxrects); + if (ret == OK) + { + ret = trv_load_worldplane(fp, &g_yplane, header.nyrects); + } + + if (ret == OK) + { + ret = trv_load_worldplane(fp, &g_zplane, header.nzrects); + } + + return ret; +} + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: trv_load_planefile + * + * Description: + * + * This function opens the input file and loads the world plane data from it + * + ***************************************************************************/ + +int trv_load_planefile(FAR const char *wldfile) +{ + FAR FILE *fp; + int ret; + + /* Open the map file which contains the description of the world */ + + fp = fopen(wldfile, "rb"); + if (fp == NULL) + { + int errcode = errno; + fprintf(stderr, "ERROR: Could not open plane file=\"%s\": %d\n", + wldfile, errcode); + return -errcode; + } + + /* Load the world data from the file */ + + ret = trv_load_planes(fp); + + /* Close the file */ + + fclose(fp); + return ret; +} + diff --git a/apps/graphics/traveler/src/trv_planelists.c b/apps/graphics/traveler/src/trv_planelists.c new file mode 100644 index 000000000..bfca88d65 --- /dev/null +++ b/apps/graphics/traveler/src/trv_planelists.c @@ -0,0 +1,331 @@ +/******************************************************************************* + * apps/graphics/traveler/src/trv_planelist.c + * This file contains the logic to manage world plane lists. + * + * 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_mem.h" +#include "trv_plane.h" + +/**************************************************************************** + * Public Data + ****************************************************************************/ + +/* The is the world!!! The world is described by lists of rectangles, one + * for each of the X, Y, and Z planes. + */ + +struct trv_rect_head_s g_xplane; /* list of X=plane rectangles */ +struct trv_rect_head_s g_yplane; /* list of Y=plane rectangles */ +struct trv_rect_head_s g_zplane; /* list of Z=plane rectangles */ + +/* "Deallocated" planes are retained in a free list */ + +FAR struct trv_rect_list_s *g_rect_freelist; + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Name: trv_initialize_planes + * + * Description: + * + ***************************************************************************/ + +int trv_initialize_planes(void) +{ + g_xplane.head = NULL; + g_xplane.tail = NULL; + g_yplane.head = NULL; + g_yplane.tail = NULL; + g_zplane.head = NULL; + g_zplane.tail = NULL; + g_rect_freelist = NULL; + + return OK; +} + +/**************************************************************************** + * Name: trv_add_plane + * + * Description: + * This function adds a plane to a world plane list + * + ***************************************************************************/ + +void trv_add_plane(FAR struct trv_rect_list_s *rect, + FAR struct trv_rect_head_s *list) +{ + struct trv_rect_list_s *next; + struct trv_rect_list_s *prev; + + /* Search the list to find the location to insert the new rectangle. Each + * is list is maintained in ascending plane order. + */ + + for (next = list->head; + ((next) && (next->d.plane < rect->d.plane)); + next = next->flink); + + /* Add the 'rect' to the spot found in the list. Check if the 'rect' lies + * at the end of the list. + */ + + if (!next) + { + /* No rectangle with plane larger than the one to be added was found + * in the list. The 'rect' goes at the end of the list. + */ + + prev = list->tail; + if (!prev) + { + /* Special case: The list is empty */ + + rect->flink = NULL; + rect->blink = NULL; + list->head = rect; + list->tail = rect; + } + else + { + rect->flink = NULL; + rect->blink = prev; + prev->flink = rect; + list->tail = rect; + } + } + else + { + /* The 'rect' goes just before 'next' */ + + prev = next->blink; + if (!prev) + { + /* Special case: Insert at the head of the list */ + + rect->flink = next; + rect->blink = NULL; + next->blink = rect; + list->head = rect; + } + else + { + /* Insert in the middle of the list */ + + rect->flink = next; + rect->blink = prev; + prev->flink = rect; + next->blink = rect; + } + } +} + +/**************************************************************************** + * Name: trv_move_plane + * + * Description: + * + * This function removes the specified plane from the world plane srclist + * then adds it to the world plane destlist + * + ***************************************************************************/ + +void trv_move_plane(FAR struct trv_rect_list_s *rect, + FAR struct trv_rect_head_s *destlist, + FAR struct trv_rect_head_s *srclist) +{ + /* Un-hook the backward link to the rect */ + + if (rect->flink) + { + rect->flink->blink = rect->blink; + } + else + { + srclist->tail = rect->blink; + } + + /* Un-hook the forward link to the rect */ + + if (rect->blink) + { + rect->blink->flink = rect->flink; + } + else + { + srclist->head = rect->flink; + } + + /* Then add the rect to the specified list */ + + trv_add_plane(rect, destlist); +} + +/**************************************************************************** + * Name: trv_merge_planelists + * + * Description: + * This function concatenates two world plane lists + * + ***************************************************************************/ + +void trv_merge_planelists(FAR struct trv_rect_head_s *outlist, + FAR struct trv_rect_head_s *inlist) +{ + struct trv_rect_list_s *inrect; + struct trv_rect_list_s *nextin; + struct trv_rect_list_s *outrect; + struct trv_rect_list_s *prevout; + + /* Initialize the inner plane search loop */ + + outrect = outlist->head; + + /* Process every plane in the input plane list */ + + for (inrect = inlist->head; (inrect); inrect = nextin) + { + nextin = inrect->flink; + + /* Search the output plane list to find the location to insert the + * input rectangle. Each is list is maintained in ascending plane + * order. + */ + + for (; + outrect && outrect->d.plane < inrect->d.plane; + outrect = outrect->flink); + + /* Add the 'inrect' to the spot found in the list. Check if the + * 'inrect' goes at the one of the ends of the list. + */ + + if (!outrect) + { + /* No rectangle with plane larger than the one to be added + * was found in the list. The 'inrect' goes at the end of + * the list. + */ + + prevout = outlist->tail; + if (!prevout) + { + /* Special case: The list is empty */ + + inrect->flink = NULL; + inrect->blink = NULL; + outlist->head = inrect; + outlist->tail = inrect; + } + else + { + inrect->flink = NULL; + inrect->blink = prevout; + prevout->flink = inrect; + outlist->tail = inrect; + } + } + else + { + /* The 'inrect' goes just before 'outrect' */ + + prevout = outrect->blink; + if (!prevout) + { + /* Special case: Insert at the head of the list */ + + inrect->flink = outrect; + inrect->blink = NULL; + outrect->blink = inrect; + outlist->head = inrect; + } + else + { + /* Insert in the middle of the list */ + + inrect->flink = outrect; + inrect->blink = prevout; + prevout->flink = inrect; + outrect->blink = inrect; + } + } + + /* Set up for the next time through */ + + outrect = inrect; + } + + /* Mark the input list empty */ + + inlist->head = NULL; + inlist->tail = NULL; +} + +/************************************************************************* + * Function: trv_new_plane + * + * Description: + * This function allocates memory for a new plane rectangle. + * + ************************************************************************/ + +FAR struct trv_rect_list_s *trv_new_plane(void) +{ + FAR struct trv_rect_list_s *rect; + + /* Try to get the new structure from the free list */ + + rect = g_rect_freelist; + if (rect) + { + /* Got get... remove it from the g_rect_freelist; */ + + g_rect_freelist = rect->flink; + } + else + { + /* Nothing on the free list. Allocate a new one */ + + rect = (FAR struct trv_rect_list_s*)trv_malloc(sizeof(struct trv_rect_list_s)); + } + + return rect; +} -- cgit v1.2.3