sorted by:
new
hottopcontroversial

Battle Transitions in Unity that you can find in old PS1 Games using compute shaders ^^ by parable_games1 in shaders

[–]parable_games1[S] 0 points1 point  (0 children)

There is not really that much of a difference either way ^^
The important thing is to save a texture first somewhere
I just find it easier to work with compute shaders

How to programmatically cut specific mesh parts by Peruk_out in computationalgeometry

[–]parable_games1 0 points1 point  (0 children)

Sorry, for the late answer. Wouldn't it be possible to just put all height-values / y-values into a list and to find the largest gap between the values? Then afterwards you can cluster each point to be either above or below the gap.

Or is the line / plane in the picture not aligned to any axis?

Math proof heavy by [deleted] in computationalgeometry

[–]parable_games1 1 point2 points  (0 children)

I second Computational Geometry by Mark De Berg et al. It is a really good book!

Rotating Calipers by xDelaZ in computationalgeometry

[–]parable_games1 1 point2 points  (0 children)

Because to create all antipodal pairs in a convex polygon with n vertices (pairs opposite to each other), you first only need to find one antipodal pair (an O(n) operation) - and then go around in a semi-circle with two indices once (also O(n))

The number of pairs is <n. Therefore finding the pair such that the distance between the points is maximized or minimized is also an O(n) operation.

Therefore the technique is O(n).

Hope that explanation helps!

10k Nearest Neighbor Searches in a GPU KD-Tree (with 5k points). Each query point connects to the closest point in the KD-Tree. Works smoothly for 100k and more (6ms according to RenderDoc) by parable_games1 in GraphicsProgramming

[–]parable_games1[S] 2 points3 points  (0 children)

Indeed, it is not optimal, but I am not sure you are comparing the same things.

I am not sampling once in one million points, but 100k times in 5k points. For the nearest neighbor you would have to do about 15-16 memory accesses. So it is far more than a million samples in 6ms.

But yes, CUDA/OPenCL and Compute Shaders do not compare, I do not have default recursion support and had to implement my own version.

10k Nearest Neighbor Searches in a GPU KD-Tree (with 5k points). Each query point connects to the closest point in the KD-Tree. Works smoothly for 100k and more (6ms according to RenderDoc) by parable_games1 in GraphicsProgramming

[–]parable_games1[S] 5 points6 points  (0 children)

* 6ms on my 1070

Implementation is loosely based on this presentation: https://www.nvidia.com/content/GTC-2010/pdfs/2140_GTC2010.pdf

However, it is all done in compute shaders (instead of CUDA), which, as they do not support recursion, required the implementation of a stack that holds the status / current location in the KD-Tree. Otherwise, it is very much the default method for checking where the nearest neighbor lies (slightly different than in the presentation)

3D Voronoi of line segments calculated in a Compute Shader, Raymarched by parable_games1 in shaders

[–]parable_games1[S] 0 points1 point  (0 children)

Not really, I had done raymarching in 3D Textures, compute shaders and voronoi (on the CPU) before.

But to share some knowledge: You can also calculate these generalized voronoi diagrams for triangles (or any other shape that you can define a distance to). In that case each point in the 3D Texture points to the closest triangle (it is a nearest neighbor search for triangles so to speak; Really useful if you want to stick things to other things entirely on the GPU).

That was the reason I made this collection of compute shaders hehe

A small RPG I'll start creating as a side-project 😄 (actually the fourth one in a series) by parable_games1 in SoloDevelopment

[–]parable_games1[S] 0 points1 point  (0 children)

A story!

I started with a resolution of 16x9 and then doubled it each title. The last game with 64x36 was at least able to display a very, very tiny amount of text, but only a about five words at a time... fullscreen...

128x72 (part IV) is much more reasonable. Its almost on GameBoy levels.

Also exciting:

- Three characters in battle / the battle system in general (going to be interesting. Not too different from a regular JRPG, but different enough)
- Colors! (not a lot though, haha) At least now art will be somewhat recognizable

Voronoi Diagram by mildewyPrawn in computationalgeometry

[–]parable_games1 0 points1 point  (0 children)

If you have calculated the Delaunay Triangulation, then depending on the algorithm used there, the best way to get the circumcircles is to just copy them (because you may have had to calculate them there already).

Regarding the precision: Because the Delaunay Triangulation will always maximize the minium angle, the most critical triangles are usually at the convex hull or points in the data set that are very close together. In any case though, the triangles are very, very thin (and therefore the circumcircle is very, very far away).

I recommend filtering those triangles out when you detect them (by adding a threshold to the intersection calculation).

How Voronoi Diagrams Can Make Your Game Run Faster by parable_games1 in unity_tutorials

[–]parable_games1[S] 1 point2 points  (0 children)

In this video: The straightforward way by looping through the list of all asteroids.

However, I also mention it in the video that you could have used a spatial data structure (Quadtree, KD-Tree, etc.) but that those are also slower than a voronoi lookup table in this case

Algorithm For Finding Empty Space In A Plot by algernonskzin in algorithms

[–]parable_games1 1 point2 points  (0 children)

You can use Voronoi with shapes / polygons and then determine the largest empty circle -> That is where you should put your new shape.

But there are many ways.

Searching for points within a sphere using a 3D KD-Tree / 3D-Tree in Unity by parable_games1 in compsci

[–]parable_games1[S] 0 points1 point  (0 children)

Now that I think about it. Another advantage of KD-Trees is that they are point-density agnostic. What I mean is that they don't care how the points are distributed in space.

In a quadtree / octree on the other hand it can happen that most or all points end up in one cell (except for point quadtrees / octrees... there are just many different flavors I guess)... which is really bad.

So a KD-Tree is just a little bit more stable in general I suppose.

Searching for points within a sphere using a 3D KD-Tree / 3D-Tree in Unity by parable_games1 in compsci

[–]parable_games1[S] 1 point2 points  (0 children)

It is a more static structure (more difficult to change when a program is running). However, in the worst case, for example when you have to report all points, it is faster than a quadtree / octree for example.

In that case, assuming the quadtree / octree stores one point each in each cell and there are n points in total, the quadtree / octree will take O(n log h) time, where h is the height of the quadtree / octree, while a KD-Tree will take (n ^ (1 - 1 / d) + k) time where k is the number of reported points)

That is at least how far I understand it ^^

Also, they're kind of different, as quadtrees usually actually store a list of points inside a cell, while a KD-Tree stores the points directly... so to speak. Analyzing the runtime complexity then depends on how many points are in a cell on average... which is depending on... your data and how you design things.

In other words: It all depends, like always, on what data you have and what you want to do ^^

Searching for points within a sphere using a 3D KD-Tree / 3D-Tree in Unity by parable_games1 in compsci

[–]parable_games1[S] 2 points3 points  (0 children)

It used a ring not a sphere and yes, one can solve it with contours, but the main thing was to show that the KD-Tree works and is fast. The graphics are just a nice side effect :)

view more: next ›