Stars of Shareware: Raytrace & Morphing/SOS-RAYTRACE.ISO/programm/source/rayce27s/csg.c

C/C++ Source or Header | 1994-02-02 | 9.2 KB | 412 lines

/*
 * csg.c -- this implements CSG
 *
 * (c) 1993, 1994 Han-Wen Nienhuys <[e-mail]>
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 675 Mass Ave, Cambridge, MA 02139, USA.
 */


#include "ray.h"
#include "proto.h"
#include "extern.h"

extern struct methods CSGinter_methods;
extern struct methods CSGunion_methods;

/*
 * intersect a CSG union.
 *
 * Actually I could use the same code to do CSG intersections, since
 *
 * intersection { { A inverse } { B inverse } inverse }
 *
 * is equivalent to
 *
 * union { A B }
 *
 * My algorithm relies on the Jordan curve theorem (Gee, that sounds great...
 * ) Well kindof... Jordan curves have to divide space into a *bounded*
 * and unbouded set.;
 *
 * Anyway, this works because each crossed boundary means from
 * inside->outside or outside->inside, thus making the number of shapes
 * we're in very easy to keep track of.
 */

PRIVATE bool
all_CSGunion_intersections(dqueue * dq, object *o, struct ray *r,
               int flags, bool *isinside)
{
    object         *p,
                   *CSG;
    int             encl_shapes,/* shapes we're inside of. */
                    total;
    bool            b,
                    gotcha,
                    chkall,
                    loc_ins;    /* found an intersection? */
    dqueue         *CSGq,
                   *q;


    CSGunion_methods.test++;
    chkall = flags & CHKALL;
    CSG = o->data.CSG;
    encl_shapes = 0;
    total = 0;
    CSGq = get_new_queue();    /* set up a new queue for results of this
                 * CSG union. */
    gotcha = FALSE;

    /* count the shapes, and intersect them. */
    for (p = CSG; p != NULL; p = p->next) {
    total++;
    p->methods->all_intersections_method(CSGq, p, r, CHKINSIDE | CHKALL, &b);
    if (b)
        encl_shapes++;
    }

    if (!encl_shapes)
    loc_ins = *isinside = FALSE;
    else
    loc_ins = *isinside = TRUE;


    /*
     * encl_shapes now holds the number of shapes we're in
     *
     * during the following loop, it holds the number of shapes we're in,
     * after we've passed intersection q
     *
     * During the loop, loc_ins is wether we are inside or outside a shape.
     * Of course, isinside does not have to be init'ed, since it is
     * delivered with the parameters. Note that for every intersection of
     * the CSG we're looking in to, isinside is flipped.
     */

    for (q = CSGq; q != NULL && (chkall || !gotcha); q = q->next) {
    if (q->obj == NULL)    /* some kind of void intersection.. Hmmm,
                 * not very elegant. */
        continue;

    if (q->entering) {    /* going into a shape */
        ++encl_shapes;
        assert(encl_shapes <= total);    /* we can't be in more
                         * shapes than there are
                         * shapes to be in (huh
                         * :-) */


        if (encl_shapes == 1) {    /* from outside CSG -> inside CSG,
                     * this is an intersection */
        loc_ins = !loc_ins;
        q->entering = loc_ins;
        add_to_queue(dq, *q);
        gotcha = TRUE;
        }
    } else {
        /* exiting a shape */
        --encl_shapes;
        assert(encl_shapes >= 0);

        if (encl_shapes == 0) {    /* just left the CSG structure */
        loc_ins = !loc_ins;
        q->entering = loc_ins;
        add_to_queue(dq, *q);
        gotcha = TRUE;
        }
    }

    }

    if (gotcha)
    CSGunion_methods.hit++;

    free_queue(CSGq);
    return gotcha;
}

PRIVATE bool
all_CSGinter_intersections(dqueue * dq, object *o, struct ray *r,
               int flags, bool *isinside)
{
    object         *p,
                   *CSG;
    int             encl_shapes,/* shapes we're inside of. */
                    total;
    bool            inside_this,
                    gotcha,
                    chkall,
                    loc_ins;    /* found an intersection? */
    dqueue         *CSGq,
                   *q;

    CSGinter_methods.test++;
    CSG = o->data.CSG;
    gotcha = FALSE;
    chkall = flags & CHKALL;

    /* count the shapes, and intersect them. */
    encl_shapes = 0;
    total = 0;
    CSGq = get_new_queue();    /* set up a new queue for results of this
                 * CSG union. */
    for (p = CSG; p != NULL; p = p->next) {
    total++;
    p->methods->all_intersections_method(CSGq, p, r, CHKINSIDE | CHKALL, &inside_this);
    if (inside_this)
        encl_shapes++;
    }

    if (encl_shapes < total)
    *isinside = loc_ins = FALSE ^ o->inverted;
    else
    *isinside = loc_ins = TRUE ^ o->inverted;

    /*
     * encl_shapes now holds the number of shapes we're in
     *
     * during the following loop, it holds the number of shapes we're in,
     * after we've passed intersection q->i
     *
     * During the loop, isinside is wether we are inside or outside a shape.
     * Note that for every intersection of the CSG we're looking in to,
     * isinside is flipped.
     */

    for (q = CSGq;
     q != NULL && (chkall || !gotcha);
     q = q->next) {
    if (q->obj == NULL)    /* some kind of void intersection.. Hmmm,
                 * not very elegant. */
        continue;

    if (q->entering) {    /* going into a shape */
        ++encl_shapes;
        assert(encl_shapes <= total);    /* we can't be in more
                         * shapes than there are
                         * shapes to be in (huh
                         * :-) */

        if (encl_shapes == total) {    /* from outside CSG -> inside CSG,
                     * this is an intersection */
        loc_ins = !loc_ins;
        q->entering = loc_ins;
        add_to_queue(dq, *q);
        gotcha = TRUE;
        }
    } else {
        if (encl_shapes == total) {    /* just left the CSG structure */
        loc_ins = !loc_ins;
        q->entering = loc_ins;
        add_to_queue(dq, *q);
        gotcha = TRUE;
        }
        /* exiting a shape */
        --encl_shapes;
        assert(encl_shapes >= 0);
    }
    }

    /* throw away the queue. It's needed anymore. */
    free_queue(CSGq);
    if (gotcha)
    CSGinter_methods.hit++;

    return gotcha;
}

/* inside?  True if we're at least inside one of the components */
PRIVATE bool
inside_CSGunion(object *c, vector x)
{
    object         *p;

    for (p = c->data.CSG; p != NULL; p = p->next)
    if (p->methods->inside_method(p, x))
        return !c->inverted;
    return c->inverted;
}


/* inside of  CSGinter if we're inside all parts of CSG */
PRIVATE bool
inside_CSGinter(object *c, vector x)
{
    object         *p;

    for (p = c->data.CSG; p != NULL; p = p->next)
    if (!p->methods->inside_method(p, x))
        return c->inverted;
    return !c->inverted;
}

PRIVATE void
print_CSG(object *p)
{
#ifdef DEBUG
    printf(" {\n");
    print_object_list(p->data.CSG);
    printf("} \n");
#endif
}


/*
 * QUESTION: from what file were the routines below copied? (u gaat door
 * voor de koelkast!)
 */

/* add an object to the CSG c */
PUBLIC void
add_to_CSG(object *c, object *o)
{
    object         *tmp;

    tmp = c->data.CSG;
    c->data.CSG = o;
    o->next = tmp;
    o->daddy = c;
}

/* this is getting boring... */
PRIVATE void
copy_CSG(object *dst, object *src)
{
    object         *p,
                   *new;

    dst->type = src->type;
    dst->data.CSG = NULL;
    for (p = src->data.CSG; p != NULL; p = p->next) {
    new = get_new_object();
    copy_object(new, p);
    add_to_CSG(dst, new);
    }
}

/* standard */
PRIVATE void
translate_CSG(object *c, vector t)
{
    translate_object_list(c->data.CSG, t);
}

/* hooooeeewaahhh, Geez, why do I write these comments? */
PRIVATE void
rotate_CSG(object *c, matrix rotmat)
{

    rotate_object_list(c->data.CSG, rotmat);
}

/*
 * I guess .. because somebody will read them, some day (Hello, is there
 * somebody out there?
 *
 * and another free_XXX() (en wat hebben ze gewonnen, Pierre, als ze goed
 * raden waar dit voor is ?
 */
PRIVATE void
free_CSG(object *c)
{
    free_object_list(c->data.CSG);
    c->type = NOSHAPE;
}

/* 3X raden (Yes, you folks out there, I'm now commenting in Dutch! */
PRIVATE void
scale_CSG(object *c, vector s)
{
    scale_object_list(c->data.CSG, s);
}

PRIVATE vector
CSG_normal(struct intersect i, vector loc)
{
    assert(FALSE);
}

PRIVATE void
precompute_CSG(object *o)
{
    precompute_object_list(o->data.CSG);

    global_stats.nonprims++;
    if (o->type == CSGINTER)
    CSGinter_methods.howmuch++;
    else
    CSGunion_methods.howmuch++;
}


PRIVATE struct methods CSGinter_methods =
{
    all_CSGinter_intersections,
    CSG_normal,
    copy_CSG,
    inside_CSGinter,
    rotate_CSG,
    translate_CSG,
    scale_CSG,
    free_CSG,
    print_CSG,
    precompute_CSG,
    "intersection"
};

PRIVATE struct methods CSGunion_methods =
{
    all_CSGunion_intersections,
    CSG_normal,
    copy_CSG,
    inside_CSGunion,
    rotate_CSG,
    translate_CSG,
    scale_CSG,
    free_CSG,
    print_CSG,
    precompute_CSG,
    "union",
};

PUBLIC object  *
get_new_CSGinter_object(void)
{
    object         *o;

    o = get_new_object();
    o->methods = &CSGinter_methods;
    o->type = CSGINTER;
    o->data.CSG = NULL;


    return o;
}

PUBLIC object  *
get_new_CSGunion_object(void)
{
    object         *o;

    o = get_new_object();
    o->methods = &CSGunion_methods;
    o->data.CSG = NULL;
    o->type = CSGUNION;


    return o;
}