SaraP
cbec90699f
- creato il progetto in Visual Studio per compilare come libreria statica - modifiche al codice originale per integrarlo nelle nostre librerie.
652 lines
16 KiB
C++
652 lines
16 KiB
C++
/*****************************************************************************/
|
|
/* */
|
|
/* F I S T : Fast, Industrial-Strength Triangulation */
|
|
/* */
|
|
/*****************************************************************************/
|
|
/* */
|
|
/* (C) Martin Held */
|
|
/* (C) Universitaet Salzburg, Salzburg, Austria */
|
|
/* */
|
|
/* This code is not in the public domain. All rights reserved! Please make */
|
|
/* sure to read the full copyright statement contained in api_functions.cpp. */
|
|
/* */
|
|
/*****************************************************************************/
|
|
|
|
/* get standard i/o library */
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <assert.h>
|
|
|
|
/* get my header file */
|
|
#include "fpkernel.h"
|
|
#include "martin.h"
|
|
#include "defs.h"
|
|
#include "list.h"
|
|
#include "header.h"
|
|
|
|
/* */
|
|
/* function prototypes of functions provided in this file */
|
|
/* */
|
|
void RemoveZeroEdges(listdef* list, list_ind *ind);
|
|
void FreeList(listdef* list);
|
|
list_ind MakeHook(listdef* list);
|
|
void DeleteHook(listdef* list, int curr_loop);
|
|
int MakeLoopHeader(listdef* list);
|
|
void DecrementLoops(listdef* list);
|
|
list_ind MakeNode(listdef* list, int index);
|
|
void InsertAfter(listdef* list, list_ind ind1, list_ind ind2);
|
|
void DeleteLinks(listdef* list, list_ind ind);
|
|
list_ind FetchNextData(listdef* list, list_ind ind1, int *index);
|
|
list_ind FetchPrevData(listdef* list, list_ind ind1, int *index);
|
|
int CountListElements(listdef* list, list_ind ind1);
|
|
void UpdateIndex(listdef* list, list_ind ind, int index);
|
|
void SwapLinks(listdef* list, list_ind ind1);
|
|
boolean InPolyList(listdef* list, list_ind ind);
|
|
boolean InLoopList(listdef* list, int loop);
|
|
//void InitAngle(listdef* list, list_ind ind, int convex);
|
|
void ResetPolyList(listdef* list, list_ind ind);
|
|
list_ind GetNode(listdef* list);
|
|
int GetOriginal(listdef* list, list_ind ind);
|
|
void SetOriginal(listdef* list, list_ind ind, int original);
|
|
#ifdef NORMALS
|
|
void SetTexNormData(listdef* list, list_ind ind, int index1, int index2);
|
|
int GetNormalIndex(listdef* list, list_ind ind);
|
|
int GetTextureIndex(listdef* list, list_ind ind);
|
|
#endif
|
|
void SplitSplice(listdef* list, list_ind ind1, list_ind ind2, list_ind ind3, list_ind ind4);
|
|
void RotateLinks(listdef* list, list_ind ind1, list_ind ind2);
|
|
void ResetListData(listdef* list);
|
|
void StoreChain(listdef* list, list_ind ind);
|
|
list_ind GetNextChain(listdef* list, boolean *done);
|
|
void InitStorageList(listdef* list, int number);
|
|
void InitStorageLoops(listdef* list, int number);
|
|
void InitFace(listdef* list, int number);
|
|
void DecrementFaces(listdef* list);
|
|
int GetNumList(listdef* list);
|
|
boolean GetBridgeNode(listdef* list, list_ind ind);
|
|
void SetBridgeNodePair(listdef* list, list_ind ind1, list_ind ind2);
|
|
#ifdef PARTITION_FIST
|
|
boolean isCorner(global_struct *all, int current_partition, list_ind ind);
|
|
#endif
|
|
|
|
#define MEGA_BLOCK_SIZE 65536
|
|
#define BLOCK_SIZE 16384
|
|
#define HALF_BLOCK_SIZE 512
|
|
#define MARK_LIST_BOUND 40
|
|
|
|
void InitListDefaults(listdef* list)
|
|
{
|
|
list->list = (list_node*)NULL;
|
|
list->num_list = 0;
|
|
list->max_num_list = 0;
|
|
|
|
list->loops = (list_ind*)NULL;
|
|
list->num_loops = 0;
|
|
list->max_num_loops = 0;
|
|
|
|
list->faces = (int*)NULL;
|
|
list->num_faces = 0;
|
|
list->max_num_faces = 0;
|
|
|
|
list->first_node = 0;
|
|
|
|
list->chains = (list_ind*)NULL;
|
|
list->num_chains = 0;
|
|
list->max_num_chains = 0;
|
|
}
|
|
|
|
|
|
int GetNumList(listdef* list)
|
|
{
|
|
return list->num_list;
|
|
}
|
|
|
|
|
|
void ResetListData(listdef* list)
|
|
{
|
|
list->num_list = 0;
|
|
list->num_chains = 0;
|
|
list->first_node = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
void FreeList(listdef* list)
|
|
{
|
|
FreeMemory(list->memptr, (void**) &list->list, "list:list");
|
|
FreeMemory(list->memptr, (void**) &list->loops, "list:loops");
|
|
FreeMemory(list->memptr, (void**) &list->faces, "list:faces");
|
|
FreeMemory(list->memptr, (void**) &list->chains, "list:chains");
|
|
|
|
list->max_num_list = 0;
|
|
list->num_list = 0;
|
|
list->max_num_loops = 0;
|
|
list->num_loops = 0;
|
|
list->max_num_chains = 0;
|
|
list->num_chains = 0;
|
|
list->max_num_faces = 0;
|
|
list->num_faces = 0;
|
|
|
|
return;
|
|
}
|
|
|
|
#ifdef PARTITION_FIST
|
|
boolean isCorner(global_struct *all, int current_partition, list_ind ind) {
|
|
if (ind == all->corner_nodes[current_partition])
|
|
return true;
|
|
if (ind == all->corner_nodes[(current_partition+1) % all->number_of_heaps])
|
|
return true;
|
|
|
|
return false;
|
|
}
|
|
#endif
|
|
|
|
|
|
/* */
|
|
/* allocates storage for a dummy list node; pointers are set to itself; */
|
|
/* returns pointer to node */
|
|
/* */
|
|
list_ind MakeHook(listdef* list)
|
|
{
|
|
list_ind ind;
|
|
list_node *addr;
|
|
|
|
if (list->num_list >= list->max_num_list) {
|
|
list->max_num_list += MEGA_BLOCK_SIZE;
|
|
list->list = (list_node*) ReallocateArray(list->memptr, list->list, list->max_num_list,
|
|
sizeof(list_node), "list:list");
|
|
}
|
|
ind = list->num_list;
|
|
addr = &(list->list[list->num_list]);
|
|
addr->prev = ind;
|
|
addr->next = ind;
|
|
addr->index = NIL;
|
|
addr->bridge = false;
|
|
#ifdef PARTITION_FIST
|
|
addr->delete_reflex = false;
|
|
#endif
|
|
++list->num_list;
|
|
|
|
return ind;
|
|
}
|
|
|
|
|
|
|
|
void DeleteHook(listdef* list, int curr_loop)
|
|
{
|
|
list_ind ind1, ind2;
|
|
|
|
assert(InLoopList(list,curr_loop));
|
|
ind1 = list->loops[curr_loop];
|
|
assert(InPolyList(list,ind1));
|
|
ind2 = list->list[ind1].next;
|
|
assert(InPolyList(list,ind2));
|
|
DeleteLinks(list,ind1);
|
|
list->loops[curr_loop] = ind2;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
int MakeLoopHeader(listdef* list)
|
|
{
|
|
int i;
|
|
list_ind ind;
|
|
|
|
ind = MakeHook(list);
|
|
|
|
if (list->num_loops >= list->max_num_loops) {
|
|
list->max_num_loops += BLOCK_SIZE;
|
|
list->loops = (list_ind*) ReallocateArray(list->memptr, list->loops, list->max_num_loops,
|
|
sizeof(list_ind), "list:loops");
|
|
}
|
|
list->loops[list->num_loops] = ind;
|
|
i = list->num_loops;
|
|
++list->num_loops;
|
|
|
|
return i;
|
|
}
|
|
|
|
|
|
|
|
void DecrementLoops(listdef* list)
|
|
{
|
|
assert(list->num_loops > 0);
|
|
--list->num_loops;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void InitStorageList(listdef* list, int number)
|
|
{
|
|
if (number >= list->max_num_list) {
|
|
list->max_num_list = number;
|
|
list->list = (list_node*) ReallocateArray(list->memptr, list->list, list->max_num_list,
|
|
sizeof(list_node), "list:list");
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
void InitStorageLoops(listdef* list, int number)
|
|
{
|
|
if (number >= list->max_num_loops) {
|
|
list->max_num_loops = number;
|
|
list->loops = (list_ind*) ReallocateArray(list->memptr, list->loops, list->max_num_loops,
|
|
sizeof(list_ind), "list:loops");
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
/* */
|
|
/* allocates storage for a new list node, and stores the index of the point */
|
|
/* at this node; pointers are set to NIL; returns pointer to node */
|
|
/* */
|
|
list_ind MakeNode(listdef* list, int index)
|
|
{
|
|
list_ind ind;
|
|
list_node *addr;
|
|
|
|
if (list->num_list >= list->max_num_list) {
|
|
list->max_num_list += BLOCK_SIZE;
|
|
list->list = (list_node*) ReallocateArray(list->memptr, list->list, list->max_num_list,
|
|
sizeof(list_node), "list:list");
|
|
}
|
|
ind = list->num_list;
|
|
addr = &(list->list[list->num_list]);
|
|
addr->index = index;
|
|
addr->prev = NIL;
|
|
addr->next = NIL;
|
|
addr->bridge = false;
|
|
#ifdef PARTITION_FIST
|
|
addr->delete_reflex = false;
|
|
#endif
|
|
++list->num_list;
|
|
|
|
return ind;
|
|
}
|
|
|
|
|
|
/* */
|
|
/* inserts node ind2 after node ind1 */
|
|
/* */
|
|
void InsertAfter(listdef* list, list_ind ind1, list_ind ind2)
|
|
{
|
|
list_ind ind3;
|
|
|
|
assert(InPolyList(list,ind1));
|
|
assert(InPolyList(list,ind2));
|
|
list->list[ind2].next = list->list[ind1].next;
|
|
list->list[ind2].prev = ind1;
|
|
list->list[ind1].next = ind2;
|
|
ind3 = list->list[ind2].next;
|
|
assert(InPolyList(list,ind3));
|
|
list->list[ind3].prev = ind2;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
/* */
|
|
/* deletes node ind from list (with destroying its data fields) */
|
|
/* */
|
|
void DeleteLinks(listdef* list, list_ind ind)
|
|
{
|
|
list_node *addr;
|
|
|
|
assert(InPolyList(list,ind));
|
|
addr = &(list->list[ind]);
|
|
assert(InPolyList(list,addr->prev));
|
|
assert(InPolyList(list,addr->next));
|
|
if (list->first_node == ind) list->first_node = addr->next;
|
|
list->list[addr->next].prev = addr->prev;
|
|
list->list[addr->prev].next = addr->next;
|
|
addr->prev = addr->next = ind;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
/* */
|
|
/* returns pointer to the successor ind2 of ind1, and its data */
|
|
/* */
|
|
list_ind FetchNextData(listdef* list, list_ind ind1, int *index)
|
|
{
|
|
list_ind ind2;
|
|
|
|
assert(InPolyList(list,ind1));
|
|
ind2 = list->list[ind1].next;
|
|
assert(InPolyList(list,ind2));
|
|
*index = list->list[ind2].index;
|
|
|
|
return ind2;
|
|
}
|
|
|
|
|
|
|
|
|
|
/* */
|
|
/* returns pointer to the successor ind2 of ind1, and its data */
|
|
/* */
|
|
list_ind FetchPrevData(listdef* list, list_ind ind1, int *index)
|
|
{
|
|
list_ind ind2;
|
|
|
|
assert(InPolyList(list,ind1));
|
|
ind2 = list->list[ind1].prev;
|
|
assert(InPolyList(list,ind2));
|
|
*index = list->list[ind2].index;
|
|
|
|
return ind2;
|
|
}
|
|
|
|
|
|
|
|
|
|
/* */
|
|
/* this function counts the number of elements of a circular list */
|
|
/* */
|
|
int CountListElements(listdef* list, list_ind ind1)
|
|
{
|
|
int num_ele = 1;
|
|
list_ind ind2;
|
|
|
|
assert(InPolyList(list,ind1));
|
|
ind2 = list->list[ind1].next;
|
|
|
|
while (ind2 != ind1) {
|
|
assert(InPolyList(list,ind2));
|
|
++num_ele;
|
|
ind2 = list->list[ind2].next;
|
|
}
|
|
|
|
return num_ele;
|
|
}
|
|
|
|
|
|
|
|
void UpdateIndex(listdef* list, list_ind ind, int index)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
list->list[ind].index = index;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
/* */
|
|
/* swap the list pointers in order to change the orientation */
|
|
/* */
|
|
void SwapLinks(listdef* list, list_ind ind1)
|
|
{
|
|
list_ind ind2, ind3;
|
|
|
|
assert(InPolyList(list,ind1));
|
|
ind2 = list->list[ind1].next;
|
|
assert(InPolyList(list,ind2));
|
|
list->list[ind1].next = list->list[ind1].prev;
|
|
list->list[ind1].prev = ind2;
|
|
ind3 = ind2;
|
|
while (ind2 != ind1) {
|
|
assert(InPolyList(list,ind2));
|
|
ind3 = list->list[ind2].next;
|
|
list->list[ind2].next = list->list[ind2].prev;
|
|
list->list[ind2].prev = ind3;
|
|
ind2 = ind3;
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
boolean InPolyList(listdef* list, list_ind ind)
|
|
{
|
|
return ((ind >= 0) && (ind < list->num_list) && (list->num_list <= list->max_num_list));
|
|
}
|
|
|
|
|
|
|
|
boolean InLoopList(listdef* list, int loop)
|
|
{
|
|
return ((loop >= 0) && (loop < list->num_loops) &&
|
|
(list->num_loops <= list->max_num_loops));
|
|
}
|
|
|
|
|
|
|
|
|
|
void ResetPolyList(listdef* list, list_ind ind)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
list->first_node = ind;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
list_ind GetNode(listdef* list)
|
|
{
|
|
assert(InPolyList(list,list->first_node));
|
|
|
|
return list->first_node;
|
|
}
|
|
|
|
|
|
|
|
int GetOriginal(listdef* list, list_ind ind)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
return list->list[ind].original;
|
|
}
|
|
|
|
|
|
|
|
void SetOriginal(listdef* list, list_ind ind, int original)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
list->list[ind].original = original;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
boolean GetBridgeNode(listdef* list, list_ind ind)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
|
|
return list->list[ind].bridge;
|
|
}
|
|
|
|
|
|
void SetBridgeNodePair(listdef* list, list_ind ind1, list_ind ind2)
|
|
{
|
|
assert(InPolyList(list,ind1));
|
|
assert(InPolyList(list,ind2));
|
|
|
|
list->list[ind1].bridge = true;
|
|
list->list[ind2].bridge = true;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
#ifdef NORMALS
|
|
void SetTexNormData(listdef* list, list_ind ind, int t_index, int n_index)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
list->list[ind].t_index = t_index;
|
|
list->list[ind].n_index = n_index;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
int GetTextureIndex(listdef* list, list_ind ind)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
|
|
return list->list[ind].t_index;
|
|
}
|
|
|
|
|
|
int GetNormalIndex(listdef* list, list_ind ind)
|
|
{
|
|
assert(InPolyList(list,ind));
|
|
|
|
return list->list[ind].n_index;
|
|
}
|
|
#endif
|
|
|
|
|
|
|
|
void SplitSplice(listdef* list, list_ind ind1, list_ind ind2, list_ind ind3, list_ind ind4)
|
|
{
|
|
assert(InPolyList(list,ind1));
|
|
assert(InPolyList(list,ind2));
|
|
assert(InPolyList(list,ind3));
|
|
assert(InPolyList(list,ind4));
|
|
assert(list->list[ind1].next == ind2);
|
|
assert(list->list[ind2].prev == ind1);
|
|
assert(list->list[ind3].next == ind4);
|
|
assert(list->list[ind4].prev == ind3);
|
|
|
|
list->list[ind1].next = ind4;
|
|
list->list[ind4].prev = ind1;
|
|
list->list[ind2].prev = ind3;
|
|
list->list[ind3].next = ind2;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void RotateLinks(listdef* list, list_ind ind1, list_ind ind2)
|
|
{
|
|
list_ind ind;
|
|
list_ind ind0, ind3;
|
|
|
|
assert(InPolyList(list,ind1));
|
|
assert(InPolyList(list,ind2));
|
|
ind0 = list->list[ind1].next;
|
|
ind3 = list->list[ind2].next;
|
|
assert(InPolyList(list,ind0));
|
|
assert(InPolyList(list,ind3));
|
|
|
|
Swap(list->list[ind1].next, list->list[ind2].next, ind);
|
|
list->list[ind0].prev = ind2;
|
|
list->list[ind3].prev = ind1;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void StoreChain(listdef* list, list_ind ind)
|
|
{
|
|
if (list->num_chains >= list->max_num_chains) {
|
|
list->max_num_chains += HALF_BLOCK_SIZE;
|
|
list->chains = (list_ind*) ReallocateArray(list->memptr, list->chains, list->max_num_chains,
|
|
sizeof(list_ind), "list:chains");
|
|
}
|
|
list->chains[list->num_chains] = ind;
|
|
++list->num_chains;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
|
|
list_ind GetNextChain(listdef* list, boolean *done)
|
|
{
|
|
if (list->num_chains > 0) {
|
|
*done = true;
|
|
--list->num_chains;
|
|
return list->chains[list->num_chains];
|
|
}
|
|
else {
|
|
*done = false;
|
|
list->num_chains = 0;
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
void InitFace(listdef* list, int number)
|
|
{
|
|
if (list->num_faces >= list->max_num_faces) {
|
|
list->max_num_faces += BLOCK_SIZE;
|
|
list->faces = (int*) ReallocateArray(list->memptr, list->faces, list->max_num_faces,
|
|
sizeof(int), "list:faces");
|
|
}
|
|
list->faces[list->num_faces] = number;
|
|
++list->num_faces;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void DecrementFaces(listdef* list)
|
|
{
|
|
assert(list->num_faces > 0);
|
|
--list->num_faces;
|
|
|
|
return;
|
|
}
|
|
|
|
|
|
|
|
void RemoveZeroEdges(listdef* list, list_ind *ind)
|
|
{
|
|
list_ind ind1, ind2, ind3;
|
|
int i1, i2;
|
|
|
|
ind1 = *ind;
|
|
i1 = GetIndex(list,ind1);
|
|
ind2 = GetNextNode(list,ind1);
|
|
do {
|
|
i2 = GetIndex(list,ind2);
|
|
if (i1 == i2) {
|
|
ind3 = GetNextNode(list,ind2);
|
|
DeleteLinks(list,ind2);
|
|
ind2 = ind3;
|
|
}
|
|
else {
|
|
i1 = i2;
|
|
ind2 = GetNextNode(list,ind2);
|
|
}
|
|
} while (ind2 != ind1);
|
|
|
|
i2 = GetIndex(list,ind2);
|
|
if (i1 == i2) {
|
|
*ind = GetNextNode(list,ind2);
|
|
DeleteLinks(list,ind1);
|
|
}
|
|
|
|
return;
|
|
}
|