Tag Info

Hot answers tagged

27

This is caused in the history. Early computers had Cathode Ray Tubes (CRTs) which "draw" the image with a cathode ray from the upper left corner to the lower right. To ease the interface between the graphics card memory and the CRT the memory was read from the beginning and the image was drawn from the top left (with the lowest memory address) to the lower ...


10

Have you actually tried a hierarchical graph and measured the performance? Have you investigated simple physics engines to see how they handle the problem, even a 2D engine that has linkage between objects would help guide you in a proven direction. I would not try to run your physics in multiple spaces, the complexity would be daunting. Run the physics ...


7

That is a neat demo. The best reference for Delaunay triangulations and Voronoi diagrams that I've found is Jonathan Shewchuk's book and lecture notes. The book is significantly more advanced than the lecture notes, and talks more about mesh refinement. I suggest you start with the lecture notes. Do you need to go to grad school to generate a Delaunay ...


7

When traversing the graph, always turn the same direction. You can use cross product to check what is the left or rightmost direction in a junction.


5

A* doesn't really care about the shape of the graph you're using. Let's see the pseudocode for A*, stolen from Wikipedia: function A*(start,goal) closedset := the empty set // The set of nodes already evaluated. openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node came_from := the empty map ...


5

You may not want to use a graph, but ultimately the problem is one of planar 6-connectedness. I challenge you to find a simpler and better-suited structure than a graph for this :) I wouldn't be intimidated by the data structure for this -- when you consider how trivial the implementation will be, it's not like you'd be writing Boost Graph Library all over ...


4

Keeping things simple I don't know the exact context of your problem, but I give below the most accurate solution possible given the specific question you've asked. However, if you want to keep things simple, it is better to construct the graph yourself. In that way, there is no need for you to identify subgraphs, since in creating them within a larger ...


3

Force-directed graphs may be use to create a planar graph embedding in which there are no crossings and each individual node is a reasonable distance (depending on your definition thereof) from each of the others. However there is more to this than meets the eye. A planar embedding is distinct from the concept of a planar graph. A planar embedding is simply ...


3

Use the tween engine. (tweening) It is very powerful and easy to use. You can create animations for any atribute, timelines with simultaneous and/or sequencial animations, and assign callbacks for starting, ending, looping, etc.


3

Perhaps I´m over thinking it. Yes, you are. Transformation being done in shaders is meant to be literal. "Transformation" in this case being the application of some transform to the various per-vertex attributes. Where that particular transformation comes from is generally irrelevant to the shader. It is given a transformation, and it applies it to the ...


2

Finding connectivity in a general graph is usually done with floodfill-style algorithms (i.e., breadth- or depth- first search and variants thereof) anyway, so I don't think that abstracting out the process in the way you're describing is actually any great help. Instead I would maintain the core data structure in a grid; there are very standard approaches ...


2

Using a simple 2D array works. Then you don't have to walk a graph to get somewhere. Deciding what should fall next is as easy iterating up the current "column" of the array you're in. You can easily step into the grid anywhere with the x/y coordinates and do your collision detection or whatever you need to. That means you can get neighbors in constant ...


2

Model, View and Projection matrices are passed as uniforms to the vertex shader, which uses them to transform vertex coordinates and normals. Typically projection matrix is constant between frames, view matrix is calculated once per frame and model matrix is unique for each object. Model matrix is in world space. This is of course not the only way to do ...


1

This is a great question that I've thought of many times. The simple answer to "why" is because TV formats also drew their lines from left-to-right then top-to-bottom. Original computer monitors were CRT screens (small TVs), so the format naturally stayed the same. When monitors became flat screens (and TVs became flat screens too), it was equally natural to ...


1

The only algorithm I've found for solving this problem is the constrained Delaunay triangulation algorithm discovered by Paul Chew (http://www.cmlab.csie.ntu.edu.tw/~plokm/htdocs/cmlab/%B1M%C3D/triangulate/Constrained%20Delaunay%20Triangulations.pdf ). As in the case of the classical Delaunay triangulation, the complexity is still O(n log n), which is ...


1

This took some figuring out for myself, but I've got one for you. Note that in the if statement we have no changes to path (since nothing is removed from it). Now edge2 is changed it it's next every iteration, removing the need of the else statement. I added nextEdge1Spot to avoid checking whether an edge has been deleted or not. public static ...


1

Your code only makes a single test with edge1 before advancing. This skips over certain nodes that are in a straight line. For example, if you have 5 points (A->B->C->D->E) all in a straight. The smoothed path should only contain two points (A->E). In your logic you test if you can travel between A->C and if you can then B is eliminated. You then check ...


1

You can create an algorithm based of edge intersection. The idea is to draw a line between the two points called a ray. This then acts as a line to test whether the polygons lines intersect. You can do this in pseudo-code: // Method in point: bool IsPointBehindPolygon( testPoint, polygon) { originPoint = this; ray = new Line(originPoint, ...


1

Here's the algorithm I see happening in your question: (I use "inside" meaning specifically not ON the cut line but only inside it) P = Plane To Cut Across. For every edge in the graph as Line A->B { A_inside = Is point A inside plane P? if (point B is on line P && !A_inside) return nothing; B_inside = Is point B inside plane P? ...


1

I have been in the same situation as you and this is how I solved it. Before that, some clarification: In my SceneGraph each SceneNode keeps track of its own local transform (scale, rotation, translation) and a concatenated transform (world). SceneNodes can have multiple components. BEPUPhysics is the physics library being used, its entity transforms are ...


1

You are approaching the problem from the wrong side. You don't have a scene graph and need to integrate physic engine. You are using a rendering library that uses a scene graph and want to also use a physics library that does not use a scene graph. How about you step one step back and stop thinking about the solution domain (scene graph) and start thinking ...


1

The following simple algorithm should give you O(E) solution: Create a directed graph from your graph by adding arcs to both directions for each edge in your initial graph Start traversing the graph from any node with the current logic of always turning to the same direction in junctions Only proceed through arcs that are directed away from the node Remove ...


1

I have to solve a few basic graph problems: find strongly connected components, find best traversal, etc. Quickgraph is the sort of library I'm looking for but the binaries don't work with mono/unity, I'm willing to try compiling it myself but if there's a better option out there I'd much rather start with that. ~ From the Unity forums Suggestions ...


1

You're essentially looking for short interior paths. I'm assuming that you have a planar embedding of your graph and can determine the circumference. An interior path is a path between nodes that doesn't contain edges on the circumference. The short paths you're looking for have the following properties: They're between two nodes that are both on the ...


1

Perhaps you should look at "The Visibility Skeleton: A Powerful And Efficient Multi-Purpose Global Visibility Tool," Durand et al., a 1997 paper that Google Scholar shows has been cited 148 times since. The question you pose has been heavily studied! One of the key search phrases is walkthrough.


1

I don't believe that's possible in the general case. You can easily imagine a graph where your source node has only a single connection to the rest of the graph. If that edge changes, the weight of every path from the source will change (although not the paths themselves). There are other pathological cases you can imagine where even a single edge change ...


1

As far as a direct answer, all I have off the top of my head is: A* might help if you can make a good heuristic. Other ideas: You might be able to do full recalculation over multiple frames (or in a thread). Or maybe try representing your search space in a way that you can use progressive refinement; for example, a quadtree where you can perform a search ...


1

Not an answer but might this help? http://www.lix.polytechnique.fr/~liberti/sppsurvey.pdf Also, a general tip - maybe you already know. If you know of a paper related to the problem, checking CiteCeer to see if there are papers referencing it, you might find your way to an answer (or not, but always interesting papers on your travels). ...



Only top voted, non community-wiki answers of a minimum length are eligible