Simulation of optical detectors

[Bryan Y]

The classic art gallery problem (http://en.wikipedia.org/wiki/Museum_guard_problem). Here's a book (http://www.amazon.com/Theorems-Algorithms-International-Monographs-Computer/dp/0195039653). I remember reading this author and his description of the problem. Here's a paper (http://citeseer.ist.psu.edu/cache/papers/cs/1210/ftp:zSzzSzfubinf.inf.fu-berlin.dezSzpubzSzreportszSztr-b-94-22.pdf/hoffmann94art.pdf) for rectilinear solutions.

[heavenly1]

Thank you so much, Bryan! I was trying to google every keywords that I could find, but couldn't find anything. So it is seems to be an old problem, it makes sense that it is a big issue for art galleries.

Thanks a lot, man.


I have another question. In my project, I am dealing with optical flame detectors, which has limited range, thus they can only detect flame to a certain distance, because they have sensitivity to light (lux) to a certain limit. So it is an extension of the art gallery problem. Don't know if any of you have any ideas for this.

(edit: added further question)

[Bryan Y]

I myself don't know. I only remember coming across it one of O'Rourke's books.

[tbaypaul]

..... your problem with the limiting distance may be more like that of the Voroni diagram.....it's known as the forest fire watch tower problem......ORoark is the source there too...."Computational Geometry in C" for your lite summer reading.....

[heavenly1]

..... your problem with the limiting distance may be more like that of the Voroni diagram.....it's known as the forest fire watch tower problem......ORoark is the source there too...."Computational Geometry in C" for your lite summer reading.....

Thanks Paul. I wasn't aware of this. I had actually borrowed that book from the library because of art gallery problem, but I see now that it covers Fire Observation Towers too. However, a fire tower covers 360 degrees, which isn't a case for an optical fire detector. At most today's flame detectors have a field of view of 90 degrees. Which means that it in order to cover 360 degrees, we would have like 4 sensors in the same place, which never happens in real life. So I would welcome any tips and ideas.

I am surprised that this kind of problem hasn't been raised before, or at least I don't know the popular term of this very problem.

[ThE_JacO]

A lot of things like art gallery and watch towers are intentional formalizations and abstractions of the problem, not necessarily meant to present a schema to solve the practicalities of those situations.

You're asking the question in a programming forum, so I assume you have (or wish to acquire) a basic understanding of the subject, correct me if this is a wrong assumption.

In first place what exactly are you after? Something that you can feed cad data of a locale to and that will then return the ideal position (based on a set of rules I assume) of cameras to cover the near totality of the volume with the least amount of camera possible?

If that's the case, and considering you'll have fairly big thresholds, I can't see why something like that couldn't be solved with a brute force approach, like discretizing your volume, having a set of points for all possible camera positions, and run sheer permutations. Even with several million subdivisions to inspect and several hundreds possible camera positions that would only take minutes to solve at worst, and the most basic optimizations like an acceleration structure for the volumes (OCtree probably being the best bang for the buck) and the most basic permutation filtering would take it down to seconds.

What kind of complexity and size of (floor) plans and number of installations are we talking about here?

Formalized problems are fantastic exercises and study tools, but they don't necessarily always relate to the best practical implementation given the volume of cpu power of modern processors.

It's kinda hard to deal with this as a practical problem when you present it completely unbounded :)

[heavenly1]

Hi ThE_JacO.

You seem very knowledgeable about this. Pretty much spot on.

I want to simulate optical flame detectors in typical oil installations, environments with obstacles like pipes, tanks and such. So mostly it is outdoor environment I think, like oil drilling platform, which can have multiple floors. But I will be very glad even if we can solve it for a small room with minimal obstacles too.

So it will be feeding a program with CAD drawings, and ideally, this software will use a "magic" algorithm to place these optical flame detectors in the environment with the minimum number of detectors with a given coverage percentage of hazard areas or the the whole volume of the bounded area.

I would also like to mention that these detectors doesn't have unlimited distance range. They have a limited range for a given flame size.

As we can see, there exists so many different algorithms, and I am not sure what can be used to solve this problem. Perhaps some alorithm/optimization experts could guide me through this.

Thanks for your help.

[ThE_JacO]

I'm not that knowledgable about the subject, but it can easily be generalized and put close to existing rendering techniques.
Dealing with boxy enclosed environments is a fairly simple problem that can be bruteforced through, if you start having possible obstructions though the problems becomes of a completely different order, since instead of simply having to test each voxel being inside or outside a cone, you have to pretty much render the whole thing through each camera.

What is still unclear to me is what programming/cg/rendering knowledge you have at hand (yours or others'), and what you have to achieve by when.

You could use some very simple system to generate the camera position permutations, and an app like blender to generate and render a number of scenes, but it would need a good system worked out and it might turn out quite complicated.

If it's open environments you also start having to deal with photometric issues and thresholds, and I have no idea if your data for the camera already contemplates that and you always work by the worst possible case, or if you need those variables considered as well.

[heavenly1]

I'm not that knowledgable about the subject, but it can easily be generalized and put close to existing rendering techniques.
Dealing with boxy enclosed environments is a fairly simple problem that can be bruteforced through, if you start having possible obstructions though the problems becomes of a completely different order, since instead of simply having to test each voxel being inside or outside a cone, you have to pretty much render the whole thing through each camera.

What is still unclear to me is what programming/cg/rendering knowledge you have at hand (yours or others'), and what you have to achieve by when.

You could use some very simple system to generate the camera position permutations, and an app like blender to generate and render a number of scenes, but it would need a good system worked out and it might turn out quite complicated.

If it's open environments you also start having to deal with photometric issues and thresholds, and I have no idea if your data for the camera already contemplates that and you always work by the worst possible case, or if you need those variables considered as well.

This university thesis is due in less than 2 months time. I know some Java and C++, but I don't know much about CG programming. It's not that important anyway, since I won't be able to implement it in this short amount of time. The most important thing is to know the algorithms and mathematics for solving this problem, and how it could be implemented for example, in C++ and OpenGL. It's about designing and have the theory to be able to implement it later.

So I have like i previously stated, I have come across a software for simulation of lamps. This software is implemented in C++ using OpenGL, using a radiosity-engine to calculate all the light illuminations and reflections, before rendering it with OpenGL. It can import a 3D CAD drawing of a room or environment and then place the lamps around it and then do the light calculation to show how the light will be spreaded in that environment. You can put calculation planes (xy) in that room in different heights to show the lux value for the points in that plane. It can also show lux curves, in the same way as height curves in a geographic map. Obviously there is a a lot of things in this software that can be reused for my project.

I have had talks with them together with an external company I am doing this project for. They won't give away the source code to me to modify it. So I will only be coming up with ideas for how that software could be modified to suit our goals for flame detection simulation.

As we are simplifying things, we don't have to worry about reflections and other photometric issues.

The external company I'm working for want to be able to compare the differences between their detectors and their competitors' detectors by using this "to-be-simulation-software".

Some other useful things I would also like to have is showing hard/distinct light beams going out from the the detectors, just to better illustrate what the detectors can detect. I don't know how it could be done in OpenGL.

Feel free to ask me, if something is still unclear, I will gladly explain it.

Thanks for your help.

[CGTalk Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.