On Fri, Mar 18, 2016 at 9:14 PM, Vasco Alexandre da Silva Costa <
vasco.co...@gmail.com> wrote:
> On Fri, Mar 18, 2016 at 1:17 PM, Param Hanji <param.catchch...@gmail.com>
> wrote:
>
>> Hello,
>>
>> On Thu, Mar 17, 2016 at 4:57 AM Vasco Alexandre da Silva Costa <
>> vasco.co...@gmail.com> wrote:
>>
>>> On Wed, Mar 16, 2016 at 9:44 PM, Param Hanji <param.catchch...@gmail.com
>>> > wrote:
>>>
>>> You will need a lot of time to port bool.c so you need to schedule
>>> appropriately. That code is rife with gotos, structs with pointers, and
>>> dynamic memory allocation. We don't want any of that in OpenCL. The sooner
>>> you start looking into that code the better. I did some patches last summer
>>> to remove many gotos from the existing code but there are still several
>>> left.
>>>
>>> I suggest you read the presentation Sean linked to so you can get an
>>> idea for what boolean operations and CSG are:
>>> http://web.iitd.ac.in/~hegde/cad/lecture/L30_solidmod_basics.pdf
>>>
>>> The main functions of interest in bool.c are rt_bool_eval, rt_boolweave,
>>> and rt_boolfinal. rt_boolweave and rt_bool_final do dynamic memory
>>> allocations with linked lists but, if you read their code carefully, the
>>> maximum output size is bounded as a function of the input size. The input
>>> is the list of intersection points. The size of the list of intersection
>>> points is already being computed by rt.cl:count_hits(). So you can pre
>>> allocate a chunk of memory with the maximum possible output size and pass
>>> that array to your functions.
>>> As for rt_bool_eval the boolean ops tree is stored as a tree of pointers
>>> to structs. Can't have that. The rt_bool_eval function uses gotos. Can't
>>> have those either.
>>>
>>
>> I'll start looking into the code as soon as i can. Is there any resource
>> I can refer to get a brief high level understanding of how ray tracing
>> occurs. I have no knowledge of computer graphics and even theoretical
>> resources pertaining to the specific functions(eval, weave) would be
>> helpful. I'll look out for some on my own too.
>>
>
> If you want a brief idea of how the ray-tracing algorithm works you can
> look at the relevant Wikipedia page. Wikipedia is a decent resource for
> basic computer graphics knowledge:
> https://en.wikipedia.org/wiki/Ray_tracing_%28graphics%29
>
> For knowing how CSG works, including the boolean ops, that lecture PDF is
> a good resource.
>
>
>> I started a patch in ANSI C to reimplement rt_bool_eval without gotos
>> with a linearized tree, stored in an array, which can be easily copied to
>> the compute device. You can find that patch here:
>> https://sourceforge.net/p/brlcad/patches/417/
>>
>>> The rt_bool_eval patch #417 is functional but it still has some warts in
>>> it.
>>>
>>>
>> I noticed that you had proposed to design a new implementation of the
>> boolean weave function in this pdf last year.
>>
>> https://drive.google.com/file/d/0B85Rkmt7rnCTZV9HNVIyZTRUMWM/view
>>
>> Was this discarded entirely? If not, does it make sense to change the way
>> weave is performed currently to facilitate easy portability to OpenCL? Or
>> should I just go about porting the existing code?
>>
>
> That PDF you linked to is from a pre-proposal which was later changed with
> output from Sean and the others. Eventually it was decided that we would
> start with a first hit ray tracer and later on work on the boolean
> evaluation proper to get working CSG. It just turns out that there was too
> much effort involved in getting the object partitioning and the rendering
> pipeline up to speed. Not to mention all those primitives... So I couldn't
> finish work on boolean evaluation before the GSoC period ended. I just did
> some cleanups (e.g. goto removal) on bool.c.
>
> Which is a good thing too or there would be little left to work on for
> this GSoC. :-)
>
> Just ignore that PDF you got from Google Drive, which is something I wrote
> before the GSoC 2015 period started, and read the advice I gave you about
> how to tackle bool.c in this maling-list which includes the knowledge I
> have now. I described a possible approach in detail here. I also said which
> functions were most important (rt_bool_eval, rt_boolweave, rt_bool_final)
>
PS: That project timeline in the PDF was shot down and I had to revise it.
There was too much time doing research in it and not enough time actually
coding. At the time I was unsure if the current bool weave algorithm
BRL-CAD uses would make sense on a GPU or not. It turns out it does make
sense but its like I said: you have to remove all the gotos, remove all
pointers inside data structures, figure out the bounds of the memory you
need a priori, and rethink the algorithm from those dynamic linked lists to
a priori bounded arrays.
--
Vasco Alexandre da Silva Costa
PhD in Computer Engineering (Computer Graphics)
Instituto Superior Técnico/University of Lisbon, Portugal
------------------------------------------------------------------------------
Transform Data into Opportunity.
Accelerate data analysis in your applications with
Intel Data Analytics Acceleration Library.
Click to learn more.
http://pubads.g.doubleclick.net/gampad/clk?id=278785231&iu=/4140
_______________________________________________
BRL-CAD Developer mailing list
brlcad-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
