Uniform random point sampling on polygonal meshes
Sampling points uniformly on meshes in Blender for custom addon.
Let's define a triangle
$$ \triangle ABC $$ $$ \vec{s} = (\vec{B} - \vec{A}) u + (\vec{C} - \vec{A}) v + \vec{A} $$ $$ \vec{s} = \overrightarrow{AB} u + \overrightarrow{AC} v + \vec{A} $$
\( \vec{s} \) is inside the triangle if
If \( u + v > 1 \) then to make \( \vec{s} \) end up back inside the triangle
def random_point(A, B, C):
u = random.uniform(0.0, 1.0)
v = random.uniform(0.0, 1.0)
if (u + v) <= 1:
random_point.result = (B - A) * u + (C - A) * v + A
else:
# flip the direction
u = 1 - u
v = 1 - v
random_point.result = (B - A) * u + (C - A) * v + A
Calculate area of triangles and store them the traingle index and area in a list.
The arrow over AB and AC denotes the tail and head of vector, pointing from, to.
The cross product of two vectors has a magnitude equal to the area of a parallologram formed between them.
$$ \| \overrightarrow{AB} \times \overrightarrow{AC} \| $$When we divide the parallellogram we get the area of the triangle.
$$ \text{Area} = \frac{1}{2} \| \overrightarrow{AB} \times \overrightarrow{AC} \| = \frac{1}{2} \| (\vec{B} - \vec{A}) \times (\vec{C} - \vec{A}) \|$$We'll use this to calculate the area of each triangle on a polygon mesh. Reason we want to do this is because we want the density of the samples across the mesh to be uniform, if we don't account for this the large polygons will be sparsely filled with point and small ones will be denser.
- Find smallest area triangle, divide all other triangles by it, round to next integer.
- Convert triangles to parallellograms, sample along x and y. Flip (multiply by -1) when s > 1 to make sample end up inside the triangle again.
Gamedev Maths: point in triangle by Sebastian Lague
Probability
Simulating a coin toss:
import random
random = random.random()
probability = 0.5
if probability =< random:
print('HEADS!')
else:
print('TAILS!')
No matter how many times the coin is tossed, it will always result in a ratio that half the total number of times it is heads, the other half it's tails.
- Sample greyscale texel value in UV space to determine probability of instancing at sample point. Otherwise throw sample away.
- Probability is a 0-1 range. Generate random 0-1 number, if texel sample value is higher than random number instance gets created.
def random_point_no_uv(polypicklist):
randompoly = []
polychoice = randomizer.choice(polypicklist)
randompoly.append(polychoice)
A = randompoly[0][0]
B = randompoly[0][1]
C = randompoly[0][2]
s1 = randomizer.uniform(0.0, 1.0)
s2 = randomizer.uniform(0.0, 1.0)
if (s1 + s2) <= 1:
random_point_no_uv.result = ((((B - A) * s1) + ((C - A) * s2)) + A)
elif (s1 + s2) > 1:
random_point_no_uv(polypicklist)
return
def random_point(polypicklist, dim_x, dim_y, image_array):
randompoly = []
polychoice = randomizer.choice(polypicklist)
randompoly.append(polychoice)
A = randompoly[0][0]
B = randompoly[0][1]
C = randompoly[0][2]
A_uv = randompoly[0][3][0]
B_uv = randompoly[0][3][1]
C_uv = randompoly[0][3][2]
s1 = randomizer.uniform(0.0, 1.0)
s2 = randomizer.uniform(0.0, 1.0)
if (s1 + s2) <= 1:
chance = randomizer.uniform(0.0, 1.0)
random_uv_point = ((((B_uv - A_uv) * s1) + ((C_uv - A_uv) * s2)) + A_uv)
pixel_x = math.floor(dim_x * random_uv_point.x)
pixel_y = math.floor(dim_y * random_uv_point.y)
if image_array[pixel_x, pixel_y] > chance:
random_point.result = ((((B - A) * s1) + ((C - A) * s2)) + A)
else:
random_point(polypicklist, dim_x, dim_y, image_array)
elif (s1 + s2) > 1:
random_point(polypicklist, dim_x, dim_y, image_array)
return
Create image to sample pixels from
if (active_canvas != None) and (active_instance != None):
bpy.ops.object.select_all(action='DESELECT')
""" Choose image in UV editor """
try:
if pixelimage != (pixelimage == pixelimage):
# set selected image mask from pulldown menu as active image in UV editor
for area in bpy.context.screen.areas:
if area.type == 'IMAGE_EDITOR':
# loop through the index of names of objects
for imagename in range(len(bpy.data.images)):
if bpy.data.images[imagename].name == scene.Image:
area.spaces.active.image = bpy.data.images[imagename]
pixelimage = bpy.data.images[imagename]
""" get pixels of image """
# get pixels of image
image_width = pixelimage.size[0]
image_height = pixelimage.size[1]
rgba = list(pixelimage.pixels)
# store pixels in a list of lists
parted_rgba = [rgba[i:i+4] for i in range(0, len(rgba), 4)]
image_list = []
for floats in range(len(parted_rgba)):
image_list.append(parted_rgba[floats][0])
img_array = numpy.array(image_list)
reshape_array = img_array.reshape(image_height, image_width)
""" fix this so it's rotated properly """
rot_array = numpy.rot90(reshape_array, 3)
image_array = numpy.fliplr(rot_array)
#flip array as well
""" UV coordinates"""
if uv_layer:
uvlist = []
for v in active_canvas.data.loops:
uvlist.append(uv_layer[v.index].uv)
# use a variable for number of verts in poly later
parted_uvs = [uvlist[i:i+3] for i in range(0, len(uvlist), 3)]
except:
pass
Create cumulative density function.
# get all polygons, their areas, vertices
polylist = [] #get all polys and put them in a list
arealist = [] # list to store area of polys
for poly in active_canvas.data.polygons:
polyarea = poly.area # get area of polygon
arealist.append(polyarea)
vertlist = []
for loop_index in poly.vertices: # iterate through all vertices on every face index
# iterate through all vertices, multiply it to world space
k = (active_canvas.matrix_world * active_canvas.data.vertices[loop_index].co)
# append vertices to list
vertlist.append(k)
polylist.append(vertlist)
try:
for y in range(len(polylist)):
polylist[y].append(parted_uvs[y])
except:
pass
""" cumulative distribution: """
# sort arealist
sortedareas = arealist[:]
sortedareas.sort()
smallest_area = sortedareas[0]
cumul_distribution = []
# step through all area values in arealist and divide with the smallest area
for o in range(len(arealist)):
divide_by_smallest= math.ceil(arealist[o] / smallest_area)
cumul_distribution.append(divide_by_smallest)
polypicklist = []
for u in range(len(cumul_distribution)):
list_step = cumul_distribution[u]
for g in range(list_step):
distrib_polylist = polylist[u]
polypicklist.append(distrib_polylist)
Error that appears if UV set used extends beyond 0-1 UV space bounds.
Distribution error that was resolved by changing the order of evaluation.
# resulting random points on canvas
pointlist = []
if uv_layer != None:
# loop number of times population slider is set to
for t in range(bpy.context.scene.population):
try:
random_point(polypicklist, image_width, image_height, image_array)
pointlist.append(random_point.result)
except:
random_point_no_uv(polypicklist)
pointlist.append(random_point_no_uv.result)
# for every point
for l in pointlist:
if (bpy.context.scene.lodactive == True) and (active_camera != None):
cameradistance = ((l) - active_camera.location)
vecmagnitude((cameradistance.x), (cameradistance.y), (cameradistance.z))
# change to built in vector magnitude
if vecmagnitude.vector_magnitude <= (bpy.context.scene.camdistance):
bpy.ops.object.select_all(action='DESELECT')
#select object from pulldown menu and create instances
active_instance.select = True
bpy.ops.object.duplicate(linked=True)
# randomize scale
randomscale(scene.minscale, scene.maxscale)
# randomize rotation
randomrotation(scene.rotx, scene.roty, scene.rotz)
# pick randoms from list "facepoints" with choice, use that instead of
# random_point.result
# remove used list item after use!
bpy.ops.transform.translate(value=(l - (active_instance.location)))
bpy.ops.object.select_all(action='DESELECT')
elif vecmagnitude.vector_magnitude > (bpy.context.scene.camdistance):
#select object from pulldown menu and create instances
LODlevel_one_instance.select = True
bpy.ops.object.duplicate(linked=True)
# randomize scale
randomscale(scene.minscale, scene.maxscale)
# randomize rotation
randomrotation(scene.rotx, scene.roty, scene.rotz)
# pick randoms from list "facepoints" with choice, use that instead of
# random_point.result
# remove used list item after use!
bpy.ops.transform.translate(value=(l - (LODlevel_one_instance.location)))
bpy.ops.object.select_all(action='DESELECT')
elif (bpy.context.scene.lodactive == False):
bpy.ops.object.select_all(action='DESELECT')
#select object from pulldown menu and create instances
active_instance.select = True
bpy.ops.object.duplicate(linked=True)
# randomize scale
randomscale(scene.minscale, scene.maxscale)
# randomize rotation
randomrotation(scene.rotx, scene.roty, scene.rotz)
# pick randoms from list "facepoints" with choice, use that instead of
# random_point.result
# remove used list item after use!
bpy.ops.transform.translate(value=(l - (active_instance.location)))
bpy.ops.object.select_all(action='DESELECT')
elif (bpy.context.scene.lodactive == True) and (active_camera == None):
raise Exception("No camera selected")
else:
# print error message
raise Exception("No objects selected")
return {'FINISHED'}
Greyscale texture decides probability of sample points across mesh.
