CODEWITHSUNDEEP
pythonmayapymel
Peter
Peter

Reputation: 3495

How to find separate objects in a list of 3D coordinates

I started giving a basic voxel type script a shot, where it'll look in the 6 directions adjancent to a point n draw a plane across any side that doesn't have anything next to it. Then I can combine the planes and it'll make an object.

This works nicely when it's all one object, but if there's space between the objects, it still combines it all as one object. With the list of coordinates being like (x,y,z), how would I split it based on what is connected? The only way I can think of would be very processing heavy and would involve checking every free space around an object while building it up until there is none left, but I imagine there should probably be a better way.

For the record, this isn't actually going to be used for anything, it's just for fun to see if I could do it

import pymel.core as py

directions = [[1, 0, 0], [-1, 0, 0], [0, 1, 0], [0, -1, 0], [0, 0, 1], [0, 0, -1]]

grid = {}
grid[(0,0,0)] = 1
grid[(1,0,0)] = 0
grid[(-1,0,0)] = 1
grid[(0,1,0)] = 1


for originalCoordinate in grid.keys():
    adjacentCoordinates = [tuple( sum( j ) for j in zip( i, originalCoordinate ) ) for i in directions]
    blockHere = grid[originalCoordinate]
    if blockHere:
        for newCoordinate in adjacentCoordinates:
            if not grid.get( newCoordinate, 0 ):
                newDirection = tuple( i[1]-i[0] for i in zip( originalCoordinate, newCoordinate ) )
                newSide = py.polyPlane( width = 1, height = 1, sx = 1, sy = 1 )[0]
                sideLocation = list( originalCoordinate )
                sideRotation = [0, 0, 0]
                if newDirection[0]:
                    if newDirection[0] > 0:
                        print originalCoordinate, "Facing X"
                        sideLocation[0] += 0.5
                        sideRotation[2] += -90
                    else:
                        print originalCoordinate, "Facing -X"
                        sideLocation[0] += -0.5
                        sideRotation[2] += 90
                if newDirection[1]:
                    if newDirection[1] > 0:
                        print originalCoordinate, "Facing Y"
                        sideLocation[1] += 0.5
                        sideLocation[1] += 0
                    else:
                        print originalCoordinate, "Facing -Y"
                        sideLocation[1] += -0.5
                        sideLocation[1] += 180
                if newDirection[2]:
                    if newDirection[2] > 0:
                        sideLocation[2] += 0.5
                        sideRotation[0] += 90
                        print originalCoordinate, "Facing Z"
                    else:
                        sideLocation[2] += -0.5
                        sideRotation[0] += -90
                        print originalCoordinate, "Facing -Z"
                py.move( newSide, sideLocation )
                py.rotate( newSide, sideRotation )

Upvotes: 1

Views: 433

Answers (1)

theodox
theodox

Reputation: 12208

The usual method for searching a 3-d regular grid like this is an octree. The basic idea is that you divide your space into powers-of-two cubes: each cube becomes 8 smaller cubes of half size, and reports the presence of objects in its children. By recursively subdividing this way you can quickly eliminate checks for large areas of the world that are empty. It's not too difficult to implement because it's fundamentally recursive: if you get it working for two levels of subdivision you've got the ability to go deeper as needed. There are several python implementations on github to look at, I haven't got one to recommend.

Upvotes: 1

Related Questions