diff options
author | Brecht Van Lommel <brechtvanlommel@pandora.be> | 2007-11-27 01:09:57 +0300 |
---|---|---|
committer | Brecht Van Lommel <brechtvanlommel@pandora.be> | 2007-11-27 01:09:57 +0300 |
commit | 7da56f4a9ba0bdd0cdcd40b8ca6e69d776d26abe (patch) | |
tree | 663c13aae5606937571ac1e7a4c77ca2866e75dd /source/blender/blenlib/intern/BLI_kdtree.c | |
parent | 121dab1bcd9467bd8e11d0a82e83a1621758fd8e (diff) | |
parent | 770291b9ea1ec03d98b6bae4fd2a2d3f0091be41 (diff) |
Particles
=========
Merge of the famous particle patch by Janne Karhu, a full rewrite
of the Blender particle system. This includes:
- Emitter, Hair and Reactor particle types.
- Newtonian, Keyed and Boids physics.
- Various particle visualisation and rendering types.
- Vertex group and texture control for various properties.
- Interpolated child particles from parents.
- Hair editing with combing, growing, cutting, .. .
- Explode modifier.
- Harmonic, Magnetic fields, and multiple falloff types.
.. and lots of other things, some more info is here:
http://wiki.blender.org/index.php/BlenderDev/Particles_Rewrite
http://wiki.blender.org/index.php/BlenderDev/Particles_Rewrite_Doc
The new particle system cannot be backwards compatible. Old particle
systems are being converted to the new system, but will require
tweaking to get them looking the same as before.
Point Cache
===========
The new system to replace manual baking, based on automatic caching
on disk. This is currently used by softbodies and the particle system.
See the Cache API section on:
http://wiki.blender.org/index.php/BlenderDev/PhysicsSprint
Documentation
=============
These new features still need good docs for the release logs, help
for this is appreciated.
Diffstat (limited to 'source/blender/blenlib/intern/BLI_kdtree.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdtree.c | 327 |
1 files changed, 327 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdtree.c b/source/blender/blenlib/intern/BLI_kdtree.c new file mode 100644 index 00000000000..dbb9e95d379 --- /dev/null +++ b/source/blender/blenlib/intern/BLI_kdtree.c @@ -0,0 +1,327 @@ +/** + * $Id$ + * + * ***** 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 use 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) 2001-2002 by NaN Holding BV. + * All rights reserved. + * + * The Original Code is: none of this file. + * + * Contributor(s): Janne Karhu + * Brecht Van Lommel + * + * ***** END GPL/BL DUAL LICENSE BLOCK ***** + */ + +#include <stdlib.h> +#include <string.h> +#include <math.h> + +#include "MEM_guardedalloc.h" + +#include "BLI_arithb.h" +#include "BLI_kdtree.h" + +#define SWAP(type, a, b) { type sw_ap; sw_ap=(a); (a)=(b); (b)=sw_ap; } + +typedef struct KDTreeNode { + struct KDTreeNode *left, *right; + float co[3], nor[3]; + int index; + short d; +} KDTreeNode; + +struct KDTree { + KDTreeNode *nodes; + int totnode; + KDTreeNode *root; +}; + +KDTree *BLI_kdtree_new(int maxsize) +{ + KDTree *tree; + + tree= MEM_callocN(sizeof(KDTree), "KDTree"); + tree->nodes= MEM_callocN(sizeof(KDTreeNode)*maxsize, "KDTreeNode"); + tree->totnode= 0; + + return tree; +} + +void BLI_kdtree_free(KDTree *tree) +{ + if(tree) { + MEM_freeN(tree->nodes); + MEM_freeN(tree); + } +} + +void BLI_kdtree_insert(KDTree *tree, int index, float *co, float *nor) +{ + KDTreeNode *node= &tree->nodes[tree->totnode++]; + + node->index= index; + VecCopyf(node->co, co); + if(nor) VecCopyf(node->nor, nor); +} + +static KDTreeNode *kdtree_balance(KDTreeNode *nodes, int totnode, int axis) +{ + KDTreeNode *node; + float co; + int left, right, median, i, j; + + if(totnode <= 0) + return NULL; + else if(totnode == 1) + return nodes; + + /* quicksort style sorting around median */ + left= 0; + right= totnode-1; + median= totnode/2; + + while(right > left) { + co= nodes[right].co[axis]; + i= left-1; + j= right; + + while(1) { + while(nodes[++i].co[axis] < co); + while(nodes[--j].co[axis] > co && j>left); + + if(i >= j) break; + SWAP(KDTreeNode, nodes[i], nodes[j]); + } + + SWAP(KDTreeNode, nodes[i], nodes[right]); + if(i >= median) + right= i-1; + if(i <= median) + left= i+1; + } + + /* set node and sort subnodes */ + node= &nodes[median]; + node->d= axis; + node->left= kdtree_balance(nodes, median, (axis+1)%3); + node->right= kdtree_balance(nodes+median+1, (totnode-(median+1)), (axis+1)%3); + + return node; +} + +void BLI_kdtree_balance(KDTree *tree) +{ + tree->root= kdtree_balance(tree->nodes, tree->totnode, 0); +} + +static float squared_distance(float *v1, float *v2, float *n1, float *n2) +{ + float d[3], dist; + + d[0]= v2[0]-v1[0]; + d[1]= v2[1]-v1[1]; + d[2]= v2[2]-v1[2]; + + dist= d[0]*d[0] + d[1]*d[1] + d[2]*d[2]; + + if(n1 && n2 && n1[0]*n2[0] + n1[1]*n2[1] + n1[2]*n2[2] < 0.0f) + dist *= 10.0f; + + return dist; +} + +int BLI_kdtree_find_nearest(KDTree *tree, float *co, float *nor, KDTreeNearest *nearest) +{ + KDTreeNode *root, *node, *min_node; + KDTreeNode **stack, *defaultstack[100]; + float min_dist, cur_dist; + int totstack, cur=0; + + if(!tree->root) + return -1; + + stack= defaultstack; + totstack= 100; + + root= tree->root; + min_node= root; + min_dist= squared_distance(root->co,co,root->nor,nor); + + if(root->left) + stack[cur++]=root->left; + + if(root->right) + stack[cur++]=root->right; + + while(cur--){ + node=stack[cur]; + + cur_dist = node->co[node->d] - co[node->d]; + + if(cur_dist<0.0){ + cur_dist= -cur_dist*cur_dist; + + if(-cur_dist<min_dist){ + cur_dist=squared_distance(node->co,co,node->nor,nor); + if(cur_dist<min_dist){ + min_dist=cur_dist; + min_node=node; + } + if(node->left) + stack[cur++]=node->left; + } + if(node->right) + stack[cur++]=node->right; + } + else{ + cur_dist= cur_dist*cur_dist; + + if(cur_dist<min_dist){ + cur_dist=squared_distance(node->co,co,node->nor,nor); + if(cur_dist<min_dist){ + min_dist=cur_dist; + min_node=node; + } + if(node->right) + stack[cur++]=node->right; + } + if(node->left) + stack[cur++]=node->left; + } + if(cur+3 > totstack){ + KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack"); + memcpy(temp,stack,totstack*sizeof(KDTreeNode*)); + if(stack != defaultstack) + MEM_freeN(stack); + stack=temp; + totstack+=100; + } + } + + if(nearest) { + nearest->index= min_node->index; + nearest->dist= sqrt(min_dist); + VecCopyf(nearest->co, min_node->co); + } + + if(stack != defaultstack) + MEM_freeN(stack); + + return min_node->index; +} + +static void add_nearest(KDTreeNearest *ptn, int *found, int n, int index, float dist, float *co) +{ + int i; + + if(*found<n) (*found)++; + + for(i=*found-1; i>0; i--) { + if(dist >= ptn[i-1].dist) + break; + else + ptn[i]= ptn[i-1]; + } + + ptn[i].index= index; + ptn[i].dist= dist; + VecCopyf(ptn[i].co, co); +} + +/* finds the nearest n entries in tree to specified coordinates */ +int BLI_kdtree_find_n_nearest(KDTree *tree, int n, float *co, float *nor, KDTreeNearest *nearest) +{ + KDTreeNode *root, *node=0; + KDTreeNode **stack, *defaultstack[100]; + float cur_dist; + int i, totstack, cur=0, found=0; + + if(!tree->root) + return 0; + + stack= defaultstack; + totstack= 100; + + root= tree->root; + + cur_dist= squared_distance(root->co,co,root->nor,nor); + add_nearest(nearest,&found,n,root->index,cur_dist,root->co); + + if(root->left) + stack[cur++]=root->left; + + if(root->right) + stack[cur++]=root->right; + + while(cur--){ + node=stack[cur]; + + cur_dist = node->co[node->d] - co[node->d]; + + if(cur_dist<0.0){ + cur_dist= -cur_dist*cur_dist; + + if(found<n || -cur_dist<nearest[found-1].dist){ + cur_dist=squared_distance(node->co,co,node->nor,nor); + + if(found<n || cur_dist<nearest[found-1].dist) + add_nearest(nearest,&found,n,node->index,cur_dist,node->co); + + if(node->left) + stack[cur++]=node->left; + } + if(node->right) + stack[cur++]=node->right; + } + else{ + cur_dist= cur_dist*cur_dist; + + if(found<n || cur_dist<nearest[found-1].dist){ + cur_dist=squared_distance(node->co,co,node->nor,nor); + if(found<n || cur_dist<nearest[found-1].dist) + add_nearest(nearest,&found,n,node->index,cur_dist,node->co); + + if(node->right) + stack[cur++]=node->right; + } + if(node->left) + stack[cur++]=node->left; + } + if(cur+3 > totstack){ + KDTreeNode **temp=MEM_callocN((totstack+100)*sizeof(KDTreeNode*), "psys_treestack"); + memcpy(temp,stack,totstack*sizeof(KDTreeNode*)); + if(stack != defaultstack) + MEM_freeN(stack); + stack=temp; + totstack+=100; + } + } + + for(i=0; i<found; i++) + nearest[i].dist= sqrt(nearest[i].dist); + + if(stack != defaultstack) + MEM_freeN(stack); + + return found; +} + |