Line data    Source code

       1           0 : /*
       2             : 
       3             : Octree.h
       4             : 
       5             : Octtree class for collision detection.
       6             : 
       7             : Oolite
       8             : Copyright (C) 2004-2013 Giles C Williams and contributors
       9             : 
      10             : This program is free software; you can redistribute it and/or
      11             : modify it under the terms of the GNU General Public License
      12             : as published by the Free Software Foundation; either version 2
      13             : of the License, or (at your option) any later version.
      14             : 
      15             : This program is distributed in the hope that it will be useful,
      16             : but WITHOUT ANY WARRANTY; without even the implied warranty of
      17             : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      18             : GNU General Public License for more details.
      19             : 
      20             : You should have received a copy of the GNU General Public License
      21             : along with this program; if not, write to the Free Software
      22             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
      23             : MA 02110-1301, USA.
      24             : 
      25             : */
      26             : 
      27             : #import "OOCocoa.h"
      28             : #import "OOOpenGL.h"
      29             : #import "OOMaths.h"
      30             : 
      31           0 : #define OCTREE_MIN_HALF_WIDTH   1.0
      32             : 
      33             : 
      34             : #if !defined(OODEBUGLDRAWING_DISABLE) && defined(NDEBUG)
      35             : #define OODEBUGLDRAWING_DISABLE 1
      36             : #endif
      37             : 
      38             : 
      39           0 : @interface Octree: NSObject
      40             : {
      41             : @private
      42           0 :         GLfloat                         _radius;
      43           0 :         uint32_t                        _nodeCount;
      44           0 :         const int                       *_octree;
      45           0 :         BOOL                            _hasCollision;
      46             :         
      47           0 :         unsigned char           *_collisionOctree;
      48             :         
      49           0 :         NSData                          *_data;
      50             : }
      51             : 
      52             : /*
      53             :         - (id) initWithDictionary:
      54             :         
      55             :         Deserialize an octree from cache representation.
      56             :         (To make a new octree, build it with OOOctreeBuilder.)
      57             : */
      58           0 : - (id) initWithDictionary:(NSDictionary *)dictionary;
      59             : 
      60           0 : - (Octree *) octreeScaledBy:(GLfloat)factor;
      61             : 
      62             : #ifndef OODEBUGLDRAWING_DISABLE
      63           0 : - (void) drawOctree;
      64           0 : - (void) drawOctreeCollisions;
      65             : #endif
      66             : 
      67           0 : - (GLfloat) isHitByLine:(Vector)v0 :(Vector)v1;
      68             : 
      69           0 : - (BOOL) isHitByOctree:(Octree *)other withOrigin:(Vector)origin andIJK:(Triangle)ijk;
      70           0 : - (BOOL) isHitByOctree:(Octree *)other withOrigin:(Vector)origin andIJK:(Triangle)ijk andScales:(GLfloat)s1 :(GLfloat)s2;
      71             : 
      72           0 : - (NSDictionary *) dictionaryRepresentation;
      73             : 
      74           0 : - (GLfloat) volume;
      75             : 
      76           0 : - (Vector) randomPoint;
      77             : 
      78             : 
      79             : #ifndef NDEBUG
      80           0 : - (size_t) totalSize;
      81             : #endif
      82             : 
      83             : @end
      84             : 
      85             : 
      86           0 : enum
      87             : {
      88             :         kMaxOctreeDepth = 7     // 128x128x128
      89             : };
      90             : 
      91             : 
      92           0 : @interface OOOctreeBuilder: NSObject
      93             : {
      94             : @private
      95           0 :         int                                     *_octree;
      96           0 :         uint_fast32_t           _nodeCount, _capacity;
      97           0 :         struct OOOctreeBuildState
      98             :         {
      99           0 :                 uint32_t                        insertionPoint;
     100           0 :                 uint32_t                        remaining;
     101           0 :         }                                       _stateStack[kMaxOctreeDepth + 1];
     102           0 :         uint_fast8_t            _level;
     103             : }
     104             : 
     105             : /*
     106             :         -buildOctreeWithRadius:(GLfloat)radius
     107             :         
     108             :         Generate an octree with the current data in the builder and the specified
     109             :         radius, and clear the builder. If NDEBUG is undefined, throws an exception
     110             :         if the structure of the octree is invalid.
     111             : */
     112           0 : - (Octree *) buildOctreeWithRadius:(GLfloat)radius;
     113             : 
     114             : /*
     115             :         Append nodes to the octree.
     116             :         
     117             :         There are three types of nodes: solid, empty, and inner nodes.
     118             :         An inner node must have exactly eight children, which may be any type of
     119             :         node. Exactly one node must be added at root level.
     120             :         
     121             :         The order of child nodes is defined as follows: the index of a child node
     122             :         is a three bit number. The highest bit represents x, the middle bit
     123             :         represents y and the low bit represents z. A set bit indicates the high-
     124             :         coordinate half of the parent node, and a clear bit indicates the low-
     125             :         coordinate half.
     126             :         
     127             :         For instance, if the parent node is a cube ranging from -1 to 1 on each
     128             :         axis, the child 101 (5) represents x 0..1, y -1..0, z 0..1.
     129             : */
     130           0 : - (void) writeSolid;
     131           0 : - (void) writeEmpty;
     132           0 : - (void) beginInnerNode;
     133           0 : - (void) endInnerNode;
     134             : 
     135             : @end