summaryrefslogtreecommitdiff
path: root/apps/graphics/traveler/src/trv_planelists.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/graphics/traveler/src/trv_planelists.c')
-rw-r--r--apps/graphics/traveler/src/trv_planelists.c331
1 files changed, 331 insertions, 0 deletions
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 <gnutt@nuttx.org>
+ *
+ * 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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-25 06:56:11 +0000