Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon W. <jw...@gm...>]

>
> at least the variance of each contributing pixel would have to be stored
> for each pixel


Unless I miss something, the variance is possible to calculate
incrementally. You store the sum of the elements, the sum of the square of
the elements, and the number of elements contributing, all of which can be
incrementally added to. But maybe I'm missing something?

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Fri, Jun 18, 2010 at 2:05 AM, Stefan Dänzer <ste...@gm...>wrote:

> Jon,
>
> I'm not sure how one would model this as a probability density function. If
> one would want the voxel value to be the expected value of the probability
> density function, at least the variance of each contributing pixel would
> have to be stored for each pixel. Also, there needs to be a function which
> takes distance and value of a pixel as parameters and maps it into the space
> of the probability density function of a voxel.
>
> Am I missing something with the probability-density function approach?
>
> Stefan
>
> On Wed, Jun 16, 2010 at 9:13 PM, Jon Watte <jw...@gm...> wrote:
>
>> If the algorithm requires "rich" data, then no, you can't incrementally
>> compute it.
>>
>> If the algorithm ends up with a probability/density function for each
>> target voxel after each image pass, then you could just adjust the
>> probabilities based on the new data, which is possible to do incrementally.
>>
>> Sincerely,
>>
>> jw
>>
>>
>> --
>> Americans might object: there is no way we would sacrifice our living
>> standards for the benefit of people in the rest of the world. Nevertheless,
>> whether we get there willingly or not, we shall soon have lower consumption
>> rates, because our present rates are unsustainable.
>>
>>
>>
>> On Wed, Jun 16, 2010 at 4:00 AM, Stefan Dänzer <ste...@gm...>wrote:
>>
>>> Very interesting approaches here,
>>>
>>> @Manuel: I think the 3D-DDA (or the Bresenham 3D Algorithm suggested by
>>> Jon Watte) might be the way to go.
>>>
>>> @Jon Olic: The application is 3-D Ultrasound (US) reconstruction from
>>> spatially positioned and oriented 2-D US images. We basically use an optical
>>> tracking system and spatially track the US-Probe. This way we can record
>>> 3D-US volumes using a conventional 2D-US machine. Your suggested
>>> rasterization algorithm which projects the voxel center onto the image plane
>>> and calculates the distance of the projected point in the plane looks also
>>> fine, but i'm not sure if I can implement it more efficiently than a
>>> modified Bresenham 3D or 3D-DDA algorithm.
>>>
>>> @Jon Watte: If we end up weighting the contribution of each pixel in the
>>> proximity of a voxel inverse linearly to the distance to the voxel center,
>>> there might not be a way around using some extra storage for each voxel. We
>>> might end up storing distance and color of a pixel for each voxel during
>>> distance calculation and (as Manuel mentioned also) calculating the color of
>>> each voxel as a post processing step. I don't see any way how it would be
>>> possible to compose the value for each voxel incrementally. Am I missing
>>> something here?
>>>
>>> Thanks for this excellent discussion so far,
>>>
>>> Stefan
>>>
>>>
>>> On Tue, Jun 15, 2010 at 6:52 PM, Jon Watte <jw...@gm...> wrote:
>>>
>>>> You can incrementally build the 3D voxels by tracing the plane of each
>>>> contributing image, using an algorithm similar to Bresenham or Marching
>>>> Cubes. As long as the value for each voxel can be composed incrementally,
>>>> you can do this for images sequentially without needing extra storage.
>>>>
>>>> And, yes, recursive tree-like data structures are almost always used for
>>>> voxels, because > 90% of the voxel volume is either all-solid or all-open.
>>>>
>>>> Btw: if you're interested in voxel terrain, you probably should check
>>>> out the implementation in the C4 engine. It's pretty nice feature-wise, and
>>>> high quality code as well. The source license is $350, although you probably
>>>> want to be careful with the license terms; you probably can't copy and paste
>>>> code from the engine into your own code, for example.
>>>>
>>>> Sincerely,
>>>>
>>>> jw
>>>>
>>>>
>>>> --
>>>> Americans might object: there is no way we would sacrifice our living
>>>> standards for the benefit of people in the rest of the world. Nevertheless,
>>>> whether we get there willingly or not, we shall soon have lower consumption
>>>> rates, because our present rates are unsustainable.
>>>>
>>>>
>>>>
>>>> On Sun, Jun 13, 2010 at 12:10 PM, Jon Olick <jon...@gm...>wrote:
>>>>
>>>>> If its a 2D image to 3d voxel rasterization algorithm, definitely make
>>>>> a oct-tree of the voxel data and then intersect it with the 2D image plane
>>>>> (plus a depth if you want water-tight), and further clip by the extents of
>>>>> the image. Then for each voxel which is considered intersecting the 2D image
>>>>> volume, determine the color by projecting the voxel center onto the image
>>>>> plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
>>>>> image. You could then alpha the voxel based on the amount that the voxel is
>>>>> intersected with the volume. For example 20% inside = 20% alpha.
>>>>>
>>>>> On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...>wrote:
>>>>>
>>>>>> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
>>>>>> space?
>>>>>>
>>>>>>
>>>>>> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <
>>>>>> m.m...@wa...> wrote:
>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> > @Manuel: I think he wants to find the nearest point on the image to
>>>>>>> the
>>>>>>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>>>>>>
>>>>>>> I was thinking of the following:
>>>>>>> Think of each 2d scanline as a 3d ray which passes through the
>>>>>>> voxel grid. Traverse the voxel grid along the ray direction using
>>>>>>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral)
>>>>>>> into the
>>>>>>> appropriate voxel.
>>>>>>>
>>>>>>> Additionally, one could use summed area tables or somesuch to
>>>>>>> pre-filter/match
>>>>>>> the voxel and pixel footprint approximately.
>>>>>>>
>>>>>>> bye,
>>>>>>>
>>>>>>>        Manuel
>>>>>>>
>>>>>>>
>>>>>>> ------------------------------------------------------------------------------
>>>>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>>>>> lucky parental unit.  See the prize list and enter to win:
>>>>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>>>>> _______________________________________________
>>>>>>> GDAlgorithms-list mailing list
>>>>>>> GDA...@li...
>>>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>>>> Archives:
>>>>>>>
>>>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>>> lucky parental unit.  See the prize list and enter to win:
>>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>>> _______________________________________________
>>>>> GDAlgorithms-list mailing list
>>>>> GDA...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>> Archives:
>>>>>
>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>> lucky parental unit.  See the prize list and enter to win:
>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>>
>>> --
>>> --
>>> Stefan Daenzer
>>> Körnerplatz 8
>>> 04107 Leipzig
>>>
>>> Tel.: +49-176-61157550
>>>
>>>
>>> "Work like you don't need the money, love like you've never been hurt and
>>> dance like no one is watching." - Randall G Leighton
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>> lucky parental unit.  See the prize list and enter to win:
>>> http://p.sf.net/sfu/thinkgeek-promo
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>> lucky parental unit.  See the prize list and enter to win:
>> http://p.sf.net/sfu/thinkgeek-promo
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> --
> Stefan Daenzer
> Körnerplatz 8
> 04107 Leipzig
>
> Tel.: +49-176-61157550
>
> "Work like you don't need the money, love like you've never been hurt and
> dance like no one is watching." - Randall G Leighton
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>