You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This PR adds a new package Octree. This is a tree data structure which subdivides 3d space, similar to kD_tree. The package will replace the Octree used in Shape Detection's RANSAC algorithm. See the GSoC wiki page or the compiled docs for more information.
b1d1e54 Implement nearest neighbor benchmark a868a82 Implement construction benchmark 8f03c71 Implement the point generating method 7464db9 Add an unimplemented utility for generating test datasets ea73c33 Perform tests non-linearly f570b32 Create csv files in both benchmarks eebf5e4 Add benchmark program files for construction and nearest_neighbor 7834778 Remove benchmarking code e482108 Reduce subheading depth by removing Usage header 7cfbd1f Add a sentence discussing when to use Intersection and nearest neighbor 9e431be Merge branch 'master' of github.com:CGAL/cgal into gsoc2020-Octree-campolattaro 985ef73 Move relevant includes inside test b4fc571 Remove unused includes e69db45 Merge branch 'gsoc2020-Octree-campolattaro' of https://github.com/JacksonCampolattaro/cgal into gsoc2020-Octree-campolattaro 6d95250 Add section "History" b1bdad0 remove trailing whitespace ceefaa7 fix project name 9bd127f Add descriptions for preorder traversal and nearest-neighbor 5f0538c Add a short description for manual traversal 910daba Add a short description for building with a custom split criterion. 3f9ae5f Add a short description for building from a point set fbd27e1 Add a short description for building from a point vector 61b36d8 Use bold text to indicate examples 488a295 Add headers for types of examples ca21aec Rename concept Split_criterion to SplitCriterion 6b887f4 Rename concept Split_criterion to SplitCriterion 2b01228 Add a brief and a short description to the intersection function 014237d Add parameter descriptions to the intersection method 7f20336 Add ray intersection test d29ec3d Implement sphere intersection test 7eda09d Test of intersection with point is now passing 59b6463 Add base case to recursive intersection function 34b007c Invoke recursive intersection function in public function b968807 Add recursive node intersection signature 91bdbe1 Remove leaves method e22430c Factor out the query primitive 142cf3b Add point intersection test assertions 268a9a9 Add intersecting_nodes invocations 58d7a83 Add scoped sections for each test 7daba0f Add intersection test to CMakeLists.txt 2a1485c Add empty intersection test 4d1baed Add intersecting_nodes method signature 88be3ad Update adjacent_node descriptions 18cfdfa Add a lookup table for the Direction enum d0a967c Add an ascii diagram for the Dimension enum 1882411 Add a lookup table 9eb8413 Shrink ascii diagram 083da62 Add description to Child enum with ascii diagram e45ada6 Add doxygen comments with briefs to both enums cabc6ac Implement Split_criterion concept 9f91ef2 Add items to the Classified Reference Pages list 0a0871f Remove include guards c0cfa64 Add Traversal concept aeabc18 Add empty "Split_criterion" and "Traversal" concept headers 2b11c41 Add to the grade example description 6386984 Implement grade example 1c60964 Add short description to grade example 5f316de Add empty Octree_grade example 3df1c47 Eliminate m_bbox_side member variable 493df76 Set m_side_per_depth directly, instead of using m_bbox_side 0803bef Use side_per_depth instead of bbox_side when checking equality a04482a Rename Direct_octree to RANSAC_octree 4c1473e Eliminate Indexed_octree 0cf29ea Initialize m_side_per_depth with length instead of 2 16a9cc5 Update max depth before splitting a387da4 Eliminate m_max_depth_reached value d21f428 Use max_depth_reached() to get depth in equality operator 1763564 Determine max depth by size of m_side_per_depth d2c54c0 Correct mistake updating max depth b8b1e2b Add tests concerning max depth 0b1c9a7 Add documentation to subscript operator ff12caa Add examples of using the subscript operator directly on the octree 02fc711 Add subscript operator for accessing children of the root node ca61bc2 Use Self typedef in equality operators 2d3d01a Use Self typedef in equality operators 63acc50 Add Self typedef fe24292 Add first values to side length mep during constructor 32a55ec Update refine function to remove limits on depth b31169f Update function invocations 9df95b7 Implement randomized grade() test 8ecfd7b Add description for grade() 5849067 Remove non-const node range and node traversal method typedefs 4c7a865 Eliminate Points_iterator_range 5182bff Add doxygen comment for operator!= 5e02c55 Add doxygen comment to Self typedef 100882c Add reminders to link other adjacency methods 88a99e0 Move adjacent_node to correct section 715b46d Add a doxygen description for adjacent_node d1b2f9c Add ascii quadtree for explaining adjacency c35a42a Incorporate unbalanced_neighbors_to_split into grade 3ca8683 Fix typos induced by blind word replacement 4a6eed5 Rename adjacent() to adjacent_node() be38237 Add non-const adjacent method 225473e Collect list of leaves using Leaves traversal with const_cast 8fde332 Refactor unbalanced_neighbors_to_split 1c7a52a Remove old greater_or_equal_neighbor method 902d176 Swap simple and complex refine() invocations 85af7a9 Move point vector example before point set example f123ecb Account for nodes adjacent to parent nodes 06b7047 Begin accounting for parent nodes e4ba2be Begin adding tests for children of children fa57a31 Add correctness tests b24275c Swap BACK/FRONT notation cb4f2ae Reverse negation by sign 60b79a4 Add Child enum 5d693e8 Add Direction enum 6eb55ec Add Self typedef to Node f622683 Add more root node tests a8daae7 Implement adjacent for direct siblings adf6b74 Add first test of adjacent b4f13d8 Implement bit operations that find the offset 474ca79 Begin implementing adjacent method c5591da Add empty test of node adjacency 8f91c93 Implement unbalanced_neighbors_to_split 0faf150 Begin implementing unbalanced_neighbors_to_split ad58923 Add greater_or_equal_neighbor stub df5fc72 Begin rewriting grade with more documentation 9cbe9d9 Add typedefs necessary for non-const traversal 79d680b Don't use output iterator to add nodes to queue e5d38cf Add recursive method for adding leaves to a queue c932607 Rename tree walk test to traverse 63c4d62 Use traversal to fill the leaf queue b70181c Implement visual grade() test 110885e Add grade test to CMakeLists.txt 95ac96c Add empty grade test 43302c8 Rename PointMap to Point_map a56ef32 Rename PointRange to Point_range f020e4f Set default template for point map 033d0d7 Rename Point_set to Point_vector 0e7a364 Update doxygen tag d1f5c8c Comment out custom traversal example 852740a Add description for vector octree example 9b23a59 Add description for manual and preorder traversal examples ad0fa67 Add description for nearest neighbor example 9f727d1 Rename walk to traverse 8091145 Add preorder traversal example 306bf5f Use a more verbose method to choose octree split criterion 897860d Add manual traversal example f6d41e7 Remove point map declaration before constructors ef948f1 Remove point map declaration before constructors 3627f4e Build octree without passing point map 4959864 Automatically construct point map if not passed c157e07 Pass point map directly (not by ref) 3563645 Add octree with vector demonstration ad96992 Finish nearest neighbor demonstration 4724a61 Begin implementing nearest neighbor example f0ef3d7 Add description to custom split criterion example 100fe8c Add split by ratio example ec3fca2 Add description to Vector tree example with placeholder file e1c964b Add description to Point_set tree example de09a1e Build the octree 1f9196b Load points from file ff6a043 Add data for testing 6bf3b23 Link example files 3281230 Set example path 2eb052b Add examples to examples.txt 6a4fd50 Add examples as single source programs dfba799 Rename examples for consistency 03328b2 Add more empty examples 81428c3 Add empty construction examples d6e67af Add examples directory with Cmake file 144f5a8 Remove redundant "Example" from example titles ec0f9c7 Add titles for several examples d07fa87 Update refine method of Direct octree to match indexed 6781a48 Add brackets to do-while loop for clarity 50dc514 Add brackets to keep_searching check for clarity 252fd07 Force bbox value to make sure it's not causing issues 2a85336 Disable randomness in scene test 5ce9381 Remove fixed seed for random generator e4f2a40 Re-enable all cone parameter tests 0d2911b Remove printouts 5dfbbc6 Remove printouts from Efficient_RANSAC.h c9b003d Return to independently defined Direct octree 6d93602 Update max depth when building a tree 9fb5182 Add reminder to replace fixed side length map size b9b269e Give indexed octree consistent api with direct 9db51b8 Mark location of issue b1c9f6f Print out first input iterator value at multiple points in the code d851dbe Force random seed for deterministic testing f3260b7 Refactor check for enough samples dc74af1 Add more printouts to sample drawing d3ba9f7 Remove printouts from refine() 5299bc1 Add logic changing max level based on cluster epsilon 25c1aaa Add initial side length to map when building octree 6cca8b2 Implement node_containing_point using older version's logic 963df46 Refactor logic confirming the node was found b1c6e31 Add printout whether the relevant node was found 7e59be6 Include IO.h for printing octree nodes 450f366 Reduce printouts to most relevant information bc2fbd6 Add printouts for loop information d86816b Add printouts for relevant functions 99e0341 Add printouts for detecting and preprocessing a18ba3a Add printouts when building and deleting Efficient_RANSAC 02872e9 Rename boundingBox to bbox 4d4b44c Don't return bounding box by reference 3d0f2f2 Make Direct_octree more similar to Indexed_octree d6ec4d5 Rename createTree to refine 3768abb Use indexed property map for Indexed octree 228dfc2 Update width to avoid access to private octree members 73d8a7e Add root accessor e8bfe55 Typedef Input_range as vector of ints 38abfb6 Switch from is-a to has-a relationship with CGAL::Octree a330f28 Replace Index() with dereference 46ac050 Add width accessor 18f76a5 Typedef Cell as Node 320968a Replace call to Index with dereferencing iterator a16a9cd Add index map to both octrees 2099d72 Octrees use vectors of sizes rather than Input_range as Point_range a3eb226 Use for each loop over point indices contained by a node 8113320 Replace code block with method for finding the leaf containing a point acda0b5 Use octree to find barycenter positions 4b8af27 Make Octree::barycenter public ac0c5ef Typedef Cell as Node f4f20c2 Add Indexed_octree constructor 5da9a28 Add createTree function 610bfe2 Add Direct_octree constructor ff4e6e5 Add offset accessor 3b8c94a Add boundingBox method 9a4fc61 Add size method 8a73388 Make both octrees extend the new octree 85fa39f Remove Octree declaration and typedef from Shape_base 3c8f16f Add new octree class declarations e25d905 Remove all RANSAC octree code e7611c6 Mark code using Cell in ways incompatible with Node 3d42b8b Make Cell center private, add barycenter accessor ccde26b Make Cell level private, add depth accessor 3bfef92 Rename isLeaf to is_leaf c129487 Move Cell class definition outside octrees a7752ce Remove beyond from Indexed_octree 555fdc9 Remove first from Indexed_octree 037185a Remove beyond from Direct_octree bfc0bd8 Remove first from Direct_octree cfe2440 Remove setData from Indexed_octree 56092d5 Remove setData from DirectOctree 8b5f303 Replace "Walker" with "Traversal" ad2cd41 Replace number_of_children with size 575d56c Replace Child_list with Children 771ac61 Remove namespace Node e304418 Incorporate IndexedPointAccessor into Indexed_octree f2e6f91 Incorporate DirectPointAccessor into Direct_octree 46ed241 Use node's operator!= for simpler syntax 51df442 Replace is_empty() with empty() ee7e197 Make Child_list more descriptive 38883a0 Move helper methods out of Walker namespace c22ed35 Shorten "is dependent" to "depends" d290ddc Remove capitalization from doxygen summaries 774c1ab Wrap std::max in parens to avoid problems with VC++ b89e131 Fix typo "heirarchy" --> "hierarchy" 7674b9f Remove redundant includes 98c4423 Make externalized octree functions take a const pointer 9850968 Make accessor index() methods const 00f3223 Split templated octree into pair of separately implemented versions cceb96d Begin implementing DirectOctree constructor d4ab810 Begin defining a DirectOctree class containing a CGAL::Octree b3e48eb Remove extern int scoreTime c40cfb3 Remove Efficient_RANSAC forward declaration eef1b0d Move maxLevel argument from constructor to createTree 5c363e1 Move bucketSize argument from constructor to createTree d8f797d Remove normal map from octree d24931b Make member variables private, with only const access 47f90ae Add const width accessor e99bf47 Use const accessor everywhere root is used 19e36a0 Add const root accessor dda6b95 Remove drawSamplesFromCellContainingPoint from octree d7dc5dc Add drawSamplesFromCellContainingPoint outside octree 7b212d5 Remove transl() 936f092 Eliminate use of transl() 2398c44 Replace translation function with a sum e0c54ae Remove constr_vec() a4f3b83 Remove constr_pt() f6dffe4 Eliminate use of constr_pt() 52a2b14 Remove get_coord 0798390 Remove get_x, get_y, get_z 17928f9 Eliminate use of get_coord 5754b94 Eliminate use of get_x, get_y, get_z c851722 Make split() private 388f210 Make buildBoundingCube private a73632b Remove ability to change bucket size after construction cd797bf Remove Shape typedef 9eeb731 Remove Efficient_RANSAC as friend class of octree 4d89849 Remove Efficient_RANSAC::fullScore() 3a79810 Remove Octree::fullScore(); it was never used! 521460d Remove Octree::score() 24f37af Eliminate usage of Octree::score() d502f73 score and fullScore now take octree arg by pointer 375f6c6 Define score method outside octree 691e1c7 Make Cell struct public c3fde50 Define fullScore method outside octree 1430413 Reinstate original RANSAC tree code 963f5b8 Reinstate const/non-const duplication 97c04b8 Merge branch 'master' of github.com:CGAL/cgal into gsoc2020-Octree-campolattaro deecf18 Add to doxygen comments on point accessors 3d5e0f3 Eliminate duplication between point accessors e7f386e Add to doxygen comments on index, leaf, root accessors e5dfb94 Add to doxygen comments on depth and location accessors 963c8bf Add to doxygen comment on parent accessor 7f11108 Eliminate duplication between [] operators 49d8fe6 Add to doxygen comments on [] operators d29b744 Add to doxygen comment on unsplit() c7592ba Add to doxygen comment on split() 8da19bb Add to doxygen comment on constructor 00bfcc7 Mark Node constructor explicit b8d0abc Add to doxygen comments on types 2d97cd7 Remove m_unit_per_depth d314d56 Add max_depth_reached accessor cd20011 Reset max depth before refining 7d1699a Define extension of package Octree 32ff55f Remove RANSAC octree entirely c833827 Add Internal_octree typedef ec79940 Remove all RANSAC octree implementation details 90a5d6a Merge branch 'gsoc2020-Octree-campolattaro' of https://github.com/JacksonCampolattaro/cgal into gsoc2020-Octree-campolattaro a72b77b Add automated testing of the node split method 0becb9c handle license check for Octree c0269e9 update project name c32ccd3 Merge branch 'master' of github.com:CGAL/cgal into gsoc2020-Octree-campolattaro 8923c56 Update template class name bd6e078 Fix walker function fbe4234 Update locate test 5c62edc Remove non-const access to root node 110744d Rename barycenter function ca08d16 Enable repeated refinement of an octree cbe61e6 Add safety check to node splitting function 6f5c423 Combine node splitting and point reassignment 2e27f09 Add to doxygen comments on equality and inequality operators 17666cd Replace neighbour (British spelling) with neighbor (American spelling) for consistency 3d84a2a Add to doxygen comments on nearest neighbours functions a2d6089 Assert point passed to locate is bounded by octree 99da036 Add to doxygen comments on locate and bbox methods 1c0c5d1 Add to doxygen comments on constructor and refine methods 18237d0 remove exe flag 2bbb374 dependencies e6dda4f update for travis 4b51b40 make package appear in overview 85977e5 license headers eb6d888 Simplify printouts 7be0da5 Add timing data to kd_tree/octree comparison test 718d5d0 Merge remote-tracking branch 'fork/gsoc2020-Octree-campolattaro' into gsoc2020-Octree-campolattaro f7ecb21 Add epsilon as optional argument 2c32873 Remove underscore marking new nearest neighbor implementation e68d7fc Add new benchmark cd674d7 Add nearest_k_neighbours_in_radius, implement nearest_k_neighbours in terms of this function f415df4 Remove old nearest neighbour solution 7efd47e Implement streamlined nearest neighbour as drop in replacement for old version 45c65d5 Outline recursive case 23877be Implement base case of streamlined algorithm bdf59a1 Begin outlining streamlined nearest neighbour implementation ac78eff Add first benchmark results e456d67 Add search benchmarking 97af9a0 Add number_of_points method to Node 21c6d6b Add is_empty method to Node 5259900 Rename value accessors to points 85b80a6 Rename m_value to m_points 2601de4 Rename Node_range to Point_range bfbab94 Add Node_range typedef 409f28e Rename node content type to Node_index 9036b65 Nodes now expect to contain iterator ranges 8ef4840 Parametrize K for comparisons 9fd3504 Simplify test printouts 000bdaa Remove sorting after using nearest_neighbour algorithm, confirmed to be redundant 069b2d4 Add inequality operators 8eb54e0 Add short introduction stub 579ee15 Define User Manual sections 2557dab Simplify names of split criterion b0c4041 Add Split_criterion namespace 5c6fff2 Add brief documentation to split criterion 73820f7 Add assertions for added safety of node functions 37e20c2 Pass k explicitly, simplifying the logic necessary to add a new point to the output list d981675 Test show an improvement in octree performance 1edbc99 Find mistake: only update search radius after K points are found f1b2160 Add more useful printout to the kd_tree comparison test ad6c943 Add node ranking for increased nearest neighbour performance, currently failing tests for k > 1 5c130ef Add test comparing octree results to kd_tree results for a K value of 16 f34c8b2 Add kd_tree construction 6858dd4 Add Kd_tree typedefs df887c5 Octree equality operator is now const a3b1632 Add param documentation to all public member functions 9f02caa Add brief documentation for bbox and nearest_k_neighbours 635bc89 Octree now outperforms naive for over 1000 points 23d6fb2 Octree now outperforms naive for the largest dataset 5031f09 Add tests to catch the error just fixed 6dfc459 Fix error setting location when building a node e727811 Find presumed cause of error through testing of bbox 2b69321 Fix indentation of octree pretty-print 5a897b4 Prepare for child of child tests b820846 Add first child node tests 6ed1803 Add root node tests da016d8 Outline test of bbox function cc8a24e Add bbox function for getting the bounding box of a node 4e342f1 Use pairs to map each point to its distance from the search point, reducing recalculation b1ec3f9 Nearest neighbour algorithm now skips nodes, but not yet enough to be faster than the naive algorithm 439af83 Add timing information to test printout 53bbfd7 Add Bbox construction from node 808fd02 Add do_intersect invocation eead9b6 Add Sphere typedef e542203 Outline intersection method between nodes and spheres 29b6d86 Deactivate kD_tree test 65c5f49 Remove timing tooling from kD_tree tests 8ee3350 Remove un-simplified algorithm, rename simple version 87be88b Make the simplified algorithm functional, but slower than the brute force solution de9ddf1 Flesh out the algorithm's outline 672ecd3 Flesh out the algorithm's outline a0f27e0 Fix iteration over node children a8820a4 Add largest_distance arg to simplified recursive algorithm 6023f1a Add Node argument to simple recursive algorithm 172187d Print number of points when running nearest neighbour tests 18b3ecf Implement nearest neighbours recursive caller method 9371514 Begin defining a simplified nearest neighbours algorithm c5dd606 Recursive nearest neighbours now sorts its node queue 1ce265c Add recursive invocation b607e9b Rename nearest neighbour test 74a3492 Begin outlining recursive nearest neighbour search 6ff6cfb Determine function signature for recursive neighbours method ba14e30 Add nearest_k_neighbours_recursive private method stub 6ab7583 Nearest_k_neighbours is now const 03370ef Add unimplemented kd_tree based test 2521cb3 Add placeholder nearest_k_neighbours with testing e44b255 Move pretty-printing responsibility to octree ostream operator d1ec728 Add doxygen comment stubs to walkers 163388a Add a short description of the locate method 361013a Add a larger test of locate() 741c6c2 Implement and test locate() 6ec3e85 Move std::endl out of node ostream operator f10a3c4 Improve Index printout cb9f388 Add more thorough testing of locate() 644bc51 Update node equality documentation acc44d2 Node equality now compares location eb18e29 Add placeholder doxygen comment for locate() d87e52f Add outline of locate() implementation 45fa4f9 Add simple locate test for a tree that only has a root node abfa7e9 Node comparison is now const for both nodes 53a63a9 Rename nearest neighbour test cb5920c Add empty locate test ff59b2f Add locate method stub f71a767 Add cmake language standard flag to test 8f0baec Remove redundant nodes method fc3697a Replace Preorder_tree_walker with Preorder c2caff5 Replace invocations of nodes method with new walk method 3787671 Remove second boost bind header 4484955 Remove boost bind header 513aaf0 Fix walker + some corrections 3d07872 Add timing checks to nearest neighbour test 4dca573 Add naive nearest neighbour solver and printouts 46f0ec5 Add outline for nearest neighbor test dc73062 Fix namespace indentation f7df4a1 Add demonstration of walker failure f48b384 Attempt several tree walker solutions 3a7851c Remove octree_test.cpp 5554a75 Add new octree equality test 4489afe Add test_4_points() 5b5e71f Improve test_2_points, node comparison no longer compares values d5cba79 Add test of refining an octree with two points 3672152 Resume using assertion statements for tests 531298d Improve tree walk test ec7b4a8 Begin outlining a new potential solution for working with walker methods d6da421 Add documentation to the node class 054bc89 Remove default iterator in Walker_iterator 1f46736 Update tree walker test to use Walker namespace 66164ee Template tree walkers on node value class instead of node class 98d35cf Add empty documentation to Points_iterator_range typedef d2f32d1 Remove old node class e242e89 Benchmark new node class 2f7a525 Deprecate old Node class 3172584 Switch octree to use new node class a41ad7b Add value check to equality operator a4b981d Add equality operator 4abe1c5 Add is_leaf and is_root 57d98fd Add value accessor methods e23e50f Add is_root() method 474f297 Add is_leaf() method 984f7d7 Add ostream operator for new Node class 53aecbb Add index and location types f2bf92a Add array index operators f10b275 Implement Node.split() 01504a5 Implement move semantics 2c28636 Implement Node.unsplit() a8cb911 Begin outlining a new Node class 5402eea Remove function is_sibling ce4bac4 Remove most non-const accessors 33c1c8b Remove use of accessors in node splitting abfba18 Add documentation to Node functionality 38389e0 Split function docs into more sections 5e1c66a Make some Octree_node typedefs private 27667e2 Make several typedefs private 0490d26 Add more typedefs for cleaner function signatures 483ced9 Add Node_range typedef 4fca064 Add short documentation to typedefs 560dd25 Begin adding Doxygen comments to Walker_iterator 7b663fc Remove const_iterator from Octree 04f2321 Switch to Walker_iterator in Octree range method 4b97dee Implement Walker_iterator 3f01217 Begin defining a Walker_iterator class which isn't a member of Octree ea1a90c Add doxygen description of octree class 65bdd7d Add tests of preorder traversal 638d283 Add empty doxygen comments to Octree_node.h 694eb5c Restore Vector typedef 2df93d6 Remove unused vector typedef 445839a Add more documentation files 1ae3afc Add placeholder documentation to octree code 8390eb9 Add placeholder text to manual 43c07f3 Add placeholder text to PackageDescription.txt 6945a56 Remove old version of octree and node 915b9e9 Begin setting up doxygen generation 42fd6db Replace points_begin() and points_end() with begin() and end() for range compatibility 970eb07 Use const ref to generate nodes iterator e7a8316 Use const ref to split criterion function 558c264 Use const ref to function pointer as member of node iterator 9cc5fd1 Use const ref to function pointer for node iterator 52cfccd Add empty files necessary to enable documentation build 74e7a32 Add Tree_walker namespace 10786c6 Add octree namespace 5d78a7d Use node range to implement ostream operator non-recursively 9a49c13 Mark node range builder const 14a97f9 Nodes range generator is now parametric for different traversals b15275a Refine node printing method 769e5cf Begin testing iterator-based tree traversal 8d6f329 Node comparison is now const f39ee93 Add boost iterator over nodes as member class of octree 52afe2e Implement leaves traversal 7e78099 Implement postorder traversal 8f9f653 Clarify naming of node point iterator accessors a3cc923 Begin creating framework for testing refinement 66c9142 Begin splitting tree traversal tests bd7cfab Tree walking is now done with const nodes, octree stream operator is based on it 6295277 Fully implement preorder traversal method f88dd80 Rename depth_first to preorder 43a9819 Split tree walker testing into its own file beac2ee Begin implementing depth first traversal 1784035 Add print method which takes a tree walker as an argument 8222f93 Add 'Siblings' tree walker method dcfeb0a Add method for an octree node to determine what its index is. 2e1adcb Begin implementing siblings tree walker 8a05be6 Switch to std::max when finding the longest side of the bounding box in the constructor 8c94985 Remove non-recursive split solution 023871a Add default arguments to recursive split 508208c Rearrange recursive split arguments 25976ec Benchmark recursive split d8e35dd Implement recursive split method f02f859 Begin defining a recursive split method 7ae4432 Add a couple of Tree walker algorithms with code outlines ed52249 Add empty tree-walker criterion file 20c1c4e Fix error in Split_to_bucket_size 7881758 Add bucket size split criterion 167df1f Remove naive partitioning algorithm c8e52ce Benchmark naive algorithm 7fd1aaa Add naive partitioning algorithm for comparison. 015fe9e Kernel is now deduced from other template parameters 6452311 Replace stop criterion with split criterion c263f74 Change stop criterion to accept node references 194b8fd Run benchmark 2c2db64 Stop criterion now provided in Stop_criterion.h b31869e Add refinement method which takes a stop criterion c1b12ad Remove recursive refinement method 72aa220 Add sequential refinement method 40ac8d9 Add criterion.h, where tree building oracle functors will be added 9a69b22 Make point iterators contained by nodes private efa616f Underscore now denotes older versions of files. 979ce0c Re-run benchmark 0ba7199 Add latest benchmark results f7d4037 Remove member variables used by old refinement method 921cefe Remove points() accessor 5000230 Remove underscores from new refinement functions. 05ab54c Remove old refinement methods c392cfc Add benchmark results 117ebde New refinement method produces identical trees to original 9cb7d85 New refinement method can now produce trees, but doesn't account for points near edges 3656eb8 Add new versions of important methods, preceded by underscores e41a8f4 Add rudimentary function for partitioning the points of a node among its children 23269b4 Run benchmark to measure effects of tweaks 07f77d4 Fix test of equality operator 54433ad Change root accessor to return a reference 1835856 Add recursive check to node equality operator 87c8b72 Remove child() accessor, prefer references over pointers bd64978 Add array index operator for accessing Node children e4eaf17 Begin implementing Node equality operator 2bcaf9d Implement miminal Octree equality operator e26398f Add empty equality test b646c7d Normal map removed from octree template a218a74 Remove more unused methods ae83a2b Remove children() accessor 6204c2a Switch from shared_ptr to unique_ptr for children array 10c08a0 Remove unused IntPoint_3 code a5e037b Replace IntPoint_3 with std::array<uint32_t, 3> 80ab980 Change how child nodes are stored and perform benchmark 9fd475b Add note to original benchmark result 0d1d4f5 Change barycentric point constructor syntax 71dcaa0 Document how bounding box is used in constructor 8ce6b6d Remove Grade() 032b0b4 Backup node implementation 1b93e41 Add commentary to Octree.h f533170 Fix typo in octree node comment 9fd7aba Add today's benchmark results fb9565c Create benchmark with reliable results 157e6e0 Add large .ply statue scan 3e07c36 Benchmark results file now has header 0715b3e Benchmarking program creates file with date 6bb3603 Add placeholder benchmarking function 0fb1bd3 Remove private functions no longer used bb0484f Remove debugging functions 4fb9fd7 Add backup of code before removing functionality 33fa963 Remove (unused) normal map f908466 Fix backwards insertion. 619aa44 Add placeholder stream operator for octree nodes e952ea8 Add empty IO header 0ede04b Move Octree_node to seperate header b37d116 Test program now constructs an octree instance b165420 Remove unnecessary OCTREE namespace 11723fa Add CMakeLists.txt for running tests b8170ad Add placeholder files in package_info, placeholder test a13b895 Rename Octree_3.h to Octree.h 44f5007 Add empty test program a3dd4f5 Add CMakeLists.txt for building tests 474b30f Add Pierre's octree header, including tweaks made for benchmarking 0ce7ec0 Add Octree directory containing empty description
The text was updated successfully, but these errors were encountered:
Jackson Campolattaro's GSoC 2020 Submission
Overview
New feature adding an Octree package to CGAL
This PR adds a new package Octree. This is a tree data structure which subdivides 3d space, similar to kD_tree. The package will replace the Octree used in Shape Detection's RANSAC algorithm. See the GSoC wiki page or the compiled docs for more information.
Associated Pull Request
Commit Log
b1d1e54 Implement nearest neighbor benchmark
a868a82 Implement construction benchmark
8f03c71 Implement the point generating method
7464db9 Add an unimplemented utility for generating test datasets
ea73c33 Perform tests non-linearly
f570b32 Create csv files in both benchmarks
eebf5e4 Add benchmark program files for construction and nearest_neighbor
7834778 Remove benchmarking code
e482108 Reduce subheading depth by removing Usage header
7cfbd1f Add a sentence discussing when to use Intersection and nearest neighbor
9e431be Merge branch 'master' of github.com:CGAL/cgal into gsoc2020-Octree-campolattaro
985ef73 Move relevant includes inside test
b4fc571 Remove unused includes
e69db45 Merge branch 'gsoc2020-Octree-campolattaro' of https://github.com/JacksonCampolattaro/cgal into gsoc2020-Octree-campolattaro
6d95250 Add section "History"
b1bdad0 remove trailing whitespace
ceefaa7 fix project name
9bd127f Add descriptions for preorder traversal and nearest-neighbor
5f0538c Add a short description for manual traversal
910daba Add a short description for building with a custom split criterion.
3f9ae5f Add a short description for building from a point set
fbd27e1 Add a short description for building from a point vector
61b36d8 Use bold text to indicate examples
488a295 Add headers for types of examples
ca21aec Rename concept Split_criterion to SplitCriterion
6b887f4 Rename concept Split_criterion to SplitCriterion
2b01228 Add a brief and a short description to the intersection function
014237d Add parameter descriptions to the intersection method
7f20336 Add ray intersection test
d29ec3d Implement sphere intersection test
7eda09d Test of intersection with point is now passing
59b6463 Add base case to recursive intersection function
34b007c Invoke recursive intersection function in public function
b968807 Add recursive node intersection signature
91bdbe1 Remove leaves method
e22430c Factor out the query primitive
142cf3b Add point intersection test assertions
268a9a9 Add intersecting_nodes invocations
58d7a83 Add scoped sections for each test
7daba0f Add intersection test to CMakeLists.txt
2a1485c Add empty intersection test
4d1baed Add intersecting_nodes method signature
88be3ad Update adjacent_node descriptions
18cfdfa Add a lookup table for the Direction enum
d0a967c Add an ascii diagram for the Dimension enum
1882411 Add a lookup table
9eb8413 Shrink ascii diagram
083da62 Add description to Child enum with ascii diagram
e45ada6 Add doxygen comments with briefs to both enums
cabc6ac Implement Split_criterion concept
9f91ef2 Add items to the Classified Reference Pages list
0a0871f Remove include guards
c0cfa64 Add Traversal concept
aeabc18 Add empty "Split_criterion" and "Traversal" concept headers
2b11c41 Add to the grade example description
6386984 Implement grade example
1c60964 Add short description to grade example
5f316de Add empty Octree_grade example
3df1c47 Eliminate m_bbox_side member variable
493df76 Set m_side_per_depth directly, instead of using m_bbox_side
0803bef Use side_per_depth instead of bbox_side when checking equality
a04482a Rename Direct_octree to RANSAC_octree
4c1473e Eliminate Indexed_octree
0cf29ea Initialize m_side_per_depth with length instead of 2
16a9cc5 Update max depth before splitting
a387da4 Eliminate m_max_depth_reached value
d21f428 Use max_depth_reached() to get depth in equality operator
1763564 Determine max depth by size of m_side_per_depth
d2c54c0 Correct mistake updating max depth
b8b1e2b Add tests concerning max depth
0b1c9a7 Add documentation to subscript operator
ff12caa Add examples of using the subscript operator directly on the octree
02fc711 Add subscript operator for accessing children of the root node
ca61bc2 Use Self typedef in equality operators
2d3d01a Use Self typedef in equality operators
63acc50 Add Self typedef
fe24292 Add first values to side length mep during constructor
32a55ec Update refine function to remove limits on depth
b31169f Update function invocations
9df95b7 Implement randomized grade() test
8ecfd7b Add description for grade()
5849067 Remove non-const node range and node traversal method typedefs
4c7a865 Eliminate Points_iterator_range
5182bff Add doxygen comment for operator!=
5e02c55 Add doxygen comment to Self typedef
100882c Add reminders to link other adjacency methods
88a99e0 Move adjacent_node to correct section
715b46d Add a doxygen description for adjacent_node
d1b2f9c Add ascii quadtree for explaining adjacency
c35a42a Incorporate unbalanced_neighbors_to_split into grade
3ca8683 Fix typos induced by blind word replacement
4a6eed5 Rename adjacent() to adjacent_node()
be38237 Add non-const adjacent method
225473e Collect list of leaves using Leaves traversal with const_cast
8fde332 Refactor unbalanced_neighbors_to_split
1c7a52a Remove old greater_or_equal_neighbor method
902d176 Swap simple and complex refine() invocations
85af7a9 Move point vector example before point set example
f123ecb Account for nodes adjacent to parent nodes
06b7047 Begin accounting for parent nodes
e4ba2be Begin adding tests for children of children
fa57a31 Add correctness tests
b24275c Swap BACK/FRONT notation
cb4f2ae Reverse negation by sign
60b79a4 Add Child enum
5d693e8 Add Direction enum
6eb55ec Add Self typedef to Node
f622683 Add more root node tests
a8daae7 Implement adjacent for direct siblings
adf6b74 Add first test of adjacent
b4f13d8 Implement bit operations that find the offset
474ca79 Begin implementing adjacent method
c5591da Add empty test of node adjacency
8f91c93 Implement unbalanced_neighbors_to_split
0faf150 Begin implementing unbalanced_neighbors_to_split
ad58923 Add greater_or_equal_neighbor stub
df5fc72 Begin rewriting grade with more documentation
9cbe9d9 Add typedefs necessary for non-const traversal
79d680b Don't use output iterator to add nodes to queue
e5d38cf Add recursive method for adding leaves to a queue
c932607 Rename tree walk test to traverse
63c4d62 Use traversal to fill the leaf queue
b70181c Implement visual grade() test
110885e Add grade test to CMakeLists.txt
95ac96c Add empty grade test
43302c8 Rename PointMap to Point_map
a56ef32 Rename PointRange to Point_range
f020e4f Set default template for point map
033d0d7 Rename Point_set to Point_vector
0e7a364 Update doxygen tag
d1f5c8c Comment out custom traversal example
852740a Add description for vector octree example
9b23a59 Add description for manual and preorder traversal examples
ad0fa67 Add description for nearest neighbor example
9f727d1 Rename walk to traverse
8091145 Add preorder traversal example
306bf5f Use a more verbose method to choose octree split criterion
897860d Add manual traversal example
f6d41e7 Remove point map declaration before constructors
ef948f1 Remove point map declaration before constructors
3627f4e Build octree without passing point map
4959864 Automatically construct point map if not passed
c157e07 Pass point map directly (not by ref)
3563645 Add octree with vector demonstration
ad96992 Finish nearest neighbor demonstration
4724a61 Begin implementing nearest neighbor example
f0ef3d7 Add description to custom split criterion example
100fe8c Add split by ratio example
ec3fca2 Add description to Vector tree example with placeholder file
e1c964b Add description to Point_set tree example
de09a1e Build the octree
1f9196b Load points from file
ff6a043 Add data for testing
6bf3b23 Link example files
3281230 Set example path
2eb052b Add examples to examples.txt
6a4fd50 Add examples as single source programs
dfba799 Rename examples for consistency
03328b2 Add more empty examples
81428c3 Add empty construction examples
d6e67af Add examples directory with Cmake file
144f5a8 Remove redundant "Example" from example titles
ec0f9c7 Add titles for several examples
d07fa87 Update refine method of Direct octree to match indexed
6781a48 Add brackets to do-while loop for clarity
50dc514 Add brackets to keep_searching check for clarity
252fd07 Force bbox value to make sure it's not causing issues
2a85336 Disable randomness in scene test
5ce9381 Remove fixed seed for random generator
e4f2a40 Re-enable all cone parameter tests
0d2911b Remove printouts
5dfbbc6 Remove printouts from Efficient_RANSAC.h
c9b003d Return to independently defined Direct octree
6d93602 Update max depth when building a tree
9fb5182 Add reminder to replace fixed side length map size
b9b269e Give indexed octree consistent api with direct
9db51b8 Mark location of issue
b1c9f6f Print out first input iterator value at multiple points in the code
d851dbe Force random seed for deterministic testing
f3260b7 Refactor check for enough samples
dc74af1 Add more printouts to sample drawing
d3ba9f7 Remove printouts from refine()
5299bc1 Add logic changing max level based on cluster epsilon
25c1aaa Add initial side length to map when building octree
6cca8b2 Implement node_containing_point using older version's logic
963df46 Refactor logic confirming the node was found
b1c6e31 Add printout whether the relevant node was found
7e59be6 Include IO.h for printing octree nodes
450f366 Reduce printouts to most relevant information
bc2fbd6 Add printouts for loop information
d86816b Add printouts for relevant functions
99e0341 Add printouts for detecting and preprocessing
a18ba3a Add printouts when building and deleting Efficient_RANSAC
02872e9 Rename boundingBox to bbox
4d4b44c Don't return bounding box by reference
3d0f2f2 Make Direct_octree more similar to Indexed_octree
d6ec4d5 Rename createTree to refine
3768abb Use indexed property map for Indexed octree
228dfc2 Update width to avoid access to private octree members
73d8a7e Add root accessor
e8bfe55 Typedef Input_range as vector of ints
38abfb6 Switch from is-a to has-a relationship with CGAL::Octree
a330f28 Replace Index() with dereference
46ac050 Add width accessor
18f76a5 Typedef Cell as Node
320968a Replace call to Index with dereferencing iterator
a16a9cd Add index map to both octrees
2099d72 Octrees use vectors of sizes rather than Input_range as Point_range
a3eb226 Use for each loop over point indices contained by a node
8113320 Replace code block with method for finding the leaf containing a point
acda0b5 Use octree to find barycenter positions
4b8af27 Make Octree::barycenter public
ac0c5ef Typedef Cell as Node
f4f20c2 Add Indexed_octree constructor
5da9a28 Add createTree function
610bfe2 Add Direct_octree constructor
ff4e6e5 Add offset accessor
3b8c94a Add boundingBox method
9a4fc61 Add size method
8a73388 Make both octrees extend the new octree
85fa39f Remove Octree declaration and typedef from Shape_base
3c8f16f Add new octree class declarations
e25d905 Remove all RANSAC octree code
e7611c6 Mark code using Cell in ways incompatible with Node
3d42b8b Make Cell center private, add barycenter accessor
ccde26b Make Cell level private, add depth accessor
3bfef92 Rename isLeaf to is_leaf
c129487 Move Cell class definition outside octrees
a7752ce Remove beyond from Indexed_octree
555fdc9 Remove first from Indexed_octree
037185a Remove beyond from Direct_octree
bfc0bd8 Remove first from Direct_octree
cfe2440 Remove setData from Indexed_octree
56092d5 Remove setData from DirectOctree
8b5f303 Replace "Walker" with "Traversal"
ad2cd41 Replace number_of_children with size
575d56c Replace Child_list with Children
771ac61 Remove namespace Node
e304418 Incorporate IndexedPointAccessor into Indexed_octree
f2e6f91 Incorporate DirectPointAccessor into Direct_octree
46ed241 Use node's operator!= for simpler syntax
51df442 Replace is_empty() with empty()
ee7e197 Make Child_list more descriptive
38883a0 Move helper methods out of Walker namespace
c22ed35 Shorten "is dependent" to "depends"
d290ddc Remove capitalization from doxygen summaries
774c1ab Wrap std::max in parens to avoid problems with VC++
b89e131 Fix typo "heirarchy" --> "hierarchy"
7674b9f Remove redundant includes
98c4423 Make externalized octree functions take a const pointer
9850968 Make accessor index() methods const
00f3223 Split templated octree into pair of separately implemented versions
cceb96d Begin implementing DirectOctree constructor
d4ab810 Begin defining a DirectOctree class containing a CGAL::Octree
b3e48eb Remove extern int scoreTime
c40cfb3 Remove Efficient_RANSAC forward declaration
eef1b0d Move maxLevel argument from constructor to createTree
5c363e1 Move bucketSize argument from constructor to createTree
d8f797d Remove normal map from octree
d24931b Make member variables private, with only const access
47f90ae Add const width accessor
e99bf47 Use const accessor everywhere root is used
19e36a0 Add const root accessor
dda6b95 Remove drawSamplesFromCellContainingPoint from octree
d7dc5dc Add drawSamplesFromCellContainingPoint outside octree
7b212d5 Remove transl()
936f092 Eliminate use of transl()
2398c44 Replace translation function with a sum
e0c54ae Remove constr_vec()
a4f3b83 Remove constr_pt()
f6dffe4 Eliminate use of constr_pt()
52a2b14 Remove get_coord
0798390 Remove get_x, get_y, get_z
17928f9 Eliminate use of get_coord
5754b94 Eliminate use of get_x, get_y, get_z
c851722 Make split() private
388f210 Make buildBoundingCube private
a73632b Remove ability to change bucket size after construction
cd797bf Remove Shape typedef
9eeb731 Remove Efficient_RANSAC as friend class of octree
4d89849 Remove Efficient_RANSAC::fullScore()
3a79810 Remove Octree::fullScore(); it was never used!
521460d Remove Octree::score()
24f37af Eliminate usage of Octree::score()
d502f73 score and fullScore now take octree arg by pointer
375f6c6 Define score method outside octree
691e1c7 Make Cell struct public
c3fde50 Define fullScore method outside octree
1430413 Reinstate original RANSAC tree code
963f5b8 Reinstate const/non-const duplication
97c04b8 Merge branch 'master' of github.com:CGAL/cgal into gsoc2020-Octree-campolattaro
deecf18 Add to doxygen comments on point accessors
3d5e0f3 Eliminate duplication between point accessors
e7f386e Add to doxygen comments on index, leaf, root accessors
e5dfb94 Add to doxygen comments on depth and location accessors
963c8bf Add to doxygen comment on parent accessor
7f11108 Eliminate duplication between [] operators
49d8fe6 Add to doxygen comments on [] operators
d29b744 Add to doxygen comment on unsplit()
c7592ba Add to doxygen comment on split()
8da19bb Add to doxygen comment on constructor
00bfcc7 Mark Node constructor explicit
b8d0abc Add to doxygen comments on types
2d97cd7 Remove m_unit_per_depth
d314d56 Add max_depth_reached accessor
cd20011 Reset max depth before refining
7d1699a Define extension of package Octree
32ff55f Remove RANSAC octree entirely
c833827 Add Internal_octree typedef
ec79940 Remove all RANSAC octree implementation details
90a5d6a Merge branch 'gsoc2020-Octree-campolattaro' of https://github.com/JacksonCampolattaro/cgal into gsoc2020-Octree-campolattaro
a72b77b Add automated testing of the node split method
0becb9c handle license check for Octree
c0269e9 update project name
c32ccd3 Merge branch 'master' of github.com:CGAL/cgal into gsoc2020-Octree-campolattaro
8923c56 Update template class name
bd6e078 Fix walker function
fbe4234 Update locate test
5c62edc Remove non-const access to root node
110744d Rename barycenter function
ca08d16 Enable repeated refinement of an octree
cbe61e6 Add safety check to node splitting function
6f5c423 Combine node splitting and point reassignment
2e27f09 Add to doxygen comments on equality and inequality operators
17666cd Replace neighbour (British spelling) with neighbor (American spelling) for consistency
3d84a2a Add to doxygen comments on nearest neighbours functions
a2d6089 Assert point passed to locate is bounded by octree
99da036 Add to doxygen comments on locate and bbox methods
1c0c5d1 Add to doxygen comments on constructor and refine methods
18237d0 remove exe flag
2bbb374 dependencies
e6dda4f update for travis
4b51b40 make package appear in overview
85977e5 license headers
eb6d888 Simplify printouts
7be0da5 Add timing data to kd_tree/octree comparison test
718d5d0 Merge remote-tracking branch 'fork/gsoc2020-Octree-campolattaro' into gsoc2020-Octree-campolattaro
f7ecb21 Add epsilon as optional argument
2c32873 Remove underscore marking new nearest neighbor implementation
e68d7fc Add new benchmark
cd674d7 Add nearest_k_neighbours_in_radius, implement nearest_k_neighbours in terms of this function
f415df4 Remove old nearest neighbour solution
7efd47e Implement streamlined nearest neighbour as drop in replacement for old version
45c65d5 Outline recursive case
23877be Implement base case of streamlined algorithm
bdf59a1 Begin outlining streamlined nearest neighbour implementation
ac78eff Add first benchmark results
e456d67 Add search benchmarking
97af9a0 Add number_of_points method to Node
21c6d6b Add is_empty method to Node
5259900 Rename value accessors to points
85b80a6 Rename m_value to m_points
2601de4 Rename Node_range to Point_range
bfbab94 Add Node_range typedef
409f28e Rename node content type to Node_index
9036b65 Nodes now expect to contain iterator ranges
8ef4840 Parametrize K for comparisons
9fd3504 Simplify test printouts
000bdaa Remove sorting after using nearest_neighbour algorithm, confirmed to be redundant
069b2d4 Add inequality operators
8eb54e0 Add short introduction stub
579ee15 Define User Manual sections
2557dab Simplify names of split criterion
b0c4041 Add Split_criterion namespace
5c6fff2 Add brief documentation to split criterion
73820f7 Add assertions for added safety of node functions
37e20c2 Pass k explicitly, simplifying the logic necessary to add a new point to the output list
d981675 Test show an improvement in octree performance
1edbc99 Find mistake: only update search radius after K points are found
f1b2160 Add more useful printout to the kd_tree comparison test
ad6c943 Add node ranking for increased nearest neighbour performance, currently failing tests for k > 1
5c130ef Add test comparing octree results to kd_tree results for a K value of 16
f34c8b2 Add kd_tree construction
6858dd4 Add Kd_tree typedefs
df887c5 Octree equality operator is now const
a3b1632 Add param documentation to all public member functions
9f02caa Add brief documentation for bbox and nearest_k_neighbours
635bc89 Octree now outperforms naive for over 1000 points
23d6fb2 Octree now outperforms naive for the largest dataset
5031f09 Add tests to catch the error just fixed
6dfc459 Fix error setting location when building a node
e727811 Find presumed cause of error through testing of bbox
2b69321 Fix indentation of octree pretty-print
5a897b4 Prepare for child of child tests
b820846 Add first child node tests
6ed1803 Add root node tests
da016d8 Outline test of bbox function
cc8a24e Add bbox function for getting the bounding box of a node
4e342f1 Use pairs to map each point to its distance from the search point, reducing recalculation
b1ec3f9 Nearest neighbour algorithm now skips nodes, but not yet enough to be faster than the naive algorithm
439af83 Add timing information to test printout
53bbfd7 Add Bbox construction from node
808fd02 Add do_intersect invocation
eead9b6 Add Sphere typedef
e542203 Outline intersection method between nodes and spheres
29b6d86 Deactivate kD_tree test
65c5f49 Remove timing tooling from kD_tree tests
8ee3350 Remove un-simplified algorithm, rename simple version
87be88b Make the simplified algorithm functional, but slower than the brute force solution
de9ddf1 Flesh out the algorithm's outline
672ecd3 Flesh out the algorithm's outline
a0f27e0 Fix iteration over node children
a8820a4 Add largest_distance arg to simplified recursive algorithm
6023f1a Add Node argument to simple recursive algorithm
172187d Print number of points when running nearest neighbour tests
18b3ecf Implement nearest neighbours recursive caller method
9371514 Begin defining a simplified nearest neighbours algorithm
c5dd606 Recursive nearest neighbours now sorts its node queue
1ce265c Add recursive invocation
b607e9b Rename nearest neighbour test
74a3492 Begin outlining recursive nearest neighbour search
6ff6cfb Determine function signature for recursive neighbours method
ba14e30 Add nearest_k_neighbours_recursive private method stub
6ab7583 Nearest_k_neighbours is now const
03370ef Add unimplemented kd_tree based test
2521cb3 Add placeholder nearest_k_neighbours with testing
e44b255 Move pretty-printing responsibility to octree ostream operator
d1ec728 Add doxygen comment stubs to walkers
163388a Add a short description of the locate method
361013a Add a larger test of locate()
741c6c2 Implement and test locate()
6ec3e85 Move std::endl out of node ostream operator
f10a3c4 Improve Index printout
cb9f388 Add more thorough testing of locate()
644bc51 Update node equality documentation
acc44d2 Node equality now compares location
eb18e29 Add placeholder doxygen comment for locate()
d87e52f Add outline of locate() implementation
45fa4f9 Add simple locate test for a tree that only has a root node
abfa7e9 Node comparison is now const for both nodes
53a63a9 Rename nearest neighbour test
cb5920c Add empty locate test
ff59b2f Add locate method stub
f71a767 Add cmake language standard flag to test
8f0baec Remove redundant
nodesmethodfc3697a Replace
Preorder_tree_walkerwithPreorderc2caff5 Replace invocations of
nodesmethod with newwalkmethod3787671 Remove second boost bind header
4484955 Remove boost bind header
513aaf0 Fix walker + some corrections
3d07872 Add timing checks to nearest neighbour test
4dca573 Add naive nearest neighbour solver and printouts
46f0ec5 Add outline for nearest neighbor test
dc73062 Fix namespace indentation
f7df4a1 Add demonstration of walker failure
f48b384 Attempt several tree walker solutions
3a7851c Remove octree_test.cpp
5554a75 Add new octree equality test
4489afe Add test_4_points()
5b5e71f Improve test_2_points, node comparison no longer compares values
d5cba79 Add test of refining an octree with two points
3672152 Resume using assertion statements for tests
531298d Improve tree walk test
ec7b4a8 Begin outlining a new potential solution for working with walker methods
d6da421 Add documentation to the node class
054bc89 Remove default iterator in Walker_iterator
1f46736 Update tree walker test to use Walker namespace
66164ee Template tree walkers on node value class instead of node class
98d35cf Add empty documentation to Points_iterator_range typedef
d2f32d1 Remove old node class
e242e89 Benchmark new node class
2f7a525 Deprecate old Node class
3172584 Switch octree to use new node class
a41ad7b Add value check to equality operator
a4b981d Add equality operator
4abe1c5 Add is_leaf and is_root
57d98fd Add value accessor methods
e23e50f Add is_root() method
474f297 Add is_leaf() method
984f7d7 Add ostream operator for new Node class
53aecbb Add index and location types
f2bf92a Add array index operators
f10b275 Implement Node.split()
01504a5 Implement move semantics
2c28636 Implement Node.unsplit()
a8cb911 Begin outlining a new Node class
5402eea Remove function is_sibling
ce4bac4 Remove most non-const accessors
33c1c8b Remove use of accessors in node splitting
abfba18 Add documentation to Node functionality
38389e0 Split function docs into more sections
5e1c66a Make some Octree_node typedefs private
27667e2 Make several typedefs private
0490d26 Add more typedefs for cleaner function signatures
483ced9 Add Node_range typedef
4fca064 Add short documentation to typedefs
560dd25 Begin adding Doxygen comments to Walker_iterator
7b663fc Remove const_iterator from Octree
04f2321 Switch to Walker_iterator in Octree range method
4b97dee Implement Walker_iterator
3f01217 Begin defining a Walker_iterator class which isn't a member of Octree
ea1a90c Add doxygen description of octree class
65bdd7d Add tests of preorder traversal
638d283 Add empty doxygen comments to Octree_node.h
694eb5c Restore Vector typedef
2df93d6 Remove unused vector typedef
445839a Add more documentation files
1ae3afc Add placeholder documentation to octree code
8390eb9 Add placeholder text to manual
43c07f3 Add placeholder text to PackageDescription.txt
6945a56 Remove old version of octree and node
915b9e9 Begin setting up doxygen generation
42fd6db Replace points_begin() and points_end() with begin() and end() for range compatibility
970eb07 Use const ref to generate nodes iterator
e7a8316 Use const ref to split criterion function
558c264 Use const ref to function pointer as member of node iterator
9cc5fd1 Use const ref to function pointer for node iterator
52cfccd Add empty files necessary to enable documentation build
74e7a32 Add Tree_walker namespace
10786c6 Add octree namespace
5d78a7d Use node range to implement ostream operator non-recursively
9a49c13 Mark node range builder const
14a97f9 Nodes range generator is now parametric for different traversals
b15275a Refine node printing method
769e5cf Begin testing iterator-based tree traversal
8d6f329 Node comparison is now const
f39ee93 Add boost iterator over nodes as member class of octree
52afe2e Implement leaves traversal
7e78099 Implement postorder traversal
8f9f653 Clarify naming of node point iterator accessors
a3cc923 Begin creating framework for testing refinement
66c9142 Begin splitting tree traversal tests
bd7cfab Tree walking is now done with const nodes, octree stream operator is based on it
6295277 Fully implement preorder traversal method
f88dd80 Rename depth_first to preorder
43a9819 Split tree walker testing into its own file
beac2ee Begin implementing depth first traversal
1784035 Add print method which takes a tree walker as an argument
8222f93 Add 'Siblings' tree walker method
dcfeb0a Add method for an octree node to determine what its index is.
2e1adcb Begin implementing siblings tree walker
8a05be6 Switch to std::max when finding the longest side of the bounding box in the constructor
8c94985 Remove non-recursive split solution
023871a Add default arguments to recursive split
508208c Rearrange recursive split arguments
25976ec Benchmark recursive split
d8e35dd Implement recursive split method
f02f859 Begin defining a recursive split method
7ae4432 Add a couple of Tree walker algorithms with code outlines
ed52249 Add empty tree-walker criterion file
20c1c4e Fix error in Split_to_bucket_size
7881758 Add bucket size split criterion
167df1f Remove naive partitioning algorithm
c8e52ce Benchmark naive algorithm
7fd1aaa Add naive partitioning algorithm for comparison.
015fe9e Kernel is now deduced from other template parameters
6452311 Replace stop criterion with split criterion
c263f74 Change stop criterion to accept node references
194b8fd Run benchmark
2c2db64 Stop criterion now provided in Stop_criterion.h
b31869e Add refinement method which takes a stop criterion
c1b12ad Remove recursive refinement method
72aa220 Add sequential refinement method
40ac8d9 Add criterion.h, where tree building oracle functors will be added
9a69b22 Make point iterators contained by nodes private
efa616f Underscore now denotes older versions of files.
979ce0c Re-run benchmark
0ba7199 Add latest benchmark results
f7d4037 Remove member variables used by old refinement method
921cefe Remove points() accessor
5000230 Remove underscores from new refinement functions.
05ab54c Remove old refinement methods
c392cfc Add benchmark results
117ebde New refinement method produces identical trees to original
9cb7d85 New refinement method can now produce trees, but doesn't account for points near edges
3656eb8 Add new versions of important methods, preceded by underscores
e41a8f4 Add rudimentary function for partitioning the points of a node among its children
23269b4 Run benchmark to measure effects of tweaks
07f77d4 Fix test of equality operator
54433ad Change root accessor to return a reference
1835856 Add recursive check to node equality operator
87c8b72 Remove child() accessor, prefer references over pointers
bd64978 Add array index operator for accessing Node children
e4eaf17 Begin implementing Node equality operator
2bcaf9d Implement miminal Octree equality operator
e26398f Add empty equality test
b646c7d Normal map removed from octree template
a218a74 Remove more unused methods
ae83a2b Remove children() accessor
6204c2a Switch from shared_ptr to unique_ptr for children array
10c08a0 Remove unused IntPoint_3 code
a5e037b Replace IntPoint_3 with std::array<uint32_t, 3>
80ab980 Change how child nodes are stored and perform benchmark
9fd475b Add note to original benchmark result
0d1d4f5 Change barycentric point constructor syntax
71dcaa0 Document how bounding box is used in constructor
8ce6b6d Remove Grade()
032b0b4 Backup node implementation
1b93e41 Add commentary to Octree.h
f533170 Fix typo in octree node comment
9fd7aba Add today's benchmark results
fb9565c Create benchmark with reliable results
157e6e0 Add large .ply statue scan
3e07c36 Benchmark results file now has header
0715b3e Benchmarking program creates file with date
6bb3603 Add placeholder benchmarking function
0fb1bd3 Remove private functions no longer used
bb0484f Remove debugging functions
4fb9fd7 Add backup of code before removing functionality
33fa963 Remove (unused) normal map
f908466 Fix backwards insertion.
619aa44 Add placeholder stream operator for octree nodes
e952ea8 Add empty IO header
0ede04b Move Octree_node to seperate header
b37d116 Test program now constructs an octree instance
b165420 Remove unnecessary OCTREE namespace
11723fa Add CMakeLists.txt for running tests
b8170ad Add placeholder files in package_info, placeholder test
a13b895 Rename Octree_3.h to Octree.h
44f5007 Add empty test program
a3dd4f5 Add CMakeLists.txt for building tests
474b30f Add Pierre's octree header, including tweaks made for benchmarking
0ce7ec0 Add Octree directory containing empty description
The text was updated successfully, but these errors were encountered: