Re: [brlcad-devel] [brlcad-commits] SF.net SVN: brlcad:[35314] brlcad/trunk

[Christopher S. M. <br...@ma...>]

Nick,

You may want to check out the red-black tree in LIBBU for this instead of a custom linked list or other search tree.  They're ideally suited for situations where you want bounded insertion, deletion, and lookup times.  They are O(log n) time, making them great for things like a run loops and work queues with dynamic levels.

The red-black tree interface has a manual page (brlman redblack) as well as a few examples sprinkled throughout.

Cheers!
Sean


On Monday, July 27, 2009, at 04:58PM, <n_...@us...> wrote:
>Revision: 35314
>          http://brlcad.svn.sourceforge.net/brlcad/?rev=35314&view=rev
>Author:   n_reed
>Date:     2009-07-27 20:58:36 +0000 (Mon, 27 Jul 2009)
>
>Log Message:
>-----------
>starting to add support for point heirarchy
>
>Modified Paths:
>--------------
>    brlcad/trunk/include/dm-rtgl.h
>    brlcad/trunk/src/libdm/dm-rtgl.c
>
>Modified: brlcad/trunk/include/dm-rtgl.h
>===================================================================
>--- brlcad/trunk/include/dm-rtgl.h	2009-07-27 20:12:59 UTC (rev 35313)
>+++ brlcad/trunk/include/dm-rtgl.h	2009-07-27 20:58:36 UTC (rev 35314)
>@@ -83,6 +83,20 @@
>     float color[3];
> };
> 
>+struct objTree {
>+    char *treeName;
>+    int numChildren;
>+    struct objTree **children;
>+    struct ptInfoList *ptInfo;
>+};
>+
>+#define INIT_OBJTREE(p) { \
>+(struct objTree *)(p)->name = NULL; \
>+(struct objTree *)(p)->numChildren = 0; \
>+(struct objTree *)(p)->children = NULL; \
>+(struct objTree *)(p)->ptInfo = NULL; \
>+}
>+
> #endif /* __DM_RTGL__ */
> 
> /** @} */
>
>Modified: brlcad/trunk/src/libdm/dm-rtgl.c
>===================================================================
>--- brlcad/trunk/src/libdm/dm-rtgl.c	2009-07-27 20:12:59 UTC (rev 35313)
>+++ brlcad/trunk/src/libdm/dm-rtgl.c	2009-07-27 20:58:36 UTC (rev 35314)
>@@ -899,7 +899,7 @@
> double startScale = 1;
> 
> /*
>- *  			O G L _ L O A D M A T R I X
>+ *  		       R T G L _ L O A D M A T R I X
>  *
>  *  Load a new transformation matrix.  This will be followed by
>  *  many calls to rtgl_drawVList().
>@@ -1109,6 +1109,8 @@
> 
> }
> 
>+
>+
> /* add all hit point info to info list */
> int recordHit(struct application *app, struct partition *partH, struct seg *segs)
> {
>@@ -1208,6 +1210,31 @@
>     glPointSize(1);
> }
> 
>+struct objTree objects;
>+
>+void buildTree(struct ged *gedp) {
>+    int i, len;
>+    char *curr, *result, *name;
>+
>+    /* get names of tree tops */
>+    ged_tops(gedp, 2, "tops -n");
>+    result = bu_vls_strdup(&(gedp->ged_result_str));
>+
>+    /* extract individual names */
>+    len = strcspn(result, "/ ");   /* num chars before '/' or ' ' */
>+
>+    name = malloc(sizeof(char) * (len + 1));
>+    name[len] = '\0';
>+
>+    strncpy(name, result, len);
>+
>+    /* skip to  next name */
>+    while(result[len] != ' ') len++;
>+    while(result[len++] == ' ');
>+
>+    result = &(result[len]);
>+}
>+
> /*
>  *  			R T G L _ D R A W V L I S T
>  *
>@@ -1217,8 +1244,8 @@
> {
>     static int call;
> 
>-    int i, j, numTrees, new, newTrees;
>-    char *currTree, *trees[RT_MAXARGS];
>+    int i, j, new, numVisible, numNew;
>+    char *currTree, *visibleTrees[RT_MAXARGS];
>     struct ptInfoList *curr;
>     
>     /* get ged struct */
>@@ -1239,6 +1266,7 @@
>     if (rtip == RTI_NULL)
>         return TCL_ERROR;
>     
>+    /* initialize list */
>     if (ptInfo.l.forw == BU_LIST_NULL) {
> 	/* initialize head */
>         BU_LIST_INIT(&(ptInfo.l));
>@@ -1248,13 +1276,20 @@
> 	BU_GETSTRUCT(currItem, ptInfoList);
> 	BU_LIST_PUSH(&(ptInfo.l), currItem);
> 	currItem->used = 0;
>+
>+	call = 1;
>     }
> 
>+    
>+    if (call == 1) {
>+	buildTree(gedp);
>+    }
>+
>     /* get number and names of visible tree tops */
>-    numTrees = ged_build_tops(gedp, trees, &trees[RT_MAXARGS]);
>+    numVisible = ged_build_tops(gedp, visibleTrees, &visibleTrees[RT_MAXARGS]);
> 
>     /* no objects are visible */
>-    if (numTrees == 0) {
>+    if (numVisible == 0) {
> 
> 	/* drop all display points */
> 	freeInfoList();
>@@ -1268,10 +1303,10 @@
>     }
> 
>     /* look for new trees in need of ray tracing */
>-    newTrees = 0;
>+    numNew = 0;
>     
>-    for (i = 0; i < numTrees; i++) {
>-        currTree = trees[i];
>+    for (i = 0; i < numVisible; i++) {
>+        currTree = visibleTrees[i];
>         new = 1;
>         
>         /* if this tree is in the old tree list, it's not new */
>@@ -1286,14 +1321,13 @@
>                 return TCL_ERROR;
> 
> 	    /* add new tree to list of displayed */
>-            newTrees++;
>+            numNew++;
> 	    oldTrees[oldNumTrees++] = currTree;
>         }
>     }
> 
>     /* get points for new trees */
>-    if (newTrees) {
>-	call = 1;
>+    if (numNew > 0) {
> 
>         /* set up application */
>         RT_APPLICATION_INIT(&app);
>
>
>This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
>
>------------------------------------------------------------------------------
>_______________________________________________
>BRL-CAD Source Commits mailing list
>brl...@li...
>https://lists.sourceforge.net/lists/listinfo/brlcad-commits
>
>