Point grid on 3D polygon. Algorithm.

[kroko]

Good day!

This is my first post here, hope this is the right section.

I'm stuck in between some 3d points. Probably the reason is that my math knowledge has worsened over years and thus cannot see the solution or it's just plain stupidity Although I have revised topics in geometry and math in general that could help solving the problem - no clean solution has been found yet.
Note: this is a sketch for a probable app, so I'm using stripped down java in processing.org environment. Anyways - the question is a bout algorithm, not specific language.

The app reads in OBJ file.
In return I get:
•*mutable ArrayList
• ArrayList contains n PVector[] arrays
Each PVector[] array contains point coordinates for a face in obj model. Basically PVector[] is the same as Vector3f[] would be.

For clarity let us assume that OBJ model contains only one face: ArrayList then would have size==1 and the only PVector[] showing all vertexes of a poly would look like
[0] [ -64.84054, -154.23578, 218.20401 ]
[1] [ -88.10743, -208.14879, 15.154615 ]
[2] [ 2.03344, -128.74051, 183.98877 ]
[3] [ 125.528145, -120.85528, -66.2497 ]
[4] [ 116.617676, -95.49965, 75.52347 ]
[5] [ 253.30537, -9.454201, 167.5301 ]
[6] [ 264.19238, -50.72506, -54.801544 ]
[7] [ 82.04771, -149.59639, -102.055 ]
[8] [ 175.0281, -150.58365, -323.50552 ]
[9] [ -38.72393, -249.22241, -295.97183 ]
[10] [ -102.96771, -240.9769, -106.86887 ]
[11] [ -246.85388, -311.42358, -107.65498 ]
[12] [ -193.96344, -255.13881, 37.660084 ]
[13] [ -306.5557, -271.1468, 223.72104 ]
[14] [ -118.29632, -174.61548, 245.55397 ]

Visually


Forget the cube in the pic it's only to show that the polygon can be rotated against any axis.
Polygon can be concave and convex. It cannot have holes.

What I'm trying to achieve:

Construct coordinates for points:
• that belongs to the polygon plane
• AND is inside polygon "borders"
• AND that are regularly distributed as a grid where step is some variable S

A polygon filled with such a grid (perspective view)


The visual representation for the app is one of the goal, but each point of the grid has to be known. I mean - i need those point coord. for further calculus, it's not that the solution can be only visual - i.e. texture mapping on that poly.

As for now everything works in "2D" - if the poly is parallel to any of the planes that can be constructed from 2 axes (x-y, y-z, x-z). In this case I construct a bounding rectangle for the poly, then using step S walk through inside the rect and check if the point is inside poly using Jordan Curve Theorem.
As I start working with a poly which surface normal isn't parallel/perpendicular to any axis.... I'm drowning into loops loops loops...

Resumē:
Does anybody has an idea for an algorithm, that could create 3D points that are distributed in a grid with some step S inside a 3D poly.
The only thing known* about poly is it's
- vertex coordinates
- and the order (the PVector[] array contains sequential vertex coordinates, "walking along the perimeter").

Many many thanks in advance,
Kroko


* Meaning that for a poly (triangle) ABC we also know
• vectors belonging and parallel to poly plane - AB & BC & ..
• surface normal - cross product of any two vectors (that are not parallel) belonging to the poly
• plane equation

[Zachm]

Originally Posted by kroko

As for now everything works in "2D" - if the poly is parallel to any of the planes that can be constructed from 2 axes (x-y, y-z, x-z). In this case I construct a bounding rectangle for the poly, then using step S walk through inside the rect and check if the point is inside poly using Jordan Curve Theorem.
As I start working with a poly which surface normal isn't parallel/perpendicular to any axis.... I'm drowning into loops loops loops...

As you state you can solve the problem if the poly is parallel to any 2-axis plane of the x,y and z axes, why not just:
1. Transform the poly so it would be aligned with one of those axes.
2. Run the algorithm you stated to work fine in "2D".
3. Transform the resulting "grid points" back onto the original polygon surface, using the inverse transformation of the one used in step 1.

Regards,
Zachm