• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By Pixelated_Nate
      Hello all!
      I'm currently designing a 2D, Puzzle/Action RPG, in a similar vein to Legend of Zelda: Link to The Past, in Unity and require a Programmer partner in which to work with me.
      The project, yet to be titled, will feature:
      A semi-open world, represented through pixel art, in which the player traverses to enter dungeons and advance the story. A handful of side-quests that require memorizing details and using puzzle-mechanics. A fast-paced, melee combat system that will include dodging, blocking and utilizing four different attack types that can be switched on the fly. A simple inventory of "Key Items" to be used in order to advance the story. Day & Night system and Weather Effects, with weather effecting combat.  A very simple Dialogue System to convey information via colored text. Saving/Loading via exporting and importing a physical save file. Majority of the project is already planned out, with plans to release commercially and splitting the profits equally among the two of us. 
      I would request that the applicant is able to work semi-independently, following an outline, and that they have experience in both C# programming  *and* putting those scripts to use inside Unity, whilst I will be creating the Art, Music/SFX and doing Level Design (Though if you are also comfortable in assisting me with these, I wouldn't be opposed.).
      Work will be shared in either Github or Unity Collab (Applicants preference), with communication done via Discord. 
      For more information and to apply, please contact me at nathan.jenkins1012@gmail.com
      Thanks for reading! 
    • By AndyCo
      I`m looking for some project to boost up my portfolio, I`m not a pro but I`m not bad at all.
      Feel free to contact me.
    • By Just4lol
      I'm looking for my dream teammate(s) to help me work on my Unity game. I still dont know where Im going with that project but I want to make a good final product that I would be able to sell or publish it for free on Steam.  Here a video of the prototype (The only thing I dint made is the skybox) https://www.youtube.com/watch?v=y2Otmt9jRkc
      My discord : Just4lol#46982
      I want somone at least as competent as me : 
      - I want somone with at least one year of experience in Unity (already worked with scriptable object and know oop).
      - Already worked with shaders or can do editors tools is a plus.
      - Can do 3d models in Blender or can do 2d art for the ui or particles effects.
      - Can make soundtracks or sound effects a bonus.
      Im a french Canadian so mind my english I will do my best to edit any errors I see. 
    • By lucky6969b
      I want to calculate the position of the camera, but I always get a vector of zeros.

      D3DXMATRIX viewMat; pDev->GetTransform(D3DTS_VIEW, &viewMat); D3DXMatrixInverse(&viewMat, NULL, &viewMat); D3DXVECTOR3 camPos(viewMat._41, viewMat._42, viewMat._43); log->Write( L"Camera Position: %f %f %f\n", camPos.x, camPos.y, camPos.z);

      Could anyone please shed some lights on this?
    • By bsudheer
      Leap Leap Leap! is a fast-paced, endless running game where you leap from rooftop to rooftop in a computer simulated world.

      This is a free run game and get excited by this fabulous computer simulated world of skyscrapers and surreal colors in parallax effect. On your way, collect cubes and revival points as many as you can to make a long run.

      Features of Leap Leap Leap:
      -Option of two themes: Black or White.
      -Simple one touch gameplay.
      -Attractive art.
      -Effective use of parallax.
      To Download the game:
      Playstore: https://play.google.com/store/apps/details?id=com.avakaigames.leap
      Appstore: https://itunes.apple.com/us/app/leap-leap-leap/id683764406?mt=8

  • Advertisement
  • Advertisement

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