[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [15104] branches/soc-2008-jaguarandi/ source/blender/blenlib: Removed BLI_kdopbvh
André Pinto
andresusanopinto at gmail.com
Tue Jun 3 21:20:58 CEST 2008
Revision: 15104
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=15104
Author: jaguarandi
Date: 2008-06-03 21:20:57 +0200 (Tue, 03 Jun 2008)
Log Message:
-----------
Removed BLI_kdopbvh
Removed Paths:
-------------
branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
Deleted: branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-06-03 19:06:54 UTC (rev 15103)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/BLI_kdopbvh.h 2008-06-03 19:20:57 UTC (rev 15104)
@@ -1,77 +0,0 @@
-/**
- *
- * ***** 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.
- *
- * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
- *
- * The Original Code is Copyright (C) 2006 by NaN Holding BV.
- * All rights reserved.
- *
- * The Original Code is: all of this file.
- *
- * Contributor(s): Daniel Genrich, Andre Pinto
- *
- * ***** END GPL LICENSE BLOCK *****
- */
-
-
-#ifndef BLI_KDOPBVH_H
-#define BLI_KDOPBVH_H
-
-#include <float.h>
-
-struct BVHTree;
-typedef struct BVHTree BVHTree;
-
-typedef struct BVHTreeOverlap {
- int indexA;
- int indexB;
-} BVHTreeOverlap;
-
-typedef struct BVHTreeNearest
-{
- int index; /* the index of the nearest found (untouched if none is found within a dist radius from the given coordinates) */
- float nearest[3]; /* nearest coordinates (untouched it none is found within a dist radius from the given coordinates) */
- float dist; /* squared distance to search arround */
-} BVHTreeNearest;
-
-/* returns square of the minimum distance from given co to the node, nearest point is stored on nearest */
-typedef float (*BVHTree_NearestPointCallback) (void *userdata, int index, const float *co, float *nearest);
-
-
-BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
-void BLI_bvhtree_free(BVHTree *tree);
-
-/* construct: first insert points, then call balance */
-int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints);
-void BLI_bvhtree_balance(BVHTree *tree);
-
-/* update: first update points/nodes, then call update_tree to refit the bounding volumes */
-int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_moving, int numpoints);
-void BLI_bvhtree_update_tree(BVHTree *tree);
-
-/* collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value */
-BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result);
-
-float BLI_bvhtree_getepsilon(BVHTree *tree);
-
-/* find nearest node to the given coordinates (if nearest is given it will only search nodes where square distance is smaller than nearest->dist) */
-int BLI_bvhtree_find_nearest(BVHTree *tree, float *co, BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata);
-
-#endif // BLI_KDOPBVH_H
-
-
-
-
Deleted: branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c
===================================================================
--- branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-06-03 19:06:54 UTC (rev 15103)
+++ branches/soc-2008-jaguarandi/source/blender/blenlib/intern/BLI_kdopbvh.c 2008-06-03 19:20:57 UTC (rev 15104)
@@ -1,988 +0,0 @@
-/* kdop.c
-*
-*
-* ***** BEGIN GPL/BL DUAL 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. The Blender
-* Foundation also sells licenses for usinle in proprietary software under
-* the Blender License. See http://www.blender.org/BL/ for information
-* 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-*
-* The Original Code is Copyright (C) Blender Foundation
-* All rights reserved.
-*
-* The Original Code is: all of this file.
-*
-* Contributor(s): Daniel Genrich, Andre Pinto
-*
-* ***** END GPL/BL DUAL LICENSE BLOCK *****
-*/
-
-#include "math.h"
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "MEM_guardedalloc.h"
-
-#include "BKE_utildefines.h"
-
-#include "BLI_kdopbvh.h"
-#include "BLI_arithb.h"
-
-#ifdef _OPENMP
-#include <omp.h>
-#endif
-
-#define node_get_bv(tree, node) ((node)->bv)
-#define node_get_child(tree,node,i) ((node)->children[i])
-
-/* Util macros */
-#define TO_STR(a) #a
-#define JOIN(a,b) a##b
-
-/* Benchmark macros */
-#if 1
-
-#define BENCH(a) \
- do { \
- clock_t _clock_init = clock(); \
- (a); \
- printf("%s: %fms\n", #a, (float)(clock()-_clock_init)*1000/CLOCKS_PER_SEC); \
-} while(0)
-
-#define BENCH_VAR(name) clock_t JOIN(_bench_step,name) = 0, JOIN(_bench_total,name) = 0
-#define BENCH_BEGIN(name) JOIN(_bench_step, name) = clock()
-#define BENCH_END(name) JOIN(_bench_total,name) += clock() - JOIN(_bench_step,name)
-#define BENCH_RESET(name) JOIN(_bench_total, name) = 0
-#define BENCH_REPORT(name) printf("%s: %fms\n", TO_STR(name), JOIN(_bench_total,name)*1000.0f/CLOCKS_PER_SEC)
-
-#else
-
-#define BENCH(a) (a)
-#define BENCH_VAR(name)
-#define BENCH_BEGIN(name)
-#define BENCH_END(name)
-#define BENCH_RESET(name)
-#define BENCH_REPORT(name)
-
-#endif
-
-
-typedef struct BVHNode
-{
- struct BVHNode **children;// max 8 children
- struct BVHNode *parent; // needed for bottom - top update
- float *bv; // Bounding volume of all nodes, max 13 axis
- int index; // face, edge, vertex index
- char totnode; // how many nodes are used, used for speedup
- char traversed; // how many nodes already traversed until this level?
- char main_axis; // axis that was used to split childs
-} BVHNode;
-
-struct BVHTree
-{
- BVHNode **nodes;
- BVHNode *nodearray; // pre-alloc branchs
- BVHNode **nodechild; // pre-alloc childs for nodes
- float *nodebv; // pre-alloc bounding-volumes for nodes
- float epsilon; // epslion is used for inflation of the k-dop
- int totleaf; // leafs
- int totbranch;
- char tree_type; // type of tree (4 => quadtree)
- char axis; // kdop type (6 => OBB, 7 => AABB, ...)
- char start_axis, stop_axis; // KDOP_AXES array indices according to axis char start_axis, stop_axis; // KDOP_AXES array indices according to axis
-};
-
-typedef struct BVHOverlapData
-{
- BVHTree *tree1, *tree2;
- BVHTreeOverlap *overlap;
- int i, max_overlap; /* i is number of overlaps */
-} BVHOverlapData;
-
-typedef struct BVHNearestData
-{
- BVHTree *tree;
- float *co;
- BVHTree_NearestPointCallback callback;
- void *userdata;
- float proj[13]; //coordinates projection over axis
- BVHTreeNearest nearest;
-} BVHNearestData;
-////////////////////////////////////////
-
-
-////////////////////////////////////////////////////////////////////////
-// Bounding Volume Hierarchy Definition
-//
-// Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
-// Notes: You have to choose the type at compile time ITM
-// Notes: You can choose the tree type --> binary, quad, octree, choose below
-////////////////////////////////////////////////////////////////////////
-
-static float KDOP_AXES[13][3] =
-{ {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0},
-{1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0},
-{0, 1.0, -1.0}
-};
-
-//////////////////////////////////////////////////////////////////////////////////////////////////////
-// Introsort
-// with permission deriven from the following Java code:
-// http://ralphunden.net/content/tutorials/a-guide-to-introsort/
-// and he derived it from the SUN STL
-//////////////////////////////////////////////////////////////////////////////////////////////////////
-static int size_threshold = 16;
-/*
-* Common methods for all algorithms
-*/
-static int floor_lg(int a)
-{
- return (int)(floor(log(a)/log(2)));
-}
-
-/*
-* Insertion sort algorithm
-*/
-static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
-{
- int i,j;
- BVHNode *t;
- for (i=lo; i < hi; i++)
- {
- j=i;
- t = a[i];
- while((j!=lo) && (t->bv[axis] < (a[j-1])->bv[axis]))
- {
- a[j] = a[j-1];
- j--;
- }
- a[j] = t;
- }
-}
-
-static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode * x, int axis)
-{
- int i=lo, j=hi;
- while (1)
- {
- while ((a[i])->bv[axis] < x->bv[axis]) i++;
- j--;
- while (x->bv[axis] < (a[j])->bv[axis]) j--;
- if(!(i < j))
- return i;
- SWAP( BVHNode* , a[i], a[j]);
- i++;
- }
-}
-
-/*
-* Heapsort algorithm
-*/
-static void bvh_downheap(BVHNode **a, int i, int n, int lo, int axis)
-{
- BVHNode * d = a[lo+i-1];
- int child;
- while (i<=n/2)
- {
- child = 2*i;
- if ((child < n) && ((a[lo+child-1])->bv[axis] < (a[lo+child])->bv[axis]))
- {
- child++;
- }
- if (!(d->bv[axis] < (a[lo+child-1])->bv[axis])) break;
- a[lo+i-1] = a[lo+child-1];
- i = child;
- }
- a[lo+i-1] = d;
-}
-
-static void bvh_heapsort(BVHNode **a, int lo, int hi, int axis)
-{
- int n = hi-lo, i;
- for (i=n/2; i>=1; i=i-1)
- {
- bvh_downheap(a, i,n,lo, axis);
- }
- for (i=n; i>1; i=i-1)
- {
- SWAP(BVHNode*, a[lo],a[lo+i-1]);
- bvh_downheap(a, 1,i-1,lo, axis);
- }
-}
-
-static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis) // returns Sortable
-{
- if ((a[mid])->bv[axis] < (a[lo])->bv[axis])
- {
- if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
- return a[mid];
- else
- {
- if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
- return a[hi];
- else
- return a[lo];
- }
- }
- else
- {
- if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
- {
- if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
- return a[lo];
- else
- return a[hi];
- }
- else
- return a[mid];
- }
-}
-/*
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list