Jump to content

  • Log In with Google      Sign In   
  • Create Account

luca-deltodesco

Member Since 10 May 2006
Offline Last Active Sep 07 2013 03:50 PM

#5043030 Confused on Big Oh

Posted by luca-deltodesco on 14 March 2013 - 07:11 AM

I think the best example of that is triangulation:

 

Triangulating a polygon 'can' be done in O(n) time, but the algorithm to do this is so incredibly complex that unless you have a polygon with 100000000000000 (*number pulled out of my arse) vertices, an O(n.log(n)) or O(n^2) algorithm is going to do it faster.




#5027342 Collision Physics Question

Posted by luca-deltodesco on 30 January 2013 - 04:21 PM

It is not that there is less trig involved when using x-y vectors, but that there is NO trig involved.

 

I already showed you earlier how to do bouncing.

 

That you say you have done bouncing, but cannot figure out this, plus that you talk about the 'angle' of the slope tells me you are using trigonometry to do the bouncing... *sigh* smile.png

The solution is incredibly simple, using simple vector operations.

You have the slope normal vector (As opposed to its angle)
You have the incident velocity.

The outgoing velocity is then: newVelocity = velocity - normal*(1+e)*dot(velocity, normal)
where e is the coefficient of restitution. For a perfectly elastic bounce e = 1, for a perfectly inelastic bounce (your 'slide') e = 0.

If you're struggling to compute the normal vector. Assuming you have two positions for the slope 'a' and 'b' that you're using to compute your angle like atan2(b.y-a.y, b.x-a.x), then the normal for this slope is instead: unit(a.y-b.y, b.x-a.x). The normal is a unit-length vector that points 'out' (or 'in' for these purposes, makes no difference to the result) of the surface, so the left side of a box will have normal (-1, 0) etc.




#5026170 Collision Physics Question

Posted by luca-deltodesco on 27 January 2013 - 02:17 PM

That you say you have done bouncing, but cannot figure out this, plus that you talk about the 'angle' of the slope tells me you are using trigonometry to do the bouncing... *sigh* :)

The solution is incredibly simple, using simple vector operations.

You have the slope normal vector (As opposed to its angle)
You have the incident velocity.

The outgoing velocity is then: newVelocity = velocity - normal*(1+e)*dot(velocity, normal)
where e is the coefficient of restitution. For a perfectly elastic bounce e = 1, for a perfectly inelastic bounce (your 'slide') e = 0.

If you're struggling to compute the normal vector. Assuming you have two positions for the slope 'a' and 'b' that you're using to compute your angle like atan2(b.y-a.y, b.x-a.x), then the normal for this slope is instead: unit(a.y-b.y, b.x-a.x). The normal is a unit-length vector that points 'out' (or 'in' for these purposes, makes no difference to the result) of the surface, so the left side of a box will have normal (-1, 0) etc.


#5015554 How do I create a vector tangent to each point in a non-function defined surf...

Posted by luca-deltodesco on 29 December 2012 - 04:40 PM

sounds like an XY situation: http://www.perlmonks.org/index.pl?node_id=542341

Why don't you describe what your actually trying to do?

 

You want to write a shader, a shader to do what? 

 

You mention lighting, you mean that you want to write a shader to emulate how opengl would do its lighting?

 

You're talking about 'vector tangent to a point', do you mean the surface normal? You need to specify those for opengl lighting in the first place, so lighting is not really the question here, it seems to me you have a mesh, and you want to find the normals for each vertex of the mesh's triangles.




#5006619 Caustics - simple questions

Posted by luca-deltodesco on 03 December 2012 - 09:11 AM

It seems to simply mean that, given the triangle of a model which is specular, it casts a caustic; the caustic it casts when projected onto the plane is also a triangle (the caustic triangle) and the volume that the original specular triangle, and the projected caustic make is the caustic volume.


#5006584 New is SLOW!

Posted by luca-deltodesco on 03 December 2012 - 07:09 AM

Well if you think about what is actually happening:

In the first case, it is in the worst scenario doing a loop that has nothing to do; the local int is going to have been assigned to a register and at worst a space on the stack. In either case setting it to 0 is like nothing at all. Most likely your compiler is not even bothering to set it since it's unused, and may even be removing the loop altogether as it's not doing any work.

In the second case, each time you call 'new int' it's calling the operating system to ask it for space and performing lots of computations to choose the best place to allocate the int, with perhaps further logic to maintain the heap, same with delete in reverse.


#5006468 I need to remove these interior lines.

Posted by luca-deltodesco on 02 December 2012 - 08:07 PM

Further examples shown with results in red (additional number being number of times in total that vertex appears in output)

http://www.zimagez.com/zimage/screenshot-031212-021000.php


#5006465 I need to remove these interior lines.

Posted by luca-deltodesco on 02 December 2012 - 07:55 PM

For fun, I implemented my solution in Haxe and checked it worked with a somewhat degenerate case as well of having a dangling vertex connected outside the main exterior set

http://pastebin.com/uyu2ZehA


#5006450 I need to remove these interior lines.

Posted by luca-deltodesco on 02 December 2012 - 06:24 PM

Your step doesn't really need a triangulation. Eitherway given purely a set of lines you need to determine what the triangles are in the first place; and that same step can be used to simply determine the sub-polygons which would then lead to the same rule of an internal line has more than one sub-polygon using it and the triangulation step is pointless.

Eitherway, I don't see how you could determine those internal sub-polygons any faster than just traversing the exterior directly.


#5006422 I need to remove these interior lines.

Posted by luca-deltodesco on 02 December 2012 - 04:51 PM

Paradigm shifter, that only works if the lines always form triangles..

eg: http://www.zimagez.com/zimage/screenshot-021212-225045.php

here, your solution would choose to remove the crossed-out red line. My algorithm would give us the green polygon.


#5006421 I need to remove these interior lines.

Posted by luca-deltodesco on 02 December 2012 - 04:44 PM

One way to identify the exterior shell of your set of points (so we're assuming there are not any 'holes' that should be considered exterior to the volume).

a) Identify a point on the exterior of the line set.
b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c &amp;amp;&amp;amp; b < d)
For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

^^ this is very similar to gift wrapping algorithm for computing a convex hull and is exactly equivalent if we join every vertex to every other one using this algorithm.


#5005040 LPD3DXMESH to btConeShape

Posted by luca-deltodesco on 28 November 2012 - 01:26 PM

.... Assuming that the box is axis aligned, and the cone is aligned with y-axis.


#4996291 Calculating angles of rotation

Posted by luca-deltodesco on 01 November 2012 - 01:43 PM

Previous two responses: I think you missed his response that the API he's using permits ONLY setting z-x-y euler angles.


#4996120 Calculating angles of rotation

Posted by luca-deltodesco on 01 November 2012 - 03:01 AM

Use a better SDK? :P

We need to know what order the final transform gets applied, does it do X followed by Y, followed by Z or some other order?


#4995979 Calculating angles of rotation

Posted by luca-deltodesco on 31 October 2012 - 04:56 PM

You only need 2 angles to specify a direction in 3 dimensions, and your question really depends on what axis those rotations should be about, and in what order the rotations are supposed to occur.

Even specified properly, there's no total solution, since you can end up with gimbal lock, eg:

Say you define the rotations to be: a rotation about the y-axis, then a rotation about the x-axis; if AB starts at (0, 1, 0) then it is only possible to define the rotations if the new AB happens to be in the yz plane. No matter how you specify the two rotations you will end up with this problem. I 'guess' you could add a third rotation, that is only used in this corner case; but really you can probably do much better with a different representation of rotation, whether it be a quaternion or axis-angle

[Edit: Bob's suggestion is to use axis-angle]




PARTNERS