Jump to content
  • Advertisement
Sri Harsha

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

Recommended Posts



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 this post

Link to post
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 this post

Link to post
Share on other sites

Hi JoeJ,

Thanks a lot for your quick reply.I went through the above links.I need some more information to start on with it.

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 this post

Link to post
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 this post

Link to post
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 this post

Link to post
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??

Thanks in Advance


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
  • Advertisement
  • Popular Tags

  • Similar Content

    • By JoshuaFraser
      Hi and thanks for reading, I have an issue with this reactive crosshair script, everything works fine until I start changing the offset. Give the script a go and you will see what I mean, when I do SetOffset(0f); it doesnt always set back to the origional state, if anyone can spot a fix I'd be super appreciative!
      using System.Collections; using System.Collections.Generic; using UnityEngine; public class ReactiveCrosshair : MonoBehaviour { [SerializeField] GameObject c_limb_prefab; private float center_offset = 0f; private float current_offset = 0f; private float max_offset = .5f; private int number_of_limbs = 4; private float limb_length = .05f; private float limb_width = .005f; private List<GameObject> c_limbs = new List<GameObject>(); public void SetupCrosshair(){ for (int i = 0; i < number_of_limbs; i++) { GameObject line_go = (GameObject)Instantiate (c_limb_prefab); line_go.transform.SetParent (this.transform); Vector3 limb_pos = new Vector3 (0f,0f,0f); //line_go.transform.position = limb_pos; line_go.transform.localPosition = limb_pos; LineRenderer line = line_go.GetComponent<LineRenderer>(); line.startWidth = limb_width; line.positionCount = 2; line.SetPosition (0, line_go.transform.localPosition + new Vector3(center_offset, 0f, 0f)); line.SetPosition (1, line_go.transform.localPosition + new Vector3(center_offset + limb_length, 0f, 0f)); line.useWorldSpace = false; c_limbs.Add(line_go.gameObject); } if (c_limbs != null) { OrientLimbs (); SetOffset (0f); } } public void OrientLimbs(){ for (int i = 0; i < c_limbs.Count; i++) { float rotation_step = 360f / (float)c_limbs.Count; c_limbs [i].transform.RotateAround (c_limbs[i].transform.position, c_limbs[i].transform.forward, 90f + (rotation_step * (float)i)); } } public void SetOffset(float _current_spread){ float offset = Mathf.Lerp (0f, max_offset, _current_spread); for (int i = 0; i < number_of_limbs; i++) { if (offset > current_offset) { Vector3 pos = c_limbs [i].transform.position + (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } if (offset < current_offset) { Vector3 pos = c_limbs [i].transform.position - (c_limbs [i].transform.TransformDirection (Vector3.right) * offset); c_limbs [i].transform.position = pos; } } Debug.Log ("SetOffset() offset: " + offset.ToString () + " _current_spread: " + _current_spread.ToString() + " localPos: " + c_limbs[1].transform.localPosition); current_offset = offset; } }  
    • By Woody Stevens
      I am looking for a TCP or HTTP networking library similar to Lidgren (UDP).
      This is primarily for sending game map data and potentially other large messages from Server to Client.
      I do want to keep Lidgren for my chat messages, player position, small fast updates etc. I especially love the flow of data and the library usage in general, so any libraries of a similar style would be excellent. Preferably something open source, free and reliable.
      I also must be able to swap between localhost and an ip address with ease, like Lidgren, as I run a server for singleplayer/mp/lan.
      My game maps are similar to minecraft, but it is 2d and only one Z-level, so i'm sending a jagged array of Tile object data (currently only enum TileID.Grass) down the pipe to the Client. Problem is if i'm sending a large map 1024 x 1024 tiles down the to client that's quite a lot of data, and Lidgren is relatively slow to build the writes (before the message is even sent!). It is fine when i'm using smaller maps < 512 x 512 ( xTiles * yTiles ).

      I know about chunking and will look into implementing this later, whilst taking into account the user's position in the world to only send nearby chunks.
      An example of my code that can be slow:
      private void WriteWorld(NetOutgoingMessage outgoing) { try { var world = WorldManager.Instance.CurrentWorld; outgoing.Write(world.XTiles); outgoing.Write(world.YTiles); for (int x = 0; x < world.XTiles; x++) { for (int y = 0; y < world.YTiles; y++) { // Write Tile obj data outgoing.Write((int)world.Tiles[x][y]); // <-------- Slow here when xTiles and yTiles are each > 512 ! } } } catch (Exception ex) { // log send error } }  
      I'd love to hear from you guys, especially if any of you have come across a similar challenge.
    • By ethancodes
      I'm working on a system for my game that will allow the player to stack pick ups in a queue. As one pick up expires, the next automatically activates. I'm having an issue though where if I pick up the first one, it activates fine, but if i pick up a second directly after it, it overrides the first one, activates the second one, and then once it has run it's course, everything goes back to normal gameplay, no first pick up. I'm not sure why this is happening. Hopefully someone can spot what I'm doing wrong in my code.
      Here is the code for the pick up manager:
      // Update is called once per frame void Update () { if (pickUpQueue.Count != 0 && !pickUpActive) { pickUpActive = true; pickUpQueue[0].ActivatePickUp(); } DeactivatePickUp(); } void DeactivatePickUp () { if (pickUpQueue.Count != 0 && pickUpActive) { Destroy (pickUpQueue [0]); pickUpQueue.RemoveAt (0); pickUpActive = false; } } And here is the PickUp:
      public override void ActivatePickUp () { ball.GetComponent<Ball>().Speed = 2.0f; //increase ball speed... ball.GetComponent<Ball>().StartCoroutine(timer); //...set time that power up is active }  
      There is also a Base Pick Up:
      public void OnCollisionEnter2D (Collision2D collision) { Vector2 tweak = new Vector2 (Random.Range(0f, 0.2f),Random.Range(0f, 0.2f)); this.gameObject.GetComponent<Rigidbody2D>().velocity += tweak; //if the pickup makes contact with the paddle or ball.... if (collision.gameObject.tag == "Paddle" || collision.gameObject.tag == "Ball") { GameObject.FindObjectOfType<GameManager>().GetComponent<PickUpManager>().pickUpQueue.Add(this); Destroy(gameObject); //...and finally destroy power up object } } As a side note, I am trying to find a solution to this that will work for all of my pickups. Some pickups are ammo based, some are timed. 
    • By Hellados
      Hello guys, my name is Giorgi and i'm newbie game developer i'm learning Pixel art and after pixel art  i want learn C# and don't know how and where start i'm bad with programming language and know only HTML/CSS
    • By NanaMarfo
      Hello Everyone!
      I am looking for a small team to do a rendering project with me. The roles I need are:
      -Character Modeller
      -Environment Designer
      -Environment Modeller(Found)
      You can use this in your portfolio and you will be credited at the end.
      If you are interested, please email me at marfo343@gmail.com. Thank you!
    • By D34DPOOL
      Edit Your Profile D34DPOOL 0 Threads 0 Updates 0 Messages Network Mod DB GameFront Sign Out Add jobEdit jobDeleteC# Programmer for a Unity FPS at Anywhere   Programmers located Anywhere.
      Posted by D34DPOOL on May 20th, 2018
      Hello, my name is Mason, and I've been working on a Quake style arena shooter about destroying boxes on and off for about a year now. I have a proof of concept with all of the basic features, but as an artist with little programming skill I've reached the end of my abilities as a programmer haha. I need someone to help fix bugs, optomize code, and to implent new features into the game. As a programmer you will have creative freedom to suggest new features and modes to add into the game if you choose to, I'm usually very open to suggestions :).
      What is required:
      Skill using C#
      Experience with Unity
      Experience using UNET (since it is a multiplayer game), or the effort and ability to learn it
      Since the game currently has no funding, we can split whatever revenue the game makes in the future. However if you would perfer I can create 2D and/or 3D assets for whatever you need in return for your time and work.
      It's a very open and chill enviornment, where you'll have relative creative freedom. I hope you are interested in joining the team, and have a good day!
      To apply email me at mangemason@yahoo.com
    • By Andrew Parkes
      I am a talented 2D/3D artist with 3 years animation working experience and a Degree in Illustration and Animation. I have won a world-wide art competition hosted by SFX magazine and am looking to develop a survival game. I have some knowledge of C sharp and have notes for a survival based game with flexible storyline and PVP. Looking for developers to team up with. I can create models, animations and artwork and I have beginner knowledge of C sharp with Unity. The idea is Inventory menu based gameplay and is inspired by games like DAYZ.
      Here is some early sci-fi concept art to give you an idea of the work level. Hope to work with like minded people and create something special. email me andrewparkesanim@gmail.com.
      Developers who share the same passion please contact me, or if you have a similar project and want me to join your team email me. 
      Many thanks, Andrew.

    • By thecheeselover
      I made this post on Reddit. I need ideas and information on how to create the ground mesh for my specifications.
  • Advertisement
  • Popular Now

  • Forum Statistics

    • Total Topics
    • Total Posts

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!