Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 10 Oct 2005
Offline Last Active Today, 12:49 AM

#5228150 Get the distance of an intersection

Posted by haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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 haegarr 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.

#5223007 Alternatives to global variables / passing down references through deep "...

Posted by haegarr on 13 April 2015 - 02:06 PM

Let's make sure we are talking about the same things here, could you explain what exactly you mean by layers and levels, up and down?
The way I see it is, a layer is a scope, like the function body of main() or the scope of a class like GameState. Up is main() and down is something like statemanager.gamestate.level.player, right?
So if the Player wants to be drawn, it should not interact with the Renderer but instead the Renderer should "collect" all Renderables "below" it, or the class that owns Renderer should feed the renderer the Sprites/Renderables?

Well, let me give an example where several sub-systems are mentioned.


The player manipulates its input device, so input is generated. The Input sub-system fetches the raw input, preprocesses / prepares it and stores it into the game's input queue. Notice that the Input sub-system does not call any other sub-system. Somewhere at the beginning of the game loop the PlayerController looks into the input queue and determines whether current input situation matches one or more of its configurations. Notice that this can be understood so that the PlayerController accesses a service of the Input sub-system, namely its input queue, so a higher level system (PlayerController) utilizes a lower level system (Input).


Let's say that the PlayerController determines an input situation and hence generates / updates a motion data structure for "intention for forward walking". Notice that such intentions may also origin from another sub-system, namely AI for NPCs. The difference is that AI usually outputs such intention like "move to location X". However, both these are examples of all possible intentions that address the Movement sub-system. When that sub-system runs its update, it investigates the intentions and checks whether they are "physically" possible. If not then the intention is cleared and ignored. Notice that the lower level sub-system (Movement) does not communicate directly with a higher level one (PlayerController or AI), instead perhaps replying to AI by canceling an intention.


The Movement sub-system updates the movement structure to reflect the new intention (assuming that it has passed the possibility check). It updates the belonging placement data structure accordingly to the current motion.


Later in the game loop the animation sub-system is updated. It iterates the animated sprites and adapts their drawable, i.e. determines the valid slice from the texture and such.


Later on in the game loop, (visual) rendering is invoked. The upper layer of rendering investigates all sprites (notice: no distinction to PC, NPC, or whatever) and does visibility culling. Any sprite that passes is enqueued into a rendering queue, not as sprite but as drawable (this rect, this texture, this texture rect; something like that). Then the lower layer renderer is invoked. This is the renderer that actually knows about D3D, OpenGL, or whatever. It iterates the queue of drawables and generates graphic API calls from it. Notice that the lower layer of rendering is fed with low level data (close to meshes and textures) which also is ready to use (placed where needed, animated if necessary, and so on). Again no need for it to communicate with any higher sub-system.

#5222892 Alternatives to global variables / passing down references through deep "...

Posted by haegarr on 13 April 2015 - 02:34 AM

The best approach is to avoid dependencies, but obviously that can be done only within limits. In the end ever pieces of software work together to implement a solver for a problem. So in reality one simply tries to get closer to the minimum of dependencies, and to make the dependencies explicit.


A first step is to define modules, each one with a well defined API by which clients can call the services of the module. A module need not be a single object, but it can be beneficial if the API is provided by a single object (see e.g. the facade pattern, to some extent also the strategy pattern). The usual name for such modules is "sub-system" here in the forums.  The code snippets in the OP show that such modularization seems to be used.


Now if enough sub-systems are available, the problem of disorganization appears again. This can be lowered by using a layered architecture. Sub-systems collaborate with sub-systems in the same layer, they utilize sub-systems of the next lower layer, but they MUST NOT call sub-systems of upper layers (although they MAY respond to them), and they SHOULD NOT utilize sub-systems from the layer after next. Of course, in reality this is more a rule thumb than a strict law.


So far, the above gives a kind of top level organization, but it does not actually solve OP's problem. However, it gives a hint to us: When a lower level sub-system MUST NOT call a higher level one, then the lower level sub-system also has no clue what kind of structures the higher levels are using. That means that top down communication should be done with data structures belonging to the lower levels. 


The next thought is about the game loop. The game loop is actually a sequence of update calls on high level sub-systems. It is sequential, because we want clear and stable (as far as possible) world states (i.e. not an oscillation between particular sub-systems, so that the frame is delayed unpredictably!). Also from an efficiency point of view, it is beneficial to run a particular update step on all entities before passing on to the next kind of step.


So in such a scenario we actually have a sub-system (on the game loop level) that runs an update on all of its active entities, and for each prepares a data structure for passing the updated data, and … that's it. Because all interested sub-systems using that same pool of data structures, they already know where to find it. Of course, such a high level sub-system will utilize other sub-systems and this may mean to pass pointers around, also often only at initialization time. But the amount of pointers in each particular case is low, especially since you couple sub-systems instead of (data) objects.