Polygon Triangulator!!

For my 3D games, I've been playing around with ideas around semi-procedural geometry, by which I mean geometry which is generated from a small amount of authored data.  For example, I could draw out the shape of an island in a dozen or so 3D points, and the actual terrain geometry could be generated from that.

A big step along the way to that is splitting up a non-convex polygon into triangles.  The triangles mustn't overlap, nor must they cover any space which the polygon itself doesn't cover.  For example, this diagram.

Today, I managed to get a python program* running which took a list of 2D points defining a polygon, split it into sub-triangles and displayed them in a tkinter canvas**.

I am certain this has been solved by clever people in much better ways, but I still feel proud to have figured this one out (and I haven't managed to break it yet!).

The basic algorithm is:

  • Create a temporary copy of the polygon points list
  • start with the three points from the beginning of the list e.g. [0,1,2]
  • can I make a valid triangle with these points?
    • Is the winding correct? (this stops me generating triangles which would be outside the polygon)
    • If so, are any other polygon points within this triangle? (this stops me generating triangles which overlap)
    • If there aren't any points inside it, go ahead and make the triangle!
  • If I made a triangle, remove the point which is no longer necessary from the list (essentially, making the polygon smaller by that one triangle)
  • If I did not make a triangle, take the three points starting at the next one along (e.g. [1,2,3]) 
  • Try to make the next triangle (in the smaller poly, or from the next set of points)!
  • Keep going until there are only three points left
  • Make the final triangle
  • et voilà!

I think my next step will be to make the program produce a polygon graph (with edge and adjacency information) so I can do the edge-flipping to make it a valid DeLaunay triangulation (which will have much more nicely shaped triangles).

Or I might write a Unity version of this before I do the DeLaunay stuff.

Anyways - I feel like this is a big step forward! :D

* why python?  Well, because it was there - I was only playing after all.
** why tkinter?  I know it sucks so badly, but again, it was there and I knew how to use it quickly.


Comments

Post a Comment

Popular posts from this blog

Micro:Bit and SPI display

I want to explore the full potential of the BBC Micro:bits my school has. Making rock-paper-scissors games and the like is all well and good, and the students love it (for the most part), but it always feels a little bit gimmicky.  But when students really get engaged and suggest ideas for them (e.g. games, compass display), it all gets a little bit cramped and feels like it could  kinda  work, but not really . Then I found out that all the tiny strips on the edge are actually GPIO pins, not just the fat 0, 1 and 2 ones.  Since then, I've wanted to explore what I can do with it. Hence, over the last few days I have been trying to get the microbit to control a TFT display. I first went for this 2.4" display with a touchscreen.  The SPI interface is just for the microSD, not for the screen but I didn't think that would be a problem because the micro:bit has so many pins.  After much frustration, I discovered that there are many of the pins you can't reliably use extern
Read more

DCS World with TrackIR under Ubuntu

This is a record of my experience of setting this up.  It's meant more as a record for my future self than a tutorial, but maybe somebody will find it useful. 1 - Install DCS First step, install DCS World via the Steam client as normal.  2 - Install LinuxTrack Linuxtrack Download here: https://github.com/uglyDwarf/linuxtrack/wiki/Downloads   Instructions here: https://github.com/uglyDwarf/linuxtrack/wiki/universal-Linuxtrack-package   Using the gui (ltr_gui) requires qt4 libraries, which I could not find in my standard Ubuntu repositories, so I had to use the ppa instructions here: https://ubuntuhandbook.org/index.php/2020/07/install-qt4-ubuntu-20-04 Run ltr_gui from linuxtrack's bin directory to check everything works so far before moving on to get it running under Proton.  3 - Install LinuxTrack into the DCS World prefix NOTE: Attempting to install for Wine games WON'T WORK e.g. here https://github-wiki-see.page/m/uglyDwarf/linuxtrack/wiki/Wine-Games   This is because Ste
Read more

Cardboard Mock-up of USB Joystick

Image
For years now (literally years ), I have been playing around with the idea of making a USB joystick.  You may have seen my previous experiment in building a throttle control . I wanted to use a similar idea to the throttle, taking the angular motion of the handle and magnify it when applying it to the potentiometer.  e.g. move the handle through 45 degrees and the potentiometer gets moved through 90 degrees. I also wanted it anchored at the rear, so I can build a mount to attach it to my computer chair. In the video you can see a cardboard mock-up I made today.  I'm amazed it worked at all, but it even provides a solid foundation for designing the proper plywood one. The process of making a cardboard mock-up was really useful.  There were three fatal flaws in my sketch design which I would not have found out until I tried to make it: Pushing the joystick left/right when it was already pulled full back makes it catch on the rear support. The internal supports in the
Read more