# Flood filling algorithm for filling the region enclosed between intermediate points generated by Bresenham 3D Line algorithm

This topic is 398 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi,

I have a triangle,oriented in a 3D Plane i.e. I have my vertices as (x1,y1,z1) ; (x2,y2,z2) and (x3,y3,z3)

I am trying to convert this triangular facet to voxelised model i.e.

Along each edge,I am applying Bresenhams 3D Line algorithm and generating intermediate points.After generating intermediate points, I want to fill the inside region.

I have been searching for some algorithm like flood filling,but did not find anything relevant till now.

I would be really glad,if some one can provide an algorithm for achieving this.

I basically have a List of tuple for storing all the (x,y,z) data created along the edges.(generated using Brsenhams 3D Line algorithm).

Now,I want an algorithm,which creates cubes in the inside region.

##### Share on other sites

You could use any triangle rasterizer. Using orthonormal projection pixel XY and depth Z give you the voxel index in a 3D grid.

But: Pick x,y or z plane for rasterization based on what fits each triangles normal best, otherwise you get holes. (So you need to setup 3 projections, 'screen' width and height and near / far clip planes likely refer to the bounding box of your object or scene for example)

You need to be careful with subpixel accuracy to get robust and watertight results. Existing code probably uses different rounding rules for screen positions and depth. Because you alternate projections those things need to match up.

There are basically two ways of rasterization:

Easy: Bounding rect for triangle, then test each pixel to be inside all edge half spaces, e.g. https://fgiesen.wordpress.com/2013/02/08/triangle-rasterization-in-practice/

Hard: classical scanline conversation, e.g.: http://chrishecker.com/Miscellaneous_Technical_Articles

Note that Bresenham is probably a bad start as it is not subpixel accurate. (jittering edges like first Playstation versus nice edge crawling in Quake. For voxelization this is even worse as it can generate holes.)

Edit: Even simpler approach intersecting triangles with cubes: https://github.com/karimnaaji/voxelizer

Edited by JoeJ

##### Share on other sites

Hi JoeJ,

I m actually implementing everything in C#. After implenting Bresenhams 3D Line algorithm ,I am storing all the coordinates(available on the edges/boundaries) in a List of Tuple..something like List<Tuple<doubl,double,double>>.

I would be really glad,if you can let me know a  basic code,which can use the data from the list of tuple and fill all the voxels inside the triangle and also on edges.

Edited by Sri Harsha

##### Share on other sites

I tried to do something similar, but figured that filling triangles with lines doesnt really work, unless its that scanline based approach (which doesnt apply for most 3D triangles).

I suggest you go with the voxel-by-voxel intersection-tester approach. Pass an arbitrary function to your rasterizer (eg lambda), and it just checks all voxel coords in some bounding volume for an intersection (could be simple boolean, or you can allow partial/negative intersection for more possibilities) and adds it to your list if such an intersection exists.

Because it operates on a voxel-by-voxel basis, it is inherently parallel, which is always good.

It also allows rasterizing any arbitrary 3D function you want, not just a specific type of triangle.

I believe the result will have more filled voxels than absolutely necessary for watertightness (if you dont care for thickness). Those could be removed in a post processing step (not sure about quality), or maybe someone has an intersection function that is able to skip those entirely. Depends what youre doing.

If performance is a problem, you could rasterize hierarchially to avoid evaluating so many voxels (rasterize to low res grid, then use the resulting big voxel set as the bounding volume for a higher resolution grid).

##### Share on other sites

I had this problem in the past, and i ended up with a rather navie but effective algorithm, first of all, find the bounding box of your traingle, then for each dimension, compute the size of your voxel and perform a triangle-axis aligned bounding box collision test, if triangle and this box collide, then you have your voxel.

##### Share on other sites

Hi Programmer71,

Thanks for your reply.So,for example,my bounding box is a cube of size 32.Then if suppose,I fix the resolution to be 1,and then I find all the sampling points on my triangle of size 1.

Now,I will be looping through each pixel,and color the pixel on which sampling point lies.

So,in this process,if my sampling point is an intersection point of 3 or 4 pixels,will I be coloring all those pixels??

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 31
• 16
• 11
• 10
• 11
• ### Forum Statistics

• Total Topics
634113
• Total Posts
3015592
×