Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] View of /branches/vis15/src/lib/include/diderot/kdtree.hxx
ViewVC logotype

View of /branches/vis15/src/lib/include/diderot/kdtree.hxx

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3916 - (download) (as text) (annotate)
Sat May 28 12:01:02 2016 UTC (2 years, 11 months ago) by jhr
File size: 2838 byte(s)
  Working on merge: code generation
/*! \file kdtree.hxx
 *
 * \author John Reppy
 */

/*
 * This code is part of the Diderot Project (http://diderot-language.cs.uchicago.edu)
 *
 * COPYRIGHT (c) 2016 The University of Chicago
 * All rights reserved.
 */

#ifndef _DIDEROT_KDTREE_HXX_
#define _DIDEROT_KDTREE_HXX_

#ifndef _DIDEROT_BASE_HXX_
#include "diderot/base.hxx"
#endif

#include <cmath>

#ifndef DIDEROT_STRANDS_PER_LEAF
#define DIDEROT_STRANDS_PER_LEAF	8
#endif

namespace diderot {

    namespace __details {

	struct KDNodeBase {
	    uint32_t	_nStrands;	// if this node is a leave, then this is 0.  Otherwise
					// it is the number of strands in _strands
	};

	struct KDNode : public KDNodeBase {
	    float	_split;		// split value for this axis
	    KDNodeBase	*_kids[2];
	};

	struct KDLeaf : public KDNodeBase {
	    uint32_t	_strands[DIDEROT_STRANDS_PER_LEAF];
	};

    } // namespace __details

    class KDTree {
      public:

      protected:
	__details::KDNode *new_node ();
	__details::KDLeaf *new_leaf ();

      private:
	__details::KDNodeBase	*_root;

	struct Chunk {
	    char	*_mem;
	    char	*_next;
	    char	*_limit;
	};

	std::vector<Chunk>	_chunks;	// memory pool
    };

  // are two 1D positions within a specified spherical radius?
    template <typename REAL>
    inline bool withinSphere1 (REAL pos1, REAL pos2, REAL radius)
    {
	return abs(pos1 - pos2) <= radius;
    }

  // are two 1D positions within a specified retangular radius?
    template <typename REAL>
    inline bool withinBox1 (REAL pos1, REAL pos2, REAL radius)
    {
	return abs(pos1 - pos2) <= radius;
    }

  // are two 2D positions within a specified spherical radius?
    template <typename REAL>
    inline bool withinSphere2 (vec2<REAL> pos1, vec2<REAL> pos2, REAL radius)
    {
	REAL dx = pos1[0] - pos2[0];
	REAL dy = pos1[1] - pos2[1];
	return (dx*dx + dy*dy) <= (radius * radius);
    }

  // are two 2D positions within a specified retangular radius?
    template <typename REAL>
    inline bool withinBox2 (vec2<REAL> pos1, vec2<REAL> pos2, REAL radius)
    {
	return withinBox(pos1[0], pos2[0], radius)
	    && withinBox(pos1[1], pos2[1], radius);
    }

  // are two 3D positions within a specified spherical radius?
    template <typename REAL>
    inline bool withinSphere3 (vec3<REAL> pos1, vec3<REAL> pos2, REAL radius)
    {
	REAL dx = pos1[0] - pos2[0];
	REAL dy = pos1[1] - pos2[1];
	REAL dz = pos1[2] - pos2[2];
	return (dx*dx + dy*dy + dz*dz) <= (radius * radius);
    }

  // are two 3D positions within a specified retangular radius?
    template <typename REAL>
    inline bool withinBox3 (vec3<REAL> pos1, vec3<REAL> pos2, REAL radius)
    {
	return withinBox(pos1[0], pos2[0], radius)
	    && withinBox(pos1[1], pos2[1], radius)
	    && withinBox(pos1[2], pos2[2], radius);
    }

} // namespace Diderot

#endif // !_DIDEROT_KDTREE_HXX_

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0