Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 07 Nov 2010
Offline Last Active Today, 01:00 AM

Posts I've Made

In Topic: An alternative to the Sponza mesh for demos?

Yesterday, 10:26 AM

My personal favorite is a San Miguel scene that I've seen used a few times. A bunch of really nice ones are listed here: http://graphics.cs.williams.edu/data/meshes.xml

In Topic: Delaunay Traingulation

Yesterday, 09:38 AM


Now I'm struggling to produce a Delaunay Traingulation.  I'm trying to make my initial set of triangles by adding points randomly to the grid.  If the point is inside of the triangle, then the triangle splits into three smaller triangles.  If it is outside of another triangle then it finds the two nearest points and makes a new triangle with them.


This is not working at all. 


I'm not sure what's wrong with this, because this is completely correct, at least to create an arbitrary triangulation. You don't need to know baycentric coordinates to make it work, though. If your triangles are in counter-clockwise winding, a triangle with verts A, B, and C would be split as such: http://i.imgur.com/PNNEtkf.png




I've seen this concept of edge flipping in my travels.  I haven't been able to wrap my head around it well enough to turn it into code. Do you have a simplish explanation for what is going on?



Sure, I'll take a whack at it.


There are many ways to triangulate a set of points. Delaunay triangulation is a specific type of triangulation that seeks to maximize the minimum angle of each triangle, to avoid skinny triangles. Now, this doesn't necessarily mean that it's the correct or the only way of avoiding skinny triangles, it's just one method. See here for a more complete list of different ways to create optimal triangulations: http://en.wikipedia.org/wiki/Point_set_triangulation#Time_complexity_of_various_algorithms


So, in an effort to maximize the minimum angle, and taking advantage of the Delaunay property of circles, the easiest way to go about turning a random triangulation into a Delaunay one is to compare and correct adjacent triangles together. Something like:

for every pair of adjacent triangles
    if they aren't delaunay
        make them delaunay

, which is actually really nice. Not many other triangulation methods that I know of become correct just by correcting triangles piecewise like this.


The "make delaunay" step is the key here. It just so happens that the easiest way to make a non-Delaunay pair of adjacent triangles correct again is to turn the exterior vertices into interior vertices and vice versa


Hope that helped a little!

In Topic: Delaunay Traingulation

Yesterday, 02:01 AM

Just a quick question, do you want a Delaunay Triangulation, like your title suggests, or do you want a Voronoi mesh, like your post suggests? If you're calculating a Voronoi with the end goal of turning it into a Delaunay, then there are far easier ways to do it.


The only issue with your Voronoi algorithm is that your first step essentially requires you to make a Delaunay triangulation. Keep in mind that just because you can find create an arbitrary triangulation over a set of points doesn't mean that you are creating the inverse of the corresponding Voronoi diagram, which is what you need. Everything else about it seems like it should do the trick.


Fortunately, you can construct a Delaunay very easily by:

1) creating an arbitrary triangulation. There are many ways to do this, but the easiest way is to append and subdivide triangles as you add points to the triangulation. I can elaborate on that if you need.

2) edge flip 'till you can't flip no more ( http://en.wikipedia.org/wiki/Delaunay_triangulation#Visual_Delaunay_definition:_Flipping )


Hope this helps! smile.png

In Topic: Understanding function for generating sphere ...

17 February 2015 - 01:29 AM

Read up on Spherical Coordinates: http://mathworld.wolfram.com/SphericalCoordinates.html


Specifically pay attention to the part where it talks about decomposing spherical angles to euclidean coordinates:






, and keep in mind that axises my be flipped, or might be viewed in a different frames of reference.


As for the p variable, notice that theta2 - theta1 = (M_PI*2)/p, or, in degrees, 360/p. So the variable p has to do with the number of slices around the sphere you make to generate a soup of flat polygons


Also, for the normals, notice that the surface normal of a sphere is exactly the position of the sphere, without taking into account any radius scaling or translation


Hope that sorta helped!


EDIT: text editor decided half my post didn't exist tongue.png

In Topic: Tech/Game Dev Blog?

11 February 2015 - 11:03 AM

GameDev.net has a Journals section. A lot of members post there pretty often and use it as a dev blog and ranting blog of sorts. It even has an RSS feed! :D