Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 26 Sep 2010
Offline Last Active Aug 27 2013 10:45 AM

Topics I've Started

Calculating area left uncovered by overlapping projected circles on a plane

23 August 2013 - 12:56 PM

I have a relatively flat mesh that can be projected onto a plane. The area of this projected mesh can be easily calculated.


I will be projecting disks (cylinders with 0 height) onto this projected mesh which will result in ellipsoids.


I need to find the area left uncovered.


Originally to accomplish this I quantified the mesh into n uniform pieces and used a colouring algorithm where each dsicrete piece is marked as overlapped or not overlapped. Then I sum the areas of the overlapped pieces and subtract those from the total areas of the projected mesh.


This is implemented in a compute shader as part of an energy calculation for simulated annealing.


Unfortunately it is does not yield suitable performance at high resolutions, nor the accuracy required at lower resolutions.


Is there any other way to calculate this?


EDIT: Is there a name for this type of problem, I do not know what to search to find ideas.

Area of mesh surface uncovered by accumulated convex sub-meshes

26 July 2013 - 02:48 PM

Lets say I concave triangular mesh surface, M, and convex submeshes, sMi, each of which are generated from the surface of M (so that any shared triangles can be considered identical). Submeshes can overlap eachother.


Lets say we need to find the total area of M that is not part of over of the submeshes.


I would do this by simply iterating over every submesh, and flagging each corresponding triangle on M. Then simply summing up all non-flagged triangles.


This is easy. My problem is a little more complicated.


My submeshes contain not only fully corresponding triangles, but also triangles that have been subdivided into partial triangles. They are generated from circular projections from the centre point normal.


Here is an example of a submesh, with black lines being the triangles from M and the green lines for the cuts of the subdivided triangles. The black circular outlines could be ignored.





Remember that these submeshes can overlap, so therefore the sub triangles could also overlap.


For example, this particular triangle is overlapped by two submeshes, blue and green (purple is the union of both).




Does anyone know of an approach I could look into for this type of problem?

Bi-Cubic interpolation over irregular patch

14 June 2013 - 11:26 AM

Essentially I would like to create a bi-cubic spline patch, define by four points, however the patch will not be rectangular. Is this possible?


Someone recommended Hermite Splines to me. In 2D it seems that it is defined by two points and 2 tangents. But I can't seem to find resources explaining how to approach it in 3D, let alone for irregular patches.


Could anyone recommend any resources?




I've looked around more and the only resource I was able to find talking about BiCubic Hermite splines is "Curves and Surfaces for Computer Graphics" by Salomon, D. found at


Section 4.9 has the information on BiCubic Hermite Curves.


Here's essentially the formulas for creating the Hermite Curve spliced together. I find it very difficult to follow as he refers to variables defined in previous chapters that rely on information that does not make sense (to me) in their current formula. Other variables are never defined. And everything is simply defined as a rearrangement of itself.



P(u,w) and aij are apparently from a previous chapter, which are defined as:




I feel like im on crazy pills. Does this make sense to anyone?

Finding a unit vector orthogonal to another vector, on a plane

12 June 2013 - 10:46 PM

I have a vector A, and I have a plane P consisting of a point (Pp) and normal (Pn)


I need to find the vector B, that is orthogonal to A and also on P.  To prevent infinite solutions, lets make B unit length.


If V is perpendicular to P there are infinite, we can ignore this case, as in my application it will never occur.


As far as I can see in every other case there will be two vectors.


We have 3 unknowns and therefore need three equations:


1) A and B are orthogonal, therefore their dot product is zero


    (A.x * B.x) + (A.y * B.y) + (A.z * B.z) = 0


2) If B is in the plane P, then there are orthogonal and the dot product between B and Pn is zero


    (B.x * Pn.x) + (B.y * Pn.y) + (B.z * Pn.z) = 0


3) B will be unit length


    sqrt(B.x^2 + B.y^2 + B.z^2) = 1


Now I assume I could plug these into a fancy equation solver and find vector B (and its negation), butI was hoping there is a more specific / optimized approach.


Any ideas?



Composing the concave hull of a textured sprite

27 April 2013 - 06:39 PM

I'm writing a 2D rendering engine, and currently I have shadow casting on convex shapes generated from the sprite textures. I would like to expand it to concave shapes, so now i need the concave hull of my sprite. Generating the edge vertices isn't difficult, it is assembling them into a coherent ordering that is giving me trouble.





I know there are more than one concave hulls for a generic set of points, but im hoping it is possible to exploit the spatial locality of the points produced from the texture to ensure the correct hull.


At first I was hoping to simply pick a random point, and then choose the closest point and just follow the trail. However, this fails quite easily. I'm wondering if anyone has any knowledge about this or any ideas on how to accomplish this...