Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Uniform distribution of points in a 3D Tri

This thread is locked; no one can reply to it. rss feed Print
Uniform distribution of points in a 3D Tri
Dario ff
Member #10,065
August 2008
avatar

{"name":"607586","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/d\/cd85544d49fcd8d2d7c2c975206427c4.png","w":400,"h":373,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/d\/cd85544d49fcd8d2d7c2c975206427c4"}607586

Given a certain Triangle in 3D (Kinda irrelevant to the problem since it can be solved in a plane with just transforming coordinates), I'd like to generate a set amount of points (which is set obviously by just dividing the area of the tri by a certain value) that are equidistant between each other, while filling up as much as possible of the given area of the triangle.

There should be some separation from the edges, otherwise when I do this on the polygon right next to it I'll get some overlapping points. I'd rather generate the points on the edges myself with another method.

{"name":"607585","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/3\/e327c180ce4f872176eb3c94121c97e1.png","w":400,"h":373,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/3\/e327c180ce4f872176eb3c94121c97e1"}607585

Generating on the edges of the triangle is simple enough, covering the surface of it is my biggest problem tho. I'm using this to generate a bunch of sampling points to take in reference for some colored lighting on objects (light reflected off surfaces), and having sampling points that cover all my meshes in a consistent manner would be of big help.

I've googled a fair bit but I haven't found much of use yet that isn't for super accurate stuff. Since this is just for calculating some lighting, accuracy is not really needed and it doesn't matter if there's much holes on the shape. It should just be fairly consistent in covering the surface in most of these polies.

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

pkrcel
Member #14,001
February 2012

Has the distribution to be tied to the linear dimensions of the triangle, or you were thinking about a predetermined density?

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Raidho36
Member #14,628
October 2012
avatar

You seem to choose complex way to solve some simple problem. What exactly are you trying to accomplish? Is it cube map? Specular light? Bump map?

Dario ff
Member #10,065
August 2008
avatar

pkrcel said:

Has the distribution to be tied to the linear dimensions of the triangle, or you were thinking about a predetermined density?

Predetermined density, constant for every tri this algorithm goes through. Ideally it should leave a fairly consistent set of points depending on the size of the tri.

Raidho36 said:

You seem to choose complex way to solve some simple problem. What exactly are you trying to accomplish? Is it cube map? Specular light? Bump map?

Global illumination for objects using an adaptive Octree that stores the irradiance map and diffuse reflection, taken from baked GI textures used in these surfaces. :P I simply need to generate these points across the surfaces of the stage to have a reference in the density of objects/reflections of each area. The rest is already coded and running as intended, but without having access to the renderer of these baked maps, the most I can do is approximation like this.

TranslatorHack 2010, a human translation chain in a.cc.
My games: [GiftCraft] - [Blocky Rhythm[SH2011]] - [Elven Revolution] - [Dune Smasher!]

Raidho36
Member #14,628
October 2012
avatar

Okay, how about you obtain these points from hardware rasterized triangle and perform the whole thing via shader?

pkrcel
Member #14,001
February 2012

Shaders seem a way to work with it....but I ain't no expert there.

Crazy Idea: you said that putting the sampling point on the edges is already okay for you; then why not use the same algorithm for a fixed set of sub-triangles?

You can obtain the sub triangles by a "scale" transform, and you can predetermine the number based on the predetermined density (alas, you determine the SMALLEST inscribed tri clone and thus the total number..).

You would end up with a point distribution starting from the centre of the triangle "expanding" outwards.

I may later add a picture to explain better myself. :-/

{"name":"607587","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/1\/e15dfe504e5d618c54861aeeacc40405.png","w":415,"h":364,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/1\/e15dfe504e5d618c54861aeeacc40405"}607587

Here it is, well...looking at it seems NOT that uniform.... :-/

But it's fairly consistent. >:(

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

J-Gamer
Member #12,491
January 2011
avatar

Couldn't you do this with barycentric coordinates?(or something like it?)

ie:
Having a triangle ABC, you might get good results when going with A + i/n*AB + j/m*AC with AB and AC being the vectors from A to B or C respectively (This is just my guess, don't know what it would look like)

" There are plenty of wonderful ideas in The Bible, but God isn't one of them." - Derezo
"If your body was a business, thought would be like micro-management and emotions would be like macro-management. If you primarily live your life with emotions, then you are prone to error on the details. If you over-think things all the time you tend to lose scope of priorities." - Mark Oates

Audric
Member #907
January 2001

Or split each triangle in two on its longest side, until all sides are smaller than what you need.

Go to: