[SciPy-User] SciPy for Computational Geometry

[jkhilmer at chemistry.montana.edu]

Lorenzo,

There is a very substantial body of research dedicated to your topic,
since it is essential for real-time rendering of 3D environments:
http://en.wikipedia.org/wiki/Binary_space_partitioning

You can certainly adapt existing code for your need, although
depending on your efficiency needs, it's probably easiest to just
write something from scratch.

1. For each sphere, determine a plane perpendicular to the line-of-sight.
2. For each sphere, calculate a set of points on the radius.
Granularity can be as fine as you need.
3. For each circumference point, find the intersection between the
line (circumference to origin) and each plane.
3. Calculate whether the line/plane intersection point is within the
radius for that circle (one circle per plane).
4. If the intersection is within the radius, that circumference point
is occluded.  Break out of plane calculations if you find an
occlusion.
5. Break out of sphere point testing if you find a circumference point
that is not occluded: that sphere is visible.

It's naive and not terribly efficient, but it is simple.

Jonathan



On Tue, Nov 1, 2011 at 9:12 AM, Anthony Palomba <apalomba at austin.rr.com> wrote:
> I am very interested in finding a good python package that does
> computational geometry.
>
> I was looking at CGAL for a while, but they python bindings do
> not seem to work and examples are pretty limited.
>
> If you do find something that works, please be sure to inform
> us as well.
>
>
>
>
> Thanks,
> Anthony
>
>
>
>
> On Mon, Oct 31, 2011 at 4:58 PM, <hayne at sympatico.ca> wrote:
>>
>> Maybe have a look at "microsphere interpolation":
>> http://www.dudziak.com/how_microsphere_projection_works.php
>> (Perhaps just looking at the diagram at the bottom of that page would
>> suffice for a start.)
>> This is not a Python implementation, but it might give you some ideas.
>>
>> --
>> Cameron Hayne
>> macdev at hayne.net
>>
>> On 31-Oct-11, at 5:14 PM, Lorenzo Isella wrote:
>> > This is admittedly a bit off topic, but I wonder if anybody on the
>> > list
>> > is familiar with this problem (which should belong to computational
>> > geometry) and is able to point me to an implementation (possibly
>> > relying
>> > on scipy).
>> > Imagine that you are sitting at the origin (0,0,0) of a 3D coordinate
>> > system and that you are looking at a set of (non-overlapping) spheres
>> > (all the spheres are identical and with radius R=1).
>> > You ask yourself how many spheres you can see overall.
>> > The result is in general a (positive) real number as one sphere may
>> > partially eclipse another sphere for an observer in the origin (e.g.
>> > if
>> > one sphere is located at (0,0,5) and the other (0,0.3,10)).
>> > Does anybody know an algorithm to calculate this quantity efficiently?
>> > I have in mind (for now at least) configurations of less that 100
>> > spheres, so hopefully this should not be too demanding.
>> > I had a look at
>> > http://www.qhull.org/
>> > but I am not 100% sure that this is the way to go.
>>
>>
>>
>>
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>