Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 24 Apr 2008
Offline Last Active Jul 14 2014 09:09 AM

Topics I've Started

Calculating the polygon outline from the set of overlapping polygons

17 June 2014 - 09:55 AM

Hello all. I am working on pathfinding and I am using navigation meshes. I am using A* and have it working. However, as I'm sure most of you know, there's a 'jagged-ness' to the calculated path. I am using the vertices of the various navigation meshes to calculate my path (hence, for me, the jagged-ness). Now the beauty of navigation meshes so that any point on a nav mesh to reachable to any other point on the same nav mesh. So I am trying to put two and two together by using raycasting/line-of-sight/whatever to smooth out my path.


I don't know how.


My current plan is to post process my calculated path to make it smoother. This will be done by taking the starting point and checking if it has a line-of-sight to the goal, if not check if the starting point has a LoS to the point before the goal and so on. When a LoS is found a path from the start to the point is created, and the process starts again with the found point being the new 'starting point'. Sounds good, but I have a problem with the line-of-sight part.


I don't know how.


My current plan (regarding the LoS issue) is to calculate a polygon 'outline' that covers the navigation meshes (IE: I'm taking several (overlapping/connected) polygons and 'adding' them together so any overlapping parts are removed and I have a single silhouette polygon). Once I have that, I can simply check if a ray from point-to-point crosses said polygon's edge, if it does then there's no LoS. Of course, I have a problem calculating the outline polygon.


I don't know how.


So my question is: How do I calculate the polygon outline from set of overlapping/connected polygons?

Or, perhaps even, is this dumb and is there a better way to do this?

Determining if a 3D point is in a 3D polygon

04 June 2014 - 03:26 PM

Hey guys, I need help in determining if a point is in a polygon (in 3D).


I found this: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html, which works great in 2D. But now I'm expanding into 3D and this method no longer works. When I Google, all i find is how to do this in 2D (such as winding numbers, or edge counting) but nothing for 3D.


Ideally, I would like an explanation of the solution with pesudo code solving the problem. This way I can understand what is going on and can confirm that I know what is going on by programing it and having it work.

Entity Component System questions/tips

25 March 2014 - 02:52 PM

Hey guys, I've been doing a lot of reading on Entity Component Systems and I figured I'd give it a go. I have a basic design layout and I was hoping to get some feedback, both to help out a beginer with this new design implementation and to so I can see people's thought processes.


Here's what I've come up with (sorry, no code right now):




  • Just a Universally Unique ID (UUID).
  • Since an entity is a UUID, this will be implemented within an entity manager (see below).


Entity Manager:

  • Manages entity creation and removal.
  • Entities are stored in an array (maybe, this seems redunant as the UUID will act the array index but I will need someway to store created entities, right?).


  • Each entity has it's own creation method where an entity is created and components are created and assigned to the newly created enity. This is so it's a simple function call to create as many tanks, jets, unicorns, sharks with freaking lazer beams, etc as desired.
  • This means the entity manager will be keeping track of components and whom they belong to. To keep it fast and simple, I figure an array for each component where the entity's UUID can index into said array(s) to get it's components. This way systems can simply iterate over the array(s) it needs and to make use of pre-fetching and caches.


  • Entity removal will cause the UUID to be thrown into a list of some sort so that it can be recycled (on entity creation). This will prevent the UUID from becoming impossibly large should a large number of entities be created then destroyed.



  • Data only.
  • A list of components is held by the entity manager (see above).



  • One system per aspect (physics, AI, etc). These are independed of each other so it should be trival to put them in different threads if desired.


System manager:

  • Primary use is to be a black box to hide the data structure containing the systems (array, vector, linked list, who knows).
  • This will also make it easy to have each system in a thread (if desired), in the add method just start a thread for the system, or add it to a data structure that is iterated over every frame, or whatever).
  • To keep it simple and easy for now, it'll be a vector.


  • This can also provide a way to prioritize systems, pause systems or outright remove them (though I'm thinking this is probably a stupid idea; I can't really think when I'd want to remove a system outright or even to just pause it).


  • I'm not even sure If need this. It's a 'nice-to-have' in that it helps seperate world functionality (see below) from system specific functionality. But this could be my OOP background nagging me.



  • There's only one world so this will be an object (as in OOP).
  • Will contain an entity manager and system manager.
  • Will have methods to load & save the world.
  • Will contain the main loop.
  • Will behave as everyone elses world object (I'm sure).




I think this is a pretty decent design (to start with) but I'm curious as to what you guys think. After all I could be heading toward a world of hurt and not realize it or be on my way.


I do have one question though. My entity manager contains the list of components used by the entities. This is because I would like to go EntityManager.tank(...), EntityManager.SharkWithFreakingLaserBeams(...), etc rather than manually type: create entity; create componenets; assign components to entity; each time I want to create something (the only difference is what components are created because it depends on the entity, so why not automate it?). However, this leaves me in a bit of a pickle for systems. Since they are two are seperated objects, the system manager does not have access to the list of componenets that it needs to iterate over and do its thing.


What would be considered the best idea to solve this (yes, I know there's a hundred different ways I can solve it). I'm thinking of something like:

  • The entity manager has a 'get components' function(s).
  • The components are fed into the system manager's update function.
  • Each system takes the components it needs to work on and iterates though them, doing it's thing.

That's probably the easiest solution I have, for the design I have; but I don't think it's upgradable. IE: What if I want to change the system manager from a data structure to a thread creation implementation. Ideally I can simply make the change in the add/remove methods of the system manager, but now the solution to give the system manager the list of components goes out the window since the system manager no longer has an update function (each system is in it's own thread so it'll be best to let it deteremine when it needs to update since some systems will be likely to run at different times. EG: render all the time, update at the frame rate).

How to fit a box in the camera's view frustum

31 January 2013 - 05:09 PM

Hey guys, I'm having a problem with some basic math for a basic concept.



I have a rectanglar box in my scene and I want to distance the camera such that the box just fits.



So right now I have my camera set up so that I can select a heading and an elevation. The software then calculates the camera's position using that data as if the camera is connected to a piece of string attached to the middle of the cube, tethering it to a spherical area. EG: I give it a heading of 45 degress and an elevation of 30 degrees, the camera is positioned 'Southwest' of the cube so it's looking 'Northeast' (45 degrees) and has an elevation of 30 degrees from the ground. If I give it a heading of 180 and an elevation of 90, the top of the screen is 'South' and the camera is directly above the box. (The x-axis is East/West, the y-axis is North/South). Now I'm trying to figure out to calculate the distance the camera needs to be so the box fills the screen. I know how to calculate the distance the camera needs to be so that no matter how the cube is rotated it fits (distance = boundRadius / sin(FOV / 2)). The problem with this is that the box is a wide, narrow rectangle, with little depth so using this method the box fills the screen only at a specific heading and elevation, otherwise there is a lot of empty space.


Current idea:

Since, ultimately, there's no difference between positioning the camera and rotating the mesh, I can think of the camera as being stationary and the mesh is being rotated so it's displayed with the correct heading and elevation. I was thinking that if I calculate the width and height of the box after it's rotated I can use trigonometry to calculate the distance (distance = halfWidth / tan(FOV / 2)). (If there's an easier/better idea, by all means, please let me know). I know how to calculate a 2D square's height and width after a 1D rotation, but I don't know how to calculate a 3D box's height and width after a 2D rotation.


What I know:

The box's height, width and depth; the camera's field of view, elevation (IE: x-axis rotation) and heading (IE: z-axis rotation).

Maya 2010 move tool problem

16 February 2011 - 12:33 AM

I've ran into an odd problem. When I try to translate (move) any part of a mesh (vertex, face, edge, etc; other than as a whole (IE: NOT in object mode)) along the X-axis, it scales the parts rather than moving them. If I'm in object mode or moving along the Y or Z-axis, I can move the mesh or its parts just fine. I've tried restarting Maya, my computer and just making a new scene; but the problem persists, leading me to think I've accidentally changed a setting somewhere. I spent about 2 hours searching the Autodesk website and Google but I haven't found anything to help me fix this.

I figured it out, under the move tool options; I somehow enabled the 'reflection' property (which actually makes sense in hindsight). That'll teach me to stay up till 2 in the morning :)