Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 10 Oct 2005
Offline Last Active Oct 23 2016 03:22 PM

#5228713 Intersection between circle and line segment

Posted by on 13 May 2015 - 01:32 AM

Okay now i restructured my code

Well, now you use a totally different method of computation: Before it was checking for the point on the segment that is closest to the circle's origin, now you use the implicit circle formula to check for identical points on the line. That is a replacement, not a restructuring!


The originally used method has the advantage that the distance of the intersection along the segment was computed, and that is good to judge whether the intersection is inside or outside the segment's range. The now use method does not compute that distance anywhere. So ...


a) you go back and use the original method, together with the 2 conditions I've posted above; I would suggest this way (in assumption that the original method works well for lines),




b) you check whether the computed intersections(s) are between the end-points of the segment. For this you can use the projection method, too.

#5228703 Intersection between circle and line segment

Posted by on 13 May 2015 - 12:53 AM

AFAIS the method used above computes the relative projected length of the difference vector (between the line segment's start and the center of the circle) and the line segment. The result denotes the distance to the point on the segment and closest to the circle, and it is stored in variable t. 


a) If there is just 1 intersection than t need to be between 0 and 1, because the closest point is also the intersection point.


b) If there are 2 intersections then the intersections are at distances t-dt and t+dt. Any of these need to be in the range [0,1] to be valid.

#5228150 Get the distance of an intersection

Posted by on 09 May 2015 - 12:48 PM

Yes because basically the ray object just holds two points [...]

The ray has a member named "origin" and a member named "direction". While the type of the origin is a point vector, the type of the direction is, well, a direction vector. A direction vector is the difference vector from one point to another and, usually also normalized in its length. Defining a ray that way is natural since a ray is a directed infinite long line. The formula I've chosen to describe the ray in one of the posts above reflects this, i.e.

   r( k ) = v1 + k * v2

where v1 is the origin (a point) and v2 is the direction. Since a point plus a difference vector gives again a point, the formula describes well an infinite set of points that together give the ray.


[…] and i didn't want to create another object

Since your line segments use the same class, they naturally fall into the same interpretation. It is not good practice to interpret the same class in different ways just at will. As you can see here, all my posts have been written under the assumption that the variable names stand for what commonly is understood for them, and foremost that they are interpreted uniformly.


[…] because now my segments are not displayed the way i wanted them to be, aren't they?

To solve this, if your line segment goes from point p1 to point p2, and you want to use the ray class to store it, then convert (p1,p2) into a ray like so:

    seg.origin.x = p1.x;

    seg.origin.y = p1.y;

    seg.direction.x = p2x - p1x;
    seg.direction.y = p2y - p1y;
and all is okay.


If, on the other hand, you want to store a segment as 2 points, then make another class with members e.g. from and to, and adapt the computations accordingly to the substitution

    v3 := p1

    v4 := p2 - p1

resp. in code

    x3 = seg.from.x;

    y3 = seg.from.y;

    x4 = seg.to.x - seg.from.x;

    y4 = seg.to.y - seg.from.y;

#5228099 Get the distance of an intersection

Posted by on 09 May 2015 - 07:20 AM

The intersection test works fine, but your javascript is wrong at two places (or: your naming of variables does not match their usage):


1.) You draw the segment as point to point, but the naming suggests that it has an origin and a direction.


2.) The same is true for the ray.


Hence try the following replacement:

           var draw = function(){
                for(var i = 0; i < segments.length; i++){
                    var seg = segments[i];
                    ctx.moveTo(seg.origin.x, seg.origin.y);
                    ctx.lineTo(seg.origin.x + seg.direction.x, seg.origin.y + seg.direction.y); // <<<< LOOK HERE

            canvas.onmousemove = function(event){
                ctx.clearRect(0,0,ctx.canvas.width, ctx.canvas.height);
                ctx.arc(event.pageX, event.pageY, 4, 0, 2 * Math.PI, false);
                ctx.fillStyle = '#FF0000';
                var r = new ray(new vec(center_x,center_y), new vec(event.pageX - center_x, event.pageY - center_y)); // <<<< LOOK HERE
                var ret = r.intersect();
                if(ret != null){
                    var hitPoint = r.origin.add(r.direction.multFloat(ret)); // <<<< ((compute this only if ret != null))
                    ctx.moveTo(center_x, center_y);
                    ctx.lineTo(hitPoint.x, hitPoint.y);

#5228091 Get the distance of an intersection

Posted by on 09 May 2015 - 06:46 AM

Sorry, I've made a mistake in replacing the indices when copying from paper to the web editor. The mistake was below "Otherwise…".


Please try

var k = (-y4 * (x3 - x1) + x4 * (y3 - y1)) / det;
var n = (-y2 * (x3 - x1) + x2 * (y3 - y1)) / det;

instead of what I told before.


That's clearly the reason why I always mention "please check twice" ;)

#5228075 Get the distance of an intersection

Posted by on 09 May 2015 - 04:55 AM

Instead using an arbitrary number as limit, using a value that could not occur in a valid solution would be better. That could (if supported by the language) a nil / null / void, in case of a floating point result also NaN, and so on. In your case you want to return only positive distances, so an invalid value would also be any negative number. Hence

something like

var finalLen = -1.0;
if (finalLen<0 || length < finalLen)
     finalLen = length;

would be a working solution that does not use arbitrary numbers, and hence would be better practice.

However, that will not make the code working on the whole. For me its not clear what all that calculations shown in the code snippet are actually good for. It seems me that there is more done than necessary. Have you copy-&-paste'd it, or can you give an explanation of what's going on?
I'd solve the problem as follows (here comes some reasoning in math, followed by the stuff that needs to be programmed from and inclusive the computation of "det"; but noticed that I've written this without having tested it, so please check twice):
The ray is defines as:  r( k ) := v1 + k * v2
A line segment is defined as:  s( n ) := v3 + n * v4   w/   0 <= n <= 1
An intersection point requires:  r( k' ) == s( n' ) for some (k',n')
Hence the equation to solve is:
   v1 + k' * v2 == v3 + n' * v4  with k' and n' being the unknowns.
With some re-ordering
   v2 * k' - v4 * n' = v3 - v1
and written in matrix form
  [ v2  -v4 ] * [ k'  n' ]tv3 - v1
so that
  [ k'  n' ]t = [ v2  -v4 ]-1 * ( v3 - v1 )
one has to compute the right side to get the solution.
The right side can be computed if and only if the matrix given by v2 and v4 can be inverted (if not, then the ray and the line segment are parallel, including the case of lying one above the other). So … let's try to invert it; we'll go the way shown here.
First we need to compute the determinant of the matrix, which gives us
    det = x2 * -y4 - y2 * -x4 = x4 * y2 - x2 * y4
We can compute the inverse of the determinant, 1/det, only if det is not 0 (what this means is already said above). So cancel to consider the current segment if det is computed to be 0.
Otherwise… the inverse matrix looks like so
   [ [ -y4  -y2 ]t  [ x4  x2 ]t ] / det
and multiplying this with ( v3 - v1 ) gives finally
   k' = ( -y4 * ( x3 - x1 ) + x4 * ( y3 - y1 ) ) / det
   n' = ( -y2 * ( x3 - x1 ) + x2 * ( y3 - y1 ) ) / det
You do want to use only intersections in front of the ray's origin, what means the condition k' > 0. If this is not given, then cancel the current line segment.
You also want line segments, so that the condition (see above) n'>=0 && n'<=1 must be true, too. If it is not given, then cancel the current line segment.
If all conditions are passed, then remember the smallest k'.
After all segments have been processed, and the remembered smallest k' is valid (see the beginning of this post what "valid" should mean), then compute the intersection of interest as
   r( k' )
and you're done.
EDIT: As you can see, there is much less stuff than in your latest code snippet. That is what makes me wonder what exactly you are doing therein.
EDIT_2: Indices below "Otherwise…" corrected.

#5228061 Get the distance of an intersection

Posted by on 09 May 2015 - 02:20 AM

Is my code correct?

I haven't investigated the math in that code snippet. However ...


* The selection is definitely not correct, since it does not necessarily return the minimal distance of all intersections in front of the ray origin. Instead, it returns the distance of the last intersection found in that direction. You need to assign the computed length to the finalLen if and only if the new distance is less than any previously assigned value.


* Where comes the initial "5000" from? Is it an arbitrary value you have picked, or it is correctly chosen as a limit where actually computed lengths definitely fall below? If the latter, have you considered that a length is computed (and hence to be compared) as square norm, so that a limit need to be squared, too?

#5227968 "simple" equation confusion (a - b = c)

Posted by on 08 May 2015 - 09:50 AM

-B = C - A (-5 = 10 - 15)
and NOT
B = A - C

Err, why NOT??



  A - B = C

both forms

  -B = C - A  ((A subtracted on both sides))


  B = A - C ((B added and C subtracted on both sides))

are equivalent, because you just need to multiply one of the equations by -1 to yield in the other equation.



But what do you personally used as a 'bridge' / reminder to approach it the right way at once?
(most of the item I end up trying B = A - C and get it wrong)

I don't understand. I make equivalence transformations until the unknown variable is isolated (or else I do not know how to continue). In the given example I'm interested in B, not in -1 times B.

#5227948 Get the distance of an intersection

Posted by on 08 May 2015 - 07:46 AM

So like this?

if(this.direction.dot(point.sub(this.origin)) > 0)

Yep, seems me principally okay.

#5227937 Get the distance of an intersection

Posted by on 08 May 2015 - 06:52 AM

Hi and thanks for your detailed answer:



If this is not wanted, then the dot-product of the ray's direction vector with the difference vector from the ray's origin to the intersection point can be used to determine whether the intersection lies "before" or "behind" the origin.


Which value should the result be to be in front (so in the rays direction) of the origin?

The dot-product yields in 0 if the both vectors are orthogonal (or the distance is zero, i.e. the intersection is exactly at the ray origin), a value greater than 0 if the both vectors point roughly in the same direction, and a negative value if the both vectors point roughly in reverse directions.


So, if you compute the difference vector v from the ray origin o to the intersection point p

   v := p - o

then you can expect positive values of the dot-product for intersections points in direction of the ray, and negative values for points in anti-direction. (The sign will reverse if you use difference vectors from the intersection point to the ray origin, i.e. o - p.)

#5227922 Get the distance of an intersection

Posted by on 08 May 2015 - 05:00 AM

1.) This statement

I have this code which intersects a ray and line segment:

is wrong. The code snippet shows at most an intersection of a ray with a line, but not with a line segment. There is nothing that detects whether the ray passes past the endpoints of the segment.


2.) This line

var y3 = seg.direction.y;

should obviously be

var y3 = seg.origin.y;


3.) To come to the originally asked question: 


a) Since all points are on the same ray, the distance of the ray's origin and the intersection point can be used

ai := sqrt( ( xi - x1 ) * ( xi - x1 ) + ( yi - y1 ) * ( yi - y1 ) )

from which the minimum is the valid point.


Notice that this kind of solution takes into account intersections both in direction of as well as in anti-direction of the ray. If this is not wanted, then the dot-product of the ray's direction vector with the difference vector from the ray's origin to the intersection point can be used to determine whether the intersection lies "before" or "behind" the origin.


Optimization: Since you just need the relative ordering of intersections, you can use any transformation that does not change that order. It allows for dropping the (costly) square-root:

ai := ( xi - x1 ) * ( xi - x1 ) + ( yi - y1 ) * ( yi - y1 )

b) Another solution would be solve the original problem by computing the traveling distance of the ray.

#5227910 arrays

Posted by on 08 May 2015 - 12:57 AM

I'm not familiar with that SDK, but the following issues seem me exist:


1.) Reading 16 floats if just 1 is needed is wasteful.

2.) Allocating another 16 floats if 1 is used is wasteful.

3.) Within XPLMSetDatav you take the address of the 10-th element and apply the unary negation!?


IMHO the needed code snippet looks like so (but is untested):

    float value;
    XPLMGetDatavf(pnlBri, &value, 10, 1);
    value = 100-value;
    XPLMSetDatavf(pnlBri, &value, 10, 1);

#5226983 How to separate xyManager effectively into smaller responsibility classes?

Posted by on 03 May 2015 - 11:37 AM

Well, i am pretty sure passing some refs/pointers all around the code base just because somewhere deeply in the codebase somebody might want to use it is a bigger antipattern than using singletons...
And if 99 command from 100 don't use it, then i feel like it's unnecessary.

In such a case the design itself is probably wrong.


Well, maybe i will be unable to keep the "1 command pattern for every cases", but it's possible that from the same function i can create different type of commands, and that's problematic.
For example, i have a unit with these skills:
- Summon 2 skeleton (Unit pool required for execution)
- Give a shield to a building (Building pool required, it would be kinda strange if a building would have a pointer to the pool, which contains the building itself)
- Give vision to somewhere in the map (map, or whatever will handle the fog of war required)
The "solutions" i see:
- Make some classes singleton, so i can reach them when i need, but then... i ended up with using singletons, which is kinda sad.
- Passing pointers around to the pools and other stuffs, which is even worse than the singleton way and make it a nightmare to refactor anything.

Or: Have a few pointers that refer to high level objects, e.g. Scene / World / Level.

And/or: Use sub-systems and link them beforehand.

And/or: Store the commands in command queues and let the belonging sub-systems do their job when they are processed in the course of the game loop anyway.


I will probably have 1 for buildings, 1 for units, 1 for Images (to don't read the same images over and over again just because i have 10 units from the same type)

What are you doing exactly? From a game's point of view your answer makes me think that you are mixing up resources and scene objects. There is a difference between game objects that populate the scenery and resources that work as templates for game objects and/or storage for reusable, well, resources.

#5226925 Adding non ECS features in an ECS engine (tilemap)?

Posted by on 03 May 2015 - 03:55 AM

Fact is that OOP does not provide inheritance alone, but also composing. While the former allows for a kind of specialization / generalization thing, the latter allows for a kind of collaboration thing. ECS was an attempt to make the OOP object level composing an architectural pattern especially with the background of game development (later on "sub-systems", cache friendliness and so on are added). It is a fuss since the game industry has determined this way of doing things, although composing as mechanism exists since the dawn of OOP at all. It should be mentioned that, following the relevant literature, composing was mentioned to be generally preferred over inheritance years before Dungeon Siege. That said, even if you do not use an ECS, the basic principle of it should still be considered. (And: ECS is not the opposite of OOP.)


On the other hand, ECS is a tool like others. Do not use a tool if it does not fit the problem. Not all stuff in a game fits in it, that's for sure. Terrain, sky, foliage, … do not fit. The conclusion is simple: Do not try to make them fit, and hence do not base the entire engine on it. Your doubts mentioned in the OP are absolutely valid.


To overcome your problem, use systems as a hierarchy of services. Each more lower layer in the hierarchy provides more basic services and uses more general structures. Even rendering is not a single layer but consists of several layers. At the bottom there is the graphics layer dealing with triangles and textures (if done this way). Above it there may be a "sprite layer". Above it there may be … At the top, not counting to rendering at all, is the scene layer which deals with terrain / ground, sky, game objects / entities. Notice please that layers in this sense are by all means possibly a couple of sub-systems. Sub-systems may collaborate with other ones on the same layer, and may use sub-systems of lower layers.


That said, during rendering, terrain / ground will be converted to some kind of graphic primitives by some rendering layer(s) along a path from the scene layer down to the graphics layer. Game objects / entities will be converted also to some kind of graphic primitives, not necessarily the same primitives, and probably not along the same path as terrain / ground. If "sprite" is your graphic primitive of choice for both ground and entities, then you will have a ground renderer and an entity renderer in the end, the first using a ground representation as input and the latter using game objects as input, and both yielding in sprites as output.


So, question is to which layer(s) do Game::render and RenderSystem::update belong to? Both possible solutions shown in the OP violate a clear abstraction. First of, usually "update(time)" is used to, well, drive the update of the world state. It has nothing to do with rendering, and hence should not call a renderer, and RenderSystem::update(time) should not exists as such. Instead, after the world has been updated properly, the renderer can use the world state to just draw it.


Coming back to the problem: Game::render seems to be the top layer of rendering, so it should work on the level of scene objects (hence iterating the ground tile by tile is a no-go there). It may iterate all drawables in the scene and invoke their render() method. That render() methods will be the second layer of rendering and perhaps already output the sprite primitives.


All the above: My 2 cents, of course ;) 

#5226810 Animate a polygon

Posted by on 02 May 2015 - 01:59 AM

What is at least wrong inside circle.java is that the variable angle is initialized to zero and then counted up to 360 within drawCircle, but it is never reset to zero. So the condition

while(angle <= 360.0)

will inhibit the generation of a second set of vertices. You want to use a for loop instead of a while loop here, because a for loop is useable to reset angle each time the loop is entered.


BTW: A principle issue you have here is that variables like angle, s and c should be local variables in the scope of the routine drawCircle, because they are used just for the inner workings of that routine. Besides that, short names like s and c may be used for loop variables (often i, j, or n are used for that), but they should never be used as member variables. Instead use expressive names.