BME_structure.c

Go to the documentation of this file.

/*
 * BME_structure.c    jan 2007
 *
 *  Low level routines for manipulating the BMesh structure.
 *
 *
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * 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; either version 2
 * of the License, or (at your option) any later version.
 * about this.  
 *
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2007 Blender Foundation.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): Geoffrey Bantle.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#include <limits.h>

#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_utildefines.h"
#include "BKE_bmesh.h"
int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
    if(e->v1 == v || e->v2 == v) return 1;
    return 0;
}
int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
    if(e->v1 == v1 && e->v2 == v2) return 1;
    else if(e->v1 == v2 && e->v2 == v1) return 1;
    return 0;
}

BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){  
    if(e->v1 == v) return e->v2;
    else if(e->v2 == v) return e->v1;
    return NULL;
}

int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
    if(e->v1 == orig){ 
        e->v1 = new;
        e->d1.next = NULL;
        e->d1.prev = NULL;
        return 1;
    }
    else if(e->v2 == orig){
        e->v2 = new;
        e->d2.next = NULL;
        e->d2.prev = NULL;
        return 1;
    }
    return 0;
}

BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
    BME_Vert *v=NULL;
    v = BLI_mempool_alloc(bm->vpool);
    v->next = v->prev = NULL;
    v->EID = bm->nextv;
    v->co[0] = v->co[1] = v->co[2] = 0.0f;
    v->no[0] = v->no[1] = v->no[2] = 0.0f;
    v->edge = NULL;
    v->data = NULL;
    v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
    v->flag = v->h = 0;
    v->bweight = 0.0f;
    BLI_addtail(&(bm->verts), v);
    bm->nextv++;
    bm->totvert++;

    if(example){
        VECCOPY(v->co,example->co);
        CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
    }
    else
        CustomData_bmesh_set_default(&bm->vdata, &v->data);

    return v;
}
BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
    BME_Edge *e=NULL;
    e = BLI_mempool_alloc(bm->epool);
    e->next = e->prev = NULL;
    e->EID = bm->nexte;
    e->v1 = v1;
    e->v2 = v2;
    e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
    e->d1.data = e;
    e->d2.data = e;
    e->loop = NULL;
    e->data = NULL;
    e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
    e->flag = e->h = 0;
    e->crease = e->bweight = 0.0f;
    bm->nexte++;
    bm->totedge++;
    BLI_addtail(&(bm->edges), e);
    
    if(example)
        CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
    else
        CustomData_bmesh_set_default(&bm->edata, &e->data);


    return e;
}
BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
    BME_Loop *l=NULL;
    l = BLI_mempool_alloc(bm->lpool);
    l->next = l->prev = NULL;
    l->EID = bm->nextl;
    l->radial.next = l->radial.prev = NULL;
    l->radial.data = l;
    l->v = v;
    l->e = e;
    l->f = f;
    l->data = NULL;
    l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
    l->flag = l->h = 0; //stupid waste!
    bm->nextl++;
    bm->totloop++;
    
    if(example)
        CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
    else
        CustomData_bmesh_set_default(&bm->ldata, &l->data);

    return l;
}

BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
    BME_Poly *f = NULL;
    f = BLI_mempool_alloc(bm->ppool);
    f->next = f->prev = NULL;
    f->EID = bm->nextp;
    f->loopbase = NULL;
    f->len = 0;
    f->data = NULL;
    f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
    f->flag = f->h = f->mat_nr;
    BLI_addtail(&(bm->polys),f);
    bm->nextp++;
    bm->totpoly++;

    if(example)
        CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
    else
        CustomData_bmesh_set_default(&bm->pdata, &f->data);


    return f;
}

/*  free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
    data is added though these will be needed.
*/
void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
    bm->totvert--;
    CustomData_bmesh_free_block(&bm->vdata, &v->data);
    BLI_mempool_free(bm->vpool, v);
}
void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
    bm->totedge--;
    CustomData_bmesh_free_block(&bm->edata, &e->data);
    BLI_mempool_free(bm->epool, e);
}
void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
    bm->totpoly--;
    CustomData_bmesh_free_block(&bm->pdata, &f->data);
    BLI_mempool_free(bm->ppool, f);
}
void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
    bm->totloop--;
    CustomData_bmesh_free_block(&bm->ldata, &l->data);
    BLI_mempool_free(bm->lpool, l);
}
void BME_cycle_append(void *h, void *nt)
{
    BME_CycleNode *oldtail, *head, *newtail;
    
    head = (BME_CycleNode*)h;
    newtail = (BME_CycleNode*)nt;
    
    if(head->next == NULL){
        head->next = newtail;
        head->prev = newtail;
        newtail->next = head;
        newtail->prev = head;
    }
    else{
        oldtail = head->prev;
        oldtail->next = newtail;
        newtail->next = head;
        newtail->prev = oldtail;
        head->prev = newtail;
        
    }
}

int BME_cycle_length(void *h){
    
    int len = 0;
    BME_CycleNode *head, *curnode;
    head = (BME_CycleNode*)h;
    
    if(head){ 
        len = 1;
        for(curnode = head->next; curnode != head; curnode=curnode->next){ 
            if(len == INT_MAX){ //check for infinite loop/corrupted cycle
                    return -1;
            }
            len++;
        }
    }
    return len;
}


int BME_cycle_remove(void *h, void *remn)
{
    int i, len;
    BME_CycleNode *head, *remnode, *curnode;
    
    head = (BME_CycleNode*)h;
    remnode = (BME_CycleNode*)remn;
    len = BME_cycle_length(h);
    
    if(len == 1 && head == remnode){
        head->next = NULL;
        head->prev = NULL;
        return 1;
    }
    else{
        for(i=0, curnode = head; i < len; curnode = curnode->next){
            if(curnode == remnode){
                remnode->prev->next = remnode->next;
                remnode->next->prev = remnode->prev;
                /*zero out remnode pointers, important!*/
                //remnode->next = NULL;
                //remnode->prev = NULL;
                return 1;
        
            }
        }
    }
    return 0;
}

int BME_cycle_validate(int len, void *h){
    int i;
    BME_CycleNode *curnode, *head;
    head = (BME_CycleNode*)h;
    
    /*forward validation*/
    for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
    if(curnode != head) return 0;
    
    /*reverse validation*/
    for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
    if(curnode != head) return 0;
    
    return 1;
}

/*Begin Disk Cycle routines*/

BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
{   
    if(BME_vert_in_edge(e, v)){
        if(e->v1 == v) return e->d1.next->data;
        else if(e->v2 == v) return e->d2.next->data;
    }
    return NULL;
}

BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
    /*returns pointer to the cycle node for the appropriate vertex in this disk*/
    if(e->v1 == v) return &(e->d1);
    else if (e->v2 == v) return &(e->d2);
    return NULL;
}

int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
{ 
    
    BME_CycleNode *base, *tail;
    
    if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
    
    /*check for loose vert first*/
    if(v->edge == NULL){
        v->edge = e;
        base = tail = BME_disk_getpointer(e, v);
        BME_cycle_append(base, tail); /*circular reference is ok!*/
        return 1;
    }
    
    /*insert e at the end of disk cycle and make it the new v->edge*/
    base = BME_disk_getpointer(v->edge, v);
    tail = BME_disk_getpointer(e, v);
    BME_cycle_append(base, tail);
    return 1;
}

void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
{
    BME_CycleNode *base, *remnode;
    BME_Edge *newbase;
    int len;
    
    base = BME_disk_getpointer(v->edge, v);
    remnode = BME_disk_getpointer(e, v);
    
    /*first deal with v->edge pointer...*/
    len = BME_cycle_length(base);
    if(len == 1) newbase = NULL;
    else if(v->edge == e) newbase = base->next-> data;
    else newbase = v->edge;
    
    /*remove and rebase*/
    BME_cycle_remove(base, remnode);
    v->edge = newbase;
}

BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
    
    /* BME_CycleNode *diskbase; */ /* UNUSED */
    BME_Edge *curedge;
    int /* len, */ /* UNUSED */ ok;
    
    if(eflag && tflag) return NULL;
    
    ok = BME_vert_in_edge(e,v);
    if(ok){
        /* diskbase = BME_disk_getpointer(e, v); */ /* UNUSED */
        /* len = BME_cycle_length(diskbase); */ /* UNUSED */
        curedge = BME_disk_nextedge(e,v);
        while(curedge != e){
            if(tflag){
                if(curedge->tflag1 == tflag) return curedge;
            }
            else if(eflag){
                if(curedge->eflag1 == eflag) return curedge;
            }
            curedge = BME_disk_nextedge(curedge, v);
        }
    }
    return NULL;
}

int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
    BME_CycleNode *diskbase;
    BME_Edge *curedge;
    int i, len=0, count=0;
    
    if(v->edge){
        if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
        diskbase = BME_disk_getpointer(v->edge, v);
        len = BME_cycle_length(diskbase);
        
        for(i = 0, curedge=v->edge; i<len; i++){
            if(tflag){
                if(curedge->tflag1 == tflag) count++;
            }
            else if(eflag){
                if(curedge->eflag1 == eflag) count++;
            }
            curedge = BME_disk_nextedge(curedge, v);
        }
    }
    return count;
}

int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
    BME_CycleNode *diskbase;
    BME_Edge *curedge;
    int i, len=0;
    
    if(v->edge){
        diskbase = BME_disk_getpointer(v->edge,v);
        len = BME_cycle_length(diskbase);
        
        for(i = 0, curedge=v->edge; i<len; i++){
            if(curedge == e) return 1;
            else curedge=BME_disk_nextedge(curedge, v);
        }
    }
    return 0;
}
/*end disk cycle routines*/

BME_Loop *BME_radial_nextloop(BME_Loop *l){
    return (BME_Loop*)(l->radial.next->data);
}

void BME_radial_append(BME_Edge *e, BME_Loop *l){
    if(e->loop == NULL) e->loop = l;
    BME_cycle_append(&(e->loop->radial), &(l->radial));
}

void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
{
    BME_Loop *newbase;
    int len;
    
    /*deal with edge->loop pointer*/
    len = BME_cycle_length(&(e->loop->radial));
    if(len == 1) newbase = NULL;
    else if(e->loop == l) newbase = e->loop->radial.next->data;
    else newbase = e->loop;
    
    /*remove and rebase*/
    BME_cycle_remove(&(e->loop->radial), &(l->radial));
    e->loop = newbase;
}

int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
{
        
    BME_Loop *curloop;
    int i, len;
    
    len = BME_cycle_length(&(e->loop->radial));
    for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
        if(curloop->f == f) return 1;
    }
    return 0;
}

struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
    BME_Loop *l;
    int i, len;
    
    len = BME_cycle_length(f->loopbase);
    for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
        if (l->v == v) return l;
    }
    return NULL;
}