KD-Tree

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

23:14
Thu
09
Jul 2009

KD-Tree

People at forums are usually advised to learn BSP, quadtree or octree as space partitioning data structure, but there are many more interesting structures than these three. This time my choice for home project is KD-tree. It's actually something between BSP and octree. Just like BSP it's a binary tree (each non-leaf node has two child nodes) and optimal splitting plane is estimated each time by special algorithm, but splitting planes are always aligned to one of three main axes and thus each node can be described by an AABB (axis-aligned bounding box), just like in octree.

As my tree is designed to manage objects and not geometry, nothing can be split and some of objects may intersect splitting planes. How to deal with them? I simply assign them to the parent node, so not only leaves are allowed to contain list of objects. To avoid too many small objects intersecting splitting planes to degrade performance by falling into top level nodes (it's called "sticky planes" or something like that :) I adopted "loose octree" idea to my KD-tree. It simply means I extend each node’s bounding box so that each node's children slightly overlap each other and small objects intersecting splitting plane fall into one of the children.

My KD-tree is also dynamic, which means it reorganizes itself as objects get added, removed and moved in the tree. It's actually quite simple. Each time an object is added to a node, that node can be split into two children if it's object number exceeds constant limit. Similarly node can be merged by deleting it's children each time an object is removed from one of its children, if the number of objects in that node and its children drops under constant minimum.

For additional performance, I allocate tree nodes from my own "Free List" memory pool and I keep objects connected to each node as doubly-linked list.

I also came up with an idea how to easily visualize quality of my space partitioning technique. I keep track of the number of tree nodes and objects on each depth level. This way I can tell from these several numbers whether tree is more "tall" or "wide" and whether most of objects stay in leaves instead of some top-level nodes.

Here are some screenshots and a video from my recent code:

KD-tree KD-tree KD-tree

Comments (2) | Tags: rendering video gallery algorithms math | Author: Adam Sawicki | Share

Comments

ayman
2015-12-07 09:57:53
<a href="http://accountingeg.blogspot.com/2015/02/blog-post_15.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="http://babelsoftco.com/Info_Program.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1575;&#1583;&#1575;&#1585;&#1577; &#1575;&#1604;&#1593;&#1602;&#1575;&#1585;&#1575;&#1578;</a>
<a href="http://www.babelsoftco.com">&#1576;&#1585;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1610;&#1607;</a>
<a href="http://babelsoftco.com/mkawlat2015.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="https://www.youtube.com/watch?v=ZOM03KIKv4w">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="http://www.babelsoftco.com/Mokwlat_Main.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="www.babelsoftco.com/Mokwlat/MySite/Acc_Mokwlat.html">&#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1588;&#1585;&#1603;&#1575;&#1578; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="https://www.youtube.com/playlist?list=PL02004C5091D4C0F4">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="https://www.facebook.com/babelmokwalt">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="https://www.facebook.com/mkawlat">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="http://www.babelsoftco.com/Mokwlat_Main.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="http://www.babelsoftco.com/Mokwlat_Main.html">&#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1602;&#1575;&#1608;&#1604;&#1575;&#1578;</a>
<a href="http://www.babelsoftco.com/Invest_Main.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1575;&#1604;&#1575;&#1587;&#1578;&#1579;&#1605;&#1575;&#1585; &#1575;&#1604;&#1593;&#1602;&#1575;&#1585;&#1609;</a>
<a href="http://www.babelsoftco.com/Mahlat_Main.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1604;&#1604;&#1605;&#1581;&#1604;&#1575;&#1578;</a>
<a href="http://babelsoftco.com/Info_Program.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1581;&#1604;&#1575;&#1578;</a>
<a href="http://www.babelsoftco.com/Hosp_Main.html">&#1606;&#1592;&#1575;&#1605; &#1575;&#1583;&#1575;&#1585;&#1577; &#1575;&#1604;&#1605;&#1587;&#1578;&#1588;&#1601;&#1610;&#1575;&#1578;</a>
<a href="http://babelsoftco.com/Ma3mal_Main.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1604;&#1575;&#1583;&#1575;&#1585;&#1577; &#1575;&#1604;&#1575;&#1587;&#1578;&#1608;&#1583;&#1610;&#1608;</a>
<a href="http://www.babelsoftco.com/m3ared.html">&#1576;&#1585;&#1606;&#1575;&#1605;&#1580; &#1605;&#1581;&#1575;&#1587;&#1576;&#1577; &#1605;&#1593;&#1575;&#1585;&#1590; &#1587;&#1610;&#1575;&#1585;&#1575;&#1578;</a>
yll
2016-03-25 03:32:51
https://www.google.co.jp/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=Comments+site:http://asawicki.info/&start=20
http://asawicki.info/news_1340_a_reminder_about_my_links.html?x=viewnews&id=1340
http://asawicki.info/news_1435_visual_studio_2010_service_pack_1_released_yesterday.html?x=viewnews&id=1435
http://asawicki.info/news_1585_my_lecture_on_careercon.html?x=viewnews&id=1585
http://asawicki.info/news_1606_unicode_w_visual_c_-_my_old_article.html?x=viewnews&id=1606
http://asawicki.info/news_1526_sbx_-_scale-bias_transform.html?x=viewnews&id=1526
http://asawicki.info/news_1611_type_safe_ptr_-_idea_for_type-safe_void_pointer.html?x=viewnews&id=1611
http://asawicki.info/news_1487_noconsole_-_my_c_project.html?x=viewnews&id=1487
http://asawicki.info/news_1370_origami_sonobe_module.html?x=viewnews&id=1370
http://asawicki.info/news_1336_generating_and_compressing_avi_video_files.html?x=viewnews&id=1336
http://asawicki.info/news_1322_fractals_ifs_and_a_fern.html?x=viewnews&id=1322
http://asawicki.info/news_1465_handling_ctrlc_in_windows_console_application.html?x=viewnews&id=1465
http://asawicki.info/news_1612_printstream_20_-_polymorphic_printf.html?x=viewnews&id=1612
http://asawicki.info/news_1579_writing_ofx_video_processing_plugin.html?x=viewnews&id=1579
http://asawicki.info/news_1584_psychill_evening_-_my_first_music_visualizations.html?x=viewnews&id=1584
http://asawicki.info/news_1538_type_visualization_in_visual_studio_2012_debugger.html?x=viewnews&id=1538
http://asawicki.info/news_1609_poznan_game_arena_game_industry_conference_2015.html?x=viewnews&id=1609

Post comment

Nick *
Your name or nickname
E-mail
Your contact information (optional, will not be shown)
Text *
Content of your comment
Calculate *
(* - required field)
STAT NO AD [Stat] [Admin] [STAT NO AD] [pub] [Mirror] Copyright © 2004-2017 Adam Sawicki
Copyright © 2004-2017 Adam Sawicki