4
\$\begingroup\$

I am implementing a BVH (Bounding volume hierarchy) in Cython and thought of using a doubly linked list to hold reference of the volumes that still need to be split and push new volumes at one end while popping others on the other side in a recursive manner.

But I am not sure if I got the code right, it gets confusing to me really fast.

Here AABB stands for Axis Aligned Bounding Box, the kind of bounding volume I want to use in my BVH.

    cdef struct AABB:
        double min_x, max_x
        double min_y, max_y
        double min_z, max_z
        AABB* next
        AABB* children
        int id

    cdef struct AABBListItem:
        AABB* box
        AABBListItem* next
        AABBListItem* prev

    cdef AABBList* aabb_list_create(AABB* start):
        cdef AABBList* lst = <AABBList *> malloc(sizeof(AABBList))
        cdef AABBListItem* item = <AABBListItem *> malloc(sizeof(AABBListItem))
        item.next = NULL
        item.prev = NULL
        item.box = start
        lst.first = item
        lst.last = item
        lst.length = 1
        return lst

    cdef void aabb_list_free(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABBListItem* next
        while not item == NULL:
            next = item.next
            free(item)
            item = next
        free(lst)

    cdef void aabb_list_push_last(AABBList* lst, AABB* box):
        cdef AABBListItem* item = <AABBListItem *> malloc(sizeof(AABBListItem))
        item.box = box
        item.prev = lst.last
        item.next = NULL
        lst.last.next = item
        lst.last = item
        lst.length += 1

    cdef void aabb_list_push_first(AABBList* lst, AABB* box):
        cdef AABBListItem* item = <AABBListItem *> malloc(sizeof(AABBListItem))
        item.box = box
        item.next = lst.first
        item.prev = NULL
        lst.first.prev = item
        lst.first = item
        lst.length += 1

    cdef AABB* aabb_list_pop_first(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABB* box = item.box
        lst.first = item.next
        lst.first.prev = NULL
        free(item)
        lst.length -= 1
        return box

    cdef AABB* aabb_list_pop_last(AABBList* lst):
        cdef AABBListItem* item = lst.last
        cdef AABB* box = item.box
        lst.last = item.prev
        lst.last.next = NULL
        free(item)
        lst.length -= 1
        return box

```
\$\endgroup\$
1
\$\begingroup\$

Empty Constraint

You do not allow to create an empty list.

cdef AABBList* aabb_list_create(AABB* start):

However, the pop methods don't check against the empty constraint. In fact, when popping the sole node, you end up with an error.

For instance,

 cdef AABB* aabb_list_pop_first(AABBList* lst):
        cdef AABBListItem* item = lst.first
        cdef AABB* box = item.box
        lst.first = item.next     // <- if item.next is NULL
        lst.first.prev = NULL     // <- lst.first will be NULL, and .prev is an error
        free(item)
        lst.length -= 1
        return box

Single Remaining Item after Pop

Furthermore, when after pop a single item remains, it should be set as both first and last on the list.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks, I would never have caught this. \$\endgroup\$ – Jeacom Aug 4 at 18:24
  • \$\begingroup\$ many API's use a cyclic reference to avoid such bugs. For instance, a single node would have next and previous set to itself. Iterators know to stop - not when reaching null - but when reaching the node itself again. \$\endgroup\$ – dfhwze Aug 4 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.