objtree.c

#include "stdafx.h"
#include "LoftyCAD.h"
#include <stdio.h>


// Free lists for Edges, Points and Objects. Only singly linked.
ListHead free_list_edge = { NULL, NULL };
ListHead free_list_pt = { NULL, NULL };
ListHead free_list_obj = { NULL, NULL };

// List head for ZPolyEdge free list. Used by G-code visualisation.
ListHead free_list_zedge = { NULL, NULL };

#ifdef DEBUG_FREELISTS
// Some counters
int n_alloc_obj = 0;
int n_alloc_pt = 0;
int n_alloc_edge = 0;
#endif

// Creation functions for objects
Object *obj_new(void)
{
    Object *obj;

    // Try and obtain an object from the free list first
    if (free_list_obj.head != NULL)
    {
        obj = free_list_obj.head;
        free_list_obj.head = free_list_obj.head->next;
        if (free_list_obj.head == NULL)
            free_list_obj.tail = NULL;
        memset(obj, 0, sizeof(Object));
    }
    else
    {
        obj = calloc(1, sizeof(Object));
#ifdef DEBUG_FREELISTS
        n_alloc_obj++;
#endif
    }

    obj->type = OBJ_NONE;
    obj->ID = 0;
    return obj;
}

// Get me a fresh clean Point!
Point* point_new_raw()
{
    Point* pt;

    // Try and obtain a point from the free list first
    if (free_list_pt.head != NULL)
    {
        pt = (Point*)free_list_pt.head;
        free_list_pt.head = free_list_pt.head->next;
        if (free_list_pt.head == NULL)
            free_list_pt.tail = NULL;
        memset(pt, 0, sizeof(Point));
    }
    else
    {
        pt = calloc(1, sizeof(Point));
#ifdef DEBUG_FREELISTS
        n_alloc_pt++;
#endif
    }
    return pt;
}

Point *point_new(double x, double y, double z)
{
    Point* pt = point_new_raw();

    pt->hdr.type = OBJ_POINT;
    pt->hdr.ID = objid++;
    pt->x = x;
    pt->y = y;
    pt->z = z;
    return pt;
}

// Copy just the coordinates from the given point.
Point *point_newp(Point *p)
{
    Point* pt = point_new_raw();

    pt->hdr.type = OBJ_POINT;
    pt->hdr.ID = objid++;
    pt->x = p->x;
    pt->y = p->y;
    pt->z = p->z;
    return pt;
}

// The same, but don't store or increment an objid. Used for viewlists.
Point* point_newv(double x, double y, double z)
{
    Point* pt = point_new_raw();

    pt->hdr.type = OBJ_POINT;
    pt->hdr.ID = 0;
    pt->x = x;
    pt->y = y;
    pt->z = z;
    return pt;
}

Point* point_newpv(Point* p)
{
    Point* pt = point_new_raw();

    pt->hdr.type = OBJ_POINT;
    pt->hdr.ID = 0;
    pt->x = p->x;
    pt->y = p->y;
    pt->z = p->z;
    return pt;
}

// Divide the line between p0 and p1 in a given ratio (usually 0-1), and put a new point there.
Point* point_newr(Point* p0, Point* p1, double ratio)
{
    Point* pt = point_new_raw();

    pt->hdr.type = OBJ_POINT;
    pt->hdr.ID = objid++;
    pt->x = (1 - ratio) * p0->x + ratio * p1->x;
    pt->y = (1 - ratio) * p0->y + ratio * p1->y;
    pt->z = (1 - ratio) * p0->z + ratio * p1->z;
    return pt;
}

// Edges. 
Edge *edge_new(EDGE edge_type)
{
    FreeEdge* fe;
    Edge* e;

    if (free_list_edge.head != NULL)
    {
        fe = (FreeEdge *)free_list_edge.head;
        free_list_edge.head = free_list_edge.head->next;
        if (free_list_edge.head == NULL)
            free_list_edge.tail = NULL;
        memset(fe, 0, sizeof(FreeEdge));
    }
    else
    {
        fe = calloc(1, sizeof(FreeEdge));
#ifdef DEBUG_FREELISTS
        n_alloc_edge++;
#endif
    }

    e = (Edge*)fe;
    e->hdr.type = OBJ_EDGE;
    e->hdr.ID = objid++;
    e->hdr.show_dims = edge_type & EDGE_CONSTRUCTION;
    e->type = edge_type;

    if ((edge_type & ~EDGE_CONSTRUCTION) == EDGE_ARC)
        ((ArcEdge*)e)->ecc = 1.0f;

    return e;
}

Face *face_new(FACE face_type, Plane norm)
{
    Face *face = calloc(1, sizeof(Face));

    face->hdr.type = OBJ_FACE;
    face->hdr.ID = objid++;
    face->type = face_type;
    face->normal = norm;

    // Have a stab at allocating the edge array. Always a power of 2.
    switch (face_type & ~FACE_CONSTRUCTION)
    {
    case FACE_TRI:
    case FACE_RECT:
    case FACE_CIRCLE:
        face->hdr.show_dims = face_type & FACE_CONSTRUCTION;
        // fallthrough
    case FACE_CYLINDRICAL:
    default:                // barrel/bezier types here too
        face->max_edges = 4;
        break;

    case FACE_HEX:
        face->hdr.show_dims = face_type & FACE_CONSTRUCTION;
        face->max_edges = 8;
        break;

    case FACE_FLAT:
        face->max_edges = 16;
        break;
    }

    face->edges = (Edge **)malloc(face->max_edges * sizeof(struct Edge *));

    // Allocate the 2D view list array
    if (IS_FLAT(face))
    {
        face->n_alloc2D = 16;
        face->view_list2D = malloc(face->n_alloc2D * sizeof(Point2D));  
    }

    return face;
}

Volume *vol_new(void)
{
    Volume *vol = calloc(1, sizeof(Volume));

    vol->hdr.type = OBJ_VOLUME;
    vol->hdr.ID = objid++;
    vol->op = OP_UNION;
    clear_bbox(&vol->bbox);
    vol->point_bucket = init_buckets();

    return vol;
}

Group *group_new(void)
{
    Group *grp = calloc(1, sizeof(Group));

    grp->hdr.type = OBJ_GROUP;
    grp->hdr.ID = objid++;
    grp->hdr.lock = LOCK_VOLUME;
    grp->op = OP_NONE;
    clear_bbox(&grp->bbox);
    return grp;
}

// Test if an object is in a tree at the top level (and not a component)
BOOL
is_top_level_object(Object *obj, Group *tree)
{
    Object *o;

    if (tree == NULL)
        return FALSE;   // its parent group is NULL
    for (o = tree->obj_list.head; o != NULL; o = o->next)
    {
        if (obj == o)
            return TRUE;
    }
    return FALSE;
}


// Find an object owned by another object; return TRUE if it is found.
BOOL
find_obj(Object *parent, Object *obj)
{
    int i;
    EDGE type;
    Edge *edge;
    ArcEdge *ae;
    BezierEdge *be;
    Face *face;
    Volume *vol;

    switch (parent->type)
    {
    case OBJ_POINT:
        // a Point cannot be a parent of anything
        return FALSE;

    case OBJ_EDGE:
        edge = (Edge *)parent;
        if ((Object *)edge->endpoints[0] == obj)
            return TRUE;
        if ((Object *)edge->endpoints[1] == obj)
            return TRUE;
        type = ((Edge *)parent)->type & ~EDGE_CONSTRUCTION;
        switch (type)
        {
        case EDGE_ARC:
            ae = (ArcEdge *)parent;
            if ((Object *)ae->centre == obj)
                return TRUE;
            break;

        case EDGE_BEZIER:
            be = (BezierEdge *)parent;
            if ((Object *)be->ctrlpoints[0] == obj)
                return TRUE;
            if ((Object *)be->ctrlpoints[1] == obj)
                return TRUE;
            break;
        }

        break;

    case OBJ_FACE:
        face = (Face *)parent;
        for (i = 0; i < face->n_edges; i++)
        {
            edge = face->edges[i];
            if ((Object *)edge == obj)
                return TRUE;
            if (find_obj((Object *)edge, obj))
                return TRUE;
        }
        if (face->text != NULL)
        {
            if ((Object *)&face->text->origin == obj)
                return TRUE;
            if ((Object *)&face->text->endpt == obj)
                return TRUE;
        }
        break;

    case OBJ_VOLUME:
        vol = (Volume *)parent;
        for (face = (Face *)vol->faces.head; face != NULL; face = (Face *)face->hdr.next)
        {
            if ((Object *)face == obj)
                return TRUE;
            if (find_obj((Object *)face, obj))
                return TRUE;
        }
        break;

    case OBJ_GROUP:
        ASSERT(FALSE, "Shouldn't be calling find_obj on a group");
        break;
    }

    return FALSE;
}

// Find the parent object (i.e. in the object tree or in a group) for the given object.
// The parent object maintains the lock on all its components. Will not return a group (unless given).
// There are two versions: a "deep" version which searches the object tree and all groups,
// and a shallow version which does not go down into groups.
Object *
find_parent_object(Group *tree, Object *obj, BOOL deep_search)
{
    Object *top_level;

    // Special case for groups and volumes, just return the object.
    if (obj->type == OBJ_VOLUME || obj->type == OBJ_GROUP)
        return obj;

    // Special case for faces, as we can get to the volume quickly.
    if (obj->type == OBJ_FACE)
    {
        Face *f = (Face *)obj;

        if (f->vol != NULL)
            return (Object *)f->vol;
    }

    // Nothing for it but to search the tree exhaustively.
    for (top_level = tree->obj_list.head; top_level != NULL; top_level = top_level->next)
    {
        if (top_level->type == OBJ_GROUP)
        {
            if (deep_search)
            {
                Object *o = find_parent_object((Group *)top_level, obj, deep_search);
                if (o != NULL)
                    return o;
            }
        }
        else if (top_level == obj || find_obj(top_level, obj))
        {
            return top_level;
        }
    }
    return NULL;
}


// Find the highest parent object or group (i.e. in the object tree) for the given object.
Object *
find_top_level_parent(Object *obj)
{
    Object *top_level;
    
    // If we're starting with a group, just go up to the highest level quickly;
    // otherwise we have to do the search.
    if (obj->type == OBJ_GROUP)
        top_level = obj;
    else
        top_level = find_parent_object(&object_tree, obj, TRUE);

    if (top_level == NULL)
        return NULL;
    for (; top_level->parent_group->hdr.parent_group != NULL; top_level = (Object *)top_level->parent_group)
        ;
    return top_level;
}

// Purge an object. Points are put in the free list.
void
purge_obj_top(Object *obj, OBJECT top_type)
{
    int i;
    Edge *e;
    ArcEdge *ae;
    BezierEdge *be;
    EDGE type;
    Face *face;
    Face *next_face = NULL;
    Object *next_obj = NULL;
    Object *o;
    Volume *vol;
    Group *group;

    switch (obj->type)
    {
    case OBJ_POINT:
        if (obj->ID == 0)
            break;              // it's already been freed
        obj->ID = 0;
        free_point(obj);
        break;

    case OBJ_EDGE:
        e = (Edge *)obj;
        purge_obj_top((Object *)e->endpoints[0], top_type);
        purge_obj_top((Object *)e->endpoints[1], top_type);
        type = ((Edge *)obj)->type & ~EDGE_CONSTRUCTION;
        switch (type)
        {
        case EDGE_ARC:
            ae = (ArcEdge *)obj;
            purge_obj_top((Object *)ae->centre, top_type);
            free_view_list_edge(e);
            break;

        case EDGE_BEZIER:
            be = (BezierEdge *)obj;
            purge_obj_top((Object *)be->ctrlpoints[0], top_type);
            purge_obj_top((Object *)be->ctrlpoints[1], top_type);
            free_view_list_edge(e);
            break;
        }
        //if (top_type <= OBJ_FACE)       // If this edge is not part of a volume, we can safely delete it
        if (obj->ID == 0)
            break;
        obj->ID = 0;
        free_edge(obj);
        if (curr_path == obj)
            curr_path = NULL;
        break;

    case OBJ_FACE:
        face = (Face *)obj;
        free_view_list_face(face);
        for (i = 0; i < face->n_edges; i++)
            purge_obj_top((Object *)face->edges[i], top_type);
        free(face->edges);
        free(face->view_list2D);
        if (face->contours != NULL)
            free(face->contours);
        if (face->text != NULL)
            free(face->text);
        free(obj);
        break;

    case OBJ_VOLUME:
        vol = (Volume *)obj;
        for (face = (Face *)vol->faces.head; face != NULL; face = next_face)
        {
            next_face = (Face *)face->hdr.next;
            purge_obj_top((Object *)face, top_type);
        }
        free_bucket(vol->point_bucket);
        free(obj);
        break;

    case OBJ_GROUP:
        group = (Group *)obj;
        for (o = group->obj_list.head; o != NULL; o = next_obj)
        {
            next_obj = o->next;
            purge_obj(o);       // purge these objects played by themselves (not belonging to a top-level object)
        }
        if (group->mesh != NULL)
            mesh_destroy(group->mesh);
        if (group->loft != NULL)
            free(group->loft);
        free(obj);
        if (curr_path == obj)
            curr_path = NULL;
        break;
    }
}

void
purge_obj(Object *obj)
{
    // Pass the type of the top-level object being purged.
    purge_obj_top(obj, obj->type);
}

// Free the ZPolyEdges attached to their own group. They are recycled in their own
// free list. The group is left alone to be reused.
void
purge_zpoly_edges(Group* group)
{
    ASSERT(group->hdr.lock == LOCK_VOLUME, "Group is not a ZPolyEdge group");
    if (free_list_zedge.head == NULL)
        free_list_zedge.head = group->obj_list.head;
    else
        free_list_zedge.tail->next = group->obj_list.head;
    free_list_zedge.tail = group->obj_list.tail;

    group->n_members = 0;
    group->obj_list.head = NULL;
    group->obj_list.tail = NULL;
}

// Free a list of temporary edges. They and their points have ID's of zero.
// Points are never shared and may be placed directly in the free list.
void
purge_temp_edge_list(ListHead* list)
{
    Object* obj;
    Object* nextobj = NULL;
    EDGE type;
    Edge* e;
    ArcEdge *ae;
    BezierEdge* be;

    for (obj = list->head; obj != NULL; obj = nextobj)
    {
        nextobj = obj->next;
        ASSERT(obj->type == OBJ_EDGE, "Only edges should be in here");
        ASSERT(obj->ID == 0, "Only temporary edges should be in here");
        e = (Edge*)obj;
        free_point((Object*)e->endpoints[0]);
        free_point((Object*)e->endpoints[1]);
        type = ((Edge*)obj)->type & ~EDGE_CONSTRUCTION;
        switch (type)
        {
        case EDGE_ARC:
            ae = (ArcEdge*)obj;
            free_point((Object*)ae->centre);
            free_view_list_edge(e);
            break;

        case EDGE_BEZIER:
            be = (BezierEdge*)obj;
            free_point((Object*)be->ctrlpoints[0]);
            free_point((Object*)be->ctrlpoints[1]);
            free_view_list_edge(e);
            break;
        }
        free_edge(obj);
    }

    list->head = NULL;
    list->tail = NULL;
}

// Purge a tree, freeing everything in it, except for Points, which are
// placed in the free list. 
void
purge_tree(Group *tree, BOOL preserve_objects, ListHead *saved_list)
{
    Object *obj;
    Object *nextobj = NULL;

    if (preserve_objects)
    {
        *saved_list = tree->obj_list;
    }
    else
    {
        for (obj = tree->obj_list.head; obj != NULL; obj = nextobj)
        {
            nextobj = obj->next;
            purge_obj(obj);
        }
    }

    tree->obj_list.head = NULL;
    tree->obj_list.tail = NULL;
    if (tree->mesh != NULL)
        mesh_destroy(tree->mesh);
    tree->mesh = NULL;
    tree->mesh_valid = FALSE;
    tree->mesh_complete = FALSE;
}

// Can we extrude this face? Any face can be extruded, as long it has a valid normal
// and is not a corner face or a construction face. 
BOOL
extrudible(Object* obj)
{
    Face* face = (Face*)obj;

    if (obj == NULL || obj->type != OBJ_FACE)
        return FALSE;
    if (face->type & FACE_CONSTRUCTION)
        return FALSE;
    if (!normalised(&face->normal))
        return FALSE;
    if (face->corner)
        return FALSE;

    return TRUE;
}

// Calculate the extruded heights for a volume that was created by extruding faces.
// Mark faces having a valid oppsite number (and a height to it) as being paired.
// If the extrude heights are negative, the volume is a hole (it will be intersected)
void
calc_extrude_heights(Volume* vol)
{
    Face* last_face, * prev_last, *f, *g;

    // An extruded volume made in LoftyCAD always has its last two faces
    // initially extruded. If they were not, we assume the volue is imported and
    // may not have any parallel faces (you can still extrude, but no heights will be shown)
    last_face = (Face *)vol->faces.tail;
    prev_last = (Face *)last_face->hdr.prev;

    // Unpair everything first
    vol->measured = FALSE;
    for (f = (Face*)vol->faces.head; f != NULL; f = (Face*)f->hdr.next)
        f->paired = FALSE;

    // if this is ~ -1 then normals are opposite, and the faces are paired.
    if (!nz(pldot(&last_face->normal, &prev_last->normal) + 1.0f))
        return;         // forget it. Nothing is paired.

    last_face->extrude_height = 
        -distance_point_plane(&last_face->normal, &prev_last->normal.refpt);
    prev_last->extrude_height = last_face->extrude_height;
    last_face->paired = TRUE;
    prev_last->paired = TRUE;

    // Stop here for multi-contour faces (such as text) as only the top and bottom faces can be paired
    if (last_face->n_contours > 1)
        return;

    vol->measured = TRUE;   // assume it is, unless we find an exception

    // If the volume has a negative height, we assume it's for intersection (holes).
    // Otherwise just leave it alone as it may have been specified on the input.
    if (last_face->extrude_height < 0)
        vol->op = OP_INTERSECTION;

    // Check the rest of the faces, skipping those that are already paired.
    // If all the faces are flat and paired (other than possible round-corner faces)
    // then the volume is measured (dimensions may be shown and changed)
    for (f = (Face*)vol->faces.head; f != NULL; f = (Face*)f->hdr.next)
    {
        if (f->paired)
            continue;
        //if (!extrudible((Object*)f))
        if (!IS_FLAT(f))
        {
            vol->measured = FALSE;
            continue;
        }

        for (g = (Face*)f->hdr.next; g != NULL; g = (Face*)g->hdr.next)
        {
            //if (!extrudible((Object*)g))
            if (!IS_FLAT(g))
                continue;

            if (nz(pldot(&g->normal, &f->normal) + 1.0f))
            {
                ASSERT(!g->paired, "Pairing with already paired face?");
                g->extrude_height =
                    -distance_point_plane(&g->normal, &f->normal.refpt);
                f->extrude_height = g->extrude_height;
                g->paired = TRUE;
                f->paired = TRUE;
                break;
            }
        }
        if (g == NULL)
        {
            // A pair was not found for this face.
            vol->measured = FALSE;
        }
    }
}