Timo Kokkonen [Fri, 8 Jul 2011 08:49:32 +0000 (11:49 +0300)]
quadtree: Document subtree indexing
As stupid as it might sound, I forgot how the subtrees are indexed in
spatially. Therefore it might make sense to simply document even the
trivial things in the header file to avoid future confusion.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
If we move planet in the quadtree, we must call quadtree_move() in
order to keep the tree sorted. As the tree ordering might change, the
merge planet must also return the possibly new parent node of the
tree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 6 Dec 2010 09:09:36 +0000 (11:09 +0200)]
Makefile: Reduce wildcard usage
Having wildcards in the Makefile is error prone in situations where
there are unrelated files in the source tree that are not related to
the actual project. For example, if some source files have been
renamed and there are leftover .*.o.d files that still contain the old
source files. Then make will incorrectly determine that some old files
would still be needed even though they are not part of the project any
more.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 30 Oct 2010 16:57:19 +0000 (19:57 +0300)]
Move position vector from planet to quadtree
Moving the position information inside the quadtree structure will
make it eventually much easier to do varios tree operations within the
quadtree code. Most of the quadtree callback functions can be moved
inside the quadtree code. This patch implements just the first part of
the change, moving the coordinates inside quadtree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sun, 13 Jun 2010 13:04:57 +0000 (16:04 +0300)]
main.c: Skip simulation when time step is zero
When user has set the simulation speed to zero, there is no need to
run the simulation at all, as it won't be changing anyway. This makes
it possible to run excessively large simulations and occassionally
freeze the simulation. Then, for example, inspecting the tree topology
(if draw_lines variable is enabled) becomes easier without need to
worry about slow camera movement.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 24 Apr 2010 11:00:49 +0000 (14:00 +0300)]
quadtree: Try to keep the tree in better balance.
When a tree node is removed, we now attempt to add the detached
subtree in more optimized order to the new tree. This is done so that
we walk down the detached tree and add a new node to the main tree
always when the tree is one quarter'th smaller than the previous node
that was added.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 24 Apr 2010 10:59:14 +0000 (13:59 +0300)]
quadtree_add: Zero child pointers when a new node is added
Since we don't support adding an entire subtree, it is better to zero
out the child pointers to ensure there are no leftover child nodes
that might corrupt the tree integrity.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sun, 11 Apr 2010 15:05:13 +0000 (18:05 +0300)]
Introduce struct quadree_ops
Store all related function pointers (so far only the comparison) in
one structure. This will make it easier to add function pointers that
are needed in various quadtree operations.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sun, 11 Apr 2010 09:13:55 +0000 (12:13 +0300)]
planet.c: Optimize moving of planets within thetree
If there is no changes in the tree topology when a planet is moved,
there is no need to do any tree operations. This will decrease tree
maintenance overhead especially with large trees.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 5 Apr 2010 16:33:53 +0000 (19:33 +0300)]
main loop: Fade correctly when simulation runs fast
There was a bug that buffer fade amount was relative to the time it
took to run one simulation step, not relatively to the time interval
between two drawn frame. This patch fixes the issue.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 5 Apr 2010 12:43:43 +0000 (15:43 +0300)]
quadtree: Be more careful when deleting a node from the tree
Before attempting to move nodes back to the main tree, detach the
subtree completely from the main tree. When detaching individual nodes
from the tree, also ensure that each node has its old children
removed.
If these measures are not taken into account, loops will form in the
tree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Mon, 5 Apr 2010 09:19:26 +0000 (12:19 +0300)]
quadtree: Implement node removing
Removing a node from a quadtree is a tricky process. The node might
have multiple children which all need to be repositioned in the
remainig tree, which propably requires a recursive recreation of the
entire (sub)tree. If the given node happens to be the root node of the
tree, a new root needs to be selected for the remaining tree.
This kind of tree manipulation might have significant impact on the
balance of the tree. On the contrary, as massive tree reorganization
might be required, this is a good opportunity to rebalance the
(sub)tree. The introduced implementation does not address any
balancing issues at all.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 3 Apr 2010 10:02:44 +0000 (13:02 +0300)]
fade_buf: Optimizations
Since most of the buffer is usually black, we can skip the fading
entirely on those words that are already null. Only when the buffer
contains something to fade, individual color values are being
substracted.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Fri, 2 Apr 2010 09:59:03 +0000 (12:59 +0300)]
setup_planet: Concentrate the mass mostly in the middle of the system
This will increase the stability of the created planetar system. Most
of the central planets collapse into one large object, which will keep
most of the system more stable.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 31 Mar 2010 16:54:29 +0000 (19:54 +0300)]
main loop: Separate simulation time from true time
This allows simulation and other actions, such as camera movements, to
use different time steps. Now camera will move the same speed
regardless of the simulation time (eg. very low fps scenarios).
Furthermore, the maximum time step value is always respected and won't
be exceeded even though user adjusts the simulation speed to higher.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Wed, 31 Mar 2010 16:42:41 +0000 (19:42 +0300)]
gettime fixes
Return microseconds instead of nanoseconds. Also return value is now
delta from the first call to gettime instead of the absolute value of
the monotonic clock.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Sat, 27 Mar 2010 08:30:47 +0000 (10:30 +0200)]
quadtree: Move quadtree_add function in quadtree.c
The function in question is higly recursive. It is not likely the compiler will
be able to optimize it if it is kept in the header file as an inline function.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
Timo Kokkonen [Fri, 26 Mar 2010 21:24:44 +0000 (23:24 +0200)]
Quadtree: Initial commit
Add an initial and very basic form of the quadtree implementation. At
this point there is code only for the actual quadtree structure and a
function for adding nodes into the tree.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>