Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail From: BGB Newsgroups: comp.lang.java.programmer Subject: Re: particle container in Java Date: Fri, 04 Nov 2011 19:48:12 -0700 Organization: albasani.net Lines: 74 Message-ID: References: <17fed3e9-15e0-466c-bb24-10e74633ea1b@t8g2000yql.googlegroups.com> <89r8b7964oa0l75o7cvgh06r53l3f4t96d@4ax.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.albasani.net OmS4pkLtdEPpZwp881iw10o0P2di+mzYsY6/8LvaUwtMyx6NMVw7vT8/yp5RUiNkGkIMOxC0/4BesdGIIHPnfmydLmYVTxHAWWPUKHyyS8qmrXjIKMs1QTO99KRw/arX NNTP-Posting-Date: Sat, 5 Nov 2011 02:48:43 +0000 (UTC) Injection-Info: news.albasani.net; logging-data="7W7aCQ5jJde+P6SoNSpNyKLClsP/q1IbLQ2bWc005ZcSmXtEl1whpwlKBiEoKtsRAlMTUWQ53bmcmJ8YO8CJmuedMWFs2xjnR73VcIUYrlmZsvlFy5q4YYESuHZ/lPo6"; mail-complaints-to="abuse@albasani.net" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:7.0.1) Gecko/20110929 Thunderbird/7.0.1 In-Reply-To: <89r8b7964oa0l75o7cvgh06r53l3f4t96d@4ax.com> Cancel-Lock: sha1:dMFOJcTPFkRxglvjIeSn1mpNzoE= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9559 On 11/4/2011 3:54 PM, Roedy Green wrote: > On Thu, 03 Nov 2011 13:51:38 -0700, BGB 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.