Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #9559

Re: particle container in Java

Show all headers | View raw

On 11/4/2011 3:54 PM, Roedy Green wrote:
> On Thu, 03 Nov 2011 13:51:38 -0700, BGB<cr88192@hotmail.com>  wrote,
> quoted or indirectly quoted someone who said :
>
>> in my 3D engine (mostly written in plain C) I use a BSP-tree style
>> structure.
>
> I had never heard of Binary Space Partitioning trees before.
>   http://en.wikipedia.org/wiki/Binary_space_partitioning
>

I use BSP tree variants for lots of things (rendering, physics, 
particles, scene-graph, ...).

early on (before about 2005 or so), I just used them mostly for 
geometry, but then later discovered algorithms which allowed updating 
and rebuilding them in real-time (or, IOW, a dynamic BSP), which I have 
been making use of since (my 3D engine does not use a prebuilt BSP).

there are a few drawbacks (the BSPs are less optimal, thus far my 3D 
engine doesn't do inter-brush clipping/CSG, ...), but in general it is a 
reasonable tradeoff (not having to pre-build the scene allows a lot more 
nifty stuff).


> I invented Hanging Moss myself back in the 1970s to optimise the
> motions of pen-plotters.  The problem was to rapidly find a nearby
> thing to draw next.  It was astoundingly faster that computing the
> distance to everything else and finding the minimum.
>

yes, it would be...
a BSP is much faster than a linear search as well, FWIW.

another (common) option is oct-trees, but a drawback of oct-trees is 
that one either needs a bounding-box for the region, or to decide upon a 
maximum region size, before one can build an oct-tree.


FWIW, I did not exist in the 70s (my existence began in the 80s).


> It is just a classifying grid.  At each square you have a chain of
> objects.  To find a point near another you chase the chain in the
> appropriate square. If you don't find anything you search the next
> outer ring of squares.
>
> If you doubly link the chain, you can efficiently delete and insert.
> If you singly link, you can do LIFO/FIFO.
>

so, like a chain-hash?...

I guess it could work.


I guess a downside of BSPs is that they can really be built 
asynchronously and/or scaled to an arbitrary size (at least not with my 
current algorithms).

a partial solution (in my 3D engine) may be (or may have been with) the 
introduction of "regions" (loosely influenced by the regions in 
Minecraft), which are currently cubes with a size of 16384 units (1.5 
inches/unit) on a side (albeit they are only 4096 units tall). however, 
currently the "region" system exists independently of the BSP (it mostly 
manages voxel terrain and similar).

the idea would be to allow an arbitrarily large yet continuous world 
(like that in Minecraft) with piecewise loading/unloading as the player 
moves around the world.

as-is, there had been some work at trying to integrate voxels with the 
pre-existing Quake-style worlds.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

particle container in Java bob <bob@coolgroups.com> - 2011-11-03 01:05 -0700
  Re: particle container in Java Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-03 08:33 +0000
  Re: particle container in Java Roedy Green <see_website@mindprod.com.invalid> - 2011-11-03 08:12 -0700
    Re: particle container in Java BGB <cr88192@hotmail.com> - 2011-11-03 13:51 -0700
      Re: particle container in Java Roedy Green <see_website@mindprod.com.invalid> - 2011-11-04 15:54 -0700
        Re: particle container in Java BGB <cr88192@hotmail.com> - 2011-11-04 19:48 -0700
          Re: particle container in Java Roedy Green <see_website@mindprod.com.invalid> - 2011-11-05 06:42 -0700
  Re: particle container in Java Giovanni Azua <bravegag@hotmail.com> - 2011-11-03 23:38 +0100
    Re: particle container in Java BGB <cr88192@hotmail.com> - 2011-11-03 22:41 -0700
      Re: particle container in Java Roedy Green <see_website@mindprod.com.invalid> - 2011-11-05 06:49 -0700
        Re: particle container in Java BGB <cr88192@hotmail.com> - 2011-11-05 09:16 -0700
          Re: particle container in Java Roedy Green <see_website@mindprod.com.invalid> - 2011-11-06 03:07 -0800
            Re: particle container in Java Giovanni Azua <bravegag@hotmail.com> - 2011-11-06 15:15 +0100
              Re: particle container in Java BGB <cr88192@hotmail.com> - 2011-11-06 11:06 -0700
  Re: particle container in Java Arne Vajhøj <arne@vajhoej.dk> - 2011-11-03 19:03 -0400

csiph-web