Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[MadocComadrin]

I'd say it depends on how often you're displaying the strings compared to how often you're comparing (via addition, deletion, etc) them. If you're displaying them often(compared to comparing), it might be worth the slow down at the comparison. IIRC, your best case sort for something like this is going to be at least O(n) (with a O(n) traversal assuming a node-based BST), while insertion is O(log(n)) followed by the O(n) traversal.

[da_nang]

Let's still centrally project the rectangle onto a plane orthogonal to p, so our cone of light intersects the new plane in a circle, not just any ellipse. That's the circle you need to use, by the way.

Well, see, there an infinite number of planes I could project the rectangle onto, the circle of each being a different size.

If x,y,z are Cartesian coordinates with the positive z-axis being the axis of the cone (I don't care how the other two are oriented as long as their components are orthonormal) and the origin at the apex, then the circle is given by x² + y² = (z tan α)² with z >= 0. So which z am I suppose to use here? Changing z would change the size of the red area when projected onto the plane.

Pick one of those planes, any one. Each will give the same result. Remember, you're not looking for the area of the red shape, but for its solid angle from P.

Also, for the spherical trigonometry bit: If the triangle has points P₁, P₂ and P₃, then the normal on the unit sphere where these points are projected are the position vector of each point, yes? As such, the spherical angles would therefore be the angles between these vectors. (I guess I also need to find the edges of the triangle so I can calculate the right angles).

EDIT: Wait, no it wouldn't, but I could calculate the arc lengths and from there use the law of cosines for spherical trigonometry to get them, right?

Exactly.

Sorry for dragging this on, but I have my doubts about this as a solution. If the choice the circle doesn't matter, then can't I pick an arbitrarily large or small circle that covers/doesn't cover the entire rectangle? Here's a thought. Say I have a rectangle that doesn't intersect the cone. Then the solid angle of the red area in question should be zero. But if I pick a sufficiently small enough circle such that the projected polygon is outside the circle, then the triangles formed by the edges of the polygon and the center point of the circle should only intersect as circle sectors.

Furthermore, according to the algorithm you proposed, then these sectors should have solid angles proportional to the solid angle of the spherical cap as well as the fraction of the circle they cover, which is non-zero. But that contradicts with the initial assumption: The rectangle doesn't intersect with the cone so it should have a solid angle of zero since no "light" is shone upon it and as such it casts no shadow.

In other words, shouldn't I take into consideration which parts of the projected polygon are inside vs outside the cone?

[MagmaMcFry]

Let's still centrally project the rectangle onto a plane orthogonal to p, so our cone of light intersects the new plane in a circle, not just any ellipse. That's the circle you need to use, by the way.

Well, see, there an infinite number of planes I could project the rectangle onto, the circle of each being a different size.

If x,y,z are Cartesian coordinates with the positive z-axis being the axis of the cone (I don't care how the other two are oriented as long as their components are orthonormal) and the origin at the apex, then the circle is given by x² + y² = (z tan α)² with z >= 0. So which z am I suppose to use here? Changing z would change the size of the red area when projected onto the plane.

Pick one of those planes, any one. Each will give the same result. Remember, you're not looking for the area of the red shape, but for its solid angle from P.

Also, for the spherical trigonometry bit: If the triangle has points P₁, P₂ and P₃, then the normal on the unit sphere where these points are projected are the position vector of each point, yes? As such, the spherical angles would therefore be the angles between these vectors. (I guess I also need to find the edges of the triangle so I can calculate the right angles).

EDIT: Wait, no it wouldn't, but I could calculate the arc lengths and from there use the law of cosines for spherical trigonometry to get them, right?

Exactly.

Sorry for dragging this on, but I have my doubts about this as a solution. If the choice the circle doesn't matter, then can't I pick an arbitrarily large or small circle that covers/doesn't cover the entire rectangle? Here's a thought. Say I have a rectangle that doesn't intersect the cone. Then the solid angle of the red area in question should be zero. But if I pick a sufficiently small enough circle such that the projected polygon is outside the circle, then the triangles formed by the edges of the polygon and the center point of the circle should only intersect as circle sectors.

No, no, you misunderstood. You don't pick the circle on the rectangle's plane, you pick a circle by intersecting the cone orthogonally with a totally new plane (this plane intersects the cone in a circle, which you then pick), and then you project your rectangle onto that plane centrally from P. The projected polygon is no longer necessarily a rectangle.

Furthermore, according to the algorithm you proposed, then these sectors should have solid angles proportional to the solid angle of the spherical cap as well as the fraction of the circle they cover, which is non-zero. But that contradicts with the initial assumption: The rectangle doesn't intersect with the cone so it should have a solid angle of zero since no "light" is shone upon it and as such it casts no shadow.

In other words, shouldn't I take into consideration which parts of the projected polygon are inside vs outside the cone?

That is exactly what I was explaining the whole time; my dissection algorithm was to help you figure out the part of the projected polygon which lies inside the circle (<=> inside the cone) and calculate its solid angle.

[da_nang]

Let's still centrally project the rectangle onto a plane orthogonal to p, so our cone of light intersects the new plane in a circle, not just any ellipse. That's the circle you need to use, by the way.

Well, see, there an infinite number of planes I could project the rectangle onto, the circle of each being a different size.

If x,y,z are Cartesian coordinates with the positive z-axis being the axis of the cone (I don't care how the other two are oriented as long as their components are orthonormal) and the origin at the apex, then the circle is given by x² + y² = (z tan α)² with z >= 0. So which z am I suppose to use here? Changing z would change the size of the red area when projected onto the plane.

Pick one of those planes, any one. Each will give the same result. Remember, you're not looking for the area of the red shape, but for its solid angle from P.

Also, for the spherical trigonometry bit: If the triangle has points P₁, P₂ and P₃, then the normal on the unit sphere where these points are projected are the position vector of each point, yes? As such, the spherical angles would therefore be the angles between these vectors. (I guess I also need to find the edges of the triangle so I can calculate the right angles).

EDIT: Wait, no it wouldn't, but I could calculate the arc lengths and from there use the law of cosines for spherical trigonometry to get them, right?

Exactly.

Sorry for dragging this on, but I have my doubts about this as a solution. If the choice the circle doesn't matter, then can't I pick an arbitrarily large or small circle that covers/doesn't cover the entire rectangle? Here's a thought. Say I have a rectangle that doesn't intersect the cone. Then the solid angle of the red area in question should be zero. But if I pick a sufficiently small enough circle such that the projected polygon is outside the circle, then the triangles formed by the edges of the polygon and the center point of the circle should only intersect as circle sectors.

No, no, you misunderstood. You don't pick the circle on the rectangle's plane, you pick a circle by intersecting the cone orthogonally with a totally new plane (this plane intersects the cone in a circle, which you then pick), and then you project your rectangle onto that plane centrally from P. The projected polygon is no longer necessarily a rectangle.

Furthermore, according to the algorithm you proposed, then these sectors should have solid angles proportional to the solid angle of the spherical cap as well as the fraction of the circle they cover, which is non-zero. But that contradicts with the initial assumption: The rectangle doesn't intersect with the cone so it should have a solid angle of zero since no "light" is shone upon it and as such it casts no shadow.

In other words, shouldn't I take into consideration which parts of the projected polygon are inside vs outside the cone?

That is exactly what I was explaining the whole time; my dissection algorithm was to help you figure out the part of the projected polygon which lies inside the circle (<=> inside the cone) and calculate its solid angle.

Except there always exists a circle large enough to encompass the projected polygon. Example seen from the side:

The green rectangle doesn't intersect the magenta cone. But I can pick two red planes orthogonal to the grey axis of the cone such that the cyan circle either partially covers or doesn't cover the blue projection of the rectangle as shown by the yellow normals.

[MagmaMcFry]

I said central projection, not orthogonal projection. You need to make the yellow lines go through P too.

[da_nang]

I said central projection, not orthogonal projection. You need to make the yellow lines go through P too.

Oh, well now it makes sense. Ok, then I'm off to finding a way to write a Matlab friendly version of it.

[ed boy]

I have a linear algebra problem in my code.

Suppose I have a vector V of N unknown values.
I also have four matrices of known values, A,B,C,D, such that:

A*V=B
C*V≥D

That is, each row of C*V is at least the value of the corresponding row of D.

I'm interested in knowing if there exists a vector V that satisfies this. Finding the values of V would be nice, but it is by no means necessary.

Is there a python module that can do this? Failing that, how would I go about coding it myself?

[MagmaMcFry]

That type of problem is called a linear programming problem. A quick Google search suggests that PuLP looks really nice to use.

[ed boy]

That type of problem is called a linear programming problem. A quick Google search suggests that PuLP looks really nice to use.

Thanks. i could find lots of modules that could solve linear programming with equality constraints, but not mixing inequality and equality.

[MorleyDev]

You know, with all the "C++11 wooh C++ is back" and "Functional programming is the salvation of efficient computation in a multicore environment", you'd think there'd be a few more attempts out there to provide libraries that combine to two.

But all I've found is a single library called FC++, that is mostly lambdas and lazy lists, and one github repository that could be used as a basis and takes advantage of shared_ptr, which is a clever idea for sharing the memory though the current implementation it uses does come at the expense of locality. May give implementing the list and RBMap a go, see if I can give them custom allocator support.

Maybe I've just become too enraptured by Scala and Haskell of late...

[alway]

You know, with all the "C++11 wooh C++ is back" and "Functional programming is the salvation of efficient computation in a multicore environment", you'd think there'd be a few more attempts out there to provide libraries that combine to two.

But all I've found is a single library called FC++, that is mostly lambdas and lazy lists, and one github repository that could be used as a basis and takes advantage of shared_ptr, which is a clever idea for sharing the memory though the current implementation it uses does come at the expense of locality.

Maybe I've just become too enraptured by Scala and Haskell of late...

So the thing is, function pointers are only good for efficient computation in a subset of multicore environments.

GPU architecture, which is sort of my specialty at this point, is vastly different. Your typical CPU is Multiple Instruction, Multiple Data (MIMD); whereas gpu architecture is much more oriented towards Single Instruction, Multiple Data (SIMD). What this means is that the CPU has multiple instruction sets; one for each of your cores. Functional programming works well there, since each core is off doing its own thing. The GPU, on the other hand, has significant sharing of instruction sets. A typical GPU has thousands of cores, but a complex hierarchy of allocation which results in around 128 - 512 cores at a time (user specified) to be all following the same set of instructions. Within these dynamically allocated, user-specified chunks, there are manufacturer specific "warps"/"wavefronts" (term varies by manufacturer/gpgpu language, but they're all basically the same thing; 32 for NVidia, 64 for AMD). These warps consist of a number of compute cores all executing exactly the same instructions in lockstep. Even having 2 code paths is very bad, since this setup runs both code paths, simple idling the threads in the warp which do not enter into a branch. So the following pseudocode:

Code: [Select]

if(warpId < 16)
DoStuff();
else
DoOtherStuff();
Will first run the DoStuff branch, taking all 32 cores for the ride, then run the DoOtherStuff branch afterwards, again taking all 32 cores for the ride. The first 16 cores will DoStuff, while the last 16 cores simply idle, waiting for the code irrelevant to their path to finish; afterwards, the first 16 cores will simple idle, while the last 16 cores DoOtherStuff. Because these warps are part of GPU hardware architecture, the cores within them can not be re-allocated to another process while idling during branching instructions like this. And so, simply by splitting your cores into 2 groups this way, you're wasting a full 50% of your compute power. So, while functional programming can be nice for some applications, it utterly fails on many of the most powerful forms of parallelism.

And really, even on the CPU, I doubt it's the most efficient use of resources. You would likely get higher performance from the most parallelizable problems by using a Data Oriented Programming technique (super easy to load balance, and thus parallelize efficiently, while optimal in terms of cache misses which can destroy performance on modern cpus). The only real reason you would want to use functional programming for parallelism is problems which are not already massively parallel. Or in summary, parallelizing a problem is only the first step, and usually not the hard one. The next step is taking into account hardware architecture and how to make a solution which is as efficient as possible. Doubling your compute power for a 1.2x speedup is nice; doubling your compute power for a 1.95x speedup is better.

[Telgin]

I just shuddered a tiny bit rereading all of that and remembering how one of my early grad school projects involved writing a Valgrind plugin to simulate warp divergence and reconvergence.  The idea was to find which branches caused the most divergences and for how long the program stayed diverged.  That really sucked, but I eventually managed to get it to work for the most part.  Then no paper ever came of it.    Partly because the programs ran 100x slower than normal, and also partly because Nvidia's profiling tools apparently can now do that.

Anyway, the discussion on functional programming reminds me that I should probably actually look into that again some day.  We very briefly covered it in an algorithms class at some point, but I can't remember if I've ever even written a program in a functional language.

[MorleyDev]

I wasn't actually saying functional programming is a silver bullet, I was more making a joke that the way that some of advocates are talking about it you'd think it was the next Jesus

A strict OOP approach doesn't spread well over multiple cores, true, but from all the talk I've seen (and my own experience) a pure OOP is becoming increasingly uncommon in the main OOP-languages. Heck, I've found that just applying the "good" programming principles (SOLID, TDD) tends to force a more functional approach nowadays anyway because it's easier to test and reason about. At the function level, state is the exception rather than the rule.

Of course it always depends on the problem domain, a small application hardly needs the speed gains of parallelism after all. GPUs and CPUs have entirely different requirements placed upon them. I was more just curious what libraries were available for 'functional' data structures, and surprised by the lack of even young libraries floating around that provide such a thing.

Also I guess it depends on exactly what one is counting as functional programming.  Functional programming is all about lacking state, as I understand it shader languages could be considered a subset of functional programming, shaders don't typically have state between each "run" as I understand it. Actor model approaches are often used in a functional way, and offer high parallelism in CPU environments. MapReduce is common in functional data structures, and can easily be spread over multiple cores, and arguably all shader operations are map operations. Even Java has introduced MapReduce operations in Java 8.

[Telgin]

I'm not sure stateless really describes shader languages, although I admit that I have only written OpenCL programs and not GLSL or whatever DirectX uses these days, so it might be a bit different.  They're written like most any other C-like language, with program flow and memory usage working roughly the same from a programmer's perspective.  It's really more of a matter of being locked into having blocks of threads doing the same computation than lacking state, since you can store and use temporaries in local memory, or change global host memory if you want.

Actually, that might really be different for graphics shaders compared to CUDA and OpenCL.  GLSL and DirectX shaders rely more on explicit parameters coming in if I recall, and I'm not sure if they allow reading and writing host memory directly.

Also, I'm now aware that I really need to go look up the precise definitions of all of this stuff, because if I recall being functional / stateless meant something a bit different from just being able to store things in persistent memory.

[MorleyDev]

I know you can have variables inside a shader run itself, but I'm not sure if GLSL/HLSL allow for persisting those variables from one iteration of the shader to another. So for a given definition of stateless...I mean, it may be possible and I just missed it as I've not done a lot of shader stuff. And I know GLSL has mutability, since for loops are possible. I meant more that, as I understood it, to the outside world a GLSL/HLSL shader appears stateless as it only takes a defined input and returns a defined output with no internal state being persisted between calls and no side-effects. So given the same input, a shader should always return the same output.

Functional data structures are often written as persistent data structures, since that's more memory/CPU efficient than constant copying of large chunks of data. Hence why shared_ptr makes sense for a basic implementation, it works as simple way to guarantee that as soon as no data structure refers to that value it is freed.

I could be fundamentally misunderstanding something, and I'm definitely not an expert on shaders since I've only written some simple ones a few years ago and not revisited much since.